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

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

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

#include
#include
#include
#include

// 进程运行状态标志
#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 {
if (status[i] == FALSE && Need[i*R + 0] < minR)
{
minR = Need[i*R + 0];
minP = i;
}
}

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

// 验证挑选出来的进程能否满足
for (j=0; 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 {
Available_tmp[l] += Allocation[minP*R + l]; // 回收
}

// 唤醒等待的所有进程
for(k=0; 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 {
scanf("%d", Resource + i);
}

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

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

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

// 计算各资源的需求量
for (i=0; 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;
}