武汉理工大学华夏学院课程设计报告书
课程名称:操作系统原理
题目:编程序模拟银行家算法
系名:信息工程系
专业班级:计算机1112
姓名:曾高峰
学号: 10210411221
指导教师:苏永红司晓梅
2013 年 6 月 28 日
课程设计任务书
学生姓名:曾高峰专业班级:10210411221
指导教师:苏永红工作单位:武汉理工大学华夏学院设计题目:编程序模拟银行家算法
初始条件:
Linux操作系统,GCC编译环境
要求完成的主要任务:
主要任务:
银行家算法是避免死锁的一种重要方法,本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
思想:将一定数量的资金供多个用户周转使用,当用户对资金的最大申请量不超过现存资金时可接纳一个新客户,客户可以分期借款,但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付,但是能够使客户在有限的时间内得到借款,客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时,测试进程对资源的最大需求量,若现存资源能满足最大需求就满足当前进程的申请,否则推迟分配,这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束,然后归还资源,若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。
设计报告撰写格式要求:
1设计题目与要求 2 设计思想
3系统结构 4 数据结构的说明和模块的算法流程图
5 使用说明书(即用户手册):内容包含如何登录、退出、读、写等操作说明
6 运行结果和结果分析(其中包括实验的检查结果、程序的运行情况)
7 自我评价与总结 8 附录:程序清单,注意加注释(包括关键字、方法、变量等),
在每个模块前加注释;
时间安排
6月24日布置课程设计任务;分配题目后,查阅资料、准备程序;
6月 25~6月27 日上机调试程序、书写课程设计报告;
6月28 日提交课程设计报告及相关文档。
指导教师签字:2013年6月21日
系主任签字:2013年6月21日
1.设计目的
1.1模拟实现银行家算法,用银行家算法实现资源分配。
1.2了解多道程序系统中,多个进程并发执行的资源分配。
1.3掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。
1.4掌握预防死锁的方法,系统安全状态的基本概念。
1.5掌握银行家算法,了解资源在进程并发执行中的资源分配策略。
1.6理解死锁避免在当前计算机系统不常使用的原因。
2. 问题描述
在死锁的避免中,银行家算法把系统状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可以避免发生死锁。所谓安全状态,是指系统能按某种顺序为每个进程分配所需资源,直到最大需求,使每一个进程都可以顺利完成,即可找到一个安全资源分配序列。模拟实现这个工作过程。
3. 设计思路
我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
4.详细设计
4.1银行家算法
4.1.1在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满
意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
4.1.2设进程m提出请求REQUEST [m],则银行家算法按如下规则进行
判断。
4.1.2.1如果REQUEST [m] [n]<= NEED[m][n],则转(2);否则,出错。
4.1.2.2如果REQUEST [m] [n]<= A V AILABLE[m][n],则转(3);否则,
出错。
4.1.2.3系统试探分配资源,修改相关数据:
A V AILABLE[n]-=REQUEST[m][n];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
4.1.2.4系统执行安全性检查,如安全,则分配成立;否则试探险性分配
作废,系统恢复原状,进程等待。
4.1.2.5对于某一进程m,若对所有的n,有NEED[m][n]=0,则表此进程
资源分配完毕,应将占用资源释放。
4.2关于死锁的一些结论:
4.2.1参与死锁的进程最少是两个(两个以上进程才会出现死锁)
4.2.2参与死锁的进程至少有两个已经占有资源
4.2.3参与死锁的所有进程都在等待资源
4.2.4参与死锁的进程是当前系统中所有进程的子集
4.2.5注:如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃。
4.3资源分类:
4.3.1永久性资源:可以被多个进程多次使用(可再用资源)
4.3.1.1可抢占资源
4.3.1.2不可抢占资源
4.3.2临时性资源:只可使用一次的资源;如信号量,中断信号,同步信号等(可消耗性
资源)
“申请—分配—使用—释放”模式
4.4产生死锁的四个必要条件:
4.4.1、互斥使用(资源独占)
一个资源每次只能给一个进程使用
4.4.2不可强占(不可剥夺)
资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放
4.4.3请求和保持(部分分配,占有申请)
一个进程在申请新的资源的同时保持对原有资源的占有(只有这样才是动态申请,动态分配)
4.4.4循环等待
存在一个进程等待队列
{P1 , P2 , … , Pn},
其中P1等待P2占有的资源,P2等待P3占有的资源,…,Pn等待P1占有的资源,形
成一个进程等待环路
4.5死锁的解决方案
4.5.1 产生死锁的例子
申请不同类型资源产生死锁
P1:
…
申请打印机
申请扫描仪
使用
释放打印机
释放扫描仪
…
P2:
…
申请扫描仪
申请打印机
使用
释放打印机
释放扫描仪
…
申请同类资源产生死锁(如内存)
设有资源R,R有m个分配单位,由n个进程P1,P2,…,Pn(n > m)共享。假设每个进程对R的申请和释放符合下列原则:
* 一次只能申请一个单位
* 满足总申请后才能使用
* 使用完后一次性释放
m=2,n=3
资源分配不当导致死锁产生
4.5.2死锁避免:
定义::系统设计时确定资源分配算法,保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一
4.5.2.1破坏“不可剥夺”条件
在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请
4.5.2.2破坏“请求和保持”条件
要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配
4.5.2.3破坏“循环等待”条件
采用资源有序分配法:
把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次、序进行,否则操作系统不予分配。
4.6安全状态与不安全状态
安全状态:如果存在一个由系统中所有进程构成的安全序列P1,…Pn,则系统处于安全状态。一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和,系统处于安全状态(安全状态一定是没有死锁发生的)
不安全状态:不存在一个安全序列,不安全状态一定导致死锁。
5、数据结构设
5.1、定义全局变量
#define M,N; //定义常量,便于修改
int Available[N]; //各种资源可利用的数量
int Allocation[M][N]; //各进程当前已分配的资源数量
int Max[M][N]; //各进程对各类资源的最大需求数
int Need[M][N]; //还需求矩阵
int Request[M]; //申请各类资源的数量
int Work[M]; //工作向量,表示系统可提供给进程运行所需各类资源数量
int Finish[N]; //表示系统是否有足够的资源分配给进程,0为否,1为是
int p[N]; //存储安全序列
int i,j; //全局变量,主要用于循环语句中
int n,m; //n为进程的数量,m为资源种类数
5.2安全性检查算法
5.2.1设置两个工作向量Work=AVAILABLE;FINISH
5.2.2从进程集合中找到一个满足下述条件的进程,
FINISH==false;
NEED<=Work;
如找到,执行(3);否则,执行(4)
5.1.3设进程获得资源,可顺利执行,直至完成,从而释放资源。
Work+=ALLOCATION;
Finish=true;
GOTO 2
5.1.4如所有的进程Finish= true,则表示安全;否则系统不安全。
6、流程图(如图1)
图1:流程图
7.运行界面图
开始界面图(如图2)
图2开始界面图输入数据后图a(如图3)
图3输入数据后图a
输入数据后图b(如图4)
图4输入数据后图4 申请资源错误图(如图5)
图5申请资源错误图
资源申请正确图(如图6)
图6资源申请正确图
8、心得与体会:
“银行家算法的模拟实现”是本学期操作系统课程唯一的课程设计。在设计此程序的过程中,我遇到过许多问题,也学到了很多东西。本程序的设计实现主要是用C语言实现,通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决,在C学习上也有了很大的进步。程序设计过程中开始遇到的最大的问题是算法的结构设计问题,课本上只给了设计要求及简单的算法,要真正实现还需要考虑很多方面。在算法的数据结构设计上考虑了很长时间。在程序设计中先后参考了很多网络资料,也参考了一些别人写的的程序,综合这些算法思想和自己的思路对程序做了很好的设计方式,对一些算法的优越性等也作了一些考虑在课程设计过程中遇到了许多问题,也向同宿舍的同学做了一些请教一起讨论,积极解决遇到的问题。
在本次实验中我们使用了liunx变成环境,让我们更加系统深入的了解了liunx,gcc 编程思路和思想,同时让我更加深刻的了解银行家算法,了解死锁的避免和预防,对操作系统对资源的申请和释放有了更加深刻的理解,同时在编程过程中积极的向老师同学请教问题与他们一起探讨在系统中存在的问题和漏洞。
经过本次课程设计,我对liunx的操作能力和解决问题的实际能力有了很大的提高,同时对团队协作能力有了更加深刻的理解。如果还有类似的课程设计我一定会好好对待。
9.参考文献
[1]、汤子嬴编:《计算机操作系统》,西安电子科技大学出版社
[2]、张尧学、史美林编:《计算机操作系统教程》,清华大学出版社
[3]、任爱华、王雷编:《操作系统实用教程》,清华大学出版社
[4]、郑莉、董渊、何江丹编《C++语言程序设计》,清华大学出版社附录
#include
#include
#include
#include
#define M 50 /*进程数*/
#define N 30/*资源数*/
#define FALSE 0
#define TRUE 1
/*M个进程对N类资源最大资源需求量*/
int MAX[M][N];
/*系统可用资源数*/
int A V AILABLE[N];
/*M个进程已经得到N类资源的资源量*/
int ALLOCATION[M][N];
/*M个进程还需要N类资源的资源量*/
int NEED[M][N];
int Request[N];
int m,n;
/*输入M个进程对N类资源最大资源需求量*/
void scanfmax(int a,int b)
{
int i,j;