قفل دوار

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

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

يُعدّ تنفيذ أقفال الدوران بشكل صحيح أمرًا صعبًا، إذ يجب على المبرمجين مراعاة إمكانية الوصول المتزامن إلى القفل، مما قد يُسبب حالات تنافس . عمومًا، لا يُمكن تنفيذ هذا النوع من الأقفال إلا باستخدام تعليمات خاصة بلغة التجميع ، مثل عمليات الاختبار والتعيين الذرية (أي غير القابلة للمقاطعة) ، ولا يُمكن تنفيذه بسهولة في لغات البرمجة التي لا تدعم العمليات الذرية الحقيقية. ^{[ 1 ]} في البنى التي لا تدعم هذه العمليات، أو إذا تطلّب الأمر تنفيذًا بلغة عالية المستوى ، يُمكن استخدام خوارزمية قفل غير ذرية، مثل خوارزمية بيترسون . مع ذلك، قد يتطلب هذا النوع من الأقفال ذاكرة أكبر من قفل الدوران، وقد يكون أبطأ في السماح بالتقدم بعد فك القفل، وقد لا يكون قابلًا للتنفيذ بلغة عالية المستوى إذا سُمح بالتنفيذ خارج الترتيب .

يستخدم المثال التالي لغة التجميع x86 لتنفيذ قفل الدوران. وسيعمل على أي معالج متوافق مع Intel 80386 .

بناء جملة Intelمُقفل: ؛ متغير القفل. 1 = مُقفل، 0 = غير مُقفل. dd 0spin_lock: mov eax , 1 ; اضبط قيمة سجل EAX إلى 1. xchg eax , [ locked ] ; قم بتبديل قيمة سجل EAX مع متغير القفل بشكل ذري. سيؤدي هذا دائمًا إلى تخزين القيمة 1 في القفل، تاركًا القيمة السابقة في سجل EAX. test eax , eax ; اختبر قيمة EAX مع نفسها. من بين أمور أخرى، سيؤدي هذا إلى ضبط علامة الصفر للمعالج إذا كانت قيمة EAX تساوي 0. إذا كانت قيمة EAX تساوي 0، فهذا يعني أن القفل قد تم فكه وقمنا بقفله للتو. وإلا، فإن قيمة EAX تساوي 1 ولم نحصل على القفل. jnz spin_lock ; ارجع إلى تعليمة MOV إذا لم يتم ضبط علامة الصفر؛ فقد تم قفل القفل مسبقًا، وبالتالي نحتاج إلى الدوران حتى يتم فكه. ret ; تم الحصول على القفل، ارجع إلى الدالة المستدعِية.spin_unlock: xor eax , eax ; اضبط قيمة سجل EAX إلى 0. xchg eax , [ locked ] ; قم بتبديل قيمة سجل EAX مع متغير القفل بشكل ذري. ret ; تم تحرير القفل.

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

في الإصدارات اللاحقة من معمارية x86، يمكن لـ spin_unlock استخدام MOV غير مقفل بأمان بدلاً من XCHG المقفل الأبطأ. ويعود ذلك إلى قواعد ترتيب الذاكرة الدقيقة التي تدعم ذلك، على الرغم من أن MOV ليس حاجز ذاكرة كامل . مع ذلك، قد تقوم بعض المعالجات (مثل بعض معالجات Cyrix ، وبعض إصدارات Intel Pentium Pro (بسبب وجود أخطاء برمجية)، وأنظمة Pentium و i486 SMP القديمة ) بتصرف خاطئ، مما قد يؤدي إلى تلف البيانات المحمية بالقفل. في معظم المعماريات غير x86، يجب استخدام حاجز ذاكرة صريح أو تعليمات ذرية (كما في المثال). في بعض الأنظمة، مثل IA-64 ، توجد تعليمات "فك قفل" خاصة توفر ترتيب الذاكرة المطلوب.

