代码编织梦想

目录

一、银行家算法概述

二、银行家算法需要的数组结构

三、算法概述

1.安全性算法

2.银行家算法

四、代码实现

五、实验结果验证


一、银行家算法概述

银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

二、银行家算法需要的数组结构

1)可利用资源向量Available:这是一个含有m个元素的数组,其中的每一个元素代表一类可用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j] = K,则表示系统中现有Rj类资源K个。

2)最大需求矩阵Max:这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j] = K,则表示进程i需要Rj类资源的最大数目为K。

3)分配矩阵Allocation:这也是一个n*m的矩阵,它定义了系统中的每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j] = K,则表示进程i当前已分得Rj类资源的数目为K。

4)需求矩阵Need:这也是一个n*m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K,则表示进程i还需要Rj类资源K个方能完成其任务。

其中三个矩阵间存在下述关系:

Need[i,j] = Max[i,j] - allocation[i,j]

三、算法概述

1.安全性算法

系统所执行的安全性算法可描述如下:

(1)设置两个向量:
        ① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work=Available;② Finish: 它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=false; 当有足够资源分配给进程时, 再令Finish[i]=true。

(2)从进程集合中找到一个能满足下述条件的进程:
        ① Finish[i]=false;
        ② Need[i,j]≤Work[j]; 若找到, 执行步骤3);否则,执行步骤4)。

