هياكل البيانات غير المقفلة: دليل شامل مع أمثلة بلغات C++ و Java و .NET

آلية التزامن (mutex) بسيطة. تقوم بقفلها، ثم تعديل الحالة المشتركة، ثم فك قفلها. كل خيط يرغب بالوصول ينتظر دوره. تكمن المشكلة في "انتظار الدور"، فمع عدد كبير من النوى ومعدل نقل بيانات عالٍ، يصبح هذا التسلسل هو الحد الأقصى. يمكن مقاطعة الخيط الذي يحمل القفل، مما يؤدي إلى توقف جميع الخيوط الأخرى عن العمل. كما يمكن أن يؤدي انعكاس الأولوية إلى قيام الخيوط ذات الأولوية المنخفضة بحجب الخيوط ذات الأولوية العالية. في الأنظمة التي تعالج ملايين العمليات في الثانية عبر عشرات النوى، لا يؤدي التنازع على التزامن إلى إبطاء العمليات فحسب، بل يؤدي أيضًا إلى انهيار معدل نقل البيانات.

تستبدل هياكل البيانات غير المُقفلة الاستبعاد المتبادل بعمليات ذرية. فبدلاً من منع التعارض، تتسامح معه وتتعافى منه. يُعيد الخيط الذي يفشل في عملية المقارنة والتبديل المحاولة بحالة مُحدثة. لا يُعيق أي خيط آخر، ويحرز خيط واحد على الأقل تقدماً دائماً. والنتيجة هي إنتاجية أفضل بكثير في ظل التنافس الشديد، وزمن استجابة متوقع دون تأثيرات القوافل، والقضاء على حالات الجمود وانعكاس الأولوية بحكم التصميم. أما ثمن ذلك فهو تعقيد التنفيذ: فمشكلة ABA، ومخاطر استعادة الذاكرة، والمشاركة الخاطئة، ومتطلبات ترتيب الذاكرة الدقيقة، كلها فخاخ غير موجودة في التعليمات البرمجية القائمة على الأقفال. تُغطي هذه المقالة جميعها مع أمثلة عملية.

الأقفال غير المقفلة مقابل الأقفال غير المنتظرة مقابل الأقفال المتبادلة: أيها نستخدم؟

قبل اختيار أسلوب التنفيذ، السؤال الصحيح هو ما هو ضمان التقدم الذي يحتاجه النظام فعلاً. تختلف النماذج الثلاثة فيما تعد به عند تنافس الخيوط.

الموديل	ضمان التقدم	زمن الوصول النموذجي	تعقيد	أفضل ل
Mutex / قائم على القفل	حظر، تنتظر الخيوط	غير متوقع في ظل المنافسة	منخفض	حالة مشتركة منخفضة التنازع، متطلبات صحة بسيطة
بدون قفل	على مستوى النظام، يتقدم خيط واحد على الأقل.	منخفض تحت المنافسة	مرتفع	قوائم انتظار عالية الإنتاجية، ومكدسات، وعدادات
بدون انتظار	لكل خيط، ينتهي كل خيط في خطوات محدودة	أسوأ حالة محدودة	عالي جدا	أنظمة الوقت الحقيقي، ذات أهمية بالغة للسلامة، واتفاقيات مستوى الخدمة الصارمة المتعلقة بزمن الاستجابة
خالٍ من العوائق	التقدم الفردي، فقط عندما لا يكون هناك من ينافسه	منخفض بدون نزاع	متوسط	نماذج أولية للذاكرة التفاعلية، سياقات البحث

يُعدّ استخدام العمليات بدون تأمين الخيار الافتراضي العملي لأنظمة الإنتاج عالية التزامن. فقائمة انتظار مايكل سكوت، ومكدس ترايبر، ومعظم مخازن MPMC الحلقية المستخدمة في الإنتاج، كلها تعتمد على هذه العمليات. قد تتعطل بعض الخيوط الفردية في ظلّ التنافس الشديد، لكن النظام ككلّ يُحرز تقدماً.

