1.銀行家算法

銀行家算法是操作系統(tǒng)中死鎖避免的一種算法,這是一個(gè)理想化的方法,一般實(shí)際中很少用到,因?yàn)橐崆爸烂恳粋€(gè)進(jìn)程申請(qǐng)資源的最大需求量,這一般很難控制. 算法的思想: 1.知道系統(tǒng)中每個(gè)資源的資源量. 2.知道每個(gè)進(jìn)程對(duì)每個(gè)資源的最大需求量. 3.當(dāng)給每個(gè)進(jìn)程進(jìn)行申請(qǐng)對(duì)應(yīng)資源的時(shí). 3.1.如果此次申請(qǐng)的資源數(shù)+已經(jīng)持有的資源數(shù)大于了該進(jìn)程的最大需求量,那么則拒絕分配. 3.2.如果此次申請(qǐng)的資源數(shù)+已經(jīng)持有的資源數(shù)小于等于該進(jìn)程的最大需求量.那么就需要和此時(shí)系統(tǒng)中剩余的資源數(shù)進(jìn)行判斷.轉(zhuǎn)到第4步驟. 4.如果系統(tǒng)中剩余的資源數(shù)可以滿(mǎn)足該進(jìn)程尚需的最大資源數(shù),則進(jìn)行分配.否則拒絕分配. 5.如果最后滿(mǎn)足了上面第3和第4的分配后,還需要做最后一步,若給了該進(jìn)程此次的申請(qǐng)資源數(shù),是否可以查找到一個(gè)安全序列,如果可以找到一個(gè)安全序列,那么則最后再分配,否則也不予分配該進(jìn)行的此次的申請(qǐng).

如果可以找到一個(gè)安全序列,則系統(tǒng)處于安全狀態(tài). 如果找不到一個(gè)安全序列,則系統(tǒng)處于不安全狀態(tài).

【資料圖】

注意:如果系統(tǒng)處于不安全的狀態(tài),不一定會(huì)產(chǎn)生死鎖,如果系統(tǒng)產(chǎn)生了死鎖,那么該系統(tǒng)一個(gè)處于不安全狀態(tài).

2.例子和運(yùn)行結(jié)果

3.算法實(shí)現(xiàn)

3.1 定義數(shù)據(jù)結(jié)構(gòu)

#include#include#define KIND_MAX 100//默認(rèn)的資源種類(lèi)數(shù)量#define PROCESS_MAX 100//默認(rèn)的進(jìn)程數(shù)量typedef  struct ResourcesEntity{int  max;//最大的擁有量    int  haved;//還剩下的數(shù)量    int  temp;//臨時(shí)存儲(chǔ)剩余的,檢查安全序列的時(shí)候用到的}RE;typedef struct ProcessEntity {int  maxKindCount[KIND_MAX];//對(duì)每個(gè)資源的最大需求量數(shù)組    int  allocatedKindCount[KIND_MAX];//已經(jīng)分配的種類(lèi)數(shù)量    int  needKindCount[KIND_MAX];//對(duì)每個(gè)資源尚需要的量    int tempKindCount[KIND_MAX];//存儲(chǔ)臨時(shí)申請(qǐng)的資源數(shù)量}PE;

KIND_MAX:默認(rèn)的系統(tǒng)中最大的資源種類(lèi)數(shù)量. PROCESS_MAX:默認(rèn)系統(tǒng)中同時(shí)申請(qǐng)資源進(jìn)程的數(shù)量.

ResourcesEntity:進(jìn)程資源的數(shù)據(jù)結(jié)構(gòu) max:存儲(chǔ)系統(tǒng)中最大擁有該資源的數(shù)量 haved:存儲(chǔ)系統(tǒng)中還剩下的該資源的數(shù)量 temp:用于臨時(shí)存儲(chǔ)申請(qǐng)資源的進(jìn)程申請(qǐng)的數(shù)量,用于尋找安全序列的計(jì)算.

