为了处理死锁的问题，即避免死锁，引入了安全序列的思想，所谓安全序列，就是指系统按照某种序列分配资源，则每个进程都能顺利完成，只要找出一个安全序列，系统就处于安全状态。

系统处于安全状态时一定不会发生死锁；系统处于不安全状态可能会发生死锁；

但系统发生死锁时必然处于不安全状态！

因此在分配资源之前先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应该进程的资源分配请求，这就是银行家算法的思想

假设系统中有n个进程、m种资源

 用n*m表示进程与该进程所申请资源的矩阵，。同理用n*m的分配矩阵表示对所有进程的资源分配情况

设资源总数数组Available【】为10,5,7,的一个一维向量数组，各进程最开始所需构成的矩阵设为MAX矩阵

在满足进程需求之前，系统会先给各个进程分配一点资源，当然不会直接分配完

则Allocation矩阵表示系统分配的资源

所以MAX[I][J]-ALLOCATION【I】【J】=Need[i][j];

Need矩阵表示各个进程此时还需要的资源

假设p1进程的MAX=7,5，3系统分配给他的Allocation=0，1，0；此时系统资源还剩下3,3,2，显然满足不了p1的需求，但此时Available可满足p2与p3的Need，所以先分配给他们

此时AVAILABLE=（3,3，2）-Need（1,2,3）=（2,1,0）p2得到满足

MAX(3,2,2)+Available（2,1,0）=（5,3,2）以此类推

涉及到的数据结构：

长度为m的一维数组Available表示系统中还有多少可用资源；

n*m矩阵MAX表示各进程对资源的最大申请数；

n*m矩阵Allocation表示系统已经先给各个进程分配的资源；

MAX-Allocation=Need矩阵，表示现在各进程最多还需多少资源；

用长度为m的一维数组Request表示此次申请的各种资源数；

可用银行家算法预判本次分配是否令系统处于不安全状态；

核心思想：

如果 Request[j]<=Need[i][j](0<=j<=m)   便执行下一步；

如果 Request[j]<=Allocation[j] 便执行下一步，否则表示 尚无申请资源，pi进程进入等待

前两部确认无误后，执行算法：

Available-=Available-Request;

Allocation[i][j]=Allocation[i][j]+Request[j];

#include<pch.h>
#include<stdlib.h>
#include<stdio.h>
#define False 0
#define True 1

/*****数据结构 ****/
char NAME[100] = { 0 };//系统资源总数数组 
int MAX[100][100] = { 0 };//各进程最大需求量矩阵
int Allocation[100][100] = { 0 };//系统事先分配给各进程的资源数矩阵 
int Available[100] = { 0 };//目前可用资源矩阵 
int Need[100][100] = { 0 };//进程还需要资源矩阵 
int Request[100] = { 0 };//进程请求资源向量 
int Work[100] = { 0 };//存放系统可提供资源量 
int Finish[100] = { 0 };//标记系统是否有足够的的资源分配给各个进程 
int Security[100] = { 0 };//存放安全序列

int M = 100;//进程最大数（矩阵的列） 
int N = 100;//资源最大数 （矩阵的行） 

