Interview Talk-Four Major Conditions and Treatment Strategies of Deadlock

Interview Talk-4.Major Conditions and Treatment Strategies of Deadlock

Deadlock refers to a blocking phenomenon caused by competition for resources or due to communication with each other during the execution of two or more processes. If there is no external force, they will not be able to advance. At this time, the system is said to be in a deadlock state or the system has a deadlock. These processes that are always waiting for each other are called deadlock processes.

For example: Two threads A and B each hold a resource that cannot be shared, and both of them need to acquire the resource currently held by the other party before they can proceed to the next step, but they must wait for the other party to release before they can obtain it, so A waits for B, B is also waiting for A. In this way, a deadlock occurs.

4.conditions for deadlock

The occurrence of deadlock must meet the following four necessary conditions

Mutual exclusion

Resources cannot be shared and can only be used by one process.

Request and hold conditions (Hold and wait)

Processes that have already obtained resources can apply for new resources again.

No pre-emption

The allocated resources cannot be forcibly deprived from the corresponding process.

Loop/Circular wait condition (Circular wait)

Several processes in the system form a loop, and each process in the loop is waiting for the resources that neighboring processes are occupying.

Let's take a look at the beginning example after understanding the four necessary conditions:

Two threads each hold a resource that cannot be shared (mutual exclusion conditions), and they both need to obtain (request and hold conditions) the resources currently held by the other to proceed to the next step, but they must wait for the other to release before they can obtain it. (Inalienable condition), so A is waiting for B, and B is also waiting for A (loop waiting condition). In this way, a deadlock occurs.

Prevent deadlock

By destroying one or more of the four necessary conditions, the deadlock can never be satisfied. The implementation is simple, but because the imposed constraints are often too strict, it may lead to a decrease in system resource utilization and system throughput.

Pre-resource allocation

Apply for all required resources at once. As long as one resource does not meet the requirements, even if the other required resources are sufficient, no allocation will be made. In this way, there is no "reserved" resource state, only the "requested" resource state, which destroys the request and retention conditions.

Orderly resource allocation

When applying for different types of resources, they must apply in the specified order, which breaks the loop waiting conditions.

  • Positive example: Threads A and B apply for resources in the order of R1->R2;
  • Counter-example: A's application sequence is R1->R2, and B's application sequence is R2->R1.

Avoid deadlock

It is also a pre-deadlock, but it will not destroy the necessary conditions of the deadlock in advance. It is just that when someone requests a resource, some method is used to prevent the system from entering an insecure state (deadlock), thereby avoiding a deadlock.

Banker's algorithm

The basic idea is to judge whether the system is safe before allocating resources; if so, only allocate them.

Deadlock detection and release

No measures are taken to prevent deadlocks, allowing the system to generate deadlocks, but the deadlocks can be detected by some means, and then the deadlocks can be removed.

Detection method:

  1. Timing detection
  2. Detection when efficiency is low
  3. Detect while the process is waiting

Method to remove deadlock:

According to specific business scenarios, deadlocked processes/threads can be revoked or suspended to release resources.