Concept:
A phenomenon where multiple concurrent processes wait for each other due to competing for system resources.
Principle:
A set of processes is said to be in a deadlock when each process in the set is waiting for an event that can only be triggered by other processes in the set.
Essential Causes:
- Limited system resources.
- Unreasonable process advancement sequence.
Four Necessary Conditions for Deadlock Generation:
- Mutual Exclusion:
A resource allows access by only one process at a time. That is, once the resource is allocated to a process, other processes cannot access it until the process finishes using it.
- Hold and Wait:
A process holds some resources (one or more) and is waiting for other processes to release resources because its resource needs are not fully met.
- No Preemption:
If another process has already occupied a certain resource, you cannot seize that resource just because you also need it.
- Circular Wait:
There exists a chain of processes, where each process holds at least one resource required by the next process in the chain.
When all the above four conditions are satisfied, a deadlock will inevitably occur. Processes in a deadlock cannot proceed, and the resources they hold cannot be released. This will lead to a decrease in CPU throughput. Therefore, deadlock is a situation that wastes system resources and affects the performance of the computer. Thus, it is quite necessary to solve the problem of deadlock.
Methods to Avoid Deadlock
1. Deadlock Prevention — Ensuring the system never enters a deadlock state
Since four conditions are required for a deadlock to occur, a deadlock is impossible if at least one of these conditions is not met. The mutual exclusion condition is necessary for non-shared resources; it cannot be changed and should be guaranteed. Therefore, the focus is on destroying the other three conditions that lead to deadlock.
a. Destroy the “hold and wait” condition
- Method 1: All processes must apply for all the resources they need throughout their entire running process at once before starting to run.
- Advantages: Simple to implement and safe.
- Disadvantages: If a certain resource is not available, the process cannot start, and other resources that have been satisfied will not be utilized, which seriously reduces resource utilization and causes resource waste. It also makes processes often suffer from starvation.
- Method 2: This method is an improvement on the first one. It allows a process to obtain the resources needed in the initial stage and start running. During the running process, it gradually releases the allocated resources that have been used up, and then requests new resources. In this way, resource utilization will be improved, and the problem of process starvation will be reduced.
b. Destroy the “no preemption” condition
When a process that already holds some resources fails to get a new resource request satisfied, it must release all the resources it has held and reapply for them when needed later. This means that the resources held by the process will be temporarily released or preempted.
This method is relatively complex to implement and costly. Releasing the resources already held is likely to invalidate the previous work of the process. Repeatedly applying for and releasing resources may cause the execution of the process to be postponed indefinitely, which not only prolongs the process’s turnaround time but also affects the system’s throughput.
c. Destroy the “circular wait” condition
It can be prevented by defining a linear order of resource types. Each resource can be numbered. When a process holds a resource with number i, the next resource it applies for can only be a resource with a number greater than i.