ProcessEntity:進(jìn)程的數(shù)據(jù)結(jié)構(gòu). maxKindCount:數(shù)組中存放該進(jìn)程最每個(gè)資源最大需求量 allocatedKindCount:數(shù)組存放該進(jìn)程已經(jīng)申請(qǐng)到的每個(gè)資源的數(shù)量 needKindCount:數(shù)組存放該進(jìn)程該需要每個(gè)進(jìn)程的數(shù)量 tempKindCount:數(shù)組用存儲(chǔ)該進(jìn)程對(duì)每個(gè)資源的本次申請(qǐng)的數(shù)量.

3.2算法實(shí)現(xiàn)思想

int resources_Size;//資源種類(lèi)總數(shù)int process_Size;//進(jìn)程總數(shù)RE resource[KIND_MAX];//資源種類(lèi)數(shù)組PE process[PROCESS_MAX];//進(jìn)程的數(shù)量

resources_Size:用于存儲(chǔ)動(dòng)態(tài)的資源種類(lèi)數(shù)量. process_Size:用于存儲(chǔ)動(dòng)態(tài)的進(jìn)程數(shù)量. resource:數(shù)組存放資源種類(lèi). process:數(shù)組存放申請(qǐng)資源的進(jìn)程.

1.當(dāng)初始化了系統(tǒng)資源和初始化進(jìn)程 1.1判斷每個(gè)進(jìn)程對(duì)每種資源初始化的數(shù)量是否大于了該進(jìn)程的最大需求量(process[i].needKindCount[j]<0),如果這樣的進(jìn)程數(shù)量大于0,那么拒絕分配.初始化失敗. 1.2.判斷每個(gè)進(jìn)程的最大需求量是否大于了系統(tǒng)最大持有的數(shù)量(resource[j].max-process[i].maxKindCount[j]),如果這樣的進(jìn)程數(shù)量大于了0,則拒絕分配,初始化失敗. 1.3.判斷所有的進(jìn)程對(duì)每種資源已分配的數(shù)量總和是否大于了系統(tǒng)中最大的持有數(shù)量.如果這樣的資源種類(lèi)大于0(resource[j].haved<0),那么拒絕分配,初始化失敗. 1.4.判斷系統(tǒng)是否是安全狀態(tài)(是否找到一個(gè)安全序列),至于怎么尋找安全序列,申請(qǐng)資源的時(shí)候再介紹.如果尋找到了安全序列,則初始化成功,否則初始化失敗. 2.到了這里,表示初始化成功了,下面就是當(dāng)進(jìn)程申請(qǐng)資源的時(shí). 2.1.如果把該進(jìn)程此次申請(qǐng)的資源數(shù)量分配給該進(jìn)程,是否超過(guò)了該進(jìn)程的對(duì)該資源的最大需求量(process[progressNum].maxKindCount[i]-process[progressNum].allocatedKindCount[i]-process[progressNum].tempKindCount[i]),如果小于0表示,超過(guò)了該進(jìn)程的最大需求量,拒絕分配. 2.2判斷該系統(tǒng)剩余的資源數(shù)量是否滿(mǎn)足該進(jìn)程尚需的需求量(resource[i].haved-process[progressNum].needKindCount[i]),小于0表示不滿(mǎn)足,拒絕分配. 2.3如果上面兩個(gè)條件都不符合,那么再判斷若分配給該進(jìn)程此次申請(qǐng)的資源,系統(tǒng)是否處于安全狀態(tài)(尋找安全序列).如果找到安全序列,則分配,更新系統(tǒng)資源和進(jìn)程資源信息,否則拒絕分配. 3.這里介紹尋找安全序列. 3.1:用于數(shù)組存儲(chǔ)安全序列. 3.2.如果安全序列數(shù)組不等于進(jìn)程數(shù)量,則繼續(xù)尋找,否則跳轉(zhuǎn)到3.4步驟 3.3.順序?qū)ふ疫M(jìn)程數(shù)組,找到第一個(gè)滿(mǎn)足該進(jìn)程尚需的資源數(shù)組(needKindCount).如果在安全序列數(shù)組未滿(mǎn)的時(shí)候,未找到滿(mǎn)足條件的進(jìn)程,則查找失敗,未找到安全序列,則拒絕此次的申請(qǐng)?zhí)鰧ふ?轉(zhuǎn)到3.4.如果找到了,則添加到安全序列數(shù)組中,然后更新系統(tǒng)的剩余的每個(gè)資源數(shù)量(存儲(chǔ)在temp數(shù)組中).繼續(xù)跳轉(zhuǎn)到3.2步驟. 3.4如果未找到安全序列,那么拒絕此次分配,如果找到了安全序列,則將申請(qǐng)資源進(jìn)程的信息和系統(tǒng)剩余的資源信息.

