银行家算法——软考探究(四)

2024-05-16 11:18
文章标签 算法 软考 探究 银行家

本文主要是介绍银行家算法——软考探究(四),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

    著名的银行家算法,最早是由Dijkstra提出来的。它是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。

    银行家算法最重要的就是判断是可用资源和仍需资源之间的关系,如果可用资源数大于人需资源数,那么我们认为这个进程就是可以执行的,也是安全的,反之,便是不安全的。所以重中之重的是找到各种资源数。

对进程的判断遵循以下步骤:

1.计算系统开始时所有的资源数,即开始的可用资源数;

2.在仍需资源数和可用资源数中作比较,找到符合条件的进程,最后修改进程执行完毕时系统的可用资源数;

3.继续比较剩余进程和可用资源数,找到下边可以执行的进程;

4.依次类推;


    下面那一个例子来解释这些晦涩的文字,一定要认真去看哦O(∩_∩)O~

【例】假设系统中有3类互斥资源R1、R2、R3,可用资源分别是9、8、5,。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,则进程如何执行是安全的。

资源


进程  

最大需求量

已分配资源数

R1

R2

R3

R1

R2

R3

P1

6

5

2

1

2

1

P2

2

2

1

2

1

1

P3

8

0

1

2

1

0

P4

1

2

1

1

2

0

P5

3

4

4

1

1

3


这里需要强调的是,无论题目中给出何种条件,我们只要找到以下信息便可从容应对各种变化:

资源

进程

最大需求量

已分配资源数

仍需资源

可用资源

R1

R2

R3

R1

R2

R3

R1

R2

R3

R1

R2

R3

P1

6

5

2

1

2

1

5

3

1

7

7

5

P2

2

2

1

2

1

1

0

1

0

4

2

1

①    

P3

8

0

1

2

1

0

6

-1

1

9

8

5

P4

1

2

1

1

2

0

0

0

1

5

4

1

②    

P5

3

4

4

1

1

3

2

3

1

6

5

4

③    


【注】:

可用资源:表示相应的进程执行完毕(即释放该进程占用的资源)以后可用的资源,满足公式可用资源=可用资源+已分配资源,(因为已分配的资源将会在进程执行完毕以后释放,所以可用资源会不断增多,进程执行完毕便会全部释放)同时它也是下一个进程执行时可用的资源。

**需要说明的是根据进程执行情况的不同,每次填入表格中的可用资源也不会相同(因为每个进程分配的资源是有差异的),那么执行顺序也会有所差异,合理即可。

仍需资源:仍需资源数=最大需求量-已分配资源数,据此公式可以求得R1、R2、R3在不同的进程时仍需的资源数,如上表中所示。

    按照之前所讲的步骤,实现如下: 

R1已分配的总资源数为1+2+2+1+1=7

R2已分配的总资源数为2+1+1+2+1=7

R3已分配的总资源数为1+1+0+0+3=5

则R1 R2 R3可用资源数分别为9-7=2,

                          8-7=1,

                          5-5=0,

1.开始有的资源数R1 R2R3分别为2、1、0,所以从仍需资源中查找(需要说明的是查找的时候以最少资源数作为限定条件能够较快地找出结果),只有P2进程符合条件,此时可用资源变为4、2、1;

2.接下来在在其余的进程中查找符合条件的进程,只能执行P4,此时可用资源变为5、4、1,以此类推,按照以上的步骤即可找到所有进程执行的顺序P2->P4->P5->P1->P3

    以上便是有关银行家算法的计算过程,总体看来,银行家算法更多的是对概念的考察,弄清楚各个条件之间的制约关系便可迎刃而解了,希望能对大家有所帮助!




这篇关于银行家算法——软考探究(四)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/994754

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

Android平台播放RTSP流的几种方案探究(VLC VS ExoPlayer VS SmartPlayer)

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候,不知道如何选的好,本文针对常用的方案,做个大概的说明: 1. 使用VLC for Android VLC Media Player(VLC多媒体播放器),最初命名为VideoLAN客户端,是VideoLAN品牌产品,是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式,并支持DVD影音光盘,VCD影

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int