14.9. Deadlock and Its Avoidance

Deadlock: Occurs when two or more threads are blocked forever, each waiting for the other to release a lock.

A deadlock happens in a multithreaded environment when two or more threads are unable to proceed with their execution because each is waiting for the other to release a lock on a resource. Think of it like two cars stuck at a two-way stop sign, where neither can move forward because the driver of each car is waiting for the other to back up. In programming, when Thread A locks Resource 1 and needs Resource 2, while Thread B has locked Resource 2 and needs Resource 1, they both end up waiting indefinitely.

Imagine two friends at a restaurant who both want to eat the same dessert. Friend A picks the dessert first, but they can't share it without Friend B letting go of their fork. At the same moment, Friend B wants to eat the dessert too but can't take a bite until Friend A shares the fork. So, they both sit there, waiting, unable to enjoy their dessert until one decides to let go—the deadlock!

Example: Thread A locks Resource 1 and waits for Resource 2; Thread B locks Resource 2 and waits for Resource 1.

This specific example illustrates how deadlocks occur. Thread A acquires a lock on Resource 1 and then attempts to access Resource 2, which is already locked by Thread B. Simultaneously, Thread B, holding the lock on Resource 2, tries to access Resource 1, which Thread A owns. Because both threads are waiting for each other to release the locks, they enter a deadlocked state, and neither can proceed.

Think of two people trying to cross a narrow bridge from opposite sides. Each person reaches the middle and tries to pass, but they can't move forward without the other backing up. Neither wants to give way, just like the threads in a deadlock situation—both stuck because they are waiting on the other.

Avoiding Deadlock: • Lock ordering • Timeout for lock acquisition • Using try-lock mechanisms (e.g., ReentrantLock.tryLock())

There are several strategies to prevent deadlock in programming. One is 'lock ordering', where all threads acquire locks in a predefined order that prevents circular waiting. For example, if both threads always lock Resource 1 before Resource 2, then they can't end up in a deadlock. Another method is to impose a timeout for acquiring locks, where if a thread cannot obtain a lock within a specified time, it gives up and can try again later. Lastly, using try-lock mechanisms allows a thread to attempt to acquire a lock without blocking indefinitely; if it cannot get the lock instantly, it can move on to other tasks, preventing deadlock.

Consider an intersection with traffic lights. To avoid a traffic jam (akin to deadlock), traffic lights can be set to prevent two cars from entering the intersection at the same time. Also, if one car can't enter the intersection when its light turns green (timeout), it could turn right instead, similar to how a thread would try another task instead of waiting indefinitely for a lock.

--