计算机操作系统第3章节幻灯片.ppt

　　(2) ?P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： 　　① Request1(1，0，2)≤Need1(1，2，2) 　　② Request1(1，0，2)≤Available1(3，3，2) 　　③ 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图3-16中的圆括号所示。 ④ 再利用安全性算法检查此时系统是否安全。如图3-18所示。 图3-18　P1申请资源时的安全性检查 　　(3) ?P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： 　　① Request4(3，3，0)≤Need4(4，3，1)； 　　② Request4(3，3，0)≤Available(2，3，0)，让P4等待。 　　(4) ?P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： 　　① Request0(0，2，0)≤Need0(7，4，3)； 　　② Request0(0，2，0)≤Available(2，3，0)； 　　③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-19所示。 图3-19　为P0分配资源后的有关资源数据 　　(5) 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。 　　如果在银行家算法中，把P0发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它，请读者考虑。 3.7　死锁的检测与解除 3.7.1　死锁的检测 　　当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到： 　　(1) 保存有关资源的请求和分配信息； 　　(2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 　1．资源分配图(Resource Allocation Graph) 　　系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G=(N1E)，它具有下述形式的定义和限制： 　　(1) 把N分为两个互斥的子集，即一组进程结点P={p1，p2，…，pn}和一组资源结点R={r1，r2，…，rn}，N=P∪R。在图3-20所示的例子中，P={p1，p2}，R={r1，r2}，N={r1，r2}∪{p1，p2}。 　　(2) 凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi，rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj，pi}是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。图3-13中示出了两个请求边和两个分配边，即E={(p1，r2)，(r2，p2)，(p2，r1)，(r1，p1)}。 　　我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的rj，而分配边则应始于方框中的一个点。图3-20示出了一个资源分配图。图中，p1进程已经分得了两个r1资源，并又请求一个r2资源；p2进程分得了一个r1和一个r2资源，并又请求r1资源。 图3-20　每类资源有多个时的情况 　　2．死锁定理 　　我们可以利用把资源分配图加以简化的方法(图3-21)，来检测当系统处于S状态时是否为死锁状态。简化方法如下： 　　(1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去pi所求的请求边和分配边，使之成为孤立的结点。在图3-21(a)中，将p1的两个分配边和一个请求边消去，便形成图(b)所示的情况。 图3-21　资源分配图的简化 　　(2) p1释放资源后，便可使p2获得资源而继续运行，直至p2完成后又释放出它所占有的全部资源，形成图(c)所示的情况。 　　(3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。 　　对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。同样可以证明：S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。 　3．死锁检测中的数据结构 　　死锁检测中的数据结构类似于银行家算