文章檢索器

1 創作的小心思
2 追根溯源
3 演算法設計
- 3.1 銀行家演算法
- - 3.1.1 所需維護的資料結構
  - 3.1.2 演算法執行步驟
  - 3.1.3 流程圖
- 3.2 安全性演算法
- - 3.2.1 所需維護的資料結構
  - 3.2.2 演算法執行步驟
  - 3.2.3 流程圖
4 演算法示例
- 4.1 示例題目
- 4.2 例題求解
5 C++代碼實作
- 5.1 C++源代碼（全）
- 5.2 測驗截圖
- - 5.2.1 初始化
  - 5.2.2 行程1發出資源請求（1，0，1）
  - 5.2.3 行程2發出資源請求（1，0，1）
  - 5.2.4 檢查當前狀態安全性

1 創作的小心思

該作旨在完成老師布置的實驗任務，也借此機會系統的將銀行家演算法再學一遍，也可以蹭一波大家的熱度，嘻嘻🤭，歡迎來訪🎉🎉🎉

2 追根溯源

銀行家演算法（Banker’s Algorithm） 是一個避免死鎖（Deadlock） 的著名演算法，是由艾茲格·迪杰斯特拉在1965年為T.H.E系統設計的一種避免死鎖產生的演算法，它以銀行借貸系統的分配策略為基礎，判斷并保證系統的安全運行，(來源：百度百科)

3 演算法設計

3.1 銀行家演算法

3.1.1 所需維護的資料結構

1、可利用資源向量 A v a i l a b l e Available Available，這是一個含有 m m m個元素的一維陣列，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態的改變，若
A v a i l a b l e [ j ] = K Available[j] = K Available[j]=K,則表示系統中現有 R j R_j Rj? 類資源 K K K 個，

2、最大需求矩陣 M a x Max Max，這是一個 n × m n×m n×m 的矩陣，它定義了系統中 n n n 個行程中的每個行程對 m m m 類資源的最大需求，若 M a x [ i ] [ j ] = K Max[i][j] = K Max[i][j]=K ,則表示行程 i i i 需要 R j R_j Rj? 類資源的最大數目為 K K K ，

3、分配矩陣 A l l o c a t i o n Allocation Allocation，這是一個 n × m n×m n×m 的矩陣，它定義了系統中每一類資源當前已分配給每一行程的資源數，若 A l l o c a t i o n [ i ] [ j ] = K Allocation[i][j] = K Allocation[i][j]=K ,則表示行程 i i i 當前已分得 R j R_j Rj? 類資源的數目為 K K K ，

4、需求矩陣 N e e d Need Need，這是一個 n × m n×m n×m 的矩陣，用以表示每一個行程尚需的各類資源數，若 N e e d [ i ] [ j ] = K Need[i][j] = K Need[i][j]=K ,則表示行程 i i i 還需要 R j R_j Rj? 類資源 K K K個方能完成其任務，

3.1.2 演算法執行步驟

設 R e q u e s t [ i ] Request[i] Request[i] 是行程 P i P_i Pi? 的請求向量，如果 R e q u e s t [ i ] [ j ] = K Request[i][j]=K Request[i][j]=K, 表示行程 P i P_i Pi? 需要 K K K 個 R j R_j Rj?型別的資源，
當 P i P_i Pi? 發出資源請求后，系統按下述步驟進行檢查：
(1)、如果 R e q u e s t [ i ] [ j ] ≤ N e e d [ i ] [ j ] Request[i][j]≤Need[i][j] Request[i][j]≤Need[i][j],便轉向步驟(2); 否則認為出錯，因為它所需要的資源數已經超過它所宣布的最大值，
(2)、如果 R e q u e s t [ i ] [ j ] ≤ A v a i l a b l e [ j ] Request[i][j]≤Available[j] Request[i][j]≤Available[j] ,便轉向步驟(3); 否則，表示尚無足夠資源， P i P_i Pi? 須等待，
(3)、系統試探著把資源分配給行程 P i P_i Pi? ，并修改下面資料結構中的值：
A v a i l a b l e [ j ] = A v a i l a b l e [ j ] ? R e q u e s t [ i ] [ j ] A l l o c a t i o n [ i ] [ j ] = A l l o c a t i o n [ i ] [ j ] + R e q u e s t [ i ] [ j ] N e e d [ i ] [ j ] = N e e d [ i ] [ j ] ? R e q u e s t [ i ] [ j ] Available[j]=Available[j]-Request[i][j] \\ Allocation[i][j]=Allocation[i][j]+Request[i][j] \\ Need[i][j]=Need[i][j]-Request[i][j] Available[j]=Available[j]?Request[i][j]Allocation[i][j]=Allocation[i][j]+Request[i][j]Need[i][j]=Need[i][j]?Request[i][j]
(4)、系統執行安全性演算法，檢查此次資源分配后系統是否處于安全狀態，若安全，才正式將資源分配給行程 P i P_i Pi? ，以完成本次分配；否則，將本次試探分配作廢，恢復原來資源分配狀態，讓行程 P i P_i Pi? 等待，