/*****初始化数据：输入进程数量、资源种类、各种资源可利用数量******/
int i, j;
int m, n;
int number, flag;
char name;//输入资源名称
int temp[100] = { 0 };//统计已经分配的资源数量
//输入系统的总资源数目以及各资源初需个数
	 printf("系统可用资源种类为：");
	scanf("%d", &n);//矩阵行 
	N = n;
	for (i = 0; i < n; i++)
	{
		printf("资源种类%d的名称", i);
		fflush(stdin);//清空输入流入缓冲区的字符 
		scanf("%c", &name);//随便起名
		NAME[i] = name;
		printf("资源%c的初始个数为：", name);
		scanf("%d", &number);
		Available[i] = number;
	}
	//输入进程数以及各个进程所需的最大资源矩阵
	printf("\n请输入进程的数量");
	scanf("%d", &m);//矩阵列 
	M = n;
	printf("请输入各进程的最大需求矩阵的值【MAX】：\n");
	do {

		flag = False;
		for (i = 0; i < M; i++)
			for (j = 0; j < N; j++) {
				scanf("%d", &MAX[i][j]);
				if (MAX[i][j] > Available[j])
					flag = True;
			}
		if (flag)
			printf("资源的最大需求量大于系统总资源量，请从新输入！\n");
	} while (flag);
	do
	{
		flag = False;
		printf("请输入各进程已被提前分配的资源数量[Allocation]:\n");
		for (i = 0; i < M; i++)
		{
			for (j = 0; j < N; j++)
			{
				scanf("%d", &Allocation[i][j]);
				if (Allocation[i][j] > MAX[i][j])
					flag = True;
				Need[i][j] = MAX[i][j] - Allocation[i][j];
				temp[j] = temp[j] + Allocation[i][j];/***统计已经分配给各个进程的资源数目*/

			}
		}
		if (flag)
			printf("事先分配的资源大于系统总资源，请从新输入！\n");

	 while (flag);
	/**求得系统中目前可利用的资源数量*/
	for (j = 0; j < N; j++) {

		Available[j] = Available[j] - temp[j];/**/
/
	}
	/******显示资源分配矩阵*****/

	void showdata();/**/
	{

		int i, j;
		printf("***************************\n");
		printf("系统目前可用的资源【available】：\n");
		for (i = 0; i < N; i++)
			printf("%c", NAME[i]);
		printf("\n");
		printf("系统当前分配的资源如下:\n");
		printf("   MAX   Allocation   Need\n");
		printf("进程名  ");
		//输出与当前进程同行的资源名MAX,Allocation，Need分别对应如下
		for (j = 0; j < 3; j++)
		{
			for (i = 0; i < N; i++)
			{
				printf("%c", NAME[i]);
				printf("  ");

			}
			printf("\n");
			/**输出每个进程的MAX，Allocation，Need；*/
			for (i = 0; i < M; i++)

				printf("P%d ", i);

			for (j = 0; j < N; j++)
				printf("%d  ", MAX[i][j]);
			printf("  ");
			for (j = 0; j < N; j++)
				printf("%d", Allocation[i][j]);
			printf(" ");
			for (j = 0; j < N; j++)
				printf("%d", Need[i][j]);

		}	printf("\n");
	}
	/********尝试分配资源*****/
	int test(int i);//试探性的将资源分配给第i个进程;
	{

		for (j = 0; j < N; j++)
		{
			Available[j] = Available[j] - Request[j];
			Allocation[i][j] = Allocation[i][j] + Request[j];
			Need[i][j] = Need[i][j] - Request[j];

		}
		return(void)True;
	}
	/********试探性分配资源作废*********/
	int Retest(int i);//与test操作相反;
	{
		for (j = 0; j < N; j++) {

			Available[j] = Available[j] + Request[j];
			Allocation[i][j] = Allocation[i][j] - Request[j];
			Need[i][j] = Need[i][j] + Request[j];
		}
		return(void)True;
	}

	/**********安全性算法***********/
	int safe();
	{
		int i;
		int j;
		int k = 0;
		int m;
		int apply;
		//初始化work：存放系统可提供资源量数组
		for (j = 0; j < N; j++)
			Work[j] = Available[j];
		//初始化finish ：标志数组，标志系统现在是否有足够的资源提供给进程
		for (i = 0; i < M; i++)
			Finish[i] = False;
		//开始求得安全序列
		for (i = 0; i < M; i++) {

			apply = 0;
			for (j = 0; j < N; j++)
			{
				if (Finish[i] == False && Need[i][j] <= Work[j])

				{
					apply++;
					//一直到每类资源需求数都小于系统可分配资源数才开始分配，否则一直循环等待

					if (apply == N) {
						for (m = 0; m < N; m++)
							Work[m] = Work[m] + Allocation[i][m];//更改当前可分配资源
						Finish[i] = True;
						Security[k++] = 1;
						i = 1; //保证每次查询都从第一个进程开始

					}
				}
			}


		}


		for (i = 0; i < M; i++)
		{
			if (Finish[i] == False)
			{
				printf("系统处于不安全序列");// 剩余的可利用系统总资源数无法满足剩下任意进程的Need；进入不安全序列

				return (void)False;
			}
			else {
				printf("系统是安全的！\n");
				printf("存在一个安全序列：");
				for (i = 0; i < M; i++)
				{
					printf("P%d", Security[i]);  //输出运行在安全序列的数组
					if (i < M - 1)

						printf("->");
				}
				printf("\n");
				return (void)True;
			}
		}
		/************利用银行家算法对申请资源尝试进行分配****************/
		void bank();// 分配资源函数

		{
			int flag = True;//标志变量，判断能否进入银行家算法的下一步
			int i;
			int j;
			printf("请输入进程P%d要申请的资源个数\n", i);
			for (i = 0; i < N; i++)
			{
				printf("%c", NAME[j]);
				scanf("%d", &Request[j]);//输入要申请的资源

			}

			//下面判断银行家算法的两条前提是否成立
			for (j = 0; j < N; j++)
			{
				if (Request[j] > Need[i][j])//判断进程的申请资源数是否大于其需求数，大于则出错，无法进行下一步
				{
					printf("进程P%d申请的资源数大于系统目前可利用数", i);
					printf("分配不合理，不予分配！");
					flag = False;
					break;

				}
				else {
					if (Request[j] > Available[j])//判断申请是否大于当前可分配的资源，若大于则出错 

						printf("进程%d的申请资源数大于目前可用资源数", i);
					printf("\n");
					printf("系统尚无足够资源，不予分配！\n");
					flag = False;
					break;
				}
			}
		}
		//当前两个条件成立的情况下才可以尝试分配资源，然后再寻找安全序列
		if (flag)
		{
			test(i);//根据进程需求数量试探性的分配资源
			showdata(); //根据进程需求数量显示分配后的资源
			if (safe()) //寻找安全数列
			{
				Retest(i);
				showdata();

			}

		}
	}

	int main();
	{//主函数
		char choice;
		printf("\t----------------------------------------------\n");
		printf("\t||                    //\n");
		printf("\t||        银行家算法的实现     //\n");
		printf("\t||                  //\n");
		printf("\t||                  //\n");
		printf("\t||          在此输入个人姓名：*****//\n");
		printf("\t||                    //\n");
		printf("\t----------------------------------------------\n");
		int();//初始化数据
		showdata();//显示各种资源
		if (!safe())
			exit(0);

		do
		{



			printf("********************************************\n");
			printf("\n");
			printf("\n");
			printf("\t-----------银行家算法演示-----------------\n");
			printf("          R(r):请求分配     \n");
			printf("          E(e):退出         \n");
			printf("\t------------------------------------------\n");
			printf("请选择： ");
			fflush(stdin);//还是清空输入缓冲区的字符
			scanf("%c", choice);
			switch (choice)
			{
			case 'r':
			case 'R':
				void bank();
				break;
			case 'e':
			case 'E':
				exit(0);
			default: printf("请正确做出您的选择！\n");
				break;
			}

		} while (choice);
	}
}

