השחיל יישומי מבנה נתונים LIFO בטוחים
1. הקדמה
במדריך זה, נדון באפשרויות שונות ליישומי מבנה נתונים LIFO הבטוחים בחוטים.
במבנה הנתונים של LIFO, אלמנטים מוכנסים ונשלפים על פי עקרון Last-in-First-Out. משמעות הדבר היא שהאלמנט שהוכנס לאחרונה מאוחזר תחילה.
במדעי המחשב, לַעֲרוֹם הוא המונח המשמש להתייחסות למבנה נתונים כזה.
א לַעֲרוֹם הוא שימושי להתמודד עם כמה בעיות מעניינות כמו הערכת ביטוי, יישום פעולות ביטול וכו 'מכיוון שניתן להשתמש בו בסביבות ביצוע במקביל, ייתכן שיהיה עלינו להפוך אותו לבטוח חוטים.
2. הבנה ערימות
בעיקרון, א לַעֲרוֹם חייב ליישם את השיטות הבאות:
- לִדחוֹף() - הוסף אלמנט בחלקו העליון
- פּוֹפּ() - להביא ולהסיר את האלמנט העליון
- לְהָצִיץ() - להביא את האלמנט מבלי להסיר אותו מהמיכל הבסיסי
כפי שנדון קודם, נניח שאנחנו רוצים מנוע לעיבוד פקודות.
במערכת זו, ביטול פקודות שבוצעו הוא תכונה חשובה.
באופן כללי, כל הפקודות נדחקות אל הערימה ואז פשוט ניתן ליישם את פעולת הביטול:
- פּוֹפּ() שיטה להשיג את הפקודה האחרונה שבוצעה
- תתקשר ל לבטל() שיטה על אובייקט הפקודה
3. הבנת בטיחות חוטים ב ערימות
אם מבנה נתונים אינו בטוח בשרשור, כאשר נגיש אליו במקביל, ייתכן שיהיה לו תנאי מרוץ.
תנאי המירוץ, בקצרה, מתרחשים כאשר הביצוע הנכון של הקוד תלוי בתזמון ורצף החוטים. זה קורה בעיקר אם יותר מחוט אחד חולק את מבנה הנתונים ומבנה זה אינו מיועד למטרה זו.
בואו נבדוק שיטה למטה משיעור אוסף Java, ArrayDeque:
סקר E ציבורי ראשון () {int h = head; תוצאה E = (E) אלמנטים [h]; // ... פעולות אחרות לניהול ספרים הוסרו, לשם פשטות head = (h + 1) & (elements.length - 1); תוצאת החזרה; }כדי להסביר את מצב הגזע הפוטנציאלי בקוד לעיל, נניח שני שרשורים שמבצעים קוד זה כפי שניתן ברצף שלהלן:
- השרשור הראשון מבצע את השורה השלישית: מגדיר את אובייקט התוצאה עם האלמנט באינדקס 'ראש'
- החוט השני מבצע את השורה השלישית: קובע את אובייקט התוצאה עם האלמנט ב'ראש 'האינדקס
- השרשור הראשון מבצע את השורה החמישית: מאפס את אינדקס 'ראש' לאלמנט הבא במערך הגיבוי
- החוט השני מבצע את השורה החמישית: מאפס את 'אינדקס' הראש לאלמנט הבא במערך הגיבוי
אופס! כעת, שתי ההוצאות להורג יחזירו את אותו אובייקט תוצאה.
כדי להימנע מתנאי מרוץ כאלה, במקרה זה, חוט לא אמור לבצע את השורה הראשונה עד שהחוט השני יסתיים באיפוס מדד ה'ראש 'בשורה החמישית. במילים אחרות, גישה לאלמנט באינדקס 'ראש' ואיפוס אינדקס 'ראש' צריכות להתרחש באופן אטומי עבור חוט.
ברור שבמקרה זה, ביצוע נכון של הקוד תלוי בתזמון השרשור ולכן הוא אינו בטוח בשרשור.
4. ערימות חסינות הברגה באמצעות מנעולים
בחלק זה נדון בשתי אפשרויות אפשריות ליישומים קונקרטיים של כספת חוט לַעֲרוֹם.
בפרט, נכסה את Java לַעֲרוֹם ומעוטר בחוט חוט ArrayDeque.
שניהם משתמשים במנעולים לצורך גישה בלעדית.
4.1. שימוש בג'אווה לַעֲרוֹם
לאוספי Java יש הטמעה מדור קודם לאבטחת חוטים לַעֲרוֹם, מבוסס על וֶקטוֹר שהוא בעצם גרסה מסונכרנת של רשימת מערך.
עם זאת, המסמך הרשמי עצמו מציע לשקול להשתמש ArrayDeque. מכאן שלא נפרט יותר מדי.
למרות שג'אווה לַעֲרוֹם הוא חוט בטוח וישר לשימוש, ישנם חסרונות גדולים עם מעמד זה:
- אין לו תמיכה בהגדרת הקיבולת הראשונית
- הוא משתמש במנעולים לכל הפעולות. זה עלול לפגוע בביצועים לביצועי הברגה בודדת.
4.2. באמצעות ArrayDeque
משתמש ב דק ממשק הוא הגישה הנוחה ביותר עבור מבני נתונים של LIFO מכיוון שהוא מספק את כל פעולות הערימה הנדרשות.ArrayDeque הוא יישום קונקרטי כזה.
מכיוון שהוא אינו משתמש במנעולים לצורך הפעולות, הוצאות להורג בעל הברגה אחת יעבדו בסדר גמור. אבל עבור הוצאות להורג מרובות שרשור, זה בעייתי.
עם זאת, אנו יכולים ליישם מעצב סנכרון עבור ArrayDeque. אם כי זה מתפקד באופן דומה לזה של Java Collection Framework לַעֲרוֹם הכיתה, הנושא החשוב של לַעֲרוֹם הכיתה, היעדר הגדרת קיבולת ראשונית, נפתרת.
בואו נסתכל על הכיתה הזו:
מחלקה ציבורית DequeBasedSynchronizedStack {// Deque פנימי שמתקשט לסינכרון. פרטית ArrayDeque dequeStore; ציבורי DequeBasedSynchronizedStack (int initialCapacity) {this.dequeStore = ArrayDeque חדש (initialCapacity); } DequeBasedSynchronizedStack () ציבורי () {dequeStore = ArrayDeque חדש (); } פופ T מסונכרן פומבי () {להחזיר this.dequeStore.pop (); } דחיקת חלל ציבורית מסונכרנת (אלמנט T) {this.dequeStore.push (אלמנט); } הצצה מסונכרנת ציבורית () {להחזיר this.dequeStore.peek (); } גודל int מסונכרן ציבורי () {להחזיר this.dequeStore.size (); }}שימו לב שהפתרון שלנו לא מיושם דק עצמו לפשטות, מכיוון שהוא מכיל הרבה יותר שיטות.
כמו כן, גויאבה מכיל SynchronizedDeque שהוא יישום מוכן לייצור של מעוטר ArrayDeque.
5. ערימות חסינות הברגה ללא נעילה
ConcurrentLinkedDeque הוא יישום ללא נעילה של דק מִמְשָׁק. יישום זה הוא לגמרי חוט בטיחותי מכיוון שהוא משתמש באלגוריתם יעיל ללא נעילה.
יישומים ללא נעילה הם חסינים מפני הנושאים הבאים, בניגוד לבעיות מבוססות נעילה.
- היפוך עדיפות - זה קורה כאשר הברגה בעדיפות נמוכה אוחזת במנעול הדרוש לברגה בעדיפות גבוהה. זה עלול לגרום לחסימת העדיפות הגבוהה
- חסמים - זה קורה כאשר שרשורים שונים נועלים את אותה קבוצת משאבים בסדר אחר.
נוסף על כך, ליישומים ללא נעילה יש כמה תכונות שהופכות אותם למושלמים לשימוש בסביבות בודדות וברב-הברגה.
- עבור מבני נתונים לא משותפים ועבור גישה עם הברגה אחת, הביצועים יהיו בקנה אחד עם ArrayDeque
- עבור מבני נתונים משותפים, ביצועים משתנה בהתאם למספר הנושאים שניגשים אליו בו זמנית.
ומבחינת השימושיות, זה לא שונה מ ArrayDeque כאשר שניהם מיישמים את דק מִמְשָׁק.
6. מסקנה
במאמר זה דנו ב לַעֲרוֹם מבנה הנתונים ויתרונותיו בתכנון מערכות כמו מנוע עיבוד פיקוד ומעריך ביטוי.
כמו כן, ניתחנו יישומי מחסנית שונים במסגרת אוספי ג'אווה ודנו בביצועיהם ובניואציות בטיחות החוטים.
כרגיל, ניתן למצוא דוגמאות קוד ב- GitHub.
