操作系统实验2--银行家算法模拟实现

问题描述

利用 C 语言设计与实现银行家算法，构建计算机系统资源的模拟管理和处理场景并对自己的银行家算法实现方案加以测试验证。

实验要求

基于 C语言的银行家算法的设计与实现
计算机系统资源的模拟管理和处理场景的构建（初始化操作包括系统各类资源配备情况、一组并发进程及相应资源最大需求明细，进程申请资源操作需要指定进程及其对所需各类资源的申请数量，进程释放资源操作需要指定进程及其对当前所占用各类资源的释放数量）
算法原型应能正确处理进程申请/释放资源的各种操作请求
针对银行家算法原型开展基于计算机系统资源管理的完备的测试验证

项目结构

宏定义、全局变量和结构体定义

#define TRUE 1
#define FALSE 0
#define ERR -1
#define N 5
#define SUCCESS 0

typedef struct Resource
{
    int A;
    int B;
    int C;
}RES;

typedef struct Request
{
    int id;
    RES res;
}REQ;

RES Available,Work,Max[N],Allocation[N]={{0,0,0}},Need[N];
REQ Request;
int Finish[N];

N是进程数，TRUE FALSE ERR SUCCESS是标志位，Resource结构体存储资源，Request结构体存储请求，Available Work Max[N] Allocation[N] Need[N] Request Finish对应银行家算法里的各个部分。

函数一览

void init();
void run();
int isAllFinish(int* finish);
int cmpReqNeed();
int cmpReqAvailable();
int preAllocate();
int safeCheck();
int isASmallerB(RES A,RES B);
RES add(RES A,RES B);
RES minus(RES A,RES B);
void printLog();

详细设计

初始化

void init()
{
    printf("输入总资源数(A B C):\n");
    scanf("%d%d%d",&Available.A,&Available.B,&Available.C);
    printf("依次输入%d个进程所需最大资源(A B C):\n",N);
    for(int i=0;i<N;i++)
    {
        scanf("%d%d%d",&Max[i].A,&Max[i].B,&Max[i].C);
        Need[i]=Max[i];
    }
    return;
}

获取用户输入的总资源数和每个进程所需最大资源数，并且开始时每个Allocation 资源都是0，所以Need 赋值为 Max。

结构体工具函数

RES add(RES A,RES B)
{
    RES temp;
    temp.A=A.A+B.A;
    temp.B=A.B+B.B;
    temp.C=A.C+B.C;
    return temp;
}

RES minus(RES A,RES B)
{
    RES temp;
    temp.A=A.A-B.A;
    temp.B=A.B-B.B;
    temp.C=A.C-B.C;
    return temp;
}

int isASmallerB(RES A,RES B)
{
    if(A.A<=B.A&&A.B<=B.B&&A.C<=B.C)
    {
        return TRUE;
    }
    return FALSE;
}

因为C语言没有运算符重载，所以自定义加、减、小于等于函数方便阅读和编写

日志输出

void printLog()
{
    printf("***Log Start***\n");
    printf("系统剩余资源:\n%d %d %d\n",Available.A,Available.B,Available.C);
    printf("线程需求资源:\n");
    for(int i=0;i<N;i++)
    {
        printf("%d %d %d\n",Need[i].A,Need[i].B,Need[i].C);
    }
    printf("完成情况:\n");
    for(int i=0;i<N;i++)
    {
        printf("%d ",Finish[i]);
    }
    printf("\n***Log End***\n");
}

银行家算法主体

void run()
{
    while (!isAllFinish(Finish))
    {
        printLog();
        printf("---------------------------------------\n输入资源申请(id A B C):\n");
        scanf("%d%d%d%d",&Request.id,&Request.res.A,&Request.res.B,&Request.res.C);
        if(cmpReqNeed()!=ERR&&cmpReqAvailable()!=ERR)
        {
            if(preAllocate()!=ERR)
            {
                if(Need[Request.id].A==0&&Need[Request.id].B==0&&Need[Request.id].C==0)
                {
                    Available=add(Available,Allocation[Request.id]);
                    Finish[Request.id]=TRUE;
                }
            }
        }
    }
}

通过isAllFinish 函数判断是否所有进程已经完成，接收用户输入以模拟进程对资源的请求，通过cmpReqNeed 和cmpReqAvailable 检测请求是否超出，如果不超出，使用 preAllocate 进行预分配，如果预分配安全且执行完成，释放资源。

预分配

int preAllocate()
{
    RES tempAvailable=Available,tempAllocation=Allocation[Request.id],tempNeed=Need[Request.id];
    Available=minus(Available,Request.res);
    Allocation[Request.id]=add(Allocation[Request.id],Request.res);
    Need[Request.id]=minus(Need[Request.id],Request.res);
    if(safeCheck()==ERR)
    {
        Available=tempAvailable;
        Allocation[Request.id]=tempAllocation;
        Need[Request.id]=tempNeed;
        return ERR;
    }
    return SUCCESS;
}

首先使用temp开头的几个变量将原始资源余量等信息暂存，然后试着去分配，调用safeCheck检测安全性，如果不安全，则撤销预分配。

安全性检测

int safeCheck()
{
    int tempFinish[N];
    int safeList[N],safeNum=0;
    int flag;
    for(int i=0;i<N;i++)
    {
        tempFinish[i]=Finish[i];
    }
    Work=Available;
    while (isAllFinish(tempFinish)!=TRUE)
    {
        flag=FALSE;
        for(int i=0;i<N;i++)
        {
            if(tempFinish[i]==FALSE&&isASmallerB(Need[i],Work))
            {
                Work=add(Work,Allocation[i]);
                tempFinish[i]=TRUE;
                safeList[safeNum++]=i;
                flag=TRUE;
            }
        }
    }
    if(flag==FALSE)
    {
        printf("不安全\n");
        return ERR;
    }
    else
    {
        printf("安全序列:\n");
        for(int i=0;i<safeNum;i++)
        {
            printf("线程%d ",safeList[i]);
        }
        printf("\n");
        return SUCCESS;
    }
}