الفصل الثامن: حالات الجمود (Deadlocks)
دراسة شاملة لحالات الجمود في أنظمة التشغيل، تشمل التوصيف، الرسوم البيانية لتخصيص الموارد، وطرق التعامل معها مثل الوقاية، التجنب، الاكتشاف، والتعافي.
Chapter 8: Deadlocks
Comprehensive study of deadlocks in operating systems, including characterization, resource-allocation graphs, and handling methods like prevention, avoidance, detection, and recovery.
أهداف التعلم
- توضيح كيف يمكن أن يحدث الجمود عند استخدام أقفال الاستبعاد المتبادل (mutex locks).
- تحديد الشروط الأربعة الضرورية التي تصف حالة الجمود.
- تحديد حالة الجمود في مخطط تخصيص الموارد (Resource Allocation Graph).
- تقييم المناهج الأربعة المختلفة لمنع حالات الجمود.
- Illustrate how deadlock can occur when mutex locks are used.
- Define the four necessary conditions that characterize deadlock.
- Identify a deadlock situation in a resource allocation graph.
- Evaluate the four different approaches for preventing deadlocks.
1 توصيف حالة الجمود (Deadlock Characterization)
1 Deadlock Characterization
الجمود هو حالة تتوقف فيها مجموعة من العمليات لأن كل عملية تحتفظ بمورد وتنتظر مورداً آخر تحتفظ به عملية أخرى في نفس المجموعة.
A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
لكي يحدث الجمود، يجب أن تتحقق أربعة شروط في وقت واحد:
- الاستبعاد المتبادل (Mutual Exclusion): يمكن لعملية واحدة فقط استخدام المورد في وقت واحد.
- الاحتفاظ والانتظار (Hold and Wait): عملية تحتفظ بمورد واحد على الأقل وتنتظر الحصول على موارد إضافية تحتفظ بها عمليات أخرى.
- عدم المقاطعة (No Preemption): لا يمكن سحب المورد إلا طواعية من قبل العملية التي تحتفظ به بعد إكمال مهمتها.
- الانتظار الدائري (Circular Wait): توجد مجموعة من العمليات المنتظرة بحيث تنتظر كل عملية مورداً تحتفظ به العملية التالية في الدائرة.
Deadlock can arise if four conditions hold simultaneously:
- Mutual exclusion: only one process at a time can use a resource.
- Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
- No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.
- Circular wait: there exists a set {P0, P1, ..., Pn} of waiting processes such that P0 is waiting for a resource held by P1, P1 is waiting for P2, ..., and Pn is waiting for P0.
هذه الشروط الأربعة هي شروط ضرورية (Necessary) وليست كافية بمفردها في الأنظمة ذات النسخ المتعددة من الموارد، ولكن في الأنظمة ذات النسخة الواحدة لكل مورد، تصبح ضرورية وكافية.
كسر أي شرط من هذه الشروط الأربعة يضمن استحالة حدوث الجمود، وهو أساس استراتيجيات 'الوقاية من الجمود' (Deadlock Prevention).
These four conditions are necessary. If any one of them is broken, a deadlock cannot occur. This is the foundational principle behind 'Deadlock Prevention' strategies.
Note that while they are necessary, in systems with multiple instances of resources, they might not be strictly sufficient to guarantee a deadlock (a cycle doesn't always mean deadlock there), but they must all be present for a deadlock to exist.
لماذا لا يمكننا ببساطة إلغاء شرط 'الاستبعاد المتبادل' لمنع الجمود تماماً؟ Why can't we simply invalidate the 'Mutual Exclusion' condition to prevent deadlocks entirely?
بعض الموارد بطبيعتها غير قابلة للمشاركة (مثل الطابعات أو المتغيرات المشتركة التي يتم تعديلها). إلغاء الاستبعاد المتبادل سيؤدي إلى تلف البيانات أو تداخل المخرجات.
Some resources are inherently non-sharable (e.g., printers, or shared variables being written to). Invalidating mutual exclusion for these would lead to data corruption or interleaved, incorrect outputs.
2 مخطط تخصيص الموارد (Resource-Allocation Graph)
2 Resource-Allocation Graph
رسم بياني موجه يوضح حالة تخصيص الموارد والطلبات الحالية للعمليات في النظام.
A directed graph that illustrates the current resource allocation and requests of processes in the system.
يتكون المخطط من مجموعة من العقد (Vertices) مقسمة إلى نوعين: العمليات (P) والموارد (R). يحتوي المورد على نقاط تمثل عدد النسخ (Instances) المتاحة منه.
هناك نوعان من الحواف (Edges):
- حافة الطلب (Request Edge): تتجه من العملية إلى المورد (Pi -> Rj)، وتعني أن العملية تطلب المورد.
- حافة التخصيص (Assignment Edge): تتجه من المورد إلى العملية (Rj -> Pi)، وتعني أن المورد مخصص حالياً للعملية.
The graph consists of a set of vertices V partitioned into two types: Processes P = {P1, P2, ..., Pn} and Resources R = {R1, R2, ..., Rm}. Resource nodes contain dots representing the number of instances.
There are two types of directed edges:
- Request edge: directed from process Pi to resource Rj (Pi -> Rj).
- Assignment edge: directed from resource Rj to process Pi (Rj -> Pi).
تحليل المخطط:
- إذا لم يحتوي المخطط على دورات (Cycles)، فلا يوجد جمود.
- إذا احتوى على دورة:
- أ) إذا كان لكل مورد نسخة واحدة فقط، فإن الدورة تعني حتماً وجود جمود.
- ب) إذا كان للموارد نسخ متعددة، فإن الدورة تعني احتمالية وجود جمود (قد تقوم عملية خارج الدورة بتحرير مورد يكسر الدورة).
Graph analysis:
- If the graph contains no cycles, there is NO deadlock.
- If the graph contains a cycle:
- a) if there is only one instance per resource type, then a deadlock exists.
- b) if there are several instances per resource type, there is a POSSIBILITY of deadlock (it is not guaranteed, as a process outside the cycle might release a needed resource).
إذا كان لدينا مخطط تخصيص موارد يحتوي على دورة، ولكن أحد الموارد في الدورة يمتلك 3 نسخ، هل النظام بالضرورة في حالة جمود؟ If we have a resource-allocation graph with a cycle, but one of the resources in the cycle has 3 instances, is the system necessarily in a deadlock?
لا، ليس بالضرورة. وجود نسخ متعددة يعني أن الدورة هي شرط ضروري ولكن غير كافٍ للجمود. قد تقوم عملية أخرى تمتلك إحدى النسخ بتحريرها، مما يكسر الدورة.
No, not necessarily. With multiple instances, a cycle is a necessary but not sufficient condition for deadlock. Another process holding one of the instances might release it, breaking the cycle.
3 الوقاية من الجمود (Deadlock Prevention)
3 Deadlock Prevention
تصميم النظام بطريقة تضمن عدم تحقق واحد على الأقل من الشروط الأربعة الضرورية للجمود.
Designing the system to ensure that at least one of the four necessary conditions for deadlock cannot hold.
طرق إبطال الشروط:
- 1. الاستبعاد المتبادل: لا يُطلب للموارد القابلة للمشاركة (مثل الملفات للقراءة فقط)، ولكن يجب أن يظل للموارد غير القابلة للمشاركة.
- 2. الاحتفاظ والانتظار: نطلب من العملية طلب جميع مواردها وتخصيصها قبل بدء التنفيذ، أو السماح لها بطلب موارد فقط عندما لا تحتفظ بأي مورد آخر.
- 3. عدم المقاطعة: إذا طلبت عملية تحتفظ بموارد مورداً لا يمكن تخصيصه فوراً، يتم تحرير جميع الموارد التي تحتفظ بها حالياً وتضاف لقائمة الانتظار.
- 4. الانتظار الدائري: فرض ترتيب كلي (Total Ordering) لجميع أنواع الموارد، واشتراط أن تطلب كل عملية الموارد بترتيب تصاعدي.
Invalidating conditions:
- 1. Mutual Exclusion: not required for sharable resources (e.g., read-only files); must hold for non-sharable.
- 2. Hold and Wait: guarantee that whenever a process requests a resource, it does not hold any other resources (request all before execution).
- 3. No Preemption: if a process holding resources requests another that cannot be immediately allocated, all currently held resources are released and preempted.
- 4. Circular Wait: impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
الوقاية من الجمود غالباً ما تؤدي إلى انخفاض في استخدام الموارد (Resource Utilization) وانخفاض في إنتاجية النظام (Throughput).
على سبيل المثال، طلب جميع الموارد مسبقاً يربط الموارد لفترة طويلة حتى لو لم تكن مستخدمة إلا في نهاية العملية.
إبطال 'الانتظار الدائري' هو الأكثر شيوعاً وعملية (مثل إعطاء أرقام فريدة لأقفال mutex وطلبها بالترتيب).
Deadlock prevention often leads to low device utilization and reduced system throughput.
For instance, requesting all resources upfront ties up resources that might only be needed at the very end of execution.
Invalidating the 'Circular Wait' condition is the most practical and common approach in software development (e.g., assigning a unique number to each mutex lock and enforcing that threads acquire locks in strictly increasing order).
/* Preventing Circular Wait by acquiring locks in order */
void *do_work_one(void *param) {
pthread_mutex_lock(&first_mutex); // 1
pthread_mutex_lock(&second_mutex); // 5
/* Do work */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}
void *do_work_two(void *param) {
/* MUST acquire in the same order (1 then 5) to prevent deadlock */
pthread_mutex_lock(&first_mutex); // 1
pthread_mutex_lock(&second_mutex); // 5
/* Do work */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}
ما هو العيب الرئيسي لسياسة 'الاحتفاظ والانتظار' التي تتطلب من العملية طلب جميع مواردها في البداية؟ What is the main drawback of the 'Hold and Wait' prevention policy that requires a process to request all its resources at the beginning?
يؤدي إلى استغلال سيء للموارد (Low Resource Utilization) لأن العملية قد تحتفظ بمورد لفترة طويلة دون استخدامه فعلياً، مما يحرم العمليات الأخرى منه.
It leads to low resource utilization because a process might hold a resource for a long time without actually using it, depriving other processes of its use.
4 تجنب الجمود والحالة الآمنة (Deadlock Avoidance & Safe State)
4 Deadlock Avoidance & Safe State
التجنب يتطلب معلومات مسبقة عن أقصى احتياجات كل عملية، لضمان عدم دخول النظام أبداً في 'حالة غير آمنة' قد تؤدي للجمود.
Avoidance requires a priori information about the maximum needs of each process to dynamically ensure the system never enters an 'unsafe state' that could lead to deadlock.
الحالة الآمنة (Safe State): يكون النظام في حالة آمنة إذا كان هناك تسلسل
الحقائق الأساسية:
- إذا كان النظام في حالة آمنة -> لا يوجد جمود.
- إذا كان في حالة غير آمنة -> هناك احتمالية للجمود.
التجنب يضمن بقاء النظام دائماً في الحالة الآمنة.
Safe State: A system is in a safe state if there exists a sequence
Basic Facts:
- Safe state -> no deadlocks.
- Unsafe state -> possibility of deadlock.
Avoidance ensures the system never enters an unsafe state.
لتحقيق التجنب، نستخدم خوارزميات مختلفة بناءً على نوع الموارد:
- إذا كان لدينا نسخة واحدة من كل نوع مورد، نستخدم مخطط تخصيص الموارد مع إضافة 'حافة المطالبة' (Claim Edge) المتقطعة التي تشير إلى أن العملية قد تطلب المورد مستقبلاً. لا يُمنح الطلب إلا إذا كان تحويل حافة الطلب إلى حافة تخصيص لا يكوّن دورة.
- إذا كان لدينا نسخ متعددة، نستخدم خوارزمية المصرفي (Banker's Algorithm).
To achieve avoidance, different algorithms are used based on resource instances:
- For a single instance of a resource type, we use a Resource-Allocation Graph with a 'Claim edge' (dashed line indicating a process may request the resource in the future). A request is granted only if converting the request edge to an assignment edge does not result in a cycle.
- For multiple instances, we use the Banker’s Algorithm.
هل الحالة غير الآمنة تعني بالضرورة أن النظام في حالة جمود الآن؟ Does an unsafe state necessarily mean the system is currently in a deadlock?
لا، الحالة غير الآمنة تعني فقط أن النظام فقد السيطرة على ضمان عدم حدوث جمود. الجمود قد يحدث أو لا يحدث بناءً على الطلبات الفعلية للعمليات.
No, an unsafe state only means the system cannot guarantee that a deadlock will be avoided. A deadlock might or might not occur depending on the actual future requests of the processes.
5 خوارزمية المصرفي (Banker's Algorithm)
5 Banker's Algorithm
خوارزمية لتجنب الجمود في الأنظمة ذات النسخ المتعددة للموارد، تحاكي تخصيص الموارد للتحقق مما إذا كان الطلب سيترك النظام في حالة آمنة.
A deadlock avoidance algorithm for systems with multiple instances of resources, which simulates allocation to check if a request leaves the system in a safe state.
تتطلب الخوارزمية من كل عملية الإعلان مسبقاً عن الحد الأقصى لاستخدامها (Max). تستخدم هياكل البيانات التالية (حيث n=العمليات، m=الموارد):
- Available: متجه يمثل الموارد المتاحة.
- Max: مصفوفة تمثل أقصى طلب لكل عملية.
- Allocation: مصفوفة تمثل الموارد المخصصة حالياً.
- Need: مصفوفة تمثل الموارد الإضافية المطلوبة (Need = Max - Allocation).
تتكون من جزأين:
- خوارزمية الأمان (Safety Algorithm): تبحث عن تسلسل آمن.
- خوارزمية طلب الموارد (Resource-Request Algorithm): تتظاهر بتخصيص المورد وتتحقق من الأمان؛ إذا كان آمناً يتم التخصيص، وإلا تنتظر العملية.
The algorithm requires each process to a priori claim maximum use. Data structures (n=processes, m=resources):
- Available: vector of available resources.
- Max: matrix of maximum demand.
- Allocation: matrix of currently allocated resources.
- Need: matrix of remaining needs (Need = Max - Allocation).
It consists of two parts:
- Safety Algorithm: checks if a safe sequence exists using 'Work' and 'Finish' vectors.
- Resource-Request Algorithm: pretends to allocate requested resources (Available = Available - Request; Allocation = Allocation + Request; Need = Need - Request) and runs the Safety Algorithm. If safe, allocate; if not, process waits.
خوارزمية الأمان تعمل بتعقيد زمني O(m * n^2). تبدأ بتعيين Work = Available و Finish[i] = false.
تبحث عن عملية i حيث Finish[i] == false و Need_i <= Work. إذا وجدتها، تضيف Allocation_i إلى Work وتجعل Finish[i] = true، وتكرر.
إذا أصبحت كل Finish[i] == true، فالنظام آمن.
هذه الخوارزمية متحفظة جداً وقد ترفض طلبات آمنة فعلياً لأنها تفترض أن العمليات ستطلب الحد الأقصى (Max) دفعة واحدة.
The Safety Algorithm runs in O(m * n^2) time. It initializes Work = Available and Finish[i] = false.
It finds an index i where Finish[i] == false and Need_i <= Work. If found, it simulates completion: Work = Work + Allocation_i, Finish[i] = true, and repeats.
If all Finish[i] == true, the state is safe.
The algorithm is highly conservative; it assumes processes might request their maximum declared needs all at once, potentially delaying requests unnecessarily.
في خوارزمية طلب الموارد، لماذا نقوم بـ 'التظاهر' (Pretend) بتخصيص الموارد بدلاً من تخصيصها مباشرة؟ In the Resource-Request algorithm, why do we 'pretend' to allocate resources instead of allocating them directly?
لأننا نحتاج إلى اختبار ما إذا كان هذا التخصيص سيؤدي إلى حالة غير آمنة. إذا أدى لحالة غير آمنة، يمكننا التراجع عن 'التظاهر' وإجبار العملية على الانتظار دون إحداث ضرر فعلي للنظام.
Because we need to test if the allocation leads to an unsafe state. If it does, we can easily revert the 'pretend' state and force the process to wait, without having actually committed the resources and risked a deadlock.
6 اكتشاف الجمود (Deadlock Detection)
6 Deadlock Detection
السماح للنظام بالدخول في حالة جمود، ثم تشغيل خوارزمية لاكتشافه، وتطبيق آلية للتعافي منه.
Allowing the system to enter a deadlock state, running an algorithm to detect it, and then applying a recovery scheme.
تعتمد طريقة الاكتشاف على عدد نسخ الموارد:
- نسخة واحدة لكل مورد: يتم الحفاظ على مخطط الانتظار (Wait-for graph)، وهو نسخة مبسطة من مخطط تخصيص الموارد يحتوي على العمليات فقط (Pi -> Pj يعني Pi تنتظر Pj). يتم استدعاء خوارزمية للبحث عن دورة (Cycle) بشكل دوري (تتطلب عمليات O(n^2)).
- نسخ متعددة: تستخدم خوارزمية مشابهة لخوارزمية المصرفي، تعتمد على مصفوفات Available و Allocation و Request (الطلب الحالي وليس الأقصى). إذا كانت Finish[i] == false لبعض العمليات، فهذه العمليات في حالة جمود.
Detection methods depend on resource instances:
- Single instance: Maintain a Wait-for graph (nodes are processes, Pi -> Pj means Pi is waiting for Pj). Periodically invoke an algorithm to search for a cycle (requires O(n^2) operations).
- Multiple instances: Uses an algorithm similar to Banker's, utilizing Available, Allocation, and Request (current request, not max) matrices. If Finish[i] == false for some i, the system is in a deadlock state, and Pi is deadlocked.
متى يتم استدعاء خوارزمية الاكتشاف؟ يعتمد ذلك على مدى تكرار حدوث الجمود وعدد العمليات التي ستتأثر.
إذا تم استدعاؤها بشكل عشوائي أو متباعد جداً، قد تتراكم دورات عديدة في المخطط، مما يجعل من المستحيل تحديد العملية التي 'تسببت' في الجمود الأصلي.
الاكتشاف المستمر يستهلك موارد المعالج (CPU overhead).
When and how often to invoke the detection algorithm depends on how often a deadlock is likely to occur and how many processes will need to be rolled back.
If invoked arbitrarily or too infrequently, there may be many cycles in the resource graph, making it impossible to tell which of the deadlocked processes 'caused' the deadlock.
Frequent detection causes significant CPU overhead.
| Single Instance (نسخة واحدة) | Multiple Instances (نسخ متعددة) | |
|---|---|---|
| معنى الدورة في المخطط (Cycle Meaning) Cycle Meaning in Graph | جمود مؤكد Definite Deadlock | احتمالية جمود فقط Possibility of Deadlock only |
| خوارزمية التجنب (Avoidance Algorithm) Avoidance Algorithm | مخطط تخصيص الموارد (مع حواف المطالبة) Resource-Allocation Graph (with claim edges) | خوارزمية المصرفي Banker's Algorithm |
| خوارزمية الاكتشاف (Detection Algorithm) Detection Algorithm | مخطط الانتظار (Wait-for Graph) Wait-for Graph | خوارزمية اكتشاف مشابهة للمصرفي Detection algorithm similar to Banker's |
لماذا تستخدم خوارزمية الاكتشاف مصفوفة 'Request' الحالية بدلاً من مصفوفة 'Max' المستخدمة في خوارزمية المصرفي؟ Why does the detection algorithm use the current 'Request' matrix instead of the 'Max' matrix used in Banker's algorithm?
لأن الاكتشاف يتعامل مع الحالة الحالية الفعلية للنظام لمعرفة ما إذا كان هناك جمود *الآن*، بينما خوارزمية المصرفي تحاول التنبؤ بأسوأ سيناريو مستقبلي (Max) لتجنب الجمود.
Because detection deals with the actual current state of the system to see if a deadlock exists *right now*, whereas Banker's algorithm tries to predict the worst-case future scenario (Max) to avoid deadlocks.
7 التعافي من الجمود (Recovery from Deadlock)
7 Recovery from Deadlock
بمجرد اكتشاف الجمود، يجب كسر الدورة إما بإنهاء العمليات أو سحب الموارد منها.
Once a deadlock is detected, the cycle must be broken either by terminating processes or preempting resources.
هناك طريقتان رئيسيتان للتعافي:
- 1. إنهاء العمليات (Process Termination): إما إحباط (Abort) جميع العمليات المتورطة في الجمود (مكلف جداً)، أو إحباط عملية واحدة في كل مرة حتى يتم القضاء على دورة الجمود. يتم اختيار العملية بناءً على الأولوية، وقت التنفيذ، الموارد المستخدمة، ونوع العملية (تفاعلية أم دفعية).
- 2. سحب الموارد (Resource Preemption): اختيار 'ضحية' (Victim) لتقليل التكلفة، ثم التراجع (Rollback) بالعملية إلى حالة آمنة سابقة وإعادة تشغيلها. يجب الحذر من المجاعة (Starvation) حيث قد يتم اختيار نفس العملية كضحية دائماً.
There are two main approaches to recovery:
- 1. Process Termination: Abort all deadlocked processes (very costly), or abort one process at a time until the deadlock cycle is eliminated. The choice of which to abort depends on priority, computed time, resources used, and if it's interactive/batch.
- 2. Resource Preemption: Select a victim to minimize cost, rollback the process to some safe state, and restart it. Must handle Starvation, ensuring the same process isn't always picked as the victim (e.g., by including the number of rollbacks in the cost factor).
التراجع (Rollback) معقد جداً في أنظمة التشغيل الحقيقية لأنه يتطلب حفظ حالة النظام (Check-pointing) بشكل دوري.
لتجنب المجاعة عند سحب الموارد، يجب أن يتضمن عامل التكلفة (Cost factor) عدد المرات التي تم فيها التراجع عن العملية، بحيث تزداد تكلفة اختيارها كضحية في كل مرة.
Rollback is highly complex in real OS implementations because it requires periodic state saving (check-pointing).
To prevent starvation during resource preemption, the cost factor for selecting a victim must include the number of times a process has been rolled back, ensuring its cost increases and it eventually completes.
| Prevention (الوقاية) | Avoidance (التجنب) | Detection & Recovery (الاكتشاف والتعافي) | |
|---|---|---|---|
| النهج الأساسي Basic Approach | إبطال أحد الشروط الأربعة Invalidate one of the 4 conditions | تجنب الحالات غير الآمنة ديناميكياً Dynamically avoid unsafe states | السماح بالجمود ثم حله Allow deadlock, then resolve it |
| استغلال الموارد (Resource Utilization) Resource Utilization | منخفض (متحفظ جداً) Low (very conservative) | متوسط Medium | عالي (حتى يحدث الجمود) High (until deadlock occurs) |
كيف يمكننا منع المجاعة (Starvation) عند استخدام سياسة سحب الموارد للتعافي من الجمود؟ How can we prevent starvation when using resource preemption to recover from deadlocks?
من خلال تضمين عدد مرات التراجع (Rollbacks) في دالة التكلفة عند اختيار الضحية. العملية التي تم التراجع عنها عدة مرات تصبح تكلفتها عالية ولن يتم اختيارها كضحية مرة أخرى.
By including the number of rollbacks in the cost function when selecting a victim. A process that has been rolled back multiple times will have a higher cost and won't be picked as a victim again.