מודל זיכרון ופעולות אטומיות

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

פעולת read-modify-write מאפשרת לחבר קריאה ועדכון של מילה אטומית אחת. הממשק compare-exchange מעדכן רק אם הערך הנוכחי שווה לערך שציפינו לו. אם מישהו שינה אותו, אנחנו מקבלים מידע שמאפשר לחשב מחדש את הבקשה. זאת אינה עסקה על כל הזיכרון שסביב המונה.

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

use std::sync::atomic::{AtomicUsize, Ordering};
fn reserve(used: &AtomicUsize, limit: usize, amount: usize) -> bool {
    let mut current = used.load(Ordering::Relaxed);
    loop {
        let Some(next) = current.checked_add(amount) else { return false; };
        if next > limit { return false; }
        match used.compare_exchange_weak(current, next, Ordering::Relaxed, Ordering::Relaxed) {
            Ok(_) => return true,
            Err(observed) => current = observed,
        }
    }
}
fn main() {
    let used = AtomicUsize::new(0);
    let accepted = AtomicUsize::new(0);
    std::thread::scope(|scope| {
        for _ in 0..8 {
            let used = &used;
            let accepted = &accepted;
            scope.spawn(move || {
                if reserve(used, 5, 1) { accepted.fetch_add(1, Ordering::Relaxed); }
            });
        }
    });
    assert_eq!(used.load(Ordering::Relaxed), 5);
    assert_eq!(accepted.load(Ordering::Relaxed), 5);
}

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

ה־atomicity שומרת על הפעולה במונה אחד. היא אינה אומרת שהקורא רואה באותו זמן גם שדה רגיל שהכותב עדכן קודם. עבור הקשר הזה נצטרך יחס happens-before שנוצר באמצעות סנכרון מתאים. בשיעור הבא נבנה פרסום של נתונים ונראה מדוע דגל אטומי ב־Relaxed אינו מספיק לבדו.

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

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

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

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

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

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