סדרים אטומיים וגבולותיהם

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

ניסוי כזה נקרא litmus test. הוא אינו benchmark ואינו בודק מערכת שלמה. מטרתו לשאול האם צירוף מסוים של קריאות מותר תחת סדרי הזיכרון שנבחרו. העדר צירוף בהרצות אינו הוכחה שהוא אסור.

שני כותבים ושני קוראים

התוכנית הבאה מפעילה מספר מוגבל של סבבים. המחסומים משמשים להקמת כל סבב ולקריאת התוצאות, אך אינם נמצאים בין ה־store ל־load בתוך הסבב:

#include <atomic>
#include <barrier>
#include <iostream>
#include <thread>

int main() {
    constexpr int rounds = 20000;
    std::atomic<int> x{0}, y{0};
    int first = -1, second = -1;
    std::barrier phase(3);
    constexpr auto order = std::memory_order_relaxed;

    std::jthread a([&] {
        for (int i = 0; i < rounds; ++i) {
            phase.arrive_and_wait();
            x.store(1, order);
            first = y.load(order);
            phase.arrive_and_wait();
        }
    });
    std::jthread b([&] {
        for (int i = 0; i < rounds; ++i) {
            phase.arrive_and_wait();
            y.store(1, order);
            second = x.load(order);
            phase.arrive_and_wait();
        }
    });

    unsigned both_zero = 0;
    for (int i = 0; i < rounds; ++i) {
        x.store(0, std::memory_order_relaxed);
        y.store(0, std::memory_order_relaxed);
        phase.arrive_and_wait();
        phase.arrive_and_wait();
        if (first == 0 && second == 0) ++both_zero;
    }
    a.join();
    b.join();
    std::cout << "both-zero=" << both_zero << '\n';
}

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

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

מדוע acquire ו־release אינם קסם כללי

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

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

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

מחסומי זיכרון דורשים כתובת של סיפור

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

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

גבול בין C++ ל־Windows

משפחת Interlocked מספקת פעולות אטומיות עם חוזי Windows, ובחלק מן היעדים קיימות גרסאות עם סדרים שונים. יש לבדוק את היישור, הטיפוס והסמנטיקה של הפונקציה המדויקת. אין להמיר כתובת של std::atomic ל־LONG pointer ולערבב שתי משפחות פעולות מתוך הנחה שייצוגן זהה.

השימוש ב־volatile אינו תחליף ל־mutex או std::atomic בקוד C++ נייד. ל־MSVC היו ויש אפשרויות בעלות סמנטיקה מורחבת עבור volatile, אבל הישענות על הרחבה צריכה להיות בחירה מפורשת עם דגלי בנייה ויעד. בקורס נשתמש בחוזי סנכרון ברורים ולא נסיק מהצלחת ניסוי ב־x64 שהוא יעבוד גם ב־ARM64.

אפשר להשתמש ב־atomic::wait וב־notify כדי להימנע מסיבוב המתנה פעיל. עדיין צריך לפרסם את המידע בסדר הנכון. ההתראה עצמה אינה מחליפה את ה־store, וערך שמשתנה ואז חוזר לערכו הישן יכול לדרוש מונה דור כדי שלא נאבד שינוי רלוונטי.

קריאה להעמקה

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