خوارزمية بيترسون
خوارزمية بيترسون (أو حل بيترسون ) هي خوارزمية برمجة متزامنة للاستبعاد المتبادل ، تسمح لعمليتين أو أكثر بمشاركة مورد مخصص للاستخدام لمرة واحدة دون تعارض، باستخدام الذاكرة المشتركة فقط للتواصل . صاغها غاري ل. بيترسون عام 1981. [ 1 ] كانت خوارزمية بيترسون الأصلية تعمل مع عمليتين فقط؛ ويمكن تعميمها لتشمل أكثر من عمليتين. [ 2 ]
الخوارزمية
تستخدم الخوارزمية متغيرين: flagو turn. تشير flag[n]قيمة إلى trueأن العملية nترغب في دخول القسم الحرج . يُمنح دخول القسم الحرج للعملية P0 إذا لم ترغب P1 في دخول قسمها الحرج أو إذا أعطت P1 الأولوية لـ P0 عن طريق تعيين turnإلى 0.
volatile bool flag [ 2 ] = { false , false }; volatile int turn ; | |
P0 : flag [ 0 ] = true ; P0_gate : turn = 1 ; while ( flag [ 1 ] && turn == 1 ) { // انتظار مشغول } // القسم الحرج ... // نهاية القسم الحرج flag [ 0 ] = false ; | P1 : flag [ 1 ] = true ; P1_gate : turn = 0 ; while ( flag [ 0 ] && turn == 0 ) { // انتظار نشط } // القسم الحرج ... // نهاية القسم الحرج flag [ 1 ] = false ; |
تُحقق الخوارزمية المعايير الأساسية الثلاثة لحل مشكلة القسم الحرج. ويعمل شرط while حتى مع المقاطعة. [ 1 ]
المعايير الثلاثة هي الاستبعاد المتبادل ، والتقدم، والانتظار المحدود. [ 3 ]
بما أن turnالقيمة يمكن أن تأخذ إحدى قيمتين، فيمكن استبدالها ببت واحد، مما يعني أن الخوارزمية لا تتطلب سوى ثلاثة بتات من الذاكرة. [ 4 ] : 22
الاستبعاد المتبادل
لا يمكن أن يكون كل من P0 وP1 في القسم الحرج في الوقت نفسه. إذا كان P0 في قسمه الحرج، فإن flag[0]الشرط صحيح. بالإضافة إلى ذلك، إما flag[1]أن يكون الشرط false(أي أن P1 قد غادر قسمه الحرج)، أو turnأن يكون 0الشرط (أي أن P1 يحاول الآن دخول القسم الحرج، ولكنه ينتظر)، أو أن يكون P1 عند التسمية P1_gate(يحاول دخول قسمه الحرج، بعد ضبط قيمة المتغير flag[1]على 0 trueولكن قبل ضبط قيمة المتغير turnعلى 00 وهو في حالة انتظار نشط). لذا، إذا كان كلا العمليتين في قسمهما الحرج، نستنتج أن الحالة يجب أن تحقق الشرطين flag[0]و flag[1]و turn = 0و turn = 1. لا يمكن لأي حالة أن تحقق الشرطين معًا turn = 0، turn = 1وبالتالي لا يمكن أن توجد حالة يكون فيها كلا العمليتين في قسمهما الحرج. (هذا يعيد سرد حجة تم توضيحها بدقة في شنايدر 1997. [ 5 ] )
تقدم
يُعرَّف التقدم على النحو التالي: إذا لم يكن أيٌّ من العمليات قيد التنفيذ في قسمه الحرج، ورغبت بعض العمليات في دخول أقسامها الحرجة، فإنّ العمليات التي لا تُنفَّذ في أقسامها المتبقية فقط هي التي يُمكنها المشاركة في اتخاذ القرار بشأن العملية التي ستدخل قسمها الحرج تاليًا. تجدر الإشارة إلى أن الأقسام المتبقية، بالنسبة للعملية أو الخيط، هي أجزاء من التعليمات البرمجية غير المرتبطة بالقسم الحرج. لا يُمكن تأجيل هذا الاختيار إلى أجل غير مسمى. [ 3 ] لا يُمكن لعملية ما أن تعود فورًا إلى القسم الحرج إذا قامت عملية أخرى بتعيين علامتها للإشارة إلى رغبتها في دخول قسمها الحرج.
انتظار مقيد
يعني الانتظار المحدود، أو التجاوز المحدود ، أن عدد مرات تجاوز عملية ما بواسطة عملية أخرى بعد أن تُشير إلى رغبتها في دخول القسم الحرج، يكون محدودًا بدالة لعدد العمليات في النظام. [ 3 ] [ 4 ] : 11 في خوارزمية بيترسون، لن تنتظر أي عملية أكثر من دورة واحدة للدخول إلى القسم الحرج.
خوارزمية التصفية: خوارزمية بيترسون لأكثر من عمليتين
تُعمم خوارزمية التصفية خوارزمية بيترسون لتشمل أكثر من عمليتين (N > 2) . [ 6 ] وبدلاً من استخدام علامة منطقية، تتطلب هذه الخوارزمية متغيرًا صحيحًا لكل عملية، يُخزن في سجل ذري أحادي الكتابة/متعدد القراءة (SWMR) ، بالإضافة إلى N − 1 متغيرًا إضافيًا في سجلات مماثلة. ويمكن تمثيل هذه السجلات في الشفرة الزائفة على شكل مصفوفات .
المستوى: مصفوفة من N عددًا صحيحًا last_to_enter : مصفوفة من N − 1 عدد صحيح
تأخذ متغيرات المستوى قيمًا تصل إلى N − 1 ، حيث يمثل كل منها "غرفة انتظار" مميزة قبل القسم الحرج. [ 6 ] تنتقل العمليات من غرفة إلى أخرى، لتنتهي في الغرفة N − 1 ، وهي القسم الحرج. تحديدًا، للحصول على قفل، تُنفذ العملية i [ 4 ] : 22
i ← ProcessNo لـ ℓ من 0 إلى N − 1 حصريًا المستوى[i] ← ℓ last_to_enter[ℓ] ← i بينما last_to_enter[ℓ] = i ويوجد k ≠ i، بحيث level[k] ≥ ℓ انتظر
لتحرير القفل عند الخروج من القسم الحرج، تقوم العملية i بتعيين المستوى [i] إلى -1.
يمكن إثبات أن هذه الخوارزمية تحقق الاستبعاد المتبادل كما يلي: تخرج العملية i من الحلقة الداخلية عندما لا توجد عملية بمستوى أعلى من المستوى [i] ، وبالتالي تكون غرفة الانتظار التالية متاحة؛ أو عندما يكون i ≠ last_to_enter[ℓ] ، أي أن عملية أخرى انضمت إلى غرفة انتظارها. عند المستوى صفر، حتى لو دخلت جميع العمليات N غرفة الانتظار صفر في الوقت نفسه، فلن يتقدم أكثر من N − 1 عملية إلى الغرفة التالية، وستكون العملية الأخيرة هي الأخيرة التي تدخل الغرفة. وبالمثل، في المستوى التالي، ستتقدم N − 2 عملية، وهكذا ، حتى المستوى الأخير، حيث يُسمح لعملية واحدة فقط بمغادرة غرفة الانتظار ودخول القسم الحرج، مما يحقق الاستبعاد المتبادل. [ 4 ] : 22-24
بخلاف خوارزمية بيترسون ثنائية العمليات، لا تضمن خوارزمية التصفية انتظارًا محدودًا. [ 4 ] : 25-26
مشاكل العصر الحديث
في الأجهزة الحديثة، تفشل خوارزمية بيترسون (كما هو موضح هنا) في توفير الاستبعاد المتبادل. يمكن لبعض التصريحات و/أو التعليمات الإضافية أن تجعلها تعمل (مع أن طرقًا مختلفة تستخدم ميزات اللغة و/أو تعليمات الآلة الجديدة يمكنها تحقيق الاستبعاد المتبادل بكفاءة أكبر). لقد أصبحت الحواسيب أكثر تعقيدًا بكثير منذ عام 1981؛ فلم تعد تُنفذ التعليمات بشكل متزامن. تُغير معظم المُترجمات ترتيب العمليات بطرق تُنتج نفس النتائج بشكل أسرع، لكنها لا تُراعي تفاعل العمليات المتزامنة التي تصل إلى نفس البيانات. تُعيد وحدات المعالجة المركزية ترتيب التعليمات داخل مسارات التنفيذ الخاصة بها. تقرأ وحدات المعالجة المركزية محتويات الذاكرة مسبقًا، وتُخزن محتويات ذاكرة التخزين المؤقت، وتُؤخر عمليات الكتابة وتُدمجها. يمكن لعدة نوى معالجة مركزية الوصول إلى نفس الذاكرة بتزامن حقيقي. يمكن أن تحتوي وحدات المعالجة المركزية المتعددة على ذاكرات تخزين مؤقت منفصلة تُؤخر التزامن. أي من هذه العوامل يُمكن أن يُعطل خوارزمية بيترسون. [ 7 ] للسماح بالاستبعاد المتبادل القابل للاستخدام في هذه البيئة الجديدة، تمت إضافة تعليمات الآلة، مثل حاجز الذاكرة وعمليات القراءة والتعديل الذرية. تُتيح هذه التعليمات "اللحاق بالركب" عند الضرورة. أضافت لغات البرمجة ميزات تستدعي هذه التعليمات. في العديد من اللغات، يؤدي تعريف متغير على أنه متقلب إلى إنتاج كود قابل للتنفيذ يصل إلى المتغير بحذر أكبر.
لا تُستخدم خوارزمية بيترسون عادةً لضمان الوصول الذري. في المعالجات وأنظمة التشغيل القديمة، كان يكفي تعطيل المقاطعات مباشرةً قبل القسم الحرج، ثم إعادة تفعيلها بعد اكتماله. تحتوي معظم المعالجات الحديثة على تعليمات خاصة تُتيح إنشاء عناصر التزامن بكفاءة أعلى من تلك المُتاحة باستخدام أساليب الذاكرة المشتركة البحتة. يمكن استخدام هذه التعليمات، من خلال قفل ناقل الذاكرة ، لضمان الذرية وتوفير الاستبعاد المتبادل في أنظمة المعالجة المتعددة المتناظرة . تشمل الأمثلة تعليمات الاختبار والتعيين (test-and-set ) XCHGوالمقارنة والتبديل (compare-and-swap ) CMPXCHGعلى معالجات x86 ، وتعليمات التحميل والربط/التخزين المشروط (load-link/store-conditional ) على معالجات Alpha و MIPS و PowerPC وغيرها من البنى.
تُعيد معظم وحدات المعالجة المركزية الحديثة ترتيب عمليات الوصول إلى الذاكرة لتحسين كفاءة التنفيذ (راجع ترتيب الذاكرة للاطلاع على أنواع إعادة الترتيب المسموح بها). توفر هذه المعالجات دائمًا طريقة ما لفرض الترتيب في سلسلة عمليات الوصول إلى الذاكرة، عادةً من خلال تعليمة حاجز الذاكرة . يتطلب تطبيق خوارزمية بيترسون والخوارزميات ذات الصلة على المعالجات التي تُعيد ترتيب عمليات الوصول إلى الذاكرة استخدام هذه العمليات لضمان عملها بشكل صحيح ومنع حدوث العمليات المتسلسلة بترتيب خاطئ. يمكن أن تحدث إعادة ترتيب عمليات الوصول إلى الذاكرة حتى على المعالجات التي لا تُعيد ترتيب التعليمات (مثل معالج PowerPC في جهاز Xbox 360 ).
انظر أيضاً
الحواشي
- 1 2 جي. إل. بيترسون: "خرافات حول مشكلة الاستبعاد المتبادل"، رسائل معالجة المعلومات 12(3) 1981، 115-116
- ↑ كما نوقش في مراجعة أنظمة التشغيل ، يناير 1990 ("إثبات خوارزمية الاستبعاد المتبادل"، م. هوفري).
- 1 2 3 سيلبرشاتز. مفاهيم أنظمة التشغيل: الطبعة السابعة. جون وايلي وأولاده، 2005، الصفحة 194.
- 1 2 3 4 5 راينال، ميشيل (2012). البرمجة المتزامنة: الخوارزميات والمبادئ والأسس . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-3642320279.
- ↑ FB Schneider, On Concurrent Programming , Springer Verlag, 1997, pages 185–196.
- 1 2 هيرليهي، موريس ؛ شافيت، نير (2012). فن برمجة المعالجات المتعددة . إلسيفير. ص 28-31 . ISBN 9780123977953.
- ↑ خوارزمية الثمانينيات لتجنب حالات التزامن (ولماذا فشلت) .
روابط خارجية
- https://elixir.bootlin.com/linux/v5.6.19/source/arch/arm/mach-tegra/sleep-tegra20.S#L120 مثال على خوارزمية بيترسون التي كانت تستخدم سابقًا في نواة لينكس ( تمت إزالتها في الإصدار 5.7).
- خوارزميات التحكم في التزامن