化简资源分配图判断是否发生死锁

化简资源分配图判断是否发生死锁

引用

CSDN

1.

https://m.blog.csdn.net/weixin_69884785/article/details/139144181

在计算机系统中，死锁是一个常见的问题，它会导致系统资源无法有效利用，严重影响系统的性能和稳定性。本文将通过资源分配图这一工具，帮助读者理解如何判断系统是否发生死锁。

资源分配图的概念

资源分配图表示进程和资源之间的请求关系，例如下图：

• P代表进程，R代表资源，R方框中 有几个圆球就表示有几个这种资源，在图中，R1指向P1，表示R1已经分配了一个资源给P1了，R1指向P1的边叫做分配边（资源-->进程）；P1指向R2，表示P1还需要一个R2才能执行，P1指向R2的边叫做请求边（进程-->资源）。

• 阻塞节点：某进程中所请求的资源已全部分配完毕，无法获取所需资源，则该进程被阻塞了无法继续执行，如上图P2。

• 非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中P1，P3。当一个进程资源图中所有进程都是阻塞节点时，即进入死锁状态。

说明一下：
上面的图表示，系统分配一个 R1 资源给进程 p2，然后又分配一个 R1类资源给进程 p1,
最后进程 p1 收到一个 R1 类资源后又继续申请1个R1类资源，此时，还剩下一个 R1类资源可以分配给 P1，但还没分配给 P1。(注意：图中P1的申请是还没得到响应的，不要以为 R1 指向P1的那个箭头是响应 P1的申请，而分配了资源给 P1)。“右箭头”跟“左箭头”是没任何关系的。
也就是先分配，再看进程的请求是否能够被满足。如果某个进程的请求能被满足，那么这个进程就是非阻塞节点，不能被满足，就是阻塞节点。

判断是否发生死锁

判断下图是否存在死锁：

1. 先看资源，r1分配了2个资源给p1，分配了1个资源给p2，无剩余资源；r2分配了1个资源给p2，还剩1个资源。
2. 再看p1进程，p1向r2申请了一个资源，r2刚好剩余一个资源，p1是非阻塞节点。删去所有与p1相连的边。
3. 再看p2进程，p2向r1申请1个资源，由于p1释放了r1资源，r1还剩余2个资源，p2节点能够申请到资源，所以p2也是非阻塞节点。

再看下面这个例子：

1. 对于r1，分配了2个资源，剩余1个资源。对于r2，分配了1个资源，剩余2个资源。
2. 先看p1，p1向r1申请了1个资源，r1刚好剩余1个资源，向r2申请1个资源，而r2剩余2个资源，绰绰有余。所以p1是非阻塞节点。p1进程完成后，释放资源。

3. 此时r1剩余2个资源，r2剩余2个资源，p2可以申请到r1的1个资源，p2非阻塞。

当所有的点都处于“孤立状态”，那么这个进程不存在死锁。

若资源分配图如下图所示，也就是对于p2而言，只有分配边，没有请求边：

那么可以直接“孤立”这一进程：

总结

1. 先将分配给进程，再看进程的请求（顺序一定不能乱）。
2. 对于较复杂的资源分配图，当一个进程是非阻塞节点时，可以想将它“孤立”起来。
3. 进程请求资源才可能发生死锁，所以只有分配边没有请求边的进程节点可以直接“孤立”起来。

利用上面的总结，做一下题吧：

1. 下面的进程资源图是（）

1. R1无剩余资源，R2无剩余资源，R3剩余1个资源。

2. 由于R1，R2都没有资源分配了，突破口就来自R3，先看连接R3的请求边：
   P3向R3请求1个资源，R3刚好剩余1个资源，P3是非阻塞节点。P3“孤立”起来。

3. 重新计算一下剩余资源，R1剩余1个资源，R2剩余1个资源，首先看P1，P1向R2申请了1个资源，可以被满足。“孤立”p1。

4. 剩下的资源对P2而言绰绰有余了，所以P2也不会阻塞，所以这个资源分配图不存在死锁。

