Part5. 避免死锁——银行家算法的实现

往期回顾：
Part0. 实验环境
Part1-1.熟悉UKylin环境
Part1-2.熟悉UKylin环境
Part2.进程控制
Part3.进程通信
Part4.管道通信

一、实验目的

1.了解避免死锁的原理。
2.研究银行家算法的实现方法。

二、实验内容

编程实现银行家算法，语言不限。程序中设置资源向量和各个矩阵的元素个数及初始值，由用户通过输入界面输入某进程对各类资源的请求向量，由程序判断是否能为用户请求进行资源分配，并显示结果。

银行家算法的分析、设计与实现

（一）算法设计理论描述

银行家算法的基本思想是：始终保持系统处于安全状态，当进程提出资源请求时，系统先进行预分配，再判断系统分配后是否仍然处于安全状态。如果仍然处于安全状态，就进行实际分配；如果处于不安全状态，则撤销预分配、拒绝该进程的资源请求。
操作系统按照银行家指定的规则为进程分配资源，当进程首次申请资源时，测试对资源的最大需求量，如果系统现存的资源可以满足其最大需求量则按当前申请量分配资源，否则推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配，若没有超过在测试系统现存的资源能否满足该进程尚需的最大资源量，如果可以满足则按当前的申请量分配资源，否则也要推迟分配。

（二）数据结构模型及算法描述

