About the "deadlock" problem

Computer shop news

1, why there is a deadlock

1.1, a simple example

There are two processes ready Scan the document and record it on the CD. Process A requests the scanner and gets it, while Process B first requests the CD burner and gets it. Then process A requests the CD burner, which fails because process B already has a CD burner and is unwilling to release it, and also requests the scanner to complete the work. As a result, no one in the two processes can complete the work, and a deadlock appears.

1.2, About Resources

Scanners are a kind of resource. As you can see from the above, the request for resources is the root of the deadlock. In fact, the resource can be a hardware device (such as a CD burner) or a set of information (such as a locked record in the database). Simply put, the resource is anything that can be obtained, used, and released after use.

Resources fall into two categories: preemptible and non-preemptable. Preemptible means that resources are preempted from the process that owns them without side effects. From this, it can be seen that the re-allocation of resources can be solved when the use of preemptible resources is deadlocked.

In fact, there are a small number of deadlocks that are not caused by resources. I will not discuss them here.

2, deadlock modeling

2.1, deadlock specification definition

If each process in a process collection is waiting only by the process collection The events that other processes can raise, then the collection of processes is deadlocked.

Since every process is waiting, the result is that each process cannot raise events that satisfy other processes, and all processes will wait. In the case of resource usage, each process requires additional resources to continue, and processes that own those resources do not release them because they continue because there are not enough resources.

2.2, resource deadlock conditions and coping strategies

2.2.1, resource deadlocks have four necessary conditions: 1 mutually exclusive conditions. This means that a resource cannot be used simultaneously by multiple processes. 2 possession and waiting conditions. Processes that have already obtained a resource can continue to request additional resources. 3 can not preempt the conditions. As mentioned above, when a resource is preempted, it can cause side effects and can only be explicitly released by the process that owns it. 4 loop waiting condition. There is a chain of process loops in which resources acquired by each process in the chain are simultaneously requested by the next process.

2.2.2, there are four strategies for dealing with deadlocks: 1 ignore the problem. 2 detect deadlock and recover. 3 Carefully allocate resources to avoid deadlocks. 4 Prevent deadlocks from occurring by destroying one of the four necessary conditions that cause deadlocks. These strategies are discussed separately below.

3, ostrich algorithm

The algorithm corresponds to the first strategy above: ignore. The so-called ostrich algorithm is due to a folklore: the ostrich will bury its head in the sand when it encounters a problem, and nothing will pretend that there is no problem. Maybe you will feel very tangled: How can there be such a nonsense algorithm? For mathematicians, their ideas are just like you, and they must not tolerate a strategy of doing nothing. But for engineers, they will seriously consider the ostrich algorithm. When the probability of a deadlock is low and low, and there are a lot of other problems waiting to be resolved, they will adopt an ostrich algorithm for the deadlock problem.

4, deadlock detection and deadlock recovery

Deadlock detection is based on the aforementioned loop, that is, the detection process has a loop on the possession of resources and requests, and if so, The side illustrates the dead latch. This article is “simplified” and does not specifically describe the detection algorithm.

There are three ways to recover from deadlock: 1 Use preemption recovery. 2 use rollback recovery. Revert to an earlier state. 3 recover by killing the process. In fact, these methods are not good methods and have many drawbacks.

5, deadlock avoidance

The main algorithm to avoid deadlock is based on the concept of security state. The security state means that if no deadlock occurs, and even if all processes suddenly request the maximum demand for resources, there is still some sort of scheduling order that enables each process to finish running, which is said to be safe.

Deadlock Avoidance The most famous algorithm is the banker algorithm, which checks each request. If it is still safe after satisfying this request, it will be satisfied, otherwise the satisfaction of this request will be postponed.

6, deadlock prevention

Deadlock prevention is to destroy one of the four necessary conditions for causing deadlock. 1 destroys the mutually exclusive condition. Use spooling technology to simulate multiple processes occupying one resource at a time. 2 Destroy occupancy and waiting conditions. Specifies that all processes request and obtain all the resources they need before starting execution. 3 damage can not be preempted conditions. It is also using spooling technology. 4 break the loop waiting condition. All resources are numbered uniformly, and processes are requested in order when multiple resources are requested.

7, Summary

There is no perfect way to deal with deadlocks, and there is no universally applicable method. Only in different situations, comprehensively consider various strategies and formulate algorithms that satisfy the requirements to some extent.