Search⌘ K
Home
Courses
Operating Systems: Virtualization, Concurrency & Persistence

Deadlock Bugs

Explore the nature of deadlock bugs in concurrent systems by understanding the four necessary conditions for deadlock occurrence. Learn how circular wait and resource locking can halt thread execution and discover techniques to prevent, avoid, or recover from deadlocks. This lesson also highlights the challenges of deadlocks in complex large-scale software and the importance of careful locking strategies.

We'll cover the following...

Beyond the concurrency bugs mentioned in the previous lesson, a classic problem that arises in many concurrent systems with complex locking protocols is known as deadlock. Deadlock occurs, for example, when a thread (say Thread 1) is holding a lock (L1) and waiting for another one (L2); unfortunately, the thread (Thread 2) that holds lock L2 is waiting for L1 to be released. Here is a code snippet that demonstrates such a potential deadlock:

C
Thread 1:                   Thread 2:

pthread_mutex_lock(L1);     pthread_mutex_lock(L2);

pthread_mutex_lock(L2);     pthread_mutex_lock(L1);

Note that if this code runs, deadlock does not necessarily occur; rather, it may occur if, for example, Thread 1 grabs lock L1 and then a context switch occurs to Thread 2. At that point, Thread 2 grabs L2, and tries to acquire L1. Thus we have a deadlock, as each thread is waiting for the other and neither can run. See the figure below for a graphical depiction; the presence of a cycle in the graph is indicative of ...