Deadlock

Deadlocks occur when two or more tasks/processes are waiting indefinitely for resources held by each other, resulting in a circular wait. To prevent deadlocks, you can use various strategies and techniques.

---

Necessary Conditions for Deadlock

A deadlock occurs if all of the following four conditions are true:

1. Mutual Exclusion: A resource can only be held by one task at a time.

2. Hold and Wait: A task holding a resource is waiting to acquire additional resources.

3. No Preemption: Resources cannot be forcibly taken away from a task.

4. Circular Wait: A circular chain of tasks exists, where each task holds a resource and waits for another.

Preventing deadlock involves breaking at least one of these conditions.

---

Techniques to Prevent Deadlock

1. Resource Allocation Ordering

• Assign a strict order to resources, and require tasks to request resources in this order.

• This avoids circular wait because tasks will always acquire resources in a specific sequence.

Example:

• Suppose tasks need resources A and B.

• If a task holds resource A, it can only request resource B next. It cannot request B first, ensuring no circular chain is formed.

2. Avoid Hold and Wait

• Allocate all required resources at the start of a task’s execution.

• Tasks will not hold some resources while waiting for others.

Pros: Prevents deadlock completely.
Cons: Can result in resource under utilization, as some tasks may hold resources longer than needed.

Example in C++ pseudocode:

cppCopy codelock(mutexA);
lock(mutexB); // Acquire all required locks at once
// Perform operations
unlock(mutexB);
unlock(mutexA);

---

3. Resource Timeout

• Use timeouts when acquiring resources. If a task cannot acquire the resource within a certain time, it will release any held resources and retry later.

Example:

cppCopy codeif (lock.try_lock_for(std::chrono::seconds(2))) {
    // Lock acquired
} else {
    // Handle timeout (e.g., retry, release other locks)
}

This breaks the hold and wait condition because tasks don’t wait indefinitely.

---

4. No Circular Wait – Resource Hierarchies

• Impose a strict resource hierarchy to prevent circular waiting.

• A task can only request a resource with a higher priority than the ones it already holds.

Example:

• Suppose resources A, B, and C have priorities: A < B < C.

• If a task holds A, it can request B but not C directly.

---

5. Release Resources When Blocking

• Ensure that a task releases held resources if it cannot proceed.

• This technique can break the hold and wait condition.

Example:

• If Task A is waiting for resource B, it will release resource A and try again later.

---

6. Use Deadlock Detection and Recovery

Instead of preventing deadlocks outright, you can detect them and recover:

1. Deadlock Detection Algorithm: Periodically check the system for circular waits.

2. Recovery Mechanisms:

   • Abort tasks: Kill one or more tasks to release resources.

   • Preempt resources: Forcefully take resources from lower-priority tasks.

Drawback: Detection and recovery can be resource-intensive and disruptive.

---

7. Lock Ordering (Priority Inversion Solution)

• Always acquire locks in the same order across tasks to avoid circular waiting.

• This method aligns with priority inheritance: A lower-priority task holding a lock can temporarily inherit the higher priority of a waiting task to complete quickly and release the lock.

Example:

cppCopy codelock(mutex1); 
lock(mutex2); // Always acquire mutex1 first, then mutex2
// Perform operations
unlock(mutex2);
unlock(mutex1);

---

8. Deadlock-Free Locking Libraries

Modern programming frameworks provide libraries or mechanisms that avoid deadlocks:

• C++ STL std::lock: Prevents deadlocks when acquiring multiple locks simultaneously.

Example:

cppCopy codestd::lock(mutex1, mutex2); // Locks mutex1 and mutex2 without risk of deadlock

---

Summary of Deadlock Prevention Strategies

---

Practical Tips for Real-Time Systems

• Always prioritize timing and responsiveness in real-time operating systems (RTOS).

• Use priority inversion handling (e.g., priority inheritance) to prevent tasks from getting indefinitely blocked.

• Test concurrency extensively with tools like thread sanitizers or race condition detectors.