What is a deadlock

Multithreading and multi-process improve the utilization of system resources and improve the processing capacity of the system. However, concurrent execution also introduces a new problem – deadlocks.

A deadlock is a deadlock (Deadly Embrace) in which two or more processes (threads) compete for resources while running, and none of them can move forward without an external force.

Here are some examples to illustrate the deadlock phenomenon.

First look at an example of life, two people eat together but only one pair of chopsticks, two people take turns to eat (have two chopsticks at the same time can eat).

Took the left one, a chopsticks, one person took the chopsticks right, both occupy a resource at the same time, waiting for another resource, this time a waiting for b finish and release it occupies the chopsticks, in the same way, b is waiting for a finish and release it occupies the chopsticks, so you into an infinite loop, who also can’t continue to eat…

A similar situation exists in computer systems. For example, a computer system has only one printer and one input device. Process P1 is occupying the input device and requests to use the printer. Process P2 is occupying the printer and requests to use the input device occupied by process P1 before releasing the printer.

So the two processes wait endlessly for each other, neither of them can continue to execute, and the two processes become deadlocked.

Some conclusions about deadlocks:

  • The number of processes involved in a deadlock must be at least two

  • All processes participating in a deadlock wait for resources

  • At least two processes participating in the deadlock already have resources

  • A deadlocked process is a subset of the current set of processes in the system

  • Deadlocks can waste a lot of system resources and even cause system crashes.

Deadlock and hunger

Starvation refers to the time when resources are not available to a process.

Deadlocks and starvation are both caused by processes competing for resources. Hunger generally does not possess resources, deadlock processes must possess resources.

Third, the type of resources

Reusable and consumable resources

Reusable resources (persistent resources)

Can be used multiple times by multiple processes, such as all hardware.

  • It can be allocated to only one process and cannot be shared by multiple processes.

  • When a process uses reusable resources, it must request, use, and release them in such a sequence.

  • The number of units in each type of reusable resource in the system is relatively fixed, and the process can neither be created nor deleted while running.

Expendable resources (temporary resources)

  • Also known as temporary resources, they are dynamically created and consumed by processes during runtime.

  • Consumable resources can vary over the course of a process and can sometimes be zero.

  • As a process runs, it can continuously create units of expendable resources and put them into the buffer of that resource class to increase the number of units of that resource class.

  • While a process is running, it can request several units of expendable resources to be consumed by the process itself without returning them to the resource class.

Consumable resources are typically created by producer processes and consumed by consumer processes. The most typical consumable resource is the message used for interprocess communication.

Preemble resources and non-preemble resources

Preemptable resource

Preemble resources refer to resources that can be preempted by other processes or systems after a process obtains them. Deadlocks are not caused for such resources.

CPU and main memory are preemptive resources.

Do not preempt resources

Once a resource is allocated to a process, it cannot be forcibly reclaimed. It can only be released when the process is used up.

Tape drives and printers are non-preemptive resources.

4. Causes of deadlock

  • Contention does not preempt resources causing deadlocks

  • In general, the amount of non-preemptable resources in the system is insufficient to meet the requirements of multiple processes. As a result, processes are locked in the process of competing for resources, such as tape drives and printers. Only competition for non-preemble resources can cause deadlocks, but competition for preemble resources does not cause deadlocks.

  • Contention consumes resources and causes deadlocks

  • Improper progression of processes causes a deadlock

  • When a process is running, requesting and releasing resources in the wrong order can also cause deadlocks. For example, concurrent processes P1 and P2 hold resources R1 and R2, respectively. When process P1 applies for resource R2, and process P2 applies for resource R1, both processes are blocked because required resources are occupied.

  • Improper use of semaphores can also cause deadlocks. Processes waiting for messages from each other can also make it impossible for those processes to move forward. For example, process A waits for the message sent by process B, and process B waits for the message sent by process A. In this case, processes A and B are not competing for the same resource, but are waiting for each other’s resources, resulting in A deadlock.

Contention does not preempt resources causing deadlocks

For example, file sharing causes a deadlock

The system has two processes, P1 and P2, each preparing to write two files, F1 and F2. Both are reusable and non-preemptive resources.

If P1 opens F1 at the same time as P2 opens F2, when P1 wants to open F2, it will be blocked because F2 is occupied, and when P2 wants to open 1, it will be blocked because F1 is occupied.

Contention consumes resources and causes deadlocks

For example, deadlocks occur during process communication

There are three processes P1, P2, and P3 in the system. M1, M2, and M3 are three consumable resources. Process P1 produces message M1, sends it to P2, and receives message M3 from P3.

