الاستبعاد المتبادل الموزع وانتخاب القائد
يُعد الاستبعاد المتبادل وانتخاب القائد من المشكلات التنسيقية الكلاسيكية: ضمان وصول عملية واحدة على الأكثر إلى مورد حرج، واختيار منسق مميز واحد من بين الأقران.
Definition
يضمن الاستبعاد المتبادل الموزع أن عملية واحدة على الأكثر تحتفظ بمورد مشترك في كل مرة مع ضمان الوصول النهائي لجميع طالبي الخدمة؛ يختار انتخاب القائد بشكل حتمي عملية واحدة بالضبط كمنسق، مع موافقة جميع العمليات على النتيجة.
Scope
يغطي هذا الموضوع خوارزميات الاستبعاد المتبادل القائمة على الأذونات (خوارزمية لامبورت للطوابع الزمنية، ريكارت-أغراوالا، نهج مايكاوا للحصص) والخوارزميات القائمة على الرموز، بالإضافة إلى تعقيد رسائلها وخصائص الإنصاف؛ وخوارزميات انتخاب القائد للحلقات (تشانغ-روبرتس) والشبكات العامة (خوارزمية المتنمر)، بما في ذلك افتراضاتها حول المعرفات والتزامن. تتكرر هذه البدائيات في جميع خدمات التنسيق والأنظمة المنسوخة.
Core questions
- كيف يمكن للعمليات تسلسل الوصول إلى مورد مشترك باستخدام الرسائل فقط؟
- ما هي المقايضات بين تعقيد الرسائل والإنصاف بين المخططات القائمة على الأذونات والمخططات القائمة على الرموز؟
- كيف يتم اختيار قائد فريد، وكيف يتم إعادة تشغيل الانتخاب بعد فشل القائد؟
Key theories
- الاستبعاد المتبادل القائم على الأذونات
- تقوم الخوارزميات مثل ريكارت-أغراوالا بترتيب الطلبات حسب الطوابع الزمنية المنطقية وتمنح الدخول بمجرد حصول الطالب على إذن من جميع الأقران (أو حصة منهم)، مما يحقق الإنصاف بتكلفة رسائل محدودة لكل دخول إلى القسم الحرج.
- الاستبعاد المتبادل القائم على الرموز
- يتم تداول رمز فريد أو طلبه عند الطلب، ويجوز لحامله فقط الدخول إلى القسم الحرج، مما يقلل من حركة الرسائل ولكنه يتطلب آليات لإعادة إنشاء رمز مفقود بعد الأعطال.
- انتخاب القائد
- تستخدم خوارزميات الانتخاب مثل تشانغ-روبرتس للحلقات وخوارزمية المتنمر للشبكات العامة معرفات العمليات للتقارب على منسق واحد ذي أولوية قصوى تتعرف عليه جميع العمليات الصحيحة.
Clinical relevance
يتم استدعاء انتخاب القائد كلما احتاج نظام منسوخ إلى اختيار أساسي أو منسق، ويعمم القفل الموزع الاستبعاد المتبادل؛ وكلاهما مكشوف كخدمات أساسية بواسطة أنظمة التنسيق المستخدمة في جميع أنحاء البنية التحتية السحابية.
History
قدمت ورقة لامبورت عام 1978 حول الساعات المنطقية خوارزمية استبعاد متبادل قائمة على الطوابع الزمنية؛ قام ريكارت وأغراوالا بتحسينها في عام 1981، وقدم مايكاوا الحصص بعد ذلك بوقت قصير، وقامت خوارزمية المتنمر لغارسيا-مولينا عام 1982 بإضفاء الطابع الرسمي على انتخاب القائد، مما أعطى المجال خوارزمياته التنسيقية الأساسية.
Key figures
- Leslie Lamport
- Glenn Ricart
- Ashok Agrawala
- Hector Garcia-Molina
Related topics
Seminal works
- ricart1981
- garcia-molina1982
- lynch1996
Frequently asked questions
- كيف يختلف الاستبعاد المتبادل الموزع عن القفل على جهاز واحد؟
- لا توجد ذاكرة مشتركة أو مدير قفل مركزي يمكن الاعتماد عليه، لذلك يجب على العمليات التنسيق فقط من خلال تبادل الرسائل ويجب عليها التعامل بشكل صريح مع تأخير الرسائل والأعطال، وهو ما يمكن لقفل الجهاز الواحد أن يعتبره أمرًا مسلمًا به.