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

2021年4月1日15:06:39 发表评论 1,908 次浏览

作为银行家的算法使用一些表,像分配,请求,可用的所有东西来了解什么是系统的状态。类似地,如果你想理解系统的状态而不是使用那些表,实际上表很容易表示和理解,但是你仍然可以在图中表示相同的信息。这个图被称为资源分配图(RAG)。

那么, 资源分配图向我们说明了系统的状态是什么

流程和资源

。就像有多少可用资源一样, 分配了多少资源, 每个进程的要求是什么。一切都可以用图表表示。拥有图表的优点之一是, 有时可以通过使用RAG直接看到死锁, 但是你可能无法通过查看表来了解死锁。但是, 如果系统包含大量进程和资源, 则表会更好;而如果系统包含较少数量的进程和资源, 则图会更好。

我们知道任何图都包含顶点和边。因此, RAG也包含顶点和边。在RAG中, 顶点有两种类型-

1.处理顶点– 每个过程都将被表示为一个过程顶点。通常, 该过程将以圆圈表示。

2.资源顶点– 每个资源都将表示为一个资源顶点。这也是两种类型–

  • 单实例类型资源–它表示为一个盒子, 盒子内部会有一个点, 因此点的数量表示每种资源类型存在多少个实例。
  • 多资源实例类型资源–它还表示为一个框, 在框内, 将存在许多点。
操作系统中的资源分配图(RAG)1

现在来到RAG的边缘。RAG中有两种类型的边缘-

1.分配边– 如果你已经将资源分配给进程, 则称为分配边缘。

2.请求边缘– 这意味着将来该进程可能需要一些资源来完成执行, 这称为请求边缘。

操作系统中的资源分配图(RAG)2

因此, 如果流程正在使用资源, 则会从资源节点向流程节点绘制一个箭头。如果流程正在请求资源, 则会从流程节点到资源节点绘制一个箭头。

示例1(单实例RAG)–

操作系统中的资源分配图(RAG)3

如果资源分配图中有一个循环, 并且循环中的每个资源仅提供一个实例, 那么进程将处于死锁状态。例如, 如果进程P1拥有资源R1, 进程P2拥有资源R2, 进程P1在等待R2, 进程P2在等待R1, 则进程P1和进程P2将处于死锁状态。

操作系统中的资源分配图(RAG)4

这是另一个示例, 它显示了进程P1和P2在获取资源R1和R2的同时, 进程P3正在等待获取这两种资源。在此示例中, 没有死锁, 因为没有循环依赖性。

因此, 单实例资源类型中的循环是发生死锁的充分条件。

示例2(多实例RAG)–

操作系统中的资源分配图(RAG)5

从上面的示例中, 不可能说出RAG处于安全状态或不安全状态。因此, 要查看该RAG的状态, 让我们构造分配矩阵和请求矩阵。

操作系统中的资源分配图(RAG)6

进程总数为三; P1, P2和P3以及资源总数为两个; R1和R2。

分配矩阵–

要构造分配矩阵, 只需转到资源并查看将其分配到哪个进程即可。

R1被分配给P1, 因此在分配矩阵中写入1, 类似地, R2被分配给P2和P3, 而对于其余元素, 只写0。

请求矩阵–

为了找出请求矩阵, 你必须转到该过程并查看输出边缘。

P1正在请求资源R2, 因此在矩阵中写入1, 类似地, P2请求R1, 其余元素则写入0。

因此, 现在可用资源为=(0, 0)。

检查死锁(是否安全)–

hgh-1

因此, 该RAG中没有死锁, 即使有周期也没有死锁, 因此在多实例资源循环中没有足够的死锁条件。

操作系统中的资源分配图(RAG)7

除了请求资源R1的过程P3之外, 上述示例与先前示例相同。

因此, 该表如下所示。

操作系统中的资源分配图(RAG)8

因此, 可用资源为=(0, 0), 但要求为(0, 1), (1、0)和(1, 0)。因此你无法满足任何一项要求。因此, 它处于死锁状态。

因此, 多实例资源类型图中的每个周期都不是死锁, 如果必须要有死锁, 则必须有一个周期, 因此, 对于具有多实例资源类型的RAG而言, 该周期是必要的僵局的条件, 但还不够。

GATE CS Corner问题

练习以下问题将帮助你测试知识。在前几年的GATE或GATE模拟测试中, 所有问题都已提出。强烈建议你练习它们。

  1. GATE CS 2009, 问题60
  2. GATE CS 2014(Set 1), 问题65

参考–

操作系统概念(第8版)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: