银行家算法

利用银行家算法避免死锁

1. 银行家算法中的数据结构

(1) 可利用资源向量Available。

这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

(2) 最大需求矩阵Max。

这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3) 分配矩阵Allocation。

这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。?

(4) 需求矩阵Need。

这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

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

2. 银行家算法

设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果Requesti[j]≤Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j] := Available[j]-Requesti[j];

Allocation[i,j] := Allocation[i,j]+Requesti[j];

Need[i,j] := Need[i,j]-Requesti[j];

(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3. 安全性算法

(1) 设置两个向量：

① 工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work := Available;

② Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i] := false; 当有足够资源分配给进程时，再令Finish[i] := true。

(2) 从进程集合中找到一个能满足下述条件的进程：

① Finish[i]=false;

② Need[i,j]≤Work[j]；

若找到，执行步骤(3)，否则，执行步骤(4)。

(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j] := Work[j]+Allocation[i,j];?

Finish[i] := true;?

go to step 2;

(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

总结：银行家算法分为两部分：

第一部分：是资源预分配算法，即对某进程的一个资源请求，先进行模拟分配，然后运行银行家算法的第二部分，找出是否存在安全序列。

第二部分：是安全性算法，找出当前系统状态是否有安全序列。

#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

int Available[10];        //可使用资源向量
int Max[10][10];        //最大需求矩阵
int Allocation[10][10] = { 0 };    //分配矩阵
int Need[10][10] = { 0 };    //需求矩阵

int Work[10];            //工作向量
int Finish[10];            //状态标志
int Request[10][10];        //进程申请资源向量
int Pause[10];

int i, j;
int n;                //系统资源总数
int m;                //总的进程数
int a;                //当前申请的进程号
int l, e;            //计数器
int b = 0, c = 0, f = 0, g;    //计数器

void mainenter()        //主要的输入部分代码
{
    printf("请输入系统总共有的资源数：");
    scanf("%d", &n);
    printf("请输入总共有多少个进程：");
    scanf("%d", &m);
    for (i = 1; i <= n; i++) {
        printf("第%d类资源有的资源实例：", i);
        scanf("%d", &Available[i]);
    }
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            printf("进程P[%d]对第%d类资源的最大需求量：", i, j);
            scanf("%d", &Max[i][j]);
            Need[i][j] = Max[i][j];
        }
    }
}

void mainrequest()        //进程提出新申请的代码部分
{
    printf("请输入申请资源的进程：");
    scanf("%d", &a);
    for (i = 1; i <= n; i++) {
        printf("请输入进程P[%d]对%d类资源的申请量：", a, i);
        scanf("%d", &Request[a][i]);
        if (Request[a][i] > Need[a][i])
            printf("\n出错！进程申请的资源数多于它自己申报的最大量\n");
        if (Request[a][i] > Available[i])
            printf("\n P[%d]必须等待\n", a);

        //以下是试探性分配
        Available[i] = Available[i] - Request[a][i];
        Allocation[a][i] = Allocation[a][i] + Request[a][i];
        Need[a][i] = Need[a][i] - Request[a][i];
        Work[i] = Available[i];
    }
    for (i = 1; i <= n; i++) {
        Pause[i] = Available[i];//Pause[i]只是一个暂时寄存的中间变量，为防止在下面
        //安全性检查时修改到Available[i]而代替的一维数组
        Finish[i] = false;
    }
    for (g = 1; g <= m; g++) {     //m个进程分别要求申请资源
        for (i = 1; i <= m; i++) {//每个进程要求分配资源检查是否安全
            b = 0;    //计数器初始化
            for (j = 1; j <= n; j++) {
                if (Need[i][j] <= Pause[j]) {
                    b = b + 1;
                }
                if (Finish[i] == false && b == n) {
                    for (l = 1; l <= n; l++) {
                        Pause[l] = Pause[l] + Allocation[i][l];
                    }
                    Finish[i] = true;
                    printf("$$ %d ", i);    //依次输出进程安全序列之一中每个元素
                }
            }
        }
    }
    printf("\n");
    for (i = 1; i <= m; i++) {
        if (Finish[i] == true)
            f = f + 1;    //统计Finish[i]＝＝true的个数
    }
    if (f == m) {
        printf("safe static");
        f = 0;        //将计数器f重新初始化，为下一次提出新的进程申请做准备
    } else {
        printf(" unsafe static ");    //以下代码为当系统被判定为不安全状态时
        //返回提出申请前的状态
        for (i = 1; i <= n; i++) {
            Available[i] = Available[i] + Request[a][i];
            Allocation[a][i] = Allocation[a][i] - Request[a][i];
            Need[a][i] = Need[a][i] + Request[a][i];
        }
    }
}