(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
        Work[j]=Work[i]+Allocation[i,j];
        Finish[i]=true;
        go to step 2;

(4)如果所有进程的Finish[i]=true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。

2.银行家算法

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

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

(2) 若 Requset_i[j] ≤ Available[j],转向步骤(3),否则表示尚无足够资源,Pi必须等待。

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

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

四、代码实现

#include<iostream>
using namespace std;

const int p=5;//进程数
const int r=4;//资源种类

int num = 1;//需要分配资源的进程序号

void init_request(int request[r])
{
    //初始化request矩阵
    cout<<"Input the number of request:"<<endl;
    cin>>num;
    num-=1;//下标减1
    cout<<"Input the request vector:"<<endl;
    for(int i=0;i<r;i++)
        cin>>request[i];
}

void init_matrix(int maximum[p][r],int allocation[p][r],int need[p][r],int available[r],int request[r])
{
    //初始化函数
    cout<<"Input the Allocation matrix:"<<endl;
    for(int i=0;i<p;i++)
        for(int j=0;j<r;j++)
            cin>>allocation[i][j];
    cout<<"Input the Need matrix:"<<endl;
    for(int i=0;i<p;i++)
        for(int j=0;j<r;j++)
            cin>>need[i][j];
    //cout<<"Input the Max matrix:"<<endl;
    //Max矩阵可以由Need和Allocation矩阵推导得出
    //Max[i,j]= Need[i,j]+Allocation[i,j]
    for(int i=0;i<p;i++)
        for(int j=0;j<r;j++)
            maximum[i][j]=need[i][j]+allocation[i][j];
    cout<<"Input the available vector:"<<endl;
    for(int i=0;i<r;i++)
        cin>>available[i];
}

void output_func(int allocation[p][r],int need[p][r],int available[r])
{
    //输出函数
    cout<<endl<<"     "<<"Allocation"<<"     Need"<<"        Available"<<endl;
    for(int i=0;i<p;i++)
    {
        cout<<"P"<<i+1<<"   :";
        for(int j=0;j<r;j++)
        {
            cout<<allocation[i][j]<<' ';

        }
        cout<<"     ";
        for(int j=0;j<r;j++)
            cout<<need[i][j]<<' ';
        if(i==0)
        {
            cout<<"     ";
            for(int k=0;k<r;k++)
                cout<<available[k]<<' ';
        }
        cout<<endl;
    }
    cout<<endl;

}

bool compare(int need[],int work[])
{
    bool flg = 1;
    for(int i=0;i<r;i++)
    {
        //检查是否有大于的情况存在
        if(need[i]>work[i])
        {
            flg=0;
            break;
        }
    }
    return flg;
}

int check_security(int allocation[p][r],int need[p][r],int available[r])
{
    //安全性检查函数
    int finish[p] = {0};//初始化finish向量
    int work[r];  //拷贝available
    int lis[p];//用来记录安全时的队列
    int cnt=0;
    for(int i=0;i<r;i++)
        work[i] = available[i];//初始化work向量
    //序列分配
    //循环p次
    for(int m=0;m<p;m++)
    {
        for(int i=0;i<p;i++)
        {
            //如果当前进程执行完成,跳过
            if(finish[i] == 1)
                continue;
            //找到finish[i] = false
            else{
                //如果Need[i,j]<=Work[j]
                if(compare(need[i],work))
                {
                    for(int j=0;j<r;j++)
                        work[j]+=allocation[i][j];
                    finish[i] = 1;
                    lis[cnt++] = i+1;//将该状态放入安全状态队列中
                    break;
                }
            }
        }
    }
    int flag=1;
    for(int i=0;i<r;i++)
    {
        if(finish[i]==0)
        {
            flag = 0;
            break; //如果存在F的进程,表明系统处于不安全状态
        }
        else
            continue;
    }
    if(flag)
    {
         cout<<"系统处于安全状态!"<<endl;
         cout<<"安全序列为:";
         for(int i=0;i<p;i++)
            cout<<lis[i]<<' ';
         cout<<endl;
    }
    else cout<<"系统处于不安全状态!"<<endl;
    return flag;

}

void banker(int allocation[p][r],int need[p][r],int available[r],int request[r],int n)
{
    if(!compare(request,need[n]))
    {
        //如果存在Requesti[j]>Need[i][j],认为出错
        cout<<"出错!所需资源已超过所宣布的最大值!"<<endl;
        return ;
    }
    else{
        //银行家算法(1)没有出错
        if(!compare(request,available))
        {
            //如果存在Requesti[j]>Available[j],认为出错
            cout<<"尚无足够资源,必须等待!"<<endl;
            return ;
        }
        else{
            for(int j=0;j<r;j++)
            {
                available[j]-=request[j];
                allocation[n][j]+=request[j];
                need[n][j]-=request[j];
            }
            if(check_security(allocation,need,available))
            {
                cout<<"安全!将资源正式分配"<<endl;
            }
            else
            {
                cout<<"不安全!资源分配作废!恢复以前状态"<<endl;
                for(int j=0;j<r;j++)
                {
                    need[n][j]+=request[j];
                    allocation[n][j]-=request[j];
                    available[j]+=request[j];
                }
            }
        }
    }
    output_func(allocation,need,available);

}

int main()
{
    int maximum[p][r],allocation[p][r],need[p][r];
    int available[r],request[r];
    init_matrix(maximum,allocation,need,available,request);
    cout<<endl<<"检查T0时刻系统是否处于安全状态..."<<endl;
    check_security(allocation,need,available);
    int flag = 1;
    while(flag)
    {
        cout<<endl<<"对请求资源进行银行家算法检查..."<<endl;
        init_request(request);//初始化request矩阵
        banker(allocation,need,available,request,num);
        cout<<"是否继续输入?(输入0退出):";
        cin>>flag;
    }

    return 0;
}
/*测试数据
0 0 3 2
1 0 0 0
1 3 5 4
0 3 3 2
0 0 1 4
0 0 1 2
1 7 5 0
2 3 5 6
0 6 5 2
1 6 5 6
1 6 2 2
*/

五、实验结果验证

1.能安全分配的情况


 

 

2.分配不安全情况(注意一定要恢复原来的状态)

 3.需要的资源超过自己需要的最大值

 4.尚无足够资源,需等待分配

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_58136789/article/details/128000571

银行家算法c++实现_lingpy的博客-爱代码爱编程

网上有很多银行家算法的源代码,下面是本人自己写的,基本算法模型参考教材。 介绍 银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉(Edsge

C++实现银行家算法-爱代码爱编程

目录   1.需求分析 2.概要设计 2.1算法数据结构 2.2银行家算法 2.3安全性算法 3.C++代码实现 4.测试分析 1.需求分析 银行家算法是最具代表性的避免死锁的算法,由Dijkstra提出。该算法原本是为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。在OS中也可以用他来实现避免死锁。

C/C++实现银行家算法-爱代码爱编程

银行家算法C/C++实现 概念死锁条件安全序列安全状态不安全状态数据结构关系过程图例子代码实现DFS安全序列思路问题代码全部代码参考 概念 银行家算法是一种用来避免操作系统死锁出现的有效算法,所以在引入银行家算法的解释之前,有必要简单介绍下死锁的概念。 死锁 是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻

银行家算法C++代码实现-爱代码爱编程

一、算法介绍 ​ 银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。 ​ 多个进程动态地共享系统的资源可能会产生死锁现象。死锁的产生,必须同时满足四个条件,第一个是互斥

银行家算法c++实现-爱代码爱编程

银行家算法详述: 设 Request;是进程Pi的请求向量,如果 Requesti[j] = K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检査:   (1) 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。   (2) 如果 Request

操作系统——银行家算法c++语言实现_neymessi_jr的博客-爱代码爱编程

问题描述: 设计程序模拟预防进程死锁的银行家算法的工作过程。假设系统中有n个进程P1, … ,Pn,有m类可分配的资源R1, … ,Rm,在T0时刻,进程Pi分配到的j类资源为Allocationij个,它还需要j类资源Need ij个,系统目前剩余j类资源Workj个,现采用银行家算法进行进程资源分配预防死锁的发生。 程序要求: 1)判断当前状态是

c语言百日千题系列之《忘情水题》第一日_会敲代码的史蒂夫.的博客-爱代码爱编程

目录 绪论 1.最大数位置 2.与指定数字相同的数的个数 3.蓝桥杯2013年第四届真题-核桃的数量 4.求所给范围内水仙花数并排列 5.最大值和最小值的差 6.计算书费 7.角谷猜想 8. 最高的分数 9.年龄与疾病 10.-百钱百鸡问题 绪论       本文是C语言百日千题系列《忘情水题》的第一篇专栏文章,主要为初学

2022大厂面试秘籍java岗:中间件+算法+http+线程+虚拟机+分布式_啊码的博客-爱代码爱编程

前言 很多朋友对面试不够了解,不知道如何准备,对面试环节的设置以及目的不够了解,因此成功率不高。通常情况下校招生面试的成功率低于1%,而社招的面试成功率也低于5%,所以对于候选人一定要知道设立面试的初衷以及每个环节的意义,

李宏毅:life long learning_bulibuli蛋的博客-爱代码爱编程

Life Long Learing 也是continual Learning,也是incremental learning 目录 Life-Long Learning  vs  Transfer Learning Evaluation Research Directions Selective Synaptic Plasticity——Regul

期末复习 c语言再学习_aniyaaaaa_的博客-爱代码爱编程

作者:@小萌新 专栏:@C语言复习 作者简介: 大二学生 希望能和大家一起进步! 本篇博客简介:回顾之前的分支循环以及一些题目博客 @[TOC](这里写目录标题 分支循环选择switch caseget

【csdn竞赛】第十期解题报告_icehomegre的博客-爱代码爱编程

文章目录 感想关于自己关于平台 第一题 (难度:入门)题目描述100分做法 第二题 (难度:简单)题目描述100分做法 第三题 (难度:中等/困难)题目描述100分做法1(对应中等)10

c++类与对象(一)-爱代码爱编程

目录 一、面向过程和面向对象认识 二、类的引入 三、类的定义 类的两种定义方式: 四、类的访问限定符及封装 4.1 访问限定符 4.2 封装 五、类的作用域 六、类的实例化 七、类对象模型 7.1 如何计算类对象的大小​​​​​ 7.2 类对象的存储方式 7.3 结构体内存对齐规则 八、this指针 8.1 this指针的引出