避免死锁之——银行家算法

亦凉 2022-12-12 13:54 226阅读 0赞

## 一 概述 ##

银行家算法是最具有代表性的避免死锁的算法，原本运用于银行系统，以确保银行在发放现金贷款时，不会发生不能满足用户需求的情况。

为了实现银行家算法，每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

## 二 银行家算法所需的数据结构 ##

银行家算法中必须设置的四个数据结构：系统中的可利用资源，所有进程对资源的最大需求，系统中的资源分配，以及所有进程还需要多少资源的情况。

**可利用资源向量Available：**这是一个含有m个元素的数组，其中的每个元素代表一类可利用的资源数目。其初始值为系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available\[j\] = K，则表示系统中现有的Rj类资源为K个。

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

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

**需求矩阵Need：**同样为一个n\*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need\[i，j\] = K，则表示进程i还需要Rj类资源数为K才能够完成其任务。

Need\[i，j\] = Max\[i，j\] - Allocation\[i，j\]

## 三 银行家算法 ##

设Request为进程i的请求向量，如果Request\[j\]=K，表示进程i需要K个Rj类型的资源。当进程i发出资源请求之后，系统需要进行下述步骤进行检查：

1.  如果Request\[j\]<=Need\[i，j\]，便转向步骤2，否则认为出错，因为它所需的资源数已经超过它所宣布的最大值。
2.  如果Request\[j\]<=Available\[j\]，便转向步骤3，否则表示尚无足够资源，i进程须等待。
3.  系统试探着把资源分配给进程i，并对资源数根据分配情况动态进行更改。

Available\[j\] = Avaiable\[j\] - Request\[i，j\]；

Allocation\[i，j\] = Allocation\[i，j\] + Request\[j\]；

Need\[i，j\] = Need\[i，j\] - Request\[j\]。

**系统执行的安全性检查：**检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程i，并结束资源分配任务；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程i进行等待。

## 四 银行家算法的实现 ##

待续

参考资料：计算机操作系统第四版 汤小丹，梁红兵，哲凤屏，汤子瀛编著

发表评论取消回复

表情：

评论列表（有 0 条评论，226人围观）

还没有评论，来说两句吧...

相关阅读

相关操作系统2.4.3 避免死锁（银行家算法）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d18

红太狼/ 2023年02月20日 12:22/ 0 赞/ 10 阅读

相关 2.22死锁的处理策略——避免死锁（银行家算法）

1，什么是安全序列所谓的安全序列，就是指系统如果按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就处于安全状态。当然安全序列可以有多个 2

水深无声/ 2023年02月16日 06:35/ 0 赞/ 13 阅读

相关操作系统--死锁避免（银行家算法）

可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的

深碍√TFBOYSˉ_/ 2023年01月01日 08:51/ 0 赞/ 146 阅读

相关如何避免死锁（死锁检测算法） —— 银行家算法

一，死锁概念死锁指的是两个或两个以上的进程在对临界资源竞争或者通信过程中，因为某些处理不当，而造成各个进程彼此等待，无法继续向下推进，此使系统处于死锁状态，这些互相

Myth丶恋晨/ 2022年12月16日 09:19/ 0 赞/ 283 阅读

相关避免死锁之——银行家算法

一概述银行家算法是最具有代表性的避免死锁的算法，原本运用于银行系统，以确保银行在发放现金贷款时，不会发生不能满足用户需求的情况。为了实现银行家算法，每一个新进程在

亦凉/ 2022年12月12日 13:54/ 0 赞/ 227 阅读

相关操作系统：银行家算法（避免死锁）

[算法][Link 1]介绍： ![Center][]![Center 1][]![Center 2][] 程序实现： \[cpp\] [view plain][

红太狼/ 2022年07月16日 10:26/ 0 赞/ 277 阅读

相关避免死锁的银行家算法

死锁的定义> 如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那仫该组进程就是死锁的. 产生死锁的必要条件> 1).互斥条件:进程对所分配到

待我称王封你为后i/ 2022年07月14日 08:51/ 0 赞/ 217 阅读

相关预防死锁的银行家算法

安全与不安全状态安全状态：如果没有死锁发生，并且即使所有的进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每个进程运行完毕，那么称该状态安全。 ![这里

心已赠人/ 2022年05月29日 08:45/ 0 赞/ 242 阅读

相关操作系统：银行家算法避免死锁

银行家算法是用来避免死锁的，该方法将系统的状态分为安全和不安全，只要系统处于安全状态，便可避免死锁的发生。之所以成为银行家算法，是由于该算法能用于银行系统现金贷款的发放而得名。

雨点打透心脏的1/2处/ 2022年04月16日 06:12/ 0 赞/ 328 阅读

相关操作系统之死锁的避免-银行家算法详解

1.银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该

布满荆棘的人生/ 2021年10月01日 04:56/ 0 赞/ 372 阅读