الاستعصاءات Deadlocks

. مدخل إلى الاستعصاءات:

يمكن تعريف الاستعصاء بدقة كما يلي:

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

$الاستعصاءات Deadlocks 06-01$

لنفرض على سبيل المثال أن لدينا عمليتين A و B كل منهما تقوم بقراءة مستند
من الماسح الضوئي scanner ثم تنسخه إلى قرص مدمج compact disk.

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

كلتا العمليتين هنا جامدة، وستبقى كذلك للأبد...تدعى هذه الحالة بالاستعصاء deadlocks

$الاستعصاءات Deadlocks 06-05$

يمكن للاستعصاءات أن تقع في حالات كثيرة وليس فقط ضمن العتاد كما هو المثال السابق. الاستعصاءات البرمجية software deadlocks كثيرة الحدوث أيضاً. على سبيل المثال إذا كان لدينا نظام قواعد بيانات، ربما يقوم برنامج بقفل (حجز) مجموعة من السجلات التي يستخدمها لكي لا يقع في مشكلة
التسابق عليها مع برامج أخرى. عندها إذا كانت العملية A تقفل السجل R1
والعملية B تقفل السجل R2 ثم حاولت كل منهما أن تقفل السجل الآخر فإنه
يتشكل لدينا استعصاء. لذلك فإن الاستعصاءات يمكن أن تحدث في العتاد
hardware أو في البرامج software.

2.الموارد resources :

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

1.2 الموارد القابلة للاستيلاء preemptable resources والموارد الغير قابلة للاستيلاء nonpreemptable resources:

يمكن أن نصنّف الموارد ضمن نوعين: قابلة للاستيلاء preemptable وغير قابلة
للاستيلاء nonpreemptable. المورد القابل للاستيلاء هو المورد الذي يمكن
ان ننتزعه من العملية التي تستخدمه دون أن يسبب ذلك حدوث مشكلة. وتعتبر
الذاكرة مثالاً على الموارد القابلة للاستيلاء. خذ على سبيل المثال نظام
حاسب يحوي 32 ميغا بايت من الذاكرة، ويحوي طابعة وعمليتين A و B كلٌ منهما
تحتاج 32 ميغا بايت وتريدان طباعة شيء ما على الطابعة.

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

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

وعلى العكس فإن الموارد غير القابلة للاستيلاء هي الموارد التي لايمكن
انتزاعها من صاحبها دون حدوث فشل في الحسابات. على سبيل المثال إذا بدأت
عملية ما بالنسخ على قرص مدمج وفجأة تم انتزاع ناسخة القراص المدمجة منها
وأعطيت لعملية اخرى فسيؤدي ذلك إلى عطب القرص. إن ناسخات القراص المدمجة
CD-ROM ليست قابلة للاستيلاء متى نريد.

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

إن الخطوات التي تمر بها عملية استخدام مورد ما هي:

1. طلب المورد.
2. استخدام المورد.
3. تحرير المورد.

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

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

تتعلق كيفية طلب المورد بنظام التشغيل بشكل كبير. ففي بعض الأنظمة يوجد
استدعاء نظام system call يدعى request للسماح للعمليات بطلب الموارد بشكل
صريح، أما في بعض الأنظمة الأخرى فتكون الموارد الوحيدة التي يعلم النظام
بها عبارة عن مجموعة من الملفات التي يمكن لعملية واحدة فقط أن تفتحها في
نفس الوقت، وذلك من خلال الاستدعاء open العادي. أما إذا كان الملف قيد
الاستخدام فإن المستدعي سيتوقف ريثما يقوم مالك الملف بإغلاقه.

2.2 الحصول على مورد:

بالنسبة لبعض أنواع الموارد، مثل مجموعة سجلات في نظام قواعد بيانات، فإن مهمة إدارة استخدام الموارد تعود لعمليات المستخدم نفسها، من الطرق
الممكنة لإتاحة إدارة الموارد من قبل المستخدم هي ربط كل مورد بمسيّر
(semaphore). يتم تهيئة جميع هذه المسيرات بالقيمة 1 مبدئياً. ويمكن
الاستعاضة عنها بالمنظمات (Mutexes). يمكن في هذه الحالة تحقيق الخطوات
الثلاث الموجودة أعلاه (في الرد السابق) بتنفيذ الاستدعاء down على
المسيّر من اجل الحصول على مورد واستخدامه، ثم تنفيذ الاستدعاء up من أجل
تحرير المورد .

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

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

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

3. شروط الاستعصاء:
عام 1971 عرض كوفمان الشروط الأربعة التي يجب ان تكون محققة ليكون هناك استعصاء:

1. شرط الإقصاء التبادلي mutual exclusion: إما أن يرتبط المورد بعملية واحدة بشكل حصري، أو يكون متاحاً.
2. شرط الاحتجاز والانتظار hold and wait : تستطيع العمليات التي تمتلك حالياً موارد تم منحها إياها مسبقاً ان تطلب موارد جديدة.
3. شرط عدم الاستيلاء non preemption : لايمكن قسرياً انتزاع الموارد الممنوحة مسبقاً من عملية ما، وإنما يجب تحرير هذه الموارد من قبل العمليات التي تملكها.
4. شرط الانتظار الدائري circular wait (يبينه الشكل في الرد
السابق): يجب أن يكون هناك سلسلة دائرية مكونة من عمليتين أو اكثر، كل واحدة منها تنتظر مورداً تحوزه العملية التي تليها في السلسلة.

%1$s
الاستعصاءات Deadlocks Ohno

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

.نمذجة الاستعصاءات:

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

أما السهم المتجه من عملية إلى مورد، فيعني ان العملية متوقفة حالياً،
وتنتظر من أجل المورد. في الشكل السابق (b) تنتظر العملية B المورد S.

نلاحظ في الشكل السابق (c) وجود استعصاء. حيث تنتظر العملية C المورد T
الذي تملكه حالياً العملية D، والعملية D لن تترك المورد T لأنها تنتظر
المورد U الذي تمتلكه العملية C. وستبقى كلتا العمليتين في حالة انتظار
للأبد. إن وجود حلقة في الغراف يعني أن هناك استعصاء متشكل من العمليات
والموارد الموجودة في الحلقة (على فرض انه يوجد مورد واحد فقط من كل نوع).
وهنا في مثالنا السابق الدائرة هي C-T-D-U-C.

بشكل عام توجد أربعة خطط عمل من أجل التعامل مع الاستعصاءات:

1. تجاهل المشكلة تماماً الاستعصاءات Deadlocks Zzz

، فربما تتجاهلك إن أنت تجاهلتها..!

2. التشخيص والحل. اترك الاستعصاءات تحدث الاستعصاءات Deadlocks New_tomato

، ثم اكتشفها ثم اتخذ الإجراءات المناسبة.

3. التحاشي الديناميكي الاستعصاءات Deadlocks Wink

من خلال تخصيص الموارد بشكل متقن.

4. المنع الاستعصاءات Deadlocks Box

. من خلال إبطال أحد الشروط الأربعة المسببة للاستعصاء.

5.استراتيجيات التعامل مع الاستعصاءات:

%1$s

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

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

الرد القادم سيتناول استراتيجيات وطرق أخرى في التعامل مع الاستعصاءات. الاستعصاءات Deadlocks Cool

معالجة الاستعصاءات:

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

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

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

التخلص من الاستعصاءات عن طريق التراجع -rolback:

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

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

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

التخلص من الاستعصاء عن طريق قتل العملية :

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

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

من الأفضل، وقدر الإمكان، قتل عملية يمكن إعادة تشغيلها من البداية دون آثار جانبية ضارة . على سبيل المثال، يمكن إعادة عملية الترجمة compilation إلى البداية لأن كل ماتفعله هو قراءة ملف المصدر source file وإنتاج ملف هدف object file. فإذا قُتلت هذه العملية في منتصف عملها، فإن التشغيل الأول ليس له أي أثر على التشغيل الثاني.

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