為什么80%的碼農都做不了架構師？>>> ??

分析了一下銀行家算法,基于銀行家算法做了一個小程序.

銀行家算法主要用于操作系統進程管理程序中,用于防止死鎖.

接下來這段代碼將模擬這一過程.

首先讓我們知道銀行家算法在進程資源分配中主要做什么:

? ? 進程管理系統掌控著操作系統的一切資源.幾乎每個進程都要向操作系統索要資源.但是系統的資源又有限.試想:

? ? 當操作系統掌握A,B資源,有進程P1,P2,同一時刻,P1和P2都向操作系統索取AB兩個資源,而操作系統卻把A分給了P1,B分給了P2,這個時候P1和P2只占有一半資源,如果它們不釋放,那么這兩個進程就會進入死鎖狀態,在系統中無休止地請求資源.

為了解決這種問題,銀行家算法被應用到進程管理系統中,值得注意的是,之所以叫做銀行家算法,是因為這個算法最早被應用于銀行向客戶貸款的案例中,銀行需要分析貸款是否安全,即一段時間內滿足所有客戶.

?

算法主要過程如下:

1.數據結構

? ? Max矩陣,行號表示進程,列號表示進程所需的最大資源數目.

? ? Allocation矩陣,行號表示進程號,列表示已經分配給進程的資源.

? ? Need矩陣,表示仍然需要的資源數.Need由Max - Allocation得到.

? ? Available向量,用于表示當前系統中可分配的資源.初始化為OS所有可分配資源.

以上數據結構可用1維和2維數組表示.非常簡單.

2.銀行家算法

? ? 1.某進程某時刻向操作系統索要資源,用Request(i)表示,如果系統中有3類資源,則Request(1) = {1,2,3}表示進程1向系統所有A:1 B:2 C:3.

? ? 2.如果Request(i)[ j ] <= Need[i, j]則進入第3步.(i表示進程號,j是資源類,按照3類資源,這里的j該是0,1,2 ),否則報錯.

? ? 3.同樣,如果Request < Available,跳向4,否則報錯.

? ? 4.系統嘗試將資源分配給P(i),然后修改數據結構的值:

????????? ? Available -=?Request ( 向量的減法應該會吧??就是每個元數據相減.)

????????? ? Allocation +=?Request

????????????Need -=?Request

? ? 5.執行安全檢查,若可得出安全序列,則分配給進程資源.若得不出,說明分配資源給該進程是不安全的行為,可能導致死鎖,讓該進程的請求掛起,稍后再嘗試.

?

? ? 安全檢查步驟:

????? ? 1.將Available復制一份兒,命名Work.,為所有進程設置一個Finish向量,默認初始化為false.

????? ? 2.從進程中找出一個進程,Finish為false,Need <= Work.若找到執行3,否則4.

????? ? 3.當進程獲取到資源,執行完畢,然后將它持有的所有資源都會釋放掉.

????????????? ? Work = Work + Allocation

????????????? ? Finish =?true

????????????? ? 跳轉到第二步

????? ? 4.如果所有Finish的元數據都為true,說明所有進程都能執行完畢,則表示系統處于安全狀態.否則,不安全.

(安全序列在安全檢查過程中得出.即一個能夠執行完所有進程的進程號順序.這個序列是不唯一的,找到一個即可.)

3.算法實現代碼

? ? 1.數據結構

????????

//max,need,allocation use matrix to express.private static int[][] Max;private static int[][] Allocation;private static int[][] Need;//about safety.private static int[] Work;private static boolean[] Finish;private static int[] safeSequence;private static int seqCounter = 0;//the resources can be allocated that os handledprivate static int[] Available;private static int processCount = 0;private static int resourceCount = 0;private static int[] Request;

????2.實現模擬分配資源:

