Deadlock Prevention

A deadlock can occur only if all four necessary conditions hold simultaneously:

1. Mutual exclusion

2. Hold and wait

3. No preemption

4. Circular wait

Deadlock prevention works by ensuring that at least one of these conditions never holds. If even one condition is broken, deadlock becomes impossible.

---

1. Mutual Exclusion

Condition

At least one resource must be nonsharable (only one thread can use it at a time).

Prevention Idea

If resources are sharable, deadlock cannot occur.

Example

• Read-only files can be shared by multiple threads

• No waiting is required → no deadlock

Limitation

Most critical resources cannot be shared, such as:

• Mutex locks

• Semaphores

• I/O devices

👉 Conclusion:

Mutual exclusion cannot generally be eliminated, so this approach is impractical for most systems.

---

2. Hold and Wait

Condition

A thread holds at least one resource while waiting for additional resources.

Prevention Techniques

Protocol 1: Request All Resources at Once

• A thread must request all required resources before it begins execution

• If all are not available, the thread waits without holding any resource

Protocol 2: Request Only When Holding None

• A thread can request resources only when it holds no resources

• Before requesting new resources, it must release all currently held resources

---

Problems with These Protocols

1. Low Resource Utilization

   • Resources may be allocated but unused for long periods

2. Starvation

   • A thread that needs many resources may wait indefinitely

👉 Conclusion:
Hold-and-wait prevention is possible but inefficient and unfair.

---

3. No Preemption

Condition

Resources cannot be forcibly taken from a thread.

Prevention Idea

Allow preemption of resources.

---

Protocol

• If a thread requests a resource that is unavailable:

  • All resources it currently holds are preempted (released)

  • The thread waits until it can reacquire:

    • Its old resources

    • The new requested resources

---

Alternative Protocol

• If requested resources are held by a thread that is also waiting, preempt them

• If held by a running thread, the requester must wait

---

Applicability

Works well for:

• CPU registers

• Memory

• Database transactions

Does not work well for:

• Mutex locks

• Semaphores

👉 Conclusion:
No-preemption prevention is limited and not suitable for most synchronization primitives.

---

4. Circular Wait (Most Practical Approach)

Condition

A circular chain of threads exists, where each thread waits for a resource held by the next.

---

Prevention Strategy: Resource Ordering

1. Assign a unique order to each resource type

   $$F: R \rightarrow \mathbb{N}$$
   

2. Require that threads request resources only in increasing order

---

Example

Let:

F(first_mutex)  = 1
F(second_mutex) = 5

Correct usage:

lock(first_mutex);
lock(second_mutex);

Incorrect usage:

lock(second_mutex);
lock(first_mutex);  // Not allowed

---

Why This Works (Intuition)

• If all threads acquire locks in the same order:

  • Cycles cannot form

  • Circular wait is impossible

---

Proof by Contradiction (Simplified)

Assume a circular wait exists:

T0 → R0 → T1 → R1 → ... → Tn → Rn → T0

This implies:

F(R0) < F(R1) < ... < F(Rn) < F(R0)

This is impossible, since a number cannot be less than itself.

➡️ Therefore, circular wait cannot occur.

---

Limitations of Lock Ordering

• Difficult to enforce in large systems with many locks

• Developers must strictly follow the ordering

• Dynamic lock acquisition can still cause deadlock

---

Example: Dynamic Lock Ordering Failure

In a bank transfer system Deadlock is possible if two threads simultaneously invoke the transaction()

function, transposing different accounts.

transaction(checking, savings, 25.0);
transaction(savings, checking, 50.0);

Even with lock ordering:

• Locks are obtained dynamically

• Different threads may acquire locks in opposite orders

• Deadlock is still possible

---

Summary Table

Condition Prevented	Technique	Practical?
Mutual exclusion	Make resources sharable	❌ Rarely
Hold and wait	Request all resources at once	❌ Inefficient
No preemption	Force resource release	❌ Limited
Circular wait	Lock ordering	✅ Most practical

---

Key Takeaways 

• Deadlock prevention works by breaking one necessary condition

• Preventing circular wait is the most widely used method

• Lock ordering is effective but must be carefully enforced

• Dynamic resource requests can still introduce deadlock risks