استعصاء
عودة للموسوعةالاستعصاء أوالمأزق (بالإنجليزية: deadlock) هوحالة تطرأ في مجال الحوسبة المتوازية. تقع حالة الاستعصاء عندما تصل مهمتان متنافستان إلى حالة انتظار جميع منهما للأخرى من أجل تحرير مورد تطلبه. المهام التي تصل لهذه الحالة تخلق حالة استعصاء.
والاستعصاء الحوسبي كالاستعصاء في تقاطع الطرق يحدث حينما تحاول السيارات اجتياز التقاطع في نفس الوقت فيوقف بعضهم البعض.
مثال
مثال في الحوسبة عن حالة استعصاء نجم عن تنافس مهمتين في طلب قفلين بترتيب مختلف. فإذا كان لدينا اقصاء متبادل (M1 وM2) والمهمتين تاليتين :
مهمة أ : الحصول على M1 الحصول على M2 عمل في حاجة لقفلين تحرير M2 تحرير M1 |
مهمة ب: الحصول على M2 الحصول على M1 عمل في حاجة لقفلين تحرير M1 تحرير M2 |
الاستعصاء هنا ممكن، حيث إذا كانت عملية التطبيق تسير كما يلي :
- المهمة أ يحصل على M1.
- المهمة ب يحصل على M2.
- المهمة أ تنتظر للحصول على M2 (المملوك لـ المهمة ب).
- المهمة ب تنتظر للحصول على M1 (المملوك لـ المهمة أ).
في هذه الحالة، المهمتين أ وب في حالة استعصاء.
تفادي الاستعصاء
يمكن تدارك حالة الاستعصاء إذا عهدت بعض المعطيات مسبقا. لكل طلب احتكار لمورد، يقوم النظام بمراقبة إذا ما كان ممكنا الوقوع في حالة مريبة يمكن حتى تتحول إلى مأزق. فلا يقبل النظام إلا الطلبات التي لا تشكل خطرا. وحتى يتمكن من أخذ القرار عن إذا ما كان الطلب سيؤدي لحالة مريبة أولا، يجب حتى يعهد النظام في جميع وقت عدد ونوع الموارد الموجودة المتوفرة أوالمحجوزة. خوارزمية المصرفي هي احدى الخوارزميات الكلاسيكية للتسقط المبكر لحالة الاستعصاء. الخوارزمية بحاجة لفهم مسبقة لحدود استعمال الموارد. بالنسبة للعديد من الأنظمة يستحيل تسقط الاستعصاء قبل جميع طلب ما يجعل تفادي الاستعصاء أمرا شبه محال.
خوارزميات انتظار/موت وجريح/انتظار (بالإنجليزية: Wait/Die - Wound/Wait) هي طرق أخرى للتفادي التي تستعمل تقنية كسر التناظر. تأخذ الخورزميتان بعين الاعتبار عمر جميع مهمة وتفصل بين مهمة مسنة (م) ومهمة فتية (ف).
يمكن تحديد عمر المهمة باستعمال الختم الزمني (بالإنجليزية: timestamp) عند استحداث المهمة. التواريخ الصغيرة هي للمهام المسنة والتواريخ الكبيرة هي للفتية.
انتظار/موت | جرح/انتظار | |
---|---|---|
م بحاجة لمورد يحتكره ف | م ينتظر | ف يموت |
ف بحاجة لمورد يحتكره م | ف يموت | ف ينتظر |
من المهم الأخذ بعين الاعتبار أنه يمكن حتى تكون مهمة في حالة مريبة دون حتى يؤدي ذلك بالضرورة لحالة استعصاء. مفهوم الحالة المريبة أولا هومرجع لاحتمال وقوع النظام في حالة استعصاء أولا. مثلا إذا طلبت مهمة احتكار مورد أ وينجم عن ذلك حالة مريبة ولكن يحرر مرد آخر ب لتفادي الانتظار المتبادل، فإن الحالة المريبة لا تؤدي إلى حالة استعصاء.
الوقاية
إحدى الطرق تنص على اكتساب الإقصاء المتبادل بنفس الترتيب. في الواقع، إذا احتاجت عدة خيوط لاكتساب عدة قيود لتطبيق أعمالها وتم ذلك بترتيب مختلف فممكن وقوعها في مأزق (راجع المثال السابق).
من المفيد أيضا الاهتمام بأولوية المهام. فمثلا، إذا طلبت مهمة بأولوية عليا قفلا مشهجرا مع مهمة ذات أولوية دنيا، هنا يمكن الوقوع أيضا في حالة استعصاء. الحل لمثل هذه الحالة هواقتصار استعمال القيود فقط على المهام بنفس مستوى الأولية.
مراجع
- ^ "معلومات عن استعصاء على مسقط britannica.com". britannica.com. مؤرشف من الأصل في 22 أبريل 2016.
- Paper "Confirmation of Deadlock Potentials Detected by Runtime Analysis" by Saddek Bensalem, Jean-Claude Fernandez, Klaus Havelund and Laurent Mounier
التصنيفات: أخطاء البرمجة, إدارة الذاكرة, إدسخر ديكسترا, تزامن (حوسبة), حوسبة متوازية, شذوذ البرمجيات, مقالات تحتوي نصا بالإنجليزية, بوابة تقنية المعلومات/مقالات متعلقة, بوابة علم الحاسوب/مقالات متعلقة, جميع المقالات التي تستخدم شريط بوابات