Deadlock Conditions, RAG & Banker's Algorithm

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 in the same set.

In 1971, Edward G. Coffman Jr. proved that a deadlock can arise IF AND ONLY IF all four of the following conditions hold simultaneously:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode (only one process at a time can use the resource).

2. Hold and Wait: A process must currently be holding at least one resource and requesting additional resources held by other processes.

3. No Preemption: Resources cannot be forcibly confiscated from a process; a resource can only be released voluntarily by the process holding it.

4. Circular Wait: A closed chain of processes {P₀, P₁, ..., Pₙ} exists such that P₀ waits for P₁, P₁ waits for P₂, and Pₙ waits for P₀.

Operating systems deal with deadlocks using one of four fundamental strategies:

1. Deadlock Ignorance (The Ostrich Algorithm): Stick your head in the sand and pretend deadlocks never occur. If a deadlock strikes, reboot the machine or kill processes manually. This is the pragmatic choice of Linux and Windows, because handling deadlocks dynamically is too computationally expensive relative to their rarity.

2. Deadlock Prevention: Restrict resource requests at design time so that at least ONE of the four Coffman conditions is structurally impossible to satisfy (e.g., impose a global total ordering on all resources to eliminate Circular Wait: Havender's linear ordering).

3. Deadlock Avoidance (Dynamic Inspection): Whenever a process requests an available resource, the kernel decides whether allocating it leaves the system in a Safe State. If the state would become Unsafe, the request is deferred, even though the resource is physically free! The classic avoidance algorithm for multiple resource types is Dijkstra's Banker's Algorithm.

4. Deadlock Detection & Recovery: Allow the system to enter deadlock, periodically run a detection algorithm (e.g. cycle check on a Wait-For Graph), and recover by terminating victim processes or rolling back transactions.

Safe State vs. Unsafe State vs. Deadlock:

• Safe State: A state is safe if there exists at least one Safe Sequence \langle P_1, P_2, ..., P_n \rangle such that for each P_i, the maximum resources P_i still needs can be satisfied by the currently available resources plus the resources already held by all preceding processes P_j (j < i).

• Unsafe State: An unsafe state is NOT necessarily a deadlock! Rather, an unsafe state is a vulnerable state that can lead to deadlock if processes exercise their maximum claims.

Banker's Algorithm Data Structures:

• Available[m]: Vector of length m. If Available[j] = k, there are k instances of resource type R_j free.

• Max[n][m]: Matrix defining the maximum claim of each process. Max[i][j] is max instances of R_j that process P_i may request.

• Allocation[n][m]: Currently allocated resources. Allocation[i][j] is instances of R_j currently held by P_i.

• Need[n][m] = Max[n][m] - Allocation[n][m]: Remaining resources process P_i may need to finish.