![cover](https://img-blog.csdnimg.cn/184cd588b3304cb0abb82ca1f6e56ac3.png)
【银行家算法-安全性算法】
1. 银行家算法介绍银行家算法是最具代表性的避免死锁的算法,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态则分配,否则等待。银行家算法中四个数据结构可利用资源向量 Available长度为m的向量,如果 Available[j] = K,则表示系统中资源R(j)现在有K个;最大需求矩阵 Max是一个n x m的矩阵,定义系统中n个
1. 银行家算法
介绍
- 银行家算法是最具代表性的避免死锁的算法,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态则分配,否则等待。
银行家算法中四个数据结构
-
可利用资源向量 Available
长度为m的向量,如果 Available[j] = K,则表示系统中资源R(j)现在有K个;
-
最大需求矩阵 Max
是一个n x m的矩阵,定义系统中n个进程中的每个进程对m类资源的 最大需求,如果Max[i,j] = K,则表示进程i需要资源R(j)的最大数目为K;
-
分配矩阵 Allocation
一个n x m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,j]= K,则表示进程i当前已分得资源R(j)的数目为K;
-
需求矩阵 Need
一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K,则表示进程i还需要资源R(j)的个数为k。
1.1 安全性算法
安全性算法的步骤
-
通过Max - Allocation 获得矩阵 Need,初始化Work = Available
-
接着对Need中的每一条数据 Need(i) 和 Work 进行比较
-
如果Need(i) <= Work && Finish[i] = false, 说明为该进程分配资源是安全的;
且假设该进程会立刻释放已分配的资源Allocation[i],因此执行Work += Allocation[i]
更新Finish[i] = true;
-
如果Need(i) > Work ,说明为该进程分配资源是不安全的;
继续查找下一个安全的进程;
-
-
如果对于所有的i,Finish[i]均为true,则系统处于安全的状态。
-
操作系统概念 第七版 截图如下。
举例
- 首先初始化Work = Available,即Work = (3, 3, 2);
- 对于need(0),(7, 4, 3) > (3, 3, 2),不满足条件继续查找;
- 对于need(1),(1, 2, 2) < (3, 2, 2),满足条件执行
- Work += Allocation[1] ,work = (3,3,2) + (2,0,0) = (5,3,2);
- Finish[1] = true;
- 继续查找;
- 对于need(2),(6, 0, 0) > (5, 3, 2),不满足条件继续查找;
- 对于need(3),(0, 1, 1) < (5, 3, 2),满足条件执行
- Work += Allocation[3] ,work = (5, 3, 2) + (2,1,1) = (7,4,3);
- Finish[3] = true;
- 继续查找
- 对于need(4),(4, 3, 1) < (7, 4, 3),满足条件执行
- Work += Allocation[4] ,work =(7, 4, 3) + (0,0,2) = (7,4,5);
- Finish[4] = true;
- 继续查找
- 对于need(2),(6, 0, 0) <(7,4,5),满足条件执行
- Work += Allocation[2] ,work =(7,4,5) + (3,0,2) = (10,4,7);
- Finish[2] = true;
- 继续查找
- 对于need(0),(7, 4, 3) <(10,4,7);,满足条件执行
- Work += Allocation[0] ,work =(10,4,7); + (0,1,0) = (10,5,7);
- Finish[0] = true;
- 至此对于所有的i,均满足Finish[i] = true,因此顺序<p1,p3,p4,p2,p0>满足安全条件。
1.2 资源请求算法
资源请求算法的步骤
-
对于每一个请求Request[i],首先判断是否<=Need[i]
- 如果不满足即代表请求资源Request[i]大于最大需求资源Need[i],显然无法分配资源需等待;
- 如果满足则继续向下执行;
-
判断是否Request[i] <= Available
- 如果不满足,即请求资源Request[i] 大于可用资源Available,显然无法分配资源需等待;
- 如果满足,则假设为进程p(i)分配资源,更新Available、Allocation、Need三个矩阵
- Available = Available - Request[i];
- Allocation = Allocation + Request[i];
- Need = Need - Request[i];
- 使用安全性算法检测是否安全,如果安全则分配资源,反之则需等待。
-
操作系统概念 第七版 截图如下。
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)