5.8.1 死锁检测算法
Work:=Available; Finish:=false; T Finish[I]=true for allocation[I]=0
Finish[i]=true;
有满足条件的i: F Finish[i]=false F Request[i]Work T i ,finish[i]=true 死锁
Finish
Request[2]=(0,1), 不安全,不分配,(分配不导致死锁)
讨论
Remarks1:
银行家算法要求条件:进程所需资源最大量, 这个信息 对于充要性分析是不够的。
Remarks2:
假设:进程预先给出有关资源的命令序列,则可以给出 死锁避免的充要性算法,复杂度(NP Complete)。
5.5 资源分配图
申请:pi申请rj中的一个资源实例,由pi向rj画一申请边, 如可满足,改为分配边。
释放:去掉分配边。
例子(无环路,无死锁)
例1. P={p1,p2,p3}, R={r1(1),r2(2),r3(1),r4(3)}
E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}
Remarks3:
预先给出进程有关资源的命令序列是困难的(程序的分枝 和循环)。
5.8 死锁的检测
数据结构: Available: array[1..m]of integer; Allocation: array[1..n,1..m]of integer; Request: array[1..n,1..m]of integer; 临时变量: Work: array[1..m]of integer; Finish: array[1..n]of boolean;