前言

要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

1）安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

2）不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。

那么什么是安全序列呢？

安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

算法思路

参数介绍：

n：系统中进程的总数

m：资源类总数

Available：可用剩余资源

Max：最大需求

Allocation：已分配资源

Need：需求（缺少）资源

安全性检查的步骤：

step (1)

Work=Available;

Finish=false;

step (2)

寻找满足条件的i：

a.Finish==false;

b.Need<=Work;

如果不存在，goto step(4)

step(3)

Work=Work+Allocation;

Finish=true;

goto step(2)

step (4)

若对所有i，Finish=true，则系统处于安全状态，否则处于不安全状态

代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

/*
 *  n：系统中进程的总数
 *  m：资源总数
 */
int n, m;
/*
 *  Available：可用剩余资源
 *  Max：最大需求
 *  Allocation：已分配资源
 *  Need：需求资源
 */
int **Max, **Allocation, **Need, *Avaliable;
/*
 *  Work：动态存储当前Available的值
 *  Finish：判断进程i是否为安全序列之一（0：不是  1：是）
 *  result：存储安全序列
 */
int *Work, *Finish;
vector<int> result;

bool check() {
	Work = new int[m];
	for (int i = 0; i < m; i++) {
		Work[i] = Avaliable[i];
	}
	Finish = new int[n];
	memset(Finish, 0, n * sizeof(Finish));  // 初始化数组为0

	for (int tmp = 0; tmp < n; tmp++) {
		for (int i = 0; i < n; i++) {
			if (Finish[i] == 0) {
				int ans = 0;
				for (int j = 0; j < m; j++) {
					if (Need[i][j] <= Work[j]) {
						ans++;
					}
				}
				if (ans == m) {  // 满足安全序列条件
					for (int j = 0; j < m;j++) {
						Work[j] += Allocation[i][j];
					}
					Finish[i] = 1;
					result.push_back(i);
					break;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (Finish[i] == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	cout << "请输入进程总数n和资源总数m：" << endl;
	cin >> n >> m;
	
	// 动态初始化二维数组
	Max= new int *[n];
	Allocation = new int *[n];
	Need = new int*[n];
	for (int i = 0; i < n; i++) {
		Max[i] = new int [m];
		Allocation[i] = new int [m];
		Need[i] = new int[m];
	}
	Avaliable = new int[m];

	cout << "请输入各个进程已分配的资源数（Allocation）：" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程" << char('A' + i) << "：";
		for (int j = 0; j < m; j++) {
			cin >> Allocation[i][j];
		}
	}
	cout << "请输入各个进程的最大需求资源数（Max）：" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程" << char('A' + i) << "：";
		for (int j = 0; j < m; j++) {
			cin >> Max[i][j];
		}
	}
	cout << "请输入当前系统可用剩余资源数（Avaliable）：" << endl;
	for (int i = 0; i < m; i++) {
		cin >> Avaliable[i];
	}
	// 手动计算各个进程缺少的资源数（Need）
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			Need[i][j] = Max[i][j] - Allocation[i][j];
		}
	}

	if (check()) {
		cout << "系统处于安全状态!\n安全序列为：";
		for (int x : result) {
			cout << char('A' + x) << " ";
		}
		cout << endl;
	}
	else {
		cout << "系统处于非安全状态!！" << endl;
	}
	return 0;
}


/*

4 3
1 0 0
5 1 1
2 1 1
0 0 2
3 2 2
6 1 3
3 1 4
4 2 2
1 1 2

*/

银行家算法——输出所有安全序列

银行家算法的具体思路可见我的另一篇文章 点击了解

思路:递归从N个进程里选一个满足条件的进程作为一个安全序列的第一个元素，之后再各自从剩下的进程中选择满足条件的作为第二个元素……

问题:由于确定每一个安全序列、以及确定安全序列的每一个元素的过程中Finish[i]和Work[j]都在变化，所以需要一个撤回操作的步骤(回溯）

和深度优先搜索类似

代码如下

#include<string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max 10
int PN;           //进程数
int RT;           //资源数
int Resourse[max];//资源种类
int Available[max];//系统剩余资源
int Work[max]; //工作向量
int Allocation[max][max];//进程已分配资源
int Need[max][max];//进程目前资源需求
int MAX[max][max];//进程最大资源需求
int Request[max];//申请
bool Finish[max];//完成标志
int sum;//安全序列计数
int choice;//选择申请资源
typedef struct
{
	int SafeOrder[max];
	int top;
}stack;
void push(stack *s, int x)
{
	s->SafeOrder[s->top] = x;
	s->top++;
}
void pop(stack *s)
{
	s->top--;
}
stack Order;
void printOrder()
{
	int i;
	sum++;
	if (sum == 1) printf("当前系统安全！\n");
	printf("第%d个安全序列: ", sum);
	for (i = 0; i < PN; i++)
	{
		if (i == 0)
			printf("P%d", Order.SafeOrder[i]);
		else
			printf("->P%d", Order.SafeOrder[i]);
	}
	printf("\n");
}
void IsSafe(int k)
{
	int i, j;
	if (k == PN)  //找到了一种安全性序列，打印输出
	{
		printOrder();
		return;
	}
	for (i = 0; i<PN; i++)
	{
		if (!Finish[i])
		{
			bool flag = true;
			for (j = 0; j<RT; j++)
				if (Need[i][j] > Work[j])
					flag = false;
			if (flag)//暂时放入安全性队列
			{
				for (j = 0; j < RT; j++)
					Work[j] += Allocation[i][j];
				Finish[i] = true;
				push(&Order, i + 1);//满足要求的进程放进安全序列
				IsSafe(k + 1);     //搜索下一个
				pop(&Order);       //回溯，将第i个进程所做的改变恢复,也就是弹出刚刚放进去的进程
				for (j = 0; j<RT; j++)
					Work[j] -= Allocation[i][j];
				Finish[i] = false;
			}
		}
	}
}
void Input(int a, int b, int c[max][max])
{
	int i, j;
	for (i = 0; i < b; i++)
		if (i == 0) printf("    R%d ", i + 1);
		else printf("R%d ", i + 1);
		printf("\n");
		for (i = 0; i < a; i++)
		{
			printf("P%d  ", i + 1);
			for (j = 0; j < b; j++)
				scanf("%d", &c[i][j]);
		}
}
void init()
{
	int i, j;
	sum = 0;
	Order.top = 0;
	printf("初始化: 请输入进程个数和资源总类: ");
	scanf("%d%d", &PN, &RT);
	printf("请输入各类资源数量: \n");
	for (i = 0; i < RT; i++)
		printf("R%d ", i + 1);
	printf("\n");
	for (i = 0; i < RT; i++)
		scanf("%d", &Resourse[i]);
	printf("请输入每个进程对每种资源的最大需求量:\n");
	Input(PN, RT, MAX);
	printf("请输入各类资源已分配量:\n");
	Input(PN, RT, Allocation);
	for (i = 0; i < PN; i++)
		for (j = 0; j < RT; j++)
			Need[i][j] = MAX[i][j] - Allocation[i][j];
	for (i = 0; i < RT; i++)
	{
		int s[max] = { 0 };
		for (j = 0; j < PN; j++)
			s[i] += Allocation[j][i];
		Available[i] = Resourse[i] - s[i];
		Work[i] = Available[i];
	}
	for (j = 0; j < PN; j++)
		Finish[i] = false;
}
bool  Apply()//进程资源申请
{
	int i;
	printf("选择申请资源的进程: P");
	scanf("%d", &choice);
	printf("输入各类资源申请数量\n");
	for (i = 0; i < RT; i++)
		printf("R%d ", i + 1);
	printf("\n");
	for (i = 0; i < RT; i++)
		scanf("%d", &Request[i]);
	for (i = 0; i < RT; i++)
		if (Request[i] <= Need[choice - 1][i])
		{
			if (Request[i] > Available[i])
			{
				printf("资源不足！"); return false;
			}

		}
		else//申请超出所需
		{
			printf("申请超出所需！"); return false;
		}
	return true;
}
bool banker()
{
	sum = 0;
	Order.top = 0;
	int i = choice - 1, j;
	for (j = 0; j < RT; j++)//试分配
	{
		Available[j] -= Request[j];
		Allocation[i][j] += Request[j];
		Need[i][j] -= Request[j];
		Work[j] = Available[j];
	}
	for (j = 0; j < PN; j++)
		Finish[j] = false;
	IsSafe(0);
	if (sum == 0)
	{
		for (j = 0; j < RT; j++)
		{
			Available[j] += Request[j];
			Allocation[i][j] -= Request[j];
			Need[i][j] += Request[j];
			Work[j] = Available[j];
		}
		return false;
	}
	return true;
}
void print()
{
	int i, j;
	printf("\n资源已分配|资源尚需: \n");
	for (i = 0; i < RT; i++)
		if (i == 0) printf("           R%d    ", i + 1);
		else printf("R%d    ", i + 1);
		printf("\n");
		for (i = 0; i < PN; i++)
		{
			printf("   P%d   :", i + 1);
			for (j = 0; j < RT; j++)
				printf("%2d|%-2d ", Allocation[i][j], Need[i][j]);
			printf("\n");
		}
		printf("系统剩余:");
		for (i = 0; i < RT; i++)
			printf("  %-4d", Available[i]);
		printf("\n");
}
void Menu()
{
	printf("------------------Banker-----------------------\n");
	printf("*              1.初始化数据                    *\n");
	printf("*              2.检验T0时刻安全性              *\n");
	printf("*              3.资源申请                      *\n");
	printf("*              4.退出                          *\n");
	printf("------------------------------------------------\n");
}
void  main()
{
	bool flag1, flag2;
	Menu();
Initialization:init();
	IsSafe(0);
	if (sum == 0)
	{
		printf("当前系统处于不安全状态,请重新初始化!\n");
		goto Initialization;

	}
	else print();
Application: flag1 = Apply();
	if (flag1)
	{
		flag2 = banker();
		if (!flag2)
		{
			printf("资源申请造成系统处不安全状态!申请失败!请重新申请\n");
			goto Application;
		}
		else
		{
			printf("申请成功!");
			print();
		}
	}
	else
	{
		printf("申请失败!请重新申请\n");
		goto Application;
	}
	int n;
	printf("是否还有进程申请资源? 是请输入1,否请输入0 :");
	scanf("%d", &n);
	if (n == 1)
		goto Application;
}