Chapter 12: Deadlocks

Deadlocks, one of the most common concurrency problems, will be the first problem that we will analyze in this book. In this chapter, we will discuss the theoretical causes of deadlocks in concurrent programming. We will cover a classical synchronization problem in concurrency, called the dining philosophers problem, as a real-life example of a deadlock. We will also illustrate an actual implementation of a deadlock in Python and discuss several methods to address this problem. This chapter will also cover the concept of livelocks, which are relevant to deadlocks and are also a common problem in concurrent programming.

The following topics will be covered in this chapter:

• The concept of deadlocks
• Approaches to deadlock situations
• The concept of livelocks

By the end of this chapter, we will have gained a deep understanding of the problem, its place in concurrent programming, and the practical approaches to solving it.

Technical requirements

The code files for this chapter can be accessed through this link: https://github.com/PacktPublishing/Advanced-Python-Programming-Second-Edition/tree/main/Chapter12.

The concept of deadlocks

In concurrent programming, a deadlock refers to a specific situation in which no progress can be made, and the program becomes locked in its current state. In most cases, this phenomenon is caused by a lack of, or mishandled, coordination between different lock objects (for thread synchronization purposes). In this section, we will discuss a thought experiment, commonly known as the dining philosophers problem, to illustrate the concept of a deadlock and its causes; from there, you will learn how to simulate the problem in a Python concurrent program.

The dining philosophers problem

The dining philosophers problem was first introduced by Edgar Dijkstra, a leading pioneer in concurrent programming, in 1965. This problem was first demonstrated using different technical terms (resource contention in computer systems) and was later rephrased by Tony Hoare, a British computer scientist and the inventor of the quicksort sorting algorithm. The problem statement...

Approaches to deadlock situations

Intuitively, each of the following approaches looks to eliminate one of the four Coffman conditions from our program to prevent deadlocks. Our first solution is to implement ranking among the competing resources.

Implementing ranking among resources

From both the dining philosophers problem and our Python example, we can see that the last condition of the four Coffman conditions, circular wait, is at the heart of the deadlock problem. It specifies that the different processes (or threads) in our concurrent program wait for resources held by other processes (or threads) circularly. By taking a closer look, we can see that the root cause for this condition is the order (or lack thereof) in which the processes (or threads) access the resources.

In the dining philosophers problem, each philosopher is instructed to pick up the fork on their left first, while in our Python example, the threads always try to acquire the locks with the same name before...

The concept of livelocks

The concept of a livelock is connected to a deadlock; some even consider it an alternate version of a deadlock. In a livelock situation, the processes (or threads) in the concurrent program can switch their states; in fact, they switch states constantly. Yet, they simply switch back and forth infinitely, and no progress is made. We will now consider an actual scenario of a livelock.

Suppose that a pair of spouses are eating dinner together at a table. They only have one fork to share, so only one of them can eat at any given point. Additionally, the spouses are polite to each other, so even if one spouse is hungry and wants to eat their food, they will leave the fork on the table if their partner is also hungry. This specification is at the heart of creating a livelock for this problem: when both spouses are hungry, each will wait for the other to eat first, creating an infinite loop in which each spouse switches between wanting to eat and waiting for the...

Summary

In this chapter, we covered the causes of deadlocks in concurrent applications and implemented approaches to prevent them from occurring. Our examples have shown that concurrency cannot always be achieved straightforwardly and that some situations may require special handling. These discussions have prepared us for deadlocks in the real world and pointed us toward potential solutions.

In the next chapter, we will discuss another common problem in concurrent programming: starvation.

Questions

1. What can lead to a deadlock situation, and why is it undesirable?
2. How is the dining philosophers problem related to the problem of a deadlock?
3. What are the four Coffman conditions?
4. How can resource ranking solve the problem of a deadlock? What other problems can occur when this is implemented?
5. How can ignoring locks solve the problem of a deadlock? What other problems can occur when this is implemented?
6. How is a livelock related to a deadlock?

Further reading

• Parallel Programming with Python, by Jan. Palach, Packt Publishing Ltd, 2014
• Python Parallel Programming Cookbook, by Giancarlo Zaccone, Packt Publishing Ltd, 2015
• Python Thread Deadlock Avoidance (dabeaz.blogspot.com/2009/11/python-thread-deadlock-avoidance_20)