您的位置: 首页  >  文章  >  【操作系统】银行家算法

【操作系统】银行家算法

分类: 文章 • 2024-02-08 22:27:40

1. 什么是银行家算法

  • 银行家算法是一种用来避免操作系统死锁出现的有效算法。

2. 死锁

  • 指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法进行下去，此时称系统处于死锁状态或系统产生了死锁，称互相等待的进程称为死锁进程。
2.1 死锁产生的四个必要条件
  1. 互斥条件：在一段时间内某资源只由一个进程占用，如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
  2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
  3. 不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  4. 循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

3. 安全序列

  • 指一个进程序列{P1，…，Pn}是安全的，即对每一个进程Pi(1≤i≤n），它需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
3.1 安全状态
  • 如果存在一个由系统中所有进程构成的安全序列{P1，…，Pn}，则系统处于安全状态；
  • 安全状态一定是没有死锁发生。
3.2 不安全状态
  • 不存在一个安全序列；
  • 不安全状态不一定导致死锁。

4. 银行家算法的数据结构

  1. 可利用资源向量Available

    含有m个元素的数组，其中每一个元素代表一类可利用的资源数目；
    如果Available[j]=K，则表示系统中现有Rj类资源K个。

  2. 最大需求矩阵Max

    一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求；
    如果Max[i][j]=K，则表示进程i需要Rj类资源的最大数目为K。

  3. 分配矩阵Allocation

    一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数;
    如果Allocation[i][j]=K，则表示进程i当前已分得Rj类资源的数目为K。

  4. 需求矩阵Need

    一个n×m的矩阵，用以表示每一个进程需要的各类资源数；
    如果Need[i][j]=K，则表示进程i还需要Rj类资源K个方能完成其任务。

    最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need三者之间的关系：Need[i][j] = Max[i][j] - Allocation[i][j]

4.1 两个向量
  1. 工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，安全算法开始时：Work = Available。
  2. Finish[]：表示系统是否有足够的资源分配给进程使之运行完成。开始时先令Finish[i] = false，当有足够资源分配给进程时，再令Finish[i] = true。

5. 银行家算法

设Request[i]是进程Pi的请求向量，如果Request[i][j]=k，表示进程Pi需要K个Rj类型的资源。当Pi发现资源请求后系统将进行下列步骤：

  1. 如果Request[i][j] <= Need[i][j]，边转向步骤2)，否则出错，因为它所请求的资源数已超过它所宣布的最大值。
  2. 如果Request[i][j] <= Available[i][j]，便转向步骤3)，否则，表示尚无足够资源，Pi需等待。
  3. 系统试探着把资源分配给进程Pi，并需要修改下面数据结构中的数值；
    Available[j] = Available[j] - Request[i][j];
    Allocation[i][j]] = Allocation[i][j] + Request[i][j];
    Need[i][j]] = Need[i][j] - Request[i][j];
  4. 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。

【例题】
【操作系统】银行家算法

题目解析：
因为系统资源R =（17，5，20）而系统分配给这几个线程的资源为Allocation = (15，2，17)，则可以求出Available=（2，3，3）
【操作系统】银行家算法
（1）T0时刻是否为安全状态？若是，则给出安全序列：

是安全状态，安全序列为：{P5、P4、P3、P2、P1}；
在T0时刻，Work = Available，由于Available大于等于Need中P5（1，1，0）所在行的向量，因此Available能满足P5的运行，在P5运行后，系统的状态变更为如下图所示：
【操作系统】银行家算法
（2）T0时刻若P2请求【0，3，4】，能否实施分配？为什么？

由于P2请求资源为（0，3，4）<= P2的需求资源（1，3，4）；
由于P2请求资源为（0，3，4）>= P2的可以利用资源（2，3，3）；
综上所述，该申请无法实施分配，会使系统进入不安全状态。

（3）在（2）的基础上P4请求（2，0，1），能否实施分配？为什么？

处于安全状态：存在安全序列为：{P4、P5、P3、P2、P1}；
Reuqest(i)（2，0，1）<= Need(i)（2，2，1）；
Reuqest(i)（2，0，1） <= Availabel（2，3，3）；
对 P4 请求（2，0，1）进行预分配后，系统的状态为：

可利用资源向量Availabel =（0，3，2）（Available[j] = Available[j] - Request[i][j] -> (2，3，3) - (2，0，1））大于Need中 P4 所在行的向量（0，2，0）（Need[i][j]] = Need[i][j] - Request[i][j] -> (2，2，1) -（2，0，1）），Allocation[i][j]] = Allocation[i][j] + Request[i][j] -> （4，0，5），因此可以满足 P4 的运行，P4 运行结束后，系统的状态变为：
【操作系统】银行家算法
（4）在（3）基础上P1请求（0，2，0），能否实施分配？为什么？

Request(i) (0，2，0) <= Need(i)（3，4，7）；
Request(i) (0，2，0) <= Availabel（2，3，3）；
对 P1 的申请（0，2，0）进行预分配后，系统的状态为：
(4)是建立在第(3)问的基础上的，所以Available =（0，3，2）-（0，2，0）=（0，1，2）；
Available小于所有进程的need需求量，因此系统无法进行分配。
【操作系统】银行家算法

相关推荐