3.3方法定義

//重置資源void resetResourcesInfo(void);//重置進(jìn)程void resetProcessInfo(void);//初始化資源void initializeResources(void);//初始化進(jìn)程void initializeProcess(void);//打印Tablevoid printTable(void);//打印占位線void printfLine(int num,char c,int nextLine);//申請(qǐng)資源void applyResource(void);//檢查系統(tǒng)是否安全int checkSecurityStatus(int progressNum,int isInit);//檢查安全序列是否全部查找完成int checkSafeListFinish(int safeList[]);//獲取下一個(gè)安全進(jìn)程位置int getSafeProgressPosition(int safeList[],int progressNum,int  isInit);//打印所有的資源狀況void printfAllResource(void);//菜單int menuBank(void);

3.4方法實(shí)現(xiàn)

//判斷數(shù)組中是否包含此值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("請(qǐng)輸入資源種類(lèi)總數(shù)(例如:若有R1,R2,R3三類(lèi)資源,則輸入3):");    scanf("%d",&resources_Size);    if(resources_Size<=0){printf("系統(tǒng)資源種類(lèi)應(yīng)大于0\n"); resources_size="">KIND_MAX){resources_Size=KIND_MAX;        }        for(int i=0;i<RESOURCES_SIZE;I++){printf("請(qǐng)輸入資源R%d的總數(shù)(大于0):",i+1);            //默認(rèn)的剩余和最大是一樣的            scanf("%d",&resource[i].max);            if(resource[i].max<0){resource[i].max=0;            }            resource[i].haved=resource[i].max;        }           printfAllResource();    }    }//重置進(jìn)程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();}//初始化進(jìn)程void initializeProcess(){//初始化所有進(jìn)程    resetProcessInfo();    //初始化進(jìn)程    printf("請(qǐng)輸入進(jìn)程的數(shù)量:");    scanf("%d",&process_Size);    if(process_Size<=0){printf("進(jìn)程數(shù)量應(yīng)大于0\n"); process_size="">PROCESS_MAX){process_Size=PROCESS_MAX;        }        for(int i=0;i<PROCESS_SIZE;I++){for(int j=0;jprintf("請(qǐng)輸入 進(jìn)程P%-2d<<目前占有>> 資源R%-2d的數(shù)量:",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("請(qǐng)輸入 進(jìn)程P%-2d<<最大需求>> 資源R%-2d的數(shù)量:",i+1,j+1);               scanf("%d",&process[i].maxKindCount[j]);                //尚需的資源數(shù)量(最大需求量-已分配的)                 process[i].needKindCount[j]=process[i].maxKindCount[j]-process[i].allocatedKindCount[j];              }                    }         printTable();        //檢查初始化完畢后,是否安全        //1.檢查每個(gè)進(jìn)程已申請(qǐng)的是否超過(guò)了最大的需求量        //2.檢查每個(gè)進(jìn)程的最大需求量,是否超過(guò)了系統(tǒng)的最大持有量        //3.檢查每個(gè)進(jìn)程已申請(qǐng)的資源,是否超過(guò)了總資源的量        int  isNeedReset=0;//是否重置        //1        for(int i=0;ifor(int j=0;jif(process[i].needKindCount[j]<0){isNeedReset=1; printf("拒絕分配:進(jìn)程%d對(duì)資源%d的申請(qǐng)大于了最大需求量(%d)\n",i+1,j+1,process[i].needKindCount[j]);                 }             }        }         //2.        for(int i=0;i<PROCESS_SIZE;I++){for(int j=0;j//表示進(jìn)程i的對(duì)資源j最大需求量大于了系統(tǒng)持有的資源j的最大量.                  //所以,即使除了當(dāng)前進(jìn)程外全部進(jìn)程都釋放了資源j,也無(wú)法滿(mǎn)足當(dāng)前進(jìn)程的需求量.                  int  re=resource[j].max-process[i].maxKindCount[j];                  if(re<0){isNeedReset=1; printf("拒絕分配:進(jìn)程%d對(duì)資源%d的最大需求量大于了系統(tǒng)最大持有資源R%d數(shù)量\n",i+1,j+1,j+1);                  }              }         }        //3.        for(int j=0;j<RESOURCES_SIZE;J++){if(resource[j].haved<0){isNeedReset=1;                printf("拒絕分配:所有進(jìn)程對(duì)資源%d的已申請(qǐng)輛超過(guò)了系統(tǒng)的最大持有量(%d)\n",j+1,resource[j].haved);            }        }        if(isNeedReset==1){printf("請(qǐng)重新初始化進(jìn)程(菜單編號(hào)2)\n");           //初始化所有進(jìn)程           resetProcessInfo();        }else if(checkSecurityStatus(0,1)==0){printf("請(qǐng)重新初始化進(jìn)程(菜單編號(hào)2)\n");         //初始化所有進(jìn)程          resetProcessInfo();        }    }}//申請(qǐng)資源void applyResource(){printfAllResource();    int pNum;    do{printf("請(qǐng)輸入申請(qǐng)資源的進(jìn)程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.如果是申請(qǐng)的資源    //(1)更新申請(qǐng)資源的進(jìn)程對(duì)應(yīng)的資源數(shù)量    //(2)更新剩余的資源    if(isInit==0){for(int i=0;i<RESOURCES_SIZE;I++){//更新目前占有量:加上申請(qǐng)的資源            process[progressNum].allocatedKindCount[i]=process[progressNum].allocatedKindCount[i]+process[progressNum].tempKindCount[i];            //更新尚需要量:減去申請(qǐng)的資源            process[progressNum].needKindCount[i]=process[progressNum].needKindCount[i]-process[progressNum].tempKindCount[i];            //更新系統(tǒng)剩余的資源:減去申請(qǐng)的資源            resource[i].haved=resource[i].haved-process[progressNum].tempKindCount[i];        }    }    return 1;}//獲取安全進(jìn)程位置角標(biāo)int getSafeProgressPosition(int safeList[],int progressNum,int  isInit){for(int i=0;i=0){isAdd=isAdd&1;                    }else{isAdd=isAdd&0;                                           }                }            }            //系統(tǒng)剩余的資源量滿(mǎn)足當(dāng)前進(jìn)程尚需要量            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;}//打印資源狀態(tài)void printfAllResource(){printfLine(20, "*", 1);    printf("系統(tǒng)資源剩余情況:\n");    for(int i=0;i

