الاستبعاد المتبادل

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 3 صور
الموسوعة الحرة

يؤدي حذف عقدتين، i و i + 1 ، في وقت واحد إلى عدم حذف العقدة i + 1 .

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

المورد المشترك هو كائن بيانات ، تحاول عمليتان أو أكثر من العمليات المتزامنة تعديله (حيث يُسمح بعمليتي قراءة متزامنتين، ولكن لا يُسمح بعمليتي كتابة متزامنتين، أو عملية قراءة وأخرى كتابة، لأن ذلك يؤدي إلى عدم اتساق البيانات). تضمن خوارزميات الاستبعاد المتبادل أنه إذا كانت عملية ما تُجري بالفعل عملية كتابة على كائن بيانات [قسم حرج]، فلا يُسمح لأي عملية/خيط آخر بالوصول إلى/تعديل نفس الكائن حتى تنتهي العملية الأولى من الكتابة على كائن البيانات [قسم حرج] وتُحرر الكائن للعمليات الأخرى للقراءة والكتابة عليه.

تم تحديد شرط الاستبعاد المتبادل وحله لأول مرة بواسطة إدسكار دبليو ديكسترا في بحثه الرائد عام 1965 بعنوان "حل مشكلة في التحكم بالبرمجة المتزامنة"، [ 1 ] [ 2 ] والذي يُعتبر أول موضوع في دراسة الخوارزميات المتزامنة. [ 3 ]

يمكن توضيح أهمية الاستبعاد المتبادل عمليًا من خلال مثال بسيط، وهو استخدام قائمة مرتبطة أحادية مكونة من أربعة عناصر، حيث يُراد حذف العنصرين الثاني والثالث. تتم إزالة العقدة الواقعة بين عقدتين أخريين بتغيير مؤشر " التالي " للعقدة السابقة ليشير إلى العقدة التالية (بمعنى آخر، إذا كانت العقدة i تُحذف، فإن مؤشر "التالي " للعقدة i - 1 يُغيّر ليشير إلى العقدة i + 1 ، وبالتالي يُحذف أي مرجع للعقدة i من القائمة المرتبطة ). عند مشاركة هذه القائمة المرتبطة بين عدة سلاسل تنفيذ، قد تحاول سلسلتان حذف عقدتين مختلفتين في الوقت نفسه؛ حيث تُغيّر إحداهما مؤشر " التالي " للعقدة i - 1 ليشير إلى العقدة i + 1 ، بينما تُغيّر الأخرى مؤشر " التالي " للعقدة i ليشير إلى العقدة i + 2. على الرغم من نجاح عمليتي الحذف، إلا أن الحالة المطلوبة للقائمة المرتبطة لا تتحقق: تبقى العقدة i + 1 في القائمة، لأن مؤشر " التالي " للعقدة i - 1 يشير إلى العقدة i + 1 .

يمكن تجنب هذه المشكلة (التي تسمى حالة التنافس ) باستخدام شرط الاستبعاد المتبادل لضمان عدم حدوث تحديثات متزامنة لنفس الجزء من القائمة.

يُستخدم مصطلح الاستبعاد المتبادل أيضًا للإشارة إلى الكتابة المتزامنة لعنوان الذاكرة بواسطة خيط واحد بينما يتم التلاعب بعنوان الذاكرة المذكور أعلاه أو قراءته بواسطة خيط واحد أو أكثر من الخيوط الأخرى.

وصف المشكلة

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

يجب أن يتضمن الحل الناجح لهذه المشكلة هاتين الخاصيتين على الأقل:

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

يمكن توسيع نطاق حرية الوصول إلى حالة الجمود لتنفيذ إحدى هاتين الخاصيتين أو كلتيهما:

  • يضمن مبدأ عدم وجود عمليات حظر الوصول أن أي عملية ترغب في دخول القسم الحرج ستتمكن من ذلك في نهاية المطاف. وهذا يختلف عن تجنب حالة الجمود ، الذي يتطلب أن تتمكن عملية منتظرة من الوصول إلى القسم الحرج، ولكنه لا يشترط أن تحصل كل عملية على دورها. فإذا تبادلت عمليتان موردًا بينهما باستمرار، فقد تُحظر عملية ثالثة وتواجه نقصًا في الموارد ، حتى وإن لم يكن النظام في حالة جمود. أما إذا كان النظام خاليًا من عمليات الحظر، فإنه يضمن أن تحصل كل عملية على دورها في وقت ما في المستقبل.
  • تُوفر خاصية الانتظار المحدود بـ k التزامًا أدق من خاصية عدم الحظر. تضمن خاصية عدم الحظر وصول كل عملية إلى القسم الحرج في نهاية المطاف، لكنها لا تُقدم أي ضمان بشأن مدة الانتظار. عمليًا، قد تتجاوز عمليات أخرى ذات أولوية أعلى عمليةً ما عددًا غير محدود من المرات قبل أن يحين دورها. أما في ظل خاصية الانتظار المحدود بـ k ، فلكل عملية حد أقصى لوقت الانتظار. يتحقق ذلك من خلال وضع حد لعدد مرات دخول العمليات الأخرى إلى القسم الحرج، بحيث لا تستطيع أي عملية دخول القسم الحرج أكثر من k مرة أثناء انتظار عملية أخرى. [ 4 ]

