操作系统课件5_1.pptVIP

哲学家就餐问题—管程解决方法 Procedure put_down(I:0..4); Begin fork[I]:=free; signal(q[I]) End; Procedure init; Var I:0..4; Begin For I:=0 to 4 Do fork[I]:=free; End; Begin init End; * 哲学家就餐问题—管程解决方法 Var forks:dining_philosophers; I号哲学家活动： Repeat {thinking} with_two_forks:=false; Repeat forks.pick_up(I); If forks.try_pick_up((I+1)mod 5) Then with_two_forks:=true Else forks.put_down(I) Until with_two_forks; {Eating} forks.put_down(I); forks.put_down((I+1)mod 5) Until false; * 例5-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),(r4,p3)} p1 p2 p3 r1 r3 r2 r4 * 例5-2：有环路，有死锁 p1 p2 p3 r1 r3 r2 r4 增加边(p3,r2) * 例5-3：(有环路，无死锁) p1 p2 p3 p4 r1 r2 * 5.5.1 资源分配图的定义 结论： 如果资源分配图中不存在环路, 则系统中不存在死锁; 如果资源分配图中存在环路, 则系统中可能存在死锁, 也可能不存在死锁 * 5.5.2 资源分配图的约简 通过对资源分配图的约简，可判断系统是否处于死锁状态 资源分配图中的约简方法如下： (1)寻找一个非孤立且没有请求边的进程结点pi，若无算法结束； (2)去除所有pi的分配边使pi成为一个孤立结点； (3)寻找所有请求边均可满足的进程pj，将pj的请求边全部改为分配边； (4)转步骤(1)． * 5.5.2 资源分配图的约简 若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的 文献已证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简。这一结论称为死锁定理 ?定理： S为死锁状态的充分必要条件是S的资源分配图不可完全约简 * 5.6 死锁预防 对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。 优点：简单，系统不需要做什么。 缺点：对进程的约束，违反约束仍可能死锁。 预防方法： 预先分配法 有序分配法 * 5.6.1 预先分配法 进程：运行前申请所需全部资源； 系统： 能够满足，全部分配， 否则，一个也不分配。 破坏“保持申请hold-and-wait”条件 缺点： 资源利用效率低； 一次提出申请困难 进程在运行前可能并不知道它所需要的全部资源 * 5.6.2 有序分配法 事先将所有资源类全排序, 赋予每一个资源类一个唯一的整数 形式化定义：设R={r1,r2,…,rm}为资源类集合, 定义一个一对一的函数f: R→N, 其中N为自然数集 规定进程必需按照资源编号由小到大的次序申请资源 * 5.6.2 有序分配法 资源集：R={r1,r2,…,rn} 函数：F：R?N 例如：R={scanner,tape,printer} F(scanner)=1; F(tape)=2; F(printer)=3; 进程pi可以申请资源rj中的实例??ri,pi占有ri, F(ri)?F(rj) r1 r2 rk rm ... ... 申请次序 * 5.6.2 有序分配法 当进程不占有任何资源时, 它可以申请某一个资源类(如ri)中的任意多个资源实例 此后它可申请另一个资源类(如rj)中的若干个实例的充要条件是：f(ri)f(rj) 如果进程需要同一资源类中的若干个资源实例, 则必需在一个申请命令中同时发出请求 一个进程可以申请某一资源类ri中资源实例的充要条件是它必须已经释放了资源类rj中的所有资源实例, 这里f(ri)≤f(r