admin 管理员组文章数量: 887021
1. 什么是银行家算法
- 银行家算法是一种用来避免操作系统死锁出现的有效算法。
2. 死锁
- 指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法进行下去，此时称系统处于死锁状态或系统产生了死锁，称互相等待的进程称为死锁进程。
2.1 死锁产生的四个必要条件
- 互斥条件：在一段时间内某资源只由一个进程占用，如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
- 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
- 不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
- 循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{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. 银行家算法的数据结构
-
可利用资源向量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个方能完成其任务。最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need三者之间的关系：Need[i][j] = Max[i][j] - Allocation[i][j]
4.1 两个向量
- 工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，安全算法开始时：Work = Available。
- Finish[]：表示系统是否有足够的资源分配给进程使之运行完成。开始时先令Finish[i] = false，当有足够资源分配给进程时，再令Finish[i] = true。
5. 银行家算法
设Request[i]是进程Pi的请求向量，如果Request[i][j]=k，表示进程Pi需要K个Rj类型的资源。当Pi发现资源请求后系统将进行下列步骤：
- 如果Request[i][j] <= Need[i][j]，边转向步骤2)，否则出错，因为它所请求的资源数已超过它所宣布的最大值。
- 如果Request[i][j] <= Available[i][j]，便转向步骤3)，否则，表示尚无足够资源，Pi需等待。
- 系统试探着把资源分配给进程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]; - 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
【例题】
题目解析：
因为系统资源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需求量，因此系统无法进行分配。
版权声明：本文标题：【操作系统】银行家算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727375804h1110762.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论