Deadlock is short for process deadlock, which was first proposed by Dijkstra in 1965 when he studied banker algorithm. It is one of the most difficult problems in computer system and concurrent programming. In fact, deadlock problem not only exists in computer system, it also exists widely in our daily life. What I want to do here is to leave language behind and use an example to talk about deadlocks, how does it happen? How can it be prevented?
Suppose we had a blue key that opened a blue door; And a red key to open a red door. The two keys were kept in a suitcase. At the same time, we define six behaviors: get the blue key, open the blue door, return the blue key, get the red key, open the red door, return the red key.
The rules of the game are as follows: a person (thread) has to open two doors in a sequence of six instructions, and return the key at the end.
Just note that the order of the three instructions in the same color is “get key -> open door -> return key”. For example, the following order of execution:
We can calculate that there are 20 possible solutions (
Same rules, but instead of two threads playing the game at the same time, each thread has two doors to open, but the two threads share a set of red and blue keys. If a thread retrieves a key and finds it has already been taken by another thread, it will wait until the other thread returns the key before continuing.
We randomly took two of the six solutions in single player mode: solution 3 and solution 4.
Consider these two sets of instructions as threads A and B, and start executing both sets of instructions at the same time:
Thread B needs to wait for thread A to return the blue key in step 6 before it can continue in step 4. Therefore, thread A finishes first and thread B finishes later, but both threads successfully complete the task.
Is it ok to pick any two of the six solutions?
Let’s try solution 3 and solution 5 this time as threads A and B:
Start thread A and thread B at the same time:
As you can see, when both threads get to step 3, thread A is waiting for thread B to return the red key, and thread B is waiting for thread A to return the blue key, so both threads are stuck forever.
This creates a deadlock.
Out of all the 20 possible thread solutions, two groups of threads are randomly selected, and there is a certain probability that a deadlock will occur. How about three groups of threads? . In general, the following four conditions must be met for a deadlock to occur:
Mutual exclusion conditions:
Exclusive use of allocated resources by a process, that is, a resource is occupied by only one process in a period of time. If another process requests the resource at this time, the requester can only wait until the process holding the resource is released.
— Only one set of keys
Request and hold conditions:
A process that has held at least one resource and then makes a new resource request that has been occupied by another process. In this case, the requesting process blocks but does not release other resources that it has obtained.
— The man with the red key asks for the blue key without returning it
Non-deprivation condition:
A resource that has been acquired by a process and cannot be taken away until it is used up, but can only be released when it is used up.
A man keeps the key until he returns it
Loop waiting condition:
When deadlock occurs, there must be a process – resource ring chain, that is, process set {P0, P1, P2, ···, Pn} P0 is waiting for a resource occupied by P1; P1 is waiting for resources occupied by P2…… Pn is waiting for a resource that has been occupied by P0.
The man with the red key is waiting for the blue key, while the man with the blue key is waiting for the red key
To avoid deadlock problems, you only need to break any of the four conditions.
Let’s look at common ways to avoid deadlocks.
— Method 1. Break the mutual exclusion condition —
There is only one set of keys, which is the most important reason for a deadlock. Obviously, deadlocks can be effectively avoided if we can make a separate copy of the key for each thread before the two threads run.
Of course, this approach is not widely tried. Because sometimes this approach doesn’t work if the cost of copying that set of keys is too high and there are too many threads.
— Method 2. Destroy loop waiting conditions —
Deadlocks occur in pairs, where one line must take the red key first and the other the blue key first, leading to a possible “loop wait.” So we could force any thread to retrieve keys in a “blue key first and then red key” order to avoid deadlocks. (Only the first three of the six solutions are valid.)
— Method 3. Destruction does not deprive conditions —
Inalienable conditions are created by the thread holding the key until it returns the key itself. Here, we can solve this problem by setting a threshold of “maximum occupancy time” — if 10 minutes pass without moving to the next step, the existing key is returned. In this case, both threads can get the keys they need to continue.
— Method 4. Break request and hold conditions
Any thread that is “greedy” can cause a deadlock. Basically, if you have one key, you don’t want another. We can solve this problem by stating that in any case, a thread that has acquired a key must return the key before it can request another key.
I often use this example of taking the key to open the door to explain deadlocks, one reason is that the process of explaining can be demonstrated by people and objects, which is easier to leave an impression on people. More importantly, the methods and ideas for avoiding deadlocks in this example can be easily applied to real-world programming.
Deadlocks are a very interesting topic, and they come into contact with quite frequently in practice. Of all the deadlock problems, SQL database deadlock is actually the most discussed. Next time I have a chance to talk specifically about SQL DB deadlocks.