streamalism.org

1. הקדמה

במדריך זה נלמד מהם מבני נתונים שאינם חוסמים ולמה הם אלטרנטיבה חשובה למבני נתונים מקבילים מבוססי נעילה.

ראשית, נעבור על כמה מונחים כמו ללא מכשולים, ללא נעילה, ו ללא המתנה.

שנית, נסתכל על אבני הבניין הבסיסיות של אלגוריתמים שאינם חוסמים כמו CAS (השווה והחלפה).

שלישית, נסתכל על יישום של תור נעול בג'אווה, ולבסוף נתווה גישה כיצד להשיג המתן-חופש.

2. נעל נגד רעב

ראשית, בואו נסתכל על ההבדל בין חוט חסום לרעב.

בתמונה שלעיל, חוט 2 רוכש נעילה על מבנה הנתונים. כאשר חוט 1 מנסה לרכוש גם מנעול, עליו להמתין עד שחוט 2 ישחרר את המנעול; זה לא ימשיך לפני שהוא יכול לקבל את הנעילה. אם נשעה את הברגה 2 בזמן שהיא מחזיקה את הנעילה, חוט 1 יצטרך לחכות לנצח.

התמונה הבאה ממחישה רעב חוטים:

כאן, חוט 2 ניגש למבנה הנתונים אך אינו רוכש נעילה. שרשור 1 מנסה לגשת למבנה הנתונים בו זמנית, מזהה את הגישה בו זמנית וחוזר מיד, מודיע לשרשור שהוא לא יכול להשלים (אדום) את הפעולה. לאחר מכן חוט 1 ינסה שוב עד שהוא יצליח להשלים את הפעולה (ירוק).

היתרון בגישה זו הוא שאיננו זקוקים למנעול. עם זאת, מה שיכול לקרות הוא שאם חוט 2 (או שרשורים אחרים) ניגשים למבנה הנתונים בתדירות גבוהה, אז חוט 1 זקוק למספר גדול של ניסיונות עד שהוא יצליח לבסוף. אנחנו קוראים לזה רעב.

בהמשך נראה כיצד ה השווה והחלפה פעולה משיגה גישה שאינה חוסמת.

3. סוגי מבני נתונים שאינם חוסמים

אנו יכולים להבחין בין שלוש רמות של מבני נתונים שאינם חוסמים.

3.1. ללא מכשולים

חופש חסימה הוא הצורה החלשה ביותר של מבנה נתונים שאינו חוסם. כאן אנו דורשים כי מובחן מוביל לשרשור אם כל שאר הנושאים מושעים.

ליתר דיוק, חוט לא ימשיך להרעיב אם כל שאר הנושאים מושעים. זה שונה משימוש במנעולים במובן זה, שאם החוט המתין לנעילה וחוט המחזיק את המנעול תלוי, חוט ההמתנה יחכה לנצח.

3.2. ללא נעילה

מבנה נתונים מספק חופש נעילה אם, בכל עת, לפחות שרשור אחד יכול להמשיך. כל שאר החוטים עשויים להיות רעבים. ההבדל לחוסם-חופש הוא שיש לפחות חוט אחד שאינו מורעב גם אם אין חוטים מושעים.

3.3. ללא המתנה

מבנה נתונים הוא ללא המתנה אם הוא ללא נעילה וכל מובטח מובטח שימשיך לאחר מספר סופי של צעדים, כלומר, שרשורים לא ירעבו למספר צעדים "בלתי סבירים".

3.4. סיכום

בואו נסכם את ההגדרות הללו בייצוג גרפי:

החלק הראשון של התמונה מציג חופש חסימה כאשר חוט 1 (חוט עליון) יכול להמשיך (חץ ירוק) ברגע שאנחנו משעים את החוטים האחרים (בתחתית בצהוב).

החלק האמצעי מראה חופש נעילה. לפחות חוט 1 יכול להתקדם בעוד שאחרים עשויים להרעיב (חץ אדום).

החלק האחרון מראה חופש המתנה. כאן אנו מתחייבים כי חוט 1 יכול להמשיך (חץ ירוק) לאחר תקופת רעב מסוימת (חיצים אדומים).

4. פרימיטיבים שאינם חוסמים

