Resource Contention & Deadlock

简介

Resources

计算机为 Processes/Threads 提供执行所需的各种资源，包括 CPU time、disk space、memory、socket 等资源。从 OS 控制角度上看，它们可以分为：

Preemptable：可以被 OS 随时剥夺，如 CPU time
Non-preemptable：只能由 Process/Thread 主动释放的资源，如 disk space、virtual address space 以及 mutex 等

从资源共享角度上看，它们可以分为：

Exclusive Access：如打印机
Sharable：如 read-only files

因此 OS 的重要职责之一，就是管理好这些资源。

Starvation vs. Deadlock

Starvation 指的是 process/thread 一直无法获得 CPU 资源；Deadlock 指的是多个 processes/threads 之间形成了资源等待环，如下图所示：

Thread A 占有 Res1，等待 Res2 被释放
Thread B 占有 Res2，等待 Res1 被释放

Deadlock 会导致多个 threads 出现 Starvation，但反之不亦然，因为 Starvation 有可能结束，而 Deadlock 无法在没有外部干预的前提下自动解决。

Deadlock

Conditions for Deadlock

先观察 4 个 Deadlock 的案例

Example1: Thread A & B

可以观察到：

Deadlock 的出现与否并不确定，在特定情况下才会出现。
Deadlock 出现的场景存在多个独占资源

Example2: Bridge Crossing Example

在本例中，每段路都可以被看作是独占资源，每辆车在进入每段路之前，都必须获取它的使用权。当经过只有一个车道的桥时，两边的车必须同时获取桥左右两段道路的使用权，若两辆车分别获取左段和右段的使用权，则会出现 Deadlock。通常的解决方式时一辆车后退到桥外，让另一辆车先通过，或者上桥之前有交警协助管理，一次只能通过一个方向的车。此外，如果总是只让一个方向的车先通过，则会出现 Starvation。

Example3: Train Example

如图所示，当每辆火车都想向右转时，就可能出现 Deadlock。A 等待 B 离开当前铁轨，B 等待 C 离开当前铁轨，C 等待 D 离开当前铁轨，D 等待 A 离开当前铁轨，四者的需求形成等待环。

Example4: Dining Lawyers Problem

即哲学家就餐问题，有 5 名哲学家围坐在饭桌上，每个人餐盘左边和右边分别有 1 根筷子，每名哲学家需要拿到左右两边的筷子后，才能够吃饭。如果 5 名哲学家都拿起了左边的筷子，等待右边的筷子，就会出现 Deadlock。解决的思路有两种：

在 Deadlock 出现后解决
在 Deadlock 出现前预防

Four Requirements for Deadlock

以上的例子展现出 Deadlock 出现的 4 个先决条件：

Mutual Exclusion：资源独占
Hold and Wait：每个 thread 持有某个资源，同时等待其它资源被释放
No Preemption：资源只能被 thread 主动释放，无法直接剥夺
Circular Wait：存在等待环

Resource Allocation Graph

System Model

每个系统由一组 threads、resources 以及它们之间的关系构成：

A set of Threads： $T_1$ 、 $T_2$ 、...、 $T_n$
Resource types： $R_1$ 、 $R_2$ 、...、 $R_m$
- 每个 resource type $R_i$ 有 $W_i$ 个实例
- 每个 thread 与 resource 实例的关系可能有 Request、Use、Release

Resource-Allocation Graph

Graph 由节点 V 与边 E 构成：

V 分成两种类型：T 和 R
E 也可以分成两种：
- Request Edge： $T_1 \rightarrow R_j$
- Assignment Edge： $R_j \rightarrow T_i$

Graph Examples

Deal With Deadlock

Deadlock Detection Algorithm

当每种资源只有一个实例时，直接检查 Resource-Allocation Graph 中是否有环存在即可；当每种资源有多个实例时，则可以通过模拟的方式来实现：

[Avail] = [FreeResource]
Add all nodes to UNFINISHED
do {
    done = true
    Foreach node in UNFINISHED {
        if ([Request_node] <= [Avail]) {
            remove node from UNIFINISHED
            [Avail] = [Avail] + [Alloc_node]
            done = false
        }
    }
} until(done)