2.4.3 死锁的处理策略—避免死锁

专题讲解：死锁与银行家算法

安全不等于现在所有进程都能立刻完成

上一课用固定顺序避免生产者—消费者死锁。今天用银行家算法检查一组资源状态。Available=[3,3,2]，Allocation 与 Max 如代码，要求算 Need 并找一条安全序列。

def safe_sequence(available,allocation,maximum):
    need=[[m-a for m,a in zip(mx,al)] for al,mx in zip(allocation,maximum)]
    work=available[:]; finish=[False]*len(allocation); sequence=[]
    while len(sequence)<len(allocation):
        found=False
        for i in range(len(allocation)):
            if not finish[i] and all(n<=w for n,w in zip(need[i],work)):
                work=[w+a for w,a in zip(work,allocation[i])]
                finish[i]=True; sequence.append(i); found=True
        if not found: return None,need
    return sequence,need

allocation=[[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
maximum=[[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
seq,need=safe_sequence([3,3,2],allocation,maximum)
assert need[1]==[1,2,2]
assert seq is not None and set(seq)==set(range(5))

P1 的 Need=[1,2,2]，不超过 Work [3,3,2]，可假设它完成并释放 [2,0,0]，Work 变 [5,3,2]；随后会有更多进程满足。代码可能给出 [1,3,4,0,2] 等安全序列，安全序列不要求唯一。

为何正确：算法只让 Need≤Work 的进程“试运行”，该进程必能得到剩余资源并完成，完成后 Allocation 全部归还；若能依次完成所有进程，就构造了实际可行顺序。找不到候选说明当前试探不能证明安全。

设 n 个进程、m 类资源，朴素时间 O(n²m)，Need/状态空间 O(nm)。典型错误：Need=Max-Allocation，不能直接拿 Max 与 Available 比；不安全状态不等于当前已经死锁，只是未来存在死锁风险；预防、避免、检测与解除是不同策略。

迁移答案：新请求 Request_i 先检查 Request≤Need 与 Request≤Available，再假分配并跑安全性算法；只有仍安全才真正批准。

下一课把资源视角转到内存地址：分页如何用页号查页表，再与页内偏移拼成物理地址。

专题讲解：银行家算法向量推演

请求满足 Need 和 Available，还不能立刻批准

主章已找安全序列。强化题沿用经典状态，P1 请求 [1,0,2]。先检查请求不超过 Need[1]=[1,2,2] 且不超过 Available=[3,3,2]；然后假分配，再跑安全性算法。

def safety(available,allocation,maximum):
    need=[[m-a for m,a in zip(mx,al)] for al,mx in zip(allocation,maximum)]
    work=available[:]; done=[False]*len(allocation); seq=[]
    while len(seq)<len(allocation):
        for i in range(len(allocation)):
            if not done[i] and all(n<=w for n,w in zip(need[i],work)):
                work=[w+a for w,a in zip(work,allocation[i])]
                done[i]=True; seq.append(i); break
        else: return None
    return seq

def request_resources(pid,request,available,allocation,maximum):
    need=[m-a for m,a in zip(maximum[pid],allocation[pid])]
    if any(r>n for r,n in zip(request,need)) or any(r>a for r,a in zip(request,available)):
        return False,None
    new_avail=[a-r for a,r in zip(available,request)]
    new_alloc=[row[:] for row in allocation]
    new_alloc[pid]=[a+r for a,r in zip(new_alloc[pid],request)]
    seq=safety(new_avail,new_alloc,maximum)
    return seq is not None,seq

alloc=[[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
mx=[[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
ok,seq=request_resources(1,[1,0,2],[3,3,2],alloc,mx)
assert ok and seq is not None and set(seq)==set(range(5))

假分配后 Available=[2,3,0]，P1 Allocation=[3,0,2]、Need=[0,2,0]，P1 可先完成并释放3、0、2，Work 变 [5,3,2]，随后可继续构造完整序列，因此请求可批准。

正确性不变量：Work 表示试探过程中当前可用资源；每选一个 Need≤Work 的进程，它一定能完成并归还 Allocation，因此 Work 单调不减。完成全部进程就是一份未来可行证据。

朴素安全性时间 O(n²m)，矩阵空间 O(nm)。错解反馈：通过两项前置检查只说明“请求合法且当前拿得出”，不说明分配后安全；假分配不安全必须回滚；安全序列不唯一，不应只背一个顺序。

变式答案：若 P4 请求 [3,3,0]，虽不超过其 Need [4,3,1]，但 Available 的第一类只有3可满足、第三类无请求；仍必须假分配跑安全算法，不能凭分量比较直接断定安全。

下一步比较 FIFO 与 LRU 在同一访问串、不同页框数下的缺页曲线，亲眼看到 Belady 异常。