3.1.3 流程圖

在這里插入圖片描述

3.2 安全性演算法

3.2.1 所需維護的資料結構

1、作業向量 W o r k Work Work, 這是一個含有 m m m 個元素的一維陣列，它表示系統可提供給行程繼續運行所需的各類資源的數目，在執行安全演算法開始時， W o r k = A v a i l a b l e Work=Available Work=Available，（其實和 A v a i l a b l e Available Available 所維護的內容一樣）
2、行程狀態向量 F i n i s h Finish Finish，這是一個含有 n n n 個元素的一維陣列,它表示每一個行程是否運行完成，用布林值來表示行程的狀態， F i n i s h [ i ] = T r u e Finish[i]=True Finish[i]=True 表示行程 P i P_i Pi? 已經運行完成，否則運行未完成，

3.2.2 演算法執行步驟

(1) 從行程集合中找到一個能滿足下述條件的行程：
① F i n i s h [ i ] = F a l s e Finish[i]=False Finish[i]=False;
② N e e d [ i ] [ j ] ≤ W o r k [ j ] Need[i][j]≤Work[j] Need[i][j]≤Work[j];（注意：此處需要所有 m m m 類資源都滿足該條件）
若找到，執行步驟(2)，否則，執行步驟(3)，
(2) 當行程 P i P_i Pi?獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源：
W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i ] [ j ] ; F i n i s h [ j ] = T r u e ; g o t o s t e p 1 ; Work[j]=Work[j]+Allocation[i][j]; \\ Finish[j]=True; \\ go\ to\ step\ 1; Work[j]=Work[j]+Allocation[i][j];Finish[j]=True;go to step 1;
(4) 如果所有行程的Finish[i]=True都滿足，則表示處于安全狀態；否則，系統處于不安全狀態，

3.2.3 流程圖

在這里插入圖片描述

4 演算法示例

4.1 示例題目

4.2 例題求解

在這里插入圖片描述

5 C++代碼實作

5.1 C++源代碼（全）

1.0版本，后續有時間了可能會再回來加強一波，請求資源方面，目前只能一次性分配一個，不能同時得到請求，需要改進，其他的基本功能算是實作了，執行程序的狀態，比交好實作，加個輸出就OK，比較簡單，代碼中就沒實作，

