Deadlock and Starvation

Deadlock can be defined as the permanent blocking of a set of processes that either compete for system resources or communicate with each other. A set of processes is deadlocked when each process in the set is blocked awaiting an event (typically the freeing up of some requested resource) that can only be triggered by another blocked process in the set. Deadlock is permanent because none of the events is ever triggered. Unlike other problems in concurrent process management, there is no efficient solution in the general case. Illustration of Deadlock:

Illustration of Deadlock

死锁问题：由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待只能由其他进程引发的事件。

General Categories of Resources

Reusable Resource

资源不能被删除且在任何时刻只能有一个进程使用
进程释放资源后，其他进程可以重用

Consumable Resource

资源的创建和销毁（I/O 缓冲区的中断、信号、信息等）
可能出现死锁

Resource Allocation Graphs

A useful tool in characterizing the allocation of resources to processes is the resource allocation graph.The resource allocation graph is a directed graph that depicts a state of the system of resources and processes, with each process and each resource represented by a node. A graph edge directed from a process to a resource indicates a resource that has been requested by the process but not yet granted. Within a resource node, a dot is shown for each instance of that resource.

Examples of Resource Allocation Graphs

The Conditions for Deadlock

Mutual exclusion. Only one process may use a resource at a time. No process may access a resource unit that has been allocated to another process.
Hold and wait. A process may hold allocated resources while awaiting assignment of other resources.
No preemption. No resource can be forcibly removed from a process holding it.
Circular wait. A closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain

Deadline Avoidance

Deadlock Prevention：确保系统永远不会进入死锁状态。
Deadlock Avoidance：在使用前进行判断，只允许不会出现死锁的进程请求资源
Deadlock Detection & Recovery：在检测到运行系统进入死锁状态后，进行恢复
安全状态和死锁的关系：
- 系统处于安全状态，一定没有死锁
- 系统处于不安全状态，可能出现死锁
  - 避免死锁就是确保系统不会进入不安全状态

Banker's Algorithm

Process Initiation Denial

Consider a system of $n$ processes and $m$ different types of resources. Let us define the following vectors and matrices:

Resource $R = (R_{1}, R_{2}, \dots, R_{m})$ . Total amount of each resource in the system.
Available $V = (V_{1}, V_{2}, \dots, V_{m})$ . Total amount of each resource not allocated to any process.
Claim $C = ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ C_{11} C_{21} ⋮ C_{n 1} C_{12} C_{22} ⋮ C_{n 2} \dots \dots ⋮ \dots C_{1 m} C_{2 m} ⋮ C_{n m} ⎠ ⎟ ⎟ ⎟ ⎟ ⎞$ . $C_{i j}$ = requirement of process $i$ for resource $j$ .
Allocation $A = ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ A_{11} A_{21} ⋮ A_{n 1} A_{12} A_{22} ⋮ A_{n 2} \dots \dots ⋮ \dots A_{1 m} A_{2 m} ⋮ A_{n m} ⎠ ⎟ ⎟ ⎟ ⎟ ⎞$ . $A_{i j}$ = current allocation to process $i$ of resource $j$ .

The following relationships hold:

$R_{j} = V_{j} + i = 1 \sum n A_{i j}$ , for all $j$ : All resources are either available or allocated.
$C_{i j} \leq R_{j}$ , for all $i, j$ : No process can claim more than the total amount of resources in the system.
$A_{i j} \leq C_{i j}$ , for all $i, j$ : No process is allocated more resources of any type than the process originally claimed to need.

With these quantities defined, we can define a deadlock avoidance policy that refuses to start a new process if its resource requirements might lead to deadlock. Start a new process $P_{n + 1}$ only if $R_{j} \geq C_{(n + 1) j} + i = 1 \sum n C_{i j}, for all j$

Resource Allocation Denial

A safe state is one in which there is at least one sequence of resource allocations to processes that does not result in a deadlock (i.e., all of the processes can be run to completion).
An unsafe state is, of course, a state that is not safe.

In terms of the matrices and vectors introduced earlier, the condition to be met for process $i$ is: $C_{i j} - A_{i j} \leq V_{j}, for all j$ Safe State:

Safe State

Unsafe State:

Unsafe State

It is unsafe because each process will need at least one additional unit of R1, and there are none available. Thus, on the basis of deadlock avoidance, the request by P1 should be denied and P1 should be blocked. It is important to point out that Figure (b) is not a deadlocked state. It merely has the potential for deadlock. If P1 were run from this state, it would subsequently release one unit of R1 and one unit of R3 prior to needing these resources again. If that happened, the system would return to a safe state.

Thus, the deadlock avoidance strategy does not predict deadlock with certainty; it merely anticipates the possibility of deadlock and assures that there is never such a possibility.

Deadlock Detection

The Allocation matrix and Available vector described in the previous section are used. In addition, a request matrix $Q$ is defined such that $Q_{i j}$ represents the amount of resources of type $j$ requested by process $i$ .

The algorithm proceeds by marking processes that are not part of a deadlocked set. Initially, all processes are unmarked. Then the following steps are performed:

Mark each process that has a row in the Allocation matrix of all zeros. A process that has no allocated resources cannot participate in a deadlock.
Initialize a temporary vector $W$ to equal the Available vector.
Find an index $i$ such that process $i$ is currently unmarked and the ith row of $Q$ is less than or equal to $W$ . That is, $Q_{i k} \leq W_{k}$ , for $1 \leq k \leq m$ . If no such row is found, terminate the algorithm.
If such a row is found, mark process $i$ and add the corresponding row of the allocation matrix to $W$ . That is, set $W_{k} = W_{k} + A_{i k}$ , for $1 \leq k \leq m$ . Return to step 3.

Example I

Example of Deadlock

Mark P4, because P4 has no allocated resources.
Set $W = (00001)$
The request of process P3 is less than or equal to $W$ , so mark P3 and set $W = W + (00010) = (00011)$
No other unmarked process has a row in Q that is less than or equal to W. Therefore, terminate the algorithm.

The algorithm concludes with P1 and P2 unmarked, indicating these processes are deadlocked.

Example II

Example Two of Deadlock

由于已分配进程中找不到全 0 向量，所以不能 mark。
计算 $W$ 向量为全 0。
T0 的资源请求 $Q_{0}$ 向量小于等于 $W$ ， $W = W + A_{0} = (010)$
T2 的资源请求 $Q_{2}$ 向量小于等于 $W$ ， $W = W + A_{2} = (313)$
T3 的资源请求 $Q_{3}$ 向量小于等于 $W$ ， $W = W + A_{3} = (524)$
T4 的资源请求 $Q_{4}$ 向量小于等于 $W$ ， $W = W + A_{4} = (526)$
T1 的资源请求 $Q_{1}$ 向量小于等于 $W$ ， $W = W + A_{1} = (726)$

因此执行序列 T0, T2, T3, T4, T1 合法。

Deadlock Recovery

Once deadlock has been detected, some strategy is needed for recovery. The following are possible approaches, listed in the order of increasing sophistication:

Abort all deadlocked processes.
Back up each deadlocked process to some previously defined checkpoint, and restart all processes.
Successively abort deadlocked processes until deadlock no longer exists.
Successively preempt resources until deadlock no longer exists.