一：前言

停更一周了，在這一周里，我每時每刻都在 想這我這 29個粉絲，慶幸教師資格證終于結束了，貼心杰又可以天天更新博客了
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，I am come back;

二：題目：

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

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

輸出格式:
輸出T0時刻系統的狀態。若安全，輸出“找到安全序列，處于安全狀態。”否則，輸出“找不到安全序列，處于不安全狀態。”

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

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

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

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.首先我們進行安全性算法是為了預防死鎖，再解釋一下死鎖 比如
1>:在系統中有兩個進程p1,p2 和兩個資源r1(掃描儀)，r2(刻錄機)
p1和p2都需要將掃描的文檔通過刻錄機刻錄到CD盤上，
2>:進程p1先請求資源r1成功，進程p2請求資源r2成功，那么接下來，
p1又申請了r2資源 p2申請了r1資源，那么此時p1和p2都在等對方
釋放資源那么就會發生死鎖，兩個進程都無法進行下去
2.那么安全性算法就是使系統在分配資源時候一直處在安全的狀態（即不會發生死鎖）
那么我們在分配資源的時候就有了算法，即最終分配給各個進程的資源，都不會影響到
整個系統的安全狀態，這時會出現一個進程的執行序列
3.具體解釋算法過程
1>:幾個變量
Max:一個進程所需的最大資源量
Allocation:系統已經給其分配了多少資源
Need:這個進程還需要多少資源
Available:這個系統還剩多少資源
2>:剛開始設置work = Available 將所有進程設置為 finish = false （相當于定義一個flag）

3>:找一個進程滿足下列的條件 finish = falseneed <= work(需要的資源得比系統剩余的要少) 4>:如果 3>的條件滿足的話，我們就需要 將work += Allocation （每個進程執行完后需要釋放資源） finish = true (代表該進程完成) 返回步驟 3>繼續尋找滿足上訴條件的進程

5>:思考如何判定此時的系統狀態是安全還是不安全的
安全:如果 3>的條件不滿足 即此時的所有進程的 finsh = true 說明了所有的進程已經完成
不安全: 我們已經判斷了所有的finish = false 的進程，但是仍未找到滿足條件的
need < work 那么可以判定此狀態為 不安全的狀態
4.處理數據
1>:這里我們選取的數據結構是結構體數組因為一個進程他對應好多屬性，所以選取的是結構體
在結構體的屬性當中 我們設置一個 max[] 和 allocation[] 目的是存放多個不同類型資源
2>:關于node[i].a[j],node[i].b[j],node[i].c[j]的理解，就是3個二維數組 就是這樣的

四：先說坑

1.這個題無語了簡直了真是，不，應該是PTA這個平臺讓我真的無語了，我定義了一個變量 cnt 但我并未初始化為0 ，我在DEV-C中測試了好多數據其實也無妨正確結果，但是在PTA中提交一直顯示答案錯誤，而且測試樣例一直輸出 找不到安全序列，真的一上午我真的想砸電腦，什么呀！！ 最后堅持不懈，不信邪，終于讓我發現一個大毛病，原來在PTA上變量必須初始化，否則系統自動給你賦值一個很大數 ，但在DEV-C上卻沒有任何問題
2.這個題還需要的是無論 是否可以得到安全序列，其都必須將其系統中各個進程的狀態輸出來

五：上碼

