操作系统实验二死锁避免之银行家算法的模拟

这篇具有很好参考价值的文章主要介绍了操作系统实验二死锁避免之银行家算法的模拟。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

操作系统实验二死锁避免之银行家算法的模拟

文章目录

死锁

 (1)定义

 (2)死锁产生的原因

 (3)死锁产生的必要条件

 (4)死锁的处理策略

银行家算法

 (1)核心思想

 (2)数据结构

 (3)算法描述

   (4)  安全性检查算法

银行家算法的模拟

(1)数据结构

(2)完整代码

(3)测试


死锁

(1)定义

所谓死锁,是指多个进程因为竞争资源而导致的一种互相循环等待的“僵局”,若无外力作用调整,这些进程都无法向前推进运行。

如下图所示,在十字路口,甲车在等着乙车来让道给自己通行,但乙车司机脾气暴躁就是不让也在等待着甲车让道给自己通行,互相等待,谁都不让道,从而造成一种拥堵的僵局现象,这就是生活中常见的死锁现象。

操作系统实验二死锁避免之银行家算法的模拟

 (2)死锁产生的原因

  • 系统资源的竞争
  • 进程推进的顺序非法
  • 信号量使用不当

(3)死锁产生的必要条件

操作系统实验二死锁避免之银行家算法的模拟

  • 互斥条件:进程要求对所分配的资源进行排他性使用,即在某段时间内某种资源只能被一种进程独自使用
  • 不可剥夺条件:进程在获得资源后不能被其它进程强行夺走,而是由自己主动释放
  • 请求并保持条件:进程已经保持了一种资源,但又提出了新的资源请求,而该资源已经被其它进程所占用,此时请求进程被阻塞,但对自己已经获得的资源保持不放
  • 循环等待条件:存在一种进程资源的循环等待链,链中的每个进程所获得的资源同时被下一个资源所请求。如上图2-15所示

(4)死锁的处理策略

  • 死锁预防:设置某些限制条件,破坏产生死锁4个必要条件中的一个或几个
  • 死锁避免:在资源的动态分配中,用某种方法防止系统进入不安全状态
  • 死锁的检测与解除:无需采用任何的限制性措施,允许进程发生死锁。通过系统的检测机制来检测到死锁,并采取某种措施来解除死锁

而下面所讲的银行家算法就属于死锁避免算法的一种。


银行家算法

(1)核心思想

        银行家算法是最著名的死锁避免算法,其思想是:把操作系统视为银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量,当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源,若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配

(2)数据结构

  • 可用资源向量Available:长度为n的数组表示系统中n类资源的当前可用数目。如果Available[j]=k,表示系统中现有Rj类资源为k个。

  • 最大需求矩阵Max:m×n矩阵定义m个进程对n类资源的最大需求量。如Max[i,j]=k,表示进程Pi运行期间最多需求Rj资源的数目为k个。

  • 已分配资源矩阵Allocation:m×n矩阵定义了每个进程现在已分配到的各类资源的实际数目。如果Allocation [i,j]=k,表示进程Pi当前分到k个Rj类资源。

  •  需求矩阵Need:m×n矩阵表示每个进程还需要的各类资源的数目。如果Need [i, j]=k,表示进程Pi尚需k个Rj类资源才能完成其任务。很显然,Need[i,j]=Max[i,j] - Allocation[i,j],因而,这些数据结构的大小和值会随着时间而改变。

 其中,Need=Max-Allocation

 (3)算法描述

设Requesti表示进程Pi的资源申请向量。如Requesti[j]= k,表示进程Pi动态申请k个Rj类资源。当进程Pi申请资源时,就执行下列动作(试探性分配):

  1. 若Requesti[j]>Need[i,j],产生出错条件,因为进程Pi对资源的请求量已超过其说明的最大数量;否则,转到步骤2。

  2. 如果Requesti[j]>Available[j],则进程Pi必须等待,这是因为系统现在没有可用的资源;否则,转到步骤3。

  3. 如果系统可以给进程Pi分配所请求的资源,则应对有关数据结构进行修改:
            Available[j] = Available[j]-Requesti[j];   (j=1,2,……,n)
            Allocation[i,j] = Allocation[i,j] + Requesti[j];   (i=1,2,……,m)
            Need[i,j] = Need[i,j] - Requesti[j];

  4. 系统执行安全性检查,查看此时系统状态是否安全。如果安全,就给进程Pi 实际分配资源;否则,即系统是不安全的,则Pi等待,作废本次试探性分配,并且把资源分配状态恢复成3之前的情况。

