Deadlock Prevention - aryanjoshi0823/5143-Operating-System GitHub Wiki

Techniques for Deadlock Prevention

7.4.1 Mutual Exclusion

  • Description: Shared resources like read-only files do not cause deadlocks. However, some resources (e.g., printers, tape drives) inherently require exclusive access by one process.
  • Prevention: Design systems to minimize exclusive access wherever possible. However, for resources that inherently require exclusivity, other deadlock prevention strategies must be employed.

7.4.2 Hold and Wait

  • Description: Prevent processes from holding resources while waiting for others.
  • Techniques:
    1. Single Request for All Resources:
      • Processes must request all required resources at once.
      • Drawback: Can lead to inefficient resource utilization if a process holds resources it does not immediately need.
    2. Release and Reacquire:
      • Processes must release currently held resources before requesting additional ones.
      • Reacquisition occurs in a single new request.
      • Drawback: Risk of failure to reacquire resources, potentially leading to incomplete operations.
    • Starvation Risk:
      • Both methods may lead to starvation if a process requires highly demanded resources.

7.4.3 No Preemption

  • Description: Allow preemption of resource allocations under specific conditions.
  • Techniques:
    1. Implicit Release on Wait:
      • If a process is forced to wait for a resource, all previously held resources are released.
      • The process must then reacquire all resources, including the new one, in a single request.
    2. Preemption of Blocked Processes:
      • If a process requests a resource that is unavailable, the system checks for blocked processes holding the required resource.
      • Resources held by such processes may be preempted and reallocated.
  • Applicability:
    • Preemption works well for resources like memory or registers, where states can be saved and restored.
    • It is not feasible for devices like printers or tape drives due to the inability to save and restore states.

7.4.4 Circular Wait

  • Description: Prevent circular wait by imposing a strict order on resource requests.
  • Technique:
    • Assign a unique number to each resource.
    • Processes can only request resources in strictly increasing (or decreasing) numerical order.
    • Example:
      • If Ri and Rj are resources, and i < j, a process holding Ri can only request Rj, not Rk where k < i.
    • Challenge
      • Determining a suitable ordering of resources can be complex in systems with diverse resource types and usage patterns.