/**思路:1.首先我們進行安全性算法是為了預防死鎖，再解釋一下死鎖 比如1>:在系統中有兩個進程p1,p2 和兩個資源r1(掃描儀)，r2(刻錄機)p1和p2都需要將掃描的文檔通過刻錄機刻錄到CD盤上， 2>:進程p1先請求資源r1成功，進程p2請求資源r2成功，那么接下來，p1又申請了r2資源 p2申請了r1資源，那么此時p1和p2都在等對方釋放資源那么就會發生死鎖，兩個進程都無法進行下去2.那么安全性算法就是使系統在分配資源時候一直處在安全的狀態（即不會發生死鎖）那么我們在分配資源的時候就有了算法，即最終分配給各個進程的資源，都不會影響到整個系統的安全狀態，這時會出現一個進程的執行序列3.具體解釋算法過程1>:幾個變量Max:一個進程所需的最大資源量Allocation:系統已經給其分配了多少資源Need:這個進程還需要多少資源Available:這個系統還剩多少資源2>:剛開始設置work = Available 將所有進程設置為 finish = false （相當于定義一個flag）3>:找一個進程滿足下列的條件 finish = falseneed <= work(需要的資源得比系統剩余的要少)4>:如果 3>的條件滿足的話，我們就需要 將work += Allocation （每個進程執行完后需要釋放資源）finish = true (代表該進程完成)返回步驟 3>繼續尋找滿足上訴條件的進程 5>:思考如何判定此時的系統狀態是安全還是不安全的 安全:如果 3>的條件不滿足 即此時的所有進程的 finsh = true 說明了所有的進程已經完成不安全: 我們已經判斷了所有的finish = false 的進程，但是仍未找到滿足條件的need < work 那么可以判定此狀態為 不安全的狀態 ，否則那么就是說明該系統處在不安全的狀態（即會發生死鎖）4.處理數據 1>:這里我們選取的數據結構是結構體數組因為一個進程他對應好多屬性，所以選取的是結構體 在結構體的屬性當中 我們設置一個 max[] 和 allocation[] 目的是存放多個不同類型資源 2>:關于node[i].a[j],node[i].b[j],node[i].c[j]的理解，就是3個二維數組 就是這樣的 */ #include<bits/stdc++.h> using namespace std;struct Node{string processName;//進程名 int a[100];//Max int b[100];//allocation int c[100];//need bool finish;}node[1000];//關于重寫 sort方法中的兩個參數 都表示是一個結構體（即我們需要用兩個結構體當中的數據進行比較） bool sort_c(Node node1,Node node2){return node1.c[0] < node2.c[0]; }int main(){int N,M;int cnt = 0;//用于記進程完成的個數 vector<int>v1;//存總的資源總量 vector<int>v2;//存need需要的資源 vector<int>v3;//記錄最后需要輸出的Available cin >> N >> M;for(int i = 0; i < M; i++){int resources;cin >> resources;v1.push_back(resources); }for(int i = 0; i < N; i++){cin >> node[i].processName;//輸入Max for(int j = 0; j < M; j++){cin >> node[i].a[j];}//輸入allocation 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;//將每個進程初始狀態設為 false } for(int i = 0; i < M; i++){v3.push_back(v1[i]);} // sort(node,node+N,sort_c);//算法核心部分 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; } }// cout << endl;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; }if(cnt == N){ cout << "找到安全序列，處于安全狀態。";}else{cout << "找不到安全序列，處于不安全狀態。";} // for(int i = 0; i < M; i++){ // cout << v1[i] << ' '; // } // 驗證數據 // for(int i = 0; i < N; i++){ // // cout << node[i].processName << ' '; // // for(int j = 0; j < M; j++){ // // cout << node[i].c[j] << ' '; // } // cout << endl; // }}//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 8 6 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//5 //3 //6 3 5 //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//5 //4 //3 14 12 12 //p0 0 0 1 2 0 0 1 2 //p1 1 7 5 0 1 0 0 0 //p2 2 3 5 6 1 3 5 4 //p3 0 6 5 2 0 6 3 2 //p4 0 6 5 6 0 0 1 4

最后 再嘮叨一句 ，記得加油寶！！ 我們共勉 共同進步！！！

總結

以上是生活随笔為你收集整理的7-1 银行家算法--安全性检查 (20 分)(思路+详解+知识分析)宝 你今天 AC了吗的全部內容，希望文章能夠幫你解決所遇到的問題。

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