(4)安全性检查算法

        安全性检查算法是银行家算法的核心,在银行家算法的习题中,一般会有某个进程发出一个资源请求向量,我们只需要执行上面银行家算法的前三步,就会得到一个更新后的Allocation和Need矩阵,再按照上例的安全性算法进行判断,此时系统是否处于安全状态,就能直到系统是否能立即满足该进程提出的资源请求。

一般步骤如下:

  1. 设置两个向量:工作向量Work:表示系统可提供给进程继续运行所需要的各类资源数目,长度为n;进程完成标志向量Finish:长度为m,表示各个进程是否能够得到足够的资源并运行完成。两个向量初始化:Work=AvailableFinish[i]=false (i=1,2,...m)

  2. 从进程集合中搜寻满足下列条件的进程(找安全进程序列):Finish[i] ==false且Need[i,j]≤Work[j]。如果找到这样的进程,执行3;否则,则转向步骤4。

  3. 修改数据值:Work[j]=Work[j] + Allocation[i,j](进程Pi释放所占的全部资源);Finish[i]=true;返回步骤2

  4. 安全状态的判定:如果所有进程的Finish[i] ==true都成立(找着安全序列),则系统处于安全状态;否则,系统处于不安全状态


银行家算法的模拟

(1)数据结构

//定义银行家算法的数据结构 
int Available[3]={3,3,2};//系统可用资源 
int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//进程最大资源需求量 
int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系统已经给进程分配的资源 
int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//进程的资源最大需求量 
int Work[3];//安全性检查算法中的工作向量 
int Finish[5]={0,0,0,0,0};//进程执行完成的标志 
int SafeArray[5];//安全序列 
int Request[3];//请求资源向量 

(2)完整代码

/*
	模拟银行家算法,进行死锁的避免 
*/
#include<iostream>
using namespace std;
//定义银行家算法的数据结构 
int Available[3]={3,3,2};//系统可用资源 
int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//进程最大资源需求量 
int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系统已经给进程分配的资源 
int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//进程的资源最大需求量 
int Work[3];//安全性检查算法中的工作向量 
int Finish[5]={0,0,0,0,0};//进程执行完成的标志 
int SafeArray[5];//安全序列 
int Request[3];//请求资源向量 

void ShowSafe(int i);
//打印当前系统资源的分配情况 
void Show(){
    cout<<"T0时刻的系统资源分配情况如下:"<<endl;
    cout<<"进程名\tMax\t\tAllocation\tNeed\t\tAvailable"<<endl;
    for(int i=0;i<5;i++){
        cout<<"P"<<i<<"\t";
        for(int j=0;j<3;j++){
            cout<<Max[i][j]<<" ";
        }
        cout<<"\t\t";
        for(int j=0;j<3;j++){
            cout<<Allocation[i][j]<<" ";
        }
        cout<<"\t\t";
        for(int j=0;j<3;j++){
            cout<<Need[i][j]<<" ";
        }
        cout<<"\t\t";
        if(i==0){
            for(int j=0;j<3;j++){
                cout<<Available[j]<<" ";
            }
        }
        cout<<endl;
    }
}
//安全性检查中判断需求矩阵与工作向量关系 
int NeedLessWork(int i){
    for(int j=0;j<3;j++){
        if(Need[i][j]>Work[j]){
            return 0;
        }
    }
    return 1;
}
//打印安全序列 
void SafeLine(){
    cout<<"当前系统处于安全状态..."<<endl;
    cout<<"其中一个安全序列为:" ;
    for(int i=0;i<5;i++){
    	if(i==4)cout<<"P"<<SafeArray[i];
    	else cout<<"P"<<SafeArray[i]<<"-->";
    }
    cout<<endl;
    for(int i=0;i<5;i++){
        Finish[i]=0;
    }
}