لتقليل حركة البيانات على ناقل البيانات بين وحدات المعالجة المركزية ، يجب على الكود الذي يحاول الحصول على قفل أن يستمر في القراءة دون محاولة الكتابة حتى يقرأ قيمة متغيرة. وبفضل بروتوكولات التخزين المؤقت MESI ، يصبح خط التخزين المؤقت للقفل "مشتركًا"؛ وبالتالي، تنعدم حركة البيانات على ناقل البيانات بشكل ملحوظ أثناء انتظار وحدة المعالجة المركزية للقفل. يُعد هذا التحسين فعالًا على جميع بنى وحدات المعالجة المركزية التي تحتوي على ذاكرة تخزين مؤقت لكل وحدة، نظرًا لانتشار بروتوكول MESI على نطاق واسع. في وحدات المعالجة المركزية التي تدعم تقنية Hyper-Threading ، يُحسّن الإيقاف rep nopالمؤقت الأداء من خلال الإشارة إلى النواة بإمكانية العمل على الخيط الآخر أثناء انتظار القفل. ^{[ 2 ]}

تُستخدم امتدادات التزامن للمعاملات ومجموعات تعليمات ذاكرة المعاملات الأخرى في الأجهزة كبديل للأقفال في معظم الحالات. ورغم أن الأقفال لا تزال مطلوبة كحل احتياطي، إلا أنها قادرة على تحسين الأداء بشكل كبير من خلال تمكين المعالج من معالجة كتل كاملة من العمليات الذرية. هذه الميزة مُدمجة في بعض تطبيقات التزامن المتبادل، كما هو الحال في مكتبة glibc . يُعدّ حذف قفل الأجهزة (HLE) في معمارية x86 نسخة مُخففة ولكنها متوافقة مع الإصدارات السابقة من امتدادات التزامن للمعاملات، ويمكننا استخدامها هنا للقفل دون فقدان أي توافق. في هذه الحالة تحديدًا، يمكن للمعالج اختيار عدم القفل حتى يحدث تعارض فعلي بين خيطين. ^{[ 3 ]}

يمكن لنسخة أبسط من الاختبار استخدام cmpxchgالتعليمات الموجودة على x86، أو إما التعليمات المضمنة __sync_bool_compare_and_swapالأحدث __atomic_exchange_nالمتوفرة في العديد من مترجمات Unix.

بعد تطبيق التحسينات، سيبدو المثال كالتالي:

في لغة C: while (!__sync_bool_compare_and_swap(&locked, 0, 1)) while (locked) __builtin_ia32_pause(); spin_lock: mov ecx , 1 ; ضبط سجل ECX إلى 1. retry: xor eax , eax ; تصفير EAX، لأن cmpxchg يقارن مع EAX. XACQUIRE lock cmpxchg [ locked ], ecx ; اتخاذ قرار ذري: إذا كان locked يساوي صفرًا، فاكتب ECX إليه. ; يشير XACQUIRE إلى المعالج بأننا نحصل على قفل. je out ; إذا قمنا بقفله (القيمة القديمة تساوي EAX: 0)، فارجع. pause: mov eax , [ locked ] ; قراءة locked في EAX. test eax , eax ; إجراء اختبار الصفر كما كان من قبل. jz retry ; إذا كان يساوي صفرًا، فيمكننا إعادة المحاولة. rep nop ; أخبر وحدة المعالجة المركزية أننا ننتظر في حلقة انتظار، حتى تتمكن من العمل على الخيط الآخر الآن. يُكتب أيضًا كـ "pause". jmp pause ; استمر في التحقق والتوقف المؤقت. out: ret ; تم الانتهاء.spin_unlock: XRELEASE mov [ locked ], 0 ; بافتراض تطبيق قواعد ترتيب الذاكرة، قم بتحرير متغير القفل باستخدام تلميح "تحرير القفل". ret ; تم تحرير القفل.

في أي نظام متعدد المعالجات يستخدم بروتوكول التنافس MESI ، يكون أداء قفل الاختبار والاختبار والتعيين (TTAS) أفضل بكثير من نهج قفل الاختبار والتعيين البسيط (TAS). ^{[ 4 ]}

مع وجود أعداد كبيرة من المعالجات، فإن إضافة تأخير تراجع أسي عشوائي قبل إعادة فحص القفل يؤدي إلى أداء أفضل من TTAS. ^{[ 4 ] [ 5 ]}