يضمن أسلوب المعالجة بدون انتظار تقدمًا محدودًا لكل خيط، ولكنه يتطلب خوارزميات أكثر تعقيدًا. توجد بنى عامة، لكنها تحمل عبئًا إضافيًا كبيرًا. تُعد خوارزميات المعالجة بدون انتظار مناسبة لسياقات الوقت الحقيقي الصارمة حيث يكون زمن الاستجابة النهائي أكثر أهمية من متوسط ​​الإنتاجية.

نادراً ما يُستخدم مفهوم "الخلو من العوائق" بشكل مباشر في بيئات الإنتاج. يظهر هذا المفهوم في بعض تطبيقات الذاكرة المعاملاتية، ويُستخدم كخطوة تمهيدية عند إثبات صحة الخوارزمية.

بالنسبة لمعظم الأنظمة ذات التزامن العالي: استخدم mutex عندما يكون التنافس منخفضًا والصحة بسيطة، واستخدم بدون قفل عندما تكون الإنتاجية في ظل التنافس مهمة، واستخدم بدون انتظار فقط عندما يكون زمن الوصول لكل مؤشر ترابط في أسوأ الحالات شرطًا أساسيًا.

ما هي بنية البيانات الخالية من الأقفال؟

تُعتبر بنية البيانات خالية من الأقفال إذا ضمنت أن خيطًا واحدًا على الأقل من بين جميع الخيوط العاملة عليها سيُكمل عمليته في عدد محدود من الخطوات، بغض النظر عما تفعله الخيوط الأخرى أو كيفية جدولة عملها. لهذا التعريف الرسمي دلالة دقيقة: لا يمكن لأي خوارزمية خالية من الأقفال أن تُصاب بحالة جمود. فإذا توقف خيط واحد، أو عُلّق، أو كان بطيئًا، فإن الخيوط الأخرى ستواصل العمل.

