银行家算法

发布时间:2024年01月19日

主要内容

一.银行家算法

1.需求分析

通过编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生条件,采用适当的算法,有效防止和避免死锁发生。

  1. 模拟一个银行家算法,判断是否处于安全状态。
  2. 初始化时,让系统拥有一定的资源。
  3. 如果预分配后,系统处于不安全状态,则提示不能满足请求。

1.设置数据结构:包括资源向量(Resource),最大需求矩阵(Need),分配矩阵(Allocation),需求矩阵(Request), 可利用剩余资源数(Available)。
2.设计安全性算法:设置工作向量 Work 表示系统可提供进程继续运行可利用资源数目,Finish 表示系统是否有足够的资源分配给进程。
3. 利用三组数据分别测试银行家算法,并给出结果,包括安全状态和不安全状态。安全状态请给出进程进行资源分配的安全序列。

2.概要设计

为了实现银行家算法,在系统中必须设置这样四个数据结构:
1)Available 向量:系统中可利用的资源数目
2)Max 矩阵:每个进程对每种资源的最大需求
3)Allocation 矩阵:每个进程已分配的各类资源的数目
4)Need 矩阵:每个进程还需要的各类资源数,其中三个矩阵间存在下述关系:
Need[i,j] = Max[i,j] - allocation[i, j]

算法逻辑:
设 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 等待

3.源代码

代码如下(示例):
 #include<stdio.h>
#define true 1
#define false 0
#define N 4
#define M 3
#define MAXINT 9999

int resource[M] = { 10,5,7 };
int available[M] = { 0 };
int need[N][M] =
{ 7,5,3,
3,2,2,
9,0,2,
2,2,2 };
int allocation[N][M] =
{ 0,1,0,
2,0,0,
3,0,2,
2,1,1 };
int request[N][M] = { 0 };
bool Finish[N];
int safeSeries[N] = { MAXINT, MAXINT , MAXINT , MAXINT };//用于存放安全序列


void Init();
void showInfo();
bool isSafe();
void SafeInfo(int* work, int i);

void Init()
{
 int i, j;
 //printf("输入进程数量、资源数量\n");
 //scanf("%d %d",&processNum,&resourceNum);

 printf("输入当前资源数目\n");
 for (i = 0; i < M; i++) {
  scanf("%d", &resource[i]);
 }
 printf("输入最大需求矩阵\n");
 for (i = 0; i < N; i++) {
  for (j = 0; j < M; j++) {
   scanf("%d", &need[i][j]);
  }
 }
 printf("输入分配矩阵\n");
 for (i = 0; i < N; i++) {
  for (j = 0; j < M; j++) {
   scanf("%d", &allocation[i][j]);
  }
 }
 // printf("输入当前需求矩阵\n");
 for (i = 0; i < N; i++)
 {
  for (j = 0; j < M; j++)
  {
   request[i][j] = need[i][j] - allocation[i][j];
  }
 }
}

void showInfo()
{
 int i, j;
 printf("当前资源总量:");
 for (j = 0; j < M; j++) {
  printf("%d ", resource[j]);
 }
 printf("\n");
 //计算Avaliable向量
 for (i = 0; i < M; i++)
 {
  int count = 0;
  for (j = 0; j < N; j++)
  {
   count += allocation[j][i];
  }
  available[i] = resource[i] - count;
 }
 //计算request向量
 for (i = 0; i < N; i++)
 {
  for (j = 0; j < M; j++)
  {
   request[i][j] = need[i][j] - allocation[i][j];
  }
 }
 printf(" PID\t Need\t\tAllocation\tRequest\n");
 for (i = 0; i < N; i++)
 {
  printf(" P%d\t", i);
  for (j = 0; j < M; j++)
  {
   printf("%d ", need[i][j]);
  }
  printf("\t\t");
  for (j = 0; j < M; j++)
  {
   printf("%d ", allocation[i][j]);
  }
  printf("\t\t");
  for (j = 0; j < M; j++)
  {
   printf("%d ", request[i][j]);
  }
  printf("\n");
 }
 printf("当前资源剩余:");
 for (j = 0; j < M; j++) {
  printf("%d ", available[j]);
 }
}

bool isSafe()
{
 int i, j, k;
 int trueFinished = 0;
 int work[M];
 for (i = 0; i < M; i++)
 {
  work[i] = available[i];//
 }

 for (i = 0; i < N; i++)
 {
  Finish[i] = false;
 }
 i = 0;
 int temp = 0;
 int temp0 = 0;
 int flag = 0;
 while (trueFinished != N)
 {
  int j = 0;
  if (Finish[i] != true)
  {
   for (j = 0; j < M; j++)
   {
    if (request[i][j] > work[j])
    {
     break;
    }
   }
  }
  if (j == M)
  {
   Finish[i] = true;
   SafeInfo(work, i);
   for (k = 0; k < M; k++)
   {
    work[k] += allocation[i][k];
   }
   int k2;
   safeSeries[trueFinished++] = i;
  }
  i++;
  if (i >= N)
  {
   if (flag == 0)
   {
    temp = trueFinished;
    temp0 = trueFinished;
   }
   i = i % N;
   if (flag == 1) {
    temp = trueFinished;
    if (temp == temp0)
     break;
    else
     temp0 = temp;
   }
   flag = 1;
  }
  temp = trueFinished;
 }

 if (trueFinished == N)
 {
  printf("\n系统安全!\n\n安全序列为:");
  for (i = 0; i < N; i++)
  {
   printf("%d ", safeSeries[i]);
  }
  printf("\n");
  return true;
 }
 printf("******系统不安全!******\n");
 return false;
}

void SafeInfo(int* work, int i)
{
 int j;
 printf(" P%d\t", i);
 for (j = 0; j < M; j++)
 {
  printf("%d ", work[j]);
 }
 printf("\t\t");
 for (j = 0; j < M; j++)
 {
  printf("%d ", request[i][j]);
 }
 printf("\t ");
 for (j = 0; j < M; j++)
 {
  printf("%d ", allocation[i][j]);
 }
 printf("\t\t");
 for (j = 0; j < M; j++)
 {
  printf("%d ", allocation[i][j] + work[j]);
 }
 printf("\n");
}

int main()
{
 int i, j, curProcess;
 int wheInit = 0;
 printf("是否使用内置数据?0是,1否:");
 scanf("%d", &wheInit);
 if (wheInit)
 {
  Init();
 }
 printf("---------------------------------------------------------\n");
 showInfo();
 printf("\n---------------------------------------------------------\n");
 printf("\n系统安全情况分析\n");
 printf(" PID\t Work\t\tRequest\tAllocation\tWork+Allocation\n");
 isSafe();
 return 0;
}

在这里插入图片描述
在这里插入图片描述


总结

以上是今天要讲的内容,练习了银行家算法。

文章来源:https://blog.csdn.net/weixin_59994613/article/details/135684915
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。