资源分配图.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,资源分配图的组成,资源分配图是由顶点和边的结对组成的有向图：,G=,（,V,，,E,）式中,V,是顶点的集合，,E,是边的集合。,顶点集合分为两部分,：（,1,）,P=P1,P2,Pn,它由进程集合所有活动进程组成。,R=r1,r2,rm,它由进程集合所涉及的全部资源类型组成。边集合分为以下两种：申请边,Pi-,rj,表示进程,Pi,申请一个单位的,rj,资源，但当前,Pi,在等待该资源。赋给边,rj,-pi:,表示有一个单位的,rj,资源已分配给进程,Pi,。,r1,r3,r2,r4,P1,P2,P3,上图所示为资源分配图，通常用圆圈表示进程，用方框表示资源（一个方框表示一类资源，其中的黑点表示单个资源实体）。注意申请边要指向表示资源的方框，赋给边必须起于方框中的一个黑点。上图给出了下列的信息：,P=p1,p2,p3,R=r1,r2,r3,r4,且各类资源的个数分别为,1,，,2,，,1,和,3,E=p1-r1,p2-r3,r1-p2,r2-p2,r2-p2,r2-p1,r3-p3,即：进程,P1,占有一个,r2,资源，且等待一个,r1,资源。进程,P2,占有,r1,和,r2,资源各一个，且等待一个,r3,资源。进程,P3,占有一个,r3,资源。,环路与死锁,利用资源分配图可以直观，精确地描述死锁。对每种类型只有一个资源的系统（如只有一台扫描仪，一台,CD,刻录机，一台绘图仪）构造的资源分配图中，如果出现环路就说明存在死锁。在此环路中的每个进程都是死锁进程。如果没有出现环路，系统就没有发生死锁。,P1,P2,P3,P4,r1,r2,如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。在这种情况下，资源分配图中存在环路是死锁存在的必要条件，但不是充分条件。在上上图中，存在两个最小的环：,P1-r1-p2-r3-p3-r2-p1,和,p2-r3-p3-r2-p2,。此时系统发生死锁，进程,p1,p2,和,p3,都在环中，因而都是死锁进程。,再看一下上图，其中也有一个环路：,p1-r1-p3-r2-p1,然而，没有出现死锁。因为进程,p4,能释放它占有的资源,r2,然后就可以将,r2,分给,p3,这样环路就打开了。,总之，如果资源分配图中没有环路，那么系统就不会陷入死锁状态。如果存在环路，那么系统就有可能出现死锁。,