《中国计量学院操作系统课程设计(银行家算法+哲学家进餐).doc》由会员分享，可在线阅读，更多相关《中国计量学院操作系统课程设计(银行家算法+哲学家进餐).doc（18页珍藏版）》请在金锄头文库上搜索。
1、中国计量学院操作系统课程设计报告书 班级:姓名:学号:操作系统课程设计报告书共享资源分配与银行家算法哲学家进餐死锁问题及避免算法的实现 辅导老师：共享资源分配与银行家算法一、 课程设计目的和意义银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。所以，通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。二、 方案设计及开发过程1.
2、 课程设计背景此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。具体用银行家算法实现资源分配。要求如下：(1) 设计一个3个并发进程共享3类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2) 设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。(3) 确定一组各进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。2. 算法描述程序一开始初
3、始化个进程，打印出菜单，然后让用户选择随机算法还是银行家算法，然后分别进行不通的算法操作。随机算法：设进程I提出请求RequestN，则银行家算法按如下规则进行判断(1) 如果RequestN=AVAILABLE，则转(2)；否则，出错。(2) 系统分配资源，修改相关数据：AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUES(3) 系统执行安全性检查银行家算法：设进程I提出请求RequestN，则银行家算法按如下规则进行判断。 (1)如果RequestN=NEEDI，N，则转(2)；否则，出错。 (
4、2)如果RequestN=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。3. 数据结构int need103;/int max103;/最大需求int allocation103;/已分配int available_temp3;/可用，临时变量，用户尝试性分配request资源int available3;/可用i
5、nt path10;/记录安全序列int is_save;/是否产生安全序列标示符4. 主函数说明/初始化need，max，allocation，available，及判断初始状态是否有安全序列void init();void showMenu();/打印出菜单void print_sav_seq();/打印安全序列及分配过程void dfs(int idx);/改程序核心函数，用深度优先搜索查找安全序列void banker();/银行家算法入口void ramdon();/随机分配算法入口int main();/主程序入口5. 算法流程图(主函数)（银行家算法）（随机分配算法）三、 调试记
6、录与分析初始化数据参照课本P110：第一行为有3中资源，5个进程。最后一行为各类资源可用情况。中间数据位max，allocation，need：3 57 5 3 0 1 0 7 4 33 2 2 2 0 0 1 2 29 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 13 3 2即：在下面这种状态中 Max Allocation Need A B C A B C A B C 7 5 3 0 1 0 7 4 33 2 2 2 0 0 1 2 2 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3
7、 1Available A: 3 B: 3 C: 2请输入进程号和A, B, C请求的个数: 如果输入 3 0 0 0 Available 变成A:5 B:11 C:4 分析： 程序缺少对available更新条件的判断，因为available只在进程刚好完全执行完全后进行更新，即加上之前的Allocation。所以，更改程序，如下for(i=1; i=3; +i)if(finishedi) continue;if(processi.nd.a = 0 & processi.nd.b = 0 & processi.nd.c = 0) /即在进程刚好执行完成时进行process的更新- cntPr
8、ocess;finishedi = 1;available.a += processpr.alloc.a;available.b += processpr.alloc.b;available.c += processpr.alloc.c;四、 运行结果及说明1.打印菜单 2初始化数据，有安全序列则打印之并给出分配方案，否则，需要用户提供正常的初始化数据再运行程序：3 选择银行家算法，输入进程号，请求资源数1）分配后仍有安全序列： 2）条件不符合，不能分配 3）资源分配后照成死锁，则取消分配 4.如果输入2，进入随机算法。与3.2相同，给p0分配 3 3 2。使用随机分配算法仍然可以分配资源，如
9、下图但照成死锁。而银行家算法由于检测到会产生死锁故不将分配资源给p0，如上图没造成死锁，则给出安全序列，及分配后可以实行的分配方案五、 课程设计总结。总体来说，这个课程设计是5个当中较简单的，只要了解银行家算法，及随机分配算法，然后穷举所有情况。就可以做出相应的判断：是否会进入不安全状态需要注意的是，对于银行家算法，如果某进程提出了不合理请求后，要是判断后会进入不安全状态，需要将资源还原。通过这次课程设计实践，不仅让我对银行家算法的实现有了更深刻的理解, 也让我觉得自己的动手能力有了很大的提高;自信心也增强了,在课程设计中自己动脑子解决遇到的问题，书本上的知识有了用武之地，这巩固和深化了自己的
10、知识结构.通过这次的理论与实践相结合,我相信，只要自己在每一次实践中都能仔细思考，课程设计其实都不会很难,关键在于自己能不能认真思考,能不能亲自动手做实验，而不是想着其他人的劳动果实,其次你还要多操作,只有多操作才能从中发现问题,才能及时向老师和同学请教,解决问题,从而更好的掌握书本中知识。附录：（源代码）#include #include #include int need103;/还需int max103;/最大需求int allocation103;/已分配int available_temp3;/可用int available3;int m, n;/资源种类m种， 进程数nint pa
11、th10;/记录安全序列int is_save;/是否产生安全序列int mark10;/记录某进程是否已分配资源FILE *file;void dfs(int idx);void init()printf(从init.date初始化程序n);file = fopen(init.dat, r);fscanf(file, %d %d, &m, &n);for(int i = 0; i n; i+)for(int j = 0; j m; j+)/maxfscanf(file, %d,&maxij);for(int j = 0; j m; j+)/allocationfscanf(file, %d,
12、 &allocationij);for(int j = 0; j m; j+)/needfscanf(file, %d, &needij);for(int j = 0; j m; j+)/available_tempfscanf(file, %d, &available_tempj);availablej = available_tempj;memset(mark, 0, sizeof(mark);is_save = 0;printf(press Enter to continue.);getchar();dfs(0);void showMenu()puts(n*);puts(*0.初始化数据 1.银行家算法 2.随机分配算法 3.退出*);puts(*);void print_sav_seq()printf(安全序列如下：);for(int j = 0; j :);printf(p%d, pathj);puts();puts(*