تعتمد الآلية على العمليات الذرية، وهي تعليمات وحدة المعالجة المركزية التي تُنفذ كوحدة واحدة غير قابلة للتجزئة. العملية الأساسية الشاملة هي المقارنة والتبديل (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 (تحميل حصري/تخزين حصري)، وهو نوع LL/SC (تحميل مرتبط/تخزين مشروط). يقرأ أحد الخيوط قيمة، ويحسب قيمة جديدة، ويستخدم CAS لتثبيتها فقط إذا لم يقم أي خيط آخر بتغييرها في هذه الأثناء. إذا فشل CAS، يعيد الخيط المحاولة بالقيمة الجديدة.

في C++11 والإصدارات الأحدث، يتم عرض ذلك من خلال std::atomic:

حزب الشعب الكمبودي

#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 هي الدالة الأساسية لنظام الجبر الحاسوبي. عند الفشل، يتم تحديثها expected يتم تحديث القيمة الحالية تلقائيًا، مما يجعل حلقة إعادة المحاولة مناسبة.

مشكلة ABA: أخطر مأزق في مجال الأقفال الخالية من الأقفال

تُعدّ مشكلة ABA من أكثر المخاطر غير البديهية المتعلقة بصحة التعليمات البرمجية في البرمجة غير المعتمدة على الأقفال. يتحقق CAS مما إذا كان موقع الذاكرة لا يزال يحتوي على القيمة المتوقعة قبل تثبيت قيمة جديدة. لا يستطيع CAS اكتشاف ما إذا كانت تلك القيمة قد تغيرت ثم عادت إلى حالتها الأصلية بين عملية القراءة وعملية CAS. يبدو الموقع ظاهريًا كما هو في الأصل، لكن الحالة الأساسية للنظام قد تغيرت بطرق لا يستطيع CAS رصدها.

السيناريو خطوة بخطوة

لنفترض وجود مكدس غير مقفل يستخدم مؤشرًا واحدًا top:

1. الخيط أ يقرأ top = Node1. المؤشر التالي للعقدة Node1 هو العقدة Node2.
2. يتم مقاطعة الخيط A قبل إكمال عملية إزالة البيانات.
3. يقوم الخيط B بإخراج العقدة 1 (يصبح أعلى العقدة 2)، ثم يقوم بإخراج العقدة 2 (يصبح أعلى العقدة فارغًا).
4. يقوم الخيط B بإضافة عقدة جديدة، والتي تصادف أنها مُخصصة في نفس عنوان الذاكرة الخاص بالعقدة 1 (وهذا شائع مع مُخصصات قائمة التحرير). العقدة العلوية = العقدة 1 (نفس المؤشر، محتوى مختلف).
5. يستأنف الخيط أ. يرى نظام CAS الخاص به top == Node1 (القيمة المتوقعة)، ينجح، ويضبط top = Node2لكن العقدة الثانية كانت قد تحررت بالفعل. كارثة.

تتجلى مشكلة تحليل السلوك التطبيقي (ABA) بشكل مختلف في كل بنية بيانات:

• كومة: تنجح عملية CAS ولكنها تُثبّت مؤشرًا تالٍ قديمًا، مما يتسبب في استخدام الذاكرة بعد تحريرها
• طابوريظهر مؤشر الرأس أو الذيل دون تغيير، لكن البنية قد تغيرت.
• قائمة مرتبطةيبدو أن العقدة لا تزال في مكانها ولكن تمت إزالتها وإعادة تخصيصها.

هل يتجنب برنامج LL/SC مشكلة تحليل السلوك التطبيقي (ABA)؟

نعم، يوفر LL/SC (التحميل المرتبط/التخزين المشروط) دلالات أقوى من CAS ويتجنب بشكل طبيعي ABA. يُعلّم LL عنوان الذاكرة المُحمّل بأنه "مرتبط". يفشل SC على نفس العنوان إذا حدث أي تخزين لهذا العنوان منذ LL، حتى لو تم استعادة القيمة إلى حالتها الأصلية. يتم تتبع سجل التعديلات على مستوى العتاد، وليس فقط القيمة الحالية.

مع ذلك، فإن تطبيقات LL/SC على الأجهزة الحقيقية لها قيود عملية. ففي معالجات ARM وPOWER، قد تحدث حالات فشل LL/SC غير متوقعة حتى بدون تنازع (تبديل السياق، إخلاء الذاكرة المؤقتة). يجب أن يأخذ الكود في الحسبان حلقات إعادة المحاولة حتى بدون تعارضات حقيقية. أما في معالجات x86، فلا يوجد LL/SC أصلي؛ فـ CAS هي الآلية الأساسية في الجهاز. بالنسبة لكود x86، يجب منع ABA برمجيًا.

إصلاح تحليل السلوك التطبيقي: ثلاثة مناهج

1. عدادات الإصدارات (مؤشرات مُوسومة)

قم بتضمين عداد الإصدار في نفس الكلمة الذرية التي تحتوي على المؤشر. كل عملية CAS ناجحة تزيد العداد. حتى لو عاد المؤشر إلى قيمته الأصلية، فإن العداد يختلف:

حزب الشعب الكمبودي

#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. مؤشرات الخطر

يحتفظ كل خيط بمجموعة صغيرة من "مؤشرات الخطر"، وهي مؤشرات إلى العقد التي يصل إليها حاليًا. قبل تحرير أي عقدة، يتحقق الخيط من جميع سجلات مؤشرات الخطر للتأكد من عدم وصول أي خيط آخر إليها. يتم تأجيل العقدة التي تظهر في مؤشر خطر حتى يتم مسح ذلك المؤشر.

حزب الشعب الكمبودي

// 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)

تعمل الخيوط ضمن "حقب" يتم تتبعها عالميًا. تُخزَّن العقد المُتقاعدة مؤقتًا لكل حقبة، ولا تُحرَّر إلا بعد أن تتجاوز جميع الخيوط الحقبة التي تقاعدت فيها العقدة. يُعدّ استخدام EBR أسهل من استخدام مؤشرات المخاطر، ويتميز بانخفاض تكلفة كل عملية، على حساب نمو محدود وغير متوقع للذاكرة خلال فترات السكون.

في جافا ، 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: أقصى أداء بأقل قدر من التزامن

تُزيل قائمة الانتظار أحادية المنتج وأحادية المستهلك جميع حالات التنازع بين عمليات الكتابة والقراءة. يكتب أحد الخيوط إلى نهاية القائمة، بينما يقرأ خيط آخر من بدايتها. المؤشر الرئيسي فقط هو ما يُشارك بين المنتج والمستهلك.

حزب الشعب الكمبودي

#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) يُعدّ تحديد بداية ونهاية ذاكرة التخزين المؤقت أمرًا بالغ الأهمية. فبدون ذلك، ستُخزَّن كلتا العمليتين على سطر ذاكرة التخزين المؤقت نفسه. كل عملية كتابة إلى نهاية ذاكرة التخزين المؤقت تُؤدي إلى إبطال سطر ذاكرة التخزين المؤقت، وهو أمرٌ مرئي لرأس القراءة الأساسي، والعكس صحيح، مما يُؤدي إلى مشاركة خاطئة تُسلسل عمليات كان من المفترض أن تكون مستقلة.

قائمة انتظار MPMC: منتج متعدد المستهلكين

تُعدّ قائمة انتظار MPMC المتزامنة بالكامل أكثر تعقيدًا بشكل ملحوظ. تستخدم تطبيقات الإنتاج رقم تسلسل لكل خانة لتنسيق المنتجين والمستهلكين دون الحاجة إلى قفل.

حزب الشعب الكمبودي

#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;
    }
};

