银行家算法

死锁：

死锁产生的现场：当A进程P S2信号量而B进程P S1信号量时就会产生死锁，由于S2信号量须要B进程释放，而S1信号量须要A进程释放，因此两个进程都在等相互的资源，造成死锁。

 死锁产生的条件：

相互排斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。（信号量s1 s2为相互排斥的信号量，仅仅能被一个进程占用）

请求和保持条件：当进程因请求资源而堵塞时，对已获得的资源保持不放。（A进程在获取s2堵塞时，一直占用s1）

不可剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，仅仅能在使用完时由自己释放。（s1仅仅能由A进程释放，s2仅仅能由B进程释放）

环路等待条件：在发生死锁时，必定存在一个进程--资源的环形链。（A B 进程都是环形链路）

避免死锁的算法：

银行家算法是避免死锁的一种重要方法，防止死锁的机构仅仅能确保上述四个条件之中的一个不出现，则系统就不会发生死锁。通过这个算法能够用来解决生活中的实际问题，如银行贷款等。

程序实现思路银行家算法顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其能否限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其它进程使用资源。假设资源分配不得到就会发生进程循环等待资源，则进程都无法继续运行下去的死锁现象。
把一个进程须要和已占有资源的情况记录在进程控制中，假定进程控制块PCB当中“状态”有就绪态、等待态和完毕态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个运行过程中总共要申请的资源量。显然，，每一个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配能够避免死锁.
 
一．程序流程图：
1.初始化算法流程图：

2．银行家算法流程图：

 3.安全性算法流程图：

二．银行家算法设计:
1．设进程i提出请求Request[n]，则银行家算法按例如以下规则进行推断。
(1)假设Request[n]>Need[i，n]，则报错返回。
(2)假设Request[n]>Available，则进程i进入等待资源状态，返回。
(3)如果进程i的申请已获批准，于是改动系统状态：
    Available=Available-Request
    Allocation=Allocation+Request
    Need=Need-Request
(4)系统运行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
2．安全性检查
(1)设置两个工作向量Work=Available；Finish =False
(2)从进程集合中找到一个满足下述条件的进程，
   Finish =False
   Need<=Work
   如找到，运行(3)；否则，运行(4)
(3)设进程获得资源，可顺利运行，直至完毕，从而释放资源。
    Work=Work+Allocation
    Finish=True
    GO TO 2
