4 详细设计
齐齐哈尔大学
操作系统课程综合实践
题目： 银行家算法模拟实验
班级： 计本101班
姓名： 司伟东
学号： 2010021015
指导教师： 滕艳平
2012年11 月
4 详细设计
银行家算法模拟实现
摘要：随着计算机的普及和发展，计算机在日新月异的发展着，可以说计算机在人们生活
中占有越来越重要的地位，许多的计算机领域取得了可喜的成果，许多的计算的到了较好的改进，随着计算机的发展，人们对计算机的需求也越来越高，为了防止用户操作导致计算机同一时刻进程过多产生死锁，我们引进了银行家算法来避免计算机死锁的发生，本论文阐述了什么叫银行家算法，了解银行家算法的大体思想，经过流程图，以及银行家算法是用以解决什么问题，简单论述了银行家算法的实现过程，并说明银行家算法的中心思想，本论文设计的目的是通过编写一个 系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生.掌握避免死锁的集体实施方法。
关键字：死锁，银行家算法，，避免死锁，资源分配，安全序列 一．银行家算法概论
什么叫银行家算法：银行家算法最开始是用来模拟一个小城镇的银行家为一批顾客的贷款问题，，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁。
银行家算法其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待。
二.死锁和安全性序列
（1）死锁
死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出来的。是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那麽死锁涉及到的各个进程都将永远处于封锁状态。 它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上，死锁问题不仅在计算机系统中存在，在我们日常生活中它也广泛存在。
4 详细设计
在计算机系统中，涉及软件，硬件资源都可能发生死锁。例如：系统中只有
一台CD-ROM驱动器和一台打印机，某一个进程占有了CD-ROM驱动器，又申请打印机；另一进程占有了打印机，还申请CD-ROM。结果，两个进程都被阻塞，永远也不能自行解。 （2）安全序列
安全序列的的实际意义在于：系统每次进行资源分配后，如果对于系统中新的资源状况，存在一个安全序列，则至少存在一条确保系统不会进入死锁的路径。按照该序列，银行家可以实施一个有效的分配过程使得所有客户得到满足 。 银行家算法的核心在于安全序列的产生。安全序列正是一种安全的进程推进顺序。
三.银行家算法包含的内容
银行家算法包含三个方面的内容：
银行家算法、相应的数据结构、安全性算法。 1.银行家算法
设进程i提出请求Request[n]，则银行家算法按如下规则进行判断。 (1)如果Request[n]>Need[i，n]，则报错返回。
(2)如果Request[n]>Available，则进程i进入等待资源状态，返回。 (3)假设进程i的申请已获批准，于是修改系统状态： Available=Available-Request
Allocation=Allocation+Request Need=Need-Request
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
2．银行家算法中用到的主要数据结构
为实现银行家算法，系统中必须设置若干个数据结构
（1）可利用资源向量 int Available[j] j为资源的种类，它是一个vector向量可被初始化任意长度其中每一个元素代表一类可利用资源的数目。其值随着该类资源的分配和回收而动态的改变。
（2）最大需求矩阵 int Max[i][j] i为进程的数量，这是一个n×m的矩阵他定义了系统中n个进程中的每一个进程对m类资源的最大需求
（3）分配矩阵 int Allocation[i][j] ，这是一个n×m的矩阵他定义了系统中每一类资源当前已分配给每一进程的资源数。
（4）需求矩阵 int need[i][j]= Max[i][j]- Allocation[i][j]，它是一个n×m的矩阵用以表示每一个进程尚需的各类资源数。
3.安全性算法
安全新算法是银行家的一个子算法，是由银行家算法调用的，能够判断系统的状态是否安全
(1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程， FINISH==false; NEED<=Work; 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION;
4 详细设计
Finish=true; GOTO（2）
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
三.银行家算法模拟系统流程图及程序设计
开始创建数据结构并初始化创建进程并置数据结构执行银行家算法安全态不安全态完成资源分配撤销资源分配结束 1．程序结构
程序共有以下五个部分：
(1).初始化：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。 (2).当前安全性检查：用于判断当前状态安全性，根据不同地方的调用提示处理不同。
(3).银行家算法：进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程。 (4).显示当前状态：显示当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量。
(5).主程序main() 逐个调用初始化、显示状态、安全性检查、银行家算法函数，使程序有序的进行。 2．数据结构
（1）数据结构选取分析
相关推荐：
loading