تحتوي بعض المعالجات متعددة النوى على تعليمة "قفل الدوران الموفر للطاقة" التي تُدخل المعالج في وضع السكون، ثم تُوقظه في الدورة التالية بعد تحرير القفل. يُعد قفل الدوران باستخدام هذه التعليمات أكثر كفاءة ويستهلك طاقة أقل من أقفال الدوران مع أو بدون حلقة التراجع. ^{[ 6 ]}

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

1. لا تقم بالحصول على القفل. في كثير من الحالات، من الممكن تصميم هياكل بيانات لا تتطلب القفل ، على سبيل المثال باستخدام بيانات خاصة بكل خيط أو لكل وحدة معالجة مركزية وتعطيل المقاطعات .
2. يتم التبديل إلى خيط مختلف أثناء الانتظار. يتضمن هذا عادةً إلحاق الخيط الحالي بقائمة انتظار الخيوط المنتظرة للقفل، ثم التبديل إلى خيط آخر جاهز لأداء عمل مفيد. تتميز هذه الآلية أيضًا بضمان عدم حدوث استنزاف للموارد طالما أن جميع الخيوط تتخلى في النهاية عن الأقفال التي تحصل عليها، ويمكن اتخاذ قرارات جدولة بشأن الخيط الذي يجب أن يتقدم أولاً. تُسمى الأقفال الدورانية التي لا تتطلب التبديل أبدًا، والتي يمكن استخدامها بواسطة أنظمة التشغيل في الوقت الحقيقي ، أحيانًا بالأقفال الدورانية الخام . ^{[ 7 ]}

تستخدم معظم أنظمة التشغيل (بما في ذلك Solaris و Mac OS X و FreeBSD ) نهجًا هجينًا يُسمى " القفل المتبادل التكيفي ". وتتلخص الفكرة في استخدام قفل دوراني عند محاولة الوصول إلى مورد مقفل بواسطة مؤشر ترابط قيد التشغيل حاليًا، ولكن يتم إيقاف التنفيذ مؤقتًا إذا لم يكن مؤشر الترابط قيد التشغيل حاليًا. (وهذا هو الحال دائمًا في الأنظمة أحادية المعالج). ^{[ 8 ]}

حاولت OpenBSD استبدال أقفال الدوران بأقفال التذاكر التي فرضت سلوك "الأول في الأول خارج" ، إلا أن هذا أدى إلى زيادة استهلاك وحدة المعالجة المركزية في النواة، وأصبحت التطبيقات الأكبر حجمًا، مثل Firefox ، أبطأ بكثير. ^{[ 9 ] [ 10 ]}

• التزامن
• دوران مزدحم
• مأزق (علوم الحاسوب)
• سيكلوك
• قفل التذاكر

• توثيق pthread_spin_lock من المواصفات الأساسية لمجموعة Open Group، الإصدار 6، معيار IEEE 1003.1، إصدار 2004
• مجموعة متنوعة من تطبيقات القفل الدوراني من مجموعة أدوات التزامن
• مقال بعنوان " أقفال الدوران على مستوى المستخدم - الخيوط والعمليات والاتصال بين العمليات " بقلم جيرت بودارت
• مثال على قفل دوران المقالة في جافا
• ورقة بحثية بعنوان " أداء بدائل قفل الدوران للمعالجات المتعددة ذات الذاكرة المشتركة " بقلم توماس إي. أندرسون
• ورقة بحثية بعنوان " خوارزميات للتزامن القابل للتوسع على المعالجات المتعددة ذات الذاكرة المشتركة " من تأليف جون إم. ميلور-كرومي ومايكل إل. سكوت . وقد حازت هذه الورقة على جائزة ديكسترا في الحوسبة الموزعة لعام 2006 .
• قفل الدوران والانتظار من تصميم جيفري ريختر
• مرجع فئة SpinLock في لغة C++ النمساوية
• الوصول المتغير المتشابك (ويندوز)
• أنظمة التشغيل: ثلاثة أجزاء سهلة (الفصل: الأقفال)