1、需要用到的数据结构：
(1)int n,m; //进程总数n和资源种类数m
(2)int Pi; //发出请求向量的进程
(3)int Max[N][N]={0}; //各进程所需各类资源的最大需求
(4)int Available[N]={0}; //系统可用资源向量
(5)int Allocation[N][N]={0}; //各进程已分配资源
(6)int Need[N][N]={0}; //各进程还需要资源
(7)int Requesti[N]={0}; //进程的请求资源向量
(8)int temp[N]={0}; //存放安全序列
(9)int Work[N]={0}; //存放系统可提供使用资源，工作向量
(10)int Finish[N]={0}; //初始值均为0，表示系统是否有足够的资源分配给进程，当有足够资源时置为1
(11)char name[N]={0}; //资源的名称，可以根据设计定义成一维数组或二维数组
(12)int times = 0; //记录发出请求的次数
2、银行家算法描述：（进程Pi发出请求资源申请）
(1)如果Requesti[i]≤Need[Pi][i]，因为进程Pi所需要的资源数已经超过它所宣布的最大值，系统不安全，输出提示资源超过所宣布的最大值，即“请求资源大于该进程所需要的资源!”。
(2)如果Requesti[i]≤Available[i]，表示尚无足够资源，输出提示申请资源超出可利用的资源，系统不安全，即“可用资源不足，无法满足请求!”。
(前两点在函数Check_Need_Available_Requesti()中实现判断)
(3)若以上两个条件都满足则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：(以下公式中的符号均与代码一致）
Available[j]= Available[j]- Requesti [j]；
Allocation[Pi][j]= Allocation[Pi][j]+ Requesti [j]；
Need[Pi][j]= Need[Pi][j]- Requesti [j]；
(4)预分配资源后，执行安全性检查，调用Check()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；如果系统不安全，恢复原来的资源分配状态，让该进程等待。
(5)注意：需要特别判断分配资源后当前进程的Need矩阵中对应Pi进程的行向量是否是零向量。如果是，需要进一步修改Available矩阵和Allocation矩阵，相当于进程Pi已经执行完，将所分配到的所有资源进行释放，进而执行下一个进程请求；如果不是，只分配资源，不释放已分配矩阵中的资源。
(6)全程用while循环语句实现输入字符Y/N判断用户是否继续进行资源申请，如果是，则按提示继续操作；如果不是，则显示本次请求次数，并退出系统。
3、安全性算法描述：
(1)设置两个向量：工作向量Work,它表示系统可提供给进程运行所需的各类资源数目，在执行安全性算法时，Work[i]=Available[i];用Finish向量来表示系统是否有足够的资源分配给进程使系统保持安全状态；开始时先初始化Finish[i]=0；当有足够资源分配给进程时，再令Finish[i]=1。
注意：为了防止在安全性算法检测时，改变可利用资源的原始数据，故定义一个临时一维数组t_Available[i]=Available[i]，在安全性算法检测中使用临时数组进行安全状态检查。
(2)从进程集合通过遍历中找到一个能满足下述条件的进程:(以下公式中的符号均与代码一致）
① Finish[i]=0;
② Need[i][j]≤Work[j];(在函数Check_Need_Work(i)中实现判断)
若找到，执行步骤(3)，并break本次循环；执行完n次后，执行步骤(4)。
(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源：(以下公式中的符号均与代码一致）
Work[j]=Work[j] + Allocation[i][j];
Finish[i]=1; break;
go to step (2);
(4)如果所有进程的Finish[i]=1都满足，则表示系统处于安全状态，返回true，并输出一个安全序列；否则，系统处于不安全状态，返回false。
4、流程图如下所示：
(1)系统流程图：

(2)银行家算法：

(3)安全性算法：

（三）源代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
using namespace std;
//数据结构
#define False 0
#define True 1
#define  N  100              //作业数量，资源数量的最大值均为100
int n,m;                     //进程总数n和资源种类数m
int Pi;                      //发出请求向量的进程
int Max[N][N]={0};           //各进程所需各类资源的最大需求
int Available[N]={0};        //系统可用资源向量
int Allocation[N][N]={0};    //各进程已分配资源
int Need[N][N]={0};          //各进程还需要资源
int Requesti[N]={0};         //进程的请求资源向量
int temp[N]={0};             //存放安全序列
int Work[N]={0};             //存放系统可提供使用资源，工作向量
int Finish[N]={0};           //初始值均为0，表示系统是否有足够的资源分配给进程，当有足够资源时置为1
char name[N]={0};            //资源的名称，可以根据设计定义成一维数组或二维数组
int times = 0;               //记录发出请求的次数
//函数声明
void Print();                           //格式化输出显示，其中stew()函数表示控制字符输出间隔
bool Check_Need_Work(int pi);           //检查进程pi的需求向量是否都不大于工作向量
bool Check();                           //利用安全性算法对资源分配情况进行分析，检查此时系统是否安全
bool Check_Need_Available_Requesti();   //检查进程pi的需求向量是否都不大于需求向量和可利用资源向量
bool Banker();                          //进程Pi发出请求向量Requesti后，系统按银行家算法进行检查

int main()
{
    cout<<"请依次输入 进程总数N 和 资源种类数M（格式如:N M）："<<endl;
    cin>>n>>m;
    cout<<"请分别输入 最大需求矩阵 Max 和 已分配矩阵 Allocation："<<endl;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)  cin>>Max[i][j];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)  cin>>Allocation[i][j];
        for(int j=0;j<m;j++)  Need[i][j] = Max[i][j] - Allocation[i][j];   //需求矩阵 = 最大需求矩阵 - 已分配矩阵
    }
    cout<<"请输入各类资源的名称："<<endl;
    for(int i=0;i<m;i++)  cin>>name[i];
    cout<<"请输入各类资源的数量："<<endl;
    for(int i=0;i<m;i++)  cin>>Available[i];
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            Available[i] = Available[i] - Allocation[j][i];   //剩余可用资源=总的资源数量-进程已分配的资源
    }
    cout<<endl<<"初始时刻的资源分配情况如下："<<endl;
    Print();            //打印输出初始时刻的资源分配情况
    bool s = Check();   //利用安全性算法进行检测，判断当前系统是否处于安全状态
	if(!Check())  cout<<"目前该系统处于不安全状态！"<<endl;
    while(1)
    {
        char YorN = 'Y';
        cout<<"请问是否要发出进程的资源请求？（格式：Y or N）请输入：";
        cin>>YorN;
        if(YorN == 'N')
        {
            cout<<"您本次共计请求"<<times<<"次，系统已退出！"<<endl;
            break;
        }
        else if(YorN == 'Y')
        {
            times++;
            cout<<"请输入第"<<times<<"次即将发出请求的进程Pi:";
            cin>>Pi;
            cout<<"请输入进程P"<<Pi<<"的请求向量Requesti（格式为:A B C）："<<endl;
            for(int i=0;i<m;i++)  cin>>Requesti[i];
            if(Banker())         //调用银行家算法，进行检查，如果系统在分配后仍存在安全序列，则予以分配
            {
                cout<<"第"<<times<<"次请求后的资源分配情况如下："<<endl;
                Print();         //打印在某时刻，对进程Pi进行资源分配后的有关资源数据
            }
            else cout<<"目前系统处于不安全状态，请返回继续操作!"<<endl<<endl;
        }
        else cout<<"请您按要求输入合法字符！"<<endl;     //防止出现非法字符的输入
    }
    return 0;
}

void Print()       //格式化输出显示，其中stew()函数表示控制字符输出间隔
{
    cout<<"**********************************************************************"<<endl;
    cout<<setw(18)<<"Max"<<setw(18)<<"Allocation"<<setw(12)<<"Need"<<setw(18)<<"Available"<<endl<<"Process";
    for(int i=0;i<4;i++)
        cout<<setw(5)<<name[0]<<setw(5)<<name[1]<<setw(5)<<name[2];
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<setw(4)<<i<<setw(3)<<" ";
        for(int j=0;j<m;j++)  cout<<setw(5)<<Max[i][j];
        for(int j=0;j<m;j++)  cout<<setw(5)<<Allocation[i][j];
        for(int j=0;j<m;j++)  cout<<setw(5)<<Need[i][j];
        if(i==0)     //当前系统的可用资源只在第一行输出显示
            for(int j=0;j<m;j++)  cout<<setw(5)<<Available[j];
        cout<<endl;
    }
    cout<<endl<<"**********************************************************************"<<endl<<endl;
}

