Causes and Necessary Conditions of Deadlock

Definitions Related to Deadlock

Permanent (reusable) resources

• Preemptible resources: after a process acquires such a resource, it can be taken away by another process or the system
• Non-preemptible resources: once the system assigns such a resource to a process, it cannot be forcibly reclaimed; the process must release it on its own after use. Temporary (consumable) resources
• Resources that can be used only once

Deadlock: a set of processes is deadlocked if every process in the set is waiting for an event that can only be triggered by another process in the same set.

• Deadlock prevents processes from making progress
• Deadlock wastes system resources enormously (the resources cannot be released)

Causes of deadlock

• Competition for resources
• Improper ordering of process progress

Necessary conditions for deadlock

1. Mutual exclusion: a process uses its allocated resources exclusively
2. Hold and wait: a process already holds at least one resource but requests a new one that is held by another process; the requesting process blocks while keeping the resources it already holds
3. No preemption: resources a process has acquired cannot be taken away before it finishes with them; the process releases them only when it is done
4. Circular wait: when deadlock occurs, there must exist a circular chain of processes and resources

Resource Allocation Graph

A Resource Allocation Graph (RAG) describes the relationships between processes and resources, as well as the competition among resources. It is a directed graph showing system resources and process states, where each resource and each process is a node, and a dot represents one instance of a resource; a resource may have multiple instances.

1. Deadlock caused by competing for non-preemptible resources

3. Deadlock caused by improper process progress ordering
A Joint Progress Diagram records the execution progress of multiple processes sharing resources.

Competing for resources does not necessarily produce deadlock. Whether deadlock occurs also depends on dynamic execution and application details.

P: request A, request B, release A, release BQ: request B, request A, release B, release A

Methods of Deadlock Prevention

1. Deadlock Prevention: impose restrictions that break one or more of the four necessary conditions.
   Pros: easy to implement.
   Cons: reduces resource utilization and system throughput.
2. Deadlock Avoidance: during dynamic resource allocation, use some method to keep the system out of unsafe states.
   Pros: weaker constraints yield higher resource utilization and throughput.
   Cons: somewhat difficult to implement.
   Two approaches to deadlock avoidance:
   • If starting a process would lead to deadlock, do not start it
   • If granting an additional resource request would lead to deadlock, do not allow the allocation
3. Deadlock Detection: impose no restrictions in advance and do not check whether the system has entered an unsafe region; instead, set up a detection mechanism and resolve deadlock once detected.
4. Unlocking deadlock: commonly by terminating or suspending some processes and reclaiming some resources.

Deadlock prevention and deadlock avoidance are two different concepts. Both guard against deadlock in advance, but by different means.
Prevention considers the possibility of deadlock at system design time and takes measures to rule it out, whereas avoidance takes measures at runtime, based on the system’s state, to keep deadlock from happening.

Deadlock prevention: break the necessary conditions of deadlock; the constraints are rather strict and may hurt process concurrency.
Deadlock avoidance: allocate resources dynamically; the constraints are weaker, which is better for process concurrency.

Breaking the Hold-and-Wait Condition

First protocol: the system requires every process to request all the resources it needs at once. If any one resource request cannot be satisfied, none of the resources — including those otherwise available — are allocated to the process, and it must wait.

• Pros: simple, easy to implement, and very safe.
• Cons: serious resource waste; delayed process execution.

Second protocol: a process may start running once it has acquired only the resources needed for its initial phase. As it runs, it gradually releases the resources it has been allocated and finished using, then requests the new resources it needs.
Pros: lets processes finish faster, improves device utilization, and reduces the chance of starvation.

Breaking the No-Preemption Condition

A process requests resources only when it needs them. When a process that already holds some resources makes a new request that cannot be satisfied immediately, it must release all the resources it holds and re-request them later when needed.
Cons: complex and costly to implement; lengthens process turnaround time, increases system overhead, and lowers throughput.

Breaking the Circular-Wait Condition

The system orders all resources linearly by type (from frequently used to rarely used) and assigns each a distinct number. All processes must request resources strictly in increasing order of resource number and release them in decreasing order.

Suppose our system has three resources: A, B, and C. We rank them by usage frequency, obtaining the sequence A (most used) -> B -> C (least used). Then we assign each resource a number: A=1, B=2, C=3.
Under this policy, every process must request resources in increasing order of resource number and release them in decreasing order.

Methods of Deadlock Avoidance

Safe state: the system can allocate resources to each process in some order 〈P1, P2, …, Pn〉, satisfying each process’s maximum resource demand so that every process can run to completion; such an order is called a safe sequence. The essence of a safe sequence is that for each process Pi in the sequence, the resources it still needs to finish do not exceed the sum of the system’s currently remaining resources and the resources held by all processes before it, P1, P2, …, Pi-1.
If no such safe sequence exists, the system is in an unsafe state.