يمكن تقسيم برنامج كل عملية إلى أربعة أقسام، مما ينتج عنه أربع حالات. وتمر دورات تنفيذ البرنامج بهذه الحالات الأربع بالترتيب التالي: [ 5 ]

دورة أقسام عملية واحدة
القسم غير الحرج
العملية خارج القسم الحرج؛ فالعملية لا تستخدم أو تطلب المورد المشترك.
محاولة
تحاول العملية الدخول إلى القسم الحرج.
القسم الحرج
يُسمح للعملية بالوصول إلى المورد المشترك في هذا القسم.
مخرج
تغادر العملية القسم الحرج وتجعل المورد المشترك متاحًا للعمليات الأخرى.

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

فرض الاستبعاد المتبادل

حلول الأجهزة

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

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

يمكن استخدام العديد من العمليات الذرية الأخرى لتوفير استبعاد متبادل لهياكل البيانات؛ وأبرزها عملية المقارنة والتبديل (CAS). تُستخدم CAS لتحقيق استبعاد متبادل فوري لأي هيكل بيانات مشترك، وذلك بإنشاء قائمة مرتبطة حيث يمثل كل عقدة العملية المطلوبة. ثم تُستخدم CAS لتغيير المؤشرات في القائمة المرتبطة [ 6 ] أثناء إضافة عقدة جديدة. لا يمكن إلا لعملية واحدة أن تنجح في عملية CAS الخاصة بها؛ أما العمليات الأخرى التي تحاول إضافة عقدة في الوقت نفسه، فسيتعين عليها المحاولة مرة أخرى. يمكن لكل عملية الاحتفاظ بنسخة محلية من هيكل البيانات، وعند اجتياز القائمة المرتبطة، يمكنها تنفيذ كل عملية من القائمة على نسختها المحلية.

حلول برمجية

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

لا تعمل هذه الخوارزميات إذا تم استخدام التنفيذ خارج الترتيب على المنصة التي تُنفذها. يجب على المبرمجين تحديد ترتيب صارم لعمليات الذاكرة داخل سلسلة العمليات. [ 8 ]

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

مقيد بمشكلة الاستبعاد المتبادل

يكفي سجل اختبار وتعيين ثنائي واحد لتوفير حل خالٍ من حالات الجمود لمشكلة الاستبعاد المتبادل. لكن الحل المبني باستخدام سجل اختبار وتعيين قد يؤدي إلى حرمان بعض العمليات التي تتعثر في قسم المحاولة من الموارد. [ 4 ] في الواقع،Ω(ن){\displaystyle \Omega ({\sqrt {n}})}يلزم وجود حالات ذاكرة منفصلة لتجنب الإغلاق. ولتجنب الانتظار غير المحدود، يلزم وجود n حالة ذاكرة منفصلة. [ 11 ]

الاستبعاد المتبادل القابل للاسترداد

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

أنواع أجهزة الاستبعاد المتبادل

يمكن استخدام الحلول الموضحة أعلاه لبناء عناصر التزامن الأساسية الموضحة أدناه:

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

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

انظر أيضاً

