7-2 銀行家算法–申請資源 (30 分)（思路+詳解）Come 乖寶寶們

一：前言

這道題需要用到前面的一道題 安全性檢查 算法知識，所以強烈建議先看前面那道題
7-1 銀行家算法–安全性檢查 (20 分)

二：題目

輸入N個進程(N<=100)，以及M類資源（M<=100），初始化各種資源的總數，T0時刻資源的分配情況。例如： 假定系統中有5個進程{P0，P1，P2，P3，P4}和三類資源{A,B,C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配

輸入申請資源的進程以及申請各類資源的數目，判斷是否分配。若分配，輸出”可以找到安全序列，可以分配。“并輸出分配后的系統狀態。若不分配，輸出”找不到安全序列，不予分配。“并輸出當前系統狀態。

輸入格式:
第一行輸入進程數量N，第二行輸入資源類數M，第三行輸入M類資源個類資源的總數，以下N行分別輸入每個進程的名字，該進程對M類資源的最大需求以及已分配資源。最后一行輸入申請進程的名字和申請各類資源的數目。

輸出格式:
若分配，輸出”可以找到安全序列，可以分配。“并輸出分配后的系統狀態。

若不分配，給出不分配的原因：

1.若輸入的進程的名字不正確，輸出”查無此進程。“并輸出當前系統狀態。

2.若申請的資源數目大于最大需求，輸出”需求不合理，不予分配。“并輸出當前系統狀態。

3.若申請的資源數目大于剩余資源，輸出”剩余資源不足，不予分配。“并輸出當前系統狀態。

4.若找不到安全序列，輸出”找不到安全序列，不予分配。“并輸出當前系統狀態。

輸入樣例1:
在這里給出一組輸入。例如：

5 3 10 5 7 P0 7 5 3 0 1 0 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 2 0 0 2 P1 1 0 2 結尾無空行

輸出樣例1:
在這里給出相應的輸出。例如：

可以找到安全序列，可以分配。 name max allocation need available P0 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0 P1 3 2 2 | 3 0 2 | 0 2 0 | P2 9 0 2 | 3 0 2 | 6 0 0 | P3 2 2 2 | 2 1 1 | 0 1 1 | P4 4 3 2 | 0 0 2 | 4 3 0 | 結尾無空行

輸入樣例2:
在這里給出一組輸入。例如：

5 3 10 5 7 P0 7 5 3 0 1 0 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 2 0 0 2 P5 1 0 2

結尾無空行
輸出樣例2:
在這里給出相應的輸出。例如：

查無此進程。 name max allocation need available P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2 P1 3 2 2 | 2 0 0 | 1 2 2 | P2 9 0 2 | 3 0 2 | 6 0 0 | P3 2 2 2 | 2 1 1 | 0 1 1 | P4 4 3 2 | 0 0 2 | 4 3 0 |

結尾無空行

三：思路

思路：
1.我相信如果我們AC出來前面安全性檢查那到題，那么這道題也會很快做出來
2.前面所求的 need 和 Avaliable是 跟這道題一樣的
3.那么接下來我們就是判斷 requst 和 need 和 avaliable之間的關系
其中requset 就是 一個進程p1 申請的資源量
1>: 如果這個進程名輸入錯了 ，那就輸出 查無此進程
2>: 如果上訴條件滿足，那判斷 request 和 Max 關系 request <= Max 就歐克
否則 出輸出”需求不合理，不予分配。“并輸出當前系統狀態。
3>:如果上訴條件滿足，那就判斷 request 和 avaliable之間的關系 request <= avaliable 就歐克
否則 剩余資源不足，不予分配。“并輸出當前系統狀態
4>:當上訴條件均滿足的話 那么 相應的進程的 allocation 和 need 要做出變化
而且其 系統可利用的資源 avaliable也要做出相應的變化
5>:接下來就是 判斷在當前的avaliable下 是否是安全狀態，也就是安全性檢查
如果找到一條安全序列輸出 “可以找到安全序列，可以分配。“并輸出分配后的系統狀態。
如果找不到就輸出”找不到安全序列，不予分配。“并輸出當前系統狀態。

四：坑

需要注意的是當資源分配完成后，如果找不到安全序列的話，那么需要注意的是：
將分配給該進程的資源給收回來 也就是 該進程的need 和 allocation回到 原來的值 同時 還有 avaliable也需要回歸到原來的值

五:上碼：

/**思路：1.我相信如果我們AC出來前面安全性檢查那到題，那么這道題也會很快做出來2.前面所求的 need 和 Avaliable是 跟這道題一樣的3.那么接下來我們就是判斷 requst 和 need 和 avaliable之間的關系其中requset 就是 一個進程p1 申請的資源量 1>: 如果這個進程名輸入錯了 ，那就輸出 查無此進程2>: 如果上訴條件滿足，那判斷 request 和 Max 關系 request <= Max 就歐克否則 出輸出”需求不合理，不予分配。“并輸出當前系統狀態。 3>:如果上訴條件滿足，那就判斷 request 和 avaliable之間的關系 request <= avaliable 就歐克否則 剩余資源不足，不予分配。“并輸出當前系統狀態4>:當上訴條件均滿足的話 那么 相應的進程的 allocation 和 need 要做出變化而且其 系統可利用的資源 avaliable也要做出相應的變化5>:接下來就是 判斷在當前的avaliable下 是否是安全狀態，也就是安全性檢查如果找到一條安全序列輸出 “可以找到安全序列，可以分配。“并輸出分配后的系統狀態。 如果找不到就輸出”找不到安全序列，不予分配。“并輸出當前系統狀態。 **/#include<bits/stdc++.h> using namespace std;int N,M; string str; vector<int>v1;//用于存放各種的資源總量 vector<int>v2;//用于代表申請資源的進程申請的 資源量 vector<int>v3;//用于記錄最初的avaliable struct Node{string processName; int a[100];//Maxint b[100];//allocation int c[100];//needbool finish; } node[1000];//用于判斷是否有該進程 bool judgeExit(string str){for(int i = 0; i < N; i++){if(str == node[i].processName){return true;}}return false; }//用于計算此時的request 和 need bool requestNeed(){int count = 0;for(int i = 0; i < N; i++){int count = 0;if(str == node[i].processName){for(int j = 0; j < M; j++){if(v2[j] <= node[i].c[j]){//請求量 小于 need count++;}} }if(count == M){return true;}}return false;} //用判斷申請的資源數目是否大于剩余資源 bool requestAvaliable(){int count = 0;for(int j = 0; j < M; j++){if(v2[j] <= v1[j]){ //請求量 小于 avaliabale count++;}} if(count == M){return true;}return false;}//判斷當前的安全狀態 bool isSafe(){int cnt = 0; for(int i = 0; i < N; i++){int count = 0;for(int j = 0; j < M; j++){if(node[i].c[j] <= v1[j]){count++;}else{break;//只要有一個不合適就 break 出去 } }if(node[i].finish == false && count == M) {//count == M說明剩余的各個資源總量大于該進程的所需要的 for(int j = 0; j < M; j++){v1[j] += node[i].b[j];//那么此時剩余的資源總量為原來的加上 該進程釋放其占有的資源} node[i].finish = true; cnt++;//記錄完成進程的個數 // cout << node[i].processName << ' ';//此處牛逼之處在于 只要我們找到滿足條件的就從-1開始繼續尋找滿足條件的 i = -1; } }if(cnt == N){return true;}return false; } //用于輸出此時系統的狀態 void state(){int flag = 0;cout << "name max allocation need available" << endl;for(int i = 0; i < N; i++){cout << node[i].processName << ' ';for(int j = 0; j < M; j++){cout << node[i].a[j] << ' '; } cout << "| ";for(int j = 0; j < M; j++){cout << node[i].b[j] << ' '; }cout << "| ";for(int j = 0; j < M; j++){cout << node[i].c[j] << ' '; }cout << "|";if(flag == 0){for(int j = 0; j < M; j++){if(j == 0)cout << ' ' <<v3[j];elsecout << ' ' <<v3[j] ; } flag = 1; } cout << endl; } }int main(){cin >> N >> M;for(int i = 0; i < M; i++){int nums;cin >> nums;v1.push_back(nums); } for(int i = 0; i < N; i++){cin >> node[i].processName;//輸入Max for(int j = 0; j < M; j++){cin >> node[i].a[j]; }//輸入allovation for(int j = 0; j < M; j++){cin >> node[i].b[j];v1[j] -= node[i].b[j];//這里是每次減去分配的資源 那么剩下的最后就是 available }//計算needfor(int j = 0; j < M; j++){node[i].c[j] = node[i].a[j] - node[i].b[j];} node[i].finish = false;}cin >> str;for(int i = 0; i < M; i++){int temp;cin >> temp;v2.push_back(temp);} //將最初的avaliable記錄下來 for(int i = 0; i < M; i++){v3.push_back(v1[i]);} if(judgeExit(str) == false){cout << "查無此進程。" << endl;state();}else if(requestNeed() == false){cout << "需求不合理，不予分配。" << endl;state();}else if(requestAvaliable() == false) {cout << "剩余資源不足，不予分配。" << endl;state();}//此時開始將申請的資源賦值給該進程同時進行安全檢測 else if(judgeExit(str) == true && requestNeed() == true && requestAvaliable() == true){for(int i = 0; i < N; i++){if(str == node[i].processName){for(int j = 0; j < M; j++){node[i].b[j] += v2[j];//這里是更新 該進程的allocation node[i].c[j] -= v2[j];//這里是更新 該進程的needv1[j] -= v2[j]; //這里是更新 該進程的avaliable v3[j] -= v2[j];//存放 最初 avaliable的 }} } if(isSafe() == true){cout << "可以找到安全序列，可以分配。" << endl;state();}else{cout << "找不到安全序列，不予分配。" << endl;//如果不滿足條件的話 需要將原來 進程的的資源分配形式輸出來 for(int i = 0; i < N; i++){if(str == node[i].processName){for(int j = 0; j < M; j++){node[i].b[j] -= v2[j];//這里是更新 該進程的allocation node[i].c[j] += v2[j];//這里是更新 該進程的needv1[j] += v2[j]; //這里是更新 該進程的avaliable v3[j] += v2[j];//存放 最初 avaliable的 }} } state();} }} //5 //3 //10 5 7 //P0 7 5 3 0 1 0 //P1 3 2 2 2 0 0 //P2 9 0 2 3 0 2 //P3 2 2 2 2 1 1 //P4 4 3 2 0 0 2 //P1 2 2 2//name max allocation need available //P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2 //P1 3 2 2 | 2 0 0 | 1 2 2 | //P2 9 0 2 | 3 0 2 | 6 0 0 | //P3 2 2 2 | 2 1 1 | 0 1 1 | //P4 4 3 2 | 0 0 2 | 4 3 0 | //找到安全序列，處于安全狀態。//5 //3 //10 5 7 //P0 7 5 3 0 1 0 //P1 3 2 2 2 0 0 //P2 9 0 2 3 0 2 //P3 2 2 2 2 1 1 //P4 4 3 2 0 0 2 //P0 0 1 0

寶寶們 加油呀 我們共勉 活得坦然 走的自信 堅持熱愛 不負初心！！！！！！！！！！！！！

總結

以上是生活随笔為你收集整理的7-2 银行家算法--申请资源 (30 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

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