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:T1T_1T2T_2 、...、 TnT_n

  • Resource types: R1R_1R2R_2 、...、 RmR_m

    • 每个 resource type RiR_iWiW_i 个实例

    • 每个 thread 与 resource 实例的关系可能有 Request、Use、Release

Resource-Allocation Graph

Graph 由节点 V 与边 E 构成:

  • V 分成两种类型:T 和 R

  • E 也可以分成两种:

    • Request Edge: T1RjT_1 \rightarrow R_j

    • Assignment Edge: RjTiR_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