bool Check_Need_Work(int pi)   //检查进程pi的需求向量是否都不大于工作向量
{
    for(int i=0;i<m;i++)
        if(Need[pi][i] > Work[i])  return false;
    return true;
}

bool Check()   //利用安全性算法对资源分配情况进行分析，检查此时系统是否安全
{
    int t_Available[N] = {0};         //临时数组，防止在利用安全性算法检测时修改原可用资源向量
    for(int i=0;i<m;i++)  Work[i] = Available[i],t_Available[i] = Available[i];
    memset(Finish,0,sizeof(Finish));  //每次在调用安全性算法检测时，先初始化Finish数组和安全序列向量
    memset(temp,0,sizeof(temp));
    int t = 0;
    for(int cnt=0;cnt<n;cnt++)        //遍历
    {
        for(int i=0;i<n;i++)
        {
            if(!Finish[i] && Check_Need_Work(i))   //满足条件，开始分配
            {
                for(int j=0;j<m;j++)
                {
                    Work[j] += Allocation[i][j];
                    t_Available[j] = Work[j];
                }
                Finish[i] = 1;   //修改标志位
                temp[t++] = i;   //加入安全序列
                break;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(!Finish[i])       //如果仍有进程存在资源不足的情况，即Finish向量仍为false
        {
            return false;
        }
    }
    cout<<"目前该系统处于安全状态！"<<endl;
    cout<<"安全序列号为：";
    for(int i=0;i<n;i++)
    {
        cout<<temp[i]<<" ";
    }
    cout<<endl<<endl;
    return true;
}

bool Check_Need_Available_Requesti()    //检查进程pi的需求向量是否都不大于需求向量和可利用资源向量
{
    for(int i=0;i<m;i++)
    {
        if(Requesti[i] > Need[Pi][i])   //判断是否满足所有请求资源都不大于当前进程所需资源数目
        {
            cout<<"请求资源大于该进程所需要的资源!"<<endl<<endl;
            return false;
        }
        if(Requesti[i] > Available[i])  //判断当前资源请求是否都不大于当前的可用资源
        {
            cout<<"可用资源不足，无法满足请求!"<<endl<<endl;
            return false;
        }
    }
    return true;
}

bool Banker()  //进程Pi发出请求向量Requesti后，系统按银行家算法进行检查
{
    if(!Check_Need_Available_Requesti()) return false;    //有一个条件不满足，结束此次分配；如果前两个条件都满足，则尝试分配资源
    int num = 0;                //计数器清零
    for(int j=0;j<m;j++)
    {
        Available[j] -= Requesti[j];                      //尝试分配时，可利用资源向量减去请求向量
        Allocation[Pi][j] += Requesti[j];                 //已分配矩阵对应进程的向量加上请求向量
        Need[Pi][j] -= Requesti[j];                       //需求矩阵对应进程的向量减去请求向量
        if(Need[Pi][j] == 0)    //记录在尝试分配后需求向量是否全部为0，如果为0，则表明该进程可以将资源全部释放
            num++;
    }
    if(!Check())                //若系统不安全，恢复原状态，将尝试分配的资源进行释放
    {
		cout<<"虽满足尝试分配的条件，但分配后系统将处于不安全状态，故已将尝试分配的资源释放！"<<endl;
        for(int j=0;j<m;j++)
        {
            Available[j] += Requesti[j];                  //可利用资源向量加上请求向量 = 分配前的可利用资源向量
            Allocation[Pi][j] -= Requesti[j];             //已分配矩阵行向量减去请求向量 = 分配前的已分配矩阵
            Need[Pi][j] += Requesti[j];                   //需求矩阵行向量加上请求向量 = 分配前的需求矩阵
        }
        return false;
    }
    if(num == m)     //已满足进程对资源的所有需求，need向量每一项已变为0，此时可以将资源完全释放，进入下一个请求
    {
        for(int j=0;j<m;j++)
        {
            Available[j] += Allocation[Pi][j]; //可利用资源向量加上当前进程即将释放的所有资源数目对应的向量
            Allocation[Pi][j] = 0;             //将分配的资源释放
        }
    }
    return true;
}

/**
Max & Allocation：
7 5 3 
3 2 2 
9 0 2 
2 2 2 
4 3 3 
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
**/

注：各位旁友们自行找到测试样例进行下测试噢~

————
The End

那写看似毫无波澜的日复一日，会在某一天 让你突然发现努力的意义。 “小忙”加油！
无悔昨天 & 感谢今天 & 喜欢明天~