银行家算法的模拟实现实验报告

一、实验题目：

模拟实现银行家算法的处理过程

二、实验目的：

银行家算法是避免死锁的代表性算法。本实习旨在加深了解有关资源申请、避免死锁、状态安全性等概念.并体会和运用避免死锁的具体实施方法。然后依照本实习.自行设计模拟程序。

三、实验原理：

1. 我们可以把操作系统看作是银行家.操作系统管理的资源相当于银行家管理的资金.进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。

当进程首次申请资源时.要测试该进程对资源的最大需求量.如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源.否则就推迟分配。当进程在执行中继续申请资源时.先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源.若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量.若能满足则按当前的申请量分配资源.否则也要推迟分配。

2.  安全状态：如果存在一个由系统中所有进程构成的安全序列P1.….Pn.则系统处于安全状态。安全状态一定是没有死锁发生。       

不安全状态:不存在一个安全序列。不安全状态一定导致死锁。

安全序列：一个进程序列{P1.….Pn}是安全的.如果对于每一个进程Pi(1≤i≤n）.它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

3.  设requesti为进程p[i]的请求向量.如果requesti[j]=K.表示进程p[i]需要K个Rj资源。当系统发出请求后.系统按下述步骤开始检查：

 1）如果requesti[j]<=need[i][j],转向步骤2；否则报告出错.申请的资源已经大于它需要的最大值。

 2）如果requesti[j]<=available[j],转向步骤3；否则报告出错.尚无足够的资源。

 3）系统试探着把资源分配给p[i].并修改下列数据结构中的值：

       available[j]=available[j]-request[j]

       allocation[i][j]=allocation[i][j]+request[j]

           need[i][j]=need[i][j]-request[j]

 4）系统进行安全性算法.检查此次分配后.系统是否还处于安全状态.若安全.把资源分配给进程p[i]；否则.恢复原来的资源分配状态.让进程p[i]等待。

4.  安全性算法：

      int work[RESOURCE_NUMBER]；

      bool finish[PROCESS_NUMBER]；

   1) Work=Available;

     Finish=false;

   2) 寻找满足条件的i：

      A、Finish[i]=false;

      B、Need[i]≤Work;

     如果不存在.则转4)

   3) Work:=Work+Allocation[i]； Finish[i]:=true；转2)

   4) 若对所有i,Finish[i]=true,则系统处于安全状态.否则处于不安全状态   

四、数据结构：

   数组

五、程序代码：

#include

#include

#include

#include

using namespace std;

#define N 3   //进程数

#define M 3   //资源数

int Available[M];   //可用的资源数

int Need[N][M]={0};  //还需要的资源数

int Max[N][M];       //最大需求量

int Allocation[N][M] = {0};   //当前分配到的资源数

int Request[N][M]={0};        //请求的资源数

int n;

time_t t;

int isFinish[N] ={0};   //判断进程是否已经请求资源结束

int test1 = 0;

void Requester();  //进程随机请求资源数目

void Handle();    //处理该请求

bool Check();     //安全性算法检查

void show();      //打印出当前的进程资源状态

int Finish(int);   //进程是否已经完成.若完成返回1.否则为0

void main()

