Chinaunix首页 | 论坛 | 博客

毕赖子的ChinaUnix博客

首页　| 　博文目录　| 　关于我

毕赖子

  • 博客访问： 369335
  • 博文数量： 159
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 182
  • 用 户 组： 普通用户
  • 注册时间： 2013-11-02 10:42
文章分类

全部博文（159）

文章存档

2015年（18）

2014年（132）

2013年（9）

我的朋友
最近访客
推荐博文
相关博文
银行家算法

分类： C/C++

2013-12-09 22:15:22

利用银行家算法避免死锁

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都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

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

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

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


点击(此处)折叠或打开

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

  4. #define true 1
  5. #define false 0

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

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

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

  24. void mainenter()        //主要的输入部分代码
  25. {
  26.     printf("请输入系统总共有的资源数：");
  27.     scanf("%d", &n);
  28.     printf("请输入总共有多少个进程：");
  29.     scanf("%d", &m);
  30.     for (i = 1; i <= n; i++) {
  31.         printf("第%d类资源有的资源实例：", i);
  32.         scanf("%d", &Available[i]);
  33.     }
  34.     for (i = 1; i <= m; i++) {
  35.         for (j = 1; j <= n; j++) {
  36.             printf("进程P[%d]对第%d类资源的最大需求量：", i, j);
  37.             scanf("%d", &Max[i][j]);
  38.             Need[i][j] = Max[i][j];
  39.         }
  40.     }
  41. }

  43. void mainrequest()        //进程提出新申请的代码部分
  44. {
  45.     printf("请输入申请资源的进程：");
  46.     scanf("%d", &a);
  47.     for (i = 1; i <= n; i++) {
  48.         printf("请输入进程P[%d]对%d类资源的申请量：", a, i);
  49.         scanf("%d", &Request[a][i]);
  50.         if (Request[a][i] > Need[a][i])
  51.             printf("\n出错！进程申请的资源数多于它自己申报的最大量\n");
  52.         if (Request[a][i] > Available[i])
  53.             printf("\n P[%d]必须等待\n", a);
  54.     
  55.         //以下是试探性分配
  56.         Available[i] = Available[i] - Request[a][i];
  57.         Allocation[a][i] = Allocation[a][i] + Request[a][i];
  58.         Need[a][i] = Need[a][i] - Request[a][i];
  59.         Work[i] = Available[i];
  60.     }
  61.     for (i = 1; i <= n; i++) {
  62.         Pause[i] = Available[i];//Pause[i]只是一个暂时寄存的中间变量，为防止在下面
  63.         //安全性检查时修改到Available[i]而代替的一维数组
  64.         Finish[i] = false;
  65.     }
  66.     for (g = 1; g <= m; g++) {     //m个进程分别要求申请资源
  67.         for (i = 1; i <= m; i++) {//每个进程要求分配资源检查是否安全
  68.             b = 0;    //计数器初始化
  69.             for (j = 1; j <= n; j++) {
  70.                 if (Need[i][j] <= Pause[j]) {
  71.                     b = b + 1;
  72.                 }
  73.                 if (Finish[i] == false && b == n) {
  74.                     for (l = 1; l <= n; l++) {
  75.                         Pause[l] = Pause[l] + Allocation[i][l];
  76.                     }
  77.                     Finish[i] = true;
  78.                     printf("$$ %d ", i);    //依次输出进程安全序列之一中每个元素
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     printf("\n");
  84.     for (i = 1; i <= m; i++) {
  85.         if (Finish[i] == true)
  86.             f = f + 1;    //统计Finish[i]＝＝true的个数
  87.     }
  88.     if (f == m) {
  89.         printf("safe static");
  90.         f = 0;        //将计数器f重新初始化，为下一次提出新的进程申请做准备
  91.     } else {
  92.         printf(" unsafe static ");    //以下代码为当系统被判定为不安全状态时
  93.         //返回提出申请前的状态
  94.         for (i = 1; i <= n; i++) {
  95.             Available[i] = Available[i] + Request[a][i];
  96.             Allocation[a][i] = Allocation[a][i] - Request[a][i];
  97.             Need[a][i] = Need[a][i] + Request[a][i];
  98.         }
  99.     }
  100. }

  102. void mainprint()
  103. {
  104.     printf("当前的系统状态\n");
  105.     printf(" 目前占有量 最大需求量 尚需要量 \n进程");
  106.     for (i = 1; i <= n; i++)
  107.         for (j = 1; j <= n; j++) {
  108.             printf(" %d类", j);
  109.         }
  110.     for (i = 1; i <= m; i++) {
  111.         printf("\nP[%d]", i);
  112.         for (j = 1; j <= n; j++) {
  113.             printf(" %d ", Allocation[i][j]);
  114.         }
  115.         for (j = 1; j <= n; j++) {
  116.             printf(" %d ", Max[i][j]);
  117.         }
  118.         for (j = 1; j <= n; j++) {
  119.             printf(" %d ", Need[i][j]);
  120.         }
  121.     }
  122.     printf("\n\n系统剩余资源量： ");
  123.     for (i = 1; i <= n; i++) {
  124.         printf(" %d ", Available[i]);
  125.     }
  126.     printf("\n");
  127. }

  129. void main()
  130. {
  131.     int k, h = 1;
  132.     while (h) {
  133.         {
  134.             printf("\n\n ★ 欢迎使用本程序 ★\n");
  135.             printf("\n\n 1:输入系统的资源数、申请进程数、每个类资源的实例数");
  136.             printf("\n 2:…………………………………… 输入进程的资源申请");
  137.             printf("\n 3:…………………………………………… 输出系统状态");
  138.             printf("\n 4:………………………………………………… 退出程序");
  139.             printf("\n\n please choose ");
  140.             scanf("%d", &k);
  141.         }
  142.         switch (k) {
  143.         case 1:
  144.             mainenter();
  145.             break;
  146.         case 2:
  147.             mainrequest();
  148.             break;
  149.         case 3:
  150.             mainprint();
  151.             break;
  152.         case 4:
  153.             h = 0;
  154.             break;
  155.         }
  156.         printf("\n");
  157.     }
  158.     printf("\n\n 谢谢使用 \n");
  159.     printf("\n\n See you next time!!!\n\n\n");
  160. }
[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---毕赖子]#

 

 

 

 

 

 

 

阅读(1590) | 评论(0) | 转发(1) |
0

上一篇：约瑟夫问题实现

下一篇：镜像二叉树

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6