Causes and treatment strategies of operating system deadlock

Deadlock may occur when a process needs to access a resource in an exclusive manner. Deadlock refers to a deadlock caused by two or more processes competing for critical resources, that is, one process is waiting for a resource that has been occupied and will never be released. Without external forces, these processes cannot move forward.

The root cause of deadlock is that the number of resources that the system can provide is less than the number of processes that require the resources.

The basic causes of deadlock can be divided into two categories: resource competition and unreasonable process advancement order.

In the resource competition scenario, the resources owned by the system are limited and cannot meet the needs of each process.

example:

A has paper, B has a pen

A: If you don’t give me a pen, I can’t do my homework.

B: If you don’t give me paper, I can’t do my homework.

The two are in a stalemate...

When multiple programs are running at the same time, the order of process advancement is unreasonable .

example:

A needs to take 2 steps forward, reach the table, and then take 2 steps back.

But if the execution order is unreasonable: A retreats first, it will never reach the table, and subsequent actions cannot be triggered, which will lead to a deadlock.

There are four necessary conditions for a deadlock to occur:

• Mutually exclusive conditions
  The resources involved are non-shared, that is, only one process can use them at a time. If another process requests the resource, the requesting process must wait until the resource is released.
• Non-preemptive conditions (non-preemptive)
  The resources obtained by a process cannot be forcibly taken away by other processes before they are used up. That is, they can only be released by the process that obtains the resources.
• Hold and wait (partial allocation)
  The process requests a portion of the resources it needs each time. While waiting for new resources, the process continues to occupy the allocated resources.
• Loop condition (loop wait)
  There is a circular chain of processes that end one after another, and each process in the chain is waiting for the resources held by the next process, causing this group of processes to be in a state of eternal waiting.

There are generally three strategies for dealing with deadlock: deadlock prevention, deadlock avoidance, and deadlock detection and resolution.

• Deadlock Prevention

• Avoiding Deadlock

This method also belongs to advance prevention, but it does not take various restrictive measures in advance to destroy the four necessary conditions for deadlock. Instead, in the process of dynamic resource allocation, it uses some algorithms to prevent the system from entering an unsafe state and avoid the occurrence of deadlock.

The specific strategies are as follows:

1. If the resources requested by the process will cause deadlock, the system refuses to start the process;

2. If the allocation of a resource will lead to a deadlock in the next step, the system will reject the allocation;

Obviously, to avoid deadlock, the system must know in advance the number of resources it has and their properties.

A well-known deadlock-avoiding algorithm is the Banker's algorithm .

The banker's algorithm was proposed by DijkstraE W in 1968. It is called the banker's algorithm because it can be used in the banking system.

The so-called banker's algorithm means that before allocating resources, it is determined whether the resource allocation will cause the system to deadlock. If it will deadlock, it will not be allocated. Only after it is confirmed that it will not deadlock, it will be allocated.

The banker's algorithm needs to determine whether to allocate resources according to the following principles:

• When a new process enters the system, it must state the maximum demand for various resources, which cannot exceed the total number of system resources. Only when this condition is met will the system accept the process.

• When a process applies for a set of resources, the algorithm needs to check the maximum demand of the process for each type of resource. If the existing number of resources in the system can meet the maximum demand for resources at this time, the resources will be allocated; otherwise, the process must wait until other processes release enough resources.
• The process needs to unconditionally return all the resources it has requested within a certain period of time.

• Deadlock detection and resolution

  Deadlock prevention and avoidance both impose appropriate restrictions on resource allocation, which are advance measures and are not conducive to the full sharing of system resources. Deadlock detection does not attempt to prevent deadlocks, that is, it does not perform any operations before deadlocks occur. It only detects whether deadlocks occur at present through the set detection mechanism. If deadlocks occur, some measures are taken to resolve the deadlocks.

  The rules for determining deadlock are mainly based on the fourth necessary condition for deadlock:

• There is no loop in the resource allocation path, so the system will not deadlock.

• If there is a loop in the resource allocation path, the system may deadlock.
• If there is only one resource in each data class in the loop, the system will be deadlocked.
• If there is more than one resource of each resource class in the loop, the existence of the loop is a necessary but not sufficient condition for deadlock.

• Resource Deprivation Law

• Process Undo Method

• Cancel all processes that are deadlocked at one time, reclaim all occupied resources, and rerun the processes after the deadlock is resolved.

• The deadlocked processes are canceled one by one, and their resources are recovered and reallocated in turn until the deadlock is resolved. The processes with low priority, longest estimated remaining execution time, and low CPU consumption time can be canceled first.

• Process rollback method

Let all processes roll back to the checkpoint saved by the system. This method requires the system to establish and save checkpoints and establish a rollback mechanism.

• System Restart Method
  End all processes and reboot the system. This method is simple, but it is very lossy and all previous work may be wasted.