Direct Deadlock Prevention

operating-systems concurrency

Definition

Direct Deadlock Prevention

Direct deadlock prevention is a strategy that prevents deadlocks by explicitly prohibiting the circular wait condition from occurring.

Resource Ordering

The most common method for direct prevention is the use of a strict linear ordering $O$ of all resource types in the system.

• The Protocol: A process may only request resources of type $R_k$ if $O(R_k)>O(R_i)$ for all resources $R_i$ it currently holds.
• Notation: Each resource type is assigned a rank, for example:
  • $O(\text{Tape Drive})=2$
  • $O(\text{Disk Drive})=4$
  • $O(\text{Printer})=7$

If a process holds a Tape Drive (rank 2), it can request a Disk Drive (rank 4) or a Printer (rank 7), but it cannot request any additional Tape Drives or lower-ranked resources without first releasing its current holdings.

Correctness

By enforcing this hierarchy, the system ensures that no cycle of dependencies can ever be formed. For a proof of this mechanism, see the Circular Wait note.

Drawbacks

• Lower Concurrency: Legitimate out-of-order requests may be denied, leading to wasted resources.
• Complexity: It requires a system-wide agreement on resource ranks, which can be difficult to manage in dynamic or modular systems.