操作系统作业之银行家算法(c语言实现)

操作系统作业之银行家算法(c语言实现)银行家算法分析:银行家算法数据结构:进程数processNum资源类数resourceNum系统剩余可利用资源Available,为一个含有m个元素的数组;最大需求矩阵Max,为一个processNumresourceNum数组进程当前已分配资源数Allocation,为一个processNumresourceNum数组进程尚需要的资源数Need,为一个processNum*re…

大家好,又见面了,我是你们的朋友全栈君。

银行家算法分析:

银行家算法数据结构:

进程数 processNum
资源类数 resourceNum
系统剩余可利用资源Available,为一个含有m个元素的数组;
最大需求矩阵Max,为一个processNum*resourceNum数组
进程当前已分配资源数Allocation,为一个processNum*resourceNum数组
进程尚需要的资源数Need,为一个processNum*resourceNum数组
所以有关系如下: Need[i,j] + Allocation[i,j] = Max[i,j]

算法大致模块含:安全性检测模块,数据初始化模块,数据显示模块;
其中安全性检测为主要模块:

1.系统对进程轮流进行检查,找到可以尝试(意味着请求失败还需要还回)分配资源的进程:

此时需要一个新的数据,**Request[j]**记录当前进程的资源申请向量;
条件如下:

Request[j] + Allocation[i,j] <= Max[i,j];
Request[j] <= Available[j];

如果满足条件则对当前进程开始进行资源分配,更新当前数据结构中的值

2.检测当前系统是否会处于安全状态,是则记录安全序列

此时需要一个一维数组work记录等同于Available
(因为当前暂且属于尝试分配状态,不能改变系统资源状态,否则最后如果判断进程死锁的话,系统资源状态不好恢复)

bool类型Finish[processNum]:表示进程是否有足够资源运行完成
(想要可以运行完成,必定要满足Need[i,j]<Available[j]

如果最后判断进程死锁,则需要把尝试分配阶段的资源归还!

尚待改进:
1.没有数据初始化模块,数据在写代码时就初始化好了,可以写一个独立模块读取初始资源状态;

题目:系统共有五个进程P0,P1,P2,P3,P4,三类资源A,B,C;资源数分别为10,5,7;初始时刻资源分配状态如下(见代码):

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //bool类型数据头函数
#define processNum 5 //五个进程
#define resourceNum 3 //三类资源
//初始状态
int p;
int work[resourceNum];
int Request[resourceNum];
bool Finish[processNum];
int Available[resourceNum]={3,3,2};
int Max[processNum][resourceNum]={7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};
int Need[processNum][resourceNum]={7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};
int Allocation[processNum][3]={0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};
void print1()
{
    int i,j;
    printf("系统剩余资源数:");
    for(j = 0;j < resourceNum;j++)
        printf("%d ",Available[j]);
        printf("\n");
    printf("============当前资源分配状态=========\n");
    printf("process=== Max =====Allocation=====  Need\n");
    for(i = 0;i < processNum;i++){
        printf("p%d        ",i);
        for(j = 0;j < resourceNum;j++)
            printf("%d ",Max[i][j]);
            printf("       ");
        for(j = 0;j < resourceNum;j++)
            printf("%d ",Allocation[i][j]);
            printf("       ");
        for(j = 0;j < resourceNum;j++)
            printf("%d ",Need[i][j]);
            printf("       \n");
    }
}
void print2(int i)
{
    int j;
    printf("p%d        ",i);
    for(j = 0;j < resourceNum;j++)
        printf("%d ",work[j]);
        printf("       ");
    for(j = 0;j < resourceNum;j++)
        printf("%d ",Need[i][j]);
        printf("       ");
    for(j = 0;j < resourceNum;j++)
        printf("%d ",Allocation[i][j]);
        printf("       ");
    for(j = 0;j < resourceNum;j++)
        printf("%d ",Allocation[i][j]+work[j]);
        printf("       ");
    for(j = 0;j < resourceNum;j++)
        if(!Finish[i])
            break;
    if(j == resourceNum)
        printf("true");
    else
        printf("false");
    printf("       \n");
}
//进程不安全,回收预分配的资源
void recycle()
{
    int j;
    for(j = 0;j < resourceNum;j++){
        Need[p][j] += Request[j];
        Available[j] += Request[j];
        Allocation[p][j] -= Request[j];
    }
    printf("系统进程资源状态不改变!\n");
}
void Test_safety()
{
    int i,j;
    int finish = 0,Done = 0; //Done一轮遍历下完成的,finish总共完成的
    int safeseries[processNum] = {-1,-1,-1,-1,-1};
    //初始化
    for(i = 0;i < processNum;i++)
        Finish[i] = false;
    for(j = 0;j < resourceNum;j++)
        work[j] = Available[j]; //初始值等于Available;
    // 查找未完成进程,且当前进程尚需资源不大于系统剩余资源;
    i = 0;
    while(finish != processNum){
        j = 0;
        if(Finish[i] == false)
            for(j = 0;j < resourceNum;j++)
                if(Need[i][j] > work[j]) break;

        if(j == resourceNum){
            Finish[i] = true;
            print2(i);
            safeseries[finish++] = i; //记录下安全序列
            for(j = 0;j < resourceNum;j++)
                work[j] += Allocation[i][j];
        }
        i++; //下一个进程
        //一轮遍历后,判断是否还有可分配进程
        if(i >= processNum){
            i = i % processNum;
            if(Done == finish) //判断本轮完成进程是否等于上一轮,是则代表没有可执行进程
                break;
            else Done = finish; //否则将本轮完成进程数赋值给Done
        }
    }
    if(finish == processNum){
        printf("进程P%d请求通过,此时安全序列为:",p);
        for(i = 0;i < processNum;i++)
            printf("p%d ",safeseries[i]);
        printf("\n");
        print1(); //打印出此刻系统资源分配状态
    }
    else{
        recycle();
        printf("进程死锁,进程P%d请求无法通过!\n",p);
        print1();
    }
}
void judge_assign()
{
    int j;
    for(j = 0;j < resourceNum;j++){
        //当前请求资源加上已分配资源不能大于最大需求资源;
        if(Request[j] + Allocation[p][j] > Max[p][j]){
            printf("当前请求资源+已分配资源>最大需求资源:无法满足!错误!\n");
            break;
        }
        //当前请求资源不能大于系统现有资源;
        if(Request[j] > Available[j]){
            printf("当前请求资源>系统现有资源:无法满足!错误!\n");
            break;
        }
    }
    if(j == resourceNum){
        //尝试分配资源
        for(j = 0;j < resourceNum;j++){
            Need[p][j] -= Request[j];
            Available[j] -= Request[j];
            Allocation[p][j] += Request[j];
        }
        //检查此时系统的安全性
        printf("===========安全序列===========\n");
        printf("process=== Work===== Need =====Allocation=====work+allocation==finish\n");
        Test_safety();

    }
}
int main()
{
    int i;
    print1();
    printf("===========此时安全序列===========\n");
    printf("process=== Work===== Need =====Allocation=====work+allocation==finish\n");
    Test_safety();
    while(1){
        printf("存在进程0,1,2,3,4,资源类别0,1,2\n请依次输入请求资源的进程和进程请求的A,B,C类资源数\n例如:1 0 0 1 \n");
        scanf("%d",&p);
        for(i = 0;i < resourceNum;i++)
            scanf("%d",&Request[i]);
        //尝试分配资源给进程
        judge_assign();
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/163231.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号