Linux环境下银行家算法,C语言实现 操作系统 银行家算法

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;

}

// 进行资源预分配

for (i=0; 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个章节中：