其他算法 - [转]银行家算法 - 《技术博客》

一、银行家算法
二、代码实现
一、银行家算法

功能：避免死锁
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
二、代码实现

#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 定义全局变量 */
const int    x = 50, y = 50;                                 /* x为进程个数 y为资源种类数 */
int        Available[y];                                   /* 各资源可利用的数量 */
int        Allocation[x][y];                               /* 各进程当前已分配的资源数量 */
int        Max[x][y];                                      /* 各进程对各类资源的最大需求数 */
int        Need[x][y];                                     /* 尚需多少资源 */
int        Request[y];                                     /* 申请多少资源 */
int        Work[y];                                        /* 工作向量，表示系统可提供给进程继续运行所需的各类资源数量 */
int        Finish[x];                                      /* 表示系统是否有足够的资源分配给进程，1为是 */
int        p[x];                                           /* 存储安全序列 */
int        i, j;                                           /* i表示进程，j表示资源 */
int        n, m;                                           /* n为进程i的数量,m为资源j种类数 */
int        l    = 0;                                    /* l用来记录有几个进程是Finish[i]=1的，当l=n是说明系统状态是安全的 */
int        counter = 0;                                    /* 记数器,记录可执行的进程数 */
/* 函数声明 */
void chushihua();                                               /* 初始化函数 */
void safe();                                                    /* 安全性算法 */
void show();                                                    /* 函数show,输出当前状态 */
void bank();                                                    /* 银行家算法 */
void jieshu();                                                  /* 结束函数 */
void chushihua()
{
    cout << "输入进程的数量: ";                                    /* 从此开始输入有关数据 */
    cin >> n;
    cout << "输入资源种类数: ";
    cin >> m;
    cout << endl << "输入各种资源当前可用的数量( " << m << " 种): " << endl;
    for ( j = 0; j < m; j++ )                               /* m为资源数 */
    {
        cout << "输入资源 " << j << " 可利用的数量Available[" << j << "]: ";
        cin >> Available[j];                            /* 输入数字的过程 */
        Work[j] = Available[j];                         /* 初始化Work[j]，它的初始值就是当前可用的资源数 */
    }
    cout << endl << "输入各进程当前已分配的资源数量Allocation[" << n << "][" << m << "]: " << endl;
    for ( i = 0; i < n; i++ )                               /* n为进程数 */
    {
        for ( j = 0; j < m; j++ )                       /* m为资源数 */
        {
            cout << " 输入进程 " << i << " 当前已分配的资源 " << j << " 数量: ";
            cin >> Allocation[i][j];
        }
        cout << endl;
        Finish[i] = 0;                                  /* 初始化Finish[i] */
    }
    cout << endl << "输入各进程对各类资源的最大需求Max[" << n << "][" << m << "]: " << endl;
    for ( i = 0; i < n; i++ )                               /* n为进程数 */
    {
        for ( j = 0; j < m; j++ )                       /* m为资源数 */
        {
            cout << " 输入进程 " << i << " 对资源 " << j << " 的最大需求数: ";
            cin >> Max[i][j];
            if ( Max[i][j] >= Allocation[i][j] )    /* 若最大需求大于已分配，则计算需求量 */
                Need[i][j] = Max[i][j] - Allocation[i][j];
            else
                Need[i][j] = 0;                 /* Max小于已分配的时候，此类资源已足够不需再申请 */
        }
        cout << endl;
    }
    cout << endl << "初始化完成" << endl;
}
/* 安全性算法函数 */
void safe()
{
    l = 0;                                                                  /* l用来记录有几个进程是Finish[i]=1的，当l=n是说明系统状态是安全的 */
    for ( i = 0; i < n; i++ )                                               /* n为进程数 */
    {
        if ( Finish[i] == 0 )
        {                                                               /* 逐个查找Finish[i]==0的进程 条件一 */
            counter = 0;                                            /* 记数器,记录有多少个进程已经执行 */
            for ( j = 0; j < m; j++ )                               /* m为资源数 */
            {
                if ( Work[j] >= Need[i][j] )
                    counter = counter + 1;                  /* 可用大于需求，记数，该进程可以执行 */
            }
            if ( counter == m )                                     /* i进程的每类资源都符合Work[j]>=Need[i][j] 条件二 */
            {
                p[l]        = i;                            /* 存储安全序列 */
                Finish[i]    = 1;                            /* i进程标志为可分配 */
                for ( j = 0; j < m; j++ )
                    Work[j] = Work[j] + Allocation[i][j];   /* 释放资源 */
                l    = l + 1;                                /* 记数,现在有l个进程是安全的，当l=n时说明满足安全序列 */
                i    = -1;                                   /* 从第一个进程开始继续寻找满足条件一二的进程 */
            }
        }
    }
}
/* 显示当前状态函数 */
void show()                                     /* 函数show,输出当前资源分配情况 */
{
    int    i, j;                           /* 局部变量，i表示进程，j表示资源 */
    int    All[y];                         /* 各种资源的总数量 */
    int    L1;                             /* 局部变量L1 */
    cout << "当前的状态为：" << endl;
    cout << "各种资源的总数量:" << endl;
    for ( j = 0; j < m; j++ )               /* m为资源数 */
    {
        cout << " 资源" << j << ": ";
        All[j] = Available[j];          /* 总数量=可用的+已分配的 */
        for ( i = 0; i < n; i++ )       /* n为进程数 */
            All[j] += Allocation[i][j];
        cout << All[j] << " ";
    }
    cout << endl << "当前各种资源可用的量为(available):" << endl;
    for ( j = 0; j < m; j++ )               /* m为资源数 */
        cout << " 资源" << j << ": " << Available[j] << " ";
    cout << endl << "各进程所需的最大资源量(Max): " << endl;
    for ( i = 0; i < m; i++ )               /* m为资源数 */
    {
        cout << " 资源" << i << " ";
    }
    cout << endl;
    for ( L1 = 0; L1 < n; L1++ )            /* n为进程数 */
    {
        cout << "进程" << L1 << ": ";
        for ( j = 0; j < m; j++ )
            cout << Max[L1][j] << " ";
        cout << endl;
    }
    cout << endl << "各进程已经得到的资源量(allocation): " << endl;
    for ( i = 0; i < m; i++ )       /* m为资源数 */
    {
        cout << " 资源" << i << " ";
    }
    cout << endl;
    for ( L1 = 0; L1 < n; L1++ )    /* n为进程数 */
    {
        cout << "进程" << L1 << ": ";
        for ( j = 0; j < m; j++ )
            cout << Allocation[L1][j] << " ";
        cout << endl;
    }
    cout << endl << "各进程还需要的资源量(need):" << endl;
    for ( i = 0; i < m; i++ ) /* m为资源数 */
    {
        cout << " 资源" << i << " ";
    }
    cout << endl;
    for ( L1 = 0; L1 < n; L1++ )
    {
        cout << "进程" << L1 << ": ";
        for ( j = 0; j < m; j++ )
            cout << Need[L1][j] << " ";
        cout << endl;
    }
}
/* 银行家算法函数 */
void bank()
{
    cout << endl << "进程申请分配资源：" << endl;
    int    k    = 0;                                                            /* 用于输入进程编号 */
    bool    r    = false;                                                        /* 初值为假，输入Y继续申请则置为真 */
    do                                                                              /* 输入请求 */
    {
        cout << "输入申请资源的进程(0-" << n - 1 << "): ";
        cin >> k;                                                               /* 进程编号 */
        cout << endl;
        while ( k > n - 1 )                                                     /* 输入错误处理 */
        {
            cout << endl << "无该进程号，重新输入：" << endl;
            cout << endl << "输入申请资源的进程(0--" << n - 1 << "): ";
            cin >> k;                                                       /* 进程编号 */
            cout << endl;
        }
        cout << endl << "输入该进程申请各类资源的数量: " << endl;
        for ( j = 0; j < m; j++ )                                               /* m为资源数 */
        {
            do                                                              /* do……while 循环判断申请输入的情况 */
            {
                cout << "进程 " << k << " 申请资源[" << j << "]的数量:";
                cin >> Request[j];                                      /* 输入请求进程数 */
                cout << endl;
                if ( Request[j] > Need[k][j] )                          /* 申请大于需求量时出错，提示重新输入 cout<<"申请量大于需要量!"<<endl; */
                {
                    cout << "申请的资源" << j << "的数量为" << Request[j] << ",大于进程" << k << "对该资源需求量" << Need[k][j] << "。" << endl;
                    cout << "重新输入!" << endl;
                }
/* 先判断是否申请大于需求量，再判断是否申请大于可利用量 */
                else if ( Request[j] > Available[j] )                   /* 申请大于可利用量， 应该阻塞等待 */
                {
                    cout << "\n没有那么多资源，目前可利用资源" << j << "数量为" << Available[j] << ",本次申请不成功，进程等待!" << endl;
                    Finish[k] = 0;                                  /* 该进程等待 */
                    goto error;                                     /* goto语句跳转，结束本次申请 */
                }
            }
            while ( Request[j] > Need[k][j] );                              /* Request[j]>Available[j] */
        }
/* 改变Available、Allocation、Need的值 */
        for ( j = 0; j < m; j++ )                                               /* m为资源数 */
        {
            Available[j]        = Available[j] - Request[j];            /* 可用的资源数=可用的资源数-请求分配的资源数 */
            Allocation[k][j]    = Allocation[k][j] + Request[j];        /* 已分配的资源数=已分配的资源数+请求的资源数 */
            Need[k][j]        = Need[k][j] - Request[j];              /* 还需要的资源数=还需要的资源数-请求的资源数 */
            Work[j]            = Available[j];
        }
        safe();                                                                 /* 调用安全性算法函数，判断当前状态的安全性 */
        if ( l < n )                                                            /* l用来记录有几个进程是Finish[i]=1的，当l=n是说明系统状态是安全的 */
        {
            l = 0;
            cout << "\n试分配后,状态不安全,所以不予分配!恢复原状态" << endl;
/* 恢复数据 */
            for ( j = 0; j < m; j++ )                                       /* m为资源数 */
            {
                Available[j]        = Available[j] + Request[j];
                Allocation[k][j]    = Allocation[k][j] - Request[j];
                Need[k][j]        = Need[k][j] + Request[j];
                Work[j]            = Available[j];
            }
            for ( i = 0; i < n; i++ )                                       /* n为进程数 */
                Finish[i] = 0;                                          /* 进程均置为未分配状态 */
        }else  { /* l=n，即所有的Finish[i]=1,每一个进程均能执行 */
            l = 0;                                                          /* 判断标志 */
            cout << "\n申请资源成功!!!" << endl;
            for ( j = 0; j < m; j++ )                                       /* m为资源数 */
            {
                if ( Need[k][j] == 0 )
                    ;
                else {                                                  /*有一种资源还没全部申请到，则该进程不可执行，不能释放拥有的资源 */
                    l = 1;                                          /* 置l为1，作为判断标志 */
                    break;
                }
            }
            if ( l != 1 )                                                   /* 进程可以执行，则释放该进程的所有资源 */
            {
                for ( j = 0; j < m; j++ )                               /* m为资源数 */
                {
                    Available[j]        = Available[j] + Allocation[k][j];
                    Allocation[k][j]    = 0;
                }
                cout << "该进程已得到所有需求资源，执行后将释放其所有拥有资源！" << endl;
            }
            l = 0;                                                          /* 归零 */
            cout << "\n安全的状态!" << endl;
            cout << "安全序列为: ";
            cout << endl << "进程" << "(" << p[0] << ")";                     /* 输出安全序列，考虑显示格式，先输出第一个 */
            Finish[0] = 0;
            for ( i = 1; i < n; i++ )
            {
                cout << "==>>" << "进程" << "(" << p[i] << ")";
                Finish[i] = 0;                                          /* 所有进程置为未分配状态 */
            }
            cout << endl << endl;
        }
        show();                                                                 /* 显示当前状态 */
error:                                                                                  /* 申请大于可利用量， 应该阻塞等待,结束本次资源申请，GOTO 语句跳转至此 */
        cout << endl << "是否继续申请资源(y/n)或（Y/N）?";
        char* b = new char;                                                     /* 输入y/n，判断是否继续申请 <<endl */
        cin >> b;
        cout << endl;
        cout << "-------------------------------------------" << endl << endl;
        cout << endl;
        if ( *b == 'y' || *b == 'Y' )
            r = true;                                                       /* 继续申请 */
        else{
            r = false;                                                      /*不继续申请 */
            jieshu();                                                       /* 调用结束函数 */
        }
    }
    while ( r == true );
}
/* 结束函数 */
void jieshu()
{
    cout << endl << endl;
    cout << "\t\t 演示计算完毕" << endl;
    cout << endl << endl;
}
/* 主函数 */
int main()
{
    cout << endl << endl << "\t\t\t\t模拟银行家算法" << endl << endl;
    chushihua();                                    /* 初始化函数调用 */
    cout << endl;
    show();                                         /* 输出当前状态 */
    safe();                                         /* 判断当前状态的安全性 */
    if ( l < n )                                    /* l在safe中是用来记录安全的进程的个数的 */
    {
        cout << "\n当前状态不安全，拒绝申请！" << endl;
        cout << endl;
        return(0);
    }else  {
        int i;                                  /* 局部变量 */
        l = 0;
        cout << endl << "\n当前的状态是安全的!安全序列为:" << endl;
        cout << "进程" << "(" << p[0] << ")";     /* 输出安全序列 */
        for ( i = 1; i < n; i++ )
            cout << "->>" << "进程" << "(" << p[i] << ")";
        for ( i = 0; i < n; i++ )
            Finish[i] = 0;                  /* 所有进程置为未分配状态 */
        cout << endl;
    }
    bank();                                         /* 调用银行家算法函数 */
    cout << "\t\t 演示计算完毕" << endl;
    return(0);
}