中国计量学院操作系统课程设计(银行家算法+哲学家进餐).doc

中国计量学院操作系统课程设计报告书 班级:姓名:学号:操作系统课程设计报告书共享资源分配与银行家算法哲学家进餐死锁问题及避免算法的实现 辅导老师：共享资源分配与银行家算法一、 课程设计目的和意义银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。所以，通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。二、 方案设计及开发过程1. 课程设计背景此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。具体用银行家算法实现资源分配。要求如下：(1) 设计一个3个并发进程共享3类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2) 设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。(3) 确定一组各进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。2. 算法描述程序一开始初始化个进程，打印出菜单，然后让用户选择随机算法还是银行家算法，然后分别进行不通的算法操作。随机算法：设进程I提出请求RequestN，则银行家算法按如下规则进行判断(1) 如果RequestN=AVAILABLE，则转(2)；否则，出错。(2) 系统分配资源，修改相关数据：AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUES(3) 系统执行安全性检查银行家算法：设进程I提出请求RequestN，则银行家算法按如下规则进行判断。 (1)如果RequestN=NEEDI，N，则转(2)；否则，出错。 (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;/可用int 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. 算法流程图(主函数)（银行家算法）（随机分配算法）三、 调试记录与分析初始化数据参照课本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 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的更新- cntProcess;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。使用随机分配算法仍然可以分配资源，如下图但照成死锁。而银行家算法由于检测到会产生死锁故不将分配资源给p0，如上图没造成死锁，则给出安全序列，及分配后可以实行的分配方案五、 课程设计总结。总体来说，这个课程设计是5个当中较简单的，只要了解银行家算法，及随机分配算法，然后穷举所有情况。就可以做出相应的判断：是否会进入不安全状态需要注意的是，对于银行家算法，如果某进程提出了不合理请求后，要是判断后会进入不安全状态，需要将资源还原。通过这次课程设计实践，不仅让我对银行家算法的实现有了更深刻的理解, 也让我觉得自己的动手能力有了很大的提高;自信心也增强了,在课程设计中自己动脑子解决遇到的问题，书本上的知识有了用武之地，这巩固和深化了自己的知识结构.通过这次的理论与实践相结合,我相信，只要自己在每一次实践中都能仔细思考，课程设计其实都不会很难,关键在于自己能不能认真思考,能不能亲自动手做实验，而不是想着其他人的劳动果实,其次你还要多操作,只有多操作才能从中发现问题,才能及时向老师和同学请教,解决问题,从而更好的掌握书本中知识。附录：（源代码）#include #include #include int need103;/还需int max103;/最大需求int allocation103;/已分配int available_temp3;/可用int available3;int m, n;/资源种类m种， 进程数nint path10;/记录安全序列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, &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(*);puts(* Work Need Allocation Work+Allocation Finish *);puts(* A B C A B C A B C A B C *);for(int j = 0; j m; j+)available_tempj = availablej;for(int j = 0; j %d;B-%d;C-%dnnn,available0, available1, available2 );void dfs(int idx)int i, j;if(is_save)return ;if(idx = n)is_save = 1;return ;for(i = n - 1; i = 0; i-)/for(i = 0; i n; i+)if(marki)/已分配，跳过continue;/判断各类资源是否够分配for(j = 0; j available_tempj)break;if(j = m)/可以分配marki = 1;for(j = 0; j m; j+)available_tempj += allocationij;pathidx = i;dfs(idx + 1);if(is_save)return ;for(j = 0; j m; j+)available_tempj -= allocationij;/还原marki = 0;void banker()int oper, i, j, flag1 = 0, flag2 = 0;while(true)flag1 = flag2 = 0;printf(请输入要操作的进程号：);scanf(%d, &i);printf(请输入各类资源的请求数：);int request3;scanf(%d %d %d, &request0, &request1, &request2);for(j = 0; j needij)flag1 = 1;if(requestj availablej)flag2 = 1;if(flag1)printf(request%d(%d,%d,%d)=need%d(%d,%d,%d)不成立n, i, request0, request1, request2, i, needi0, needi1, needi2);if(flag2)printf(request%d(%d,%d,%d)=available(%d,%d,%d)不成立n, i, request0, request1, request2, available0, available1, available2);if(flag1 = 0 & flag2 = 0)for(j = 0; j m; j+)/处理请求allocationij += requestj;needij -= requestj;availablej -= requestj;available_tempj = availablej;memset(mark, 0, sizeof(mark);is_save = 0;dfs(0);if(is_save)print_sav_seq();elsefor(j = 0; j m; j+)/不能分配，还原之前修改项availablej += requestj;puts(资源分配后会造成死锁，不能分配nn);puts( 1.继续操作 2.退出);scanf(%d, &oper);if(oper = 2)break;void ramdon()int oper, i, j, flag1 = 0, flag2 = 0;while(true)flag1 = flag2 = 0;printf(请输入要操作的进程号：);scanf(%d, &i);printf(请输入各类资源的请求数：);int request3;scanf(%d %d %d, &request0, &request1, &request2);for(j = 0; j needij)flag1 = 1;if(requestj availablej)flag2 = 1;if(flag1)printf(request%d(%d,%d,%d)=need%d(%d,%d,%d)不成立n, i, request0, request1, request2, i, needi0, needi1, needi2);if(flag2)printf(request%d(%d,%d,%d)=available(%d,%d,%d)不成立n, i, request0, request1, request2, available0, available1, available2);if(flag1 = 0 & flag2 = 0)for(j = 0; j m; j+)/处理请求allocationij += requestj;needij -= requestj;availablej -= requestj;available_tempj = availablej;memset(mark, 0, sizeof(mark);is_save = 0;dfs(0);if(is_save)print_sav_seq();elseputs(请求资源已经分配，造成死锁nn);puts( 1.继续操作 2.退出);scanf(%d, &oper);if(oper = 2)break;int main()while(true)showMenu();printf(请选择接下来的操作：);int oper;scanf(%d, &oper);switch( oper )case 0:init();if(is_save = 1)print_sav_seq();elseputs(无法找到安全序列，请先修改init.dat文件中的数据再运行程序);return 0;break;case 1:banker();break;case 2:ramdon();break;case 3:return 0;default:puts(输入有误，清重试);break;return 0;哲学家进餐死锁问题及避免算法的实现课程设计内容与要求复习Linux下进程和线程编程的内容，以及操作系统课本中关于五个哲学家进餐死锁问题原理，在Linux下利用线程和线程互斥锁的机制实现哲学家进餐问题，观察记录死锁现象。并提出一种能解决五个哲学家进餐问题的一种方法，并编程实现之。课程设计需要实现哲学家进餐问题发生死锁以及不发生死锁的两份程序。1、 主要函数void printTime();/打印时间void eat(int i);/第i个哲学家开始进餐void think(int i);/第i个哲学家开始思考void get(int i, int j);/第j个哲学家拿起第i只筷子void put(int i, int j);/第j个哲学家放下第i只筷子void *f(void * arg);/哲学家线程int main();/程序入口 2、流程图（主函数）（哲学家线程）3. 程序运行，数据分析3.程序运行，数据分析3分钟后：附源代码：#include #include #include #include #include #include static pthread_mutex_t cs_mutex_ph5 = PTHREAD_MUTEX_INITIALIZER;/哲学家static pthread_mutex_t cs_mutex_ch5 = PTHREAD_MUTEX_INITIALIZER;/筷子int chopstick5 = 0;void printTime()int i;time_t timep;time (&timep);char s1024;sprintf( s,当前时间%s :,ctime(&timep); for(i = 23; i 31; i+)si-23 = si;rsi-23 = 0;printf(%s:, s);void eat(int i)printTime();printf(philosopher%d is eating .n, i);sleep(rand() % 5);printTime();printf(philosopher%d has finished ate.n, i);void think(int i)printTime();printf(philosopher%d is thinking.n, i);sleep(rand() % 5);void get(int i, int j)pthread_mutex_lock( &cs_mutex_chi);/while(chopsticki = 1);chopsticki+;printTime();printf(哲学家%d