资源分配图完整版本.docVIP

PAGE2

资源分配图

P

P1

表示:进程p1

R1表示

R1

R1P1表示

R1

P1

P1R1

P1

R1

R1P1表示：进程p1申请

R1

P1

P1R1表示：系统分配

P1

R1

R

R1

P1

P2

表示:系统分配一个R1资源给进程p2，然后又分配一个R1类资源给进程p1，最后进程p1收到一个R1类资源后又继续申请1个R1类资源，此时,还剩下一个R1类资源可以分配给P1，但还没分配给P1。（注意：图中P1的申请是还没得到响应的，不要以为R1指向P1的那个箭头是响应P1的申请,而分配了资源给P1）

P1R1R1

P1

R1

R1

P2P1

P2

P1

表示：系统分配一个R1资源给进程p2，然后又分配一个R1类资源给进程p1，最后进程p1收到一个R1类资源后又继续申请1个R1类资源，此时，系统已经没有R1类资源可以分配给进程P1了，于是p1进程受到阻塞。

（注意：千万不要误认为:

进程P1申请一个R1类资源，然后系统便分配一个R1类资源给P1。上图的“右箭头”跟“左箭头”是没任何关系的，并不是“右箭头响应左箭头的申请，而分配内存给P1”,先后顺序不能乱，时间顺序是先“分配一个R1类资源给P1”，再“P1申请一个R1类资源”；而不是先“P1申请一个R1类资源”，再“分配一个R1类资源给P1)

化简资源分配图

方法步骤：

先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的,接着把不阻塞的进程的所有边都去掉，形成一个孤立的点,再把系统分配给这个进程的资源回收回来，这样,系统剩余的空闲资源便多了起来，接着又去看看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。最后,所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。

如果一个图可完全简化，则不会产生死锁;如果一个图不可完全简化（即：图中还有“边”存在)，则会产生死锁.这就是“死锁定理”

例1

第一步:先看R1资源，它有三个箭头是向外的，因此它一共给进程分配了3个资源，此时，R1没有空闲的资源剩余。

第二步：再看R2资源，它有一个箭头是向外的，因此它一共给进程分配了1个资源，此时，R2还剩余一个空闲的资源没分配。

第三步：看完资源，再来看进程,先看进程P2,它只申请一个R1资源，但此时R1资源已经用光了，所以，进程P2进入阻塞状态，因此，进程P2暂时不能化成孤立的点。

第四步:再看进程P1，它只申请一个R2资源，此时，系统还剩余一个R2资源没分配，因此，可以满足P1的申请。这样，进程P1便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放.相当于：可以把P1的所有的边去掉，变成一个孤立的点,如下图所示：

第五步:进程P1运行完后，释放其所占有的资源（2个R1资源和1个R2资源）,系统回收这些资源后,空闲的资源便变成2个R1资源和1个R2资源，由于进程P2一直在申请一个R1资源，所以此时，系统能满足它的申请.这样，进程P2便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P2的所有的边都去掉，化成一个孤立的点，变成下图:

由于这个资源分配图可完全简化,因此,不会产生死锁。

例2

化简下面的进程--—资源图

第一步：先看R1资源，它有2个箭头是向外的，因此它一共给进程分配了2个资源，此时,R1没有空闲的资源剩余。

第二步：再看R2资源,它有2个箭头是向外的,因此它一共给进程分配了2个资源,此时，R2还剩余一个空闲的资源没分配。

第三步：看完资源,再来看进程,先看进程P1,它申请一个R1资源和一个R2资源，但此时R1资源已经用光了，所以，进程P2进入阻塞状态,因此，进程P2暂时不能化成孤立的点。

第四步:再看进程P2，它只申请一个R2资源，此时，系统还剩余一个R2资源没分配,因此，可以满足P2的申请。这样，进程P2便得到了它的全部所需资源，所以它不会进入阻塞状态,可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于:可以把P2的所有的边去掉，变成一个孤立