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

大大源码 • 2023年4月18日 pm10:39 • 其他

第一关

任务：
本关任务：编写函数，完成相关的代码，输入系统的进程数、资源数以及进程分配情况，判断系统是否处于安全状态。

说明：
输入格式说明：
第1行是系统的进程数N
第2行是系统的资源类别数M
第3行是系统的资源总数，一共有M个数值，每个数值是一类资源的总数。
第4行开始一共有N行，每一行的数据是：
进程名称（字符串）该进程对M类资源的最大需求该进程已分配的资源

预期输出：
判断当前系统是否处于安全状态，若安全，输出“找到安全序列，处于安全状态。”
否则，输出“找不到安全序列，处于不安全状态。”
测试输入：

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

上答案：

#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];
		for (int k = 0; k < m; k++)
		{
			cin >> now[i][k];
			need[i][k] = Max[i][k] - now[i][k];
			had[k] += now[i][k];
		}
	}
	for (int i = 0; i < m; i++)
		resoure[i] -= had[i];
}
void if_sale()
{
	int isafford[N] = { 0 };
	for (int i = 0; i < m; i++)
		afford[i] = resoure[i];
	int count = 0, pos = 0;
	for (int i = 0; i < n; i++)
	{
		count = 0;
		for(int j=0;j<m;j++)
			if (isafford[i] == 0 && need[i][j] <= afford[j])
			{
				count++;
				if (count == m)
				{
					isafford[i] = 1;
					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();
}

第二关

任务：
本关任务：编写函数，完成相关的代码，输入系统的进程数、资源数、申请资源的进程以及申请各类资源的数目，判断是否分配。若分配，输出“可以找到安全序列，可以分配。”并输出分配后的系统状态。若不分配，输出“找不到安全序列，不予分配。”
说明：
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

输入格式说明：
第1行是系统的进程数N
第2行是系统的资源类别数M
第3行是系统的资源总数，一共有M个数值，每个数值是一类资源的总数。
第4行开始一共有N行，每一行的数据是：
进程名称（字符串）该进程对M类资源的最大需求该进程已分配的资源
最后1行是进程的当前申请，包括：
进程名（字符串）申请资源数（M个数值）
预期输出：
对当前进程的资源请求判断是否分配。
若分配，输出“可以找到安全序列，可以分配。”并按照格式输出当前资源分配情况，包括进程名称、最大需求、已获得资源、可利用资源向量。例如T0时刻，当前的资源分配情况如下：

并若不分配，给出不分配的原因：
(1).若申请的资源数目大于最大需求，输出“需求不合理，不予分配。”
(2).若申请的资源数目大于剩余资源，输出“剩余资源不足，不予分配。”
(3).若找不到安全序列，输出“找不到安全序列，不予分配。”
测试输入：

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
P1 1 0 2

输出：

可以找到安全序列，可以分配。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0
P1 3 2 2 | 3 0 2 | 0 2 0 |
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 |

上答案：

#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];
		for (int k = 0; k < m; k++)
		{
			cin >> now[i][k];
			need[i][k] = Max[i][k] - now[i][k];
			had[k] += now[i][k];
		}
	}
    
    string add;
    int flag=0;//记录新输入的进程编号
    cin>>add;
    for(int i=0;i<n;i++)
    {
        if(add == name[i])
            flag = i;
    }
    for(int j=0;j<m;j++)
    {
        int num;
        cin>>num;
        now[flag][j]+=num;
        need[flag][j]-=num;
        had[j]+=num;
    }

	for (int i = 0; i < m; i++)
		resoure[i] -= had[i];
}
bool if_sale()
{
	int isafford[N] = { 0 };
	for (int i = 0; i < m; i++)
		afford[i] = resoure[i];
	int count = 0, pos = 0;
	for (int i = 0; i < n; i++)
	{
		count = 0;
		for(int j=0;j<m;j++)
			if (isafford[i] == 0 && need[i][j] <= afford[j])
			{
				count++;
				if (count == m)
				{
					isafford[i] = 1;
					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 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();
}

说明以及操作：

1，相关数据结构的说明：

由题目中的数据可以得知：
起码有name,max,allocation(我用的now表示),need,avialable(我用的resoure表示)这5个数组一直要用
所以我就把这几个都整成数组了。
其中name我用字符串数组来整。

2，其中函数说明：

1，输入函数：
我以第二关的举例说明：

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];//输入这个进程中这一类资源的最大需求
		for (int k = 0; k < m; k++)
		{
			cin >> now[i][k];//这个是输入这一类进程中这一类资源已经用了的
			need[i][k] = Max[i][k] - now[i][k];
			//这个是计算need数组了
			had[k] += now[i][k];
			//had数组表示目前已经用了的
			//方便后面计算
		}
	}
    
    //以下就为第二关的输入了
    string add;
    int flag=0;//记录新输入的进程编号
    cin>>add;
    for(int i=0;i<n;i++)
    {
        if(add == name[i])
            flag = i;
    }
    for(int j=0;j<m;j++)
    {
        int num;
        cin>>num;
        now[flag][j]+=num;
        need[flag][j]-=num;
        had[j]+=num;
    }//由于第二关要多输入一行，所以整这一些来

	for (int i = 0; i < m; i++)
		resoure[i] -= had[i];
}//更新资源数组

2，安全性检查函数：
这里我也用第二关的函数

bool if_sale()
{
	int isafford[N] = { 0 };//这个数组就表示
	//标记这个进程是否被用过，用过的话就是1
	//同时，经过循环后，如果还是0的话，就表示有进程不合格
	for (int i = 0; i < m; i++)
		afford[i] = resoure[i];//这个数组就用来记录当前的内存剩余状态了
	int count = 0;//这是一个计数器
	//int pos = 0;
	for (int i = 0; i < n; i++)
	{
		count = 0;
		for(int j=0;j<m;j++)
			if (isafford[i] == 0 && need[i][j] <= afford[j])//当当前进程没有被用过
			//并且需要的资源小于还有的资源的时候，就进行这一步
			{
				count++;//+1
				if (count == m)//当计数器达到这个数目时
				{//代表这个进程资源足够，可以完成
					isafford[i] = 1;//用过
					for (int k = 0; k < m; k++)
						afford[k] += now[i][j];//回收资源~
					//queue[pos++] = i;//这个嘛，可要可不要~毕竟这个题好像用不到
					i = -1;//当这一次i循环结束后，i++，从0再来，这样可以防止遗漏
				}
			}
	}
	for(int i=0;i<n;i++)
		if (isafford[i] == 0)
		{
			//cout << "找不到安全序列，处于不安全状态。";
			return false;
		}
	//cout << "找到安全序列，处于安全状态。";
    return true;
}

3，需求检查函数：
这个以第二关的为例：
其实我们可以发现：

需求不合理时，need里会有负数存在
所以这样：

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;
}

4，打印函数：

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';
    }
}

5，银行家函数：

void bank()
{
    bool con1 = if_sale();
    bool con2 = CheckNeed();
    if(con2)
    {
        if(con1)
        {
            cout<<"可以找到安全序列，可以分配。"<<'\n';
            show();
        }
        else 
            cout<<"剩余资源不足，不予分配。";
    }
    else
    {
        if(con1)
            cout<<"剩余资源不足，不予分配。";
        else 
            cout<<"需求不合理，不予分配。";
    }
}