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)

当检测到 Deadlock 存在时：

• 终止 thread，强迫它放弃资源，如

  • Bridge：上帝从桥上选中一辆车丢到河中即可

  • Dining Lawyer：枪毙一个律师

  但这种做法并不通用，直接杀死 thread 可能导致系统处于不一致的状态

• 剥夺 thread 占有的资源，但这有时候不符合语义

• 回滚 thread 的操作

• ...

Techniques for Preventing Deadlock

• 无限资源

• 无共享资源

• 不允许等待，直接拒绝，thread 只能重试

• 让所有 threads 一次性把需要的资源都获取

• 让所有 threads 按统一的顺序获取资源

Banker's Algorithm for Preventing Deadlock

核心思想：thread 启动前声明最大的资源需求量，若当前资源允许，则允许 thread 继续运行，保证整个系统永远处于安全状态。

小结

由于计算机拥有的资源有限，我们不得不通过虚拟化技术来让不同的 processes/threads 共享、复用资源，这也是 OS 要解决的核心问题：

• Multiplex CPU：Scheduling, Fix/Prevent Deadlock

• Multiplex Memory：Address Translation

• Multiplex Disk and Devices：File System, ...

明确每个话题存在的意义，能帮助我们更好地构建操作系统知识体系。

参考

slides