操作系统:银行家算法(C语言代码)详解

简介: 操作系统:银行家算法(C语言代码)详解

银行家算法流程图:

20210407214238738.png

银行家算法自然语言描述:设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:


(1)如果Requesti[j]≤  Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。


(2)如果Requesti[j]≤  Available[j],便转向步骤3;否则,表示尚无足够资源,Pi须等待。


(3)系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:Available[j]=  Available[j]-  Requesti[j];  Allocation[i,j]=  Allocation[i,j]+  Requesti[j];  Need[i,j]=  Need[i,j]-  Requesti[j];


(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。


实例:


假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况下图所示。输入M资源总数量、Max矩阵和Allocation矩阵显示初始状态表(1)判断T0时刻是否安全?存在一个安全序列<P1,P3,P0,P2,P4>


20210407214544726.png

20210407214557564.png

输入M资源总数量、Max矩阵和Allocation矩阵


20210407214618687.png


显示初始状态表

1.判断T0时刻是否安全?

20210407214729326.png


存在一个安全序列<P1,P3,P0,P2,P4>

2. P1请求资源:P1发出请求向量Request1(1,0,2),调用银行家算法检查是否能够分配?

2021040721482795.png

输入

20210407214845686.png

存在一个安全序列<P1,P3,P4,P2,P0>,显示新的状态表。

3.P4请求资源:P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查:


20210407214946459.png

输入

2021040721500154.png

① Request4(3, 3, 0)≤Need4(4, 3, 1);

② Request4(3, 3, 0) >Available(2, 3, 0),让P4堵塞等待。状态表没有变化

4.P0请求资源:P0发出请求向量Requst0(0,2,0),系统按银行家算法进行检查:


20210407215033845.png


输入

① Request0(0, 2, 0)≤Need0(7, 4, 3);

② Request0(0, 2, 0)≤Available(2, 3, 0);系统暂时先假定可为P0分配资源,并修改有关数据,如下图所示。

20210407215115932.png

可用资源Available(2,1,0)不能满足任何进程的需求,进入不安全状态。此时系统不分配资源给P0。

20210407215140989.png

输出:找不到安全序列,状态表没有变化

5.若P0发出请求向量Requst0(0,1,0),系统是否将资源分配给它?


20210407215213625.png

输入

20210407215231266.png

存在一个安全序列<P0,P1,P2,P3,P4>,显示新的状态表


程序代码:

#include <malloc.h> 
#include <stdio.h> 
#include <string.h> 
#include <windows.h>
#define M 3 
#define N 5
int Resource[M];
int Max[N][M];
int Allocation[N][M];
int Need[N][M];
int Available[M];
int Work[M];
int Finish[N]; 
int List[N];    //存放安全序列的下标序列 
void initial()   
//创建初始状态:先输入 Resource、Max和 Allocation,再计算出 Need、Available。   
{
    int i,j;
    printf("Resource--输入M种资源的总数量:\n");
    for(i=0;i<M;i++)
    {
        scanf("%d",&Resource[i]);
        Available[i]=Resource[i];
    }
    printf("Max--输入N个进程分别对M种资源的最大需求量:\n");
    for(j=0;j<N;j++)
        for(i=0;i<M;i++)
            scanf("%d",&Max[j][i]);
    printf("Allocation--输入N个进程获得M种资源的数量:\n");
    for(j=0;j<N;j++)
        for(i=0;i<M;i++)
            scanf("%d",&Allocation[j][i]);
    /****************************************/
    for(j=0;j<N;j++)
        for(i=0;i<M;i++)
            Need[j][i]=Max[j][i]-Allocation[j][i];
    for(j=0;j<M;j++)
        for(i=0;i<N;i++)
            Available[j]=Available[j]-Allocation[i][j];
} 
void printState()   
//输出当前的状态表|Process     |Max         |Allocation  |Need         |Available   | 
{
    int i;
    printf("状态表:\n|Process     |Max         |Allocation  |Need        |Available   | \n");
    for(i=0;i<N;i++)
    {
        if(i==0)
            printf("|P%-11d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|\n",i,Max[i][0],Max[i][1],Max[i][2],Allocation[i][0],Allocation[i][1],Allocation[i][2],Need[i][0],Need[i][1],Need[i][2],Available[0],Available[1],Available[2]);
        else
            printf("|P%-11d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|            |\n",i,Max[i][0],Max[i][1],Max[i][2],Allocation[i][0],Allocation[i][1],Allocation[i][2],Need[i][0],Need[i][1],Need[i][2]);
    }
} 
int isfinish()   
//返回同时满足两个条件{①Finish[i]=false;  ②Need[i][j]≤Work[j]}的进程下标 i(修改Finish[i]=true),否则返回-1。 
{
    int i,j,count;
    for(i=0;i<N;i++)
    {
        for(j=0,count=0;j<M;j++)
            if(Finish[i]==0&&Need[i][j]<=Work[j])
            {
                count++;
            }
        if(count==3)
        {
            for(j=0;j<M;j++)
                Work[j]+=Allocation[i][j];
            Finish[i]=1;
            return i;
        }
    }
    return -1;
} 
int issafe()   
//判定当前状态是否为安全状态 (返回 true 或 false),把安全序列的下标放入 List[N]数组。 
{
    int i,a,count=0;
    for(i=0;i<M;i++)
        Work[i]=Available[i];
    for(i=0;i<N;i++)
        Finish[i]=0;
    for(i=0;i<N;i++)
    {
        a=isfinish();
        if(a!=-1)
        {
            List[i]=a;
            count++;
        }
    }
    if(count==5)
        return 1;
    else
        return 0;
} 
void printList( )   
//输出安全序列表|Process |Work  |Need   |Allocation  |Work+Alloc   |Finish  | 
{
    int i,j;
    printf("\n安全序列表如下:\n|Process     |Work        |Need        |Allocation  |Work+Alloc  |Finish      |\n");
    for(j=0;j<M;j++)
    {
        Work[j]=Available[j];
    }
    for(i=0;i<N;i++)
    {
        printf("|P%-11d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|%4d%4d%4d|true\n",List[i],Work[0],Work[1],Work[2],Need[List[i]][0],Need[List[i]][1],Need[List[i]][2],Allocation[List[i]][0],Allocation[List[i]][1],Allocation[List[i]][2],Work[0]+Allocation[List[i]][0],Work[1]+Allocation[List[i]][1],Work[2]+Allocation[List[i]][2]);
        for(j=0;j<M;j++)
            Work[j]+=Allocation[List[i]][j];
    }
} 
void reqresource(int i, int Request[M])   
//表示第 i个进程请求 M类资源 request[M] 
{ 
    int flag,count1,count2; 
    int j; 
    //Step1:  判断条件 Request[j]≤Need[i][j] 
    for(j=0,count1=0;j<M;j++)
        if(Request[j]<=Need[i][j])
            count1++;
    //Step2:  判断条件 Request[j]≤Available[j]
    for(j=0,count2=0;j<M;j++)
        if(Request[j]<=Available[j])
            count2++;
    if(count2!=3)
        printf("\n尚无足够的资源,第%d个进程堵塞。\n",i);  
    //Step3:  预先分配 
    if(count2==3&&count1==3)
    {
        for(j=0;j<M;j++)
        {
            Available[j]=Available[j]-Request[j];
            Allocation[i][j]=Allocation[i][j]+Request[j];
            Need[i][j]=Need[i][j]-Request[j];
        }
        if(issafe()==0) 
        { 
            printf("\n不存在安全序列,不是安全状态。\n"); 
            for(j=0;j<M;j++)
            {
                Available[j]=Available[j]+Request[j];
                Allocation[i][j]=Allocation[i][j]-Request[j];
                Need[i][j]=Need[i][j]+Request[j];
            }
        } 
        else 
        { 
            printf("\n是安全序列分配成功!\n"); 
            printList();
        }   
    }
    //Step4:检测是否为安全状态 
    //填补程序 
} 
void main() 
{   
    int reqid=-1,j,req[M]; 
    initial(); 
    printState(); 
    if(issafe()==0) 
    { 
        printf("Initial state is unsafe!\n"); 
    } 
    else 
    { 
        printf("\nInitial state is safe!\n"); 
        printList(); 
        printf("Input the id of request process:"); 
        scanf("%d",&reqid); 
        while(reqid>=0 && reqid<N)   //输入进程 id是否合法 
        { 
            printf("Input request resources:");  
            for(j=0;j<M;j++) 
            { 
                scanf("%d",&req[j]); 
            } 
            reqresource(reqid, req); 
            printState(); 
            printf("Input the id of request process:"); 
            scanf("%d",&reqid); 
        } 
    } 
}


目录
相关文章
|
11天前
|
Unix 编译器 Shell
[oeasy]python0033_先有操作系统还是先有编程语言_c语言是怎么来的
本文回顾了计算机语言与操作系统的起源,探讨了早期 Unix 操作系统及其与 C 语言的相互促进发展。Unix 最初用汇编语言编写,运行在 PDP-7 上,后来 Thompson 和 Ritchie 开发了 C 语言及编译器,使 Unix 重写并成功编译。1974 年 Ritchie 发表论文,Unix 开始被学术界关注,并逐渐普及。伯克利分校也在此过程中发挥了重要作用,推动了 Unix 和 C 语言的广泛传播。
34 9
[oeasy]python0033_先有操作系统还是先有编程语言_c语言是怎么来的
|
10天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
|
10天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
|
10天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
|
10天前
|
存储 算法 C语言
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
这份二叉排序树习题集涵盖了二叉搜索树(BST)的基本操作,包括构建、查找、删除等核心功能。通过多个具体示例,如构建BST、查找节点所在层数、删除特定节点及查找小于某个关键字的所有节点等,帮助读者深入理解二叉排序树的工作原理与应用技巧。此外,还介绍了如何将一棵二叉树分解为两棵满足特定条件的BST,以及删除所有关键字小于指定值的节点等高级操作。每个题目均配有详细解释与代码实现,便于学习与实践。
|
10天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现,帮助读者理解和掌握二叉树的基本操作与应用。
|
10天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
10天前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
12天前
|
机器学习/深度学习 存储 算法
经典算法代码
这段代码展示了多个经典算法,包括:穷举法解决“百钱买百鸡”问题;递推法计算“猴子吃桃”问题;迭代法求解斐波那契数列及折纸高度超越珠峰的问题。同时,还提供了希尔排序算法实现及披萨票务订购系统和汉诺塔问题的链表存储解决方案。每部分通过具体案例解释了算法的应用场景与实现方法。
17 3
|
10天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。

热门文章

最新文章