操作系统中的资源分配图（RAG）详细指南

作为银行家的算法使用一些表，像分配，请求，可用的所有东西来了解什么是系统的状态。类似地，如果你想理解系统的状态而不是使用那些表，实际上表很容易表示和理解，但是你仍然可以在图中表示相同的信息。这个图被称为资源分配图(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模拟测试中, 所有问题都已提出。强烈建议你练习它们。