【计算机操作系统】银行家算法的模拟实现

admin管理员组

文章数量:1531657

文章目录

• 前言
• 1 实验相关知识理论
• • 1.1 死锁的概念
  • 1.2 产生死锁的原因
  • 1.3 避免死锁的方法
  • 1.4 解除死锁的方法
• 2 实验设计思路
• 3 实验设计涉及到的数据结构
• 4 程序算法设计
• • 4.1 银行家算法步骤
  • 4.2 安全性算法步骤
• 5 运行结果
• 6 设计心得
• 7 参考资料

---

前言

编程模拟银行家算法实现避免死锁 要求：深入理解死锁的概念、产生死锁的原因、避免死锁和解除死锁的方法，掌握利用银行家算法避免死锁的方法。
1.设计依据来源著名开源社区或重要的参考文献。
2.功能代码通过注释标注来源于哪个开源社区。
3.分析题目，制定解决方案，建立必要的数据结构，设计总体流程，详细设计必要的算法。
4.可以采用任何编程语言实现算法功能。
5.提交作业报告，包括设计思路、设计所涉及的主要数据结构、程序清单、运行结果、设计心得、参考资料等。

---

1 实验相关知识理论

1.1 死锁的概念

        在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。

1.2 产生死锁的原因

1.竞争可剥夺性资源。
2.竞争非剥夺性资源。
3.竞争临时性资源。
4.进程运行过程中，请求和释放资源的顺序不当，导致进程死锁。

1.3 避免死锁的方法

1.避免一个线程同时获取多个锁；
2.避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源；
3.尝试使用定时锁，使用lock.try-lock(timeout)来替代使用内部锁机制；
4.对于数据库锁，加锁和解锁必须在一个数据库链接里，否则会出现解锁失败的情况。

1.4 解除死锁的方法

1.剥夺资源。从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。
2.撤销进程。①最简单的是让全部进程都死掉；
②温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除为止。

---

2 实验设计思路

        依次输出进程数量与各类型资源数量,检查某一时刻系统是否处于安全状态，若系统处于安全状态则就行资源分配，也就是对用户提出的请求进行合法性检查，即检查请求的是不大于需要的资源量，是否不大于可利用的资源量。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，让其等待，返回。

---

3 实验设计涉及到的数据结构

        可利用资源向量Available。表示含有m个元素的数组，其中每一个元素表示一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目。
        最大需求矩阵Max。这是一个nm的矩阵，他定义了系统中n个进程中的每一个进程对m类资源的最大需求。
        分配矩阵Allocation*。这时一个nm的矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数。
        需求矩阵Need*。这是一个n*m的矩阵，表示每一个进程尚需的各类资源数。
上述矩阵间存在如下关系:

---

4 程序算法设计

4.1 银行家算法步骤

        银行家算法其核心是：保证自己的限额至少不小于一个客户的限额。
        设Request_i是进程Pi的请求向量，如果Request_i[j]=K，表示进程Pi需要K个Rj类资源。当Pi发出资源请求后，系统按照下面的步骤进行检查：
        如果Request_i[j]<=Need[i,j],便转向步骤2；否则认为出错，因为它所需要的资源数已超过了它所宣布的最大值。
        如果Request_i[j]<=Available[j]，便转向步骤3；否则，表示尚无足够资源，Pi需等待。
        系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j] = Available[j] - Request_i[j];
Allocation[i,j] = Allocation[i,j] + Request_i[j];
Need[i,j] = Need[i,j] - Request_i[j];
        系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式的将资源分配给进程Pi，以完成此次分配；否则，将本次的试探分配作废，恢复原来的资源分配，让进程Pi等待。

4.2 安全性算法步骤

1.设置两个向量：
1）工作向量Work，表示可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available；
2）Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始先做Finishp[i]=false;当有足够资源分配给进程时，在令Finish[i]=true。
2.从进程集合中找到一个能满足下述条件的进程：
1）Finish[i]=false;
2)Need[i,j]<=Work[j]
若找到，执行步骤3）；否则，执行步骤4).
3）当进程Pi获得资源后，可顺利执行，直到完成，并释放出分配给他的资源你，故应执行：
Work[[j] = Work[j] + Allocation[i,j];
Finish[i]=true;
go to step2 ;
4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

---

5 运行结果

---

6 设计心得

        通过这次的课程作业设计，我了解掌握了银行家算法﹐学会模拟实现资源分配﹐同时通过编写和调试一个系统分配资源的简单模拟程序﹐观察到了死锁产生的条件﹐并使用适当的算法﹐有效的防止和避免死锁的发生。对于银行家算法的设计﹑编写的思路，我通过几天反复的阅读实验指导﹐仔细的思考出现的问题﹐反复推敲﹑测试与修改﹐终于能完满的完成这次程序设计任务。
        为了使测试的数据更加直观的展现出来，我通过自己设计和参考gitee上一些作者设计的银行家算法程序设计出一个基于JFrame的可视化界面，在界面上显示该序列是否有安全序列，并且在控制台中打印出安全序列。
        通过这次程序设计的课程作业，让我进一步理解死锁的概念、产生死锁的原因、避免死锁和解除死锁的方法，并且掌握了利用银行家算法避免死锁的方法。设计的时间虽然不长﹐但带了给我知识，也带给了我战胜困难﹑完成任务的欢乐。

---

7 参考资料

[1]银行家算法的模拟实现https://max.book118/html/2021/1108/7141200150004036.shtm
[2]开源社区Gitee
https://gitee/p-santiago/banker-algorithm-/tree/master
[3]开源社区 CSDN
死锁的避免 银行家算法 java实现
https://blog.csdn/m0_46530662/article/details/121720121
[4]死锁的原理以及避免算法
https://blog.csdn/triorwy/article/details/80643753
[5]汤小丹，等，《计算机操作系统（慕课版）》，人民邮电出版社，2021

本文标签： 银行家算法操作系统计算机