בחלק זה נבחן שלוש פעולות בסיסיות המסייעות לנו לבנות פעולות ללא נעילה על מבני נתונים.

4.1. השווה והחלפה

אחת הפעולות הבסיסיות המשמשות למניעת נעילה היא השווה והחלפה פעולת (CAS).

הרעיון של השוואה והחלפה הוא, שמשתנה מתעדכן רק אם עדיין יש לו ערך זהה לזמן בו הבאנו את ערך המשתנה מהזיכרון הראשי. CAS הוא פעולה אטומית, כלומר אחזור ועדכון יחד הם פעולה אחת:

כאן, שני האשכולות מביאים את הערך 3 מהזיכרון הראשי. חוט 2 מצליח (ירוק) ומעדכן את המשתנה ל- 8. מכיוון שה- CAS הראשון לפי חוט 1 מצפה שהערך יהיה עדיין 3, ה- CAS נכשל (אדום). לכן, חוט 1 מביא שוב את הערך, וה- CAS השני מצליח.

הדבר החשוב כאן הוא ש- CAS אינו רוכש נעילה במבנה הנתונים אלא חוזר נָכוֹן אם העדכון הצליח, אחרת הוא חוזר שֶׁקֶר.

קטע הקוד הבא מתאר כיצד CAS עובד:

ערך int נדיף; cas בוליאני (int expectValue, int newValue) {if (value == expectedValue) {value = newValue; לחזור אמיתי; } להחזיר שקר; }

אנו מעדכנים את הערך רק בערך החדש אם עדיין יש לו את הערך הצפוי, אחרת הוא מחזיר שֶׁקֶר. קטע הקוד הבא מראה כיצד ניתן לקרוא ל- CAS:

בטל testCas () {int v = value; int x = v + 1; בעוד (! cas (v, x)) {v = value; x = v + 1; }}

אנו מנסים לעדכן את הערך שלנו עד שפעולת ה- CAS תצליח, כלומר תחזור נָכוֹן.

עם זאת, יתכן שחוט נתקע ברעב. זה יכול לקרות אם שרשורים אחרים מבצעים CAS על אותו משתנה בו זמנית, כך שהפעולה לעולם לא תצליח עבור שרשור מסוים (או ייקח זמן לא סביר להצליח). ובכל זאת, אם השווה והחלפה נכשל, אנו יודעים שחוט אחר הצליח, ובכך אנו מבטיחים גם התקדמות גלובלית, כנדרש לחופש המנעולים.

חשוב לציין כי החומרה צריכה לתמוך השווה והחלפה, להפוך אותו לפעולה אטומית באמת ללא שימוש בנעילה.

Java מספקת יישום של השווה והחלפה בכיתה sun.misc. לא בטוח. עם זאת, ברוב המקרים, אנחנו לא צריכים להשתמש בכיתה זו ישירות, אלא במשתנים אטומיים.

יתר על כן, השווה והחלפה אינו מונע את בעיית A-B-A. אנו נסתכל על כך בחלק הבא.

4.2. טעינת קישור / מותנה בחנות

אלטרנטיבה ל השווה והחלפה הוא קישור עומס / חנות מותנה. בואו נחזור לראשונה השווה והחלפה. כפי שראינו בעבר, CAS מעדכן את הערך רק אם הערך בזיכרון הראשי הוא עדיין הערך שאנו מצפים שיהיה.

עם זאת, CAS מצליח גם אם הערך היה משתנה, ובינתיים התחלף לערכו הקודם.

התמונה שלהלן ממחישה מצב זה:

שניהם, חוט 1 וחוט 2 קוראים את ערך המשתנה, שהוא 3. ואז הברגה 2 מבצעת CAS, המצליחה להגדיר את המשתנה ל 8. ואז שוב, הברגה 2 מבצעת CAS כדי להחזיר את המשתנה ל -3, שמצליח גם כן. לבסוף, הברגה 1 מבצעת CAS, מצפה לערך 3, ומצליחה גם כן, למרות שערכו של המשתנה שלנו שונה פעמיים בין לבין.