#include<cstdio>
#include<queue>
#include<vector>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 1010;
int n, m;
int Max[N][M], Allocation[N][M], Need[N][M];
int Available[M], Finish[N];
int Work[M], Request[M];
int Sum[M];//系統中m類資源的總量
void Init()
{
	cout << "請輸入合法的矩陣" << endl;
	cout << "初始化Max矩陣" << endl;
	cout << "請輸入一個" << n << "行" << m << "列的矩陣:" << endl;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			cin >> Max[i][j];

	cout << "初始化Allocation矩陣" << endl;
	cout << "請輸入一個" << n << "行" << m << "列的矩陣:" << endl;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			cin >> Allocation[i][j];

	cout << "初始化Available向量" << endl;
	cout << "請輸入一行" << m << "個元素表示當前可用資源的數量:" << endl;
	for (int i = 1;i <= m;i++) cin >> Available[i];

	/*初始化Need矩陣*/
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			Need[i][j] = Max[i][j] - Allocation[i][j];
		}
	}
	/*初始化Sum矩陣*/
	for (int j = 1;j <= m;j++)
	{
		for (int i = 1;i <= n;i++)
		{
			Sum[j] += Allocation[i][j];
		}
		Sum[j] += Available[j];
	}
	cout << "初始化成功>^V^<" << endl;
}
/*判斷初始化矩陣的合法性*/
bool Judge()
{
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			if (Allocation[i][j] > Max[i][j]) return false;
		}
	}
	return true;
}
/*判斷當前work向量是否大于Need[i]向量*/
bool Judge(int k)
{
	for (int j = 1;j <= m;j++)
	{
		if (Need[k][j] > Work[j]) return false;
	}
	return true;
}
/*安全性檢查的時候虛擬處理*/
void VirtureDeal(int k)
{
	for (int j = 1;j <= m;j++)
	{
		Work[j] += Allocation[k][j];
	}
	Finish[k] = true;
}
/*安全性檢查*/
bool SecurityCheck(queue<int>& q)
{
	memcpy(Work, Available, sizeof Available);
	memset(Finish, false, sizeof Finish);
	for(int k = 1;k <= n;k++) //n次迭代
	{
		bool flag = false;
		for (int i = 1;i <= n;i++)
		{
			if (!Finish[i] && Judge(i))
			{
				flag = true;
				q.push(i);
				VirtureDeal(i);
				break;
			}
		}
		if (!flag) return false;
	}
	return true;
}
/*試探性分配資源*/
void Alloc(int k)
{
	for (int j = 1;j <= m;j++)
	{
		Allocation[k][j] += Request[j];
		Need[k][j] -= Request[j];
		Available[j] -= Request[j];
	}
}
/*恢復原狀*/
void Recover(int k)
{
	for (int j = 1;j <= m;j++)
	{
		Allocation[k][j] -= Request[j];
		Need[k][j] += Request[j];
		Available[j] += Request[j];
	}
}
/*請求資源*/
void Query()
{
	int ID;
	cout << "請輸入行程ID(1 -- " << n << "):" << endl; cin >> ID;
	cout << "請輸入請求向量(輸入" << m << "個有效整數):" << endl;
	for (int j = 1;j <= m;j++) cin >> Request[j];
	for (int j = 1;j <= m;j++)
	{
		if (Request[j] > Need[ID][j])
		{
			cout << "出錯，請求的資源大于需求資源" << endl;
			return;
		}
		else if (Request[j] > Available[j])
		{
			cout << "行程無法得到資源，繼續處于等待狀態！" << endl;
			return;
		}
	}
	Alloc(ID);//試探性分配
	queue<int> q;
	if (SecurityCheck(q))
	{
		cout << "分配資源成功！" << endl;
		cout << "其中的一個安全序列是：";
		bool mark = false;
		while (q.size())
		{
			if (mark) cout << "->";
			cout << q.front();q.pop();
			mark = true;
		}
		cout << endl;
	}
	else {
		cout << "無法執行分配任務！" << endl;
		Recover(ID);//無法執行分配，恢復原狀
	}
}
int main()
{
	cout << "請輸入行程個數: "; cin >> n;
	cout << "請輸入資源的種類數: "; cin >> m;
	Init();
	system("pause");
	while (1)
	{
		system("cls");
		cout << "1、請求資源" << endl;
		cout << "2、檢查當前狀態的安全性" << endl;
		cout << "0、退出主程式" << endl;
		while (1)
		{
			int op; cin >> op;
			if (op < 0 || op > 2) {
				cout << "操做錯誤，請重新輸入！！！" << endl;
				system("pause");
			}
			else {
				if (op == 0) exit(0);
				else if (op == 1) {
					Query();
					system("pause");
				}
				else if (op == 2)
				{
					queue<int> q;
					if (SecurityCheck(q))
					{
						cout << "當前狀態安全" << endl;
						cout << "其中的一個安全序列是：";
						bool mark = false;
						while (q.size())
						{
							if (mark) cout << "->";
							cout << q.front();q.pop();
							mark = true;
						}
						cout << endl;
					}
					else {
						cout << "當前狀態不安全，極有可能進入死鎖狀態" << endl;
					}
					system("pause");
				}
			}
			break;
		}
	}
	return 0;
}
/*
Max
3 2 2
6 1 3
3 1 4
4 2 2
Allocation
1 0 0
4 1 1
2 1 1
0 0 2
Available
2 1 2
*/