//安全性检查算法 
void IsSafe(int index){
    for(int i=0;i<5;i++){
        int temp=NeedLessWork(i);
        if(Finish[i]==0&&temp){
            SafeArray[index]=i;
            index++;
            Finish[i]=1;
            ShowSafe(i);
            for(int j=0;j<3;j++){
                Work[j]=Work[j]+Allocation[i][j];
            }
            break;
        }
    }
    int mult=1;
    //如果五个标志都为1即都已经完成,则打印安全序列,否则继续执行安全性检查算法 
    for(int k=0;k<5;k++){
        mult*=Finish[k];
    }
    if(mult==0){
        IsSafe(index);
    }else{
        SafeLine();
    }
}
void ShowSafe(int i){
    cout<<"P"<<i<<"\t";
    for(int j=0;j<3;j++){
        cout<<Work[j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Need[i][j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Allocation[i][j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Work[j]+Allocation[i][j]<<" ";
    }
    cout<<"\t\t";
    cout<<Finish[i];
    cout<<endl;

}
void SafeCheck(){
    cout<<"试探着将资源分配给它后,系统安全情况分析如下:"<<endl;
    cout<<"进程\tWork\t\tNeed\t\tAllocation\tWork+Allocation\tFinish"<<endl;
    for(int i=0;i<3;i++){
        Work[i]=Available[i];
    }
    IsSafe(0);
}

int RequestLessNeed(int i){
    for(int j=0;j<3;j++){
        if(Request[j]>Need[i][j]){
            return 0;
        }
    }
    return 1;
}
int RequestLessAvailable(int i){
    for(int j=0;j<3;j++){
        if(Request[j]>Available[j]){
            return 0;
        }
    }
    return 1;
}

//处理进程发出的资源请求 
void RequestResourse(){
    cout<<"请输入发出资源请求的进程:";
    int n;
	cin>>n;
    cout<<"请依次输入所请求的资源数量:";
    for(int i=0;i<3;i++){
        cin>>Request[i];
    }
    if(RequestLessNeed(n)){
    	if(RequestLessAvailable(n)){
    		for(int j=0;j<3;j++){
            Available[j]=Available[j]-Request[j];
            Allocation[n][j]=Allocation[n][j]+Request[j];
            Need[n][j]=Need[n][j]-Request[j];
           }
            SafeCheck();//试探着将资源分配给请求进程,并进行安全性检查 
    	}else{
    		cout<<"P"<<n<<"请求的资源向量已超过系统可用资源向量,请求失败!让其继续等待..."<<endl;
    		cout<<"-------------------------------------------------------------------"<<endl; 
            return ;
    	}
    }else{
    	 cout<<"P"<<n<<"请求的资源向量已超过其最大需求向量,请求失败!让其继续等待..."<<endl;
    	 cout<<"-------------------------------------------------------------------"<<endl; 
         return ;
    }
}


int main(){
    cout<<"*************************银行家算法的模拟*************************"<<endl;
    cout<<"    \t\t\t1.显示当前系统资源情况"<<endl;
    cout<<"    \t\t\t2.进程发出请求向量"<<endl;
    cout<<"    \t\t\t3.退出系统"<<endl;
    cout<<"******************************************************************"<<endl; 
    while(true){
        int choose;
        cout<<"请选择你要执行的操作:";
        cin>>choose;
        switch (choose){
            case 1 :
                Show();//展示当前系统资源分配情况 
                break;
            case 2:
                RequestResourse();//处理进程发出的资源请求 
                break;
            case 3:
                cout<<"已退出系统!"<<endl;
                return 0;
            default:
                cout<<"输入错误,请重新输入!"<<endl;
                continue;
        }
    }
}

(3)测试

操作系统实验二死锁避免之银行家算法的模拟

 综上。

 文章来源地址https://www.toymoban.com/news/detail-428831.html

到了这里,关于操作系统实验二死锁避免之银行家算法的模拟的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [操作系统] 银行家算法

    如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要能找出一个安全序列,系统就是安全状态。 当然,安全序列可能有多个 。 此时你是一位成功的银行家,手里有100亿资金… 此时有三个企业想找你贷款,分别是企业B,企业A,企业T B:“大哥,我最多要借70亿

    2023年04月08日
    浏览(35)
  • 操作系统-银行家算法

    目录 一、银行家算法 二、银行家算法的流程和数据结构 1.数据结构 2.步骤流程 3.安全性算法 三、举例 解题思路 答案 为了避免死锁,出现了银行家算法。 系统必须确保是否有足够的资源分配给一个进程,若有,再计算分配后系统是否会处于不安全状态,若安全,才会分配。

    2024年02月02日
    浏览(44)
  • 【操作系统】银行家算法个人出题例题 (含答案)

    1.银行家算法是代表性的避免死锁的算法,在进程调度中具有重要作用。请结合所学知识回答以下问题:(23分——加长版) (1)银行家算法使用的四个必要的数据结构是:可用资源向量Available,____________,分配矩阵Allocation,需求矩阵Need。(1分) (2)以下是银行家算法具体实现

    2024年02月12日
    浏览(35)
  • 操作系统银行家算法(JAVA/Python/C#/JavaScript/C/C++)代码实现

    银行家算法是一种资源分配和死锁避免算法,它通过模拟所有资源的预定最大可能数量的分配来测试安全性,然后进行“s状态”检查以测试可能的活动,然后决定是否应该允许继续分配。 Banker’s algorithm 之所以叫“银行家算法”,是因为它在银行系统中被用来检查贷款是否

    2024年02月06日
    浏览(74)
  • 操作系统考试复习——第三章 预防死锁 避免死锁

    预防死锁: 就是破坏死锁产生的四个条件之一就行。 0.破坏互斥条件:由于互斥条件是非共享设备所必须的所以,不仅不能改变还需要保证。因此我们主要考虑剩下的三个条件。 1. 破坏 \\\"请求和保持\\\" 条件 请求和保持也就是系统已经请求了一个资源它现在占有这个资源但是它

    2024年02月03日
    浏览(44)
  • 银行家算法的实验报告

    一、实验内容 银行家算法是避免死锁的一种重要方法,本实验要求编写和调试一个简单的银行家算法程序。 1.设计进程对各类资源最大申请表示及初值的确定。 2.设定系统提供资源的初始状况。 3.设定每次某个进程对各类资源的申请表示。 4.编制程序,依据银行家算法

    2023年04月26日
    浏览(45)
  • 银行家算法 源码+实验报告(用了自取)

    XI`AN TECHNOLOGICAL UNIVERSITY 课程设计报告 实验课程名称 操作系统—银行家算法     专    业 :计算机科学与技术          班    级 :                姓    名 :                   学    号 :          实验学时 :                     

    2024年02月09日
    浏览(43)
  • 【操作系统】死锁问题---死锁的消除方法

    本文章将主要解释死锁的消除方法 一、死锁的概念         这是《操作系统》对于死锁的定义: 有并发进程P1,P2,…Pn,它们共享资源R1,R2,…Rm (n0,m0, n=m)。其中,每个Pi(1≤i≤n)拥有资源Rj(1≤j ≤m),直到不再有剩余资源。同时,各Pi又在不释放Rj的前提下要求Rk(k≠j,1≤k ≤m),

    2024年02月15日
    浏览(43)
  • 操作系统——死锁

    死锁是指 多个进程因为竞争资源 而造成的一种僵局( 互相等待 ),若无外力作用,这些进程都将无法推进。                          1.系统资源的竞争                          2.进程推进顺序非法           进程申请的资源为临界资源            进程已申请的资

    2024年02月02日
    浏览(38)
  • 操作系统之死锁详解

    本文已收录于专栏 《自考》   最近一直在做操作系统的测试题,在做题的过程中发现有很多地方涉及到了关于死锁的知识点。今天就回归课本来自己琢磨一下死锁。下面就把我琢磨的成果分享给大家。 并发编程:死锁是在并发环境下发生的,因此了解并发编程的基本概念

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包