死锁

概念

死锁（deadlock）指一组进程中的每一个都在等待一个事件，而该事件只能由这组进程中的另一个进程触发，于是谁也动不了，永远等下去。

一句话说清它是什么：死锁就是"资源上的循环等待"——A 抱着 1 等 2，B 抱着 2 等 1。它和前面几章的关系是：os/13-semaphore.md 里"P 序颠倒会死锁"、os/14-classic.md 里"哲学家各持一根筷子"就是死锁的两个真实剧本。

⚠️ 死锁与"饥饿"不是一回事（本章第一个易混点）：

对比项	死锁	饥饿（starvation，也叫"无限等待"）
等待关系	循环等待（我等的资源被你占着，你等的被我占着）	单向等待（我一直在等，但持有者会释放，只是总轮不到我）
是否有"环"	一定有（资源分配图里成环）	没有环
推进的可能性	只要不干预就永远不可能推进	理论上随时可能推进（只是调度/策略不让）
典型成因	竞争不可剥夺资源	优先级调度（低优先级永远排不上）、SJF（长作业总被后来的短作业插队）
解法	预防 / 避免 / 检测 + 解除	老化（aging，随等待时间提高优先级）

os/11-scheduling.md 里 HRRN 之所以被拿出来讲，正是为了对抗 SJF 的"长作业饥饿"——那句"最优 ≠ 公平"说的就是饥饿问题，不是死锁问题。 答题时"死锁"与"饥饿"千万别互换。

原理

一、死锁产生的四个必要条件（必背）

四个条件必须同时成立才可能死锁——少一个都不行（这就是"预防"的着力点）：

条件	含义	一句话记法
互斥条件	资源一次只能被一个进程占用	"独占"
不可剥夺条件（不剥夺）	已获得的资源不能被强行抢走，只能由持有者自愿释放	"抢不走"
请求并保持条件（占有并等待）	已经占着一些资源，又去申请新的，且申请时不释放已有资源	"吃着碗里看着锅里"
循环等待条件	存在一条进程—资源的循环等待链： $P_{0}$ 等 $P_{1}$ 的资源， $P_{1}$ 等 $P_{2}$ 的…… $P_{n}$ 等 $P_{0}$ 的	"首尾相接的等"

⚠️ 关键口径：四个条件是"必要条件"而不是"充分条件"——出现了循环等待链未必真死锁（当同类资源有多个实例时，链上的等待可能被其他进程释放的资源打破）。只有"每类资源只有一个实例"时，有环 ⟺ 死锁。

二、四种处理策略（这张表是本章的骨架）

策略	做法	代价	适用
预防（prevention）	破坏四个必要条件之一	资源利用率低、并发度低	代价可接受时
避免（avoidance）	不破坏条件，但每次分配前先算一遍"分配后是否安全"，不安全就不给	要预知最大需求、计算开销大	银行家算法（教学口径）
检测与解除（detection & recovery）	允许死锁发生，定期检测，发现后解除	检测本身有开销；解除要丢工作	通用操作系统的现实选择
忽略（鸵鸟策略）	假装看不见；出了就重启	无	多数通用 OS 的实际做法

⚠️ 别把"预防"和"避免"混为一谈：预防是"事前改造系统，让死锁根本不可能出现"（如给资源编号、要求一次申请全部）；避免是"事前不改系统，但分配时动态判断会不会不安全"。"银行家算法"属避免，不属预防。

三、预防死锁：逐个破坏四个条件

破坏的条件	具体手段	副作用
互斥	一般不能破坏（有些资源天生不可共享，如打印机）	—— 这是四条里唯一"通常不破坏"的
不可剥夺	① 申请新资源被拒时，立即释放已持有的全部资源（等以后再一起申请）；② 或由系统强行剥夺	前功尽弃、反复重试；只对"可保存现场"的资源可行（如 CPU 寄存器、内存）
请求并保持	① 一次性申请全部资源（用完才走）；② 或申请新资源前先释放已占的全部资源	① 资源浪费严重、可能饿死（申请时资源不够就一直等）；② 可能反复释放又申请
循环等待	给资源统一编号，规定"只能按序号递增的顺序申请"	限制编程自由度；编号顺序与实际使用顺序可能不一致——这是最常用、代价最小的一条

