银行家算法
一、数据结构
注：Need [i，j] = Max [i，j] - Allocation [i，j]
二、算法介绍
1. 银行家算法
（1）如果request(i) [j] <= Need [i，j]，下一步
（2）如果Rquest(i) [i，j] <= Available [j]，下一步
（3）尝试分配，修改数据结构
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）安全性算法
2. 安全性算法
（1）设置变量工作变量Work = Available，Finish：false
（2）寻找满足下列规则的进程
Finish [i] = false
Need [i，j] <= Work [j]
找到进行步骤三，否则步骤四
（3）进程获得资源，可顺利执行，执行下列步骤
Work [i，j] = Work [i，j] + Allocation [i，j]
Finish [i] = true
（4）如果所有进程Finish [i] = true，安全，否则不安全
三、例子
五个进程{P0，P1，P2，P3，P4}，三类资源{A，B，C}，资源数量10，5，7，T0时刻资源分配情况如图所示
|
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(2) |
2(3) |
3(0) |
|
P1 |
3 |
2 |
2 |
2(3) |
0(0) |
0(2) |
1(0) |
2(2) |
2(0) |
|||
|
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 |
|||
1. 安全监测
|
Max |
Allocation |
Need |
Available |
Finish |
|||||||||
|
A |
B |
C |
A |
B |
C |
A |
B |
C |
A |
B |
C |
||
|
P1 |
3 |
3 |
2 |
1 |
2 |
2 |
2 |
0 |
0 |
5 |
3 |
2 |
true |
|
P3 |
5 |
3 |
2 |
0 |
1 |
1 |
2 |
1 |
1 |
7 |
4 |
3 |
true |
|
P4 |
7 |
4 |
3 |
4 |
3 |
1 |
0 |
0 |
2 |
7 |
4 |
5 |
true |
|
P2 |
7 |
4 |
5 |
6 |
0 |
0 |
3 |
0 |
2 |
10 |
4 |
7 |
true |
|
P0 |
10 |
4 |
7 |
7 |
4 |
3 |
0 |
1 |
0 |
10 |
5 |
7 |
true |
由上图可知，存在{P1，P3，P4，P2，P0}安全
2. Request(1) (1，0，2)，银行家算法
|
Work |
Need |
Allocation |
Work+Allocation |
Finish |
|||||||||
|
A |
B |
C |
A |
B |
C |
A |
B |
C |
A |
B |
C |
||
|
P1 |
2 |
3 |
0 |
0 |
2 |
0 |
3 |
0 |
2 |
5 |
3 |
2 |
true |
|
P3 |
5 |
3 |
2 |
0 |
1 |
1 |
2 |
1 |
1 |
7 |
4 |
3 |
true |
|
P4 |
7 |
4 |
3 |
4 |
3 |
1 |
0 |
0 |
2 |
7 |
4 |
5 |
true |
|
P0 |
7 |
4 |
5 |
7 |
4 |
3 |
0 |
1 |
0 |
7 |
5 |
5 |
true |
|
P2 |
7 |
5 |
5 |
6 |
0 |
0 |
3 |
0 |
2 |
10 |
5 |
7 |
true |
3. P4请求资源，Request [4] = {3，3，0}
Request [4] <= Need [4]
Request [4] > Available
P4 等待
4. P0请求资源，Request [0] = {2，3，0}
Request [0] <= Need [0]
Request [0] <= Available
假设可为P0分配资源，修改数据
|
Allocation |
Need |
Available |
|||||||
|
A |
B |
C |
A |
B |
C |
A |
B |
C |
|
|
P0 |
0 |
3 |
0 |
7 |
2 |
3 |
2 |
1 |
0 |
|
P1 |
3 |
0 |
2 |
0 |
2 |
0 |
|||
|
P2 |
3 |
0 |
2 |
6 |
0 |
0 |
|||
|
P3 |
2 |
1 |
1 |
0 |
1 |
1 |
|||
|
P4 |
0 |
0 |
2 |
4 |
3 |
1 |
|||
5. 进行安全检查，Available（2，1，0）不满足，系统不分配
文章最后发布于: 2019-06-10 14:25:49
相关阅读
何为冒泡？ 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。
首先感谢大佬博主v_JULY_v（v_JULY_v）在从头到尾彻底理解KMP（2014年8月22日版）一文中给我在写博客组织语言上的启发，以及部分图片的转载
landmark是一种人脸部特征点提取的技术，Dlib库中为人脸68点标记，在《调用Dlib库进行人脸关键点标记》一文中有效果和标定点序号的示
摘要： 针对基于内存的协同过滤推荐算法存在推荐列表排序效果不佳的问题，提出基于Pairwise排序学习的因子分解推荐算法（简称Pairwise-
百度移动搜索将针对低质站点及页面进行一系列调整，我们称之为冰桶算法。强行弹窗app下载、用户登录、大面积广告等影响用户正常浏