银行家算法避免死锁问题

操作系统笔记

算法实现

介绍

在死锁避免方法中,把系统的状态分为安全状态和不安全状态。系统处于安全状态,可以避免发生死锁;而当系统处于不安全状态时,则可能发生死锁。
死锁是要尽量避免的。

安全状态举例:

现有P1、P2、P3三个进程,它们需要一定的资源才能完成各自的任务,每一种资源一旦被一个进程占用,就不予许另外的进程申请,而当某一进程完成任务时,该进程占用的资源就会释放,也就是说资源可被其它的进程使用。如果三个进程都无妨申请资源以完成各自的任务,这三个进程就会发生死锁。

现在我们需要找到一条有效的执行序列,使得每一个进程都得以执行,不会出现无法申请资源而死锁。

进程 最大需求 已分配 还需要 可用
P1 10 5 5 3
P2 4 2 2 NULL
P3 9 2 7 NULL


最大需求:进程需要该数量资源才能执行
已分配:已经分配给该进程的资源数量
还需要:即进程一旦申请申请到该数量的资源就可以执行,也就是`还需要 = 最大需求 - 已分配
可用:系统中还可以的申请的资源数量,每个尚未完成的进程都可以申请

现在系统中还有3个资源可以被申请。此时,P1需要5个资源,P3需要7个资源,系统可分配的资源不足以分配使得它们执行,只能分配给还需资源数小于可分配数的P2进程。

这样,那就分配2个资源给P2进程,可分配资源还剩下1个。P2进程得到后可执行完成,接着就会释放4个资源,由此,系统可分配资源就增加到了5个。

P1进程还需要5个资源就可以执行完成,所以,我们就可以把可以分配的5个资源全部分配给P1进程,等P1进程执行完成释放10个资源后,可分配的资源就增加到了10个资源。

把可分配资源全部分配给P3进程,使得P3进程执行完成。可分配资源就增加到了12个,当然,不用去管这个问题了,因为我们的进程都已经执行完毕。

由此,我们可以找到一条安全的执行序列P2->P1->P3,使得三个进程得以安全的执行而不会发生死锁。

在分配资源给一个进程时,我们需要先尝试着是否能分配资源,如果分配资源后,剩下的资源不足以使得还未完成的进程形成一条安全的执行序列,这就说明此时我们不能分配,如果能够形成安全的序列,则可以分配。

某进程发出资源请求后,相应地可用资源减少,该进程的资源状态改变(也就是上面说的已分配、可用、还需资源数)。剩下的就是在所有进程中找到一条=使所有进程进入安全状态的执行序列。能找到,则可分配,否则不能。有个这个认识,我们就可以来说下银行家算法了。
(这段话是基于理论上的,实际上,要先确定能够分配,资源才会减少,但这并不会妨碍我们的解释)

当一个新进程进入系统时,它必须申明在运行过程中,可能需要的每种资源类型的最大单元数,这个数量不应该超过系统所拥有的资源总数,否则无法执行这个新进程。银行家算法来确定当这个新进程发出资源请求时,是否能够满足这个请求。

下面介绍下银行家算法中涉及到的数据结构。

名称 含义 例子
Available 一个含有M个元素的数组,每个元素代表每类资源的可用数量 [1,2,3,4]
Max 一个N*M的矩阵,Max[i][j]表示第i个进程需要的最大资源需求 [[1,2,3],[1,2,3],[1,2,3]]
Allocation 一个N*M的矩阵,Allocation[i][j]表示第i个进程已经分配了多少资源
Need 一个N*M的矩阵,Need[i][j]表示第i个进程还多少资源就可以参与执行

事实上,这跟我们开篇所提到的安全状态举例类似,我们可以把Max看一个单个的数组,代表每个进程最大资源需求数,当然,已经从一类资源变为多种资源。Allocation和Need也是一样。在银行家算法中使用矩阵统一表示是为了方便。

已知:Need = Max - Allocation

当一个进程完成后,系统将回收该进程占用的资源,即 Available = Available + Max。

银行家算法是为了避免进程死锁的,也就是说,系统提出资源请求时,会有一个Request数组,表示该进程请求的每类资源的数量。

注意:

  • Request <= Need,否则认为出错,因为它申请的资源(Request)不能大于它实际需要的资源(Need)。
  • Request <= Available,否则认为出错,因为此时申请的资源(Request)已经超过系统可分配的资源,它必须等待

举例说明

现系统中有5个进程,分别为P0、P1、P2、P3、P4和3类资源A、B、C。各类资源的数量分别为10、5、7。

具体情况见下表

表1

表1 资源情况 Max Allocation Need Available
- 进程 A B C A B C A B C A B C
- P0 7 5 3 0 1 0 7 4 3 3 3 2
- P1 3 2 1 2 0 0 1 2 2
- P2 9 0 2 3 0 2 6 0 0
- p3 2 2 2 2 1 1 0 1 1
- p4 4 3 3 0 0 2 4 3 1

现在我们要来找一条能够让这5个进程不发生死锁的执行序列。

需要知道一个进程一旦执行完毕,系统就可以收回该进程所占用的各类资源。所以或许我们可以总结出这样一条规则:总是将系统可以分配的资源全部分配给一个进程来帮助这个进程尽快执行完毕,这样等它执行完毕,系统就回收它占用的资源,从而就可以帮助其他需要资源的多的进程。也就是说,或许把资源分配给资源需求数少的进程是一种较优选择。

如此一来,仔细分析上述表格,我们可以推导出这样一条执行序列:

P1->P3->P4->P2->P0。

对应

表2:

表2 资源情况 Available Allocation Need Available + Allocation
- 进程 A B C A B C A B C A B C
- P1 3 3 2 2 0 0 1 2 2 5 3 2
- P3 5 3 2 2 1 1 0 1 1 7 4 3
- P4 7 4 3 0 0 2 4 3 1 7 4 5
- p2 7 4 5 3 0 2 6 0 0 10 4 7
- p0 10 4 7 0 1 0 7 4 3 10 5 7

问题一

此时P1请求资源,发出Request(1,0,2),请求1个A资源,0个B资源,2个C资源。

分析

  • Request(1,0,2) <= Need(1,2,2)
  • Request(1,0,2) <= Available(3 3 2)

现在假设可以为它分配资源,那么P1的资源状态会有如下变化:
表3:

表3 资源情况 Max Allocation Need Available
- 进程 A B C A B C A B C A B C
- P3 3 2 2 3 0 2 0 2 0 2 3 0

也就是Allocation中A+1,C+2,Need中A-1,C-2。

可以看到,此时,系统可以分配的资源就变为了Available(2,3,0)。知道了系统资源可分配量,我们就要在这5个进程中找一个安全序列。再次强调,如果可以找到,就说明假设的分配资源可以实现,否则不行。

接着看5个进程的Need资源量,从中我们要找到一个进程为它分配资源。

发现P3的Need(0,1,1) <= Available(2,3,0),如果将资源分配给他,P3进程得到资源后可立即执行,执行完毕后可释放资源,这也就意味着Available数量会增加,变化的Available(4,4 1),就可以分配给那些资源需求量大的进程。直到全部进程执行完毕。

表4:

表4 资源情况 Available Allocation Need Available + Allocation
- 进程 A B C A B C A B C A B C
- P1 2 3 0 3 0 2 0 2 0 5 3 2
- P3 5 3 2 2 1 1 0 1 1 7 4 3
- P4 7 4 3 0 0 2 4 3 1 7 4 5
- p2 7 4 5 3 0 2 6 0 0 10 4 7
- p0 10 4 7 0 1 0 7 4 3 10 5 7

安全序列:

  • P1->P3->P4->P2-P0
  • P1->P3->P4->P0->P2

可以响应请求。

问题二

P4发出请求Request(3,3,0)。
分析

  • Request(3,3,0) <= Need(4,3,1)
  • Request(3,3,0) > Available(2,3,0),不满足条件,让P4等待

不能响应请求。

问题三

P0发出请求Request(0,2,0)
分析

  • Request(0,2,0) <= Need(7,4,3)
  • Request(0,2,0) <= Available(2,3,0)

先假设可以分配资源,那么P0资源状态变化为

表5:

表5 资源情况 Max Allocation Need Available
- 进程 A B C A B C A B C A B C
- P0 7 5 3 0 3 0 7 2 3 2 1 0

此时的系统资源为Available(2,1,0),可以看到无法满足任何一个进程的Need请求。

不响应请求。

问题四

P0发出请求Request(0,1,0)
分析

  • Request(0,1,0) <= Need(7,4,3)
  • Request(0,1,0) <= Available(3,3,2)

可以找到这样一条安全序列
P1->P3->P4->P2->P0

表6:

表6 资源情况 Available Allocation Need Available + Allocation
- 进程 A B C A B C A B C A B C
- P1 3 2 2 2 0 0 1 2 2 5 2 2
- P3 5 2 2 2 1 1 0 1 1 7 3 3
- P4 7 3 3 0 0 2 4 3 1 7 3 5
- p2 7 3 5 3 0 2 6 0 0 10 3 7
- p0 10 3 7 0 2 0 7 3 3 10 5 7
-------------本文结束感谢您的阅读-------------
0%