"资源有序分配法"的完整规则（破坏循环等待，考得最多）：

把资源按编号排成 1, 2, 3, ..., n
进程要申请第 i 号资源时, 必须保证:
  ★ 已经持有的所有资源编号都 < i (即"只能往大号申请")
等价说法: 每个进程持有的资源编号集合, 必须构成"一个前缀"
→ 这样就不可能形成环 (因为环上必然出现一次"从大号回到小号"的申请)

四、避免死锁：安全状态与银行家算法（本章最难、也最常考）

先建立两个概念：

安全序列：若存在一个进程排列 $P_{i_{1}}, P_{i_{2}}, \dots, P_{i_{n}}$ ，使得每一个进程都能拿到它所需的全部资源（加上此前进程释放的）而顺利完成，则称该序列是安全序列。
安全状态：只要存在一个安全序列，系统就处于安全状态。
不安全状态：不存在任何安全序列——⚠️ 不安全 ≠ 死锁，只是**"可能死锁"**（进程要是"规规矩矩"地按需申请，也可能都跑完）。

text

        安全状态  ──────▶  不安全状态  ──────▶  死锁状态
        (必无死锁)         (未必死锁)          (必不安全)
        └──────── 银行家算法把"分配后是否仍安全"当作准入条件 ────────┘

银行家算法的数据结构（设 $n$ 个进程、 $m$ 类资源）：

名称	维度	含义
Available	$1 \times m$	每类资源当前可用数量
Max	$n \times m$	每个进程对每类资源的最大需求（必须预先声明）
Allocation	$n \times m$	已分配给每个进程的量
Need	$n \times m$	还需要的量，恒有 $Need = Max - Allocation$

安全性算法（判断当前状态是否安全， $O (n^{2} m)$ ）：

① Work = Available ; Finish[i] = false (i = 0..n-1)
② 找一个满足 Finish[i] == false 且 Need[i] <= Work 的进程 P_i
③ 若找到: Work = Work + Allocation[i] ; Finish[i] = true ; 回到 ②
   若找不到: 转 ④
④ 若所有 Finish[i] 都为 true -> 安全(并得到安全序列); 否则 -> 不安全

银行家算法的"试探—回滚"三步（进程 $P_{i}$ 提出请求 ${Request}_{i}$ 时）：

① 合法性检查: Request_i <= Need_i ?  Request_i <= Available ?
     任一不成立 -> 报错(请求超需求 / 资源不够)
② 试探性分配: Available -= Request_i ; Allocation_i += Request_i ; Need_i -= Request_i
③ 安全性检查: 调用上面的安全性算法
     安全   -> ★ 正式分配
     不安全 -> ★ 撤销试分配(把三个量还原), 让 P_i 等待

⚠️ 最容易漏的一步是 ③ 的"撤销"——做题时必须把试探改变的量还原回去，否则后面的小问全部连带算错。

五、死锁检测：资源分配图的简化

资源分配图（resource allocation graph）有两种结点和两种边：

text

     ○ 进程            □ 资源(方框内的小圆点 = 该资源的实例数)
     ── 申请边 (P -> R, 我要)
     ── 分配边 (R -> P, 我占着)

  可完全简化 <=> 无死锁
  简化规则: 找一个"申请量 <= 当前可用量"的进程, 让它跑完, 收回它占的所有资源,
            再找下一个 ... 直到再也找不到 -> 剩下的进程即为死锁进程

"死锁定理"：系统处于死锁状态 $⟺$ 资源分配图的当前状态是"不可完全简化"的。

⚠️ 有环 ≠ 死锁的两种情况：
每类资源仅 1 个实例：有环 ⟺ 死锁
同类资源有多个实例：有环只是"可能死锁"，要看简化能不能做完（下例 A 就是"有环但无死锁"）

六、死锁的解除

手段	做法	代价
资源剥夺法	从别的进程那里强行抢资源给死锁进程	被抢者前功尽弃（要选"代价最小"的牺牲者）
撤销进程法	杀掉一个或多个死锁进程	丢工作；要么全杀重来（简单但代价大），要么按代价递增逐个杀
进程回退法	让进程回退到某个"未死锁"的检查点，再重新推进	要预先设检查点，实现复杂

