C语言实现 操作系统 银行家算法

C语言实现 操作系统 银行家算法

/**************************************************
银行家算法：
主要的思想是 舍大取小，先满足小的，最后才满足大的。

author: lyb
date: 2014/10/15
***************************************************/

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

// 进程运行状态标志
#define TRUE 1
#define FALSE 0
#define WAIT -1

/* version 1
#define PMAX 20 // 假设最大的进程的数目
#define RMAX 20 // 假设最大的资源的分类数

int Resource[RMAX] = {0};    // 各类资源的总量
int Max[PMAX][RMAX] = {0};    // 各资源的最大需求量
int Need[PMAX][RMAX] = {0};    // 各进程需求的资源量
int Allocation[PMAX][RMAX] = {0};  // 已分配的资源量
int Available[RMAX] = {0};    // 剩余可用的资源量
*/

// version 2  采用动态分配数组，为了函数调用的方便，使用全局指针
int *Resource = NULL;     // 各类资源的总量
int *Max  = NULL;     // 各资源的最大需求量
int *Need  = NULL;     // 各进程需求的资源量
int *Allocation = NULL;     // 已分配的资源量
int *Available = NULL;     // 剩余可用的资源量

// 检测此时的系统分配状态是否安全 （核心函数）
int testStatus(const int P, const int R)
{
 int finish = 0;    // 运行完成的进程数
 int wait = 0;    // 等待的进程数
 
 int minR = 0;    // 最小的资源数
 int minP = 0;    // 最小需求资源的进程

 int i = 0;
 int j = 0;
 int k = 0;
 int l = 0;

 int *status = (int*)malloc(P*sizeof(int));    // 进程的状态
 int *Available_tmp = (int*)malloc(R*sizeof(int)); // Available_tmp 是 Available的一份拷贝

 if (status != NULL && Available_tmp != NULL)
 {
  // 所有进程状态置零
  memset(status, FALSE, P*sizeof(int));

  // 这里拷贝 Available
  memcpy(Available_tmp, Available, R*sizeof(int));
 }
 else
 {
  printf("pointer NULL\n");
  return FALSE;
 }

 
 while( finish != P && wait != P)
 {
  // 以第一类资源为基准，选取该资源需求量最小的进程
  minR = Resource[0];  // 这里选取最大值，方便后面的比较获取最小值
  minP = 0;

  for (i=0; i<P; ++i)
  {
   if (status[i] == FALSE && Need[i*R + 0] < minR)
   {
    minR = Need[i*R + 0];
    minP = i; 
   }
  }

  //printf("%d\n", minP);

  // 验证挑选出来的进程能否满足
  for (j=0; j<R; ++j)
  {
   if (Need[minP*R + j] > Available_tmp[j])
   {
    break;
   }
  }

  if (j == R)  // 能够满足
  {
   //printf("P%d\t", minP);  //打印成功分配的进程

   status[minP] = TRUE;
   finish++;

   // 如果资源能够分配了，那么进程就能够运行结束，然后释放资源，这里需要回收资源
   for (l=0; l<R; ++l)
   {
    Available_tmp[l] += Allocation[minP*R + l];  // 回收
   }

   // 唤醒等待的所有进程
   for(k=0; k<P; ++k)
   {
    if (status[k] == WAIT)
    {
     status[k] = FALSE;
     wait--;
    }
   }
  }
  else
  {
   // 不能满足时，该进程等待，等待数++
   status[minP] = WAIT;
   wait++;
  }
 }

 free(status);
 free(Available_tmp);

 // 验证状态
 if (finish == P)
 {
  return TRUE;
 }
 else
  return FALSE;
}

