Crisis Management: Deadlocks إدارة الأزمات: Deadlocks

When processes wait forever. Prevention, Avoidance (Banker's Algorithm), Detection, and Recovery. عندما تنتظر العمليات إلى الأبد. المنع (Prevention)، التجنب (Banker's Algorithm)، الاكتشاف (Detection)، والاسترداد (Recovery).

Four Conditions الشروط الأربعة Resource Allocation Graph (RAG) Resource Allocation Graph (RAG) Prevention المنع (Prevention) Banker's Algorithm Banker's Algorithm Safe State Safe State

What creates a Deadlock? ما الذي يسبب الـ Deadlock؟

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. مجموعة من العمليات المحظورة (blocked)، كل واحدة منها تحتفظ بمورد وتنتظر الحصول على مورد آخر محتجز من قبل عملية أخرى في نفس المجموعة.
Crucial Rule: قاعدة جوهرية: Deadlock can arise IF AND ONLY IF four conditions hold simultaneously. يحدث الـ Deadlock إذا وفقط إذا تحققت أربعة شروط في وقت واحد.

1. Mutual Exclusion 1. Mutual Exclusion (الاستبعاد المتبادل) At least one resource is non-sharable (only one process at a time). مورد واحد على الأقل غير قابل للمشاركة (عملية واحدة فقط في كل مرة).
2. Hold and Wait 2. Hold and Wait (الاحتفاظ والانتظار) A process must be holding at least one resource and waiting for another. يجب أن تحتفظ العملية بمورد واحد على الأقل وتنتظر آخر.
3. No Preemption 3. No Preemption (عدم الاستيلاء) Resources cannot be forcibly taken. They must be released voluntarily. لا يمكن أخذ الموارد بالقوة. يجب أن يتم تحريرها طوعاً.
4. Circular Wait 4. Circular Wait (الانتظار الدائري) A set $\{P_0, P_1, ..., P_n\}$ exists such that $P_0 \to P_1 \to ... \to P_n \to P_0$. توجد مجموعة $\{P_0, P_1, ..., P_n\}$ بحيث $P_0 \to P_1 \to ... \to P_n \to P_0$.

Resource Allocation Graph (RAG) Resource Allocation Graph (RAG)

A graph where Processes are Circles and Resources are Rectangles (with dots for instances). رسم بياني حيث العمليات (Processes) دوائر والموارد (Resources) مستطيلات (بها نقاط لتمثيل النسخ/Instances).

Edges:الحواف (Edges):
Request Edge:Request Edge: $P \to R$
Assignment Edge:Assignment Edge: $R \to P$
IF graph contains no cycles $\implies$ NO Deadlock. إذا لم يحتوي الرسم على دورات $\impliedby$ لا يوجد Deadlock.
IF graph contains a cycle: إذا احتوى الرسم على دورة (Cycle):
- If only one instance per resource type $\implies$ DEADLOCK. - إذا كانت نسخة واحدة فقط لكل نوع مورد $\impliedby$ DEADLOCK.
- If multiple instances $\implies$ POSSIBILITY of Deadlock. - إذا كانت نسخ متعددة $\impliedby$ احتمالية (Possibility) لـ Deadlock.

Handling Strategies استراتيجيات التعامل (Handling Strategies)

Prevention المنع (Prevention)

Invalidate one of the 4 conditions so deadlock is impossible. إبطال أحد الشروط الأربعة لجعل الـ Deadlock مستحيلاً.

Avoidance التجنب (Avoidance)

Use info about future requests to steer clear of "Unsafe States". (Banker's Algo). استخدام معلومات حول الطلبات المستقبلية لتجنب "الحالات غير الآمنة". (Banker's Algo).

Detection & Recovery Detection & Recovery

Let it happen, detect cycle, and kill process (Ostrich Algorithm: Ignore it). دعه يحدث، اكتشف الدورة، وانهِ العملية (Ostrich Algorithm: تجاهله).

The Banker's Algorithm The Banker's Algorithm (خوارزمية المصرفي)

Before granting a request, the OS checks: "If I give you this, will the system remain in a Safe State?" قبل منح الطلب، يتحقق نظام التشغيل: "إذا أعطيتك هذا، هل سيبقى النظام في حالة آمنة (Safe State)؟"
A state is Safe if there exists a sequence of execution where all processes can finish. تكون الحالة آمنة (Safe) إذا وجد تسلسل للتنفيذ يسمح لجميع العمليات بالانتهاء.