نظام ConcurrentQueue في .NET: كيف يعمل داخليًا

.NET ConcurrentQueue<T> يستخدم .NET 5+ بنية مصفوفة مجزأة. كل جزء عبارة عن مصفوفة ذات حجم ثابت مع فهرس رأس وذيل تتم إدارتهما بواسطة Interlocked العمليات (التي تُطابق CAS على الأجهزة الأساسية). يتم ربط القطاعات عبر متغير متقلب _nextSegment مؤشر. تقوم وظيفة Enqueue بإضافة البيانات إلى الجزء الأخير الحالي، وتزيد من طول سلسلة الأجزاء عند امتلائها. تقوم وظيفة Dequeue بقراءة البيانات من الجزء الأول وتقدم فهرس الرأس بشكل ذري.

يتمثل القرار التصميمي الرئيسي في تجنب الاحتكار العالمي. يتنافس المنتجون فقط على مؤشر الذيل للقطاع الحالي، بينما يتنافس المستهلكون فقط على مؤشر الرأس. لا يتنافس أي منتج مع أي مستهلك. وهذا ما يجعل ConcurrentQueue<T> كفاءة عالية لخطوط الإنتاج والاستهلاك:

CSHARP

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 بايت) الذي يحتوي على ذلك الموقع في ذاكرات التخزين المؤقت لجميع المعالجات الأخرى. ويتعين عليها جلب السطر المُحدَّث قبل القراءة. في التعليمات البرمجية غير المعتمدة على التأمين والتي تتضمن تحديثات ذرية متكررة، قد يصبح إبطال سطر الذاكرة المؤقتة هذا هو التكلفة الرئيسية.

يحدث التشارك الزائف عندما يقوم خيطان بتعديل متغيرات مختلفة تتشارك سطرًا واحدًا في ذاكرة التخزين المؤقت. لا يصل أي من الخيطين إلى نفس البيانات، لكن بروتوكول تماسك ذاكرة التخزين المؤقت يتعامل مع سطر ذاكرة التخزين المؤقت بأكمله على أنه متنازع عليه.

حزب الشعب الكمبودي

// 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 (مُعدَّل، حصري، مشترك، غير صالح) كيفية تنسيق معالجات x86 لملكية خطوط ذاكرة التخزين المؤقت. عندما يرغب أحد النوى في الكتابة إلى موقع مشترك مع نوى أخرى (حالة مشتركة)، يجب عليه بث طلب كتابة، وانتظار تأكيد من جميع النوى المشاركة، ثم الانتقال إلى حالة مُعدَّل. تستغرق هذه العملية ذهابًا وإيابًا إلى بروتوكول التماسك من 50 إلى أكثر من 300 دورة على نظام متعدد المقابس. يؤدي التشارك الزائف إلى تحويل العمليات المحلية المستقلة للخيوط إلى حركة مرور لتماسك ذاكرة التخزين المؤقت، مما يُؤدي إلى انهيار الأداء الذي من المفترض أن يتناسب طرديًا مع عدد النوى.

