作为银行家的算法使用一些表，像分配，请求，可用的所有东西来了解什么是系统的状态。类似地，如果你想理解系统的状态而不是使用那些表，实际上表很容易表示和理解，但是你仍然可以在图中表示相同的信息。这个图被称为资源分配图(RAG)。
那么, 资源分配图向我们说明了系统的状态是什么
流程和资源
。就像有多少可用资源一样, 分配了多少资源, 每个进程的要求是什么。一切都可以用图表表示。拥有图表的优点之一是, 有时可以通过使用RAG直接看到死锁, 但是你可能无法通过查看表来了解死锁。但是, 如果系统包含大量进程和资源, 则表会更好；而如果系统包含较少数量的进程和资源, 则图会更好。
我们知道任何图都包含顶点和边。因此, RAG也包含顶点和边。在RAG中, 顶点有两种类型-
1.处理顶点– 每个过程都将被表示为一个过程顶点。通常, 该过程将以圆圈表示。
2.资源顶点– 每个资源都将表示为一个资源顶点。这也是两种类型–
- 单实例类型资源–它表示为一个盒子, 盒子内部会有一个点, 因此点的数量表示每种资源类型存在多少个实例。
- 多资源实例类型资源–它还表示为一个框, 在框内, 将存在许多点。
现在来到RAG的边缘。RAG中有两种类型的边缘-
1.分配边– 如果你已经将资源分配给进程, 则称为分配边缘。
2.请求边缘– 这意味着将来该进程可能需要一些资源来完成执行, 这称为请求边缘。
因此, 如果流程正在使用资源, 则会从资源节点向流程节点绘制一个箭头。如果流程正在请求资源, 则会从流程节点到资源节点绘制一个箭头。
示例1(单实例RAG)–
如果资源分配图中有一个循环, 并且循环中的每个资源仅提供一个实例, 那么进程将处于死锁状态。例如, 如果进程P1拥有资源R1, 进程P2拥有资源R2, 进程P1在等待R2, 进程P2在等待R1, 则进程P1和进程P2将处于死锁状态。
这是另一个示例, 它显示了进程P1和P2在获取资源R1和R2的同时, 进程P3正在等待获取这两种资源。在此示例中, 没有死锁, 因为没有循环依赖性。
因此, 单实例资源类型中的循环是发生死锁的充分条件。
示例2(多实例RAG)–
从上面的示例中, 不可能说出RAG处于安全状态或不安全状态。因此, 要查看该RAG的状态, 让我们构造分配矩阵和请求矩阵。
进程总数为三； P1, P2和P3以及资源总数为两个； R1和R2。
分配矩阵–
要构造分配矩阵, 只需转到资源并查看将其分配到哪个进程即可。
R1被分配给P1, 因此在分配矩阵中写入1, 类似地, R2被分配给P2和P3, 而对于其余元素, 只写0。
请求矩阵–
为了找出请求矩阵, 你必须转到该过程并查看输出边缘。
P1正在请求资源R2, 因此在矩阵中写入1, 类似地, P2请求R1, 其余元素则写入0。
因此, 现在可用资源为=(0, 0)。
检查死锁(是否安全)–
因此, 该RAG中没有死锁, 即使有周期也没有死锁, 因此在多实例资源循环中没有足够的死锁条件。
除了请求资源R1的过程P3之外, 上述示例与先前示例相同。
因此, 该表如下所示。
因此, 可用资源为=(0, 0), 但要求为(0, 1), (1、0)和(1, 0)。因此你无法满足任何一项要求。因此, 它处于死锁状态。
因此, 多实例资源类型图中的每个周期都不是死锁, 如果必须要有死锁, 则必须有一个周期, 因此, 对于具有多实例资源类型的RAG而言, 该周期是必要的僵局的条件, 但还不够。
GATE CS Corner问题
练习以下问题将帮助你测试知识。在前几年的GATE或GATE模拟测试中, 所有问题都已提出。强烈建议你练习它们。
- GATE CS 2009, 问题60
- GATE CS 2014(Set 1), 问题65
参考–
操作系统概念(第8版)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
