阅读 ‧ 电子书库

6.4.2　每种类型多个资源的死锁检测

如果有多种相同的资源存在，就需要采用另一种方法来检测死锁。现在我们提供一种基于矩阵的算法来检测从P₁ 到P_n 这n个进程中的死锁。假设资源的类型数为m，E₁ 代表资源类型1，E₂ 代表资源类型2，E_i 代表资源类型i(1≤i≤m)。E是现有资源向量（existing resource vector），代表每种已存在的资源总数。比如，如果资源类型1代表磁带机，那么E₁ =2就表示系统有两台磁带机。

在任意时刻，某些资源已被分配所以不可用。假设A是可用资源向量（available resource vector），那么A_i 表示当前可供使用的资源数（即没有被分配的资源）。如果仅有的两台磁带机都已经分配出去了，那么A₁ 的值为0。

现在我们需要两个数组：C代表当前分配矩阵（current allocation matrix），R代表请求矩阵（request matrix）。C的第i行代表P_i 当前所持有的每一种类型资源的资源数。所以，C_ij 代表进程i所持有的资源j的数量。同理，R_ij 代表P_i 所需要的资源j的数量。这四种数据结构如图6-6所示。

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

这四种数据结构之间有一个重要的恒等式。具体地说，某种资源要么已分配要么可用。这个结论意味着：

换言之，如果我们将所有已分配的资源j的数量加起来再和所有可供使用的资源数相加，结果就是该类资源的资源总数。

死锁检测算法就是基于向量的比较。我们定义向量A和向量B之间的关系为A≤B以表明A的每一个分量要么等于要么小于和B向量相对应的分量。从数学上来说，A≤B当且仅当且A_i ≤B_i (0≤i≤m)。

每个进程起初都是没有标记过的。算法开始会对进程做标记，进程被标记后就表明它们能够被执行，不会进入死锁。当算法结束时，任何没有标记的进程都是死锁进程。该算法假定了一个最坏情形：所有的进程在退出以前都会不停地获取资源。

死锁检测算法如下：

1)寻找一个没有标记的进程P_i ，对于它而言R矩阵的第i行向量小于或等于A。

2)如果找到了这样一个进程，那么将C矩阵的第i行向量加到A中，标记该进程，并转到第1步。

3)如果没有这样的进程，那么算法终止。

算法结束时，所有没有标记过的进程（如果存在的话）都是死锁进程。

算法的第1步是寻找可以运行完毕的进程，该进程的特点是它有资源请求并且该请求可被当前的可用资源满足。这一选中的进程随后就被运行完毕，在这段时间内它释放自己持有的所有资源并将它们返回到可用资源库中。然后，这一进程被标记为完成。如果所有的进程最终都能运行完毕的话，就不存在死锁的情况。如果其中某些进程一直不能运行，那么它们就是死锁进程。虽然算法的运行过程是不确定的（因为进程可按任何行得通的次序执行），但结果总是相同的。

作为一个例子，在图6-7中展示了用该算法检测死锁的工作过程。这里我们有3个进程、4种资源（可以任意地将它们标记为磁带机、绘图仪、扫描仪和CD-ROM驱动器）。进程1有一台扫描仪。进程2有2台磁带机和1个CD-ROM驱动器。进程3有1个绘图仪和2台扫描仪。每一个进程都需要额外的资源，如矩阵R所示。

要运行死锁检测算法，首先找出哪一个进程的资源请求可被满足。第1个不能被满足，因为没有CD-ROM驱动器可供使用。第2个也不能被满足，由于没有打印机空闲。幸运的是，第3个可被满足，所以进程3运行并最终释放它所拥有的资源，给出

A=(2 2 2 0)

接下来，进程2也可运行并释放它所拥有的资源，给出

A=(4 2 2 1)

现在剩下的进程都能够运行，所以这个系统中不存在死锁。

假设图6-7的情况有所改变。进程2需要1个CD-ROM驱动器、2台磁带机和1台绘图仪。在这种情况下，所有的请求都不能得到满足，整个系统进入死锁。

现在我们知道了如何检测死锁（至少是在这种预先知道静态资源请求的情况下），但问题在于何时去检测它们。一种方法是每当有资源请求时去检测。毫无疑问越早发现越好，但这种方法会占用昂贵的CPU时间。另一种方法是每隔k分钟检测一次，或者当CPU的使用率降到某一域值时去检测。考虑到CPU使用效率的原因，如果死锁进程数达到一定数量，就没有多少进程可运行了，所以CPU会经常空闲。