What is a deadlock?
Deadlock refers to a deadlock caused by the competition for resources in the running process of multiple processes. When a process is in this deadlock state, it cannot move forward without external forces. So, for example, if there is A thread A that locks A and then locks B, and at the same time there is another thread B that locks B and then locks A. As shown below:
Four necessary conditions for deadlocks
The above is just one example of a deadlock. We can describe the conditions under which a deadlock occurs in a more precise way:
- The mutex. Resources are accessed competitively, where resources can be understood as locks;
- Hold and wait. Threads hold resources that have been allocated to them while waiting for other resources;
- Don’t grab. Resources acquired by a thread are not forced to be preempted by other threads.
- Loop waiting. There is a circular dependency chain of resources between threads, each thread depends on the next thread in the chain to release the necessary resources, and the end of the chain depends on the thread at the head of the chain, and enters a circular waiting state.
These four conditions are necessary for a deadlock to occur, and if any of them are not met, no deadlock will occur. Although the definitions of these four conditions seem quite theoretical and official, in actual programming practice we build solutions based on these four requirements for deadlocks. So think about what each of the four conditions means here, and think about whether or why a deadlock can still occur if one of the conditions is removed.
Deadlock handling
- Deadlock prevention
- Deadlock avoiding
- Deadlock detection
- Deadlock recovery
1. Deadlock prevention
So to prevent deadlocks, we have to make deadlocks impossible, and the most direct way is to break the conditions necessary for deadlocks to occur. If any of the necessary conditions are not true, then the deadlock cannot occur.
Mutexes are generally unbreakable, so there are three other ways to prevent deadlocks:
(1) Destroy hold and wait:
A system that does not allow a process to apply for another resource when it already has one means to prevent the process from applying for another resource while holding the resource.
Method 1: Before all processes start running, they must request all the resources they need in the entire process at once. In this way, the process will not request resources during the entire process, thus breaking the “request” condition. When the system allocates resources, as long as one resource cannot meet the needs of the process, it does not allocate resources to the process even if all other required resources are idle, and makes the process wait. Since the process does not occupy any resources during the waiting period, the “hold” condition is broken.
Method two: Require each process to release the resources it occupies before making a new resource request. Thus, when a process needs resource S, it needs to release its previously occupied resource R before it can claim resource S, even if it needs resource R again soon.
Comparison of the two protocols: the second protocol is better than the first protocol, because the first protocol will cause a serious waste of resources, greatly reduce the utilization rate of resources, but also cause hunger problems in other processes due to occupying a large amount of resources.
(2) Destruction of non-preemption conditions: allow the implementation of resource robbery.
Method 1: If a process holding certain resources is denied further resource requests, the process must release the resources it originally held and, if necessary, request these resources and additional resources again.
Method 2: If a process requests a resource currently occupied by another process, the operating system can preempt the other process and ask it to release the resource. This method can prevent deadlocks only when the priorities of any two processes are different.
(3) Destroy loop waiting conditions
In this way, the process must apply for resources in ascending order when applying for resources. When applying for resources in the future, the process can apply for resources only when the number of resources to be applied is greater than the current number.
2. Deadlock avoidance
The system dynamically checks each resource request that a process sends and decides whether to allocate resources based on the check result. If deadlocks may occur after resource allocation, the system does not allocate resources; otherwise, the system allocates resources. This is a dynamic policy to ensure that the system does not enter the deadlock state.
Deadlock prevention vs. deadlock avoidance
Prevention is preventing deadlocks by breaking the four necessary conditions for them to occur. Avoidance prevents the system from entering an insecure state during dynamic resource allocation to avoid deadlock.
3. Deadlock detection
1. Draw a resource allocation map
A system deadlock can be described using a resource allocation diagram. As shown below, a rectangle represents a process and a box represents a class of resources. Since there can be multiple resources of one type, use a dot in the box to represent one resource in a class. Directed edge requests from a process to a resource, indicating that the process applies for a unit of such resources. The edge from resource to process is called allocation edge, indicating that one resource of this type has been allocated to the process.
2. Simplify resource allocation diagrams
Step 1: Look at resource A. It has three arrows pointing outward, so it allocates three resources to the process.
Step 2: Look at resource B. It has one arrow pointing outward, so it allocates one resource to the process. At this point, B has one free resource to allocate.
Step 3: After looking at the resources, then look at the process. First look at the process P2, it only applies for one resource A, but the resource A has been used up, so the process P2 is blocked, so the process P2 can not be isolated.
Step 4: Look at process P1, it only applies for one RESOURCE B, at this point, the system still has one resource B unallocated, so it can meet the application of P1. This way, process P1 gets all of its resources, so it doesn’t block and can keep running until it’s done, and then we can release all of its resources. All the edges of P1 can be removed to create an isolated point, as shown below:
Step 5: After process P1 runs, release the occupied resources (2 A resources and 1 B resources). After the system reclaims these resources, the idle resources become 2 A resources and 1 B resources. Since process P2 has been applying for A resource, the system can satisfy its application. This way, process P2 gets all of its resources, so it doesn’t block and can run until it’s done, and then we can release all of its resources. You can remove all the edges of P2 to form an isolated point, which looks like this:
3. Use the deadlock theory
Deadlock principle:
- (1) If there are no loops in the resource allocation diagram, the system is not deadlocked.
- ② If a loop appears in the resource allocation diagram, the system may have a deadlock.
In other words, the system state is a deadlock state if and only if the resource allocation diagram of the S state is not completely reducible
Deadlock recovery
1. Resource deprivation
Suspends some deadlocked process, preempts its resources, and allocates those resources to other deadlocked processes. However, pending processes should be prevented from being starved of resources for an extended period of time.
Undo process method
Force the removal of some or all deadlocked processes and deprive them of resources. The principle of revocation can be carried out according to the process priority and the cost of revocation.
3. Process rollback method
Allow one (more) process to fall back enough to avoid a deadlock, and the process to fall back voluntarily releases resources rather than being stripped. The system is required to retain historical process information and set the restore point.
Reference: blog.csdn.net/hd12370/art…
Blog.csdn.net/ypt523/arti…
Blog.csdn.net/jgm20475/ar…