void mainprint()
{
    printf("当前的系统状态\n");
    printf(" 目前占有量 最大需求量 尚需要量 \n进程");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++) {
            printf(" %d类", j);
        }
    for (i = 1; i <= m; i++) {
        printf("\nP[%d]", i);
        for (j = 1; j <= n; j++) {
            printf(" %d ", Allocation[i][j]);
        }
        for (j = 1; j <= n; j++) {
            printf(" %d ", Max[i][j]);
        }
        for (j = 1; j <= n; j++) {
            printf(" %d ", Need[i][j]);
        }
    }
    printf("\n\n系统剩余资源量： ");
    for (i = 1; i <= n; i++) {
        printf(" %d ", Available[i]);
    }
    printf("\n");
}

void main()
{
    int k, h = 1;
    while (h) {
        {
            printf("\n\n ★ 欢迎使用本程序 ★\n");
            printf("\n\n 1:输入系统的资源数、申请进程数、每个类资源的实例数");
            printf("\n 2:…………………………………… 输入进程的资源申请");
            printf("\n 3:…………………………………………… 输出系统状态");
            printf("\n 4:………………………………………………… 退出程序");
            printf("\n\n please choose ");
            scanf("%d", &k);
        }
        switch (k) {
        case 1:
            mainenter();
            break;
        case 2:
            mainrequest();
            break;
        case 3:
            mainprint();
            break;
        case 4:
            h = 0;
            break;
        }
        printf("\n");
    }
    printf("\n\n 谢谢使用 \n");
    printf("\n\n See you next time!!!\n\n\n");
}

[root@liixun 2011级计科1班作业---11---银行家算法---C语言实现---030---毕赖子]# gcc -o banker banker.c
[root@liixun 2011级计科1班作业---11---银行家算法---C语言实现---030---毕赖子]# ./banker

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 1
请输入系统总共有的资源数：3
请输入总共有多少个进程：5
第1类资源有的资源实例：10
第2类资源有的资源实例：5
第3类资源有的资源实例：7
进程P[1]对第1类资源的最大需求量：7
进程P[1]对第2类资源的最大需求量：5
进程P[1]对第3类资源的最大需求量：3
进程P[2]对第1类资源的最大需求量：3
进程P[2]对第2类资源的最大需求量：2
进程P[2]对第3类资源的最大需求量：2
进程P[3]对第1类资源的最大需求量：9
进程P[3]对第2类资源的最大需求量：0
进程P[3]对第3类资源的最大需求量：2
进程P[4]对第1类资源的最大需求量：2
进程P[4]对第2类资源的最大需求量：2
进程P[4]对第3类资源的最大需求量：2
进程P[5]对第1类资源的最大需求量：4
进程P[5]对第2类资源的最大需求量：3
进程P[5]对第3类资源的最大需求量：3

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    0    0    7    5    3    7    5    3
P[2]   0    0    0    3    2    2    3    2    2
P[3]   0    0    0    9    0    2    9    0    2
P[4]   0    0    0    2    2    2    2    2    2
P[5]   0    0    0    4    3    3    4    3    3

系统剩余资源量：      10    5    7

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose
请输入申请资源的进程：1
请输入进程P[1]对1类资源的申请量：0
请输入进程P[1]对2类资源的申请量：1
请输入进程P[1]对3类资源的申请量：0
$$ 1 $$ 2 $$ 3 $$ 4 $$ 5
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   0    0    0    3    2    2    3    2    2
P[3]   0    0    0    9    0    2    9    0    2
P[4]   0    0    0    2    2    2    2    2    2
P[5]   0    0    0    4    3    3    4    3    3

系统剩余资源量：      10    4    7

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 2
请输入申请资源的进程：2
请输入进程P[2]对1类资源的申请量：2
请输入进程P[2]对2类资源的申请量：0
请输入进程P[2]对3类资源的申请量：0
$$ 1 $$ 2 $$ 3 $$ 4 $$ 5
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   2    0    0    3    2    2    1    2    2
P[3]   0    0    0    9    0    2    9    0    2
P[4]   0    0    0    2    2    2    2    2    2
P[5]   0    0    0    4    3    3    4    3    3

