Handling Deadlocks

1. Introduction to Deadlocks

• A deadlock is a situation where two or more processes are blocked indefinitely, waiting for each other to release resources.

• Conditions for Deadlock (all four must be met for a deadlock to occur):

  1. Mutual Exclusion: Resources are non-sharable (only one process at a time can use a resource).

  2. Hold and Wait: A process holds at least one resource and is waiting to acquire additional resources held by other processes.

  3. No Preemption: A resource cannot be forcibly taken from a process holding it; it must be released voluntarily.

  4. Circular Wait: A set of processes ${P<em>0, P</em>1, …, P<em>n}$ exists such that ${P</em>0}$ is waiting for a resource held by ${P<em>1}$, ${P</em>1}$ is waiting for a resource held by ${P<em>2}$, …, ${P</em>{n-1}}$ is waiting for a resource held by ${P<em>n}$, and ${P</em>n}$ is waiting for a resource held by ${P_0}$.

2. Strategies for Handling Deadlocks

Operating systems employ various strategies to handle deadlocks:

2.1. Deadlock Prevention

• Aims to prevent deadlocks by ensuring that at least one of the four necessary conditions for deadlock (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) can never occur.

  • Breaking Mutual Exclusion: Not always possible (e.g., printer, non-sharable resources).

  • Breaking Hold and Wait:

  • Option 1: A process requests all its required resources at once before starting execution. If not all resources are available, it waits without holding any.

  • Option 2: A process can only request new resources when it holds none. If it needs additional resources, it must release all currently held resources first, then request everything (current and new).

  • Breaking No Preemption:

  • If a process holding resources requests another resource that's unavailable, all its currently held resources are preempted (released).

  • The process will restart only when it can acquire both its old and new resources.

  • Breaking Circular Wait: Imposes a total ordering of all resource types.

  • Processes must request resources in increasing order of enumeration.

  • Example: Printer ($R<em>1$), Tape Drive ($R</em>2$). A process holding $R<em>2$ cannot request $R</em>1$.

2.2. Deadlock Avoidance

• Requires prior knowledge of the resources a process will request and release during its lifetime.

• Dynamically decides if a request can be granted without leading to an unsafe state (a state where a deadlock might occur).

• Safe State: A state is safe if the system can allocate resources to each process in some order and avoid a deadlock.

• Banker's Algorithm: A famous deadlock avoidance algorithm.

  • Allows the system to check if allocating resources to a process will leave the system in a safe state.

  • If not, the process waits.

2.3. Deadlock Detection and Recovery

• Allows deadlocks to occur, periodically checks for their existence, and then recovers.

• Detection: An algorithm is run to detect if the system is in a deadlocked state.

  • Typically uses a resource-allocation graph or similar data structures.

  • Checks for cycles in the graph.

• Recovery: Once detected, recovery methods include:

  • Process Termination:

  • Terminate all deadlocked processes: Drastic but simple.

  • Terminate one process at a time: Terminate a process, check for deadlock, and repeat until the deadlock is resolved.

  • Selection criteria for termination: Priority, execution time, resources held, how many processes it will affect.

  • Resource Preemption:

  • Select a victim resource to preempt (take away from a process).

  • Rollback: The process whose resource was preempted must be rolled back to some safe state and restarted from there.

  • Starvation: Ensure a process is not always chosen as a victim (e.g., use a count).

2.4. Deadlock Ignorance (Ostrich Algorithm)

• The simplest approach: ignore the problem altogether and pretend deadlocks never happen.

• Often used in systems where the cost of prevention, avoidance, or detection is higher than the rare occurrence and impact of a deadlock.

• Example: Most operating systems like UNIX and Windows typically use this approach, relying on user or application intervention to resolve issues if a deadlock occurs.