Deadlock

Deadlock Detection

This is the most liberal strategy. Periodically, the OS performs an algorithm that allows it to detect the circular wait condition.

The algorithm proceeds by marking processes that are not part of a deadlocked set.

Initially, all processes are unmarked. Then the following steps are performed:

1. Mark each process that has a row in the Allocation matrix of all zeros. A process that has no allocated resources cannot participate in a deadlock.
2. Initialize a temporary vector $W$ to equal the Available vector.
3. Find an index $i$ such that process $i$ is currently unmarked and the ith row of $Q$ is less than or equal to $W$. That is, $Q_{ik}\le W_k$, for $1\le k\le m$. If no such row is found, terminate the algorithm.
4. If such a row is found, mark process i and add the corresponding row of the allocation matrix to $W$. That is, set $W_k=W_k+A_{ik}$, for $1\le k\le m$. Return to step 3.

1. Mark P4, because P4 has no allocated resources.
2. Set $W=(00001)$.
3. The request of process P3 is less than or equal to W, so mark P3 and set $W=W+(00010)=(00011)$
4. No other unmarked process has a row in $Q$ that is less than or equal to $W$. Therefore, terminate the algorithm.

The algorithm concludes with P1 and P2 unmarked, indicating these processes are deadlocked.

Deadlock Recovery

• Abort all deadlocked processes
• Back up each deadlocked process to some previously defined checkpoint, and restart all process
  • Original deadlock may occur
• Successively abort deadlocked processes until deadlock no longer exists
• Successively preempt resources until deadlock no longer exists

Related

• Deadlock Prevention
• Deadlock Avoidance