פתרון תכנון תחת מגבלת זיכרון

החלפה בטוחה מחייבת שהמועמד והמידע הנוכחי יחיו יחד עד נקודת הפרסום. נשתמש באותו משאב לשני ה־vectorים, כדי שה־swap יתבצע בין allocators שווים. הקטע הבא מצטרף לתוכנית ההרצאה, אחרי הגדרת BudgetResource, ומחליף את ה־main שלה:

#include <array>
#include <cassert>
#include <cstdint>
#include <span>

class Records {
    std::pmr::memory_resource* resource_;
    std::pmr::vector<std::uint32_t> values_;

public:
    explicit Records(std::pmr::memory_resource& resource)
        : resource_(&resource), values_(&resource) {}

    void replace(std::span<const std::uint32_t> input) {
        std::pmr::vector<std::uint32_t> candidate(resource_);
        candidate.assign(input.begin(), input.end());
        values_.swap(candidate);
    }

    std::span<const std::uint32_t> values() const noexcept {
        return values_;
    }
};

int main() {
    BudgetResource budget(256);
    {
        Records records(budget);
        std::array<std::uint32_t, 32> first{};
        first.fill(7);
        records.replace(first);

        std::array<std::uint32_t, 64> second{};
        second.fill(9);
        bool rejected = false;
        try {
            records.replace(second);
        } catch (const std::bad_alloc&) {
            rejected = true;
        }
        assert(rejected);
        assert(records.values().size() == first.size());
        for (auto value : records.values()) assert(value == 7);

        const std::array<std::uint32_t, 2> small{11, 12};
        records.replace(small);
        assert(records.values().size() == 2);
        assert(records.values()[0] == 11);
    }
    assert(budget.live() == 0);
}

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

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

הפרדת סיבות הדחייה

בתחילת do_allocate מגדילים מונה דחיות תקציב רק בענף שמזהה חוסר מקום. סביב קריאת upstream_->allocate מוסיפים catch (const std::bad_alloc&), מגדילים מונה כישלונות מערכת וזורקים מחדש באמצעות throw;. עדכון live_ נשאר אחרי הקריאה המוצלחת. אין להגדיל ואז להקטין את המונה בשני מקומות, משום שהדבר מסבך את ההוכחה ללא צורך.

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

תור בעל גבול מפורש

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

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

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