خوارزمية ديكر

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

يتجنب هذا الأسلوب التناوب الصارم لخوارزمية تبادل الأدوار البسيطة، وكان أحد أوائل خوارزميات الاستبعاد المتبادل التي تم اختراعها.

إذا حاول عمليتان الدخول إلى قسم حرج في الوقت نفسه، فإن الخوارزمية ستسمح لعملية واحدة فقط بالدخول، بناءً على دورها . إذا كانت إحدى العمليتين موجودة بالفعل في القسم الحرج، فستنتظر العملية الأخرى خروج العملية الأولى. يتم ذلك باستخدام علامتين، wants_to_enter[0] و wants_to_enter[1] ، تشيران إلى نية العمليتين 0 و1 على التوالي في دخول القسم الحرج، ومتغير turn الذي يحدد أولوية العمليتين.

يمكن التعبير عن خوارزمية ديكر بلغة شبه رمزية ، كما يلي. ^{[ 3 ]}

 المتغيرات wants_to_enter : مصفوفة من قيمتين منطقيتين الدور: عدد صحيح wants_to_enter[0] ← false wants_to_enter[1] ← خطأ انعطف ← 0 // أو 1 

p0: wants_to_enter[0] ← صحيح بينما يريد الدخول[1] { إذا كان الدور ≠ 0 { wants_to_enter[0] ← false بينما لا يساوي الدوران صفرًا { // انتظار مشغول } wants_to_enter[0] ← صحيح } } // القسم الحرج ... انعطف ← 1 wants_to_enter[0] ← false // قسم الباقي 

ص1: wants_to_enter[1] ← صحيح بينما يريد الدخول[0] { إذا كان الدور ≠ 1 { wants_to_enter[1] ← خطأ بينما لا يساوي الدور 1 { // انتظار مشغول } wants_to_enter[1] ← صحيح } } // القسم الحرج ... انعطف ← 0 wants_to_enter[1] ← خطأ // قسم الباقي 

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

تضمن خوارزمية ديكر الاستبعاد المتبادل ، والتحرر من حالة الجمود ، والتحرر من حالة التجويع . دعونا نرى لماذا تتحقق الخاصية الأخيرة. لنفترض أن p0 عالق داخل حلقة while wants_to_enter[1] إلى الأبد. هناك تحرر من حالة الجمود، لذا سينتقل p1 في النهاية إلى قسمه الحرج ويُعيّن قيمة turn إلى 0 (وستبقى قيمة turn ثابتة طالما لم يتقدم p0). في النهاية، سيخرج p0 من حلقة while turn ≠ 0 الداخلية (إذا كان عالقًا فيها من قبل). بعد ذلك، سيُعيّن قيمة wants_to_enter[0] إلى true ويستقر في انتظار أن تصبح قيمة wants_to_enter[1] خاطئة (بما أن turn = 0 ، فلن يُنفّذ الإجراءات في حلقة while). في المرة التالية التي يحاول فيها p1 دخول قسمه الحرج، سيُجبر على تنفيذ الإجراءات في حلقة while wants_to_enter[0] . على وجه الخصوص، سيؤدي ذلك في النهاية إلى تعيين قيمة `wants_to_enter[1]` إلى `false`، وسيعلق البرنامج في حلقة ` while turn ≠ 1` (لأن قيمة `turn` تبقى 0). في المرة التالية التي ينتقل فيها التحكم إلى `p0`، سيخرج البرنامج من حلقة ` while wants_to_enter[1]` ويدخل قسمها الحرج.

إذا تم تعديل الخوارزمية بتنفيذ الإجراءات في حلقة while wants_to_enter[1] دون التحقق مما إذا كان turn = 0 ، فهناك احتمال لحدوث مأزق. لذا، فإن جميع خطوات الخوارزمية ضرورية.

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

توفر أنظمة التشغيل الحديثة آليات استبعاد متبادل أكثر عمومية ومرونة من خوارزمية ديكر. مع ذلك، في حال عدم وجود تنازع فعلي بين العمليتين، يكون الدخول والخروج من القسم الحرج فعالاً للغاية عند استخدام خوارزمية ديكر.

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

بالإضافة إلى ذلك، يمكن للعديد من مُجمِّعات التحسين إجراء تحويلات تُؤدي إلى فشل هذه الخوارزمية بغض النظر عن النظام الأساسي. في العديد من لغات البرمجة، يُسمح للمُجمِّع باكتشاف عدم الوصول إلى متغيري الراية ` wants_to_enter[0]` و` wants_to_enter[1]` داخل الحلقة. عندئذٍ، يُمكنه إزالة عمليات الكتابة إلى هذين المتغيرين من الحلقة، باستخدام عملية تُسمى نقل الكود غير المتأثر بالحلقة . كما يُمكن للعديد من المُجمِّعات اكتشاف عدم تعديل المتغير `turn` بواسطة الحلقة الداخلية، وإجراء تحويل مماثل، مما قد يُؤدي إلى حلقة لا نهائية . في حال إجراء أي من هذين التحويلين، ستفشل الخوارزمية بغض النظر عن بنية النظام.

للتخفيف من هذه المشكلة، ينبغي وضع علامة "volatile " على المتغيرات القابلة للتعديل خارج نطاق سياق التنفيذ الحالي. على سبيل المثال، في لغات C وC++ وC# وجافا، تُعرَّف هذه المتغيرات بأنها "volatile". مع ذلك، تجدر الإشارة إلى أن خاصية "volatile" في C/C++ تضمن فقط أن يُولِّد المُصرِّف شيفرةً بالترتيب الصحيح؛ فهي لا تتضمن حواجز الذاكرة اللازمة لضمان تنفيذ تلك الشيفرة بالتسلسل الصحيح . يمكن استخدام المتغيرات الذرية في C++11 لضمان متطلبات الترتيب المناسبة - افتراضيًا، تكون العمليات على المتغيرات الذرية متسقة تسلسليًا، لذا إذا كان المتغيران wants_to_enter وturn ذريين، فسيعمل التنفيذ البسيط تلقائيًا. بدلاً من ذلك، يمكن ضمان الترتيب من خلال الاستخدام الصريح لحواجز منفصلة، ​​مع استخدام ترتيب مُخفَّف لعمليات التحميل والتخزين.

• خوارزمية أيزنبرغ وماكغواير
• خوارزمية بيترسون
• خوارزمية مخبز لامبورت
• خوارزمية شيمانسكي
• إشارات المرور