זה נקרא בעיית A-B-A. ייתכן שהתנהגות זו אינה מהווה בעיה בהתאם למקרה השימוש, כמובן. עם זאת, ייתכן שלא רצוי לאחרים. Java מספק יישום של קישור עומס / מותנה בחנות עם ה AtomicStampedReference מעמד.

4.3. אחזר והוסף

חלופה נוספת היא אחזור והוסף. פעולה זו מגדילה את המשתנה בזיכרון הראשי לפי ערך נתון. שוב, הנקודה החשובה היא שהפעולה מתרחשת באופן אטומי, מה שאומר ששום חוט אחר לא יכול להפריע.

Java מספקת יישום של אחזור והוסף בשיעורי האטום שלו. דוגמאות לכך הן AtomicInteger.incrementAndGet (), שמגדיל את הערך ומחזיר את הערך החדש; ו AtomicInteger.getAndIncrement (), שמחזיר את הערך הישן ואז מגדיל את הערך.

5. גישה לתור מקושר מחוטים מרובים

כדי להבין טוב יותר את הבעיה של שני (או יותר) שרשורים שניגשים לתור בו זמנית, בואו נסתכל על תור מקושר ושני שרשורים שמנסים להוסיף אלמנט במקביל.

התור שנראה הוא תור FIFO המקושר כפליים בו אנו מוסיפים אלמנטים חדשים אחרי האלמנט האחרון (L) והמשתנה זָנָב מצביע על האלמנט האחרון:

כדי להוסיף אלמנט חדש, השרשורים צריכים לבצע שלושה שלבים: 1) ליצור את האלמנטים החדשים (N ו- M), כאשר המצביע לאלמנט הבא מוגדר כ ריק; 2) יש להתייחס לנקודת האלמנט הקודמת ל L ולהתייחס ליסוד הבא של L לנקודה N (M, בהתאמה). 3) יש זָנָב הצבע על N (M, בהתאמה):

מה יכול להשתבש אם שני האשכולות מבצעים את הצעדים הללו בו זמנית? אם השלבים בתמונה לעיל מתבצעים בסדר ABCD או ACBD, L, כמו גם זָנָב, יצביע על M. N יישאר מנותק מהתור.

אם השלבים מבוצעים בצו ACDB, זָנָב יצביע על N, בעוד L יצביע על M, מה שיגרום לחוסר עקביות בתור:

כמובן, אחת הדרכים לפתור בעיה זו היא ששרשור אחד ירכוש נעילה בתור. הפיתרון שנבחן בפרק הבא יפתור את הבעיה בעזרת פעולה ללא נעילה באמצעות פעולת CAS שראינו קודם.

6. תור שאינו חוסם בג'אווה

בואו נסתכל על תור בסיסי ללא נעילה בג'אווה. ראשית, בואו נסתכל על חברי הכיתה והבנאי:

מחלקה ציבורית NonBlockingQueue {גמר פרטי AtomicReference ראש זנב; גודל סופי פרטי AtomicInteger; ציבורי NonBlockingQueue () {head = AtomicReference חדש (null); זנב = AtomicReference חדש (null); גודל = AtomicInteger חדש (); size.set (0); }}

החלק החשוב הוא הצהרת התייחסויות הראש והזנב כ AtomicReferences, מה שמבטיח שכל עדכון על הפניות אלה הוא פעולה אטומית. סוג נתונים זה ב- Java מיישם את הדרוש השווה והחלפה מבצע.

לאחר מכן, בואו נסתכל על יישום מחלקת הצומת:

מחלקה פרטית צומת {ערך T נדיף פרטי; הצומת הפכפך הפרטי הבא; צומת נדיף פרטי קודם; צומת ציבורי (ערך T) {this.value = value; this.next = null; } // גטרים וקובעים}

כאן, החלק החשוב הוא להכריז על ההתייחסויות לצומת הקודם והבא כ- נָדִיף. זה מבטיח שנעדכן את ההפניות האלה תמיד בזיכרון הראשי (ובכך גלויות ישירות לכל השרשור). אותו הדבר עבור ערך הצומת בפועל.

6.1. ללא נעילה לְהוֹסִיף

ללא נעילה שלנו לְהוֹסִיף הפעולה תוודא שנוסיף את האלמנט החדש בזנב ולא ניתק מהתור, גם אם מספר שרשורים רוצים להוסיף אלמנט חדש במקביל:

הוסף חלל ציבורי (אלמנט T) {if (element == null) {זרוק NullPointerException חדש (); } צומת צומת = צומת חדש (אלמנט); צומת currentTail; בצע {currentTail = tail.get (); node.setPrevious (currentTail); } בעוד (! tail.compareAndSet (CurrentTail, node)); אם (node.previous! = null) {node.previous.next = node; } head.compareAndSet (null, node); // להכנסת גודל האלמנט הראשון.incrementAndGet (); }

החלק המהותי שיש לשים לב אליו הוא הקו המודגש. אנו מנסים להוסיף את הצומת החדש לתור עד שפעולת ה- CAS תצליח לעדכן את הזנב, שעדיין חייב להיות אותו הזנב אליו צירפנו את הצומת החדש.

6.2. ללא נעילה לקבל

בדומה לתוספת, הפעולה ללא נעילה תוודא שנחזיר את האלמנט האחרון ונעביר את הזנב למצב הנוכחי:

ציבורי T get () {if (head.get () == null) {זרוק NoSuchElementException חדש (); } צומת currentHead; צומת nextNode; בצע {currentHead = head.get (); nextNode = currentHead.getNext (); } תוך (! head.compareAndSet (currentHead, nextNode)); size.decrementAndGet (); להחזיר currentHead.getValue (); }

שוב, החלק המהותי שיש לשים לב אליו הוא הקו המודגש. פעולת ה- CAS מבטיחה שנעביר את הראש הנוכחי רק אם בינתיים לא הוסר שום צומת אחר.

Java כבר מספקת יישום של תור שאינו חוסם, ה- ConcurrentLinkedQueue. זהו יישום של התור ללא נעילה של מ 'מייקל ול' סקוט המתואר במאמר זה. הערת לוואי מעניינת כאן היא שתיעוד Java קובע שהוא א ללא המתנה תור, איפה זה באמת ללא נעילה. תיעוד Java 8 קורא כראוי ליישום ללא נעילה.

7. תורים ללא המתנה

כפי שראינו, היישום לעיל הוא ללא נעילהעם זאת, לא ללא המתנה. ה בזמן לולאות בשני לְהוֹסִיף ו לקבל השיטה עשויה לולאה לאורך זמן (או, אם כי לא סביר, לנצח) אם יש שרשורים רבים הניגשים לתור שלנו.

איך נוכל להשיג חופש המתנה? יישום אלגוריתמים ללא המתנה, באופן כללי, הוא די מסובך. אנו מפנים את הקורא המעוניין לעיתון זה, המתאר בפירוט תור ללא המתנה. במאמר זה, בואו נסתכל על הרעיון הבסיסי כיצד נוכל לגשת ליישום תור ללא המתנה.

תור ללא המתנה מחייב שכל שרשור יתקדם מובטח (לאחר מספר סופי של צעדים). במילים אחרות, ה בזמן לולאות בשיטות ההוספה וקבלת שלנו חייבות להצליח לאחר מספר צעדים מסוים.

על מנת להשיג זאת, אנו משייכים חוט עוזר לכל חוט. אם חוט עוזר זה יצליח להוסיף אלמנט לתור, זה יעזור לשרשור השני להכניס את האלמנט שלו לפני הכנסת אלמנט אחר.

מכיוון שלחוט העוזר יש עוזר עצמו, ובכל רשימת החוטים לכל חוט יש עוזר, אנו יכולים להבטיח כי חוט יצליח להכניס אחרונה לאחר שכל חוט ביצע הכנסה אחת. האיור הבא ממחיש את הרעיון:

כמובן שהדברים הופכים מסובכים יותר כשאנחנו יכולים להוסיף או להסיר חוטים באופן דינמי.

8. מסקנה

במאמר זה ראינו את היסודות של מבני נתונים שאינם חוסמים. הסברנו על הרמות השונות והפעולות הבסיסיות כמו השווה והחלפה.

ואז בדקנו יישום בסיסי של א ללא נעילה תור בג'אווה. לבסוף, התארנו את הרעיון כיצד להשיג המתן-חופש.

קוד המקור המלא לכל הדוגמאות במאמר זה זמין באתר GitHub.