2.4.4 死锁的处理策略—死锁的检测与解除

新困难：多实例资源图有环只是必要线索，要看能否释放足够实例

资源A、B各有2个实例，当前 Available=[0,0]。分配为 P0=[1,0]、P1=[0,1]、P2=[1,1]；尚待请求 P0=[0,1]、P1=[1,0]、P2=[0,0]。P0与P1形成表面循环等待，但P2无需更多资源即可结束并释放，系统并未死锁。

def detect_deadlock(available,allocation,request):
    work=available[:]; finish=[sum(a)==0 for a in allocation]; order=[]
    changed=True
    while changed:
        changed=False
        for i in range(len(allocation)):
            if not finish[i] and all(request[i][j]<=work[j] for j in range(len(work))):
                work=[work[j]+allocation[i][j] for j in range(len(work))]
                finish[i]=True; order.append(i); changed=True
    return [i for i,done in enumerate(finish) if not done],order,work

available=[0,0]
allocation=[[1,0],[0,1],[1,1]]
request=[[0,1],[1,0],[0,0]]
dead,order,work=detect_deadlock(available,allocation,request)
assert dead==[] and order==[2,0,1] and work==[2,2]
dead2,order2,_=detect_deadlock(available,allocation,[[0,1],[1,0],[1,0]])
assert dead2==[0,1,2] and order2==[]

陪推：Work初值00，只有P2的Request=00可满足；假定P2完成，Work加其Allocation变11。此时P0可获B并完成，释放A后Work变21；P1也可完成，最终22。变式把P2请求改为10后，初始没有任何进程请求可满足，算法无法前进，三者均在死锁集合。

依据：检测算法每次寻找“剩余请求不超过当前可用”的进程，假定其完成并回收已分配资源。Work只增不减；被标记完成者存在一条可行结束次序。停住时未完成进程彼此等待无法由集合外资源解除，因此构成死锁集合。单实例资源图中环可充要，多实例时仅见环不充分。

朴素检测时间 O(P²R)、空间 O(P+R)。错误反馈：Request是当前尚待请求，不是最大需求；能完成后释放的是Allocation；有环不能忽略资源实例数；安全性预防与事后死锁检测的输入含义不同；四必要条件同时成立也不等于某个具体状态必已死锁。

迁移答案：若初始Available改为 [0,1]，P0可先完成，同样无死锁；增加一个资源实例可能打破等待，但应重新跑状态序列而不是只看总量。

桥接：资源状态按向量推进；下一课把虚拟地址按位切成目录、页表与页内偏移，逐级读取表项完成映射。