ليلة الافتتاح

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

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

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

أكثر طريقة شيوعًا لجعل تعليمة ما ذرّية في 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، الموضّحة أدناه.

التبادل والإضافة

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

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

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.

لاحظ أن 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 ذلك برفضه تخزين قيمة محسوبة من قراءة قديمة.

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

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

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

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

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

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

التعليمة المسبوقة بـ 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 صحيحة، لكنها هدرية فقط.

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