#银行家算法 ##一： 内容简述 ###1. 目标 多种资源银行家算法的模拟实现 ###3. 背景了解 ####1、死锁概念 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 ####2、关于死锁的一些结论：
- 参与死锁的进程最少是两个 （两个以上进程才会出现死锁）
- 参与死锁的进程至少有两个已经占有资源
- 参与死锁的所有进程都在等待资源
- 参与死锁的进程是当前系统中所有进程的子集
注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 ####3、资源分类。
- 永久性资源：
- 可以被多个进程多次使用（可再用资源）
- 可抢占资源
- 不可抢占资源
- 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）
“申请–分配–使用–释放”模式
####4、产生死锁的四个必要条件： 互斥使用（资源独占）、不可抢占（不可剥夺）、请求和保持（部分分配，占有申请）、循环等待。 #####1) 互斥使用（资源独占） 一个资源每次只能给一个进程使用。 #####2) 不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放。 #####3) 请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）。 ####4) 循环等待 存在一个进程等待队列 {P1 , P2 , … , Pn}, 其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。 ####5、死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 #####①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 #####②破坏“请求和保持”条件。 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 #####③破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 ####6．安全状态与不安全状态
- 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，…Pn，则系统处于安全状态。一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的)
- 不安全状态:不存在一个安全序列，不安全状态不一定导致死锁。
##二：主要内容
-
设计思路 用高级语言编制银行家算法通用程序，并检测所给状态的系统安全性。 1.算法介绍：数据结构：
- 可利用资源向量 Available； 2.最大需求矩阵Max； 3.分配矩阵Allocation； 4.需求矩阵Need 2.功能介绍
模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：
第一部分：银行家算法（扫描）；
第二部分：安全性算法。
3.主要代码设计分析
-
银行家算法中的数据结构
(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个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］
###1.代码与初始化：
#define MAXPROCESS 100 //最大进程数
#define MAXRESOURCE 100 //最大资源数
int AVAILABLE[MAXRESOURCE]; //可利用资源向量
int MAX[MAXPROCESS][MAXRESOURCE]; //最大需求矩阵
int ALLOCATION[MAXPROCESS][MAXRESOURCE]; //分配矩阵
int NEED[MAXPROCESS][MAXRESOURCE]; //需求矩阵
int REQUEST[MAXPROCESS][MAXRESOURCE]; //进程需要资源数
bool FINISH[MAXPROCESS]; //表示系统是否有足够的资源分配给进程
int p[MAXPROCESS]; //记录序列
int m, n; //m个进程,n个资源
int i, j; //遍历变量
void Init() //初始化算法 初始化银行家算法中所要模拟的各种资源
{
cout << "请输入进程的数量:";
cin >> m;
cout << "请输入资源的类数:";
cin >> n;
cout << "请输入每个资源提供的最大数量：";
for (i = 0; i < n; i++)
cin >> AVAILABLE[i];
cout << "请输入每个进程最大需求资源数：（即最大需求矩阵：格式为" << m << "x" << n <<")"<< endl;
for (i = 0; i<m; i++)
for (j = 0; j<n; j++)
cin >> MAX[i][j];
cout << "请输入每个进程已分配的资源数：（即分配矩阵：格式为" << m << "x" << n << ")" << endl;
for (i = 0; i<m; i++)
{
for (j = 0; j<n; j++)
{
cin >> ALLOCATION[i][j];
NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];
if (NEED[i][j]<0)
{
cout << "对不起！您输入的第" << i + 1 << "个进程所拥有的第" << j + 1 << "个资源数值非法,请重新输入:" << endl;
cout << "ALLOCATION[" << i + 1 << "][" << j + 1 << "]=";
j--;
continue;
}
}
}
//得到当前资源可利用值
for (i = 0; i < n; i++)
for (j = 0; j < m;j++)
{
AVAILABLE[j]-=ALLOCATION[i][j];
}
IsSafe();//判定初始值是否安全
print();//输出当前状态
}
###2. 银行家算法 设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］=Available［j］-Requesti［j］; Allocation［i,j］=Allocation［i,j］+Requesti［j］; Need［i,j］=Need［i,j］-Requesti［j］;(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 代码：
void Bank() //银行家算法
{
int i, pid, number = 0;
char flag;//标明是否继续分配
while (1)
{
cout << endl;
enterid:
cout << "请输入要申请资源的进程ID(注:第1个进程号为0,依次类推)：";
cin >> pid;
if (pid > m||pid < 0)
{
cout << "进程ID输入错误，请重新输入！" << endl;
goto enterid;
}
enternum:
cout << "请输入进程"<<pid<<"要申请的各资源数量:" << endl;
for (i = 0; i<n; i++)
{
cin >> REQUEST[pid][i];
}
for (i = 0; i<n; i++)//验证请求是否合理
{
if (REQUEST[pid][i]>NEED[pid][i])//进程ID申请的资源数量大于其所需要的进程数量
{
cout << "进程"<<pid<<"所申请的资源"<<i<<"的数量超出其进程实际需求量！请重新输入！" << endl;
goto enternum;
}
if (REQUEST[pid][i]>AVAILABLE[i])//进程ID申请的资源数量大于系统剩余可用数量
{
cout << "进程"<<pid<<"所申请的资源"<<i<<"的数量超出系统剩余最大可用量！请重新输入！" << endl;
goto enternum;
}
}
for (i = 0; i<n; i++)//如果请求合理，分配资源，计算分配后资源数量
{
AVAILABLE[i] -= REQUEST[pid][i];//剩余可用数量
ALLOCATION[pid][i] += REQUEST[pid][i];//已分配数量
NEED[pid][i] -= REQUEST[pid][i];//还需要的数量
}
if (IsSafe())//判定若资源分配后，是否安全。若安全，则同意分配。
{
cout << "系统状态安全，可以分配！" << endl;
}
else
{
cout << "系统状态为不安全，不可分配！" << endl;
for (i = 0; i<n; i++)//回到原数量
{
AVAILABLE[i] += REQUEST[pid][i];
ALLOCATION[pid][i] -= REQUEST[pid][i];
NEED[pid][i] += REQUEST[pid][i];
}
}
for (i = 0; i<n; i++)
{
if (NEED[pid][i] == 0)//进程pid的资源i分配完毕
{
number++;
}
}
if (number == n)//如果该进程各资源都已分配完毕，则释放资源
{
for (i = 0; i<n; i++)
{
AVAILABLE[i] += ALLOCATION[pid][i];
ALLOCATION[pid][i] = 0;
NEED[pid][i] = 0;
}
cout << "进程" << pid << "分配完毕，其占有的资源被释放！" << endl;
print();//输出当前状态
number = 0;
}
for (i = 0; i<m; i++)//分配好了以后将进程的标识FINISH改成false
{
FINISH[i] = false;
}
cout << "是否继续请求分配资源？（若是，请输入y/Y.否则输入其它）" << endl;
cin >> flag;
if (flag == 'y' || flag == 'Y')
{
continue;
}
break;
}
}
###3. 安全性算法 系统所执行的安全性算法可描述如下：
(1) 设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;
② Finish向量: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］=false; 当有足够资源分配给进程时， 再令Finish［i］=true。
(2) 从进程集合中找到一个能满足下述条件的进程：
① Finish［i］=false;
② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤 (4)。
(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资 源，故应执行：
Work［j］=Work［i］+Allocation［i,j］; Finish［i］=true;
go to step 2; (4) 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
代码：
bool IsSafe() //安全性算法 判定当前状态，工作是否安全 安全则返回true 不安全返回flase
{
int l = 0;
int Work[MAXRESOURCE]; //表示系统可提供给进程继续运行所需的各类资源数目
for (i = 0; i < n; i++)//对work进行初始化
Work[i] = AVAILABLE[i];
for (i = 0; i < m; i++)//对finish进行初始化
{
FINISH[i] = false;//先初始化为不安全
}
while (l<m)//正常的话，共执行m次
{
int flag=0;//0为不安全，1为安全
for (i = 0; i < m; i++)//对m个进程一次检查
{
if (FINISH[i] == true)
{
continue;
}
for (j = 0; j < n; j++)
{
if (NEED[i][j] > Work[j])
{
break;
}
}
if (j == n)//表明进程i是安全的，进程i获得资源后，可顺利执行，直至完成，并释放出分配给它的资源
{
FINISH[i] = true;//进程i安全
for (int k = 0; k < n; k++)
{
Work[k] += ALLOCATION[i][k];
}
p[l++] = i;//记录进程号
flag = 1;//表示不安全
}
else//进程i是不安全的
{
continue;
}
}
if (!flag)
{
cout << "系统是不安全的" << endl;
return false;
}
}
cout << "系统是安全的" << endl;
cout << "安全序列:" << endl;
for (i = 0; i < l; i++)//显示资源分配给进程的顺序
{
cout << p[i];
if (i != l - 1)
{
cout << "-->";
}
}
cout << "" << endl;
return true;
}
