引子
最近上作業系統課學到了銀行家演算法，起初看課本覺得這個講的是什么，仔細研究了一下發現這個演算法最重要的一點就是安全性檢查了，
抽象的程序
先說一下這個演算法模擬的是什么程序：
假設有一個銀行，里面有人民幣、美元、日元、韓幣等資源，有許多客戶向銀行申請貸款，
每個客戶都可以發出申請先貸款一部分，也可以發出申請貸款全部，比如有個客戶想貸款人民幣3元、美元2元、日元1元，那么他每種資源只申請貸款1元也可以，但是只有全部申請夠了，客戶才會還銀行錢，這個業務才完成了，
銀行要做的事情就是判斷這個客戶的申請是否是獅子大開口，貸款的資源超過了他的需求，如果不是，再判斷銀行是否有分配給這個客戶錢的能力，而這里的能力不僅包括現在的資源是否能夠滿足這個客戶的申請，而且還包括滿足這個客戶的申請后，銀行還有沒有完成全部業務的能力，這也就是所謂的安全性檢查了，
我們用極端的思想想想，如果給一個客戶分了太多資源，將有可能導致銀行面臨一個非常困難的境地——這個客戶的貸款業務還沒有完成所以銀行不能把錢識訓來，而現在銀行的錢太少了，以至于這個客戶和其他客戶的業務都完成不了，所以銀行現在只能給錢還收不回來（客戶會以你沒完成我的貸款業務為借口），
如何進行安全性檢查呢？
我們可以假設銀行已經把錢借給了這個客戶，然后按此情況進行模擬，在這種情況下，銀行如果還能夠完成全部的業務，那么，這個借錢的行為就是安全的，銀行你放心借吧，如果不行，那么銀行你千萬別借，借了之后就不能完成全部業務了，
如何模擬：
這其實是一個大魚吃小魚的游戲（4399、摩爾莊園玩過，，），我們可以把銀行現在有的資源看作是一條大魚，然后把其他客戶的業務看作是一條小魚，銀行完成一個客戶的業務就能收錢，那么銀行就會有更多的資源去完成其他的業務，這也就是一條大魚，吃了其他小魚，變得更大，然后就能吃更大的魚的程序，
需要注意的是，我們并不需要關注大魚吃的每一條小魚的順序，只需要找到比它小的魚并吃掉就可以了，這既節省時間又不會改變結果（可以自己思考一下為什么），
如果“大魚”最后能吃掉全部“魚”，那么這個系統就是安全的，否則，這個系統就是不安全的，
偽代碼
整個演算法思路如下：
為了實作銀行家演算法，在系統中必須設定這樣四個資料結構，分別用來描述系統中可利用的資源、所有行程對資源的最大需求、系統中的資源分配，以及所有行程還需要多少資源的情況，
(1) 可利用資源向量 available，這是一個含有 m 個元素的陣列，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變，如果 Available[j] = K，則表示系統中現Rj類資源K個，
(2) 最大需求矩陣Max，這是一個n x m的矩陣，它定義了系統中n個行程中的每個行程對m類資源的最大需求，如果Max[i,j] = K，則表示行程i需要Rj 類資源的最大數目為K，
(3) 分配矩陣 allocation，這也是一個n x m的矩陣，它定義了系統中每一類資源當前已分配給每一行程的資源數，如果 allocation[i,jl = K，則表示行程i當前己分得j類資源的數目為K，
(4) 需求矩陣need.這也是一個n×m的矩陣，用以表示每一個行程尚需的各類資源數，如果need[i,j] = K，則表示行程i還需要j類資源K個才能完成其業務，
上述三個矩陣間存在下述關系:
need[i,j] = Max[i,j] - allocation[i, j]
假設在行程并發執行時行程i提出請求j類資源k個后，表示為Requesti[j]=k，系統按下述步驟進行安全檢查：
（1）如果Requesti≤Needi則繼續以下檢查，否則顯示需求申請超出最大需求值的錯誤，
（2）如果Requesti≤Available則繼續以下檢查，否則顯示系統無足夠資源，Pi阻塞等待，
（3）系統試探著把資源分配給行程Pi，并修改下面資料結構中的數值：
Available［j］∶=Available［j］-Requesti［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
（4）系統執行安全性演算法，檢查此次資源分配后，系統是否處于安全狀態，若安全，才正式將資源分配給行程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態，讓行程Pi等待，
安全性演算法
（1）設定兩個向量：
作業向量Work: 它表示系統可提供給行程繼續運行所需的各類資源數目，它含有m個元素，在執行安全演算法開始時，Work∶=Available;
Finish: 它表示系統是否有足夠的資源分配給行程，使之運行完成，開始時先做Finish［i］∶=false; 當有足夠資源分配給行程時， 再令Finish［i］∶=true，
（2）從行程集合中找到一個能滿足下述條件的行程：
Finish［i］=false;
Need［i,j］≤Work［j］； 若找到， 執行步驟(3)， 否則，執行步驟(4)，
（3）當行程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：
Work［j］∶=Work［i］+Allocation［i,j］;
Finish［i］∶=true;
go to step 2;
（4）如果所有行程的Finish［i］=true都滿足， 則表示系統處于安全狀態；否則，系統處于不安全狀態，
C++代碼如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int m=3,n=5; //m為銀行資源數目,n為客戶數目
int available[m]={3,3,2}; //目前可用資源向量
const int Max[n][m]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; //最大需求矩陣
int allocation[n][m]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}; //分配矩陣，allocation[i][j]=k表示客戶[i]已經拿到k個m類資源
int need[n][m]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}}; //目前需求矩陣，need[i][j]=Max[i][j]-allocation[i][j];
vector<int> safe_series;
void showNow()
{
printf("\n-------------------------------\n");
printf("目前可用資源:\n");
for(int i=0;i<m;i++)
{
printf("%2d ",available[i]);
}
printf("\n");
printf("\n最大需求矩陣:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
printf("%2d ",Max[i][j]);
}
printf("\n");
}
printf("\n分配矩陣:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
printf("%2d ",allocation[i][j]);
}
printf("\n");
}
printf("\n目前需求矩陣:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
printf("%2d ",need[i][j]);
}
printf("\n");
}
printf("\n-------------------------------\n");
}
//檢查用戶的需求向量是否都為0，若都為0,回傳true
bool is_all_zero(int pid)
{
for(int i=0;i<m;i++)
{
if(need[pid][i]>0)
{
return false; //全部為0才算完成
}
}
return true;
}
//判斷當前系統是否安全
bool is_safe()
{
safe_series.clear();
int work[m]; //用來存盤available資訊,不破壞available
int finish[n]; //finish[i]=true,代表客戶i的業務已經被完成；finish[i]=false，代表客戶i的業務還未被完成
memset(finish,0,sizeof(finish)); //finish[i]全部設定為false
//work初始化
for(int i=0;i<m;i++)
{
work[i]=available[i];
}
int num=0; //記錄已經被完成的業務有多少個
//初始化finish
for(int i=0;i<n;i++)
{
if(is_all_zero(i))
{
finish[i]=true;
num++;
}
}
int index=0;
bool allfinished=false;
//num==n，全部業務已完成，跳出回圈
while(num!=n)
{
bool canfind=false; //記錄這次有沒有找到新的可完成的業務
//查找一個銀行可以完成其業務的客戶
for(int cur=0;cur<n;cur++)
{
if(finish[cur]==false) //該客戶的業務未被完成
{
bool flag=true;
for(int j=0;j<m;j++)
{
if(need[cur][j]>work[j])
{
flag=false;
break;
}
}
if(!flag) //銀行沒有完成其業務的能力
{
continue;
}
else
{
for(int j=0;j<n;j++)
{
work[j]+=allocation[cur][j];
}
finish[cur]=true;
num++;
canfind=true;
safe_series.push_back(cur);
if(num==n)
{
allfinished=true;
break;
}
}
}
}
if(allfinished) break; //全部業務已完成
if(!canfind) break; //這次不能找到可以完成的業務
}
if(allfinished)
{
return true;
}
else
{
return false;
}
}
void print_safe_series()
{
if(is_safe())
{
printf("本次安全檢查發現的安全序列為:\n");
for(int i=0;i<safe_series.size();i++)
{
printf("%d ",safe_series[i]);
}
printf("\n");
}
else
{
printf("系統不安全！！\n");
}
}
int main()
{
string str;
if(is_safe()) printf("該系統是安全的\n");
else
{
printf("該系統是不安全的，請重新設定系統變數");
return 0;
}
while(1)
{
printf("請輸入接下來的操作(input為輸入請求向量，output為輸出目前系統資訊，print_safe為輸出安全序列，exit為退出系統)：\n");
cin>>str;
if(str=="input")
{
int request[m],pid;
printf("請輸入客戶id:\n");
cin>>pid;
printf("請輸入該客戶的請求向量:\n");
for(int i=0;i<m;i++)
{
cin>>request[i];
}
//檢查該客戶是否獅子大開口
bool flag=false;
for(int i=0;i<m;i++)
{
if(request[i]>need[pid][i])
{
flag=true;
break;
}
}
if(flag)
{
printf("你要的太多了朋友\n");
continue;
}
//檢查銀行是否有足夠的資源滿足該客戶
flag=false;
for(int i=0;i<m;i++)
{
if(available[i]<request[i])
{
flag=true;
break;
}
}
if(flag)
{
printf("銀行太窮，沒辦法滿足你\n");
continue;
}
//先給客戶錢，后面安全檢查發現不行，會把錢識訓來
//更新現在的資源數目
for(int i=0;i<m;i++)
{
available[i]-=request[i];
}
//更新該客戶已被分配多少money
for(int i=0;i<m;i++)
{
allocation[pid][i]+=request[i];
}
//更新該客戶的需求矩陣
for(int i=0;i<m;i++)
{
need[pid][i]-=request[i];
}
//該用戶的業務已被完成,直接回收資源，若回收資源之后系統還是不安全的，只能說這個銀行系統一開始就是不安全的，所以在開頭應該對系統進行安全性檢查
if(is_all_zero(pid))
{
//回收客戶i的全部資源
for(int i=0;i<m;i++)
{
available[i]+=allocation[pid][i];
}
memset(allocation[pid],0,sizeof(allocation[pid]));
printf("客戶%d的業務已被完成\n",pid);
continue;
}
if(!is_safe()) //該請求是不安全的
{
//還原現在的資源數目
for(int i=0;i<m;i++)
{
available[i]+=request[i];
}
//還原該客戶已被分配多少money
for(int i=0;i<m;i++)
{
allocation[pid][i]-=request[i];
}
//還原該客戶的需求矩陣
for(int i=0;i<m;i++)
{
need[pid][i]+=request[i];
}
printf("該請求會導致銀行系統不安全！\n");
}
else
{
printf("請求成功！");
printf("本次安全檢查發現的安全序列為:\n");
for(int i=0;i<safe_series.size();i++)
{
printf("%d ",safe_series[i]);
}
printf("\n");
}
}
else if(str=="output")
{
showNow();
}
else if(str=="print_safe")
{
print_safe_series();
}
else if(str=="exit")
{
break;
}
else
{
printf("您輸入的字符有誤，請重新輸入，\n");
}
}
return 0;
}
運行截圖如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/218610.html
標籤：其他
上一篇：記一次簡單域滲透（part 1）