الكشف عن المشاركات المزيفة: استعمال perf stat -e cache-misses,L1-dcache-load-misses على نظام لينكس أو أداة تحليل أداء وحدة المعالجة المركزية في برنامج فيجوال ستوديو على نظام ويندوز. يُعد ارتفاع معدل أخطاء ذاكرة التخزين المؤقت من المستوى الأول (L1) في برنامج متعدد الخيوط يتناسب مع ذاكرة التخزين المؤقت مؤشرًا قويًا على المشاركة الخاطئة.

ترتيب الذاكرة: لماذا memory_order_relaxed ليس كافياً دائماً

C + + std::atomic تكشف العمليات عن النطاق الكامل لترتيب الذاكرة من نموذج ذاكرة C++11. ويُعد اختيار الترتيب الخاطئ ثاني أكثر الأخطاء شيوعًا في التعليمات البرمجية غير المُقفلة بعد مشكلة ABA.

حزب الشعب الكمبودي

// 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 مؤشر:

حزب الشعب الكمبودي

#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	Counter	بدون قفل	عدّ مخطط عالي الإنتاجية

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الصورة تعيين التبعية يوفر هذا العرض المعماري كيفية ربط مسارات البيانات المتزامنة بالمكونات المكتوبة بلغات مختلفة عبر كامل بنية النظام.

متى يكون الخيار بدون قفل غير مناسب

لا يُعدّ استخدام بنية خالية من الأقفال دائمًا أفضل من استخدام التزامن المتبادل (mutex). يعتمد اختيار البنية الخالية من الأقفال على مستوى التنافس الفعلي في عبء العمل. عند انخفاض عدد الخيوط أو مستوى التنافس، يكون التزامن المتبادل المُنفّذ جيدًا أسرع لأنه يتجنب عبء حلقات إعادة المحاولة الذرية وإبطال صلاحية أسطر ذاكرة التخزين المؤقت عبر النوى.

استخدم قفل التزامن (mutex) عندما:

• عدد الخيوط منخفض (أقل من 4-8) أو أن التنازع غير متكرر
• القسم الحرج طويل ومعقد (تصبح الحلقات غير المقفلة مكلفة نسبيًا بالنسبة لهذا القسم).
• تُعدّ الدقة أهم من الإنتاجية، وتكون الخوارزمية أبسط مع وجود قفل.
• تتميز المنصة بنظام قفل فعال يعتمد على تقنية Futex (لينكس) pthread_mutex(Windows SRWLOCK)

استخدمه بدون قفل عندما:

• عدد الخيوط مرتفع والتنافس مستمر
• العمليات قصيرة (تكلفة حلقة CAS صغيرة نسبيًا مقارنةً بالعملية)
• يُعدّ الحظر غير مقبول (الخيوط في الوقت الحقيقي، معالجات المقاطعات، معالجات الإشارات)
• التأليف مع هياكل أخرى خالية من الأقفال حيث يؤدي القفل إلى إدخال تبعيات ترتيب القفل

استخدم خاصية الانتظار بدون انتظار عندما:

• يجب أن يكتمل كل خيط في وقت محدد بغض النظر عن الخيوط الأخرى
• متطلبات صارمة في الوقت الحقيقي أو متطلبات بالغة الأهمية للسلامة حيث يكون الجوع غير مقبول
• يمكن هيكلة الخوارزمية لدعم إكمال الخطوات المحدودة لكل خيط

إن منهجية البرمجة الخالية من الأقفال لا تكمن في اختيارها في كل مكان، بل في اختيارها بدقة حيث تتطابق خصائصها، مثل التقدم غير المحظور، والقضاء على حالات الجمود، وتحمل الاستباق، مع المتطلبات الفعلية للنظام.