操作系统实训（银行家算法）

银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待。
目的在于加深催操作系统基础理论和基本知识的理解，加强学生的动手能力。银行家算法是避免死锁的一种重要方法，通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。
1、程序运行截图







2、算法大体介绍
1、算法思路:先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。
2、银行家算法:在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前, 判断系统是否是安全的; 若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求Request [i] ，则银行家算法按如下规则进行判断。
(1) 如果Request [cusneed] [i]<= Need[cusneed][i]，则转(2)；否则，出错。
(2) 如果Request [cusneed] [i]<= Available[cusneed][i]，则转(3)；否则，出错。
(3) 系统试探分配资源，修改相关数据：
Available[i]-=Request[cusneed][i];
Allocation[cusneed][i]+=Request[cusneed][i];
Need[cusneed][i]-=Request[cusneed][i];
(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢 复原状,进程等待。
3、安全性检查算法
(1) 设置两个工作向量Work=Available;finish
(2) 从进程集合中找到一个满足下述条件的进程，finish==false；
Need<=Work；如找到，执行(3)；否则，执行(4)。
(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work+=ALLOCATION；
finish=true；
GOTO 2。
(4) 如所有的进程finish= true，则表示安全；否则系统不安全。
操作系统安全状态和不安全状态：
安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不存在一个安全序列。不安全状态不一定导致死锁。

3、具体代码如下（想要报告的可以评论区留言即可）：

#include<iostream>
#include<bits/stdc++.h>
#include<string>
#include <Windows.h>
using namespace std;
int n,m;
int MAX[100][101];
int Need[1001][1101];
int Allocation[110][101];
int sum[1100];
int Available[1101];
int available[110];
int safe_list[1101];
int work[1101];
int request[101][101];
bool finish[1110];
int a[110][110];
int cnt,num;
FILE *fp;
void input()
{
    int i,j;
    cout<<"请输入进程的数目:";
    cin>>m;
    cout<<"请输入资源的种类:";
    cin>>n;
    cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩 阵输入"<<endl;
    for(i=1; i<=m; i++)
        for(j=1; j<=n; j++)
            cin>>MAX[i][j];
    cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩 阵输入"<<endl;
    for(i=1; i<=m; i++)
    {
        for(j=1; j<=n; j++)
        {
            cin>>Allocation[i][j];
        }
    }
    cout<<"请输入"<<n<<"个资源拥有的数目:"<<endl;
    for(i=1; i<=n; i++)
        cin>>available[i];
}
void Init()                /*初始化算法*/
{

    int i,j;
    for( i=1; i<=m; i++)
    {
        for( j=1; j<=n; j++)
        {
            Need[i][j]=MAX[i][j]-Allocation[i][j];
            if(Need[i][j]<0)
            {
                cout<<"您输入的第"<<i<<"个进程所拥有的第"<<j<<"个资源数 错误,请重新输入:"<<endl;
                j--;
                continue;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            sum[i]+=Allocation[j][i];
        }
    }
    for(i=1; i<=n; i++)
    {
        Available[i]=available[i]-sum[i];
    }
}
void showdata()   //显示
{
    fp=fopen("test.txt","w");
    int i;
    cout<<endl;
    cout<<"-------------------------------------------------------------"<<endl;
    fprintf(fp,"-------------------------------------------------------------\n");
    cout<<"各个进程的资源分配表:"<<endl;
    fprintf(fp,"各个进程的资源分配表:\n");
    for (i=1; i<=m+1; i++)
    {
        if(i==1)
        {
            cout<<"Process"<<"   "<<"Allocation"<<"       "<<"Max"<<"        "<<"Need"<<"        "<<"Available"<<endl;
            fprintf(fp,"Process   Allocation       Max        Need        Available\n");
        }
        else
        {
            cout<<"  p"<<i-1<<"      ";
            fprintf(fp,"  p%d        ",i-1);
            for(int j=1; j<=n; j++)
            {
                printf("%-2d ",Allocation[i-1][j]);
                fprintf(fp,"%-2d ",Allocation[i-1][j]);
            }
            cout<<"     ";
             fprintf(fp,"        ");
            for(int j=1; j<=n; j++)
            {
                printf("%-2d ",MAX[i-1][j]);
                fprintf(fp,"%-2d ",MAX[i-1][j]);
            }
            cout<<"     ";
            fprintf(fp,"       ");
            for(int j=1; j<=n; j++)
            {
                printf("%-2d ",Need[i-1][j]);
                fprintf(fp,"%-2d ",Need[i-1][j]);
            }
            cout<<"     ";
            fprintf(fp,"       ");
            if(i==2)
            {

                for(int j=1; j<=n; j++)
                {
                    printf("%-2d ",Available[j]);
                   fprintf(fp,"%-2d ",Available[j]);
                }
            }
            cout<<endl;
            fprintf(fp,"\n");
        }
    }
    fclose(fp);

}
bool isAll_0(int k)
{
    num=0;
    for(int i=1; i<=n; i++)
    {
        if(Need[k][i]==0)
            num++;
    }
    if(num==n)
    {
        return 1;
    }
    else return 0;
}
bool safe()
{
    fp=fopen("test.txt","a+");
    int finish_num=0;
    int index=0;
    int r=1;
    int temp=0;
    cnt=0;
    for(int i=1; i<=n; i++)
    {
        work[i]=Available[i];
    }
    for(int i=1; i<=m; i++)
    {
        bool result = isAll_0(i);
        if(result)
        {
            finish[i]=true;
            finish_num++;
        }
        else finish[i]=false;
    }
    while(finish_num!=m)
    {

        num=0;
        for(int i=1; i<=n; i++)
        {
            if(Need[r][i]<=work[i]&&finish[r]==false)
                num++;
        }
        if(num==n)
        {
            finish_num++;
            finish[r]=true;
            for(int k=1; k<=n; k++)
            {
                a[index][k]=work[k];
            }
            safe_list[index++]=r;
            for(int i=1; i<=n; i++)
                work[i]=Allocation[r][i]+work[i];
        }
        r++;
        if(r>m)
        {
            r=r%m;
            if(temp==finish_num)   //记录当前已经分配的进程数,如果全部都已经分配，就不需要跳到下一个进程
            {
                break;
            }
            temp=finish_num;
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(finish[i]==false)
        {
            cout<<endl<<"找不到安全序列，当前系统不安全！！！"<<endl;
            return false;
        }
    }
    cout<<endl<<"执行安全算法找安全序列，过程如下表："<<endl;
    fprintf(fp,"执行安全算法找安全序列，过程如下表：\n");
    cout<<"Process"<<"   "<<"work"<<"        "<<"Allocation"<<"       "<<"Need"<<"        "<<"work+Allocation"<<"          "<<"finish"<<endl;
     fprintf(fp,"Process   work        Allocation       Need        work+Allocation          finish\n");
    int j;
    for(int i=0; i<index; i++)
    {
        cout<<"  p"<<safe_list[i]<<"     ";
        fprintf(fp,"  p%d     ",safe_list[i]);
        for(j=1; j<=n; j++)
        {
            printf("%-2d ",a[i][j]);
             fprintf(fp,"%-2d  ",a[i][j]);
        }
        cout<<"     ";
         fprintf(fp,"      ");
        for(j=1; j<=n; j++)
        {
            printf("%-2d ",Allocation[safe_list[i]][j]);
            fprintf(fp,"%-2d ",Allocation[safe_list[i]][j]);
        }
        cout<<"      ";
         fprintf(fp,"       ");
        for(j=1; j<=n; j++)
        {
            printf("%-2d ",Need[safe_list[i]][j]);
            fprintf(fp,"%-2d ",Need[safe_list[i]][j]);
        }
        cout<<"       ";
         fprintf(fp,"        ");
        for(j=1; j<=n; j++)
        {
            printf("%-2d ",a[i][j]+Allocation[safe_list[i]][j]);
              fprintf(fp,"%-2d ",a[i][j]+Allocation[safe_list[i]][j]);
        }
        cout<<"              ";
        fprintf(fp,"                     ");
        if(finish[safe_list[i]]==1)
        {
            cout<<"true"<<endl;
             fprintf(fp,"true\n");
        }
        else cout<<"false"<<endl,fprintf(fp,"false\n");

    }

    cout<<"此时刻能找到一个安全序列，安全序列为：";
    fprintf(fp,"此时刻能找到一个安全序列，安全序列为：");
    for(int i=0; i<index; i++)
    {
        i==0?cout<<"P"<<safe_list[i]:cout<<"->"<<"p"<<safe_list[i];
        if(i==0)fprintf(fp,"p%d",safe_list[i]);
        else fprintf(fp,"->p%d",safe_list[i]);
    }
    cout<<endl;
    fprintf(fp,"\n");
    fclose(fp);
    return true;

}
int Request(int number)
{
    if(n==0)
    {
        cout<<"先初始化进程"<<endl;
        return 0;
    }

    cout<<"请输入请求的资源("<<n<<")个:";
    for(int i=1; i<=n; i++)
        cin>>request[number][i];
    int f=1;
    for(int i=1; i<=n; i++)
    {
        if(request[number][i]>Need[number][i])
        {
            f=0;
            break;
        }
    }
    if(f==0)
    {
        cout<<"进程"<<number<<"的request:";
        for(int i=1; i<=n; i++)
        {
            cout<<request[number][i]<<' ';
        }
        cout<<">"<<"Need:";
        for(int i=1; i<=n; i++)
        {
            cout<<Need[number][i]<<' ';
        }
        cout<<"申请资源失败"<<endl;
        return 0;
    }
    f=1;
    for(int i=1; i<=n; i++)
    {
        if(request[number][i]>Available[i])
        {
            f=0;
            break;
        }
    }
    if(f==0)
    {
        cout<<"进程"<<number<<"的request:";
        for(int i=1; i<=n; i++)
        {
            cout<<request[number][i]<<' ';
        }
        cout<<">"<<"Availble:";
        for(int i=1; i<=n; i++)
        {
            cout<<Available[i]<<' ';
        }
        cout<<"申请资源失败"<<endl;
        return 0;
    }
    return 1;
}
void setWindowStyle()//9e、06、8f
{
    system("title 银行家算法");
    system("color 9e");
}
void progressBar()
{
    string str;
    for(int j=0; j<1; j++)
    {
        if(j==0)
            str="\t\t初始化 ";
        for(int i=1; i<=20; i++)
        {
            system("cls");
            cout<<str<<endl;
            str=str+"■";
            cout<<"\t\t"<<5*i<<"%"<<endl;
            //Sleep(50);
            if(i<=10)
            {
                Sleep(50);
            }
            else Sleep(40);
        }
        cout<<"\t\t初始化完成！！"<<endl;
    }
}
void re_update(int number)
{
    for(int i=1; i<=n; i++)
    {
        Allocation[number][i]=Allocation[number][i]-request[number][i];
        Need[number][i]+=request[number][i];
        Available[i]+=request[number][i];
    }
}
void update(int number)
{
    for(int i=1; i<=n; i++)
    {
        Allocation[number][i]=Allocation[number][i]+request[number][i];
        Need[number][i]-=request[number][i];
        Available[i]-=request[number][i];
    }
}
void fenpei()
{
    int number;
    cout<<"请输入要操作的进程号:";
    cin>>number;
    if(Request(number))
    {
        update(number);
        showdata();
        if(safe()==false)
        {
            cout<<"请重新请求资源"<<endl;;
            re_update(number);
        }
    }

}
void show()
{
    printf("\t\t################ 银行家算法模拟程序 ################\t\t\n");
    printf("\t\t#                                                  #\n");
    printf("\t\t#                  开发者：******                  #\n");
    printf("\t\t#                                                  #\n");
    printf("\t\t####################################################\t\t\n");
    printf("\t\t\t\t  回车进入系统\t\t\t");
    getchar();
    fflush(stdin);
}

int main()
{
    show();
    setWindowStyle();
    progressBar();
    cout<<"***********银行家算法*************"<<endl;
    while(1)
    {
        cout<<"请选择操作："<<endl;
        cout<<"         1:初始化资源"<<endl;
        cout<<"         2:请求资源（银行家算法）"<<endl;
        cout<<"         3:执行安全算法"<<endl;
        cout<<"         4:关闭"<<endl;
        int x;
        cin>>x;
        switch(x)
        {
        case 1:
            input();
            Init();
            cout<<"初始化完毕"<<endl;
            break;
        case 2:
             fenpei();
            break;
        case 3:
            showdata();
            safe();
            break;
        case 4:
            return 0;
        }
    }


    /*测试例子
    5 3

    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

    10 5 7




    */
}