中国装修网官方网站,定制开发网站多少钱,商城网站建设合同范本,做论坛网站怎么样备案文章目录银行家算法实验原理数据结构初始化输出资源分配量安全性算法银行家算法完整代码测试数据测试结果第一题第二题银行家算法
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源#xff0c;但系统在进行资源分配之前#xff0c;应先…
文章目录银行家算法实验原理数据结构初始化输出资源分配量安全性算法银行家算法完整代码测试数据测试结果第一题第二题银行家算法
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源但系统在进行资源分配之前应先计算此次分配资源的安全性若分配不会导致系统进入不安全状态则分配否则等待。破坏了环路等待条件 实验原理 数据结构
1可利用资源向量Available 是个含有m个元素的数组其中的每一个元素代表一类可利用的资源数目。如果AvailablejK则表示系统中现有Rj类资源K个。 2最大需求矩阵Max 这是一个n×m的矩阵它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,jK则表示进程i需要Rj类资源的最大数目为K。 3分配矩阵Allocation 这也是一个n×m的矩阵它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,jK则表示进程i当前已分得Rj类资源的数目为K。 4需求矩阵Need。 这也是一个n×m的矩阵用以表示每一个进程尚需的各类资源数。如果Needi,jK则表示进程i还需要Rj类资源K个方能完成其任务。 Needi,jMaxi,j- Allocationi,j
int Allocation[11][101];//进程已获得资源
int Max[11][101];//进程所需最大资源
int Available[11];//可分配资源
int Need[11][101];//进程所需资源
int Requesti[11];//资源请求
int Work[11];//工作向量
int link[11];//安全序列
int x,y;//x表进程数y表资源种类初始化
帮助用户输入已知变量的函数构建银行家算法的Max、Allocation、Need、Available矩阵便于进行接下来的数据处理。
void init(){//初始化cout 请输入进程个数: endl;cin x;cout 请输入资源共有多少类: endl;cin y;cout 请输入每个进程所需要的各种资源的最大数目: endl;for (int i 0; i x; i) {cout P i1 : ;for (int j 0; j y; j) {cin Max[i][j];}}cout 请输入每个进程已分配的资源数量 endl;for(int i0; ix; i){cout P i1 : ;for(int j0; jy; j){cin Allocation[i][j];if(Allocation[i][j]Max[i][j]){cout 已分配资源数量大于进程所需的资源最大数目请重新输入 endl;i--;}}}cout 请输入系统可分配的资源数: endl;for (int i 0; i y; i) {cin Available[i];}for (int i 0; i x; i) {//计算每一个进程尚需的各类资源数Need矩阵for (int j 0; j y; j) {Need[i][j] Max[i][j] - Allocation[i][j];}}
}输出资源分配量
打印现在的矩阵状态Max、Allocation、Need、Available方便用户了解算法进行程度
void printSystemVariable(){//输出资源分配量cout 此时资源分配量如下 endl;cout 进程 Max Alloction Need Available endl;for(int i0;ix;i){//第i个进程cout P i1 ;for(int j0;jy;j){//第i个进程的Max矩阵信息cout Max[i][j] ;}cout | ;for(int j0;jy;j){//第i个进程的Allocation矩阵信息cout Allocation[i][j] ;}cout | ;for(int j0;jy;j){//第i个进程的Need矩阵信息cout Need[i][j] ;}cout | ;if(i0){for(int j0;jy;j){//第i个进程的Available矩阵信息cout Available[j] ;}}cout endl ;}
}安全性算法
1设置两个向量 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目它含有m个元素在执行安全算法开始时WorkAvailable; 工作向量Finish: 它表示系统是否有足够的资源分配给进程使之运行完成。开始时先做Finishifalse; 当有足够资源分配给进程时 再令Finishitrue。 2从进程集合中找到一个能满足下述条件的进程 Finishifalse; Needi,j≤Workj 若找到执行 (3)否则执行 (4) 3当进程Pi获得资源后可顺利执行直至完成并释放出分配给它的资源故应执行 WorkjWorkiAllocationi,j; Finishitrue; go to step 2; 4如果所有进程的Finishitrue都满足 则表示系统处于安全状态否则系统处于不安全状态
bool chesksafe(){//安全性算法for (int i 0; i y; i) {Work[i] Available[i];}bool Finish[7];//工作向量int mark x;//避免改变x的值所设的变量int temp 0;//满足需求资源少于剩余资源这一条件的资源数int flag 0;//进行资源分配的次数while (mark--) {//求安全序列的操作最多进行进程数次for(int i0;ix;i){//判定第i个进程if(Finish[i]true){continue;}for (int j 0; j y; j) {if(Need[i][j]Work[j]){//计算该进程需求资源少于剩余资源的资源数temp;}}if(tempy){//全部资源都满足需求资源少于剩余资源for (int j 0; j y; j) {//获得分配给该资源的资源数Work[j]Allocation[i][j];}Finish[i]true;flag;//进行一次资源分配link[flag]i1;//将进行资源分配的进程依次放入队列}temp0;//更新满足分配资源条件的资源数}}if(flagx){//如果没有进行进程数次资源分配说明不是安全序列cout 系统处于安全状态安全序列为 endl;for (int i 1; i x; i) {cout P link[i] ;}cout endl;return true;}else{cout 系统处于不安全状态 endl;return false;}
}银行家算法
设Requesti是进程Pi的请求向量如果RequestijK表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后系统按下述步骤进行检查 (1)如果Requestij≤Needi,j便转向步骤(2)否则认为出错因为它所需要的资源数已超过它所宣布最大值。 (2)如果Requestij≤Availablej便转向步骤(3)否则表示尚无足够资源Pi须等待。 (3)系统试探着把资源分配给进程Pi并修改下面数据结构中的数值 AvailablejAvailablej-Requestij; Allocationi,jAllocationi,jRequestij; Needi,jNeedi,j-Requestij; 系统执行安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式将资源分配给进程Pi以完成本次分配否则将本次的试探分配作废恢复原来的资源分配状态让进程Pi等待。 string an;//存储是否请求分配的用户指令bool flag false;//用于跳出两层循环的标志while(1){cout 是否请求分配yorY表是norN表否 ;cinan;if(an[0]!Yan[0]!y){break;}int num;cout 请输入请求资源的进程号如P1则输入1 endl;cin num;num - 1;//进程从1开始计数但各个数组下标从0开始计数cout 输入进程请求的资源数 endl;for (int i 0; i y; i) {cin Requesti[i];}for (int i 0; i y; i) {if(Requesti[i]Need[num][i]){cout 所需要的资源数已超过所宣布最大值Max endl;flag true;break;}if(Requesti[i]Available[i]){cout 尚无足够资源 endl;flag true;break;}Available[i]-Requesti[i];Allocation[num][i]Requesti[i];Need[num][i]-Requesti[i];}if (flag){//当任意资源请求出现问题时跳出两层循环flag false;//更新标志continue;//执行下一次循环}int temp 0;//满足Max值的Allocation值的个数if(chesksafe()){//安全,完成本次分配for (int i 0; i y; i) {if(Allocation[num][i]Max[num][i]){temp;}}if (temp y) {/*如果1个进程分配资源后每个资源已获得值都大于等于所需最大值则更新Available、Allocation和Need矩阵*/for (int i 0; i y; i) {Available[i]Allocation[num][i];//可分配资源获得该进程已获得的资源数Allocation[num][i]0;//清空该进程已获得的资源数Need[num][i]0;//清空该进程尚需的各类资源数}}cout 分配成功 endl;printSystemVariable();}else{//不安全,撤销之前的操作cout 分配失败 endl;for (int i 0; i y; i) {Available[i]Requesti[i];Need[num][i]Requesti[i];Allocation[num][i]-Requesti[i];}printSystemVariable();}}完整代码
#include iostream
using namespace std;int Allocation[11][101];//进程已获得资源
int Max[11][101];//进程所需最大资源
int Available[11];//可分配资源
int Need[11][101];//进程所需资源
int Requesti[11];//资源请求
int Work[11];//工作向量
int link[11];//安全序列
int x,y;//x表进程数y表资源种类void init();//初始化
void printSystemVariable();//输出资源分配量
bool chesksafe();//安全性算法int main(int argc, char const *argv[]) {init();printSystemVariable();if(!chesksafe()){return 0;}string an;//存储是否请求分配的用户指令bool flag false;//用于跳出两层循环的标志while(1){cout 是否请求分配yorY表是norN表否 ;cinan;if(an[0]!Yan[0]!y){break;}int num;cout 请输入请求资源的进程号如P1则输入1 endl;cin num;num - 1;//进程从1开始计数但各个数组下标从0开始计数cout 输入进程请求的资源数 endl;for (int i 0; i y; i) {cin Requesti[i];}for (int i 0; i y; i) {if(Requesti[i]Need[num][i]){cout 所需要的资源数已超过所宣布最大值Max endl;flag true;break;}if(Requesti[i]Available[i]){cout 尚无足够资源 endl;flag true;break;}Available[i]-Requesti[i];Allocation[num][i]Requesti[i];Need[num][i]-Requesti[i];}if (flag){//当任意资源请求出现问题时跳出两层循环flag false;//更新标志continue;//执行下一次循环}int temp 0;//满足Max值的Allocation值的个数if(chesksafe()){//安全,完成本次分配for (int i 0; i y; i) {if(Allocation[num][i]Max[num][i]){temp;}}if (temp y) {/*如果1个进程分配资源后每个资源已获得值都大于等于所需最大值则更新Available、Allocation和Need矩阵*/for (int i 0; i y; i) {Available[i]Allocation[num][i];//可分配资源获得该进程已获得的资源数Allocation[num][i]0;//清空该进程已获得的资源数Need[num][i]0;//清空该进程尚需的各类资源数}}cout 分配成功 endl;printSystemVariable();}else{//不安全,撤销之前的操作cout 分配失败,撤销本次操作 endl;for (int i 0; i y; i) {Available[i]Requesti[i];Need[num][i]Requesti[i];Allocation[num][i]-Requesti[i];}printSystemVariable();}}return 0;
}void init(){//初始化cout 请输入进程个数: endl;cin x;cout 请输入资源共有多少类: endl;cin y;cout 请输入每个进程所需要的各种资源的最大数目: endl;for (int i 0; i x; i) {cout P i1 : ;for (int j 0; j y; j) {cin Max[i][j];}}cout 请输入每个进程已分配的资源数量 endl;for(int i0; ix; i){cout P i1 : ;for(int j0; jy; j){cin Allocation[i][j];if(Allocation[i][j]Max[i][j]){cout 已分配资源数量大于进程所需的资源最大数目请重新输入 endl;i--;}}}cout 请输入系统可分配的资源数: endl;for (int i 0; i y; i) {cin Available[i];}for (int i 0; i x; i) {//计算每一个进程尚需的各类资源数Need矩阵for (int j 0; j y; j) {Need[i][j] Max[i][j] - Allocation[i][j];}}
}void printSystemVariable(){//输出资源分配量cout 此时资源分配量如下 endl;cout 进程 Max Alloction Need Available endl;for(int i0;ix;i){//第i个进程cout P i1 ;for(int j0;jy;j){//第i个进程的Max矩阵信息cout Max[i][j] ;}cout | ;for(int j0;jy;j){//第i个进程的Allocation矩阵信息cout Allocation[i][j] ;}cout | ;for(int j0;jy;j){//第i个进程的Need矩阵信息cout Need[i][j] ;}cout | ;if(i0){for(int j0;jy;j){//第i个进程的Available矩阵信息cout Available[j] ;}}cout endl ;}
}bool chesksafe(){//安全性算法for (int i 0; i y; i) {Work[i] Available[i];}bool Finish[7];//工作向量int mark x;//避免改变x的值所设的变量int temp 0;//满足需求资源少于剩余资源这一条件的资源数int flag 0;//进行资源分配的次数while (mark--) {//求安全序列的操作最多进行进程数次for(int i0;ix;i){//判定第i个进程if(Finish[i]true){continue;}for (int j 0; j y; j) {if(Need[i][j]Work[j]){//计算该进程需求资源少于剩余资源的资源数temp;}}if(tempy){//全部资源都满足需求资源少于剩余资源for (int j 0; j y; j) {//获得分配给该资源的资源数Work[j]Allocation[i][j];}Finish[i]true;flag;//进行一次资源分配link[flag]i1;//将进行资源分配的进程依次放入队列}temp0;//更新满足分配资源条件的资源数}}if(flagx){//如果没有进行进程数次资源分配说明不是安全序列cout 系统处于安全状态安全序列为 endl;for (int i 1; i x; i) {cout P link[i] ;}cout endl;return true;}else{cout 系统处于不安全状态 endl;return false;}
} 测试数据
这里的测试数据就拿教材上的一个习题 测试结果
第一题 第二题 注意题中排序从0开始程序排序从1开始此题中的P2对应程序中的P3输入数字应该是3而不是2 经演算结果完全正确√
