模拟银行家算法
【摘要】 介绍
data.h
#ifndef _Data_h_#define _Data_h_ #include <stdio.h>#include <stdlib.h>#include <string.h> #define ElemType PCB#define Status int#define true 1#define false 0...
介绍
data.h
-
#ifndef _Data_h_
-
#define _Data_h_
-
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
-
#define ElemType PCB
-
#define Status int
-
#define true 1
-
#define false 0
-
#define OK 1
-
#define ERROR 0
-
#define RESOURCE_NUM 3
-
#define MAX_RESOURCE_A_NUM 10
-
#define MAX_RESOURCE_B_NUM 5
-
#define MAX_RESOURCE_C_NUM 7
-
#define NAME_MAXSIZE 20
-
#define PCB_Num 5
-
typedef struct{
-
int MaxNum[RESOURCE_NUM]; //需要每项资源个数
-
int AllocationNum[RESOURCE_NUM]; //已占用每项资源个数
-
int NeedNum[RESOURCE_NUM]; //还需要的每项资源个数
-
}ResourceList;
-
-
typedef struct
-
{
-
char Name[NAME_MAXSIZE]; //进程名
-
ResourceList resList; //资源清单
-
}PCB;
-
-
typedef struct Node
-
{
-
ElemType data;
-
struct Node * Next;
-
}LNode,*LinkList;
-
-
#endif
chainlist.h
-
#ifndef _ChainList_h_
-
#define _ChainList_h_
-
-
#include "Data.h"
-
-
Status Init(LinkList *L);
-
void Assignment(ElemType *e1, ElemType e2);
-
Status ListInsert_L(LinkList L,ElemType e);
-
-
#endif
实现
ProPCB.h
-
#ifndef _ProPCB_h_
-
#define _ProPCB_h_
-
-
#include "ChainList.h"
-
#include <string.h>
-
//上队列
-
Status GetProcess(LinkList Q,ElemType e);
-
//银行家算法
-
Status BankerAlgorithm(int *Allocation, int *Request,int i, int *Need, int *Available);
-
//安全性检测算法
-
Status SecurityCheck(int *Allocation,int *Need, int *Available);
-
//分配资源
-
Status AllocateResource(LinkList PCBdata , int pos , int *Request);
-
//获取资源矩阵
-
void GetMatrixData(LinkList PCBdata,int *Max,int *Allocation,int *Need,int *Available);
-
//打印进程资源信息
-
void PrintProQueue(LinkList L, int *A);
-
//得到指定PCB名的位置
-
void GetPos(LinkList L, char *name, int len, int *pos);
-
//对当前的请求进行预分配
-
void PreGrant(int* Allocation, int *Request,int pos,int *Need, int *Available);
-
//正式分配算法
-
void GrantSource(LinkList L, int *Request, int pos, int *Available);
-
-
#endif
chainlist.c
-
#include "ChainList.h"
-
extern int CPUUsedTime;
-
Status Init(LinkList *L)
-
{
-
*L = (LinkList)malloc(sizeof(LNode));
-
strcpy((*L)->data.Name, "");
-
(*L)->Next = NULL;
-
return OK;
-
}
-
-
void Assignment(ElemType *e1, ElemType e2)
-
{
-
int i = 0;
-
strcpy(e1->Name,e2.Name);
-
for(i = 0; i < RESOURCE_NUM; ++i)
-
{
-
e1->resList.AllocationNum[i] = e2.resList.AllocationNum[i];
-
e1->resList.MaxNum[i] = e2.resList.MaxNum[i];
-
e1->resList.NeedNum[i] = e2.resList.NeedNum[i];
-
}
-
}
-
-
Status ListInsert_L(LinkList L,ElemType e) //这样修改应该不对 p = *L出错
-
{
-
LinkList p = L, s;
-
while (p->Next)
-
p = p->Next;
-
s = (LinkList)malloc(sizeof(LNode));
-
Assignment(&s->data, e);
-
s->Next = p->Next;
-
p->Next = s;
-
return OK;
-
}
-
ProPCB.c
-
#include "ProPCB.h"
-
-
Status GetProcess(LinkList Q,ElemType e)
-
{
-
return ListInsert_L(Q, e);
-
}
-
-
Status AllocateResource(LinkList PCBdata , int pos , int *Request)
-
{
-
int i = 1;
-
LNode *p = PCBdata->Next;
-
-
while (p && i < pos)
-
{
-
p = p->Next;
-
++i;
-
}
-
if(!p || i > pos)
-
return ERROR;
-
for (i = 0; i < RESOURCE_NUM; ++i)
-
{
-
p->data.resList.AllocationNum[i] += Request[i];
-
p->data.resList.NeedNum[i] -= Request[i];
-
}
-
return OK;
-
}
-
void GetMatrixData(LinkList PCBdata,int *Max,int *Allocation,int *Need,int *Available)
-
{
-
LNode *p;
-
int i, j, c = RESOURCE_NUM;
-
Available[0] = Available[1] = Available[2] = 0;
-
for(p = PCBdata->Next, i = 0; p; p = p->Next, ++i)
-
{
-
for(j = 0; j < RESOURCE_NUM; ++j)
-
{
-
Max[i * c + j] = p->data.resList.MaxNum[j];
-
Allocation[i * c + j] = p->data.resList.AllocationNum[j];
-
Need[i * c + j] = p->data.resList.NeedNum[j];
-
}
-
Available[0] += Allocation[i * c + 0];
-
Available[1] += Allocation[i * c + 1];
-
Available[2] += Allocation[i * c + 2];
-
}
-
Available[0] = MAX_RESOURCE_A_NUM - Available[0];
-
Available[1] = MAX_RESOURCE_B_NUM - Available[1];
-
Available[2] = MAX_RESOURCE_C_NUM - Available[2];
-
}
-
-
-
void PrintProQueue(LinkList L,int *available)
-
{
-
int i = 0;
-
L = L->Next;
-
printf(" -------------------------------------------------------------\n");
-
printf("|进程名 | Max | Allocation | Need | Available |\n");
-
printf("| | A B C | A B C | A B C | A B C |\n");
-
while(L)
-
{
-
printf("| %s | %d %d %d | %d %d %d | %d %d %d | %d %d %d |\n",
-
L->data.Name, L->data.resList.MaxNum[0], L->data.resList.MaxNum[1], L->data.resList.MaxNum[2],
-
L->data.resList.AllocationNum[0],L->data.resList.AllocationNum[1],L->data.resList.AllocationNum[2],
-
L->data.resList.NeedNum[0],L->data.resList.NeedNum[1],L->data.resList.NeedNum[2],
-
available[0], available[1], available[2]);
-
L = L->Next;
-
}
-
printf(" -------------------------------------------------------------\n");
-
-
}
-
-
//安全性检测算法
-
Status SecurityCheck(int *Allocation,int *Need, int *Available)
-
{
-
/ 以下补充 //
-
int work[RESOURCE_NUM];
-
int Finish[PCB_Num];
-
int k, i, j, t, f;
-
int flag;
-
-
//初始化工作向量和标记数组
-
memcpy(work, Available, sizeof work);
-
memset(Finish, 0, sizeof Finish);
-
-
//最多检测PCB_Num次
-
for(k = 0; k < PCB_Num; ++k){
-
flag = 0;
-
for(i = 0; i < PCB_Num; ++i){
-
//已经被访问
-
if(Finish[i]){
-
continue;
-
}
-
-
//检测是否所有资源都能被分配
-
for(j = 0; j < RESOURCE_NUM; ++j){
-
if(!(Need[i * 3 + j] <= work[j])){
-
break;
-
}
-
}
-
-
//可以满足，回收
-
if(j == RESOURCE_NUM){
-
for(t = 0; t < RESOURCE_NUM; ++t){
-
work[t] += Allocation[i * 3 + t];
-
}
-
Finish[i] = 1;
-
flag = 1;
-
break;
-
}
-
}
-
-
//为进行分配，跳出循环
-
if(!flag){
-
break;
-
}
-
}
-
-
for(f = 0; f < PCB_Num; ++f){
-
//只要有一个进程不满足，跳出循环
-
if(!Finish[f]){
-
return ERROR;
-
}
-
}
-
-
return OK;
-
}
-
-
//银行家算法
-
Status BankerAlgorithm(int* Allocation, int *Request,int pos,int *Need, int *Available)
-
{
-
/ 以下补充 //
-
int i;
-
//检查请求的是否大于需要的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
if(Request[i] > Need[pos*3 + i]){
-
return ERROR;
-
}
-
}
-
-
//检查请求的是否大于可分配的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
if(Request[i] > Available[i]){
-
return ERROR;
-
}
-
}
-
-
//进行预分配
-
PreGrant(Allocation, Request, pos, Need, Available);
-
-
//进行安全性检测
-
if(!SecurityCheck(Allocation, Need, Available)){
-
return ERROR;
-
}
-
-
return OK;
-
}
-
-
//根据PCB的名字得到该PCB在链表中的位置
-
void GetPos(LinkList L, char *name, int len, int *pos)
-
{
-
LinkList p = L->Next;
-
char PcbName[NAME_MAXSIZE];
-
memcpy(PcbName, name, (len + 1) * sizeof(char));
-
(*pos) = 0;
-
-
while(p){
-
if(strcmp(p->data.Name, PcbName)){
-
(*pos)++;
-
p = p->Next;
-
} else {
-
break;
-
}
-
}
-
}
-
-
//预分配算法
-
void PreGrant(int* Allocation, int *Request,int pos,int *Need, int *Available){
-
int i;
-
//1. Need减去请求的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
Need[pos*3 + i] -= Request[i];
-
}
-
-
//2. Available减去请求的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
Available[i] -= Request[i];
-
}
-
-
//3. Allocation加上请求的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
Allocation[pos*3 + i] += Request[i];
-
}
-
}
-
-
/**
-
* 1.首先对请求资源的进程进行分配资源
-
* 2.如果给该进程分配资源之后，该进程所需的资源等于已经得到的资源，那么对其拥有的资源进行回收
-
*/
-
-
//正式分配算法,pos从0开始标记
-
void GrantSource(LinkList L, int *Request, int pos, int *Available){
-
LinkList p = L->Next;
-
int tag = 0;
-
int i;
-
int flag = 0;
-
-
if(tag < pos && NULL != p){
-
p = p->Next;
-
tag++;
-
}
-
-
if(p){
-
//已获得的加上请求的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
p->data.resList.AllocationNum[i] += Request[i];
-
}
-
-
//还需要的减去请求的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
p->data.resList.NeedNum[i] -= Request[i];
-
}
-
-
//可利用的减去请求的
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
Available[i] -= Request[i];
-
}
-
-
//如果进行分配之后该进程最大所需资源数目等于已获得的资源数目，则对资源进行回收
-
flag = 0;
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
if(p->data.resList.AllocationNum[i] != p->data.resList.MaxNum[i]){
-
flag = 1;
-
break;
-
}
-
}
-
-
if(!flag){
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
Available[i] += p->data.resList.AllocationNum[i];
-
}
-
}
-
}
-
}
main
-
#include "ProPCB.h"
-
-
void InputData(LinkList * pPCBdata)
-
{
-
ElemType e = {{0},{{0},{0},{0}}};
-
strcpy(e.Name,"P0");
-
e.resList.MaxNum[0] = 7; e.resList.MaxNum[1] = 5; e.resList.MaxNum[2] = 3;
-
e.resList.AllocationNum[0] = 0;
-
e.resList.AllocationNum[1] = 1;
-
e.resList.AllocationNum[2] = 0;
-
e.resList.NeedNum[0] = 7; e.resList.NeedNum[1] = 4; e.resList.NeedNum[2] = 3;
-
GetProcess(*pPCBdata,e);
-
-
strcpy(e.Name,"P1");
-
e.resList.MaxNum[0] = 3; e.resList.MaxNum[1] = 2; e.resList.MaxNum[2] = 2;
-
e.resList.AllocationNum[0] = 2;
-
e.resList.AllocationNum[1] = 0;
-
e.resList.AllocationNum[2] = 0;
-
e.resList.NeedNum[0] = 1; e.resList.NeedNum[1] = 2; e.resList.NeedNum[2] = 2;
-
GetProcess(*pPCBdata,e);
-
-
strcpy(e.Name,"P2");
-
e.resList.MaxNum[0] = 9; e.resList.MaxNum[1] = 0; e.resList.MaxNum[2] = 2;
-
e.resList.AllocationNum[0] = 3;
-
e.resList.AllocationNum[1] = 0;
-
e.resList.AllocationNum[2] = 2;
-
e.resList.NeedNum[0] = 6; e.resList.NeedNum[1] = 0; e.resList.NeedNum[2] = 0;
-
GetProcess(*pPCBdata,e);
-
-
strcpy(e.Name,"P3");
-
e.resList.MaxNum[0] = 2; e.resList.MaxNum[1] = 2; e.resList.MaxNum[2] = 2;
-
e.resList.AllocationNum[0] = 2;
-
e.resList.AllocationNum[1] = 1;
-
e.resList.AllocationNum[2] = 1;
-
e.resList.NeedNum[0] = 0; e.resList.NeedNum[1] = 1; e.resList.NeedNum[2] = 1;
-
GetProcess(*pPCBdata,e);
-
-
strcpy(e.Name,"P4");
-
e.resList.MaxNum[0] = 4; e.resList.MaxNum[1] = 3; e.resList.MaxNum[2] = 3;
-
e.resList.AllocationNum[0] = 0;
-
e.resList.AllocationNum[1] = 0;
-
e.resList.AllocationNum[2] = 2;
-
e.resList.NeedNum[0] = 4; e.resList.NeedNum[1] = 3; e.resList.NeedNum[2] = 1;
-
GetProcess(*pPCBdata,e);
-
}
-
int main(void)
-
{
-
LinkList PCBdata; //PCBdata里面存放原始数据
-
ElemType e = {{0},{{0},{0},{0}}};
-
-
char PcbName[NAME_MAXSIZE], chioce;
-
int Max[PCB_Num][RESOURCE_NUM] = {0}, Allocation[PCB_Num][RESOURCE_NUM] = {0};
-
int Need[PCB_Num][RESOURCE_NUM] = {0}, Available[RESOURCE_NUM] = {0};
-
int Request[RESOURCE_NUM] = {0}, pos = 0;
-
LNode *p = NULL;
-
int i;
-
-
/ 以下补充 //
-
-
//初始化就绪队列
-
Init(&PCBdata);
-
-
//数据输入
-
InputData(&PCBdata);
-
-
while(1){
-
//获取所有PCB中的资源信息
-
GetMatrixData(PCBdata, *Max, *Allocation, *Need, Available);
-
-
//打印当前系统的状态
-
PrintProQueue(PCBdata, Available);
-
-
//接受请求
-
printf("请输入申请资源的进程名，资源A,资源B,资源C申请量（空格隔开）：");
-
scanf("%s", PcbName);
-
for(i = 0; i < RESOURCE_NUM; ++i){
-
scanf("%d", &Request[i]);
-
}
-
-
//获取相应的PCB在链表中的位置
-
GetPos(PCBdata, PcbName, strlen(PcbName), &pos);
-
-
//跑银行家算法，根据返回值的状态判断是否安全，
-
//如果安全，进行正式分配，否则仅仅打印不安全信息
-
if(BankerAlgorithm(*Allocation, Request, pos, *Need, Available)){
-
//正式分配资源
-
GrantSource(PCBdata, Request, pos, Available);
-
-
//分配完成后，打印资源的信息
-
GetMatrixData(PCBdata, *Max, *Allocation, *Need, Available);
-
PrintProQueue(PCBdata, Available);
-
printf("请安任意键继续. . . ");
-
getchar();
-
getchar();
-
} else {
-
printf("不安全，不可分配！\n");
-
}
-
}
-
-
return 0;
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/102896482
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）