في هذا الدرس 6تصفّح المواضيع
تشريح الجمود التام وشروط كوفمان الأربعة
تعلّمت في درس أقفال التزامن Mutex وآلية Semaphore كيف تمنع الأقفال الحصرية حالات التسابق. لكن استحواذ خيطين على أكثر من قفل بترتيب متعاكس يوقع النظام في الجمود التام Deadlock: إذ يمسك الخيط Thread A القفل Lock 1 وينتظر Lock 2، بينما يمسك الخيط Thread B القفل Lock 2 وينتظر Lock 1، فيتجمد الاثنان إلى الأبد.
وقد حدّد العالم إدوارد كوفمان عام 1971 أربعة شروط لازمة تُعرف بـ شروط كوفمان الأربعة Coffman Conditions، ولا ينشأ جمود الموارد إلا إذا اجتمعت كلها في اللحظة نفسها:
- الإقصاء المتبادل
Mutual Exclusion: المورد غير قابل للمشاركة، فلا يمتلك القفل سوى خيط واحد في كل مرة. - الحيازة والانتظار
Hold and Wait: يحتفظ الخيط بمورد واحد على الأقل أثناء انتظاره للحصول على مورد إضافي بيد خيط آخر. - عدم الاستباق
No Preemption: لا يستطيع نظام التشغيل انتزاع القفل قسراً من مالكه، بل يتحرر طوعاً عند انتهاء المالك. - الانتظار الدائري
Circular Wait: تشكّل مجموعة من العمليات حلقة مغلقة ينتظر فيها كل طرف مورداً يحتجزه الطرف التالي حتى نعود للأول.
تفصيل تقني متقدم: في الموارد وحيدة النسخة مثل أقفال Mutex المستقلة، تكون شروط كوفمان الأربعة لازمة وكافية لحدوث الجمود التام حتماً؛ أما في الموارد متعددة النسخ المتماثلة كالسيمافور العداد فتصبح الشروط لازمة لاحتمال الجمود لكنها لا تكفي وحدها إلا عند استنفاد جميع النسخ داخل الحلقة.
دورة الجمود وشروط كوفمان الأربعة
مخطط يوضح تقاطع Thread A و Thread B على القفلين Lock 1 و Lock 2 مع اجتماع شروط كوفمان الأربعة.
الفرق بين الجمود والتعثر الحي والمجاعة
لا يعني توقف البرنامج عن الإنجاز وجود جمود تام في كل الحالات؛ فهناك ثلاث حالات تعثر متميزة يجب التفريق بينها بدقة:
- الجمود التام
Deadlock: تدخل الخيوط المتعارضة في حالة انتظار نائمة داخل النواة ولا تستهلك دورات المعالج، لكنها تبقى عالقة للأبد. - التعثر الحي
Livelock: على عكس الجمود، تبقى الخيوط نشطة وتغيّر حالتها باستمرار استجابةً لبعضها البعض دون أي تقدم حقيقي؛ تماماً كشخصين مهذبين في ممر ضيق يتنحيان يميناً ثم يساراً في اللحظة نفسها بلا توقف. - المجاعة
Starvation: كما تعلّمنا في درس أهداف الجدولة وعدالة الأولويات، يبقى الخيط في حالة جاهزيةReadyلكنه يُهمل باستمرار لصالح مهام أعلى أولوية بينما يستمر بقية النظام في العمل والإنجاز.
تفصيل تقني متقدم: ينشأ التعثر الحي غالباً من آليات تعافٍ متسرعة تفرغ القفل وتعيد المحاولة بالفاصل الزمني الثابت نفسه لدى الطرفين، فتتصادم الخيوط دورياً وتستهلك المعالج بالكامل دون إتمام أي معاملة ناجحة.
جدول المقارنة بين الجمود والتعثر والمجاعة
| الحالة | حالة الخيط | استهلاك المعالج | تقدم النظام | الحل الأساسي |
|---|---|---|---|---|
| الجمود التام | نائم محجوب | قريب من 0% | توقف كامل داخل الحلقة | ترتيب الأقفال أو المهل والتعافي |
| التعثر الحي | نشط يعيد المحاولة | مرتفع ومهدر | حركة مستمرة بلا إنجاز | تراجع عشوائي أو كسر التماثل |
| المجاعة | جاهز ينتظر دوره | طبيعي لبقية المهام | ينجز غيره ويبقى محروماً | تقنية الشيخوخة وطوابير عادلة |
تراجع متباعد
لمنع التعثر الحي عند فشل التقاط قفل ثانٍ، أضف تأخيراً عشوائياً متصاعداً Randomized Jitter أو أولوية حاسمة لأحد الطرفين لكسر التطابق الزمني بين المحاولات.
تمثيل الجمود بمخطط تخصيص الموارد وكشف الدورات
بدلاً من التخمين، تمثّل أنظمة التشغيل علاقة العمليات بالموارد عبر رسم موجّه يُسمّى مخطط تخصيص الموارد Resource Allocation Graph ويُختصر بـ RAG:
- العقد
Vertices: تمثّل الدوائر العمليات أو الخيوط مثلP1وP2، وتمثّل المستطيلات أنواع الموارد مثلR1وR2مع عدد النسخ المتاحة بداخلها. - سهم الطلب
Request Edge: يتجه من العملية إلى الموردP -> Rليدل على أن العملية طلبت المورد وتنتظره. - سهم التخصيص
Assignment Edge: يتجه من المورد إلى العمليةR -> Pليدل على أن المورد محجوز حالياً لتلك العملية.
وعند فحص الرسم البياني نطبّق القاعدتين التاليتين:
- غياب أي دورة مغلقة: يستحيل وجود جمود تام في النظام.
- وجود دورة مع نسخة واحدة لكل مورد: الجمود التام مؤكد حتماً لأن كل طرف ينتظر النسخة الوحيدة المحتجزة في الحلقة. أما مع تعدد النسخ فالدورة تعني احتمالاً فقط قد ينحل بتحرير نسخة أخرى من خارج الحلقة.
تفصيل تقني متقدم: في أقفال النسخة الواحدة تختزل الأنظمة عقد الموارد لبناء مخطط الانتظار Wait-For Graph حيث يعني السهم المباشر P1 -> P2 انتظار العملية الأولى لمورد تملكه الثانية، وتستخدم بيئة ويندوز واجهة تتبع سلاسل الانتظار WCT لكشف هذه الحلقات عبر كائنات التزامن المختلفة.
مخطط تخصيص الموارد ومخطط الانتظار
تحويل مخطط تخصيص الموارد ذي النسخة الواحدة يساراً إلى مخطط الانتظار المختزل يميناً لكشف الدورة بين P1 و P2.
مورد وحيد
وجود دورة مغلقة يثبت الجمود التام بيقين كامل فقط إذا كانت كل عقدة مورد داخل الدورة تملك نسخة واحدة لا غير.
منع الجمود بالترتيب القياسي والمهل وتذاكر الانتظار
يقوم منع الجمود Deadlock Prevention على تصميم النظام بحيث يستحيل تحقق أحد شروط كوفمان الأربعة مسبقاً، وأهم تقنياته العملية بدون الحاجة لكتابة كود معقد هي:
- الترتيب القياسي للأقفال
Canonical Lock Ordering: نفرض ترتيباً تصاعدياً موحداً مثل أخذLock 1دائماً قبلLock 2في جميع الخيوط. عندئذٍ إذا سبقThread AإلىLock 1ينتظرThread Bعند البوابة الأولى، فيكملThread Aعمله ويأخذLock 2ثم يحررهما معاً فتختفي الحلقة الدائرية بالكامل. - المحاولة غير الحاجزة والمهل الزمنية: عند تعذر أخذ القفل الثاني خلال مهلة محددة مثل
flock -nأوflock -w، يتخلى الخيط عن القفل الأول فوراً وينتظر زمناً عشوائياً متباعداً قبل إعادة المحاولة. - خوارزميتا
Wait-DieوWound-Wait: تعتمدان في قواعد البيانات ونواة لينكس عبر أقفالww_mutexعلى تذكرة زمنية تصاعدية لكل معاملة: فيWait-Dieينتظر الأقدم للأحدث بينما يتراجع الأحدث ويموت أمام الأقدم، وفيWound-Waitيجرح الأقدمُ الأحدثَ برمز-EDEADLKليتنازل الأحدث ويعيد المحاولة محتفظاً بتذكرته القديمة حتى لا يتعرض للمجاعة.
تفصيل تقني متقدم: تضم نواة لينكس مدقق صحة الترتيب الحي lockdep الذي يسجّل مسارات الاستحواذ بين أصناف الأقفال، فإذا رصد مساراً يأخذ L1 -> L2 وآخر يأخذ L2 -> L1 يطلق تنبيهاً فورياً أثناء الاختبار قبل وقوع الجمود الفعلي.
أثر تنفيذ الترتيب القياسي للأقفال
تتبع بصري يوضح كيف ينتظر Thread B عند Lock 1 حتى يحرر Thread A القفلين معاً فيختفي الجمود تماماً.
ترتيب الأقفال
يُعد الترتيب القياسي للأقفال أنجح حل عملي في الأنظمة الواقعية لأنه يكسر الانتظار الدائري بنيوياً دون أي عبء إضافي أثناء التشغيل.
خوارزمية المصرفي ومنهج النعامة والكشف والتعافي
إلى جانب المنع البنيوي، تتبع أنظمة التشغيل وقواعد البيانات ثلاث استراتيجيات أخرى للتعامل مع الجمود:
- تجنب الجمود وخوارزمية المصرفي
Banker's Algorithm: ابتكرها ديكسترا لتفحص كل طلب تخصيص عبر مصفوفاتAvailableوMaxوAllocationوNeed = Max - Allocation. وكما لا يقرض المصرفي رصيداً يعجزه عن الوفاء بالتزامات بقية العملاء، لا يوافق النظام على الطلب إلا إذا بقي في حالة آمنةSafe Stateتضمن وجود تسلسل إنهاء متتابع للجميع، بينما تعني الحالة غير الآمنة احتمال الجمود لا حتميته. - منهج التجاهل
Ostrich Algorithm: لأن خوارزمية المصرفي تتطلب معرفة الحد الأقصى للموارد مسبقاً وتفرض كلفة فحص مستمرة، تتجاهل أنظمة لينكس وويندوز الجمود النادر في تطبيقات المستخدم العادية لترجيح الأداء اليومي. - الكشف والتعافي
Detection and Recovery: تراقب قواعد البيانات ومحركات المعاملات دورات الانتظار أو مهل الأقفال، ثم تكسر الحلقة عبر إنهاء الضحيةVictim Terminationبإلغاء أرخص مهمة، أو عبر الاستباق والاسترجاعRollbackإلى نقطة حفظ سليمة.
تفصيل تقني متقدم: عند اختيار الضحية للتعافي توازن الأنظمة بين أولوية المهمة وحجم العمل المنجز وعدد الأقفال المحتجزة، مع الحفاظ على سجل العمر لمنع تكرار قتل المهمة نفسها وتحولها إلى مجاعة متجددة.
مقارنة استراتيجيات التعامل مع الجمود
| الاستراتيجية | الآلية الأساسية | كلفة التشغيل | الاستخدام الواقعي |
|---|---|---|---|
| المنع | كسر أحد شروط كوفمان بترتيب الأقفال | منخفضة جداً | نوى الأنظمة وبرامج التشغيل والخوادم |
| التجنب بالمصرفي | محاكاة الحالة الآمنة قبل كل تخصيص | مرتفعة وتتطلب Max مسبقاً | نماذج مرجعية وأنظمة محدودة ثابتة |
| الكشف والتعافي | فحص دورات الانتظار ثم إنهاء الضحية أو الاسترجاع | متوسطة دورياً | قواعد البيانات وأدوات مراقبة الأقفال |
| التجاهل النعامي | تقبّل الحالات النادرة مقابل أقصى سرعة | صفرية | تطبيقات المستخدم في لينكس وويندوز |
إنهاء الضحية
الإنهاء القسري لعملية متوقفة دون آلية استرجاع معاملات قد يترك الملفات المشتركة أو قواعد البيانات في حالة ناقصة، لذا يُفضَّل دائماً الاعتماد على المهل الزمنية والاسترجاع المنظم.
فحص الاختناقات وقنوات الانتظار للقراءة فقط
عند تجمد خدمة على النظام لا يلجأ المهندس لإغلاق العمليات عشوائياً أو كتابة كود C منخفض المستوى، بل يبدأ بأدوات فحص القراءة فقط الآمنة في لينكس وويندوز:
- أمر
ps -eo pid,stat,wchan:20,commفي لينكس: يعرض رمز حالة العملية فيSTATواسم دالة النواة التي تنتظر عندها فيWCHAN. فحالةSمعfutex_wait_queueتشير إلى نوم على قفل مستخدم، بينما تشير الحالةDإلى نوم غير قابل للمقاطعة في النواة أو الإدخال والإخراج. - ملفا
/proc/<pid>/wchanو/proc/locks: يكشف الأول الدالة الرمزية الدقيقة لموضع نوم العملية داخل النواة وفق صلاحيات القراءة، ويعرض الثاني جدول أقفال الملفات النشطة كما تعلّمت في الدرس السابق. - اختبار الاسترداد بالمهلة
flock -w: تتيح تجربةflock -w 1في الطرفية محاكاة فشل القفل بأمان وخروج المهمة عند انتهاء المهلة بدلاً من التعلق الدائم. - تتبع سلاسل الانتظار
WCTفي ويندوز: تعرض أداة مراقب الموارد عبر خيار تحليل سلسلة الانتظار أي خيط ينتظر قفلاً يملكه خيط آخر بصورة فورية وآمنة.
Inspect Process Wait Channels Safelyفحص حالة D وقناة انتظار النواة بأمان
استعراض حالة العمليات وقنوات انتظار النواة وسجل أقفال الملفات للقراءة فقط بأمان.
ps -eo pid,stat,wchan:20,comm | head -n 5
cat /proc/1910/wchan; head -n 2 /proc/locks
Linux Wait Channel Terminal Outputمعاينة مخرجات قناة الانتظار في الطرفية
معاينة الطرفية لقنوات انتظار النواة وحالتي S و D وقراءة ملفات proc للقراءة فقط.
Recover From Contention Using Timeoutاسترداد آمن عبر مهلة انتظار flock -w
اختبار استرداد آمن عبر مهلة ثانية واحدة بأمر flock -w كي لا تتعلق المهمة الثانية إلى الأبد.
flock -x /tmp/ct-order.lock sleep 4 &
flock -w 1 -E 1 /tmp/ct-order.lock echo OK || echo Timed out
Lock Timeout Recovery Terminal Outputمعاينة الاسترداد بالمهلة الزمنية في الطرفية
معاينة الطرفية لخروج المهمة الثانية بأمان بعد انتهاء مهلة الانتظار دون تعليق دائم.
ملخص الدرس
حصاد الدرسمراجعة مركّزة لأهم المفاهيم والقواعد الهندسية التي أتقنتها في هذا الدرس قبل التطبيق العملي
ماذا تعلّمت في هذا الدرس؟
أتممت في هذا الدرس وحدة تزامن العمليات بفهم آلية الجمود التام و شروط كوفمان الأربعة، وميّزت بدقة بين الجمود النائم و التعثر الحي النشط و المجاعة المرتبطة بالجدولة، وتعرّفت على كشف الدورات في مخطط تخصيص الموارد واختزال مخطط الانتظار، وطرق المنع بالترتيب القياسي للأقفال والمهل وخوارزميتي Wait-Die و Wound-Wait، وحدس الحالة الآمنة في خوارزمية المصرفي ومنهج النعامة والتعافي، إضافةً إلى فحص الاختناقات للقراءة فقط بأوامر ps و /proc/<pid>/wchan و /proc/locks وتتبع الانتظار في ويندوز.
الخطوة التالية والدرس القادم
يفتح إتقان التزامن وإدارة الموارد الباب لفهم حدود الأمان وحماية النظام من الاستنزاف؛ انتقل الآن إلى الدرس 42 نمذجة التهديدات ومبدأ الامتياز الأقل برمز threat-modeling-and-least-privilege لبدء وحدة أمن النظام.
سجّل الدخول لحفظ تقدمك
تابع إنجاز المواضيع والمصطلحات والمهام، وكمّل من آخر خطوة على أي جهاز.
المصطلحات4
راجع المعنى، اشرحه لنفسك، ثم علّم البطاقة كمفهومة.
- 01 Deadlock الجمود التام
- توقف دائم تنام فيه مجموعة من الخيوط أو العمليات إلى الأبد لأن كل طرف يحتجز مورداً ينتظره طرف آخر داخل حلقة مغلقة.
- للمراجعة
- 02 Livelock التعثر الحي
- حالة تعثر تبقى فيها الخيوط نشطة وتبدل حالتها أو تعيد المحاولة استجابةً لبعضها البعض دون تحقيق أي تقدم فعلي.
- للمراجعة
- 03 Canonical Lock Ordering الترتيب القياسي للأقفال
- منهجية لمنع الجمود تُلزم جميع الخيوط بالاستحواذ على الأقفال المتعددة وفق ترتيب تصاعدي موحد يكسر شرط الانتظار الدائري.
- للمراجعة
- 04 Safe State الحالة الآمنة
- حالة تخصيص في خوارزمية المصرفي تضمن وجود تسلسل واحد على الأقل يتيح لكل عملية استكمال مواردها والانتهاء دون جمود.
- للمراجعة
لا توجد بطاقات تطابق البحث والتصفية.
اقرأ البطاقات بحرية. سجّل الدخول لحفظ تقدم مراجعتك.
الاختصارات4
راجع المعنى، اشرحه لنفسك، ثم علّم البطاقة كمفهومة.
- 01 RAG RAG
- Resource Allocation Graph
- مخطط تخصيص الموارد الذي يمثّل العمليات والموارد وأسهم الطلب والتخصيص
- للمراجعة
- 02 WFG WFG
- Wait-For Graph
- مخطط الانتظار المختزل لكشف دورات انتظار العمليات مباشرة
- للمراجعة
- 03 WCHAN WCHAN
- Wait Channel
- قناة الانتظار الرمزية داخل نواة لينكس التي تنام عندها العملية المنتظرة
- للمراجعة
- 04 WCT WCT
- Wait Chain Traversal
- واجهة تتبع سلاسل الانتظار في ويندوز لتشخيص تعليق الخيوط والأقفال
- للمراجعة
لا توجد بطاقات تطابق البحث والتصفية.
اقرأ البطاقات بحرية. سجّل الدخول لحفظ تقدم مراجعتك.
مهامك قبل الاختبار
خطوة صغيرة كل مرة. وإنجاز تقدر ترجع له.
-
نفّذ أمر ps -eo pid,stat,wchan:20,comm للقراءة فقط وافحص /proc/<pid>/wchan للتمييز بين حالة S وحالة D غير القابلة للمقاطعة.
-
احجز قفلاً مؤقتاً على /tmp/ct-order.lock لمدة 4 ثوانٍ ثم اختبر خروج المهمة الثانية بأمان بعد مهلة ثانية واحدة عبر flock -w 1.
-
ارسم مسار خيطين يحتاجان القفلين Lock 1 و Lock 2 وتحقق من اختفاء الدورة المغلقة في مخطط الموارد عند فرض ترتيب Lock 1 ثم Lock 2.
تأشير المهمة إقرار منك بإتمامها، وليس تصحيحًا آليًا للكود. يُحفظ تقدمك في حسابك.
اختبر فهمك.
ووصلها للإتقان.
كل سؤال خطوة لقدّام. اختار، اكتب كود، وشوف نتيجتك فورًا.
أكمل المهام، واجمع كل الإجابات الصحيحة. أقل من 100%؟ راجع وأعد المحاولة.
الأسئلة متاحة للاطلاع. سجّل الدخول للتفاعل وحفظ تقدمك.
لمحة عن التحدي9 أسئلة تنتظرك +
ما المجموعة التي تضم شروط كوفمان الأربعة اللازمة معاً لحدوث الجمود التام؟
ما المجموعة التي تضم شروط كوفمان الأربعة اللازمة معاً لحدوث الجمود التام؟
كيف يختلف التعثر الحي Livelock عن كل من الجمود التام والمجاعة؟
كيف يختلف التعثر الحي Livelock عن كل من الجمود التام والمجاعة؟
أي عبارة تصف بدقة دلالة وجود دورة مغلقة في مخطط تخصيص الموارد RAG؟
أي عبارة تصف بدقة دلالة وجود دورة مغلقة في مخطط تخصيص الموارد RAG؟
كيف يمنع الترتيب القياسي للأقفال حدوث الجمود عندما يحتاج أكثر من خيط إلى Lock 1 و Lock 2؟
كيف يمنع الترتيب القياسي للأقفال حدوث الجمود عندما يحتاج أكثر من خيط إلى Lock 1 و Lock 2؟
في تصميم أقفال ww_mutex في لينكس، ما الفرق بين Wait-Die و Wound-Wait عند تعارض التذاكر؟
في تصميم أقفال ww_mutex في لينكس، ما الفرق بين Wait-Die و Wound-Wait عند تعارض التذاكر؟
أي العبارات التالية صحيحة عن خوارزمية المصرفي وخوارزمية النعامة؟
أي العبارات التالية صحيحة عن خوارزمية المصرفي وخوارزمية النعامة؟
لماذا قد تؤدي حلقات إعادة المحاولة بعد تعارض الأقفال إلى تعثر حي Livelock ما لم يُضف تأخير عشوائي؟
لماذا قد تؤدي حلقات إعادة المحاولة بعد تعارض الأقفال إلى تعثر حي Livelock ما لم يُضف تأخير عشوائي؟
ماذا تكشف الحالة D مع عمود WCHAN في الأمر ps -eo pid,stat,wchan:20,comm؟
ماذا تكشف الحالة D مع عمود WCHAN في الأمر ps -eo pid,stat,wchan:20,comm؟
أي الآليات التالية تفحص المهام المتوقفة للقراءة فقط بأمان دون تعديل حالة العمليات؟
أي الآليات التالية تفحص المهام المتوقفة للقراءة فقط بأمان دون تعديل حالة العمليات؟