资源分配图.ppt

《资源分配图.ppt》由会员分享，可在线阅读，更多相关《资源分配图.ppt（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、资源分配图的组成资源分配图的组成n n资源分配图是由顶点和边的结对组成的有向图：资源分配图是由顶点和边的结对组成的有向图：G=G=（V V，E E）式中）式中V V是顶点的集合，是顶点的集合，E E是边的集合。是边的集合。n n顶点集合分为两部分顶点集合分为两部分：（：（1 1）P=P1,P2,P=P1,P2,PnPn,它由进程集合所有活动它由进程集合所有活动进程组成。进程组成。R=r1,r2,R=r1,r2,rmrm,它由进程集合所涉及的全部资源类型组成。它由进程集合所涉及的全部资源类型组成。边集合分为以下两种：申请边边集合分为以下两种：申请边Pi-Pi-rj rj,表示进程表示进程PiPi

2、申请一个单位的申请一个单位的rj rj资源，资源，但当前但当前PiPi在等待该资源。赋给边在等待该资源。赋给边rj rj-pi:-pi:表示有一个单位的表示有一个单位的rj rj资源已分配资源已分配给进程给进程PiPi。r1r3r2r4P1P2P3n n上图所示为资源分配图，通常用圆圈表示进程，用方框表上图所示为资源分配图，通常用圆圈表示进程，用方框表示资源（一个方框表示一类资源，其中的黑点表示单个资示资源（一个方框表示一类资源，其中的黑点表示单个资源实体）。注意申请边要指向表示资源的方框，赋给边必源实体）。注意申请边要指向表示资源的方框，赋给边必须起于方框中的一个黑点。上图给出了下列的信息：

3、须起于方框中的一个黑点。上图给出了下列的信息：n nP=p1,p2,p3P=p1,p2,p3n nR=r1,r2,r3,r4,R=r1,r2,r3,r4,且各类资源的个数分别为且各类资源的个数分别为1 1，2 2，1 1和和3 3n nE=p1-r1,p2-r3,r1-p2,r2-p2,r2-p2,r2-p1,r3-p3,E=p1-r1,p2-r3,r1-p2,r2-p2,r2-p2,r2-p1,r3-p3,即：即：进程进程P1P1占有一个占有一个r2r2资源，且等待一个资源，且等待一个r1r1资源。进程资源。进程P2P2占有占有r1r1和和r2r2资源各一个，且等待一个资源各一个，且等待一个

4、r3r3资源。进程资源。进程P3P3占有一个占有一个r3r3资源。资源。环路与死锁环路与死锁n n利用资源分配图可以直观，精确地描述死锁。对每种类型利用资源分配图可以直观，精确地描述死锁。对每种类型只有一个资源的系统（如只有一台扫描仪，一台只有一个资源的系统（如只有一台扫描仪，一台CDCD刻录刻录机，一台绘图仪）构造的资源分配图中，如果出现环路就机，一台绘图仪）构造的资源分配图中，如果出现环路就说明存在死锁。在此环路中的每个进程都是死锁进程。如说明存在死锁。在此环路中的每个进程都是死锁进程。如果没有出现环路，系统就没有发生死锁。果没有出现环路，系统就没有发生死锁。P1P2P3P4r1r2n n

5、如果每类资源的实体不止一个，那么资源分配图如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。在这种情况中出现环路并不表明一定出现死锁。在这种情况下，资源分配图中存在环路是死锁存在的必要条下，资源分配图中存在环路是死锁存在的必要条件，但不是充分条件。在上上图中，存在两个最件，但不是充分条件。在上上图中，存在两个最小的环：小的环：P1-r1-p2-r3-p3-r2-p1P1-r1-p2-r3-p3-r2-p1和和p2-r3-p2-r3-p3-r2-p2p3-r2-p2。此时系统发生死锁，进程。此时系统发生死锁，进程p1,p2p1,p2和和p3p3都在环中，因而都是死锁进程。都在环中，因而都是死锁进程。n n再看一下上图，其中也有一个环路：再看一下上图，其中也有一个环路：p1-r1-p3-p1-r1-p3-r2-p1r2-p1然而，没有出现死锁。因为进程然而，没有出现死锁。因为进程p4p4能释放能释放它占有的资源它占有的资源r2,r2,然后就可以将然后就可以将r2r2分给分给p3,p3,这样环路这样环路就打开了。就打开了。n n总之，如果资源分配图中没有环路，那么系统就总之，如果资源分配图中没有环路，那么系统就不会陷入死锁状态。如果存在环路，那么系统就不会陷入死锁状态。如果存在环路，那么系统就有可能出现死锁。有可能出现死锁。