3.5算法的注意事項(xiàng)

1.初始化系統(tǒng)資源的時(shí)候也要判斷是否存在安全序列 2.進(jìn)程申請(qǐng)資源的時(shí)候,使用temp存儲(chǔ),計(jì)算安全序列的時(shí)候,也是使用temp中的值進(jìn)行判斷 3.當(dāng)找到安全序列,記得更新申請(qǐng)資源的信息和系統(tǒng)剩余資源的信息.

4源碼下載使用

1.此代碼是在mac系統(tǒng)上的開(kāi)發(fā)工具xcode上開(kāi)發(fā)的,如果下載的代碼要在WIndow系統(tǒng)上的VC6.0或者DevC++開(kāi)發(fā)工具上運(yùn)行,可能會(huì)存在中文亂碼問(wèn)題. 解決辦法: 1.1可以在window上使用記事本打開(kāi),另存為:選擇window系統(tǒng)上開(kāi)發(fā)工具支持的編碼方式. 1.2可以使用笨方法:在window開(kāi)發(fā)工具上新建文件,然后使用記事本打開(kāi)源代碼后復(fù)制到新建的文件上.

2.如果出現(xiàn)不能運(yùn)行的問(wèn)題,就是方法中局部變量問(wèn)題. 例如:

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

就需要把i抽取到方法體的頂部.

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

自己親測(cè)在window上使用上述兩種辦法,解決了問(wèn)題.mac編譯工具到window編譯工具可以運(yùn)行.