العمليات الذرية في

نبذة عن العمليات الذرية

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

add qword [rel counter], 5

في الحقيقة، لا يملك المعالج وسيلة للجمع مباشرة في الذاكرة. فهو يفكك هذه التعليمة الواحدة إلى ثلاث خطوات أصغر تُسمى العمليات الدقيقة:

1. القراءة للقيمة الحالية من الذاكرة؛
2. التعديل على هذه القيمة في سجل، بإضافة خمسة إليها؛
3. الكتابة للنتيجة مرة أخرى.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

هذا نمط شائع يُسمى القراءة-التعديل-الكتابة (RMW).

لاحظ أن القراءة (أو التحميل) والكتابة (أو التخزين) حدثان منفصلان، لذا توجد نافذة زمنية بينهما. ولا نلاحظ ذلك عادةً لأن كل تعليمة على نواة واحدة مضمون لها أن تُحدث تأثيرها كاملًا قبل التعليمة التالية. لذا تكون هذه النافذة غير مرئية، ويتصرف add كوحدة واحدة.

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

هذا سباق بيانات، وهو مشكلة شائعة في الكود متعدد الخيوط.

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

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

التبادل الذرّي

تبدّل التعليمة xchg بين مُعطيين. يصبح مُعطى الوجهة مساويًا للقيمة السابقة في مُعطى المصدر، بينما يصبح مُعطى المصدر مساويًا للقيمة السابقة في مُعطى الوجهة. ومن حيث المفهوم، يمكن تصورها كتعليمتي mov تحدثان في آن واحد.

وكما هي الحال عادةً، يمكن استخدامها مع مُعطيين من السجلات، أو مع مُعطى واحد من الذاكرة ومُعطى واحد من السجلات:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

عند استخدامها مع مُعطى من الذاكرة، تكون xchg دائمًا ذرّية. يفرض المعالج قفلًا على الموقع طوال المدة، وهي الآلية نفسها التي تستخدمها البادئة lock مع تعليمات أخرى، كما هو موضح بعد قليل.

بادئة lock

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

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

لا تعمل lock إلا عندما تكون الوجهة ذاكرة، وإلا مع التعليمات التي تقرأ الذاكرة وتعدّلها وتكتب فيها:

1. العمليات الحسابية، مثل add وsub وinc وdec وneg؛
2. العمليات على البتات، مثل and وor وxor وnot؛
3. عمليات البتات bts وbtr وbtc؛
4. بعض التعليمات المتخصصة الأخرى، مثل xadd وcmpxchg، كما هو موضح أدناه.

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

عمليات البتات الذرّية

من بين التعليمات القابلة للإقفال، تتناسب اختبارات البتات بشكل طبيعي مع القفل الدوّار في نهاية هذه الصفحة. تنسخ كل من bts وbtr وbtc بتةً مختارة واحدة إلى راية الحمل، ثم تضبطها أو تصفّرها أو تقلبها. ومع البادئة lock يصبح ذلك قراءة وتعديلًا وكتابة لبتة واحدة: تتغير البتة ذرّيًا، وتبلّغ CF عما كانت عليه قبل ذلك.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

فالضبط الذي يجد البتة مضبوطة بالفعل يعني أن خيطًا آخر قد استحوذ عليها أولًا. وهذه نسخة ببتة واحدة من الاستحواذ على الراية الذي تقوم به xchg على كلمة كاملة.

التبادل والجمع

تحدّث lock add العادية الذاكرة لكنها تتخلص من القيمة القديمة. وغالبًا ما تكون القيمة القديمة هي بالضبط ما نريد، مثل منح كل خيط رقم تذكرة مختلف.

تُرجع التعليمة xadd (حيث x تعني التبادل) القيمة السابقة أثناء الجمع. فهي تكتب المجموع في الوجهة وتترك قيمة الوجهة الأصلية في سجل المصدر.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

ومع البادئة lock يصبح هذا جلبًا وجمعًا ذرّيًا. وعند تشغيلها من عدة خيوط على العدّاد نفسه، يُرجع كل استدعاء قيمة قديمة مختلفة.

وكما في lock add، ينتهي العدّاد عند العدد الدقيق للاستدعاءات. لكن بخلاف lock add، تُرجَع أيضًا كل قيمة وسيطة، واحدة لكل مستدعٍ.

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

المقارنة والتبادل

تضيف xadd وتستبدل xchg، لكن أياً منهما لا يستطيع جعل القيمة الجديدة تعتمد على القيمة الحالية وتطبيقها فقط إذا لم يتغير شيء في الأثناء. هذا التحديث الشرطي هو ما توفره cmpxchg، أو المقارنة والتبادل، وهي الأكثر عمومية بين هذه البدائيات.

تستخدم cmpxchg dest, src السجل rax كمركم ضمني، وتقارنه بـ dest:

• إذا كان dest == rax، فإن dest = src وZF = 1.
• إذا كان dest != rax، فإن rax = dest وZF = 0.

يتبع المركم حجم المُعطى: al للبايت، ثم ax وeax وrax للأحجام الأوسع.

