There are many exclusive resources in the computer system, and each resource can only be used by one process at the same time. We have often mentioned the printer before. This is an exclusive resource. Two printers cannot output at the same time. As a result, otherwise, it will cause the paralysis of the file system. Therefore, the operating system has the ability to authorize a process to access resources alone.
Two processes exclusively access a resource and wait for the execution result of another resource, which will cause both processes to be blocked, and neither process will release their respective resources, which is a deadlock (deadlock) .
Deadlocks can occur at any level. Deadlocks may occur between different machines. Deadlocks may also occur in database systems. For example, process A locks record R1, process B locks record R2, and then process A locks record R2. Both B and B try to lock the object’s record, in which case a deadlock will occur.
Let’s discuss what is deadlock, what are the conditions for deadlock, how to prevent deadlock, what is livelock, etc.
First of all, you need to understand a concept, that is, what is a resource.
resource
Most deadlocks are related to resources. Deadlocks occur when processes have exclusive (exclusive) access to devices and files. We call this type of object that requires exclusive use a resource. Resources are mainly divided into preemptible resources and non-preemptible resources
Preemptible and non-preemptible resources
Resources mainly include preemptible resources and non-preemptible resources. A preemptable resource can be preempted from the process that owns it without causing any other impact. Memory is a preemptable resource, and any process can preempt the use of memory.
A nonpreemtable resource means that a process cannot preempt a specified resource unless an error or exception is caused. This nonpreemptible resource, such as a CD, cannot be obtained by other processes during the process of scheduling.
Deadlocks are related to non-preemptible resources. Although preemptible resources can also cause deadlocks, the solution to this situation is usually to redistribute resources between processes to resolve. Therefore, our focus will naturally be placed on non-preemptible resources.
If the resource does not exist at the time of the request, the requesting process is forced to wait. In some operating systems, the process will automatically block when the requested resource fails, and the process will automatically wake up when the self-resource is available. In other operating systems, requesting resources fails with an error code, then waits for the process to wait for a while before continuing to retry.
A process that fails to request a resource gets stuck in a cycle of requesting the resource, sleeping, and requesting the resource again. Although such processes are not blocked, for purposes and results, such processes are similar to blocking, because such processes do not do any useful work.
The process of requesting resources is very dependent on the operating system. On some systems, a request system call is used to allow a process to access a resource. On some systems, the operating system’s perception of a resource is that it is a special kind of file that can only be opened and occupied by one process at any one time. Resources are opened with the open command. If the file is already in use, the caller blocks until the current holding process closes the file.
Resource acquisition
For resources such as records in some database systems, it should be managed by the user process. One way to manage this is to use semaphores. These semaphores are initialized to 1 . Mutexes can also do the same thing.
Let’s talk about what is mutual exclusion lock (Mutexes):
In computer programs, a mutex is a program object that allows multiple programs to share the same resource, such as file access, but not simultaneously. A thread that needs to lock a resource must bind the mutex to other threads (lock it) when using the resource. The mutex is set to unlock when the data is no longer needed or the thread ends.
The following is a pseudo-code, this part of the code illustrates the operation of semaphore resource acquisition, resource release, etc., as shown below.
typedef int semaphore;
semaphore aResource;
void processA(void){
down(&aResource);
useResource();
up(&aResource);
}The above shows the process of acquiring and releasing a process resource, but in general, there will be situations where multiple resources acquire locks at the same time. How to deal with this? As follows
typedef int semaphore;
semaphore aResource;
semaphore bResource;
void processA(void){
down(&aResource);
down(&bResource);
useAResource();
useBResource();
up(&aResource);
up(&bResource);
}For a single process, there is no need to lock, because there is no race condition with this process. Therefore, the program can run perfectly under single-entry conditions.
Now let’s consider the case of two processes, A and B, and two resources exist. As follows
typedef int semaphore;
semaphore aResource;
semaphore bResource;
void processA(void){
down(&aResource);
down(&bResource);
useBothResource();
up(&bResource);
up(&aResource);
}
void processB(void){
down(&aResource);
down(&bResource);
useBothResource();
up(&bResource);
up(&aResource);
}In the above code, both processes access resources in the same order. In this code, one process acquires the resource before the other process, if the other process wants to acquire the resource before the first process releases it, it will block due to the resource lock until the resource is available.
In the code below, there are some changes
typedef int semaphore;
semaphore aResource;
semaphore bResource;
void processA(void){
down(&aResource);
down(&bResource);
useBothResource();
up(&bResource);
up(&aResource);
}
void processB(void){
down(&bResource); // changed code
down(&aResource); // changed code
useBothResource();
up(&aResource); // changed code
up(&bResource); // changed code
}This is a different case, where it can happen that both resources are acquired at the same time and effectively block the other process until it completes. That is, it may happen that process A acquires resource A at the same time as process B acquires resource B. Each process then blocks while trying to acquire another resource.
Here we will find that a simple problem of the order of acquiring resources will cause deadlock, so deadlock is easy to occur, so let’s make a detailed understanding and introduction of deadlock.
deadlock
If you want to define a deadlock, the following definition is more appropriate
If each process in a group of processes is waiting for an event that can only be triggered by another process in the group, this situation can lead to a deadlock.
To put it simply, each process is waiting for other processes to release resources, and other resources are also waiting for each process to release resources, so that no process preemptively releases its own resources, this situation will cause deadlock, and all processes will Wait indefinitely.
In other words, each process in a deadlocked process union is waiting for a resource already held by the other deadlocked process. But since all processes cannot run, none of them can release resources, so no process can be woken up. This kind of deadlock is also called resource deadlock. Resource deadlock is the most common type, but not all types. We will introduce other types later. Let’s introduce resource deadlock first.
Resource Deadlock Conditions
According to our description above, the possible situations of resource deadlock mainly include:
Mutual exclusion condition: each resource is assigned to a process or the resource is available
Hold and wait conditions: a process that has already acquired a resource is considered to be able to acquire a new resource
Non-preemption condition: A resource allocated to a process cannot be forcibly preempted from other processes, it can only be explicitly released by the process that owns it
Circular waiting: When a deadlock occurs, there must be two or more processes in the system to form a loop, and each process in the loop is waiting for the resources released by the next process.
When a deadlock occurs, the above conditions must occur simultaneously. If any of these conditions are not met, the deadlock will not occur. Deadlock can be broken by breaking any of these conditions. The following breaking conditions are the focus of our discussion
deadlock model
Holt proposed to model deadlock in 1972, and the modeling criteria are as follows:
#The circle represents the process
#Squares represent resources
From the resource node to the process node indicates that the resource has been occupied by the process, as shown in the following figure.
In the above figure, it means that the current resource R is being occupied by the A process
The directed graph from the process node to the resource node indicates that the current process is requesting resources, and the process has been blocked and is in a state of waiting for this resource.
In the diagram above, the meaning of the representation is that process B is requesting resource S . According to Holt, the description of deadlock should be as follows
This is a deadlock process. Process C is waiting for the release of resource T, but resource T is already occupied by process D. Process D is waiting for a request to occupy resource U, but resource U is already occupied by thread C, thus forming a ring.
To sum up: eating in the bowl and watching the pot is easy to deadlock
So how to avoid deadlock? Let’s talk about the deadlock model
Suppose there are three processes (A, B, C) and three resources (R, S, T). The request and release sequence of three processes for resources is shown in the following figure.
Process A: Request R, Request S, Release R, Release S
Process B: Request S, Request T, Release S, Release T
The operating system can arbitrarily choose a non-blocking program to run, so it can decide to run A until A has done its work; it can run B until B has done its work; and finally run C.
Such an order will not lead to deadlocks (since there is no competition for resources), but there is also no parallelism at all in this case. In addition to requesting and releasing resources, processes also do computation and input/output work. When processes run sequentially, another process cannot use the CPU while waiting for an I/O. So, strictly serial order execution is not optimal. On the other hand, if no process is doing any I/O, then shortest path first jobs are preferred over round-robin scheduling, so serial is probably the most superior in this case
Now we assume that processes will perform computation and I/O operations, so round-robin scheduling is a reasonable scheduling algorithm. Resource requests may be made in the following order
- A Request R
- B Request S
- C Request T
- A Request S
- B Request T
- C Request R
The following figure is a resource allocation diagram for the above six steps.
A question to pay attention to here, why does the directed graph from the resource point to the process but indicate that the process requests the resource? The author also had this question at the beginning, but after thinking about it, it is more appropriate to interpret this meaning as the process occupying resources, and the directed graph of the process points to the resource, which means that the process is blocked.
In the fourth step above, process A is waiting for resource S; in the fifth step, process B is waiting for resource T; in the sixth step, process C is waiting for resource R, thus creating a loop and causing death Lock.
However, the operating system does not dictate that these processes must be executed in a particular order. After encountering a thread that might cause a deadlock, the operating system can simply disapprove the request and suspend the process until it is safe. For example, in the above figure, if the operating system thinks there is a possibility of deadlock, it can choose not to allocate resource S to B, so that B is suspended. In this case, the operating system will only run A and C, then the request and release of resources will be the following steps.
A Request R
C Request T
A Request S
C Request R
A Request R
A Request S
The following figure is a resource allocation diagram for the above six steps.
After the sixth step is completed, it can be found that there is no deadlock. At this time, the resource S can be allocated to B, because the A process has completed the execution, and the C process has obtained the resources it wants. Process B can directly obtain resource S or wait for process C to release resource T .
There are four strategies for dealing with deadlocks:
Ignore the impact of deadlock (stunned)
Detect deadlocks and recover from deadlocks, detect deadlocks as they occur, and take action to resolve issues once they occur
Avoid deadlocks by carefully allocating resources
Avoid deadlocks by breaking one of the four conditions a deadlock produces
In the following, we will introduce these four methods separately.
Ostrich Algorithm
The easiest solution is to use the ostrich algorithm, bury your head in the sand and pretend the problem didn’t happen at all. Everyone’s reaction to this question is different. Mathematicians believe that deadlocks are unacceptable and must be prevented by effective strategies. Engineers want to know how often problems occur, how many times the system crashes for other reasons, and the serious consequences of deadlocks. If deadlocks occur infrequently and frequently crash due to hardware failures, compiler bugs, and other OS issues, most engineers won’t fix deadlocks.
Deadlock Detection and Recovery
The second technique is deadlock detection and recovery. This solution does not attempt to prevent deadlocks from occurring. Instead, this solution would want deadlocks to occur as often as possible, and recover from deadlocks after they are detected. Let’s discuss several ways to detect and recover from deadlock.
Deadlock detection method for one resource per type
What does it mean to have one resource per resource type? The printers we often mention are like this. The resources are only printers, but there will be no more than one device.
This error can be detected by constructing a resource allocation table, such as the one we mentioned above.
Algorithm to detect deadlocks in n processes from P1 to Pn. Assuming that the resource type is m, E1 represents resource type 1, E2 represents resource type 2, and Ei represents resource type i (1 <= i <= m). E represents the existing resource vector (existing resource vector), representing the total number of existing resources of each type.
Now we need to construct two arrays: C for the current allocation matrix and R for the request matrix. Ci represents the number of resources of each type held by Pi. So, Cij represents the amount of resource j held by Pi. Rij represents the amount of resource j that Pi needs to obtain
In general, the number of allocated resources j is added together with the number of all available resources = the total number of resources of this type.
Deadlock detection is based on vector comparisons. Each process is initially unmarked, and the algorithm will start marking the process. After the process is marked, it means that the process has been executed and will not enter a deadlock. When the algorithm ends, any process that has not been marked will be marked. Determined to be a deadlocked process.
We discussed two ways to detect deadlock above, so now that you know how to detect, when do you do deadlock detection? Generally speaking, there are two criteria for consideration:
Checking whenever there is a resource request consumes expensive CPU time.
Check every k minutes, or when CPU usage drops below a certain threshold. For CPU efficiency reasons, if the deadlocked process reaches a certain number, not many processes can run, so the CPU will be idle frequently.
recover from deadlock
Above we discussed how to detect process deadlocks. Our ultimate goal must be to make the program run normally. Therefore, we need to recover the detected deadlocks. Next, we will discuss the recovery of several deadlocks. Way
Recovery by Preemption
In some cases, a resource may be temporarily transferred from its holder to another process. For example, without notifying the original process, a resource is forcibly taken away from the process for use by other processes, and returned after use. This recovery method is generally more difficult and somewhat simple and rude, which is not desirable.
Recovery by rolling back
If system designers and machine operators know that deadlocks are possible, the process can be checked regularly. A checkpoint of a process means that the state of the process can be written to a file for later recovery. A checkpoint contains not only the memory image, but also the resource state. A more effective solution is not to overwrite the original checkpoint, but to write it to a file every time a checkpoint occurs, so that when the process executes, a series of checkpoint files will be accumulated.
In order to recover, it is necessary to start from the last earlier checkpoint, so that the process that needs resources will be rolled back to the previous point in time. At this point in time, the deadlocked process has not obtained the required resources. At this point, resources are allocated to it.
kill process recovery
The simplest and most effective solution is to kill a deadlocked process directly. But killing a process may still not work, and you need to kill other resources to recover.
Another way is to choose an out-of-ring process as a victim to free process resources.
deadlock avoidance
What we discussed above is how to detect deadlocks and how to recover from deadlocks. Let’s discuss several ways to avoid deadlocks.
Banker’s Algorithm for a Single Resource
Banker’s algorithm is a scheduling algorithm proposed by Dijkstra in 1965, which itself is a deadlock scheduling algorithm. Its model is based on a banker in a town who promises a certain number of loan lines to customers in the town. All the algorithm has to do is determine whether the request will enter an unsafe state. If so, reject the request, and accept the request if the system is secure after the request.
break deadlock
Deadlock is inherently unavoidable because it needs to acquire unknown resources and requests, but deadlock occurs after four conditions are met, which are
mutually exclusive
hold and wait
Not preemptible
circular wait
We discuss these four conditions separately, and it stands to reason that breaking any one of them can break the deadlock
break the mutually exclusive condition
Our first consideration is breaking the mutex use condition. If the resource is not monopolized by a process, then deadlock will definitely not occur. If two printers use a resource at the same time, it can cause confusion. The solution for printers is to use spooling printers. This technique allows multiple processes to produce output at the same time. In this model, the only person who actually requests the printer is The process is the printer daemon, also known as the background process. Background processes do not request other resources. We can eliminate the deadlock of the printer.
Background processes are usually written to output the complete file before printing, which can lead to deadlock if both processes take up half of the spool space and neither process completes the full output.
Therefore, try to make as few processes as possible request resources.
break the condition that keeps waiting
The second way is that if we can prevent the process holding the resource from requesting other resources, we can eliminate the deadlock. One way to do this is to have all processes request all resources before they start executing. If the required resources are available, the process completes the allocation of resources and runs to completion. If any of the resources are frequently allocated, the processes that are not allocated the resource will wait.
Many processes cannot know exactly how many resources they need before execution is complete, and if they do, they can use the banker’s algorithm; another problem is that this does not make reasonable and efficient use of resources.
Another way is that when the process requests other resources, it first releases the occupied resources, and then tries to obtain all the resources at once.
break non-preemptive condition
It is also possible to break the non-preemptive condition. This can be avoided by means of virtualization.
Break the loop wait condition
Now there is one last condition left, and the circular wait condition can be broken in a number of ways. One way is to establish a standard that only one resource can be used by a process at any time. If another resource is needed, the current resource must be released. This limitation is unacceptable for processes that require copying large files from tape to printer.
Processes can make requests at any time, but all requests must be made in the order of resources. If this allocation rule is followed, there will be no loops between resource allocations.
Although deadlocks are eliminated in this way, the numbering sequence cannot be accepted by every process.
other problems
Let’s discuss other issues, including communication deadlock, what is livelock, starvation problem, and two-phase locking
two-stage locking
Although deadlock avoidance and prevention can be handled in many cases, the effect is not good. Over time, many excellent algorithms have been proposed to deal with deadlocks. For example in database systems, a common operation is to request to lock some records and then update all locked records. When there are multiple processes running at the same time, there is a risk of deadlock.
One solution is to use two-phase locking. As the name suggests, there are two phases, one where the process tries to lock all the records it needs at once. If it is successful, the second phase will start, and the second phase is to perform the update and release the lock. The first stage doesn’t do really meaningful work.
If a record needed by a process is already locked during the first phase, the process releases all locked records and starts the first phase again. In a sense, this approach is similar to pre-requesting all required resources or requesting all resources before doing some irreversible operation.
However, in general application scenarios, the two-stage locking strategy is not universal. It is unacceptable that a process is interrupted halfway and restarted if it lacks resources.
communication deadlock
What we have been discussing above is resource deadlock. Resource deadlock is a type of deadlock, but it is not the only type. There is also communication deadlock, which is a deadlock that occurs when two or more processes send messages. Process A sends a message to process B, then process A blocks until process B returns a response. Assuming that the request message is lost, then process A is waiting for a reply, and process B will also block waiting for the request message to arrive, and a deadlock occurs at this time.
Although a deadlock occurs, it is not a resource deadlock because A does not occupy B’s resources. In fact, there are no fully visible resources for communication deadlocks. According to the definition of deadlock: each process blocks because it waits for events caused by other processes, which is a kind of deadlock. Compared to the most common communication deadlock, we call the above situation a communication deadlock.
Communication deadlock cannot be avoided by scheduling, but it can be avoided by using a very important concept in communication: timeout. In the communication process, as long as a message is sent, the sender will start a timer, and the timer will record the timeout period of the message. If the timeout period expires but the message has not been returned, the message will be considered lost and resent. In this way, communication deadlocks can be avoided.
However, not all deadlocks in network communication are communication deadlocks, and resource deadlocks also exist. The following is a typical resource deadlock.
When a packet enters a router from a host, it is put into a buffer, then transmitted to another router, to another, and so on until its destination. Buffers are resources and are limited in number.Each router has 10 buffers (there are actually many).
If deadlock is infatuated, then livelock is self-defeating with an idiom.
In some cases, when a process realizes that it cannot acquire the next lock it needs, it will try to politely release the lock it has already acquired, and then wait a very short time to try to acquire it again. Imagine this scene: when two people meet on a narrow road, they both want to give way to each other, and the same pace will prevent both parties from moving forward.
Now imagine a pair of parallel processes using two resources. After their respective attempts to acquire another lock fail, both processes will release the locks they hold, try again, and the process will repeat. Obviously, no process is blocked in this process, but the process still does not execute downwards, which is called livelock.
hunger
A very similar problem to deadlock and livelock is starvvation. Imagine when you will be hungry? Do you feel hungry if you don’t eat for a while? For processes, the most important thing is resources. If resources are not obtained for a period of time, the processes will be starved, and these processes will never be served.
We assume that the allocation scheme of the printer is that it will be allocated to the process with the smallest file every time, then the process that wants to print the large file will never be served, causing the process to starve, and the process will be pushed back indefinitely, although it does not block.
Summarize
Deadlocks are a general class of problems that can occur in any operating system. A deadlock occurs when each process in each group of processes is blocked waiting for a resource occupied by other processes in the group. This situation will put all processes in an infinite wait state.
The detection and avoidance of deadlock can be judged by the safe and unsafe state. One of the detection methods is the banker’s algorithm; of course, you can also use the ostrich algorithm to ignore the deadlock, but you will definitely be attacked by it.
It is also possible to avoid deadlock from the perspective of system structure during design, which can prevent deadlock; it can also destroy the four conditions of deadlock to destroy deadlock. Resource deadlocks are not unique deadlocks, but also inter-communication deadlocks, which can be accomplished by setting an appropriate timeout.
The problems of livelock and deadlock are somewhat similar, they are both a state in which a process cannot continue to execute downwards. Process starvation occurs when the party trying to acquire the process can never get the resource due to the process scheduling policy.