操作系统中死锁的算法——银行家算法-环球播报
1.银行家算法
银行家算法是操作系统中死锁避免的一种算法,这是一个理想化的方法,一般实际中很少用到,因为要提前知道每一个进程申请资源的最大需求量,这一般很难控制. 算法的思想: 1.知道系统中每个资源的资源量. 2.知道每个进程对每个资源的最大需求量. 3.当给每个进程进行申请对应资源的时. 3.1.如果此次申请的资源数+已经持有的资源数大于了该进程的最大需求量,那么则拒绝分配. 3.2.如果此次申请的资源数+已经持有的资源数小于等于该进程的最大需求量.那么就需要和此时系统中剩余的资源数进行判断.转到第4步骤. 4.如果系统中剩余的资源数可以满足该进程尚需的最大资源数,则进行分配.否则拒绝分配. 5.如果最后满足了上面第3和第4的分配后,还需要做最后一步,若给了该进程此次的申请资源数,是否可以查找到一个安全序列,如果可以找到一个安全序列,那么则最后再分配,否则也不予分配该进行的此次的申请.
如果可以找到一个安全序列,则系统处于安全状态. 如果找不到一个安全序列,则系统处于不安全状态.
(相关资料图)
注意:如果系统处于不安全的状态,不一定会产生死锁,如果系统产生了死锁,那么该系统一个处于不安全状态.
2.例子和运行结果
3.算法实现
3.1 定义数据结构
#include #include#define KIND_MAX 100//默认的资源种类数量#define PROCESS_MAX 100//默认的进程数量typedef struct ResourcesEntity{int max;//最大的拥有量 int haved;//还剩下的数量 int temp;//临时存储剩余的,检查安全序列的时候用到的}RE;typedef struct ProcessEntity {int maxKindCount[KIND_MAX];//对每个资源的最大需求量数组 int allocatedKindCount[KIND_MAX];//已经分配的种类数量 int needKindCount[KIND_MAX];//对每个资源尚需要的量 int tempKindCount[KIND_MAX];//存储临时申请的资源数量}PE;
KIND_MAX:默认的系统中最大的资源种类数量. PROCESS_MAX:默认系统中同时申请资源进程的数量.
ResourcesEntity:进程资源的数据结构 max:存储系统中最大拥有该资源的数量 haved:存储系统中还剩下的该资源的数量 temp:用于临时存储申请资源的进程申请的数量,用于寻找安全序列的计算.
ProcessEntity:进程的数据结构. maxKindCount:数组中存放该进程最每个资源最大需求量 allocatedKindCount:数组存放该进程已经申请到的每个资源的数量 needKindCount:数组存放该进程该需要每个进程的数量 tempKindCount:数组用存储该进程对每个资源的本次申请的数量.
3.2算法实现思想
int resources_Size;//资源种类总数int process_Size;//进程总数RE resource[KIND_MAX];//资源种类数组PE process[PROCESS_MAX];//进程的数量
resources_Size:用于存储动态的资源种类数量. process_Size:用于存储动态的进程数量. resource:数组存放资源种类. process:数组存放申请资源的进程.
1.当初始化了系统资源和初始化进程 1.1判断每个进程对每种资源初始化的数量是否大于了该进程的最大需求量(process[i].needKindCount[j]<0),如果这样的进程数量大于0,那么拒绝分配.初始化失败. 1.2.判断每个进程的最大需求量是否大于了系统最大持有的数量(resource[j].max-process[i].maxKindCount[j]),如果这样的进程数量大于了0,则拒绝分配,初始化失败. 1.3.判断所有的进程对每种资源已分配的数量总和是否大于了系统中最大的持有数量.如果这样的资源种类大于0(resource[j].haved<0),那么拒绝分配,初始化失败. 1.4.判断系统是否是安全状态(是否找到一个安全序列),至于怎么寻找安全序列,申请资源的时候再介绍.如果寻找到了安全序列,则初始化成功,否则初始化失败. 2.到了这里,表示初始化成功了,下面就是当进程申请资源的时. 2.1.如果把该进程此次申请的资源数量分配给该进程,是否超过了该进程的对该资源的最大需求量(process[progressNum].maxKindCount[i]-process[progressNum].allocatedKindCount[i]-process[progressNum].tempKindCount[i]),如果小于0表示,超过了该进程的最大需求量,拒绝分配. 2.2判断该系统剩余的资源数量是否满足该进程尚需的需求量(resource[i].haved-process[progressNum].needKindCount[i]),小于0表示不满足,拒绝分配. 2.3如果上面两个条件都不符合,那么再判断若分配给该进程此次申请的资源,系统是否处于安全状态(寻找安全序列).如果找到安全序列,则分配,更新系统资源和进程资源信息,否则拒绝分配. 3.这里介绍寻找安全序列. 3.1:用于数组存储安全序列. 3.2.如果安全序列数组不等于进程数量,则继续寻找,否则跳转到3.4步骤 3.3.顺序寻找进程数组,找到第一个满足该进程尚需的资源数组(needKindCount).如果在安全序列数组未满的时候,未找到满足条件的进程,则查找失败,未找到安全序列,则拒绝此次的申请跳出寻找,转到3.4.如果找到了,则添加到安全序列数组中,然后更新系统的剩余的每个资源数量(存储在temp数组中).继续跳转到3.2步骤. 3.4如果未找到安全序列,那么拒绝此次分配,如果找到了安全序列,则将申请资源进程的信息和系统剩余的资源信息.
3.3方法定义
//重置资源void resetResourcesInfo(void);//重置进程void resetProcessInfo(void);//初始化资源void initializeResources(void);//初始化进程void initializeProcess(void);//打印Tablevoid printTable(void);//打印占位线void printfLine(int num,char c,int nextLine);//申请资源void applyResource(void);//检查系统是否安全int checkSecurityStatus(int progressNum,int isInit);//检查安全序列是否全部查找完成int checkSafeListFinish(int safeList[]);//获取下一个安全进程位置int getSafeProgressPosition(int safeList[],int progressNum,int isInit);//打印所有的资源状况void printfAllResource(void);//菜单int menuBank(void);
3.4方法实现
//判断数组中是否包含此值int isContain(int array[],int length,int value){for(int i=0;iif(array[i]==value){return 1; } } return 0;}//打印线void printfLine(int num,char c,int nextLine){for(int i=0;iprintf("%c",c); } if(nextLine==1){printf("\n"); }}//初始化资源void initializeResources(){//重置资源 resetResourcesInfo(); printf("请输入资源种类总数(例如:若有R1,R2,R3三类资源,则输入3):"); scanf("%d",&resources_Size); if(resources_Size<=0){printf("系统资源种类应大于0\n"); }else{if(resources_Size>KIND_MAX){resources_Size=KIND_MAX; } for(int i=0;iprintf("请输入资源R%d的总数(大于0):",i+1); //默认的剩余和最大是一样的 scanf("%d",&resource[i].max); if(resource[i].max<0){resource[i].max=0; } resource[i].haved=resource[i].max; } printfAllResource(); } }//重置进程void resetProcessInfo(){process_Size=0; for(int i=0;ifor(int j=0;jprocess[i].maxKindCount[j]=0; process[i].allocatedKindCount[j]=0; process[i].tempKindCount[j]=0; } }}//重置资源void resetResourcesInfo(){resources_Size=0; for (int i=0; iresource[i].max=0; resource[i].haved=0; resource[i].temp=0; } resetProcessInfo();}//初始化进程void initializeProcess(){//初始化所有进程 resetProcessInfo(); //初始化进程 printf("请输入进程的数量:"); scanf("%d",&process_Size); if(process_Size<=0){printf("进程数量应大于0\n"); }else{if(process_Size>PROCESS_MAX){process_Size=PROCESS_MAX; } for(int i=0;ifor(int j=0;jprintf("请输入 进程P%-2d<<目前占有>> 资源R%-2d的数量:",i+1,j+1); scanf("%d",&process[i].allocatedKindCount[j]); //从总资源中减去已分配的资源 resource[j].haved=resource[j].haved-process[i].allocatedKindCount[j]; } for(int j=0;jprintf("请输入 进程P%-2d<<最大需求>> 资源R%-2d的数量:",i+1,j+1); scanf("%d",&process[i].maxKindCount[j]); //尚需的资源数量(最大需求量-已分配的) process[i].needKindCount[j]=process[i].maxKindCount[j]-process[i].allocatedKindCount[j]; } } printTable(); //检查初始化完毕后,是否安全 //1.检查每个进程已申请的是否超过了最大的需求量 //2.检查每个进程的最大需求量,是否超过了系统的最大持有量 //3.检查每个进程已申请的资源,是否超过了总资源的量 int isNeedReset=0;//是否重置 //1 for(int i=0;ifor(int j=0;jif(process[i].needKindCount[j]<0){isNeedReset=1; printf("拒绝分配:进程%d对资源%d的申请大于了最大需求量(%d)\n",i+1,j+1,process[i].needKindCount[j]); } } } //2. for(int i=0;ifor(int j=0;j//表示进程i的对资源j最大需求量大于了系统持有的资源j的最大量. //所以,即使除了当前进程外全部进程都释放了资源j,也无法满足当前进程的需求量. int re=resource[j].max-process[i].maxKindCount[j]; if(re<0){isNeedReset=1; printf("拒绝分配:进程%d对资源%d的最大需求量大于了系统最大持有资源R%d数量\n",i+1,j+1,j+1); } } } //3. for(int j=0;jif(resource[j].haved<0){isNeedReset=1; printf("拒绝分配:所有进程对资源%d的已申请辆超过了系统的最大持有量(%d)\n",j+1,resource[j].haved); } } if(isNeedReset==1){printf("请重新初始化进程(菜单编号2)\n"); //初始化所有进程 resetProcessInfo(); }else if(checkSecurityStatus(0,1)==0){printf("请重新初始化进程(菜单编号2)\n"); //初始化所有进程 resetProcessInfo(); } }}//申请资源void applyResource(){printfAllResource(); int pNum; do{printf("请输入申请资源的进程P(%d,%d):",1,process_Size); scanf("%d",&pNum); }while (pNum<=0|| pNum>process_Size) ; for(int i=0;iprintf("请输入进程P%d申请资源R%d的数量:",pNum,i+1); scanf("%d",&process[pNum-1].tempKindCount[i]); } //检查安全状态 checkSecurityStatus(pNum-1,0);}//检查这次申请的安全状态int checkSecurityStatus(int progressNum,int isInit){//检查此次的申请是否超过了该进程的最大的需求量 //最大尚需和系统的剩余量比较. //如果都通过了,就寻找安全序列,如果寻找到了安全序列,则分配,否则不予分配. if(isInit==0){int status=1; for(int i=0;iint result=process[progressNum].maxKindCount[i]-process[progressNum].allocatedKindCount[i]-process[progressNum].tempKindCount[i]; if(result<0){status=0; printf("拒绝分配:若分配给进程P%d此次申请的资源R%d数量,则超过了该进程的最大需求量:(%d)\n",progressNum+1,i+1,result); } } if(status==0){//表示此次申请超过了最大的需求量 return 0; }else{//未超过最大的需求量,然后再判断系统剩余的是否满足该进程尚需的最大需求量. for(int i=0;iint re=resource[i].haved-process[progressNum].needKindCount[i]; if(re<0){status=0; printf("拒绝分配:该进程尚需的最大资源R%d数量超过了系统的剩余资源R%d的资源:(%d)\n",i+1,i+1,re); } } if(status==0){return 0; } } } //1.开始寻找安全序列 int safeList[process_Size];//安全序列 //2.先初始化 for(int i=0;isafeList[i]=-1; } //3.先初始化剩余资源的临时存储 for(int j=0;jif(isInit==0){resource[j].temp=resource[j].haved-process[progressNum].tempKindCount[j]; }else{resource[j].temp=resource[j].haved; } } //4.检查安全序列是否完成 while (checkSafeListFinish(safeList)!=1) {int pn=getSafeProgressPosition(safeList,progressNum,isInit);// printf("log:安全进程位置:%d\n",pn); if(pn!=-1){//4.1添加到安全序列 for(int i=0;iif(safeList[i]==-1){safeList[i]=pn; break; } } //4.2并且更新系统剩余的资源量(临时的) for(int j=0;jif(isInit==0 && pn==progressNum){resource[j].temp=resource[j].temp+(process[pn].needKindCount[j]-process[pn].tempKindCount[j])+(process[pn].allocatedKindCount[j]+process[pn].tempKindCount[j]); }else{resource[j].temp=resource[j].temp+process[pn].needKindCount[j]+process[pn].allocatedKindCount[j]; } } }else{//4.3 //如果返回的-1,则表示没有找到安全进程 printf("未找到安全序列,拒绝分配资源\n"); return 0; } } //5.找到了安全序列.打印安全序列 printf("分配完成->安全序列:"); for(int i=0;iif(i==0){printf("P%d",safeList[i]+1); }else{printf(",P%d",safeList[i]+1); } } printf("\n"); //6.如果是申请的资源 //(1)更新申请资源的进程对应的资源数量 //(2)更新剩余的资源 if(isInit==0){for(int i=0;i//更新目前占有量:加上申请的资源 process[progressNum].allocatedKindCount[i]=process[progressNum].allocatedKindCount[i]+process[progressNum].tempKindCount[i]; //更新尚需要量:减去申请的资源 process[progressNum].needKindCount[i]=process[progressNum].needKindCount[i]-process[progressNum].tempKindCount[i]; //更新系统剩余的资源:减去申请的资源 resource[i].haved=resource[i].haved-process[progressNum].tempKindCount[i]; } } return 1;}//获取安全进程位置角标int getSafeProgressPosition(int safeList[],int progressNum,int isInit){for(int i=0;i//如果不存在安全序列,则进行判断 if(!isContain(safeList, process_Size, i)){int isAdd=1; for(int j=0;j//寻找第一个安全进程 if(isInit==0 && progressNum==i){int r=resource[j].temp-(process[i].needKindCount[j]-process[i].tempKindCount[j]); if(r>=0){isAdd=isAdd&1; }else{isAdd=isAdd&0; } }else{if(resource[j].temp-process[i].needKindCount[j]>=0){isAdd=isAdd&1; }else{isAdd=isAdd&0; } } } //系统剩余的资源量满足当前进程尚需要量 if(isAdd==1){return i; } } } return -1;}//检查安全序列是否完成int checkSafeListFinish(int safeList[]){for(int i=0;iif(safeList[i]==-1){// printf("log:安全序列是否完成%d\n",0); return 0; } }// printf("log:安全序列是否完成%d\n",1); return 1;}//打印资源状态void printfAllResource(){printfLine(20, "*", 1); printf("系统资源剩余情况:\n"); for(int i=0;iprintf("资源R%d:总数=%d,剩余=%d\n",i+1,resource[i].max,resource[i].haved); } printfLine(20, "*", 1);}//打印Tablevoid printTable(){printfLine(50, "-", 1); printf("系统资源分配表:\n"); char titleRow1[20]={"目前占有量"}; char titleRow2[20]={"最大需求量"}; char titleRow3[20]={"尚需要量 "}; //打印Title printf("%4s",""); int spcount=0; if(resources_Size*4>10){spcount= (resources_Size*4-10); } printf("|"); printf("%*s%s%*s",spcount,"",titleRow1,spcount,""); printf("|"); printf("%*s%s%*s",spcount,"",titleRow2,spcount,""); printf("|"); printf("%*s%s%*s",spcount,"",titleRow3,spcount,""); printf("|"); printf("\n"); //打印Title(资源) printf("%4s"," "); printf("|"); for(int j=0;jprintf("R%-3d",j+1); } printf("|"); for(int j=0;jprintf("R%-3d",j+1); } printf("|"); for(int j=0;jprintf("R%-3d",j+1); } printf("|"); printf("\n"); //打印进程信息 for(int i=0;iprintf("P"); printf("%-3d",i+1); printf("|"); for(int j=0;jprintf("%-4d",process[i].allocatedKindCount[j]); } printf("|"); for(int j=0;jprintf("%-4d",process[i].maxKindCount[j]); } printf("|"); for(int j=0;jprintf("%-4d",process[i].needKindCount[j]); } printf("|"); printf("\n"); } printf("系统资源剩余情况:\n"); for(int i=0;iprintf("资源R%d:总数=%d,剩余=%d\n",i+1,resource[i].max,resource[i].haved); } printfLine(50, "-", 1);}//菜单int menuBank(){int result=1; printfLine(50, "*",1); printf("%*s%s\n",18,"","<<银行家算法系统>>"); printf("%*s%s\n",20,"","1.初始化系统资源"); printf("%*s%s\n",20,"","2.初始化进程"); printf("%*s%s\n",20,"","3.申请资源"); printf("%*s%s\n",20,"","4.查看资源状况"); printf("%*s%s\n",20,"","5.退出"); int num; printf("%*s%s",18,"","请输入菜单编码(1-5):"); do{scanf("%d",&num); if(num<1||num>5){printf("输入错误,请重新输入\n"); } }while (num<1||num>5); printfLine(50, "*",1); switch (num) {case 1: initializeResources(); menuBank(); break; case 2: if(resources_Size<=0){printf("请先初始化系统资源(菜单编号1)\n"); }else{initializeProcess(); } menuBank(); break; case 3: if(resources_Size<=0){printf("请先初始化系统资源(菜单编号1)\n"); }else if(process_Size<=0){printf("请先初始化进程(菜单编号2)\n"); }else{applyResource(); } menuBank(); break; case 4: if(resources_Size<=0){printf("请先初始化系统资源(菜单编号1)\n"); }else if(process_Size<=0){printf("请先初始化进程(菜单编号2)\n"); }else{printTable(); } menuBank(); break; case 5: printf("已退出,欢迎下次使用.\n"); result=0;// exit(0); break; } return result;}
3.5算法的注意事项
1.初始化系统资源的时候也要判断是否存在安全序列 2.进程申请资源的时候,使用temp存储,计算安全序列的时候,也是使用temp中的值进行判断 3.当找到安全序列,记得更新申请资源的信息和系统剩余资源的信息.
4源码下载使用
1.此代码是在mac系统上的开发工具xcode上开发的,如果下载的代码要在WIndow系统上的VC6.0或者DevC++开发工具上运行,可能会存在中文乱码问题. 解决办法: 1.1可以在window上使用记事本打开,另存为:选择window系统上开发工具支持的编码方式. 1.2可以使用笨方法:在window开发工具上新建文件,然后使用记事本打开源代码后复制到新建的文件上.
2.如果出现不能运行的问题,就是方法中局部变量问题. 例如:
///判断数组中是否包含此值int isContain(int array[],int length,int value){for(int i=0;iif(array[i]==value){return 1; } } return 0;}
就需要把i抽取到方法体的顶部.
//判断数组中是否包含此值int isContain(int array[],int length,int value){int i; for(i=0;iif(array[i]==value){return 1; } } return 0;}
自己亲测在window上使用上述两种办法,解决了问题.mac编译工具到window编译工具可以运行.
标签:
相关推荐:
最新新闻:
- 环球今热点:【全国计算机等级考试】2级公共基础120题之四(11)
- test.c测试游戏:测试三子棋的逻辑-最新资讯
- 世界速读:5.0以下的主流图片加载框架有哪些?安卓加载图片四大框架
- 磁盘垃圾文件清理器是什么?python接收命令行参数的方式及步骤-今日热讯
- 当前资讯!在哪里看股指期货的行情?股指期货行情信息
- 热门看点:【激活码】180天诺顿NAVirus2012版本安装
- 操作系统中死锁的算法——银行家算法-环球播报
- 每日简讯:乔尔演员想看《最后的生还者》第二季还原“乔尔之死”:最真实的版本
- 《漫漫长夜》将于4月16日离开XGP
- 荷兰弟新剧定档6月9日:在片中演精神病人|当前快讯
- 央视探访天马科技集团 | 出口内销两旺,鳗鱼产业迎来消费利好!
- N64Switch在线追加《宝可梦竞技场2》4月12日上线
- 英国实体周榜:春季游戏没人打得过《生化4重制》
- 佩蒂特:梅西被嘘简直是对足球的侮辱!
- 发行商Devolver收购《枪伞游侠》开发商doinksoft 天天热消息
- 英特尔宋继强:面向半导体“万亿时代”,以全栈创新推动算力发展_环球观焦点
- 惠普第9代游戏家族重磅发布,助力玩家 玩出内力 再来亿把|环球实时
- 出游踏青随手拍出美景 逛京东手机焕新季入手爆款新机更超值
- 快用苹果助手如何安装?快用苹果助手安装不了怎么办?
- XLUEOPS.exe是什么?XLUEOPS.exe删除的方法
- Cydia源是什么?Cydia软件卸载步骤
- dnf画面卡是怎么回事?DNF卡屏最快解决方法是什么?
- 聚焦:观察|2023年在未来五年中发挥什么样的重要作用
- MP3Resizer如何压缩MP3文件?MP3Resizer安装及使用教程
- 任务管理器打不开怎么办?任务管理器打不开解决方法
- 无线网络连接不可用怎么办?无线网络连接不可用的解决方法
- 环球精选!穷人靠变异!DC新片《蓝甲虫》预告:拉丁超英来袭
- 本地网速测试有哪些方法?本地网速测试方法
- 如何设置使用激活工具oem7F7?oem7F7使用激活方法介绍
- win10运行lol一直崩溃怎么办?win10运行lol一直崩溃解决方法
- 88e6060是什么芯片?88e6060特性和好处
- 视频如何转换为AMV格式?AMV转换精灵操作方法
- LOL图标怎么点亮?qq上的英雄联盟图标怎么点亮?
- desktop.ini是什么文件?desktop.ini可以删除吗?
- 怎么用win10制作iso镜像文件?win10制作iso镜像文件的步骤教程
- 为什么电脑看视频卡住不动?电脑看视频卡怎么办?
- win7出现黑屏代码0xc000025怎么办?黑屏代码0xc000025解决办法
- snapchat怎么注册?Snapchat账号注册方法步骤
- Svchost.exe是什么进程?svchost.exe错误的原因及解决教程
- 桌面文件夹无法删除怎么解决?桌面文件夹无法删除解决方法
- 沪深股通|海利得4月3日获外资卖出0.04%股份:天天信息
- 快看点丨《魔术士奥芬》圣域篇新艺图角色 4月12日开播
- 《海洋奇缘》真人电影公布 巨石强森主演
- 广西启动第32个全国税收宣传月暨2023年广西助企纾困活动
- 《街头霸王》将拍真人电影!网友:让成龙大哥来
- AMD宣布开发DDR5 MRDIMM内存:目标17600MB/s
- 挑战Steam Deck!华硕打造自己的掌机ROG Ally
- 当前最新:Xbox第一方游戏《量子破碎》将离开XGP阵容
- 欧洲任天堂为漂移Joy-Con手柄提供保外维修
- 要闻:《守望先锋2》新辅助英雄“生命编织者”透露
- 开发者:顽皮狗新作将是全新IP!知名演员参与配音:世界快报
- HP发布暗影精灵9系列游戏本:RTX 4080干到13999元 要闻速递
- 埃文斯谈回归漫威:我很喜欢美队 但现在有些不对劲
- 《DOTA2》柏林Major 4月26日开打 奖金50万美元-全球速递
- 《龙与地下城:侠盗荣耀》北美开画夺冠
- 通灵学院钥匙任务前置_通灵学院的骷髅钥匙和观察室钥匙怎么弄
- 帅丰电器赋能终端,助力集成灶门店实现财富共赢
- 帅丰电器荆州集成灶门店开业活动启动会圆满成功! 当前热点
- 天天百事通!帅丰电器集成灶+集成水槽新品齐上线 速来一睹丰华
- vivo X Flip真机曝光:外屏超大 当前快讯
- 苹果手表被曝令手腕烫伤 真相来了
- 环球观速讯丨CS2的影响力!CSGO三月开箱近4千万 消费超1亿美元
- 德信中国披露业绩补充公告 称开元信德同意公布去年度财报数据 今日热讯
- 真我GT Neo5 SE首销破纪录:1999起 只用1小时
- 天天快消息!女子坐飞机意外发现自己包机了 临时增设、不对外售票
- 不给手机号不能点餐!上海消保委暗访扫码点餐乱象
- CDPR宣布提供月经假:痛经员工可全额带薪按需休假
- 成为螃蟹!这款肉鸽射击游戏《Crab Champions》好评如潮:爽就完事了
- 环球今头条!微星泰坦GP68HX游戏本开启预售 预售价15999元
- 聚焦用户精细化运营场景 极客邦科技与火山引擎数智平台达成合作
- 天天微资讯!真我GT Neo5 SE发布:1999元 骁龙7+旗舰
- 真我GT Neo5 SE普及1.5K屏:144高刷 还有1Tb存储
- 小灵通退出日本市场 一个时代结束了!
- REITS研究行业重大事项点评:扩募启航之际 展望C-REITS市场长远结构
- 身残技坚 国外一《守望先锋2》残疾玩家达到大师段位