מבני נתונים ללא נעילה: מדריך מלא עם דוגמאות ל-C++, Java ו-.NET

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

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

ללא נעילה לעומת ללא המתנה לעומת מוטקס: באיזה מהם להשתמש?

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

מספר סימוכין	ערבות התקדמות	השהייה אופיינית	מוּרכָּבוּת	הכי טוב
מבוסס Mutex / מנעול	חסימה, שרשורים ממתינים	בלתי צפוי תחת מחלוקת	נמוך	מצב משותף בעל מחלוקת נמוכה, דרישות תקינות פשוטות
ללא מנעולים	כלל-מערכתית, לפחות רצף תהליכים אחד מתקדם	נמוך תחת מאבק	גָבוֹהַ	תורים, מחסניות, מונים בעלי תפוקה גבוהה
ללא המתנה	לכל רצף, כל רצף מסתיים בצעדים מוגבלים	המקרה הגרוע ביותר	גבוה מאוד	מערכות בזמן אמת, קריטיות לבטיחות, SLAs עם השהייה מחמירה
ללא חסימות	התקדמות סולו, רק כאשר אין עוררין	נמוך ללא מחלוקת	בינוני	אבות טיפוס של זיכרון טרנזקציונלי, הקשרים מחקריים

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

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

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

עבור רוב המערכות בעלות מקביליות גבוהה: השתמשו ב-mutex כאשר רמת התחרות נמוכה והתקינות פשוטה, השתמשו ב-lock-free כאשר התפוקה תחת תחרות חשובה, השתמשו ב-wait-free רק כאשר השהייה לכל הליך משנה בתרחיש היא דרישה קשה.

מהו מבנה נתונים ללא נעילה?

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

המנגנון הוא פעולות אטומיות, הוראות CPU המבצעות כיחידה אחת בלתי ניתנת לחלוקה. הפרימיטיבי האוניברסלי הוא השוואה והחלפה (CAS) :

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS הוא אטומי ברמת החומרה. ב-x86 זהו ה- CMPXCHG הוראה. ב-ARM היא מיושמת באמצעות LDXR/STXR (load-exclusive/store-exclusive), שהוא הגרסה LL/SC (Load-Linked/Store-Conditional). הליך משנה קורא ערך, מחשב ערך חדש ומשתמש ב-CAS כדי להתקין אותו רק אם אף אחד אחר לא שינה אותו בין לבין. אם CAS נכשל, הליך משנה מנסה שוב עם הערך החדש.

ב-C++11 ואילך, זה נחשף דרך std::atomic:

cpp

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

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

בעיית ה-ABA: המלכודת המסוכנת ביותר של Lock-Free

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

התרחיש שלב אחר שלב

שקול מחסנית ללא נעילה באמצעות מצביע יחיד top:

1. שרשור א' קורא top = Node1המצביע הבא של Node1 הוא Node2.
2. הליך A עובר הקדמה לפני השלמת הפופ שלו.
3. אשכול B קופץ את Node1 (החלק העליון הופך ל-Node2), לאחר מכן קופץ את Node2 (החלק העליון הופך ל-null).
4. הליך B דוחף צומת חדש, אשר במקרה מוקצה לאותה כתובת זיכרון כמו צומת 1 (נפוץ במקצים של רשימה חופשית). למעלה = צומת 1 (אותו מצביע, תוכן שונה).
5. שרשור א' מתחדש. ה-CAS שלו רואה top == Node1 (ערך צפוי), מצליח, ומגדיר top = Node2, אבל Node2 כבר שוחרר. אסון.

בעיית ה-ABA מתבטאת בצורה שונה בכל מבנה נתונים:

• לערוםCAS מצליח אך מתקין מצביע next מיושן, מה שגורם ל-use-after-free
• תורמצביע הראש או הזנב נראה ללא שינוי אך המבנה השתנה
• רשימה מקושרתצומת נראה עדיין במקומו אך הוסר והוקצה מחדש

האם LL/SC נמנעים מבעיית ה-ABA?

כן, LL/SC (Load-Linked/Store-Conditional) מספק סמנטיקה חזקה יותר מ-CAS ונמנע באופן טבעי מ-ABA. LL מסמן את כתובת הזיכרון שנטענה כ"מקושרת". SC באותה כתובת נכשל אם התרחשה אחסון כלשהו לכתובת זו מאז ה-LL, גם אם הערך שוחזר למצבו המקורי. היסטוריית השינויים נבדקת ברמת החומרה, לא רק בערך הנוכחי.