(4)如全部的进程Finish =true，则表示安全；否则系统不安全。
3．数据结构
如果有M个进程N类资源，则有例如以下数据结构:
#define W 10
#define R 20
int A ;                      //总进程数
int B ;                     //资源种类
int ALL_RESOURCE[W];        //各种资源的数目总和
int MAX[W] ;             //M个进程对N类资源最大资源需求量
int AVAILABLE ;          //系统可用资源数
int ALLOCATION[W] ;      //M个进程已经得到N类资源的资源量
int NEED[W] ;            //M个进程还须要N类资源的资源量
int Request ;            //请求资源个数
5.4主要函数说明
void showdata();           //主要用来输出资源分配情况
void changdata(int);       //主要用来输出资源分配后后的情况
void rstordata(int);       //用来恢复资源分配情况,如:银行家算法时,因为分配不安全则要恢复资源分配情况
int chkerr(int);           //银行家分配算法的安全检查
void bank()   ;             //银行家算法
银行家算法的课程设计（二)VC++6.02008-01-28 15:29源程序
数据结构分析：
如果有M个进程N类资源，则有例如以下数据结构:
#define W 10
#define R 20
int A ;                      //总进程数
int B ;                     //资源种类
int ALL_RESOURCE[W];        //各种资源的数目总和
int MAX[W] ;             //M个进程对N类资源最大资源需求量
int AVAILABLE ;          //系统可用资源数
int ALLOCATION[W] ;      //M个进程已经得到N类资源的资源量
int NEED[W] ;            //M个进程还须要N类资源的资源量
int Request ;            //请求资源个数
第3章   程序清单#include <iostream>
using namespace std;
#define MAXPROCESS 50                        /*最大进程数*/
#define MAXRESOURCE 100                        /*最大资源数*/
int AVAILABLE[MAXRESOURCE];                    /*可用资源数组*/
int MAX[MAXPROCESS][MAXRESOURCE];            /*最大需求矩阵*/
int ALLOCATION[MAXPROCESS][MAXRESOURCE];    /*分配矩阵*/
int NEED[MAXPROCESS][MAXRESOURCE];            /*需求矩阵*/
int REQUEST[MAXPROCESS][MAXRESOURCE];        /*进程须要资源数*/
bool FINISH[MAXPROCESS];                        /*系统是否有足够的资源分配*/
int p[MAXPROCESS];                             /*记录序列*/
int m,n;                                    /*m个进程,n个资源*/
void Init();
bool Safe();
void Bank();
int main()
{
    Init();
    Safe();
    Bank();
}
void Init()                /*初始化算法*/
{
    int i,j;
    cout<<"\t---------------------------------------------------"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t||                 银行家算法                    ||"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t||                             计科04151  李宏   ||"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t||                                  0415084211   ||"<<endl;
    cout<<"\t---------------------------------------------------"<<endl;
    cout<<"请输入进程的数目:";
    cin>>m;
    cout<<"请输入资源的种类:";
    cin>>n;
    cout<<"请输入每一个进程最多所需的各资源数,依照"<<m<<"x"<<n<<"矩阵输入"<<endl;
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
    cin>>MAX[j];
    cout<<"请输入每一个进程已分配的各资源数,也依照"<<m<<"x"<<n<<"矩阵输入"<<endl;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>ALLOCATION[j];
            NEED[j]=MAX[j]-ALLOCATION[j];
            if(NEED[j]<0)
            {
                cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请又一次输入:"<<endl;
                j--;
                continue;
            }
        }
    }
    cout<<"请输入各个资源现有的数目:"<<endl;
    for(i=0;i<n;i++)
    {
        cin>>AVAILABLE;
    }
}
void Bank()                /*银行家算法*/
{
    int i,cusneed;
    char again;
    while(1)
    {
        cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;
        cin>>cusneed;
        cout<<"请输入进程所请求的各资源的数量"<<endl;
        for(i=0;i<n;i++)
        {
            cin>>REQUEST[cusneed];
        }
        for(i=0;i<n;i++)
        {
            if(REQUEST[cusneed]>NEED[cusneed])
            {
                cout<<"您输入的请求数超过进程的需求量!请又一次输入!"<<endl;
                continue;
            }
            if(REQUEST[cusneed]>AVAILABLE)
            {
                cout<<"您输入的请求数超过系统有的资源数!请又一次输入!"<<endl;
                continue;
            }
        }
        for(i=0;i<n;i++)
        {
            AVAILABLE-=REQUEST[cusneed];
            ALLOCATION[cusneed]+=REQUEST[cusneed];
            NEED[cusneed]-=REQUEST[cusneed];
        }
        if(Safe())
        {
            cout<<"允许分配请求!"<<endl;
        }
        else
        {
            cout<<"您的请求被拒绝!"<<endl;
            for(i=0;i<n;i++)
            {
                AVAILABLE+=REQUEST[cusneed];
                ALLOCATION[cusneed]-=REQUEST[cusneed];
                NEED[cusneed]+=REQUEST[cusneed];
            }
        }
        for(i=0;i<m;i++)
        {
            FINISH=false;
        }
        cout<<"您还想再次请求分配吗?是请按y/Y,否请按其他键"<<endl;
        cin>>again;
        if(again==‘y‘||again==‘Y‘)
        {
            continue;
        }
        break;
        }
}
bool Safe()                                    /*安全性算法*/
{
    int i,j,k,l=0;
    int Work[MAXRESOURCE];                    /*工作数组*/
    for(i=0;i<n;i++)
    Work=AVAILABLE;
    for(i=0;i<m;i++)
    {
        FINISH=false;
    }
    for(i=0;i<m;i++)
    {    
        if(FINISH==true)
        {
            continue;
        }
        else
        {
            for(j=0;j<n;j++)
            {
                if(NEED[j]>Work[j])
                {
                    break;
                }
            }
            if(j==n)
            { 
                FINISH=true;
                for(k=0;k<n;k++)
                {
                    Work[k]+=ALLOCATION[k];
                }
                p[l++]=i;
                i=-1;
            }
            else
            {
                continue; 
            }
        }
        if(l==m)
        {
            cout<<"系统是安全的"<<endl;
            cout<<"安全序列:"<<endl;
            for(i=0;i<l;i++)
            {
                cout<<p;
                if(i!=l-1)
                {
                    cout<<"-->";
                }
            }
            cout<<""<<endl;
            return true;
        }
    }
    cout<<"系统是不安全的"<<endl;
    return false;
} 
输出数据

银行家算法的模拟实现”是本学期操作系统课程唯一的课程设计。在设计此程序的过程中，我遇到过很多问题，也学到了非常多东西。本程序的设计实现主要是用C++语言实现，通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决，在C++学习上也有了非常大的进步。程序设计过程中開始遇到的最大的问题是算法的结构设计问题，课本上仅仅给了设计要求及简单的算法，要真正实现还须要考虑非常多方面。在算法的数据结构设计上考虑了非常长时间。在程序设计中先后參考了非常多网络资料，也參考了一些别人写的的程序，综合这些算法思想和自己的思路对程序做了非常好的设计方式，对一些算法的优越性等也作了一些考虑。此外考虑最多的就是异常错误处理的设计。一个好的程序必须能在各种环境下都有其对应的处理方式，至少能应对一些常见的可能发生的错误。比方一般的要求输入为数字时，假设输入了一个非数字字符，程序就会马上出错无法继续执行，本程序针对这个问题设计了一个shuzi();函数进行处理，处理方式为：接受键盘输入的字符为字符串，然后对字符串的每一个字符进行推断是否为数字，假设有非数字字符出现则提示出错并要求又一次输入。又如在推断是否继续时要求输入Y/N时，按一般的方式，假设输入为多个字符，则多余的字符会保存在缓冲区，到下次要求输入时输入而导致出错，对此问题设计处理方式为接受输入字符保存为串然后仅仅取其首字符进行推断。还有非常多类似的错误处理。还有在设置程序的显示优化时，发现暂停函数在不同的情况下执行顺序不同，如此等等。在课程设计过程中遇到了很多问题，也向同宿舍的同学做了一些请教一起讨论，也因此从他们身上学到了很多东西。