// 从文件中读取数据
int readData(int *p, int *r)
{
 int i = 0;
 int pCount = 0;
 int rCount = 0;

 // 为方便操作，这里仅使用重定向处理
 freopen("in.txt", "r", stdin);

 scanf("%d", p);
 scanf("%d", r);

 pCount = *p;
 rCount = *r;

 // 分配内存
 Resource =  (int*)malloc( rCount * sizeof(int));
 Max =   (int*)malloc( pCount * rCount * sizeof(int));
 Need =   (int*)malloc( pCount * rCount * sizeof(int));
 Allocation = (int*)malloc( pCount * rCount * sizeof(int));
 Available =  (int*)malloc( rCount * sizeof(int));

 if (Resource == NULL || Max == NULL || Need == NULL
  || Allocation == NULL || Available == NULL )
 {
  return FALSE;
 }

 // 各资源的总量
 for (i=0; i<rCount; ++i)
 {
  scanf("%d", Resource + i);
 }

 // 最大需求量
 for (i=0; i<pCount*rCount; ++i)
 {
  scanf("%d", Max+i);
 }

 // 已分配的资源量
 for (i=0; i<pCount*rCount; ++i)
 {
  scanf("%d", Allocation+i);
 }

 // 剩余可分配的资源量
 for (i=0; i<rCount; ++i)
 {
  scanf("%d", Available+i);
 }

 // 计算各资源的需求量
 for (i=0; i<pCount*rCount; ++i)
 {
  *(Need+i) = *(Max+i) - *(Allocation+i);
 }

 return 0;
}

// 某进程申请资源的请求
int request(const int PCount, const int RCount, const int pId, const int *reqSource)
{
 int i=0;
 int *testAllocate = (int*)malloc(PCount*RCount*sizeof(int));  // 预存储尝试的分配情况

 if (testAllocate != NULL)
 {
  memcpy(testAllocate, Allocation, PCount*RCount*sizeof(int));
 }
 else
 {
  return FALSE;
 }

 // 进行资源预分配
 for (i=0; i<RCount; ++i)
 {
  if (reqSource[i] > Available[i])  // 申请的资源比剩余的资源还多！
  {
   return FALSE;
  }
  else
  {
   testAllocate[pId*RCount + i] += reqSource[i];
  }
 }

 if (testStatus(PCount, RCount) == TRUE)    // 是一个安全状态
 {
  // 正式分配
  memcpy(Allocation, testAllocate, PCount*RCount*sizeof(int));
 
  free(testAllocate);
  return TRUE;
 }
 else
 {
  free(testAllocate);
  return FALSE;
 }

}
 
// 释放所有的内存空间
int destroy()
{
 if (Resource == NULL || Max == NULL || Need == NULL
  || Allocation == NULL || Available == NULL)
 {
  return FALSE;
 }
 else
 {
  free(Resource);
  Resource = NULL;
  free(Max);
  Max = NULL;
  free(Need);
  Need = NULL;
  free(Allocation);
  Allocation = NULL;
  free(Available);
  Available = NULL;

  printf("Destroy\n");

  return TRUE;
 }

}

int main()
{
 int p = 0;  // 进程数
 int r = 0;  // 资源分类数

 int reqSource[3] = {0, 3, 4};

 readData(&p, &r);

 // test now status
 if (testStatus(p, r) == TRUE)
 {
  printf("Saft\n");
 }
 else
 {
  printf("nonSaft\n");
 }

 // for test  reqSource[3] = {0, 3, 4};
 if (request(p, r, 1, reqSource) == TRUE)
 {
  printf("Allocate\n");
 }
 else
 {
  printf("Non-Allocate\n");
 }
 

 // 释放所有的内存空间
 destroy(); 

 return 0;
}

/*  in.txt

5 3  // 进程数  资源种类数
17 5 20  // 各类资源总数

// 最大需求量
5 5 9
5 3 6
4 0 11
4 2 5
4 2 4

// 已分配资源数
2 1 2
4 0 2
4 0 5
2 0 4
3 1 4

// 剩余的资源数
2 3 3   

*/

将C语言梳理一下，分布在以下10个章节中：

1. Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成长之路（十）：其他高级议题