头歌实验06：处理机调度与死锁--银行家算法

第一关 ：安全性检查

纯享版：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100;
int n, m;   //进程数和资源类别数
int resoure[N]; //m类资源的总数值
int Max[N][N], now[N][N], need[N][N];
//进程对m类资源的最大需求，该进程已经分配到的m类资源
int had[N];
int afford[N];
int queue[N];   //安全队列
string name[N]; //进程的名字
void ini()//输入环节
{
	cin >> n >> m;//输入进程数与进程种类数
	for (int i = 0; i < m; i++)
		cin >> resoure[i];  //每一类资源的总数值
	for (int i = 0; i < n; i++)
	{
		cin >> name[i];
		for (int j = 0; j < m; j++)
			cin >> Max[i][j];   //i进程对j类资源的最大需求
		for (int k = 0; k < m; k++)
		{
			cin >> now[i][k];   //i进程已分配到的k类资源
			need[i][k] = Max[i][k] - now[i][k]; //求出需求量
			had[k] += now[i][k];
            //第k类资源还有的（其实就是所有进程可以释放的资源总和）
		}
	}
	for (int i = 0; i < m; i++)
		resoure[i] -= had[i];
        //每一类资源总数要减去已经分配下去的had数量

    //至此，完成初始化
}
void if_sale()
{
	int isafford[N] = { 0 };
    //用于标记每个进程能否被满足资源需求，初值都为0，表示都尚未确定是否能满足
	for (int i = 0; i < m; i++)
		afford[i] = resoure[i];
    //afford存储了每类资源可用的资源数量，用于模拟试探分配
	int count = 0, pos = 0;
    //count用于记录当前进程满足资源需求的资源种类数量
    //pos用来记录在queue中的位置

    //遍历尝试为每个进程分配资源
	for (int i = 0; i < n; i++)
	{
        //当前进程满足需求的资源种类数量初始化为0
		count = 0;
        //遍历每一类资源
		for(int j=0;j<m;j++)
        //如果该进程尚未被标记已完成 且 需求量<=可用量
			if (isafford[i] == 0 && need[i][j] <= afford[j])
			{
                //当前进程满足需求的资源种类+1
				count++;
                //如果当前进程满足需求的资源种类已经等于全部资源
				if (count == m)
				{
                    //对该进程进行标记
					isafford[i] = 1;

                    //对每一类资源进行遍历，更新可用资源（回收i进程的资源）
					for (int k = 0; k < m; k++)
						afford[k] += now[i][j];

                    //将其放入安全队列
					queue[pos++] = i;
					i = -1;
                    //导致下一次循环重新从第一个进程开始检查
                    //目的是重新遍历所有进程，因为资源情况已经更新，
                    //可能之前不能满足资源需求的进程现在可以满足了。
				}
			}
	}

    //遍历所有进程，看是否所有进程均已被标记
	for(int i=0;i<n;i++)
		if (isafford[i] == 0)
		{
			cout << "找不到安全序列，处于不安全状态。";
			return;
		}
	cout << "找到安全序列，处于安全状态。";
}
int main()
{
	ini();
	if_sale();
}

第二关：请求资源 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100;
int n, m;
int resoure[N];
int Max[N][N], now[N][N], need[N][N];
int had[N];
int afford[N];
int queue[N];
string name[N];
void ini()//输入环节
{
	cin >> n >> m;//输入进程数与进程种类数
	for (int i = 0; i < m; i++)
		cin >> resoure[i];  //每一类资源的总数
    

	for (int i = 0; i < n; i++)
	{
		cin >> name[i];
		for (int j = 0; j < m; j++)
			cin >> Max[i][j];   //i进程对j类资源的最大需求量
		for (int k = 0; k < m; k++)
		{
			cin >> now[i][k];   //i进程已经分配到的k类资源
			need[i][k] = Max[i][k] - now[i][k];     //i还需要多少k类资源
			had[k] += now[i][k];    //had[k]表示k类资源当前已经发了多少
		}
	}
    
    string add; 
    int flag=0;//记录新输入的进程编号
    cin>>add;   //当前申请的进程名

    //遍历所有进程，标记当前申请的进程
    for(int i = 0;i < n;i++)
    {
        if(add == name[i])
            flag = i;
    }

    //add进程对m类资源的申请资源数
    for(int j = 0;j < m;j++)
    {
        int num;
        cin>>num;
        now[flag][j] += num;    //add进程现在已经分配的j类资源增加
        need[flag][j] -= num;   //对j类资源的需求减少
        had[j] += num;          //j类资源的分发量++
    }

	for (int i = 0; i < m; i++)
		resoure[i] -= had[i];
        //计算i类资源当前剩余量
}
bool if_sale()
{
	int isafford[N] = { 0 };

    //afford[i]是剩余量，用来模拟分配
	for (int i = 0; i < m; i++)
		afford[i] = resoure[i];
    
	int count = 0, pos = 0;
    //count用来对i进程中已经满足需求的资源进行计数
    //pos是安全序列的下标
	for (int i = 0; i < n; i++)
	{
		count = 0;
		for(int j = 0; j < m; j++)
        //如果i进程还未被成功标记 且 需求量<=剩余量
			if (isafford[i] == 0 && need[i][j] <= afford[j])
			{
                //满足需求的资源数++
				count++;
                //如果满足需求的资源数=全部资源数
				if (count == m)
				{
                    //将i标记未分配成功
					isafford[i] = 1;
                    //且对i进程的资源进行回收，增加剩余量
					for (int k = 0; k < m; k++)
						afford[k] += now[i][j];
                    
                    //将i进程放入安全序列中
					queue[pos++] = i;
                    
                    //因为资源情况更新，所以需要从头遍历所有进程
					i = -1;
				}
			}
	}
	for(int i=0;i<n;i++)
		if (isafford[i] == 0)
		{
			//cout << "找不到安全序列，处于不安全状态。";
			return false;
		}
	//cout << "找到安全序列，处于安全状态。";
    return true;
}
void show()
{
    cout<<"name max allocation need available"<<'\n';
    for(int i = 0; i < n; i++)
    {
        cout<<name[i]<<" ";
        for(int j = 0; j < m; j++)
            cout<< Max[i][j] << ' ';
        cout<<"| ";
        for(int k = 0; k < m; k++)
            cout<< now[i][k]<< ' ';
        cout<<"| ";
        for(int k = 0; k < m; k++)
            cout<< need[i][k] <<' ';
        cout<<"|";
        if(i == 0)
        {
            cout<<" ";
            for(int k = 0; k <m-1; k++)
                cout<< resoure[k] <<' ';
            cout<<resoure[m-1];
        }
        cout<<'\n';
    }
}
bool CheckNeed()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(need[i][j] < 0)
                return false;
        }
    return true;
}
void bank()
{
    bool con1 = if_sale();  //判断是否能够找到一个安全序列
    bool con2 = CheckNeed();    //检查各个进程的资源需求情况是否合理
    if(con2)
    {
        if(con1)
        {
            cout<<"可以找到安全序列，可以分配。"<<'\n';
            show();
        }
        else 
            cout<<"剩余资源不足，不予分配。";
    }
    else
    {
        if(con1)
            cout<<"剩余资源不足，不予分配。";
        else 
            cout<<"需求不合理，不予分配。";
    }
}

int main()
{
	ini();
	bank();
}