Process P2 generates message M2, sends it to P3, and receives message M1 from P1. Similarly, process P3 generates message M3 on the one hand, sends it to P1, and receives message M2 from P2 on the other.

If all three processes first send messages generated by themselves and then receive messages sent by others, they can run smoothly without generating deadlocks. However, if all three processes receive messages from others first and do not generate messages, they will wait forever and generate deadlocks.

Improper progression of processes causes a deadlock

In the figure above, the two processes can be completed smoothly if the progression follows the sequence of curve 1. If we proceed in the order of curve 2, both processes can be completed smoothly.

If the sequence of curve 3 is followed, the two processes can be successfully completed. If the two processes advance according to the sequence of curve 4, they will enter the insecure zone D. At this time, P1 retains resource R1 and P2 retains resource R2, and the system is in an insecure state. If it continues to advance, deadlock may occur.

Four necessary conditions for deadlock

1 Mutually exclusive Conditions:

Processes require exclusive control over allocated resources (such as printers), that is, a resource is owned by only one process at a time. If another process requests the resource, the requesting process can only wait.

2 inalienable Conditions:

A resource acquired by a process cannot be seized by another process before it is fully used, that is, it can only be released by the process that acquired the resource itself (only on its own initiative).

3 Request and Hold Conditions:

A process that has retained at least one resource makes a request for a new resource that has already been occupied by another process. The requesting process is blocked but does not release the resource that it has acquired.

4. Cyclic waiting conditions:

There is a circular waiting chain of process resources in which each process has acquired resources that are also requested by the next process in the chain. That is, there is a set of processes {Pl, P2… , pn}, where resources such as Pi are occupied by P(I +1) (I =0, 1… , n-1), resources waiting for Pn are occupied by P0, as shown in Figure 2-15.

While the circular wait condition may seem intuitively the same as the definition of a deadlock, it is not. According to the definition of deadlock, the waiting loop requires a stricter condition, which requires that the resources waiting for Pi must be satisfied by P(I +1), while the circular waiting condition has no such restriction. For example, there are two output devices in the system, P0 occupies one, PK occupies the other, and K does not belong to the set {0, 1… , n}.

The Pn waits for an output device, which can be obtained from P0 or possibly from PK. Therefore, Pn, P0, and other processes form a circular waiting circle, but PK is not in the circle. If PK releases the output device, the circular waiting can be broken, as shown in Figure 2-16. So circular waiting is only a necessary condition for deadlocks.

The reason why the resource allocation graph contains circles and the system does not necessarily have deadlocks is that the number of similar resources is greater than 1. However, if there is only one resource for each type of resource in the system, the resource allocation graph circle becomes a necessary and sufficient condition for the system to have deadlock.

These four conditions are necessary for deadlocks, and they must be true whenever a deadlock occurs on the system, and no deadlock occurs unless one of these conditions is met.

Methods to handle deadlocks

  • Deadlock prevention: Prevent deadlocks by setting restrictions that break one or more of the four necessary conditions for causing deadlocks.

  • Deadlock avoidance: In the process of dynamic resource allocation, some method is used to prevent the system from entering an insecure state, so as to avoid the occurrence of deadlock.

  • Deadlock detection: The system is allowed to issue life-and-death locks during operation, but the detection mechanism can be set up to detect the occurrence of deadlocks in time and take appropriate measures to remove them.

  • Deadlock relief: When a deadlock is detected, appropriate action is taken to free the process from the deadlock state.

6.1 Preventing deadlocks

1. Breaking “mutually exclusive” conditions:

To break the mutual exclusion condition is to remove the mutual exclusion from the system. If the resource is not exclusively used by a process, deadlock is definitely not possible. But generally of the four conditions listed, the “mutually exclusive” condition is unbreakable. Therefore, deadlock prevention focuses on breaking several other necessary conditions, and does not involve breaking “mutually exclusive” conditions.

Note: Mutual exclusion conditions cannot be broken, otherwise the result will be non-reproducible.

2. Break the “possess and wait” condition:

Breaking a “hold and wait” condition means that a process in the system is not allowed to apply for a resource that has already been acquired. Figure out a way to prevent a process from holding resources while applying for other resources.

Method one: When creating a process, ask it to request all the resources it needs, and the system either meets all of its requirements or gives it nothing. This is known as a “lump sum allocation” scheme.

Method two: Require each process to release the resources it occupies before making a new resource request. Thus, when a process needs resource S, it must release the resource R it previously occupied before it can make a claim on resource S, even though it may need resource R again soon.