系统剩余资源量：      8    4    7

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

please choose 2
请输入申请资源的进程：3
请输入进程P[3]对1类资源的申请量：3
请输入进程P[3]对2类资源的申请量：0
请输入进程P[3]对3类资源的申请量：2
$$ 2 $$ 3 $$ 4 $$ 5 $$ 1
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   2    0    0    3    2    2    1    2    2
P[3]   3    0    2    9    0    2    6    0    0
P[4]   0    0    0    2    2    2    2    2    2
P[5]   0    0    0    4    3    3    4    3    3

系统剩余资源量：      5    4    5

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

  please choose 2
请输入申请资源的进程：4
请输入进程P[4]对1类资源的申请量：2
请输入进程P[4]对2类资源的申请量：1
请输入进程P[4]对3类资源的申请量：1
$$ 2 $$ 4 $$ 5 $$ 1 $$ 3
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   2    0    0    3    2    2    1    2    2
P[3]   3    0    2    9    0    2    6    0    0
P[4]   2    1    1    2    2    2    0    1    1
P[5]   0    0    0    4    3    3    4    3    3

系统剩余资源量：      3    3    4

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 2
请输入申请资源的进程：5
请输入进程P[5]对1类资源的申请量：0
请输入进程P[5]对2类资源的申请量：0
请输入进程P[5]对3类资源的申请量：2
$$ 2 $$ 4 $$ 5 $$ 1 $$ 3
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   2    0    0    3    2    2    1    2    2
P[3]   3    0    2    9    0    2    6    0    0
P[4]   2    1    1    2    2    2    0    1    1
P[5]   0    0    2    4    3    3    4    3    1

系统剩余资源量：      3    3    2

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 2
请输入申请资源的进程：2
请输入进程P[2]对1类资源的申请量：1
请输入进程P[2]对2类资源的申请量：0
请输入进程P[2]对3类资源的申请量：2
$$ 2 $$ 4 $$ 5 $$ 1 $$ 3
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   3    0    2    3    2    2    0    2    0
P[3]   3    0    2    9    0    2    6    0    0
P[4]   2    1    1    2    2    2    0    1    1
P[5]   0    0    2    4    3    3    4    3    1

系统剩余资源量：      2    3    0

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

please choose 2
请输入申请资源的进程：5
请输入进程P[5]对1类资源的申请量：3
  P[5]必须等待
请输入进程P[5]对2类资源的申请量：3
请输入进程P[5]对3类资源的申请量：0

 unsafe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 2
请输入申请资源的进程：1
请输入进程P[1]对1类资源的申请量：0
请输入进程P[1]对2类资源的申请量：2
请输入进程P[1]对3类资源的申请量：0

 unsafe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    1    0    7    5    3    7    4    3
P[2]   3    0    2    3    2    2    0    2    0
P[3]   3    0    2    9    0    2    6    0    0
P[4]   2    1    1    2    2    2    0    1    1
P[5]   0    0    2    4    3    3    4    3    1

系统剩余资源量：      2    3    0

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

please choose 2
请输入申请资源的进程：1
请输入进程P[1]对1类资源的申请量：0
请输入进程P[1]对2类资源的申请量：1
请输入进程P[1]对3类资源的申请量：0
$$ 2 $$ 4 $$ 5 $$ 1 $$ 3
safe static

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 3
当前的系统状态
        目前占有量     最大需求量      尚需要量
进程  1类  2类  3类  1类  2类  3类  1类  2类  3类
P[1]   0    2    0    7    5    3    7    3    3
P[2]   3    0    2    3    2    2    0    2    0
P[3]   3    0    2    9    0    2    6    0    0
P[4]   2    1    1    2    2    2    0    1    1
P[5]   0    0    2    4    3    3    4    3    1

系统剩余资源量：      2    2    0

 

            ★ 欢迎使用本程序 ★

  1:输入系统的资源数、申请进程数、每个类资源的实例数
  2:……………………………………  输入进程的资源申请
  3:……………………………………………  输出系统状态
  4:…………………………………………………  退出程序

 please choose 4

 

       谢谢使用

  See you next time!!!

[root@liixun 2011级计科1班作业---11---银行家算法---C语言实现---030---毕赖子]#