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:、 、...、
Resource types: 、 、...、
每个 resource type 有 个实例
每个 thread 与 resource 实例的关系可能有 Request、Use、Release
Resource-Allocation Graph
Graph 由节点 V 与边 E 构成:
V 分成两种类型:T 和 R
E 也可以分成两种:
Request Edge:
Assignment Edge:
Graph Examples
Deal With Deadlock
Deadlock Detection Algorithm
当每种资源只有一个实例时,直接检查 Resource-Allocation Graph 中是否有环存在即可;当每种资源有多个实例时,则可以通过模拟的方式来实现:
当检测到 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, ...
明确每个话题存在的意义,能帮助我们更好地构建操作系统知识体系。
参考
Last updated