Deadlocks Notes & Formulas

1. Definition

A deadlock is a situation where a set of processes are permanently blocked, each waiting for a resource held by another process in the set.

2. Necessary Conditions (Coffman Conditions - Very Important)

All four must hold simultaneously for deadlock:

1. Mutual Exclusion: At least one resource must be non-sharable
2. Hold and Wait: Process holds ≥1 resource and waits for more
3. No Preemption: Resources cannot be forcibly taken - only voluntarily released
4. Circular Wait: P1 waits for P2, P2 waits for P3, ..., Pn waits for P1

3. Resource Allocation Graph (RAG)

• Request edge: Process → Resource (process wants resource)
• Assignment edge: Resource → Process (resource assigned to process)
• Single instance: Cycle in RAG → deadlock
• Multiple instances: Cycle in RAG → may or may not be deadlock

4. Deadlock Handling Strategies

Prevention: Ensure at least one Coffman condition never holds

• Eliminate circular wait: impose ordering on resource types, request in order
• Eliminate hold & wait: request all resources at once before starting
• Allow preemption: if resource not available, preempt from holder

Avoidance: Dynamically check if allocation leads to unsafe state

• Requires advance knowledge of maximum resource needs
• Banker's Algorithm (Very Important)

Detection & Recovery:

• Allow deadlock to occur, detect using RAG or detection algorithm, then recover
• Recovery: process termination (abort all/one at a time) or resource preemption

Ignorance (Ostrich Algorithm): Ignore deadlock - used by most OS (Linux, Windows) for rare deadlocks

5. Banker's Algorithm (Very Important)

Data structures for n processes, m resource types:

• Available[m]: available instances of each resource
• Max[n][m]: maximum demand of each process
• Allocation[n][m]: currently allocated
• Need[n][m] = Max − Allocation

Safety Algorithm:

1. Work = Available; Finish[i] = false for all i
2. Find i where Finish[i]=false AND Need[i] ≤ Work
3. Work = Work + Allocation[i]; Finish[i] = true
4. Repeat until no such i found
5. If all Finish[i] = true → Safe state

Resource Request Algorithm:

1. If Request[i] ≤ Need[i]: proceed, else error
2. If Request[i] ≤ Available: proceed, else wait
3. Tentatively allocate, run safety algorithm
4. If safe → allocate; else → rollback and wait

6. GATE Trick

Banker's algorithm: always compute Need = Max − Allocation first. Safe sequence may not be unique - any valid sequence counts. For deadlock detection with multiple instances: use same algorithm as Banker's but with Allocation replacing Max. Cycle in single-instance RAG = deadlock (no further check needed).