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個章節中：