עם זאת, ליישומי LL/SC על חומרה אמיתית יש מגבלות מעשיות. ב-ARM וב-POWER, כשלים מזויפים של LL/SC יכולים להתרחש גם ללא קונפליקטים (מתגי הקשר, פינוי מטמון). הקוד חייב להתחשב בלולאות ניסיון חוזר גם ללא קונפליקטים אמיתיים. ב-x86, אין LL/SC מקורי; CAS הוא פרימיטיבי החומרה. עבור קוד x86, יש למנוע ABA בתוכנה.

תיקון ABA: שלוש גישות

1. מוני גרסאות (מצביעים מתויגים)

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

cpp

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

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

2. סימני סכנה

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

cpp

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

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

3. שיקום מבוסס תקופה (EBR)

הליכים פועלים ב"תקופות" (epochs) בעלות מעקב גלובלי. צמתים שהוצאו משימוש מאוחסנים במאגר לפי תקופה ומשוחררים רק כאשר כל הליכים אלו עברו את התקופה בה הצומת הוצא משימוש. EBR פשוט יותר לשימוש מאשר מצביעי hazard (hazard pointers) ויש לו תקורה נמוכה יותר לכל פעולה, במחיר של צמיחת זיכרון מוגבלת אך בלתי צפויה בתקופות רגיעה.

ב- Java, AtomicStampedReference מטפל ישירות בבעיית ABA על ידי צימוד הפניה עם חותמת מספר שלם:

תאווה

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

יישומי תור ללא נעילה

תורים הם המבנה הנפוץ ביותר ללא נעילה. התור הקנוני ללא נעילה הוא תור מייקל-סקוט, המשתמש בשני מצביעים (ראש וזנב) וצומת זקיף כדי לאפשר פעולות יצירת תור והסרת תור בו זמנית.

תור SPSC: ביצועים מקסימליים עם סנכרון מינימלי

תור יחיד של יצרן יחיד וצרכן יחיד מבטל את כל המחלוקות בין כתיבה-כתיבה וקריאה-קריאה. הליך אחד כותב לזנב; הליך אחד קורא מהראש. רק מצביע הראש משותף בין היצרן לצרכן:

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

השמיים alignas(64) על head ועל tail הוא קריטי. בלעדיו, שניהם מתאימים לאותה שורת מטמון. כל כתיבה ל-tail גורמת לביטול שורת מטמון הנראית לראש הקריאה של הליבה, ולהיפך, שיתוף כוזב שמסכם בסידור את מה שאמור להיות פעולות עצמאיות.

תור MPMC: Multi-Producer Multi-Consumer

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

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET ConcurrentQueue: איך זה עובד באופן פנימי

.NET ConcurrentQueue<T> ב-.NET 5+ משתמש במבנה מערך מפולח. כל מקטע הוא מערך בגודל קבוע עם אינדקס ראש וזנב המנוהל באמצעות Interlocked פעולות (אשר ממפות ל-CAS בחומרה הבסיסית). מקטעים מקושרים באמצעות תנודתי _nextSegment מצביע. Enqueue מתווסף לפלח הזנב הנוכחי, ומגדיל את שרשרת הפלח כשהיא מלאה. Dequeue קורא מהפלח head ומקדם את אינדקס ה-head באופן אטומי.

החלטת התכנון המרכזית היא הימנעות מנעילה גלובלית. יצרנים מתחרים רק על מדד הזנב של הסגמנט הנוכחי. צרכנים מתחרים רק על מדד הראש. אף יצרן לעולם לא מתחרה עם צרכן. זה הופך ConcurrentQueue<T> יעילות גבוהה עבור צינורות יצרן-צרכן:

צארפ

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

קוהרנטיות מטמון ושיתוף כוזב בקוד ללא נעילה

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

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

cpp

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

פרוטוקול MESI (Modified, Exclusive, Shared, Invalid) מתאר כיצד מעבדי x86 מתאמים בעלות על שורות מטמון. כאשר ליבה רוצה לכתוב מיקום שהיא חולקת עם ליבות אחרות (מצב משותף), עליה לשדר בקשת כתיבה, להמתין לאישור מכל המשתפים ולעבור למצב Modified. מעבר זה לפרוטוקול הקוהרנטיות אורך 50-300+ מחזורים במערכת מרובת שקעים. שיתוף כוזב הופך פעולות מקומיות-הליך עצמאיות לתעבורת קוהרנטיות מטמון, ופוגע בביצועים שאמורים להסתגל באופן ליניארי עם הליבות.

