פרויקט תור בעלות ומנוע עבודה שניתן לבטל

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

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

לכל load ו־store כתבו למה ordering שנבחר מספיק. סמנו את פרסום הפריט ואת פרסום החריץ הפנוי, והגדירו את משמעות מלא וריק סביב wraparound. אם הפעולה מחזירה כשל, היא צריכה להחזיר את הערך שהמפיק עדיין מחזיק ולא לאבד אותו.

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

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

תנאי הסיום הוא מסמך הוכחה קצר, מבחני סדר ובעלות, דוגמת נגד לגרסה עם ordering פגום ודוח ביצועים מול תור ספרייה או Mutex תחת אותו עומס. אין לכנות את כל מנוע העבודה lock-free רק משום שהרכיב SPSC אינו מחזיק Mutex.