What are the causes of deadlock in Linux?

The reasons for deadlock in Linux are: 1. Deadlock caused by competition for resources that cannot be preempted; 2. Deadlock caused by competition for consumable resources; 3. Deadlock caused by improper process advancement sequence (process running During the process, the order of requesting and releasing resources is inappropriate, resulting in process deadlock).

#The operating environment of this tutorial: linux5.9.8 system, Dell G3 computer.

1. The concept of deadlock:

If each process (or thread) in a group of processes (or threads) is Waiting for an event that can only be triggered by other processes (or threads) in the group of processes, then the group of processes (or threads) is deadlocked (Deadlock).

2. Reasons for deadlock:

(1) Deadlock caused by competition for non-preemptible resources

For example: deadlock caused when sharing files

There are two processes P1 and P2 in the system, both of which are preparing to write two files F1 and F2. Both of these are reusable and non-preemptible resources. If process P1 opens F1 at the same time, process P2 opens file F2. When P1 wants to open F2, it is blocked because F2 is already occupied. When P2 wants to open 1, it is blocked because F1 is already occupied. At this time, there will be no wireless connection. Waiting continues to form a deadlock.

(2) Deadlock caused by competition for consumable resources

For example: deadlock caused by process communication

There are three processes P1, P2 and P3 in the system. m1, m2 and m3 are 3 consumable resources. On the one hand, process P1 generates message m1 and sends it to P2, and on the other hand, it receives message m3 from P3. On the one hand, process P2 generates message m2 and sends it to P3, and on the other hand, it receives message m1 from P1. Similarly, process P3 on the one hand generates message m3 and sends it to P1, and on the other hand receives message m2 from P2.

If the three processes first send messages generated by themselves and then receive messages from others, they can run smoothly without causing a deadlock. However, if the three processes all receive messages from others first without If a message is generated, it will wait forever, resulting in a deadlock.

# (3) Deadlock caused by improper process advancement sequence: During the running process, the sequence of requesting and releasing resources is improper, resulting in process deadlock.

In the figure above, if you advance in the order of curve 1, the two processes can be completed smoothly; if you advance in the order of curve 2, the two processes can be completed smoothly; if you advance in the order of curve 3, , the two processes can be completed successfully; if they advance in the order of curve 4, the two processes will enter the unsafe area D. At this time, P1 retains resource R1, and P2 retains resource R2. The system is in an unsafe state. If it continues to If you push forward, a deadlock may occur.

3. Necessary conditions for deadlock

(1) Mutual exclusion condition . The resources requested by a process (thread) can only be occupied by one process (thread) lock within a period of time.

(2) Request and hold conditions. A process (thread) already occupies at least one resource, but a new resource request is made, and the resource is occupied by another process (thread).

(3) Non-preemption condition (non-preemption condition). Resources acquired by a process (thread) cannot be preempted before they are used up.

(4) Loop waiting condition (loop waiting condition). When a deadlock occurs, there must be a process (thread) - a circular chain of resources.

4. Deadlock avoidance, prevention and solutions

Deadlock avoidance is the final step to avoid deadlock during the operation of the system. occur.

The first three conditions for the occurrence of deadlock are the necessary conditions for the occurrence of deadlock, that is to say, the conditions that must be met to produce a deadlock. Rather than the existence of these three conditions, a deadlock will definitely occur. Logically, deadlock can be avoided by avoiding the fourth condition.

The basic idea of ​​deadlock avoidance: The system dynamically checks each resource request issued by the process that the system can satisfy, and decides whether to allocate resources based on the check results; if the system is likely to deadlock after allocation, then Not assigned; otherwise assigned.

(1) Commonly used methods to avoid deadlock:

1. Orderly allocation of resources

2. Banker’s algorithm, basic idea: In the deadlock avoidance method, processes are allowed to apply for resources dynamically, but before allocating resources, the system should first calculate the safety of the allocated resources. If the allocation will not cause the system to enter an unsafe state, allocate it, otherwise wait.

(2) Prevention of deadlock:

1. Destruction of the "inalienable" condition: When a process occupies a resource and then applies for another resource but cannot satisfy it, it will exit the originally occupied resource.
This strategy is complex and expensive to implement. Because a resource is forcibly deprived after being used for a period of time, it will cause the previous stage of work to fail.
2. Destroy the "request and hold" condition: adopt a static one-time resource allocation strategy, that is, apply for all resources before the process runs, run if satisfied, otherwise wait, so that it will not be occupied and applied for.
3. Destroy the "mutual exclusion" condition: This strategy is almost impossible, because the mutual exclusivity of resources is determined by its own nature.
4. Destroy the "circular waiting" condition: number all resources in the system sequentially. The general principle is that rarer and rarer resources have larger numbers. When a process applies for resources, it must strictly follow the order of resource numbers, otherwise the system will not allocate them. That is, a process can only apply for resources with larger numbers when it obtains resources with smaller numbers; when releasing resources, it should be done in descending order of numbers.

(3) Methods to solve deadlock:

There are currently two methods, one is to prevent deadlock from happening; the other is to allow deadlock to happen. It will be solved later.

There are four specific methods:

1. Prevent deadlock. Prevent deadlock from occurring by setting certain strict restrictions to destroy the conditions for deadlock, but this method will lead to low system resource utilization

2, avoid deadlock. In the process of dynamic resource allocation, some method is used to prevent the system from entering an unsafe state and avoid deadlock. This approach achieves higher resource utilization at the expense of weaker constraints.

3. Detect deadlock. Allow deadlocks to occur during system operation. By setting up a detection mechanism in the system, it can promptly detect whether a deadlock has actually occurred, accurately determine the processes and resources related to the deadlock, and then take measures to relieve the deadlock.

4. Release the deadlock. This is a measure that goes along with deadlock detection and is used to free the process from the deadlock state.

Related recommendations: "Linux Video Tutorial"

The above is the detailed content of What are the causes of deadlock in Linux?. For more information, please follow other related articles on the PHP Chinese website!