3. Breaking the “Do not Preempt” condition:

Breaking the “non-preemption” condition allows a resource to be grabbed.

Method 1: If a process holding certain resources is denied further resource requests, the process must release the resources it originally held and, if necessary, request these resources and additional resources again.

Method 2: If a process requests a resource currently occupied by another process, the operating system can preempt the other process and ask it to release the resource. Method 2 can prevent deadlocks only if any two processes have different priorities.

4. Break the “loop wait” condition:

One way to break the “circular wait” condition is to uniformly number all resources in the system. A process can request resources at any time, but all requests must be made in ascending order. This ensures that the system does not deadlock.

6.2 Avoiding deadlocks

Understanding the causes of deadlocks, especially the four necessary conditions for deadlocks, can best avoid, prevent, and remove deadlocks.

Therefore, in the system design, process scheduling and other aspects to pay attention to how to make these four necessary conditions are not established, how to determine the reasonable allocation of resources algorithm, to avoid process permanent occupation of system resources.

Also, prevent processes from taking up resources while they are in a wait state. Therefore, the allocation of resources should be given reasonable planning.

The difference between deadlock prevention and deadlock avoidance:

Deadlock prevention is an attempt to break at least one of the four necessary conditions that produce deadlocks, strictly preventing the occurrence of deadlocks, while deadlock avoidance is less strictly limiting the existence of the necessary conditions that produce deadlocks, because even if the necessary conditions for deadlocks exist, they do not necessarily occur. Deadlock avoidance is to avoid the eventual occurrence of deadlocks during system operation.

A common way to avoid deadlocks

Orderly resource allocation method

These algorithmic resources are uniformly numbered according to all resources in a regular system (e.g., printer 1, tape drive 2, disk 3, etc.) and must be applied in ascending order.

Application process:

1. All resources that it must use and belong to the same category must be applied for at one time;

2. When applying for different types of resources, you must apply according to the serial number of each type of equipment. For example, PA uses resources in the sequence R1 and R2. Process PB uses resources in the order of R2 and R1. If dynamic allocation is used, loop conditions may be formed, resulting in deadlock.

Orderly resource allocation method is adopted: R1 is numbered 1, R2 is numbered 2.

PA: The application sequence should be R1 and R2

PB: The application sequence should be R1 and R2

This breaks the loop condition and avoids deadlocks.

Deadlock avoidance techniques are commonly used

1 Lock order (threads lock in a certain order)

Deadlocks can easily occur when multiple threads need the same locks but lock them in different order.

If you can ensure that all threads acquire locks in the same order, deadlocks will not occur.

If a thread (such as thread 3) needs some locks, it must acquire them in a certain order. It can acquire the next lock only after it has acquired the first lock in the order.

For example, thread 2 and thread 3 can only attempt to acquire lock C after they have acquired lock A. Because thread 1 already owns lock A, threads 2 and 3 need to wait until lock A is released. They must then successfully lock A before they can attempt to lock B or C.

Sequential locking is an effective deadlock prevention mechanism. This method, however, requires you to know all the locks you might need in advance (and prioritize them appropriately), but sometimes it’s unpredictable.

2 Lock time limit (when a thread tries to acquire a lock, it adds a certain time limit, after which it will give up the request for the lock and release the lock it owns)

Another way to avoid deadlocks is to add a timeout period to the attempt to acquire the lock. This means that the thread will abandon the lock request if the timeout period is exceeded during the attempt to acquire the lock.

If a thread does not successfully acquire all the required locks within a given time, it will fall back and release all acquired locks, then wait a random amount of time and try again. This random waiting time gives other threads the opportunity to try to acquire the same locks and allows the application to continue running if it does not

Note: after the lock timeout, you can continue to run other things, and then go back to repeat the previous lock logic).

3 Deadlock detection

Deadlock detection is a better mechanism for deadlock prevention, mainly for situations where sequential locking is not possible and lock timeouts are not feasible.

Each time a thread acquires a lock, it is recorded in the thread and lock associated data structures (map, graph, and so on). In addition, every time a thread requests a lock, it needs to be logged in this data structure.

When a thread fails to request a lock, the thread can traverse the lock graph to see if a deadlock has occurred.

