第3章-处理机调度与死锁.pptVIP

图3-16T0时刻的安全序列(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-15中的圆括号所示；

④再利用安全性算法检查此时系统是否安全，如图3-17所示。图3-17P1申请资源时的安全性检查(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发出请求向量Request0(0，2，0)，系统按银行家算法进行检查：

①Request0(0，2，0)≤Need0(7，4，3)；

②Request0(0，2，0)≤Available(2，3，0)；

③系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。图3-18为P0分配资源后的有关资源数据(5)进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。?3.8死锁的检测与解除

如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。在这种情况下，系统应当提供两个算法：

①死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。

②死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。3.8.1死锁的检测

为了能对系统中是否已发生了死锁进行检测，在系统中必须：①保存有关资源的请求和分配信息；②提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。

1.资源分配图(ResourceAllocationGraph)

系统死锁，可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G?=?(N,E)，它具有下述形式的定义和限制：

(1)把N分为两个互斥的子集，即一组进程结点P={P1,P2,…,Pn}和一组资源结点R={R1,R2,…,Rn}，N?=?P∪R。在图3-19所示的例子中，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-19中示出了两个请求边和两个分配边，即E?=?{(P1,R2),(R2,P2),(P2,R1),(R1,P1)}。图3-19每类资源有多个时的情况2．死锁定理

我们可以利用把资源分配图加以简化的方法(图3-19)，来检测当系统处于S状态时，是否为死锁状态。简化方法如下：

(1)在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi的请求边和分配边，使之成为孤立的结点。在图3-20(a)中，将P1的两个分配边和一个请求边消去，便形成图(b)所示的情况。图3-20资源分配图的简化(2)?P1释放资源后，便可使P2获得资源而继续运行，直至P2完成后又释放出它所占有的全部资源，形成图(c)所示的情况，即将P2的两条请求边和一条分配边消去。

(3)在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的（相当于安全序列）；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。

死锁定理：如果某一时刻系统的资源分配图是不可简化的，那么此时系统死锁。3．死锁检测中的数据结构

死锁检测中的数据结构类似于银行家算法中的数据结构：

(1)可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。

(2)把不占用资源的进程(向量Allocation=0)记入L表中，即Li∪L。

(3)从进程集合中找到一个Requesti