{

    int i;

    int j;

cout << "请输入各个资源的可用数目：";

for(i=0; i     cin >> Available[i];

cout << "请依次输入各个进程对各个资源的最大需求数目：" << endl;

for(i=0; i     for(j=0; j        {

         cin >> Max[i][j];

            Need[i][j] = Max[i][j] - Allocation[i][j];

        }

cout << "------------------------原始状态------------------------" << endl;

    show();

    int test = 0;

    int testP = 0;

    int testR = 0;

    do{

        Requester ();

        test++;

    }while(test != 10);

}

int Finish(int i)

{

    int test = 0;

    int w = i;

for(int j=0; j    {

        if(Need[w][j] == 0)   //对j资源的需求量已经为0

            test++;

    }

    if(test == M)            //如果对每个资源的需求量都已经为0

            isFinish[w] = 1;   //则将其设为1.代表已经完成

    return isFinish[w];

}

void Requester ()

{

    time_t t;

    int test = 0;

    srand((unsigned)time(&t)+rand());

    n = rand()%N;

for(int j=0; j    {

if(Need[n][j] <= Available[j])

            test++;

    }

for(j=0; j    {

        if(test==N )

        {

            Request[n][j] = Need[n][j];

        }

        else

        {

            srand((unsigned)time(&t)+rand()); 

            Request[n][j] = rand()%4;

        }

    }

    Handle();

}

void Handle()         //处理请求

{

    int test1 = 0;

    int test2 = 0;

for(int j=0; j     if(Request[n][j]<=Need[n][j])

        {

         if(Request[n][j] <= Available[j])

                test1++;

            else

            {

cout<< "目前没有足够的资源分配给你的进程" << n << "的请求";

             for(j=0; j cout << Request[n][j] << " ";

             cout << ".请等待！" << endl <            }

        }

        else

        {

         cout << "你的进程" << n << "所请求的资源";

for(j=0; j cout << Request[n][j] << " ";

         cout << "已经超过进程的需求数目！" <        }

        if(test1 == M)        //请求资源数目均小于可用资源数目

        {            

             cout << "处理你的进程" << n << "的请求";

for(j=0; j cout << Request[n][j] << " ";

              cout << endl ;

             for(j=0; j                {

                    Available[j] = Available[j]- Request[n][j];

                    Allocation[n][j] = Allocation[n][j]+Request[n][j];

                    Need[n][j] = Need[n][j]-Request[n][j];

                }

                if(Check()==true)  //安全性算法检查是安全的.则打印出来

                {

                    show();

                    if(Finish(n) == 1)   //如果此次分配后该进程已经结束.那么久释放其占用的资源数目

                    {

                     cout << "进程" << n << "已经结束.会释放资源" << endl;

                     for(j=0; j                        {

                           Available[j] = Available[j] + Allocation[n][j];

                           Allocation[n][j] = 0;

                           Need[n][j] = 0;

                        }

                        show();

                    }

                }

                else

                {

                 cout << "你的进程" << n << "所请求的资源";

for(j=0; j cout << Request[n][j] << " ";

             cout << "系统不安全！本次资源申请不成功！"<                 for(j=0; j                    {

                        Available[j] = Available[j] + Request[n][j];

                        Allocation[n][j] = Allocation[n][j] - Request[n][j];

                        Need[n][j] = Need[n][j] + Request[n][j];

                    }

                }

        }

}

bool Check()   //安全性算法检测

{

    int work[M] ={0};

    bool finish[N];

for(int j=0; j       work[j] = Available[j];

for(int i=0; i        finish[i] = false;

    int test = 0;

    bool flag;

    int k=0;

for(j=0; j    {

     if(Need[n][j] <= work[j])

            test++;

    }

    if(test == M)

        flag = true;

    else

        flag = false;

    test = 0;

for(i=0;i    {

     for(i=0;i        {

            if(finish[i] == false && flag == true)

            {

             for(j=0; j                    work[j] = work[j] + Allocation[n][j];

                finish[i] = true;

                test++;

            }

        }

    }

    if(test == N)

        return true;

    else

        return false;

}

void show()

{

cout << "---------------------------------------------------------" << endl;

cout << "资源请求" << "\" << "已分配资源" << "\" << "尚需资源"<<"\" << "剩余可用资源" < cout << "进程名称" << "\A B C " << "\A B C "<< "\ A B C "< for(int i=0; i    {

     cout << " P" << i << " \";

     for(int j=0; j         cout << Allocation[i][j] << " ";

     cout << "\";

     for(j=0; j         cout << Need[i][j] << " ";

        if( i==0 )

        {

         cout << "\ ";

         for(j=0; j             cout << Available[j] << " ";

        }

     cout << endl;

    }

cout << "--------------------------------------------------------" << endl <}

六、运行结果：

七、实验心得：

这次的实验模拟实现银行家算法虽然用程序算法实现了模拟进程请求资源以及根据安全性检测是否要分配资源的整个过程.自己考虑整个代码的框架过程中期初觉得思路清晰.应该比较简单.但是列出框架以及主要函数之后开始用代码实现的时候.发现了很多隐藏的细节的考虑.比较繁琐而且环环相扣.要真的实现并没有当初以为的那么简单.比如我现在目前的算法虽然模拟了大致的过程.并且也可以不断循环请求.但是在进程请求资源那一块的实现还是有缺陷.没能很好的优化.目前只是如果有足够的资源.就让随机产生的进程i申请最大需求量.如果无法满足.则随机产生随机资源数目进行申请。但是这个请求资源并不是很优化需要进一步改造.但是还是对银行家算法有了更深入更清楚的了解.以后的程序编写不论是实验还是项目开发.无论大小.都应该把程序的整体框架构建好.提高重用性.再进行一步步实现。