Data Structures: n = processes, m = resource types Available: Vector of length m. Max: n x m matrix. (Max demand of each process). Allocation: n x m matrix. (Current allocation). Need: n x m matrix. (Max - Allocation). Need[i,j] = Max[i,j] - Allocation[i,j]

Safety Algorithm (Simplified) Safety Algorithm (مبسطة)

  1. Initialize `Work = Available` and `Finish[i] = false` for all i. ابدأ بـ `Work = Available` و `Finish[i] = false` للكل.
  2. Find a process $P_i$ such that: جد عملية $P_i$ بحيث:
    - `Finish[i] == false`
    - `Need[i] <= Work` (Can its request be satisfied?) (هل يمكن تلبية طلبها؟)
  3. If found: إذا وجدت:
    - Assume $P_i$ finishes and returns resources: افترض أن $P_i$ تنتهي وتعيد الموارد: `Work = Work + Allocation[i]`.
    - Set `Finish[i] = true`.
    - Repeat Step 2. كرر الخطوة 2.
  4. If all `Finish[i] == true`, the system is in a Safe State. إذا كان كل `Finish[i] == true`، فالنظام في Safe State.

Recovery Strategies استراتيجيات الاسترداد (Recovery Strategies)

Process Termination إنهاء العملية (Process Termination)

  • Abort All:Abort All: Extreme, but effective. Loses all progress. متطرف ولكنه فعال. تفقد كل التقدم.
  • Abort One by One:Abort One by One: Kill one, run detection, repeat until cycle breaks. اقتل واحدة، شغل الاكتشاف، كرر حتى تنكسر الدورة.
    Victim Selection: اختيار الضحية (Victim Selection): Priority, CPU usage, Resources held. الأولوية، استخدام CPU، الموارد المحتجزة.

Resource Preemption Resource Preemption (استيلاء الموارد)

  • Select a victim to steal resources from. اختر ضحية لسرقة الموارد منها.
  • Rollback:Rollback: Return process to a safe checkpoint and restart. أعد العملية إلى نقطة تفتيش آمنة وأعد التشغيل.
  • Starvation:Starvation: Ensure same process isn't always the victim (include rollback count in cost factor). تأكد من أن نفس العملية لا تكون الضحية دائماً (ضمّن عدد الـ rollback في عامل التكلفة).

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Cycle != Deadlock فخ: Cycle != Deadlock

A cycle in the Resource Allocation Graph (RAG) is a necessary condition, but NOT sufficient if resources have multiple instances. Deadlock only guaranteed if single instance per resource type. الدورة (Cycle) في الرسم البياني (RAG) شرط ضروري، لكنه غير كافٍ إذا كانت الموارد لها نسخ متعددة. الـ Deadlock مضمون فقط إذا كانت نسخة واحدة لكل نوع مورد.

TRAP: Unsafe != Deadlock فخ: Unsafe != Deadlock

An Unsafe State does not mean Deadlock exists now. It means Deadlock could happen if processes request their max resources in a specific order. الحالة غير الآمنة (Unsafe State) لا تعني وجود Deadlock الآن. تعني أن الـ Deadlock قد يحدث إذا طلبت العمليات مواردها القصوى بترتيب معين.

SECRET: Circular Wait Prevention سر: منع الانتظار الدائري

The most practical way to prevent deadlock is to attack the Circular Wait condition.
Method: Impose a total ordering of all resource types. Processes must request resources in increasing order of enumeration. الطريقة الأكثر عملية لمنع الـ deadlock هي مهاجمة شرط الانتظار الدائري (Circular Wait).
الطريقة: فرض ترتيب كلي لجميع أنواع الموارد. يجب أن تطلب العمليات الموارد بترتيب تصاعدي.

KEY CONCEPT: The Need Matrix مفهوم أساسي: The Need Matrix

In Banker's Algo problems, always calculate the NEED matrix first ($Max - Allocation$). Never compare Available against Max directly. في مسائل خوارزمية المصرفي (Banker's Algo)، احسب دائماً مصفوفة NEED أولاً ($Max - Allocation$). لا تقارن Available مع Max مباشرة أبداً.