בעלות ותיאום בין תהליכונים

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

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

התנאי הוא המידע החשוב

התוכנית הבאה מלאה ב־C++20. היא משתמשת ב־condition variable כדי להמתין לשינוי אפשרי בתנאי, וב־mutex כדי לבדוק ולשנות את התנאי:

#include <condition_variable>
#include <cstddef>
#include <deque>
#include <iostream>
#include <mutex>
#include <optional>
#include <stdexcept>
#include <thread>

class Channel {
    std::mutex mutex_;
    std::condition_variable changed_;
    std::deque<int> queue_;
    std::size_t capacity_;
    bool closed_ = false;

public:
    explicit Channel(std::size_t capacity) : capacity_(capacity) {
        if (capacity == 0) throw std::invalid_argument("zero capacity");
    }

    bool push(int value) {
        std::unique_lock lock(mutex_);
        changed_.wait(lock, [&] {
            return closed_ || queue_.size() < capacity_;
        });
        if (closed_) return false;
        queue_.push_back(value);
        lock.unlock();
        changed_.notify_all();
        return true;
    }

    std::optional<int> pop() {
        std::unique_lock lock(mutex_);
        changed_.wait(lock, [&] {
            return closed_ || !queue_.empty();
        });
        if (queue_.empty()) return std::nullopt;
        const int value = queue_.front();
        queue_.pop_front();
        lock.unlock();
        changed_.notify_all();
        return value;
    }

    void close() {
        {
            std::lock_guard lock(mutex_);
            closed_ = true;
        }
        changed_.notify_all();
    }
};

int main() {
    Channel channel(4);
    long long sum = 0;
    std::jthread consumer([&] {
        while (auto value = channel.pop()) sum += *value;
    });
    try {
        for (int value = 1; value <= 100; ++value)
            if (!channel.push(value)) throw std::runtime_error("closed");
    } catch (...) {
        channel.close();
        throw;
    }
    channel.close();
    consumer.join();
    std::cout << sum << '\n';
}

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

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

איך מאבדים התעוררות

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

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

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

בחירת מנגנון לפי משמעות

ה־mutex הסטנדרטי מתאים להגנה בלעדית על מצב C++. ב־Windows קיימים גם critical section, שמיועד לסנכרון בתוך תהליך, ו־SRW lock שמאפשר גישה משותפת לקוראים או בלעדית לכותב. נעילת קוראים וכותבים אינה מבטיחה שהקוד יהיה מהיר יותר: משך ההחזקה, תדירות הכתיבה ותחרות על cache lines משפיעים על התוצאה. בפרט, ל־SRW lock אין חוזה כללי של סדר הגעה הוגן, ואסור להניח שהוא recursive.

אירוע מתאים לאות עם מצב מוגדר. אירוע manual-reset נשאר מסומן עד reset, בעוד אירוע auto-reset משחרר ממתין בהתאם לחוזהו ומאפס את מצבו. האירוע אינו מספר כמה פריטים הוכנסו מאז האיפוס. עבור מספר יחידות זמינות, semaphore עשוי להתאים יותר, אבל גם בו צריך להוכיח התאמה בין המונה לבין המשאב האמיתי.

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

קריאה להעמקה

החוזים של משתני תנאי ב־Windows ושל נעילות קוראים וכותבים מסבירים את מגבלות המנגנונים המקבילים ב־WinAPI. יש להפריד בין החוזה המתועד לבין פרטי המימוש של ספריית C++ שבחרנו.