介绍一些常见的并发问题，尤其是死锁 (deadlock)。
非死锁问题
- 原子性违反 (atomicity violation)：加互斥锁
- 顺序违反 (order violation)：加条件变量
什么是死锁？
一系列线程持有某些资源，同时阻塞地等待其他线程持有的资源，导致所有线程都被阻塞。
死锁的条件
- 互斥 (mutual exclusion)：资源不能被多个线程共享（锁的 nature？）
- 持有并等待 (hold-and-wait)：线程持有某些资源的同时等待额外的资源
- 不抢占 (no preemption)：不能抢占线程已持有的资源
- 循环等待 (circular wait)：存在一个循环依赖，每个线程都在等待下一个线程持有的资源
死锁的预防
破坏「互斥」条件：无锁 (lock-free) 或无等待 (wait-free) 的同步方式，如应用 compare-and-swap。但可能会出现新的活锁 (livelock) 问题。
破坏「持有并等待」条件：在一开始，线程要么获取需要的所有资源，要么不获取任何资源 (all or nothing)。
破坏「不抢占」条件：若线程请求的资源不能被立即满足，则释放所有其已经持有的资源。
破坏「循环等待」条件：设定资源获取的顺序 (total or partial ordering)。
银行家算法
给定关于线程与资源的先验知识，通过调度避免死锁。
Dijkstra 提出了银行家算法 (Banker’s Algorithm)，基本思想是额外资源的分配不会导致系统进入不安全状态 (unsafe state)。
- 安全状态：在当前系统中存在一个可行的解序列使得所有线程的资源请求都能被满足
步骤：
- 通过 Max 与 Loan 矩阵计算 Claim 矩阵（每个线程需要的资源）
- 可用资源量 Available 向量
- 若对于线程 $P_i$，都存在一种资源 $R_j$ 使得 $Claim[P_i][R_j]>Available[R_j]$，该线程是不安全的；如果系统中所有的线程均不安全，那么系统处在不安全状态
- 否则把资源分配给安全线程；执行完毕后它将释放自己持有的所有资源（包括 Loan 中的）
死锁的检测与回复
所有死锁的预防措施都会极大降低资源利用率。
既然死锁的出现频率十分之低，不如等它们出现了再去处理？