yinhang.cpp

操作系统中银行家算法的模拟

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

#define M 5   /*进程数*/
#define N 3   /*资源数*/

/**
* TC中用到
#define true 1
#define false 0
typedef int bool
**/
//系统可用资源向量
int Available[N] = {3,3,2};
//最大需求向量
int Max[M][N] = {
        {7,5,3},
        {3,2,2},
        {9,0,2},
        {2,2,2},
        {4,3,3},
    };
//资源分配向量
int Allocation[M][N] = {
        {0,1,0},
        {2,0,0},
        {3,0,2},
        {2,1,1},
        {0,0,2},
        };
//需求向量
int Need[M][N] = {
    {7,4,3},
    {1,2,2},
    {6,0,0},
    {0,1,1},
    {4,3,1},
    };


//比较两个一维数组
//判断 a >= b ?
bool compare(int a[],int b[],int n)
{
  int i=0;
  for(i = 0;i < n;i++)
  {
    if(a[i] < b[i])
    {
        return false;
    }
  }   

  return true;

}

//一维数组加法
//a = a + b
void add(int a[],int b[],int n)
{
  int i = 0;
  for(i = 0;i < n;i++)
  {
    a[i] += b[i];
  }
}

//一维数组减法
//a = a - b
void subtract(int a[],int b[],int n)
{
  int i = 0;
  for(i = 0;i < n;i++)
  {
    a[i] -= b[i];
  }
}

//将数组b的值赋给a，n为数组的大小
void assign(int a[],int b[],int n)
{
  int i = 0;
  for(i = 0;i < n;i++)
  {
    a[i] = b[i];
  }
}

//判断是否是安全状态
//av 可用资源矩阵
//sl 记录安全路径
bool safe(int *sl)
{
  int i;
  int count = 0;   /*记录finish = true 的个数*/
  int n = 0;
  int work[N];
  bool finish[M];
  //work = av;
  assign(work,Available,N);
  //初始化标记 finish
  for(i = 0;i < M;i++)
  {
	  finish[i] = false;
  }
  
  //n为进程的个数
  //循环最多执行n次
  n = M;
  while(n--)
  {
    for(i = 0;i < M;i++)
    {
        //判断是否安全
        if(count >= M)
        {
          //全部进程都可安全执行（finish = true）
          return true;
        }
  
//判断能否满足进程i的要求
        //work >= Need ?
        if(finish[i] == false && compare(work,Need[i],N))
        {
          //分配，待进程完成后再释放
          add(work,Allocation[i],N);
          finish[i] = true;                 
          //记录安全路径
          sl[count] = i;
          //能满足的进程数+1           
          count++;
        }
    }
  }
  if(count >= M)
  {
    return true;
  }
  else
  {
    return false;
  }   
}

//请求分配
//pid进程，r请求向量，n资源个数
bool request(int pid,int * r,int n)
{
  int i;
  //记录安全路径
  int sl[5];   
  if(compare(Need[pid],r,n) == true &&
      compare(Available,r,n) == true) //更改，开始漏掉了compare(Available,r,n) == true
  {
    //尝试分配资源
    subtract(Available,r,N);
    add(Allocation[pid],r,N);
    subtract(Need[pid],r,N);     

    //判断是否是安全状态
    if(safe(sl))
    {
        //打印安全路径
        printf("安全路径：\n\t");     
        for(i = 0;i < M;i++)
        {
          printf("p%d ",sl);
        }
        printf("\n");
        //可以分配
        return true;
    }
    else
    {
        //不分配
        //恢复到分配前的状态
        add(Available,r,N);
        subtract(Allocation[pid],r,N);
        add(Need[pid],r,N);

        return false;
    }
  }
  else
  {
    //error
    return false;
  }
}

//打印一维数组
void print(int a[],int n)
{
  int i;
  for(i = 0;i < n;i++)
  {
    printf("%4d",a[i]);
  }
  printf("\n");
}

//提示信息
char help()
{
  printf("-----操作提示-----\n");
  printf("A--自动随机申请资源\n");
  printf("S--手动输入申请资源\n");
  return getch();
}

//显示系统信息
void init()

{
  int i;
  printf("该系统共有进程5个,\n其对资源的需求和分配情况分别是：\n");
  for(i = 0;i < M;i++)
  {
    printf("\t进程%d资源最大需求：",i);
    print(Max[i],N);
  }
  printf("\n");
  for(i = 0;i < M;i++)
  {
    printf("\t进程%d已经分配资源：",i);
    print(Allocation[i],N);
  }

  printf("系统可用资源数量：\n\t");
  print(Available,N);
}

//输入
void input(int *r,int n,int *id)
{
  char ch;
  printf("请输入进程的id(0 ~ 4):\n");
  ch = getche();
  *id = ch - 0x30;

  printf("\n请输入对0类资源的申请数量(int):\n");
  ch = getche();
  r[0] = ch - 0x30;
  
  printf("\n请输入对1类资源的申请数量(int):\n");
  ch = getche();
  r[1] = ch - 0x30;
  
  printf("\n请输入对2类资源的申请数量(int):\n");
  ch = getche();
  r[2] = ch - 0x30;

  printf("\n您输入的是：Request[%d](%d,%d,%d)\n",*id,r[0],r[1],r[2]);
}

//检查输入
bool check(int id,int r1,int r2,int r3)
{
  if(id > 4 || id < 0 || r1 < 0 || r2 < 0 || r3 < 0)
  {
    return false;
  }
  else
  {
    return true;
  }
}

int main()
{
  //进程id
  int id;
  //控制字符
  char control;
  //资源请求向量
  int r[3];
  //显示开始信息
  init();
  //随机数初始化
  srand(NULL);
  //主控过程
  while(1)
  {
    //提示
    control = help();
    if(control == 'a' || control == 'A')


{
        //随机申请资源
        id = rand()%5;
        r[0] = rand()%5;
        r[1] = rand()%5;
        r[2] = rand()%5;
        //显示申请信息
        printf("\tRequest[%d](%d,%d,%d)\n",id,r[0],r[1],r[2]);
        
        if(request(id,r,N))
        {
          printf("分配成功！\n");
        }
        else
        {
          printf("分配失败！\n");
        }
    }
    else
    {
        //输入申请信息
        input(r,N,&id);
        //检查输入
        if(check(id,r[0],r[1],r[2]) == false)
        {
          printf("\n输入错误请检查后重新输入\n");
          continue;
        }
        //执行   
        if(request(id,r,N))
        {
          printf("Request Secceed!\n");
        }
        else
        {
          printf("Request Fail!\n");
        }               
    }
    //显示当前系统资源和进程情况
    printf("系统可用资源：\n");
    print(Available,N);
    
    printf("进程%d的最大资源需求：\n",id);
    print(Max[id],N);
    
    printf("进程%d已经分配资源：\n",id);
    print(Allocation[id],N);   
    
    //提示是否继续n或N退出
    printf("\nContinue?(Y/N)!\n");
    control = getch();
    if(control == 'n' || control == 'N')
    {
        break;
    }
  }
  return 0;
}