مراجع

  1. ↑ ديكسترا، إي دبليو (1965). "حل مشكلة في التحكم بالبرمجة المتزامنة" . اتصالات رابطة مكائن ​​الحوسبة . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID 19357737 . 
  2. 1 2 تاوبنفيلد، "خوارزمية المخبز الأبيض والأسود" . في وقائع مؤتمر الحوسبة الموزعة، المؤتمر الدولي الثامن عشر، DISC 2004. المجلد 18، الصفحات 56-70، 2004
  3. ↑ "جائزة PODC للأوراق البحثية المؤثرة: 2002" ، ندوة ACM حول مبادئ الحوسبة الموزعة ، تم الاطلاع عليها بتاريخ 24 أغسطس 2009
  4. 1 2 عطية، هاجيت ؛ ويلش، جينيفر (25 مارس 2004). الحوسبة الموزعة: الأساسيات، والمحاكاة، والمواضيع المتقدمة . جون وايلي وأولاده، المحدودة. ISBN 978-0-471-45324-6.
  5. ↑ لامبورت، ليزلي (26 يونيو 2000)، "مشكلة الاستبعاد المتبادل الجزء الثاني: البيان والحلول" (ملف PDF) ، مجلة رابطة آلات الحوسبة ، 33 (2): 313-348 ، doi : 10.1145/5383.5384 ، S2CID 12012739 
  6. ↑ هاريس، تيموثي ل. (2001). "تطبيق عملي للقوائم المرتبطة غير المحظورة" (ملف PDF) . الحوسبة الموزعة . سلسلة محاضرات في علوم الحاسوب. 2180 : 300-314 . doi : 10.1007/3-540-45414-4_21 . ISBN 978-3-540-42605-9تم الاطلاع عليه بتاريخ 1 ديسمبر 2022 .
  7. ↑ لامبورت، ليزلي (أغسطس 1974). "حل جديد لمسألة البرمجة المتزامنة لديكسترا" . مجلة اتصالات رابطة مكائن ​​الحوسبة . 17 (8): 453-455 . doi : 10.1145/361082.361093 . S2CID 8736023 . 
  8. ↑ هولزمان، جيرارد جيه؛ بوسناكي، دراغان (1 أكتوبر 2007). "تصميم امتداد متعدد النوى لمدقق نموذج SPIN" ( ملف PDF) . معاملات IEEE في هندسة البرمجيات . 33 (10): 659-674 . doi : 10.1109/TSE.2007.70724 . S2CID 9080331. مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022. 
  9. ↑ سيلبرشاتز، أبراهام؛ جالفين، بيتر ب.؛ غاني، جريج (2018). مفاهيم أنظمة التشغيل ( الطبعة العاشرة). وايلي. الصفحات 233-239 . ISBN   978-1119320913.
  10. ↑ هيرليهي، موريس ؛ شافيت، نير (2012). فن برمجة المعالجات المتعددة ( الطبعة الثانية). مورغان كوفمان. الصفحات 11-15 . ISBN   978-0123973375.
  11. ↑ بيرنز، جيمس إي؛ بول جاكسون، نانسي أ. لينش (يناير 1982)، "متطلبات البيانات لتنفيذ الاستبعاد المتبادل للعمليات المتعددة باستخدام متغير مشترك واحد" (ملف PDF) ، مجلة رابطة آلات الحوسبة ، 33 (2 ) : 313-348
  12. ↑ جولاب، فويتش؛ راماراجو، أديتيا (يوليو 2016)، "الاستبعاد المتبادل القابل للاسترداد" ، وقائع ندوة ACM لعام 2016 حول مبادئ الحوسبة الموزعة ، الصفحات 65-74 ، doi : 10.1145/2933057.2933087 ، ISBN  9781450339643، S2CID 8621532 
  13. ^ بليبرجر، يوهان. بورغستالر، بيرند (2018)، كاسيميرو، أنطونيو؛ فيريرا، بيدرو م. (محرران)، “التزامن الآمن غير المحظور في Ada2x” ، تقنيات البرمجيات الموثوقة – Ada-Europe 2018 ، المجلد. 10873، شام: سبرينغر إنترناشيونال للنشر، الصفحات من 53 إلى 69، دوى : 10.1007/978-3-319-92432-8_4 ، ISBN   978-3-319-92431-1تم الاطلاع عليه بتاريخ 23 يونيو 2026{{citation}}: CS1 maint: work parameter with ISBN ( link )

للمزيد من القراءة

  • ميشيل رينال: خوارزميات الاستبعاد المتبادل ، مطبعة معهد ماساتشوستس للتكنولوجيا، ISBN 0-262-18119-3
  • سونيل ر. داس، براديب ك. سريماني: خوارزميات الاستبعاد المتبادل الموزعة ، جمعية مهندسي الكهرباء والإلكترونيات (IEEE)، رقم ISBN 0-8186-3380-8
  • توماس دبليو. كريستوفر، جورج ك. ثيروفاثوكال: الحوسبة عالية الأداء لمنصة جافا ، برنتيس هول، رقم ISBN 0-13-016164-0
  • غادي تاوبنفيلد، خوارزميات التزامن والبرمجة المتزامنة ، بيرسون/برنتيس هول، رقم ISBN 0-13-197259-6