Deadlock problem summary

What is a deadlock

Thread deadlocks are described like this ⼀ In this case ： Multiple threads are blocked at the same time , Of them ⼀ One or all of them are waiting for a resource to be released . Because the thread is ⽆ Block up for a limited period of time , So it's impossible for the program to work properly ⽌. As shown in the figure below , Threads A Resources held 2, Threads B Resources held 1, They all want to apply at the same time for ⽅ Resources for , So these two threads will wait for each other ⽽ Into the ⼊ Deadlock state .

Cause of deadlock

1、 Compete for resources
There are two types of resources in the system ：

• Deprivable resources , It refers to a process after obtaining such resources , This resource can be taken away by other processes or systems ,CPU Both main memory and main memory belong to the deprivable resources ;
• The other type of resource is an inalienable resource , When the system allocates such resources to a process , You can't take it back by force , It can only be released after the process is used up , Like a tape drive 、 Printers, etc .

One of the competing resources in deadlock refers to the competitive and undeniable resources （ for example ： There is only one printer in the system , Available for process P1 Use , Assume P1 The printer has been occupied , if P2 Continuing to ask the printer to print will block ）

Competing resources in deadlock generation. Another type of resource is competing temporary resources （ Temporary resources include hardware interrupts 、 The signal 、 news 、 Messages in the buffer, etc ）, Usually, the order of message communication is improper , A deadlock occurs

2、 The order of advancement between processes is illegal

if P1 Keep the resources R1,P2 Keep the resources R2, The system is in an unsafe state , Because these two processes move forward , A deadlock may occur

for example , When P1 Run to the P1：Request（R2） when , Will cause R2 Has been P2 Occupy and block ; When P2 Run to the P2：Request（R1） when , It will also be due to R1 Has been P1 Occupy and block , A process deadlock occurs

The necessary conditions for deadlock

1. mutual exclusion ： The process is exclusive to the required resources , If another process requests the resource , The requesting process can only wait .
2. Conditions of non deprivation ： The process has not released the obtained resources , It can't be taken away by other processes , I can only release myself .
3. Request and hold conditions ： The resources currently owned by the process when the process requests other new resources , The process continues to occupy .
4. Loop wait condition ： There is a process resource cycle waiting chain , The resources obtained by each process in the chain are simultaneously used by the next process in the chain
   request .

Deadlock solution

Ostrich strategy
Deadlock detection
Deadlock prevention
Deadlock avoidance
Deadlock Relieving

Ostrich strategy

Bury your head in the sand , Pretend there's no problem at all .

Because the cost of solving the deadlock problem is very high , So ostrich strategy, which does not take task measures, will get higher performance .

When a deadlock occurs, it will not affect the user much , Or the probability of deadlock is very low , You can use the ostrich strategy .

Most operating systems , Include Unix,Linux and Windows, The way to deal with deadlock is simply to ignore it .

Deadlock detection

1、 Deadlock detection of one resource of each type

The figure above shows the resource allocation diagram , Where the box represents the resource , A circle indicates a process . A resource pointing to a process indicates that the resource has been assigned to the process , A process pointing to a resource indicates that the process requests to get the resource .

chart a You can extract the ring , Pictured b, It satisfies the loop waiting condition , So deadlocks happen .

The deadlock detection algorithm for each type of resource is realized by detecting whether there is a ring in the digraph , Depth first search from a node , Mark visited nodes , If you access a marked node , It means that there are rings in digraphs , That is to say, deadlock is detected .

2、 Deadlock detection of multiple resources of each type

Above picture , There are three processes and four resources , Each data represents the following ：

• E vector ： Total resources
• A vector ： Resource surplus
• C matrix ： The number of resources each process has , Each line represents the amount of resources a process has
• R matrix ： The number of resources requested per process

process P1 and P2 The requested resources are not satisfied , Only process P3 Sure , Give Way P3 perform , After the release of P3 Resources we have , here A = (2 2 2 0).P2 It can be executed , Release after execution P2 Resources we have ,A = (4 2 2 1) .P1 It can also be executed . All processes can be carried out smoothly , There is no deadlock .

The algorithm is summarized as follows ：
Each process is not marked at the beginning , The execution process may be marked . When the algorithm ends , Any process that is not marked is a deadlock process .

1. Looking for a process without a tag Pi, It requests resources less than or equal to A.
2. If such a process is found , It will be C The order of the matrix i The row vector is added to A in , Mark the process , And turn back 1.
3. If there is no such process , Algorithm was terminated .

Deadlock prevention

1. Destroy mutually exclusive condition ： We can't break this condition , Because we ⽤ Locks are meant to make them mutually exclusive （ Critical resources require exclusive access ）.
2. Break request and hold condition ：⼀ Apply for all the resources for the second time .
3. Destroy the condition of non deprivation ： Occupy ⽤ Part of the resources thread into ⼀ When applying for other resources , If the application does not arrive , Can actively release the resources it occupies .
4. Break cycle waiting condition ： Prevention by applying resources in sequence . Click on ⼀ Apply for resources in order , Releasing resources releases resources in reverse order . Break cycle waiting condition .

Deadlock avoidance

Banker Algorithm

In the deadlock avoidance method, processes are allowed to request resources dynamically , But before the system allocates resources , The security of this allocation should be calculated first , If the allocation does not cause the system to go into an unsafe state , Then assign , Or wait for . To implement the banker's algorithm , The system must set up several data structures .

Deadlock Relieving

Once a deadlock is detected , We should take corresponding measures immediately , To unlock .
The main methods of deadlock release are ：

1. Law of deprivation of resources . Suspend some deadlock processes , And seize its resources , Assign these resources to other deadlock processes . But you should prevent a suspended process from getting resources for a long time , And in a state of scarcity .
2. Repeal process law . Compulsory revocation part 、 Even deadlocks all processes and deprives them of resources . The principle of revocation can be based on the priority of the process and the cost of the revocation process .
3. Process fallback . Let one （ many ） Processes are backed back enough to avoid deadlocks , Voluntary release of resources rather than deprivation when the process goes back . Ask the system to keep the historical information of the process , Set restore point .