示例

例 1：银行家算法完整推演

系统有 A、B、C 三类资源，总量 A = 10、B = 5、C = 7；5 个进程 P0~P4，当前状态如下：

进程	Allocation (A B C)	Max (A B C)	Need = Max − Alloc (A B C)
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

第一步：求初始 Available

Available = (10, 5, 7) - (0 + 2 + 3 + 2 + 0, 1 + 0 + 0 + 1 + 0, 0 + 0 + 2 + 1 + 2) = (10, 5, 7) - (7, 2, 5) = (3, 3, 2)

第二步：用安全序列扫描（选中即释放）

轮次	候选检查	选中	释放后 Work
1	P1 $n e e d (1, 2, 2) \leq (3, 3, 2)$ ✔（P0、P2、P3、P4 都不满足）	P1	$(3, 3, 2) + (2, 0, 0) = (5, 3, 2)$
2	P3 $n e e d (0, 1, 1) \leq (5, 3, 2)$ ✔	P3	$(5, 3, 2) + (2, 1, 1) = (7, 4, 3)$
3	P0 $n e e d (7, 4, 3) \leq (7, 4, 3)$ ✔	P0	$(7, 4, 3) + (0, 1, 0) = (7, 5, 3)$
4	P2 $n e e d (6, 0, 0) \leq (7, 5, 3)$ ✔	P2	$(7, 5, 3) + (3, 0, 2) = (10, 5, 5)$
5	P4 $n e e d (4, 3, 1) \leq (10, 5, 5)$ ✔	P4	$(10, 5, 5) + (0, 0, 2) = (10, 5, 7)$

安全序列 = P1 → P3 → P0 → P2 → P4（存在即安全；本题不唯一，例如把第 3、4 轮换成 P4→P0 也一样成立）。

第三步：三个请求的裁决

请求	资源够不够	试分配后 Available	试分配后是否安全	结论
P1 要 (1,0,2)	$(1, 0, 2) \leq (3, 3, 2)$ ✔	$(2, 3, 0)$	安全（仍有安全序列）	可以分配
P4 要 (3,3,0)	$3 > 2$ （A 不够）✘	——	——	不能分配（资源不足）
P0 要 (0,2,0)	$(0, 2, 0) \leq (2, 3, 0)$ ✔	$(2, 1, 0)$	不安全（无任何进程能完成）	不能分配（会让系统进入不安全状态）

P0 请求为何不安全：试分配后 Need[P1] = (0,2,0)，而 Work = (2,1,0)——B 类差 1 个；其余进程（P0 要 (7,2,3)、P2 要 (6,0,0)、P3 要 (0,1,1)、P4 要 (4,3,1)）更是全线不满足（P3 差的正是 C 类的 1 个）。一轮扫描下来一个也找不到 → 不安全 → 拒绝，并把状态还原。

例 2：C 实现——银行家算法（安全性检查 + 试探分配）

#include <stdio.h>

#define N 5        /* 进程数 */
#define M 3        /* 资源类型数 */

