1. Necessary conditions
- Mutually exclusive: Each resource is either already allocated to a process or is available.
- Hold and wait: processes that already have a resource can request new resources again.
- Non-preemption: a resource that has been assigned to a process cannot be forcibly preempted; it can only be explicitly released by the process that occupies it.
- Loop wait: a loop consisting of two or more processes in which each process is waiting for resources to be occupied by the next process.
2. Treatment methods
There are four main methods:
- The ostrich policy
- Deadlock detection and deadlock recovery
- Deadlock prevention
- Deadlock avoiding
3. Ostrich strategy
Burying your head in the sand and pretending that there is no problem because deadlocks are expensive to solve, the ostrich approach of taking no mission measures will have higher performance. When a deadlock occurs, it does not have much impact on the user or the probability of deadlock is low. Therefore, the ostrich strategy can be adopted. Most operating systems, including Unix, Linux, and Windows, deal with deadlocks simply by ignoring them.
Deadlock detection and deadlock recovery
Do not try to prevent deadlocks. When a deadlock is detected, take steps to recover.
4.1 Deadlock detection for one resource of each type
The figure above shows resource allocation, with boxes representing resources and circles representing processes. Resource-pointing process indicates that the resource is allocated to the process, and process-pointing process indicates that the process requests the resource.
- The loop can be extracted from Figure A, as shown in Figure B, which satisfies the loop wait condition, so a deadlock occurs.
- Deadlock detection algorithm of one resource of each type is realized by detecting whether there is a loop in the directed graph. Depth-first search is carried out from a node, and the nodes asked by the other party are marked. If the labeled node is visited, it means that the directed graph has a loop, that is, deadlock is detected
4.2 Deadlock detection of multiple resources of each type
In the figure above, there are three processes and four resources, and each data represents the following meanings:
- E vector: total resources
- Vector A: residual resources
- C matrix: The number of resources owned by each process. each row represents the number of resources owned by a process
- R matrix: The number of resources requested by each process
If A= (2,2,2,0), A= (2, 2, 0). P2 can be executed, and resources owned by p2 are released after the execution. If A= (4,2,2,1), p1 can also be executed. All processes execute without deadlock
The algorithm is summarized as follows:
- Each process is initially unmarked and may be marked during execution. When the algorithm ends, any process that is not marked is a deadlock process.
- Find an unmarked process PI that requests resources less than or equal to A.
- If such A process is found, add the i-th row vector of the C-matrix to A, mark the process, and revert to 1.
- If there is no such process, the algorithm terminates.
Deadlock prevention
Prevent deadlocks before the program runs
5.1. Break the mutual exclusion condition
- For example, the spool printer technical condition allows several processes to output at the same time, the only process that really requests a physical printer is the printer daemon.
5.2. Destruction of possession and waiting conditions
- One way to do this is to mandate that all processes request all the resources they need before starting execution.
5.3. Break the non-preemption condition
5.4 Destroy loop wait
- Resources are uniformly numbered. Processes can only request resources in numbered order
6. Deadlock avoidance
Avoid deadlocks while the program is running
6.1. Safety status
The second column of Figure A Has indicates the number of available resources, the third column Max bar hi indicates the total number of required resources, and Free indicates the number of available resources. Starting from Figure A, let B have all the resources it needs (Figure B), release B at the end of the run, at which point Free becomes 5 (Figure C), and then run C and A in the same way so that all processes can run successfully, so the state shown in Figure A can be said to be safe.
-
Definition: a state is safe if no deadlocks occur, and if all processes suddenly request the maximum demand for resources, there is still some scheduling sequence that allows each process to finish running.
-
Detection of security states is similar to detection of deadlocks in that security states must require that no deadlocks occur. The following banker algorithm is very similar to the deadlock detection algorithm and can be combined for reference comparison.
6.2. Banker algorithm for a single resource
A banker in a small town, he promises a bunch of customers a certain amount of money, and what the algorithm does is it decides whether the fulfillment of the request is unsafe, and if it is, it rejects the request; Otherwise it will be allocated.
Figure C is an insecure state, so the algorithm rejects the previous request to avoid entering the state in Figure C.
6.3. Banker algorithm for multiple resources
- The algorithm for checking whether a state is secure is as follows:
- Find out if there is A row in the right-hand matrix that is less than or equal to vector A. If no such row exists, the system will deadlock and be in an unsafe state.
- If such A line is found, mark the process as terminated and add its allocated resources to A.
- Repeat the above two steps until all processes are marked terminated and the state is safe.
- If a state is not secure, it needs to be denied entry to that state.