لاحظ أن dest لا يُحدَّث إلا عندما يساوي القيمة المتوقعة المحمّلة سابقًا في rax. تضمن هذه المساواة أن dest لا يزال يحمل القيمة التي حُسبت منها القيمة الجديدة، فلا يُطبَّق أبدًا تحديث مبني على قراءة قديمة. وهذا يجعل cmpxchg حجر الأساس لتحديث ذرّي، يُعرف أيضًا بـ المقارنة والتبديل (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

هذه حلقة إعادة المحاولة هي قلب التحديثات الخالية من الأقفال. النافذة بين القراءة والمقارنة والتبادل هي بالضبط حين قد يتدخل خيط آخر، ويلتقط cmpxchg ذلك برفض تخزين قيمة محسوبة من قراءة قديمة.

هناك تفصيل دقيق يستحق المعرفة. تتحقق cmpxchg من أن القيمة تساوي ما قُرئ، لا من أن الموقع لم يُمسّ قط. إذا نقل خيط آخر القيمة من A إلى B ثم أعادها إلى A داخل النافذة، فإن التبادل ينجح رغم ذلك، حتى لو تغير العالم من تحته.

بالنسبة لعدّاد عادي، هذا غير ضار، لأن العدّاد المتساوي عدّاد جيد بالقدر نفسه. لكنه ليس كذلك بالنسبة لعنوان ذاكرة في رأس قائمة خالية من الأقفال، لأن العنوان نفسه قد يؤدي الآن إلى مكان آخر. وهذه هي مشكلة ABA.

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

لكن لكي ينجح هذا في بيئة متعددة الخيوط، يجب تحديث عنوان الذاكرة وختمه معًا. ولأن عنوان الذاكرة كلمة رباعية كاملة في x86-64، لا تكفي cmpxchg لتحديثه هو وقيمة أخرى في الوقت نفسه.

توجد تعليمة بعرض مزدوج تُسمى cmpxchg16b وهي مكافئة دلاليًا لـ cmpxchg لكنها تعمل على 16 بايت في المرة الواحدة ويمكن استخدامها في تلك الحالة. ليس لها مُعطى مصدر، بل تستخدم rcx:rbx كقيمة بديلة. مُعطاها الوحيد موقع ذاكرة محاذى لـ 16 بايت. تستخدم هذه التعليمة أيضًا rdx:rax كمركم، بدلًا من rax وحده.

ترتيب الذاكرة

لمست كل عملية حتى الآن موقعًا واحدًا. عندما تنسّق الخيوط فيما بينها عبر أكثر من موقع، يظهر سؤال جديد: بأي ترتيب تصبح كتابات خيط ما مرئية لخيط آخر؟ القواعد التي تجيب عن هذا السؤال هي ترتيب الذاكرة لدى المعالج.

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

تحافظ x86-64 على ترتيب ذاكرة قوي بين عمليات التحميل والتخزين العادية، بحيث على كل نواة:

1. لا يُعاد ترتيب تحميل بعد تحميل لاحق؛
2. لا يُعاد ترتيب تخزين بعد تخزين لاحق؛
3. لا يُعاد ترتيب تحميل بعد تخزين لاحق.

إعادة الترتيب الوحيدة الممكنة هي أن يبدو تخزين ما مكتملًا بعد تحميل لاحق من عنوان مختلف.

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

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

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

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

يوجد أيضًا حاجزان أضيق:

• sfence ترتّب الكتابات بعضها بالنسبة إلى بعض، وتهم أساسًا مع عمليات التخزين المتدفقة غير الزمنية؛
• lfence ترتّب القراءات.

أما أنماط الذرّية العادية أعلاه، فالتعليمات المسبوقة بـ lock تحمل بالفعل ترتيبًا كاملًا، لذا لا حاجة إلى حاجز صريح إلا لمصافحة مبنية من عمليات تخزين وتحميل عادية مثل التي أعلاه.

لهذه الضمانات أسماء تتجاوز x86. تكون للعملية دلالة استحواذ عندما لا يمكن أن يبدو أي وصول لاحق متقدمًا عليها، ودلالة تحرير عندما لا يمكن أن يبدو أي وصول سابق متأخرًا عنها. على x86، كل تحميل هو استحواذ، وكل تخزين هو تحرير، والتعليمة المسبوقة بـ lock، أو xchg مع الذاكرة، كلاهما في آن واحد.

الدوران وpause

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

هذه هي الخوارزمية العامة، باستخدام التعليمة xchg مع راية ثنائية:

1. تبدأ الراية عند 0.
2. للحصول على القفل، تبدّل النواة القيمة في الراية بـ 1.
3. إذا كانت القيمة المُرجَعة 1، فهذا يعني أن القفل محتفظ به من نواة أخرى. عندئذ تنتظر النواة الحالية وتحاول الحصول على القفل مرة أخرى.
4. إذا كانت القيمة المُرجَعة 0، فهذا يعني أن القفل كان حرًا. وقد ضبطته xchg الآن على 1، وستنتظر النوى الأخرى حتى تحرره هذه النواة.
5. بمجرد أن تنتهي النواة الحالية من عملها، فإن تحديث الراية بـ 0 يحرر القفل.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

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

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

هناك نسخة مختلفة من هذه الخوارزمية، تُعرف بـ اختبار واختبار وضبط، تختبر (تقرأ) الراية أولًا لتتحقق مما إذا كانت مضبوطة بالفعل. ثم لا تحاول الاختبار والضبط (أي xchg في هذه الحالة) إلا عندما يبدو القفل حرًا:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

بمجرد أن ينتهي الخيط من عمله، يمكنه تحرير القفل بتخزين عادي للقيمة 0 باستخدام mov. لا حاجة إلى أكثر من mov، لأن التحميلات والتخزينات على x86-64 لا يُعاد ترتيبها أبدًا بعد تخزين لاحق. يُقال إن التخزين الذي لا يتجاوز أبدًا عمليات الوصول التي قبله يمتلك ترتيب التحرير، وعلى x86 يحمله كل تخزين عادي.