For example, if thread A requests lock 7, but lock 7 is held by thread B, thread A can check to see if thread B has requested the lock currently held by thread A. If thread B does have such A request, then A deadlock has occurred (thread A owns lock 1 and requests lock 7; Thread B owns lock 7 and requests lock 1.

Of course, deadlocks are generally more complicated than two threads holding each other’s locks. Thread A waits for thread B, thread B waits for thread C, thread C waits for thread D, and thread D waits for thread A. To detect deadlocks, thread A needs to progressively detect all locks requested by THREAD B. Starting with the lock requested by thread B, thread A finds thread C, and then finds thread D, discovering that the lock requested by thread D is held by thread A itself. That’s when it knows a deadlock has occurred.

Below is A graph of lock possession and request between four threads (A,B,C, and D). Data structures like this can be used to detect deadlocks.

6.3 Detecting deadlocks

Generally speaking, due to the concurrency, sharing, and randomness of operating systems, it is difficult to eliminate deadlocks by means of prevention and avoidance. This requires significant system overhead and does not fully utilize resources.

An easy way to do this is for the system to allocate resources to processes without any restrictive measures, but to provide a means to detect and release deadlocks: deadlocks can be found and recovered from the deadlock state. Therefore, deadlock detection and recovery methods are often used to eliminate deadlocks in actual operating systems.

Deadlock detection and recovery refers to the system has a special mechanism, when the deadlock occurs, the mechanism can detect the location and cause of the deadlock, and can destroy the necessary conditions of the deadlock through external force, so that the concurrent process from the deadlock state recovery.

At this time, process P1 occupies resource R1 and applies for resource R2; process P2 occupies resource R2 and applies for resource R1. According to the waiting conditions, process and resource form a loop, so the system is in deadlock state. Process P1, P2 is the process participating in the deadlock.

Let’s take a look at the deadlock detection algorithm. The data structure used by the algorithm is as follows: Possession matrix A: n*m rank, where N represents the number of concurrent processes and M represents the number of various resources in the system. This matrix records the number of resources currently occupied by each process in each resource class.

Application matrix R: n*m, where N represents the number of concurrent processes and M represents the number of various resources in the system. This matrix records the number of resources in each resource class that each process needs to apply for to complete its work. Idle vector T: Records the number of idle resources in m resource classes.

Completion vector F: Boolean vector-value is true (true) or false (false), records whether the current N concurrent processes can be completed. If it is true, it can finish; if it is false, it cannot finish.

The temporary vector W: starts with W: =T. Algorithm steps: (1) W: =T, for all I =1, 2… If A[I]=0 then F[I] : =true; Otherwise, F[I] : =false

(2) Find the subscript I: F[I] : =false and R[I] < =W if there is no subscript I that satisfies the above condition I, go to step (4).

(3) W: =W+A[I] F[I] : =true

(4) If there is I, F[I] : =false, the system is in a deadlock state and the Pi process participates in the deadlock. When deadlock detection is performed depends on how often deadlocks occur. If deadlocks occur frequently, the frequency of deadlock detection should be increased accordingly. In this way, on the one hand, the utilization of system resources can be improved, on the other hand, more processes can be prevented from being involved in deadlocks. If the process can not meet the resource requirements, it can be detected every time the deadlock is formed, which is similar to the deadlock avoidance algorithm, but the system costs a lot.

To reduce the system overhead caused by deadlock detection, deadlock detection is performed at intervals or when the CPU usage decreases to a certain value.

6.4 Unlocking a deadlock

Once a deadlock is detected, measures should be taken immediately to remove the deadlock.

The main ways to unlock deadlocks are:

**1) Resource deprivation law. ** Suspends some deadlocked process, preempts its resources, and allocates those resources to other deadlocked processes. However, pending processes should be prevented from being starved of resources for an extended period of time.

**2) Undo process method ** Forces some or all of the deadlocked processes to be revoked and deprived of their resources. The principle of revocation can be carried out according to the process priority and the cost of revocation.

**3) Process rollback method. ** Causes one (more) process to fall back enough to avoid a deadlock, and the process falls back voluntarily releasing resources rather than being stripped. The system is required to retain historical process information and set the restore point.

Pay attention and don’t get lost

All right, everybody, that’s all for this article. All the people here are talented. As I said before, there are many technical points in PHP, because there are too many, it is really difficult to write, you will not read too much after writing, so I have compiled it into PDF and document, if necessary

Click on the code: PHP+ “platform”

As long as you can guarantee your salary to rise a step (constantly updated)

I hope the above content can help you. Many PHPer will encounter some problems and bottlenecks when they are advanced, and they have no sense of direction when writing too many business codes. I have sorted out some information, including but not limited to: Distributed architecture, high scalability, high performance, high concurrency, server performance tuning, TP6, Laravel, YII2, Redis, Swoole, Swoft, Kafka, Mysql optimization, shell scripting, Docker, microservices, Nginx, etc