הוגנות נעילות וכשלי התקדמות

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

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

use std::sync::Mutex;
fn transfer(accounts: &[Mutex<i64>], from: usize, to: usize, amount: i64)
    -> Result<(), &'static str> {
    if amount < 0 { return Err("negative amount"); }
    if from >= accounts.len() || to >= accounts.len() { return Err("unknown account"); }
    if from == to { return Ok(()); }
    let low = from.min(to);
    let high = from.max(to);
    let mut low_value = accounts[low].lock().map_err(|_| "poisoned")?;
    let mut high_value = accounts[high].lock().map_err(|_| "poisoned")?;
    let (source, destination) = if from == low {
        (&mut *low_value, &mut *high_value)
    } else { (&mut *high_value, &mut *low_value) };
    if *source < amount { return Err("insufficient funds"); }
    let next_destination = destination.checked_add(amount).ok_or("overflow")?;
    *source -= amount;
    *destination = next_destination;
    Ok(())
}
fn main() {
    let accounts = [Mutex::new(100i64), Mutex::new(100i64)];
    std::thread::scope(|scope| {
        scope.spawn(|| { for _ in 0..50 { transfer(&accounts, 0, 1, 1).unwrap(); } });
        scope.spawn(|| { for _ in 0..50 { transfer(&accounts, 1, 0, 1).unwrap(); } });
    });
    assert_eq!(*accounts[0].lock().unwrap(), 100);
    assert_eq!(*accounts[1].lock().unwrap(), 100);
}

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

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

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

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

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

גם priority inversion היא תלות במי שמחזיק משאב. תהליכון בעדיפות גבוהה יכול להמתין לתהליכון נמוך שמחזיק נעילה, בעוד שעבודה בעדיפות בינונית מונעת ממנו לרוץ. העלאת עדיפות הממתין אינה פותרת לבדה את התלות. נבדוק משך החזקת נעילה, מדיניות scheduler ומנגנוני inheritance כאשר הם חלק מדרישות המערכת.

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

החוזה של נעילות קריאה וכתיבה נמצא בתיעוד RwLock. לכל שינוי מבני נבדוק גם בטיחות מצב וגם התקדמות: העובדה שאין data race אינה אומרת שהמשתמש יקבל תשובה.