世界快看：操作系統中死鎖的算法——銀行家算法

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編譯工具可以運行.