static int avail[M]    = {3, 3, 2};
static int maxm[N][M]  = {{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
static int alloc[N][M] = {{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
static int need[N][M];      /* need = max - alloc */
static int finish[N];

static void calc_need(void) {
    int i, j;
    for (i = 0; i < N; i++)
        for (j = 0; j < M; j++)
            need[i][j] = maxm[i][j] - alloc[i][j];
}

/* 安全性算法: 安全返回 1 并写出安全序列 seq[], 否则返回 0 */
static int is_safe(int av[], int seq[]) {
    int work[M], i, j, k, cnt = 0;
    for (j = 0; j < M; j++) work[j] = av[j];
    for (i = 0; i < N; i++) finish[i] = 0;
    for (k = 0; k < N; k++) {
        int found = -1;
        for (i = 0; i < N; i++) {
            int ok = 1;
            if (finish[i]) continue;
            for (j = 0; j < M; j++)
                if (need[i][j] > work[j]) { ok = 0; break; }
            if (ok) { found = i; break; }
        }
        if (found < 0) break;               /* 找不到可完成者 -> 不安全 */
        for (j = 0; j < M; j++) work[j] += alloc[found][j];
        finish[found] = 1;
        seq[cnt++] = found;
    }
    return cnt == N;
}

/* 试探分配: 2 = 已正式分配; 1 = 资源不足; 0 = 不安全(状态已还原)
 * nav_out 回传"试分配后"的 Available, 便于观察 */
static int try_request(int p, int req[], int av[], int seq[], int nav_out[]) {
    int j, nav[M];
    for (j = 0; j < M; j++)
        if (req[j] > av[j]) return 1;             /* ① 资源不足 */
    for (j = 0; j < M; j++) {                     /* ② 试分配 */
        nav[j]       = av[j] - req[j];
        alloc[p][j] += req[j];
        need[p][j]  -= req[j];
    }
    for (j = 0; j < M; j++) nav_out[j] = nav[j];
    if (is_safe(nav, seq)) {                      /* ③ 安全 -> 正式分配 */
        for (j = 0; j < M; j++) av[j] = nav[j];
        return 2;
    }
    for (j = 0; j < M; j++) {                     /* ③' 不安全 -> 回滚 */
        alloc[p][j] -= req[j];
        need[p][j]  += req[j];
    }
    return 0;
}

static void show_avail(const char *tag, int av[]) {
    printf("%s Available = %d %d %d\n", tag, av[0], av[1], av[2]);
}

static void try_and_report(int p, int r0, int r1, int r2, int av[], int seq[]) {
    int req[M], nav[M], r;
    req[0] = r0; req[1] = r1; req[2] = r2;
    r = try_request(p, req, av, seq, nav);
    printf("P%d 请求 (%d,%d,%d)? ", p, r0, r1, r2);
    if (r == 1) {
        printf("不能分配 (资源不足)\n");
    } else if (r == 0) {
        printf("不能分配 (分配后不安全)\n");
        show_avail("  试分配后", nav);
    } else {
        printf("可以分配\n");
        show_avail("  分配后", av);
    }
}

int main(void) {
    int seq[N], i;
    calc_need();

    printf("资源总量 A=10 B=5 C=7\n");
    show_avail("初始", avail);
    if (is_safe(avail, seq)) {
        printf("安全? 是, 安全序列 =");
        for (i = 0; i < N; i++) printf(" P%d", seq[i]);
        printf("\n");
    } else {
        printf("安全? 否\n");
    }

    try_and_report(1, 1, 0, 2, avail, seq);   /* P1 要 (1,0,2) -> 可分配 */
    try_and_report(4, 3, 3, 0, avail, seq);   /* P4 要 (3,3,0) -> 资源不足 */
    try_and_report(0, 0, 2, 0, avail, seq);   /* P0 要 (0,2,0) -> 不安全 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

资源总量 A=10 B=5 C=7
初始 Available = 3 3 2
安全? 是, 安全序列 = P1 P3 P0 P2 P4
P1 请求 (1,0,2)? 可以分配
  分配后 Available = 2 3 0
P4 请求 (3,3,0)? 不能分配 (资源不足)
P0 请求 (0,2,0)? 不能分配 (分配后不安全)
  试分配后 Available = 2 1 0

⚠️ 三点说明：

try_request 的返回码三分支对应了银行家算法的三个出口——这正是大题的采分点："资源不足"和"不安全"要分开陈述。
中文一律放在格式串末尾（show_avail / printf 的格式串里只有数字与 ASCII）——printf 的宽度说明符对中文按"字节"补齐，%-24s 遇到汉字必然错位（os/10-process.md、os/15-monitor.md 都踩过）。
本机无 C 编译器，此段代码逐行人工审查，并用等价的 Python 实现（下例同一份数据）实跑核对过输出——两边的安全序列完全一致。

例 3：Python——安全性检查与死锁检测

# ============ ① 银行家算法: 安全性检查 ============
def safe_seq(alloc, need, avail, names):
    """返回安全序列(列表)或 None(不安全)"""
    n, m = len(alloc), len(avail)
    work = avail[:]
    fin = [False] * n
    seq = []
    for _ in range(n):
        for i in range(n):
            if fin[i]:
                continue
            if all(need[i][j] <= work[j] for j in range(m)):
                for j in range(m):
                    work[j] += alloc[i][j]
                fin[i] = True
                seq.append(names[i])
                break
    return seq if all(fin) else None


names = ['P0', 'P1', 'P2', 'P3', 'P4']
ALLOC = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
MAXM  = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
TOTAL = [10, 5, 7]
need = [[MAXM[i][j] - ALLOC[i][j] for j in range(3)] for i in range(5)]
avail = [TOTAL[j] - sum(ALLOC[i][j] for i in range(5)) for j in range(3)]

print('Need =', need)
print('Available =', avail)
print('初始安全序列 =', safe_seq(ALLOC, need, avail, names))
print()

# 三个请求依次裁决(★ 前一个被批准就真的分配, 后一个要在"新状态"上判断)
def judge(p, req, alloc, need, avail, names):
    """返回 (说明文字, 是否已正式分配); 若批准, 就地更新 avail / alloc / need"""
    n, m = len(alloc), len(avail)
    if any(req[j] > avail[j] for j in range(m)):
        return '资源不足', False
    nav = [avail[j] - req[j] for j in range(m)]
    a2 = [alloc[i][:] for i in range(n)]
    for j in range(m):
        a2[p][j] += req[j]
    n2 = [[MAXM[i][j] - a2[i][j] for j in range(m)] for i in range(n)]
    if safe_seq(a2, n2, nav, names):
        for j in range(m):                       # ★ 安全 -> 状态就地更新
            avail[j]     = nav[j]
            alloc[p][j] += req[j]
            need[p][j]  -= req[j]
        return '可以分配 (试分配后仍安全, 可用 %s)' % (nav,), True
    return '不能分配 (试分配后不安全, 可用 %s)' % (nav,), False


for p, req in [(1, [1,0,2]), (4, [3,3,0]), (0, [0,2,0])]:
    msg, ok = judge(p, req, ALLOC, need, avail, names)
    print('P%d 请求 %s -> %s' % (p, req, msg))

print()
print('=== ② 死锁检测: 资源分配图的可完全简化 ===')

def detect(alloc, request, avail, nm):
    n, m = len(alloc), len(avail)
    work = avail[:]
    fin = [False] * n
    seq = []
    changed = True
    while changed:
        changed = False
        for i in range(n):
            if not fin[i] and all(request[i][j] <= work[j] for j in range(m)):
                for j in range(m):
                    work[j] += alloc[i][j]
                fin[i] = True
                seq.append(nm[i])
                changed = True
    return seq, [nm[i] for i in range(n) if not fin[i]]

# 例 A: 有申请边、但可完全简化 -> 无死锁
allocA   = [[0,1,0],[2,0,0],[3,0,3],[2,1,1],[0,0,2]]
requestA = [[0,0,0],[2,0,2],[0,0,0],[1,0,0],[0,0,2]]
seqA, deadA = detect(allocA, requestA, [0,0,0], names)
print('例 A (5 进程 3 类资源, Available 全 0):')
print('  可简化序列 =', seqA)
print('  死锁进程   =', deadA if deadA else '无')

# 例 B: 三进程成环互等 -> 真死锁
allocB   = [[1,0,0],[0,1,0],[0,0,1]]
requestB = [[0,1,0],[0,0,1],[1,0,0]]
seqB, deadB = detect(allocB, requestB, [0,0,0], ['P0','P1','P2'])
print('例 B (3 进程成环, 每类资源 1 个实例):')
print('  可简化序列 =', seqB if seqB else '无')
print('  死锁进程   =', deadB)

print()
print('=== ③ 死锁与饥饿 ===')
for who, st in [('死锁进程', '永远得不到资源, 等待关系成环'),
                ('饥饿进程', '等得久但持有者最终会释放, 只是总轮不到它')]:
    print('  ' + who + ': ' + st)

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照（真实运行结果）：

Need = [[7, 4, 3], [1, 2, 2], [6, 0, 0], [0, 1, 1], [4, 3, 1]]
Available = [3, 3, 2]
初始安全序列 = ['P1', 'P3', 'P0', 'P2', 'P4']

P1 请求 [1, 0, 2] -> 可以分配 (试分配后仍安全, 可用 [2, 3, 0])
P4 请求 [3, 3, 0] -> 资源不足
P0 请求 [0, 2, 0] -> 不能分配 (试分配后不安全, 可用 [2, 1, 0])

=== ② 死锁检测: 资源分配图的可完全简化 ===
例 A (5 进程 3 类资源, Available 全 0):
  可简化序列 = ['P0', 'P2', 'P3', 'P4', 'P1']
  死锁进程   = 无
例 B (3 进程成环, 每类资源 1 个实例):
  可简化序列 = 无
  死锁进程   = ['P0', 'P1', 'P2']

=== ③ 死锁与饥饿 ===
  死锁进程: 永远得不到资源, 等待关系成环
  饥饿进程: 等得久但持有者最终会释放, 只是总轮不到它

四条结论：

Python 的安全序列 ['P1','P3','P0','P2','P4'] 与例 1 的手算、例 2 的 C 输出三方一致——银行家算法的手算流程就是"Work 表逐轮扫描"，没有任何玄机。
例 A 是"有申请边却没有死锁"的典型：Available 全 0 时一眼看去谁都动不了，但 P0 和 P2 的请求量是 0（它们只需要自身已有的资源就能跑完），释放后链条就解开了——这就是"有环 ≠ 死锁"。
例 B 每类资源只有 1 个实例，形成 1 个环 = 死锁——三条边首尾相接（P0 等 B、P1 等 C、P2 等 A），简化一步都走不动，三个进程全在死锁集里。
judge() 与 C 版 try_request() 的分支一一对应（资源不足 / 不安全 / 可分配），比对两份实现就能确认例 1 表格里那一列"结论"是对的。

考点

1. 必背结论

四个必要条件：互斥、不可剥夺、请求并保持、循环等待——同时成立才可能死锁。
四种处理策略：预防、避免、检测与解除、忽略；"银行家算法"属"避免"，不属"预防"。
预防四手段：互斥一般不破坏；不可剥夺→申请被拒就释放全部；请求并保持→一次性申请全部；循环等待→资源有序分配（编号递增申请）。
安全状态 ⟹ 无死锁；不安全状态 ⟹ 可能死锁（≠ 一定死锁）。存在安全序列就安全。
Need = Max − Allocation；Available = 总量 − 已分配总量。
死锁定理：系统死锁 ⟺ 资源分配图不可完全简化。
每类资源 1 个实例时：有环 ⟺ 死锁；多实例时：有环只是可能死锁（例 A）。
解除三法：资源剥夺、撤销进程、进程回退。
死锁 ≠ 饥饿：死锁成环、饥饿不成环；解饥饿靠"老化"。

2. 高频陷阱

把"不安全"说成"死锁"：错。不安全只是"可能死锁"；安全状态一定无死锁，但不安全状态并不必然死锁。这句话几乎每年都在选择题里出现。
忘了"试探分配后要回滚"：错。不安全时必须把 Available / Allocation / Need 三个量全部还原，否则后续小问连环错。
把"银行家算法"归到"预防"：错（属避免）。区别在"改不改系统"：预防改系统结构，避免只在分配时判断。
说"破坏互斥条件"是常用手段：错。互斥由资源性质决定，通常不能破坏；四条里最实用的是破坏"循环等待"（资源编号）。
认为"资源分配图有环就死锁"：错（多实例时只是可能）；反过来"无环一定无死锁"是对的。
把"请求并保持"与"不可剥夺"混淆：请求并保持是"占着还要要"；不可剥夺是"占了不肯放、抢不走"。
计算安全序列时"用完的进程资源忘了加回 Work"：错。每让一个进程完成，必须 Work += Allocation[i]——这是全题唯一的累加动作，漏一次后面全崩。
把"一次性申请全部资源"写成"能提高资源利用率"：错。它恰恰严重降低利用率，还可能造成饥饿。
安全序列写成"唯一答案"：不必。安全序列通常不唯一，答出一个即算对（但必须验证每个进程都能在自己的那一步完成）。
Max 没预先知道就套银行家算法：错。银行家算法要求进程"预先声明最大需求"，这是它在通用 OS 里很少真用的根本原因。

3. 解题模板（"银行家算法大题"）

① 先列三张表: Allocation / Max / Need(=Max-Alloc), 再算 Available(=总量-列和)
② 安全性检查: Work=Available; 逐轮找 Need<=Work 的进程, 选中后 Work+=Allocation
               写出安全序列; 若某轮找不到 -> 不安全
③ 请求裁决三步走:
     合法性: Request<=Need 且 Request<=Available ? (不满足 -> 报错)
     试分配: Available-=Req; Alloc+=Req; Need-=Req
     查安全: 安全 -> 保留(回答"可以分配"); 不安全 -> 三个量全部还原(回答"不能分配")
④ 凡涉及"请求"的小问, 必须写出"试分配后 Available = (...)"与"安全性检查过程"

4. 与相邻章节的接口

os/13-semaphore.md（信号量）：P 序颠倒导致的死锁是本篇"不可剥夺 + 请求并保持 + 循环等待"的活样本。
os/14-classic.md（经典问题）：哲学家朴素版（各持一根）就是"互相持有 + 循环等待"的最小死锁模型，与例 B 的三进程环同构。
os/15-monitor.md（管程）：管程里的互斥由编译器保证，但"两个条件变量互等"照样能死锁——四条必要条件与管程无关，永远成立。
os/20-contiguous.md（连续分配）：内存分配里"某进程占着大片内存不放、另一个又申请不到"正是死锁在多资源场景下的表现，页式/段式的"按需分配"从设计上就避开了"必须预先申请全部内存"。
os/11-scheduling.md（调度）：HRRN 对抗的是"饥饿"，不是"死锁"——两处最容易互相套用，务必分清。

小结

四个必要条件：互斥、不可剥夺、请求并保持、循环等待；必须同时成立，少一个都不行。
四种策略：预防（破坏条件）/ 避免（银行家算法）/ 检测与解除 / 忽略——通用 OS 实际多用"忽略 + 检测"。
预防的四个手段里，最实用的是"资源有序分配"（破坏循环等待）；互斥条件一般不动。
安全状态一定无死锁；不安全状态只是可能死锁——这条判据是本章选择题的最大得分点。
银行家算法 = 合法性检查 → 试探分配 → 安全性检查（不安全则回滚）；Need = Max − Allocation，谁完成就把 Allocation 加回 Work。
例 1 的完整推演结论：初始 Available = (3,3,2)，安全序列 P1→P3→P0→P2→P4；P1 的 (1,0,2) 可分配、P4 的 (3,3,0) 资源不足、P0 的 (0,2,0) 会让系统不安全。
死锁定理：死锁 ⟺ 资源分配图不可完全简化；每类资源 1 个实例时有环即死锁，多实例时只是可能。
解除三法：资源剥夺、撤销进程、进程回退。
死锁 ≠ 饥饿：前者成环、必须干预；后者不成环、可用老化缓解。

下一篇：连续分配管理方式

死锁

概念

原理

一、死锁产生的四个必要条件（必背）

二、四种处理策略（这张表是本章的骨架）

三、预防死锁：逐个破坏四个条件

四、避免死锁：安全状态与银行家算法（本章最难、也最常考）

五、死锁检测：资源分配图的简化

六、死锁的解除

示例

例 1：银行家算法完整推演

例 2：C 实现——银行家算法（安全性检查 + 试探分配）

例 3：Python——安全性检查与死锁检测

考点

小结

我的笔记

评论（0）

死锁 ​

概念 ​

原理 ​

一、死锁产生的四个必要条件（必背） ​

二、四种处理策略（这张表是本章的骨架） ​

三、预防死锁：逐个破坏四个条件 ​

四、避免死锁：安全状态与银行家算法（本章最难、也最常考） ​

五、死锁检测：资源分配图的简化 ​

六、死锁的解除 ​

示例 ​

例 1：银行家算法完整推演 ​

例 2：C 实现——银行家算法（安全性检查 + 试探分配） ​

例 3：Python——安全性检查与死锁检测 ​

考点 ​

小结 ​

我的笔记

评论（0）

死锁

概念

原理

一、死锁产生的四个必要条件（必背）

二、四种处理策略（这张表是本章的骨架）

三、预防死锁：逐个破坏四个条件

四、避免死锁：安全状态与银行家算法（本章最难、也最常考）

五、死锁检测：资源分配图的简化

六、死锁的解除

示例

例 1：银行家算法完整推演

例 2：C 实现——银行家算法（安全性检查 + 试探分配）

例 3：Python——安全性检查与死锁检测

考点

小结