5. 系统中有3个不同的临界资源R1,R2,R3，被4个进程p1，p2，p3，p4共享。各进程对资源的需求为：p1申请R1和R2；p2申请R2和R3，p3申请R1和R3，p4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是（）
   A. 1 B. 2 C. 3 D. 4
   答案：C

解答：

1. 根据题目，画出的资源分配图如下：

2. P4不影响系统最终状态，只要给它分配资源，完成后就会释放资源。所以，不管给不给P4分配资源，最终三类资源都是在P1，P2，P3之间进行分配。简化资源分配图：

第一种情况：形成循环

由于题目中没有给出各类资源的具体个数，P2申请1个R2资源和1个R3资源，这里我们假设R3给到了P2一个资源，同理，R2给P1一个资源，R1给了P3一个资源，这样就形成了循环，发生死锁。三个进程都无法进行，因为只要有一个进程申请的资源得到满足，完事后就会释放相邻的资源。循环状态就被破坏了，没有循环，一定不会发生死锁。

补充：死锁的必要条件

1. 互斥 2. 不可剥夺 3. 请求和保存 4. 循环

第二种情况：没有形成循环

若没有形成循环，可以完全化简成孤立状态的，即不会发生死锁。

所以若资源分配图死锁，那么至少P1,P2,P3进程处于死锁。若没有事先给P4分配进程，那么处于死锁状态的进程为P1,P2,P3,P4。

3. 假定某计算机系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4这4个进程互斥共享，且已知这4个进程均以下面所示的顺序使用现有设备：

一>申请R1一>申请R2一>申请R1一>释放R1一>释放R2一>释放R1

请问系统运行过程中是否可能产生死锁?如果有可能的话，请举出一种情况，并画出表示该死锁状态的资源分配图。

首先p1，p2，p3，p4都申请r1资源，但是r1只有3个资源：

所以这里假设只有p1，p2，p3被分配到了资源：

由于p4没有被分配到r1资源，所以接下来的步骤也不能完成。接下来p1，p2，p3继续申请r2资源，由于r2有4个资源，所以p1，p2，p3也能被分配到r2资源：

接下来p1，p2，p3会继续申请r1资源，由于r1已经没有资源可以分配了，进而发生死锁。

4. 系统中有5个资源(R1~R5)，现有进程p1依次申请R1, R5，R3；p2依次申请 R3,R4,R2；p3依次申请 R2，R5。

当 3个进程并发执行时有可能发生死锁吗?为什么?

依照题目画出的资源分配图，如下所示：

由于是并发执行，R1先给p1资源，R3给p2资源，R2给p3资源：

接下来，若R5再给p1分配资源，就会导致循环，必定发生死锁。

若是在这之前，R5先分配资源给p3，p3进程完成后，释放资源，就不会发生死锁：

5. 系统中有3个不同的临界资源R1，R2和R3，被4个进程P1,P2,P3,P4共享。各进程对资源的需求为:P1申请R1和R2，P2申请R2和R3，P3申请R1和R3，P4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是（）
   A.1 B.2 C.3 D.4

从图中可以看出，若出现循环等待的情况，则至少有P1、P2、P三个进程在循环等待环中，在该图中不可能出现两个进程发生循环等待的情况。现在考察P1、P2、P3三个进程形成环路的情况：

① 若此时 P1、P2、P3三个进程分别拥有 R1、R2和 R3，则会形成P1 等待 P2释放 R2；P2等待 P3释放 R3；P3等待 P1释放 R1 的循环等待情况。

② P1、P2、P3三个进程分别拥有 R2、R3和R1的情况的分析类似。

以上两种情况都会形成循环等待情况，至少有三个进程陷入死锁状态。① 若P4事先已获取 R2，成功运行，则死锁进程数为3；② 若P4尚未获取R2，未运行，则死锁进程数为4。故若系统出现死锁，则处于死锁状态的进程至少是3个。