גילוי שיתוף כוזב: להשתמש perf stat -e cache-misses,L1-dcache-load-misses בלינוקס או בפרופיל ביצועי המעבד של Visual Studio ב-Windows. שיעור גבוה של החמצות במטמון L1 בתוכנית מרובת הליכי משנה שמתאימה למטמון הוא אינדיקטור חזק לשיתוף שגוי.

סידור זיכרון: למה memory_order_relaxed לא תמיד מספיק

C + + std::atomic פעולות חושפות את מלוא טווח סידור הזיכרון ממודל הזיכרון C++11. בחירת סדר שגוי היא הבאג השני בשכיחותו בקוד ללא נעילה אחרי בעיית ABA.

cpp

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

טעות נפוצה: שימוש relaxed עבור דגל שחרור. שרשור שמגדיר ready = true עם relaxed ההזמנה אינה מבטיחה שכתיבות קודמות אל data גלויים לשרשורים אחרים שקוראים readyזוג הרכישה/שחרור יוצר את מערכת היחסים "קורה-לפני" שמחברת בין הכותב לקורא.

ערימת טרייבר: ערימה נטולת מנעולים ב-C++

מחסנית טרייבר היא מבנה הנתונים הפשוט ביותר שאינו טריוויאלי ונטול מנעולים. היא משתמשת בלולאת CAS על יחידה top מַצבִּיעַ:

cpp

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

ההערה על delete node קריטי: מחיקה נאיבית היא סכנת ה-ABA שתוארה קודם לכן. במחסנית Treiber של ייצור, שחזור צומת דורש מצביעי סכנה, שחזור מבוסס-עיתון או איסוף זבל (Java/C# מטפלים בזה באופן אוטומטי).

מבני נתונים ללא נעילה בג'אווה

ספריית הסטנדרטים של ג'אווה מספקת יישומים ללא נעילה באיכות ייצור ב... java.util.concurrent:

כיתה	מִבְנֶה	התקדמות	הערות
AtomicReference<T>	ערך יחיד	ללא מנעולים	CAS על הפניה לאובייקט
AtomicStampedReference<T>	ערך + בול	ללא מנעולים	מניעת ABA באמצעות מונה גרסאות
ConcurrentLinkedQueue<T>	תור מייקל-סקוט	ללא מנעולים	FIFO, לא מוגבל
ConcurrentLinkedDeque<T>	דק ללא מנעולים	ללא מנעולים	שני הקצוות
LongAdder	דלפק	ללא מנעולים	ספירה מפוספסת, בעלת תפוקה גבוהה

LongAdder ראוי לציין זאת באופן ספציפי. במקום מונה אטומי יחיד שמתחרה בין כל השלבים, הוא מתחזק מערך מפוצל של מונים, שכל אחד מהם נגיש על ידי תת-קבוצה של שלבים. המחלוקת מתפזרת על פני פסים במקום להתרכז במיקום אחד. הסכום הכולל מסוכם בעצלתיים על sum()עבור פעולות הגדלה בתדירות גבוהה על פני מספר רב של חוטים, LongAdder ביצועים טובים יותר באופן דרמטי AtomicLong.incrementAndGet():

תאווה

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

איך SMART TS XL תומך בפיתוח מערכת ללא נעילה

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

SMART TS XL מנתח את נתיבי הביצוע המלאים של קוד בו-זמני, ועוקב אחר האופן שבו פעולות אטומיות קשורות למיקומי הזיכרון שהן שומרות. עבור מערכות המשלבות קוד ללא נעילה עם רכיבים מדור קודם או ארכיטקטורות רב-לשוניות, הוא מספק נראות חוצת גבולות שכלים בשפה אחת אינם יכולים לספק: כיצד אזור זיכרון משותף אליו ניגש רכיב C++ ללא נעילה קשור לשירות Java שקורא ממנו, או כיצד תור בו-זמני מוזן לתוך צינור עיבוד מבוסס COBOL.

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

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

כאשר חופש מנעולים הוא הבחירה הלא נכונה

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

השתמש ב-mutex כאשר:

• ספירת השרשורים נמוכה (מתחת ל-4-8) או שהמחלוקת נדירה
• הקטע הקריטי ארוך ומורכב (לולאות ללא מנעולים הופכות יקרות יחסית לקטע)
• נכונות חשובה יותר מתפוקה והאלגוריתם פשוט יותר עם נעילה
• לפלטפורמה נעילה יעילה מבוססת futex (לינוקס) pthread_mutex, נעילת SRW של Windows)

השתמשו ב"ללא נעילה" כאשר:

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

השתמשו ב-"ללא המתנה" כאשר:

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

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