华南农业大学信息学院.docx
- 文档编号:18399066
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:12
- 大小:90.35KB
华南农业大学信息学院.docx
《华南农业大学信息学院.docx》由会员分享,可在线阅读,更多相关《华南农业大学信息学院.docx(12页珍藏版)》请在冰点文库上搜索。
华南农业大学信息学院
华南农业大学信息学院
操作系统课程设计成绩单
开设时间:
2004~2005学年第一学期
小组成员、组内分工及各成员成绩
学号
2002374203
姓名
冯绍欣
分工
初始化、回收、比较函数
成绩
学号
2002374221
姓名
潘素芬
分工
主函数与实验报告撰写
成绩
学号
2002374225
姓名
余彪
分工
银行家算法
成绩
学号
姓名
分工
成绩
实验题目
实现死锁避免算法——银行家算法
教师评语
评价指标:
●题目内容和要求完成情况优□良□中□差□
●小组成员1分工完成情况优□良□中□差□
●小组成员2分工完成情况优□良□中□差□
●小组成员3分工完成情况优□良□中□差□
●小组成员4分工完成情况优□良□中□差□
●对算法原理的理解程度优□良□中□差□
●程序设计水平优□良□中□差□
●程序运行效果及正确性优□良□中□差□
●课程设计报告结构清晰优□良□中□差□
●报告中总结和分析详尽优□良□中□差□
小组成绩
教师签名
一、课程设计目的
通过模拟死锁避免的实现,加深对死锁避免,系统安全状态等的理解。
二、课程设计内容
实现死锁避免算法——银行家算法。
三、设计方案
1、银行家算法原理
死锁避免的策略中需先分析资源分配的安全性。
如果操作系统能保证所有的进程在有限时间内得到需要的全部资源,则称系统处于“安全状态”,否则说系统是不安全的。
安全状态是指,如果存在一个由系统所有进程构成的安全序列{P1,P2…Pn},则系统处于安全状态。
一个进程序列{P1,P2…Pn}是安全的,如果对于其中每一个进程Pi(1<=i<=n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j
系统处于安全状态则不会发生死锁。
如果不存在任何一个安全序列,则系统处于不安全状态。
不安全状态一定导致死锁。
银行家算法是最著名的死锁避免算法。
操作系统按照银行家的规定为进程分配资源,进程首先提出对资源的最大需求量,当进程在执行中每次申请资源时系统测试该进程已占有的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源,若没有超过,则系统再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
这样就能保证在任何时刻至少有一个进程可以得到所要的全部系统而执行结束,执行结束后归还得资源加入到系统的剩余资源中,这些资源又至少可以满足另一个进程的最大需求,……,于是,可以保证系统中所有进程都能在有限的时间内得到需要的全部资源。
2、程序主要设计方案与简化假设
考虑到C语言随机函数的特性,每次随机产生的数字是一样的,故程序运行时,采用手动输入的方法,输入进程个数,资源种类,每种资源的个数和各个进程的占有资源量,尚需资源数。
各进程已占有的各种资源数和尚需各种资源的个数分别存入二维数组,各种资源的总数和分配后剩下的各种资源个数分别存入一维数组,调用银行家算法,判断是否安全,若安全,返回安全序列的个数,并输出安全序列,若不安全,则返回零。
银行家算法在输出安全序列时采用了回溯的方法,使其找到一条安全序列后回溯到前面寻找另一条安全序列。
若有进程提出新的需求,则输入进程号和需要的各种资源的个数,重新调用银行家算法。
安全,则分配,不安全,不分配,收回试探分配的资源以便有另外的进程提出资源申请时使用。
3、数据结构
全局变量:
二维数组:
allocation[][]---各进程已占有的各种资源数
need[][]---各进程尚需各种资源的个数
一维数组:
all[]---各种资源的总数
remain[]---分配后剩下的各种资源个数
整型变量:
pnum---总的进程数,初始化时手动输入
snum---资源种类,初始化时手动输入
top---结构体数组stack的指针,初始值为-1
结构体struct:
num---记录可以分配进程个数
able[]---记录可以分配进程号
avail[]---记录当前剩余的各类资源
visited[]---记录当前进程是否已分配资源
结构体变量:
current---当前工作点,记录在当前状态下,可以分配的进程数,及进程号,当前剩余的各类资源,各进程的分配状态
stack[]---每次current工作后将其存入stack[],用于输出安全序列
子程序:
voidinit()---初始化,采用手动输入的方法,输入进程个数,资源种类,每种资源的个数和各个进程的占有资源量,尚需资源数。
voidrelease(intx[],inty[])---释放资源,把y[]数组中的资源加入x[]中。
intcompare(intx[],inty[])---判断两个数组中的各个值,若x[]数组中有一个值大于y[]数组中相应的值,则返回零,否则返回一。
voidprint()---输出安全序列。
intbanker()---银行家算法,返回值为零代表无安全序列,不为零即是返回
安全序列个数。
main()---主函数,调用初始化和银行家算法子函数,并解决进程的新资源申请要求。
4、程序框架:
5、实验环境
本程序是用C语言编写的,在TurboC和WinTC下均可运行。
四、设计过程中遇到的问题及解决方法
潘素芬:
在其他两位组员之间的合作中,由于每个人都有不同的编程风格和设计思路,函数与函数之间的接口,函数的调用问题便是最难解决的,程序的各部分编写完后,如何把它们拼接在一起,是我们在后期工作中解决的主要问题。
解决的前提是弄清楚各组员思路和设计想法,找出函数的入口参数和出口参数。
本人主要负责主函数的编写,即调用冯绍欣和余彪编写的初始化程序和银行家算法,加上进程的新的资源申请。
在实现进程的新的资源申请时,剩余资源remain[]数组和新的申请new[]数组比较,若new[]已超过remain[],则判定系统不安全,且要把试探分配的资源返回给系统。
不超过时,调用银行家算法,判断是否安全,安全则输出序列,不安全把试探分配的资源返回给系统。
开始编写时没有注意到要把试探分配的资源返回给系统的问题,当有一次申请不安全后,接下来的申请都是判定属于不安全状态,通过每步追踪才发现问题所在。
界面的设计也是在编程中遇到的问题,由于C语言本身的限制,不可能做到可视化的效果,只能是尽量让操作的人更易上手,清楚每一步的输入是什么,输出是什么。
冯绍欣:
这次设计我负责进程、资源的初始化init()、回收资源函数release(intx[],inty[])和比较函数compare(intx[],inty[])。
设计init()的时候,由于考虑到调试困难过程,所以没有用上随机函数分配资源。
在init()里面,主要确定进程数目,资源种类和对每类资源的总数数组all[RESOURCE],每个进程尚需的各类资源数组need[PROCESS][RESOURCE],已分配给每个进程的各类资源数组allocation[PROCESS][RESOURCE]进行初始化。
由于是初始化程序,因此难度不大。
设计回收资源函数和比较函数时,由于开始没有考虑到这两个函数被主算法banker调用要传入,因而没有考虑接口的问题,当大家把各自设计拼合在一起的时候,这成了问题的焦点。
后来得到他们的提示,我在函数
开始的时候设置形式参数x[]和y[].而在处理比较函数的细节问题上,一开始可能是并不了解组员如何调用compare(intx[],inty[])。
当了解到compare(intx[],inty[])是用作判断条件时,我在函数中设置了返回值,若大于就return(0),否则就返回return
(1)。
总的来说,我负责的部分问题不大。
可能是很长时间没有用C语言写程序,所以很多语法上的细节都没有注意到。
幸亏是三人合作,这些问题就变得不是问题了。
我可以在这方面省下了很多被折磨的时间。
经过这次合
作,我深深地意识到组员相互沟通的重要性:
一方面,当自己在某一知识面上遇到问题和苦难,组员可以帮组自己,节省了时间。
另一方面,通过沟通了解,知道自己怎样做才能更好的配合组员。
大概是组员的目标很明确的缘故,就是如何尽快很好的完成任务,所以大家在合作上都很配合。
自从数据结构大作业,每次合作完成作业的感受都会很多,我都可以从不同的同学身上学到东西。
这次可以说是对C语言的复习,温故而知新,很多在初学C语言时遇到的问题,这次都可以解决了,就好像函数接口和返回值问题。
我想我得又一次感谢老师给我们一次合作的机会了。
余彪:
在本次大作业的设计过程中,我们都感到了合作的重要性,我认为有时1+1不一定会有>2的效果,有时相反会起到反作用,处理得不好,甚至会出现1+1<1的情况。
所以在每个人开始完成自己的工作之前,一定要对整个问题进行详细的分析,明确各人的任务以及程序的模块化。
更重要的是各模块之间的接口问题,在设计的过程中还要与各位成员进行及时的沟通,相互协作才能比较高效地完成设计。
我的主要工作是完成银行家算法(banker()),而在当前状态下是否能满足分配的条件的算法是由我的合作伙伴提供的,还有当一个进程得到能满足运行的所有资源后的资源的回收的算法也是由伙伴提供的,这样我就可以集中精力考虑在什么情况下可以分配资源,什么样的序列才是安全的(采取一次性分配进程所需资源的方法)。
当进程所需的资源得到满足后,然后我们再回收其资源,测试当前是否有进程的需求能够得到满足,若有进程满足则分配资源让其能够运行,直到所有的进程都运行完为止。
本次实验中,本人觉得比较难的是如何将安全的序列打印出来,因为其中用到了栈的数据结构,当找到一个序列之后,还要通过回溯找到第二条,第三条.....。
总而言之,本次实验真的收获很大。
特别是体会到了开发的过程中大家相互合作的精神,以及共同完成设计所需要的配合与协作。
五、测试与运行情况
测试数据
进程数:
5资源种类:
3
每种资源个数:
1057
各进程的目前占有量:
尚需要量:
输出结果:
有进程p1提出新的申请:
102
分配后,结果为:
进程p2提出新的申请:
500
系统处于不安全状态
六、课程设计小结:
通过本次课程设计,我们进一步了解了银行家算法和死锁的实现过程,许多以前模糊的概念通过本次实验也清晰了许多。
本来,由于这学期刚学习了java面向对象的语言,在完成了本程序C语言的编写后,曾设想过将其改为java的格式,这样可以实现更人文化的界面,但在实现过程中却不断出现下标越界,空指针等异常,java语言是不支持指针的,所以在current和stack[]的附值时,会出现current值的改变伴随着stack[]值也改变的情况,因为java语言采用的是引用,即指向了同一个内存单元,所以后来由于时间问题,还是放弃了这个想法。
也曾想过用C语言的随机函数,但修改后却发现每次运行时产生的随机数一样,这样就失去了随机的目的,所以还是采用了手动输入的方法,虽然比较麻烦,但也达到了实验的目的。
这是一个简单应用程序,但也锻炼了三个人合作协调的能力,有助于我们以后的发展。
当然,程序还有许多不完善的地方,请老师指正!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华南 农业大学 信息 学院