世界快看：操作系统中死锁的算法——银行家算法

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;i<LENGTH;I++){if(array[i]==value){return 1;        }    }    return 0;}//打印线void printfLine(int num,char c,int nextLine){for(int i=0;i<NUM;I++){printf("%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"); resources_size="">KIND_MAX){resources_Size=KIND_MAX;        }        for(int i=0;i<RESOURCES_SIZE;I++){printf("请输入资源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;i<PROCESS_MAX;I++){for(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; i<KIND_MAX; --="" i++)="" {resource[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"); process_size="">PROCESS_MAX){process_Size=PROCESS_MAX;        }        for(int i=0;i<PROCESS_SIZE;I++){for(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;i<PROCESS_SIZE;I++){for(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;j<RESOURCES_SIZE;J++){if(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;i安全序列:");    for(int i=0;i<PROCESS_SIZE;I++){if(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<RESOURCES_SIZE;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=0){isAdd=isAdd&1;                    }else{isAdd=isAdd&0;                                           }                }            }            //系统剩余的资源量满足当前进程尚需要量            if(isAdd==1){return i;            }        }            }    return -1;}//检查安全序列是否完成int checkSafeListFinish(int safeList[]){for(int i=0;i<PROCESS_SIZE;I++){if(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;i

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;i<LENGTH;I++){if(array[i]==value){return 1;        }    }    return 0;}

就需要把i抽取到方法体的顶部.

//判断数组中是否包含此值int  isContain(int array[],int length,int value){int i;    for(i=0;i<LENGTH;I++){if(array[i]==value){return 1;        }    }    return 0;}

自己亲测在window上使用上述两种办法,解决了问题.mac编译工具到window编译工具可以运行.