פתרון מבנים ללא נעילה וחיי צמתים

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

שתי שרשראות חיים

בשרשרת הראשונה היצרן כותב את התא, מבצע store עם release ל־head, והצרכן רואה את הפרסום ב־load עם acquire לפני קריאת התא. בשרשרת השנייה הצרכן קורא את התא, מפרסם tail עם release, והיצרן רואה את ההתקדמות ב־acquire לפני כתיבה חוזרת לאותו תא.

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

בדיקה עם עיכוב מכוון

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

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

תרחיש חיים שנשבר

נניח שהראש מצביע ל־A שקישורו ל־B. הקורא הראשון שומר את A. הקורא השני מוציא את A ומשחרר אותו, ולאחר מכן המקצה משתמש באותה כתובת עבור אובייקט אחר. גישה של הראשון לשדה next כבר אינה גישה לאובייקט הישן. השוואת הכתובת ב־CAS אינה יכולה לתקן בדיעבד את הקריאה הלא חוקית.

בגישה של hazard pointer הקורא צריך לפרסם הגנה ולבדוק מחדש את הראש לפני dereference. אם הראש השתנה, הוא מסיר או מעדכן את ההגנה ומנסה שוב. המסיר אינו משחרר node שעדיין מוגן. עצם שמירת הכתובת במשתנה מקומי אינה פרסום הגנה.

בגישה של epochs קורא נכנס לתקופה מוגדרת לפני הגישה ויוצא לאחריה. צומת שפרש נשמר עד שהקוראים הרלוונטיים עברו את נקודת הביטחון. קורא תקוע יכול לעכב רשימת פרישה גדולה, בעוד hazard pointer מצומצם יכול להחזיק מספר nodes מסוים אבל דורש סריקות ופרוטוקול רישום מתאים. בשתי הגישות shutdown חייב להפסיק משתמשים ולנקות פרישות לפי החוזה, ולא למחוק את כל הרשימה כשדגל stop נדלק.