# 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 之间形成了资源等待环，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBMlledh02zoPfsdrz%2F-LbBWtCnA0CKz76kl-nc%2FScreen%20Shot%202019-03-30%20at%2010.57.03%20AM.jpg?alt=media\&token=46dffb92-f58c-4028-9120-2082b1949534)

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

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

## Deadlock

### Conditions for Deadlock

先观察 4 个 Deadlock 的案例

#### Example1: Thread A & B

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBMlledh02zoPfsdrz%2F-LbBYEOcfEUGFFiZ_d4X%2FScreen%20Shot%202019-03-30%20at%2011.02.56%20AM.jpg?alt=media\&token=dc6c9ab2-2fdd-4b53-bbfb-daad59f93926)

可以观察到：

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

#### Example2: Bridge Crossing Example

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBMlledh02zoPfsdrz%2F-LbBYp3-pjtQPVcKf_0e%2FScreen%20Shot%202019-03-30%20at%2011.05.30%20AM.jpg?alt=media\&token=a83335ca-5d9e-404a-9b84-f6e0ae2c5a21)

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

#### Example3: Train Example

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBMlledh02zoPfsdrz%2F-LbB_Er9qSVsOZIVoyvz%2FScreen%20Shot%202019-03-30%20at%2011.11.43%20AM.jpg?alt=media\&token=0e15614d-c35d-4af0-8cba-5570438e240f)

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

#### Example4: Dining Lawyers Problem

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBMlledh02zoPfsdrz%2F-LbBaEvqMh3_0dRZ9vjA%2FScreen%20Shot%202019-03-30%20at%2011.16.04%20AM.jpg?alt=media\&token=9dcb958b-5ab0-4cea-aee5-c76b0a89b7e8)

即哲学家就餐问题，有 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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBl9W_ohBKhpzdlbgf%2F-LbBmICyllYAbGHNsNga%2FScreen%20Shot%202019-03-30%20at%2012.08.44%20PM.jpg?alt=media\&token=60aa6426-f45f-44ff-ba17-894c5209bd6d)

#### 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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBl9W_ohBKhpzdlbgf%2F-LbBmu3ayb5ODZ-co8Yn%2FScreen%20Shot%202019-03-30%20at%2012.11.23%20PM.jpg?alt=media\&token=a895f03c-f90a-4cd3-804e-233c9ee157d1)

### Deal With Deadlock

#### Deadlock Detection Algorithm

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

```c
[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](https://inst.eecs.berkeley.edu/~cs162/sp15/static/lectures/11.pdf)&#x20;