歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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++ 設計新思維》 下載見 http://www.linuxidc.com/Linux/2014-07/104850.htm

C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm

讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm

讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm

將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成長之��(十):其他高級議題

Copyright © Linux教程網 All Rights Reserved