操作系统之银行家算法—详解流程及案例数据
操作系統(tǒng)之進(jìn)程調(diào)度——優(yōu)先權(quán)法和輪轉(zhuǎn)法（附上樣例講解）
操作系統(tǒng)之銀行家算法—詳解流程及案例數(shù)據(jù)
操作系統(tǒng)之多線程編程—讀者優(yōu)先/寫者優(yōu)先詳解
操作系統(tǒng)之存儲(chǔ)管理——FIFO算法和LRU算法
操作系統(tǒng)之磁盤調(diào)度——SCAN實(shí)例講解
要求
銀行家是操作系統(tǒng)比較經(jīng)典的算法之一，他比較好的防止死鎖情況的出現(xiàn)，增加了系統(tǒng)的安全性.在編寫銀行家算法的過程中，對(duì)操作系統(tǒng)的銀行家算法有了深入了解和心得。
一、實(shí)驗(yàn)?zāi)康?/strong>
死鎖會(huì)引起計(jì)算機(jī)工作僵死，因此操作系統(tǒng)中必須防止。本實(shí)驗(yàn)的目的在于讓學(xué)生獨(dú)立的使用高級(jí)語(yǔ)言編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，了解死鎖產(chǎn)生的條件和原因，并采用銀行家算法有效地防止死鎖的發(fā)生，以加深對(duì)課堂上所講授的知識(shí)的理解。
二、實(shí)驗(yàn)要求
設(shè)計(jì)有n個(gè)進(jìn)程共享m個(gè)系統(tǒng)資源的系統(tǒng)，進(jìn)程可動(dòng)態(tài)的申請(qǐng)和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。
系統(tǒng)能顯示各個(gè)進(jìn)程申請(qǐng)和釋放資源，以及系統(tǒng)動(dòng)態(tài)分配資源的過程，便于用戶觀察和分析；
三、數(shù)據(jù)結(jié)構(gòu)
1．可利用資源向量Available ，它是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源的數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available（j）=k，標(biāo)是系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。
2．最大需求矩陣Max，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max（i，j）=k，表示進(jìn)程i需要Rj類資源的最大數(shù)目為k。
3．分配矩陣Allocation，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中的每類資源當(dāng)前一分配到每一個(gè)進(jìn)程的資源數(shù)。如果Allocation（i，j）=k，表示進(jìn)程i當(dāng)前已經(jīng)分到Rj類資源的數(shù)目為k。Allocation i表示進(jìn)程i的分配向量，有矩陣Allocation的第i行構(gòu)成。
4．需求矩陣Need，這是一個(gè)n×m的矩陣，用以表示每個(gè)進(jìn)程還需要的各類資源的數(shù)目。如果Need（i，j）=k，表示進(jìn)程i還需要Rj類資源k個(gè)，才能完成其任務(wù)。Need i表示進(jìn)程i的需求向量，由矩陣Need的第i行構(gòu)成。
上述三個(gè)矩陣間存在關(guān)系：Need（i，j）=Max（i，j）-Allocation（i，j）；
四、安全性算法
1．設(shè)置兩個(gè)向量。
Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)目，它包含m個(gè)元素，開始執(zhí)行安全性算法時(shí)，Work = Available。
Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開始Finish（I）=false；當(dāng)有足夠資源分配給進(jìn)程Pi時(shí)，令Finish（i）=true；
2．從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程。
Finish（i）= = false；
Need i ≤work；
如找到則執(zhí)行步驟3；否則，執(zhí)行步驟4；
3．當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行直到完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行
Work = work Allocation i
Finish（i）=true；轉(zhuǎn)向步驟2；
4．若所有進(jìn)程的Finish（i）都為true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。
流程圖：
個(gè)人覺得。總的來(lái)說，銀行家算法就是一個(gè)模擬借錢。判斷假如借錢是否安全然后考慮借不借的問題。
先放代碼，和數(shù)據(jù)再說分析：
代碼
import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class bank {static Scanner sc=new Scanner(System.in);static int n;static int m;static int available[];static int max[][];//最大需求矩陣static int allocation[][];//當(dāng)前分配到每一個(gè)進(jìn)程的static int need[][];//需求矩陣static boolean isrelesed[];//資源是否已經(jīng)釋放public static void main(String[] args) {// TODO 自動(dòng)生成的方法存根 System.out.println("請(qǐng)輸入資源種類m：");m=sc.nextInt();//系統(tǒng)資源initm(m);//初始相關(guān)System.out.println("輸入進(jìn)程數(shù)量");n=sc.nextInt();//進(jìn)程數(shù)量initn(n);//初始相關(guān)矩陣//getstatus();//輸出當(dāng)前狀態(tài)while(true) {applyresouse();//申請(qǐng)資源}}static void applyresouse()//申請(qǐng)資源{getstatus();//輸出狀態(tài)int request[]=new int[m];//需求量 為了節(jié)省空間寫成全部變量System.out.println("輸入你想申請(qǐng)資源的編號(hào)");int index=sc.nextInt();while(0>index||index>=n) {System.out.println("輸入的編號(hào)不在編號(hào)范圍之內(nèi)，請(qǐng)重新輸入");index=sc.nextInt(); }while(isrelesed[index]) {System.out.println("改編號(hào)已經(jīng)完成資源的釋放，無(wú)法再請(qǐng)求資源，請(qǐng)重新輸入");index=sc.nextInt();while(0>index||index>=n) {System.out.println("輸入的編號(hào)不在編號(hào)范圍之內(nèi)，請(qǐng)重新輸入");index=sc.nextInt(); }}System.out.println("請(qǐng)輸入"+m+"個(gè)資源申請(qǐng)的個(gè)數(shù)（不申請(qǐng)的資源用0替代）");int team=0;while(team==0) {for(int i=0;i<m;i++){request[i]=sc.nextInt();if(request[i]>available[i]) {team=1;}if(request[i]>max[index][i]) {team=2;}}if(team==1) {System.out.println("您的請(qǐng)求量超出 了系統(tǒng)提供量，請(qǐng)重新輸入");team=0;}//重新循環(huán)else if(team==2) {System.out.println("您的請(qǐng)求量超出 了最大請(qǐng)求量max，請(qǐng)重新輸入");team=0;}else team=3;//退出循環(huán)用}//賦值成功后開始boolean isfinish= ifallocate(index,request);if(isfinish) {System.out.println("所有進(jìn)程完成資源分配，分配結(jié)束");System.exit(0);}} private static boolean ifallocate(int index,int[] request) {//假設(shè)分配/** 首先要將真的數(shù)組克隆，模擬已經(jīng)給資源，然后判斷這個(gè)資源是否安全*/int work[]=available.clone();boolean finish[]=isrelesed.clone();//克隆初始狀態(tài)int need2[][]=new int[n][m];int allocate2[][]=new int[n][m];for(int i=0;i<n;i++){need2[i]=need[i].clone();allocate2[i]=allocation[i].clone();}for(int i=0;i<m;i++){if(need[index][i]<request[i])request[i]=need[index][i];//可以借這么多錢但是我不需要這么多錢anwork[i]-=request[i];//假設(shè)把錢借出去allocate2[index][i]+=request[i];}//需要把need2重置一下for(int i=0;i<m;i++){need2[index][i]-=request[i];}boolean isallocate=issafety(work, finish, need2, allocate2);if(!isallocate) {System.out.println("分配造成進(jìn)程不安全,取消分配"); return false;}else {System.out.println("分配成功");//分配成功就要分配資源for(int i=0;i<m;i++){available[i]-=request[i];allocation[index][i]+=request[i];need[index][i]-=request[i];//System.out.println(request[i]);}if(!isrelesed[index])//判斷改資源是否釋放{boolean jud=false;for(int j=0;j<m;j++){if(need[index][j]!=0)jud=true;}if(!jud)//資源需要釋放 {isrelesed[index]=true;for(int j=0;j<m;j++){available[j]+=allocation[index][j];}}} }boolean isfinished=true;for(int i=0;i<n;i++){for(int j=0;j<m;j++) {if(need[i][j]!=0) {isfinished=false;return false;}}}return isfinished;}private static boolean issafety(int work[],boolean finish[],int need2[][],int allocate2[][])//模擬的需求和分配{//int work[]=available.clone();//不能直接等于復(fù)制。可以了解下對(duì)象克隆或者深淺復(fù)制。Queue<Integer>q1=new ArrayDeque<Integer>();//如果能完成的隊(duì)列int time=0;while(true){boolean loop=true;for(int i=0;i<n;i++)//n個(gè)進(jìn)程模擬{time++;if(!finish[i]) {boolean b=false;//完成不了的for(int j=0;j<m;j++){if(work[j]<need2[i][j]){b=true;//完成不了的}if(b) {break;}}if(!b) {//可以完成的,釋放資源time=0;//重新計(jì)數(shù)q1.add(i);finish[i]=true;//已經(jīng)完成for(int j=0;j<m;j++){work[j]+=allocate2[i][j];//allocate2[i][j]+=need2[i][j];need2[i][j]=0;}//打印System.out.print("進(jìn)程"+i+" max:");for(int j=0;j<m;j++){System.out.print(max[i][j]+" ");}System.out.print("allocate2: ");for(int j=0;j<m;j++){System.out.print(allocate2[i][j]+" ");}System.out.print("need2: ");for(int j=0;j<m;j++){System.out.print(need2[i][j]+" ");}System.out.print("work: ");for(int j=0;j<m;j++){System.out.print(work[j]+" ");}System.out.println();}}}boolean isfinish=false;for(int i=0;i<n;i++) {if(!finish[i]) {isfinish=true;break;}}if(!isfinish) {return true;}if(time>n) {return false;}}//return false;}static void initm(int m){System.out.println("請(qǐng)輸入"+m+"種資源的最大量");available=new int[m];isrelesed=new boolean[m];//request=new int[m];for(int i=0;i<m;i++)//初始aviliable{available[i]=sc.nextInt();}}static void initn(int n){max=new int[n][m];allocation=new int[n][m];need=new int[n][m];//finish=new boolean[n];for(int i=0;i<n;i++){System.out.println("進(jìn)程"+i+"的最大需求為：（輸入m個(gè)數(shù)）");boolean jud=false;//判斷輸出是否有誤for(int j=0;j<m;j++){max[i][j]=sc.nextInt();if(max[i][j]>available[j]) {jud=true;}}if(jud) {System.out.println("最大需求輸入有誤，請(qǐng)重新賦值（m個(gè)數(shù)）");i--;}//i自減滿足條件}System.out.println("n個(gè)線程m種資源最大需求賦值完成\n請(qǐng)輸入當(dāng)前進(jìn)程已分配資源情況");//初始maxfor(int i=0;i<n;i++)//初始allocate矩陣{System.out.println("進(jìn)程"+i+"已分配資源為：（輸入m個(gè)數(shù)）");boolean jud=false;for(int j=0;j<m;j++){allocation[i][j]=sc.nextInt();if(allocation[i][j]>max[i][j]){jud=true;}}if(jud) {System.out.println("輸入有誤，請(qǐng)重新輸入");i--;}//輸入有錯(cuò)誤}System.out.println("allocate(當(dāng)前已分配矩陣已經(jīng)分配完畢)");}static void getstatus()//輸出狀態(tài){for(int i=0;i<n;i++){for(int j=0;j<m;j++){need[i][j]=max[i][j]-allocation[i][j];}}for(int i=0;i<n;i++){System.out.print("進(jìn)程"+i+"的狀態(tài)為：max: ");for(int j=0;j<m;j++) {System.out.print(" "+max[i][j]+" ");}System.out.print("allocatem: ");for(int j=0;j<m;j++) {System.out.print(" "+allocation[i][j]+" ");}System.out.print("need: ");for(int j=0;j<m;j++) {System.out.print(" "+need[i][j]+" ");}System.out.print("avaliable: ");for(int j=0;j<m;j++) {System.out.print(" "+available[j]+" ");}System.out.println();}} }分析
A還—>借B—>B還—>C—這樣可以到最后。但是很多情況下客戶是分期借的，這就要考慮安全性問題，比如A借6，6，6還剩4，4，4那么這個(gè)銀行做多最多只能借2，2，2給其他人，因?yàn)橐坏┙瓒嗔薃也無(wú)法釋放，那么就造成死鎖。那么這種情況就不能夠借錢。所以在借錢的時(shí)候需要一個(gè)模擬的過程。
- 還有比較重要的是明白銀行加算法各個(gè)矩陣的意義和作用非常的重要，我剛開始看銀行家算法的時(shí)候因?yàn)閷?duì)一些基礎(chǔ)概念和數(shù)組矩陣的屬性不夠了解，茫然了很久，也走了很多的坑。那么就先介紹一下吧。
- 對(duì)于全局變量，我的代碼中有：
- 這些變量是在安全狀態(tài)下的真實(shí)變量其中:
- (1)n是線程的數(shù)量，m是資源的種類。
- Available[]是當(dāng)前還可以使用的資源。也就是銀行家手中被借出去錢，手中還剩余各種錢的數(shù)量。只跟資源有關(guān)
- Max[][]是最大需求矩陣，也可以理解為最終終態(tài)矩陣，因?yàn)檫@個(gè)max的狀態(tài)就是客戶想達(dá)到和滿足的狀態(tài)。也就是線程可以釋放的狀態(tài)。
- Allocate[][]是已分配矩陣。就是客戶已經(jīng)借到的錢。也就是線程已經(jīng)占有的資源量
- Need[][]是還需要資源情況，由max和allcate決定。
- Isrelese[]這個(gè)數(shù)組和線程有關(guān)和資源無(wú)關(guān)，它記錄的就是線程是否達(dá)到終態(tài)，完成資源釋放的情況，，一旦完成借錢就不需要借錢。
- 3：最后在具體實(shí)現(xiàn)的過程中。由于需要模擬過程，還是會(huì)遇到挺多坎的，在理清思路之后。在代碼上還是由挺多要注意的。
第一：對(duì)象克隆（深淺拷貝），在模擬的過程中擁有初始化和真實(shí)數(shù)據(jù)一樣的數(shù)組。但是如果直接賦值那么新對(duì)象指向的還是老數(shù)組的地址，會(huì)造成數(shù)據(jù)紊亂。那么對(duì)象克隆就一定要保證只賦值數(shù)據(jù)，不復(fù)制地址。
第二：模擬數(shù)值的改變，無(wú)論在申請(qǐng)資源，還是釋放資源的時(shí)候，模擬的數(shù)值都會(huì)改變。但是不過如果模擬成功，真實(shí)數(shù)組會(huì)增加多少。這個(gè)需要尤其注意，同時(shí)，如果發(fā)現(xiàn)數(shù)值和預(yù)期不符合可以打斷點(diǎn)單步調(diào)試。
附上我自己的流程圖：
初始化：
借錢：
ps:本人有點(diǎn)菜，這里面可能有挺多的是錯(cuò)誤的。。如果有大佬發(fā)現(xiàn)請(qǐng)指正。
如果對(duì)后端、爬蟲、數(shù)據(jù)結(jié)構(gòu)算法等感性趣歡迎關(guān)注我的個(gè)人公眾號(hào)交流：bigsai
總結(jié)
以上是生活随笔為你收集整理的操作系统之银行家算法—详解流程及案例数据的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 操作系统之进程调度——优先权法和轮转法（
- 下一篇： 操作系统之多线程编程—读者优先/写者优先