Deadlock Prevention

Deadlock prevention aims to preclude deadlocks by ensuring that at least one of the four necessary conditions for deadlock cannot hold.

1. Mutual Exclusion

• Condition: Resources are exclusively held, meaning only one process can use a resource at a time.

• Prevention: This condition generally cannot be prevented for non-shareable resources (e.g., a physical printer). While some resources can be made shareable (like using a spooling system for a printer), for truly non-shareable resources (e.g., a writeable file), mutual exclusion is both unavoidable and necessary.

• Difficulty: Often impractical or impossible as many resources are inherently non-shareable.

2. Hold and Wait

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

• Prevention Strategies:

  • Strategy 1 (All at once): A process must request and be allocated all its resources before it begins execution.

    • Pros: Simple to implement.

    • Cons:

      • Low resource utilization (resources might be held for a long time without being used).

      • Starvation (a process requiring many popular resources might never get them).

  • Strategy 2 (No resources when requesting more): A process can only request resources when it holds none. If it needs more resources later, it must release all currently held resources first, then request the new set of resources (including the ones it just released).

    • Pros: Prevents a process from holding resources while waiting for others.

    • Cons: Similar to Strategy 1, can lead to low utilization and starvation.

3. No Preemption

• Condition: Resources cannot be forcibly taken away from a process; they can only be released voluntarily by the process holding them after it has completed its task.

• Prevention Strategy: Allow preemption of resources.

  • Method 1: If a process holding some resources requests another resource that cannot be immediately allocated, all resources currently held by that process are released. These preempted resources are added to the list of resources for which the process is waiting. The process will only restart its execution when it can acquire all its old resources and the newly requested ones.

  • Method 2: If a process requests a resource that is available, it is allocated. If not, and it is held by a waiting process, then the resource is preempted from the waiting process. If the resource is held by a running process, the requesting process must wait.

• Difficulty: Preemption is not always possible (e.g., a printer actively printing). It is generally feasible for resources like CPU registers or memory.

4. Circular Wait

• Condition: 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$.

• Prevention Strategy: Impose a total linear ordering on all resource types.

  • Method: Assign a unique integer number (order) to each resource type. A process can only request resources in increasing order of enumeration.

  • Rule: A process can only request a resource type with an order number greater than any resource type it currently holds. If it needs a resource with a lower order number, it must first release all higher-order resources.

  • Pros: Guarantees no circular wait.

  • Cons:

    • Requires knowing all resource needs in advance.

    • May lead to inefficient resource utilization if processes cannot request resources in a natural order.

    • Difficult to establish an optimal ordering for all systems.