//when OS ready,allocate resource to processprivate static boolean allocateRequest(int process){if(process < 0) return false;//1,2.judge Request amount whether is illegalfor(int j = 0; j < resourceCount; j++){if(Request[j] > Need[process][j]){System.out.println("Request amount is over your Need");return false;}if(Request[j] > Available[j]){System.out.println("Request amount is over the amount that OS handled");return false;}}//3.allocate the resource to process.for(int j = 0; j < resourceCount; j++){Available[j] -= Request[j];Allocation[process][j] += Request[j];Need[process][j] -= Request[j];}return true;}

????3.實現安全分析:

//banker algorithm to check whther safe.//if safe,return a serial key.else return null;private static int[] checkSafety(){//init safeSequencesafeSequence = new int[processCount];seqCounter = 0;//1.copy Available to Work.init Finish to falseWork = Available.clone();Finish = new boolean[processCount];int process; //no process choosed.while(true){process = -1;//2.find a process like this finish = false, need < work.for(int i = 0; i < processCount; i++){if(Finish[i] == false){//compare need[i,j] <work[j].i-process number, j-resource number.for(int j = 0; j < resourceCount; j++){if(Need[i][j] > Work[j]){process = -1;break;}process = i;}if(process != -1){safeSequence[seqCounter++] = i;break;}}else{process = -1;}}if(process != -1){//3.if found,work = work + allocatation , finish = true. to step 2.//P[process] exe. and realise the resource,after.for(int j = 0; j < resourceCount; j++){Work[j] += Allocation[process][j];}Finish[process] = true;}else{//4.if finish all is true.safe! else unsafe.for(int i = 0; i < processCount; i++){if(Finish[i] == false)return null;}return safeSequence;}}}

案例分析:

就圖中的表我們使用以上算法代碼進行分析:

表中數據:5個進程

Max矩陣為

其它請參照模糊的表.

分析過程(代碼最后放出.):

1.首先我們輸入有多少個進程和多少種資源,這里輸入5,3:

2.初始化的Available,即系統還未分配的資源和已經分配的資源的總和(這里由表相加可知為 10 5 7):

3

3.接著輸入Max矩陣:

4.接著輸入Allocation矩陣:

5.程序自行計算出Need矩陣.和新的Availble資源:

6.測試當前狀態的安全性:

7.模擬請求,假設現在0號進程需要請求資源以完成任務,請求的資源數為系統總資源數:

程序嘗試分配給進程0資源,但是分配給進程后,發現當前的進程都無法順利執行完畢,因此最后撤銷了分配.

8.我們嘗試重新分配,假設1號進程齊寧求{1,2,2}:

分配成功,分配成功后系統資源數目已發生變化,不會再revoke.

?

下面貼出整個冗余到不能再冗余的代碼:

/* *use java to realise banker algorithm. *@author mrruan(RuanKun) qkmc@outlook.com */import java.util.Scanner; import java.lang.Math;class Banker{//max,need,allocation use matrix to express.private static int[][] Max;private static int[][] Allocation;private static int[][] Need;//about safety.private static int[] Work;private static boolean[] Finish;private static int[] safeSequence;private static int seqCounter = 0;//the resources can be allocated that os handledprivate static int[] Available;private static int processCount = 0;private static int resourceCount = 0;private static int[] Request;public static void main(String[] args){Scanner scn = new Scanner(System.in);System.out.println("Welcome To Bank Algorithm Program");System.out.println("note:this is a algorithm to test safety about multi process");//1.user input the process num and resource num.System.out.println("please input how many processes will be handled:");//no any process to deal with exceptions.processCount = scn.nextInt();System.out.println("please input how many kind of resources will be handled:");resourceCount = scn.nextInt();//init martrixinitMatrix(processCount, resourceCount);//2.input the amount of resources that OS has.System.out.println("please input every amount of the " + resourceCount + " resources(" + resourceCount + " integers,space to seperate)");for(int i = 0; i < resourceCount; i++){//init os resourcesif(scn.hasNextInt())Available[i] = scn.nextInt();//didn't check the safety,may cause exceptions.}System.out.println("now you have the resources and amount:");for(int i = 0; i < resourceCount; i++){System.out.print((char)(i+65)+ "."+Available[i]+" ");}//3.input Max matrixSystem.out.println("\n this step you must input the max resources that every process can handle!");for(int i = 0; i < processCount; i++){System.out.println("input P" + i + " 's max handle resources("+resourceCount+" integers,space to seperate):");System.out.print("P" + i + ": ");for(int j = 0; j < resourceCount; j++){Max[i][j] = scn.nextInt();}}//we should judge if the max needed is out of the resources that os has.for(int i = 0; i < processCount; i++){for(int j = 0; j < resourceCount; j++){try{if(Max[i][j] > Available[j]){//error, process cannot go on because the os cannot afford the resources that the process need.throw new Exception("OS cannot afford the resources that the process needed.the error process is : P" + i);}}catch(Exception e){e.printStackTrace();return;}}}//print the max matrix.System.out.println("this is the max matrix:");for(int i = 0; i < processCount; i++){for(int j = 0; j < resourceCount; j++)System.out.print(Max[i][j] + " ");System.out.println();}//4.now set the resources that processes had handled.System.out.println("this step is to allocate the resources to every process.");for(int i = 0; i < processCount; i++){System.out.println("please input th process P" + i + "'s resources," + resourceCount + " integers,space to seperate:");for(int j = 0; j < resourceCount; j++){Allocation[i][j] = scn.nextInt(); // had not check the exceptions.}}//now check the Allocation whether is legal.for(int i = 0; i < processCount; i++){for(int j = 0; j < resourceCount; j++){try{if(Allocation[i][j] > Available[j]){System.out.println(Allocation[i][j] + " " + Available[j]);throw new Exception("Allocated an illegal amount of resource,the error process is P" + i);}if(Allocation[i][j] > Max[i][j])throw new Exception("you allocated is out of Max.position is : P " + i + " the kind is :" + (char)(j+65));}catch(Exception e){e.printStackTrace();return;}}}//check sum.int tmp = 0; //this is for the follow checking.for(int i = 0; i < resourceCount; i++){for(int j = 0; j < processCount; j++){tmp += Allocation[j][i];}try{if(tmp > Available[i]){throw new Exception("over resource,position is : " + (char)(i + 65));}}catch(Exception e){e.printStackTrace();return;}tmp = 0;}vectorMinusMatrix(Available,Allocation, processCount, resourceCount);//print the allocated matrix.System.out.println("this is the Allocation matrix:");for(int i = 0; i < processCount; i++){for(int j = 0; j < resourceCount; j++)System.out.print(Allocation[i][j] + " ");System.out.println();}System.out.println("this is the Available resources after allocatation:");for(int j = 0; j < resourceCount; j++)System.out.print(Available[j] + " ");System.out.println();//5.get still need matrixNeed = matrixMinusMatrix(Max, Allocation, processCount, resourceCount);System.out.println("this is the Need matrix:");for(int i = 0; i < processCount; i++){for(int j = 0; j < resourceCount; j++)System.out.print(Need[i][j] + " ");System.out.println();}System.out.println("the multi process module has been set up.");System.out.println("please select a option");int sw;while(true){System.out.println("\n 1. check the state whether safe.");System.out.println("2. try to allocate resources to process.");sw = scn.nextInt();switch(sw){case 1:if (checkSafety() != null){System.out.println("it's safe. the safeSequence is ");for(int i = 0; i < seqCounter; i++)System.out.print(safeSequence[i] + " ");}else{System.out.println("it's unsafe.");}break;case 2:int process = -1;Request = new int[resourceCount];System.out.println("please input the process Number:");process = scn.nextInt();System.out.println("please input the requested amount of resource.(it's "+ resourceCount +" integers):");for(int i = 0; i < resourceCount; i++){Request[i] = scn.nextInt();}//then try to allocate the requested resource to process.if(allocateRequest(process))//checkif (checkSafety() != null){System.out.println("after allocated,it's safe. the safeSequence is ");for(int i = 0; i < seqCounter; i++)System.out.print(safeSequence[i] + " ");System.out.println();}else{System.out.println("after allocated,it's unsafe.");//if unsafe,DO NOT allocateif(revokeRequest(process)){System.out.println("Revoked allocation");}}break;}}//6.should get a safe serial key.}/** other methods**///create matrix and init.private static void initMatrix(int processCount,int resourceCount){Max = new int[processCount][resourceCount];Allocation = new int[processCount][resourceCount];Need = new int[processCount][resourceCount];Available = new int[resourceCount];}//vector - matrix.private static void vectorMinusMatrix(int[] vector, int[][] matrix, int row, int col){int sum = 0;//System.out.println("print martrix");//for(int i = 0; i < row; i++)// for(int j = 0; j < col; j++)// System.out.print(matrix[i][j] + " ");for(int i = 0; i < col; i++){for(int j = 0; j < row; j++){sum += matrix[j][i];}//System.out.println("------------------------------------\n"+"the sum is " + sum +"\n------------------------------------");vector[i] -= sum;sum = 0;}}//two matrix minus.private static int[][] matrixMinusMatrix(int[][] matrix1, int[][] matrix2, int row, int col){int[][] rs = new int[row][col];for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){rs[i][j] = Math.abs(matrix1[i][j] - matrix2[i][j]);}}return rs;}//judge whether a vector is bigger than another.//if vector1 > vector2, that means vector1's every elem is bigger than vector2private static boolean compareVector(int[] vector1, int[] vector2,int length){for(int i = 0; i < length; i++){if(vector1[i] < vector2[i])return false;} return true;}//banker algorithm to check whther safe.//if safe,return a serial key.else return null;private static int[] checkSafety(){//init safeSequencesafeSequence = new int[processCount];seqCounter = 0;//1.copy Available to Work.init Finish to falseWork = Available.clone();Finish = new boolean[processCount];int process; //no process choosed.while(true){process = -1;//2.find a process like this finish = false, need < work.for(int i = 0; i < processCount; i++){if(Finish[i] == false){//compare need[i,j] <work[j].i-process number, j-resource number.for(int j = 0; j < resourceCount; j++){if(Need[i][j] > Work[j]){process = -1;break;}process = i;}if(process != -1){safeSequence[seqCounter++] = i;break;}}else{process = -1;}}if(process != -1){//3.if found,work = work + allocatation , finish = true. to step 2.//P[process] exe. and realise the resource,after.for(int j = 0; j < resourceCount; j++){Work[j] += Allocation[process][j];}Finish[process] = true;}else{//4.if finish all is true.safe! else unsafe.for(int i = 0; i < processCount; i++){if(Finish[i] == false)return null;}return safeSequence;}}}//when OS ready,allocate resource to processprivate static boolean allocateRequest(int process){if(process < 0) return false;//1,2.judge Request amount whether is illegalfor(int j = 0; j < resourceCount; j++){if(Request[j] > Need[process][j]){System.out.println("Request amount is over your Need");return false;}if(Request[j] > Available[j]){System.out.println("Request amount is over the amount that OS handled");return false;}}//3.allocate the resource to process.for(int j = 0; j < resourceCount; j++){Available[j] -= Request[j];Allocation[process][j] += Request[j];Need[process][j] -= Request[j];}return true;}//warning:this method should be invoked after allocatation.//or will happen uncaught error.private static boolean revokeRequest(int process){if(process < 0) return false;for(int j = 0; j < resourceCount; j++){Available[j] += Request[j];Allocation[process][j] -= Request[j];Need[process][j] += Request[j];}return true;} }

?

轉載于:https://my.oschina.net/qkmc/blog/1581200

總結

以上是生活随笔為你收集整理的银行家算法回顾[JAVA实现]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。