模拟银行家算法

心已赠人 2023-05-29 05:11 57阅读 0赞

# 介绍 #

![20191104145857576.png][]

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;
    }

[20191104145857576.png]: https://img-blog.csdnimg.cn/20191104145857576.png