• Not every unsafe state is a deadlock state, but once the system enters an unsafe state, it may proceed into deadlock.
• When the system is in a safe state, it will not enter a deadlock state.

Deadlock avoidance does not predict deadlock precisely; it merely anticipates the possibility of deadlock and ensures that possibility never materializes.
Deadlock avoidance is less restrictive than deadlock prevention, but it still has many constraints in practice:

• Each process must declare its maximum resource demand in advance.
• The processes under consideration must be independent, with no synchronization requirements on their execution order.
• The number of resources to allocate must be fixed.
• A process cannot exit while holding resources.

🌟 The Banker’s Algorithm: A Deadlock Avoidance Strategy

Banker’s Alogorithm

Basic Idea of the Banker’s Algorithm

The key to avoiding deadlock is accurately predicting whether deadlock will occur, and thereby avoiding it. The most representative deadlock avoidance algorithm is the Banker’s Algorithm, proposed by Dijkstra in 1965. It can be used by a bank, before issuing a loan, to predict whether that loan would cause cash-flow problems.
The bank’s funds are analogous to a computer system’s resources, and loan transactions are analogous to resource allocation. Just as the Banker’s Algorithm can predict whether a loan is safe for the bank, it can predict whether a resource allocation is safe for the system.

1. In the current state, some process requests resources;
2. The system tentatively allocates the resources to that process, satisfying its request;
3. It checks whether the resulting system state is safe. If safe, the allocation is confirmed; if unsafe, the allocation is rolled back and the process is blocked (this step is also called the safety algorithm).

Data Structures of the Banker’s Algorithm

To implement the Banker’s Algorithm, the system must maintain several data structures:

1. Available resource vector Available: an array with m elements, each representing the number of available resources of one class. Its initial value is the total number of resources of that class configured in the system, and it changes dynamically as resources are allocated and reclaimed. If Available[j]= K, the system currently has K resources of class .

2. Maximum demand matrix Max: an n×m matrix defining the maximum demand of each of the n processes for each of the m resource classes. If Max[i,j]=K, process i’s maximum demand for class resources is K.

3. Allocation matrix Allocation: also an n×m matrix, defining how many resources of each class are currently allocated to each process. If Allocation[i,j]=K, process i currently holds K resources of class .

4. Need matrix Need: also an n×m matrix, representing how many resources of each class each process still needs. If Need[i,j]=K, process i still needs K more resources of class to complete its task.

   Let be the request vector of process ; means process needs K resources of type . When Pi issues a resource request, the system checks it as follows:
   (1) If , go to step 2; otherwise it is an error, because the process is requesting more resources than it declared it needs.
   (2) If , go to step (3); otherwise there are not enough resources and Pi must wait.
   (3) The system tentatively allocates the resources to process Pi and updates the following data structures:
   
   
   
   (4) The system runs the safety algorithm to check whether the system is in a safe state after this allocation. If safe, the resources are formally allocated to Pi and the allocation completes; otherwise the tentative allocation is undone, the previous allocation state is restored, and Pi waits.

   

Safety Algorithm

(1) Set up two vectors:
Work vector Work: it represents the number of resources of each class that the system can provide for processes to keep running. It has m elements, and at the start of the safety algorithm, Work is initialized to Available.
Finish: it indicates whether the system has enough resources to allocate to a process so that it can run to completion. Initially Finish[i]=false; when enough resources can be allocated to the process, set Finish[i]=true.
(2) Find a process in the process set satisfying:


If found, go to step (3); otherwise, go to step (4).
(3) Once process Pi obtains the resources, it can run to completion and release the resources allocated to it, so execute:


go to step 2;
(4) If holds for all processes, the system is in a safe state; otherwise, the system is in an unsafe state.

Safety Algorithm

Q
In the Banker’s Algorithm, suppose the following resource allocation state arises:

Process	Max	Allocation	Available
P0	0 0 4 4	0 0 3 2	1 6 2 2
P1	2 7 5 0	1 0 0 0	1 6 2 2
P2	3 6 10 10	1 3 5 4	1 6 2 2
P3	0 9 8 4	0 3 3 2	1 6 2 2
P4	0 6 6 10	0 0 1 4	1 6 2 2

1. Is this state safe?
2. If process P2 issues the request Request(1, 2, 2, 2), can the system allocate the resources to it?
3. If the system immediately grants P2’s request above, does the system immediately enter a deadlock state?

A

(1) Safe. One possible safe sequence is {P0, P3, P4, P1, P2} or {P0, P3, P1, P4, P2} >

(2) After P2 issues the request vector , the system checks it with the Banker’s Algorithm:
>
The system tentatively allocates the resources to P2 and updates the vectors:

Running the safety check: at this point, for every process the condition fails, that is, cannot satisfy any process’s request, so the system enters an unsafe state. Therefore, when process P2 issues , the system cannot allocate the resources to it.
(3) If the system immediately grants P2’s request (1,2,2,2), the system does not immediately enter deadlock, because at that moment no process has requested new resources or become blocked for lack of them. Only when these processes make new requests that leave all unfinished processes blocked waiting for resources does the system enter a deadlock state.

Deadlock Detection and Recovery

If the system is unwilling to impose heavy constraints to prevent deadlock, and does not want the extra overhead of predicting and avoiding it, then the only option is to let deadlock happen and then resolve it. The system therefore needs some way to detect deadlock.

Deadlock Detection

Reducing the Resource Allocation Graph to Detect Deadlock

Resource Allocation Graph
The graph is a pair G＝（N,E） consisting of a set of nodes N and a set of edges E, where:

1. N is divided into two disjoint subsets: a set of process nodes P={P1,P2，…，Pn} and a set of resource nodes R={R1, R2 ，…， Rn}, with N＝PUR
2. Every edge e∈E connects one node in P and one node in R
   e={Pi,Rj} means process Pi requests one unit of resource
   e={Rj,Pi} means one unit of resource is allocated to process Pi

Steps:
Step 1: first see how many resources remain unallocated, then see which processes are not blocked (i.e., the system has enough free resources to allocate to them).
Step 2: remove all edges of each unblocked process, turning it into an isolated node, and reclaim the resources the system had allocated to it.
Step 3: repeat steps 1 and 2.
Step 4: finally, if all resources and processes can become isolated nodes, the graph is called “completely reducible.”

Deadlock theorem: S is a deadlock state if and only if the resource allocation graph of state S is not completely reducible.

Data structures for deadlock detection

• The available resource vector , representing the number of available resources of each of the m classes.
• Processes that no longer hold resources (i.e., processes whose and vectors are 0) are recorded in list L, i.e.,
• Find a process in the process set with and handle it as follows: (1) reduce its part of the resource allocation graph, release its resources, and increase the work vector ; (2) record it in list L.
• If not all processes can be recorded in list L, the resource allocation graph of system state S is not completely reducible, and the system state will deadlock.

Work = Available;L = {Li| Allocation_i = 0 ∩ Request_i = 0};for(i=1; Pi not in L; i++){   if Requesti≤Work{      Work=Work+Allocation_i;      Li=Pi；      L=Li∪L;   }}deadlock= !(L={p1, p2, …, pn});

Example
p processes share m resources of the same class. Each resource can be used by only one process at a time, each process uses any resource for only a finite time and releases it immediately after use, and each process’s maximum demand for the resource class is less than the number of resources in the class. Suppose the sum of all processes’ maximum demands is less than p+m. Prove that deadlock cannot occur in the system.
Proof: assume the system deadlocks.
Let Max(i) be the maximum resource demand of process i, Need(i) the resources it still needs, and Allocation(i) the resources allocated to it. At any moment the system satisfies:

If the system deadlocks, then on one hand all m resources must have been allocated:
On the other hand, the processes will be in an indefinite waiting state.
From (1) and (2):
That is, after deadlock, the total resources still needed by the p processes is less than p, which means at least one process, say j, has already obtained all the resources it needs, i.e., . But when the system deadlocks, each process still needs at least one resource unit, i.e., , contradicting inequality (3). Moreover, since process j has already obtained all the resources it needs, it can complete its task and release the resources it holds, allowing the system to make progress, which contradicts the deadlock assumption.

Deadlock Recovery

When deadlocked processes are found, two methods are commonly used to resolve the deadlock:

1. Preempt resources. Take enough resources from other processes and give them to the deadlocked processes to break the deadlock.
2. Terminate processes. The simplest way is to abort all deadlocked processes; or terminate them one by one in some order until enough resources become available and the deadlock is eliminated.

Deadlock recovery methods, listed in increasing order of complexity:

1. Terminate the deadlocked processes — currently the most common method used in operating systems.
2. Roll the deadlocked processes back to a previous checkpoint and re-execute each process.
3. Select and terminate deadlocked processes one by one according to some principle until the deadlock is resolved.
4. Preempt resources from processes one by one according to some principle until the deadlock is resolved.

The third and fourth methods need to choose the process with the least cost to the system. Minimum-cost principles:

• the process that has consumed the least CPU time so far;
• the process that has produced the least output so far;
• the process estimated to have the most work remaining;
• the process that has acquired the fewest resources so far;
• the process with the lowest priority.
  The (minimum) cost of extricating the system from a deadlock state can be expressed as:

• is the minimum cost of getting out of the deadlock state.
• , , , … are the costs each deadlock participant (e.g., a thread, process, or transaction) must pay. These costs may differ, since each participant may be in a different state and may need to perform different operations.
• , , , … are the minimum costs of choosing each deadlock participant, because when resolving deadlock we usually pick the strategy that minimizes total cost.