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

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

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

תור ליצרן וצרכן יחידים

התוכנית הבאה מלאה. היא משאירה תא אחד פנוי כדי להבחין בין מצב מלא למצב ריק:

#include <array>
#include <atomic>
#include <cassert>
#include <cstddef>
#include <thread>

template<std::size_t N>
class SpscQueue {
    static_assert(N >= 2);
    std::array<unsigned, N> slots_{};
    std::atomic<std::size_t> head_{0};
    std::atomic<std::size_t> tail_{0};

    static constexpr std::size_t next(std::size_t value) noexcept {
        return value + 1 == N ? 0 : value + 1;
    }

public:
    bool try_push(unsigned value) noexcept {
        const auto head = head_.load(std::memory_order_relaxed);
        const auto following = next(head);
        if (following == tail_.load(std::memory_order_acquire))
            return false;
        slots_[head] = value;
        head_.store(following, std::memory_order_release);
        return true;
    }

    bool try_pop(unsigned& value) noexcept {
        const auto tail = tail_.load(std::memory_order_relaxed);
        if (tail == head_.load(std::memory_order_acquire))
            return false;
        value = slots_[tail];
        tail_.store(next(tail), std::memory_order_release);
        return true;
    }
};

int main() {
    SpscQueue<64> queue;
    constexpr unsigned count = 100000;
    std::jthread producer([&] {
        for (unsigned value = 0; value < count; ++value)
            while (!queue.try_push(value)) std::this_thread::yield();
    });
    for (unsigned expected = 0; expected < count; ++expected) {
        unsigned value = 0;
        while (!queue.try_pop(value)) std::this_thread::yield();
        assert(value == expected);
    }
    producer.join();
}

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

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

נקודת הפרסום והתקדמות

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

פעולת try אחת מבצעת מספר קבוע של צעדים ברמת האלגוריתם, אך הטענה על lock-free תלויה גם במימוש האטומיים. אפשר לבדוק is_lock_free עבור הטיפוס ביעד, ואין להניח שכל std::atomic בכל גודל ממומש בלי נעילה. לולאת ההמתנה החיצונית אינה wait-free: אם הצרכן אינו מתקדם, היצרן יכול להמשיך להיכשל לנצח.

מנגנון lock-free מבטיח התקדמות מסוג מסוים של המערכת, לא היעדר המתנה לכל משתתף ולא latency קטן. מנגנון wait-free דורש גבול להתקדמות של כל פעולה לפי ההגדרה המתאימה. אלה טענות שצריך להוכיח, ולא שמות שמקבלים משום שלא כתבנו mutex.

מדוע יצרן נוסף משנה הכול

אם נוסיף יצרן שני, שניהם יכולים לקרוא אותו head ולכתוב לאותו תא. הפיכת head ל־CAS אינה מספיקה בלי פרוטוקול שמפריד בין שמירת מקום לבין פרסום תוכן מוכן. צרכן עלול לראות מיקום שנשמר לפני שהיצרן סיים לכתוב בו. תורי MPMC משתמשים לעיתים במוני רצף לכל תא או במבני nodes עם פרוטוקול חיים מורכב יותר.

גם false sharing יכול להשפיע: head ו־tail עשויים להימצא באותו cache line, למרות שכל אחד נכתב מצד אחר. אפשר לבחון הפרדה ויישור אחרי מדידה, אך אין להקשות את ABI על סמך מספר קבוע שאמור לייצג כל חומרה. נכונות התור אינה תלויה באופטימיזציה הזו.

המצביע חזר אבל האובייקט השתנה

נחשוב על מחסנית nodes עם ראש אטומי. תהליכון קורא שהראש הוא A ועוצר. תהליכון אחר מוציא את A, מוציא את B ואז מכניס מחדש node באותה כתובת A. ה־CAS של הראשון עשוי לראות את אותה כתובת ולהצליח, אף שההיסטוריה והקישורים השתנו. זו בעיית ABA.

מונה גרסה יכול לעזור לזהות חלק מן השינויים, אך יש לבדוק גלישה, רוחב פעולה אטומית ותמיכה ביעד. הוא גם אינו פותר לבדו שימוש אחרי שחרור: הקריאה של A->next כבר עלולה להיות לא חוקית לפני שמגיעים ל־CAS.

ב־hazard pointers קורא מפרסם את הכתובת שעליה הוא עומד לעבוד, בודק מחדש שהיא עדיין רלוונטית ורק אז משתמש בה. מסיר מכניס node לרשימת פרישה ומשחרר אותו רק כשאין הגנה מתאימה. ב־epoch reclamation השחרור נדחה עד שכל קורא שעלול היה לראות את ה־node עבר מעבר מתאים. קורא שנתקע יכול לעכב שחרור, ולכן התקציב והסיום עדיין חשובים.

ב־C++20 אין כאן הבטחה שכל ספריית תקן מספקת ממשק hazard pointers מוכן. אם משתמשים בספרייה חיצונית, לומדים את חוזה הרישום, הסריקה והיציאה שלה. בתור הטבעתי שלנו נמנענו משחרור דינמי בזמן הפעולות, אך לא פתרנו באופן קסום את בעיית ה־reclamation לכל מבנה נתונים.

קריאה להעמקה

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