《操作系统课程设计银行家算法.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计银行家算法.doc（13页珍藏版）》请在三一文库上搜索。
1、用银行家算法和随机算法实现资源分配一、需求分析为了了解系统的资源分配情况，假定系统的任何一种资源在任一时刻只能被一个进程使用。任何进程已经占用的资源只能由进程自己释放，而不能由其他进程抢占。当进程申请的资源不能满足时，必须等待。因此，只要资源分配算法能保证进程的资源请求，且不出现循环等待，则系统不会出现死锁。要求编写系统进行资源调度的程序。一个是随机动态地进行资源分配的模拟程序，即只要系统当前剩余资源满足进程的当前请求，就立即将资源分配给进程，以观察死锁产生情况；一个是采用银行家算法，有效地避免死锁的产生。二、概要设计1、系统的主要功能 采用银行家算法，有效地避免死锁的产生。3、运行环境要求W
2、INDOWS VC4、实验内容概述模拟进程的资源分配算法，了解死锁的产生和避免的方法。三、详细设计 要求（1） 设计34个并发进程，共享系统的10个同类不可抢占的资源。各进程动态进行资源的申请和释放。（2） 用银行家算法和随机算法分别设计一个资源分配程序，运行这两个程序，观察系统运行情况，并对系统运行的每一步情况进行显示。提示（1）初始化这组进程的最大资源请求和依次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的格式如图所示，其中进程的状态有：就绪、等待和完成。当系统不能满足进程的资源请求时，进程处于等待态。资源需求总量表示进程运行过程中队资源的总的需求量。进程
3、名状态当前申请量资源需求总量已占资源量能执行完标志已占资源量表示进程目前已经得到但还未归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需求总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。（2）银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程。如果能，则转将资源分配给所选的进程，这样，该进程已获得资源量最大请求，最终能运行完。标记这个进程为终止进
4、程，并将其占有的全部资源归还给系统。 重复第步和第步，直到所有进程都标记为终止进程，或直到一个死锁发生。若所有进程都标记为终止进程，则梯田的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。由于银行家算法可以避免死锁，为了观察死锁现象的发生，要求采用两个算法：银行家算法和随机算法。随机算法的分配原则是：当进程申请资源时，如果系统现存资源数能满足 进程的当前申请量，就把资源分配给进程，否则，让其等待。这样，随机算法可能引起死锁。一开始输入各进程依次申请的资源数量计算各进程申请资源总量各进程申请的资源总量超过系统拥有的资源总量？在PCB中登记进程申请各
5、类资源总量将PCB中的“已占资源量”初始化为0，状态置为“就绪”选择随机算法?调随机算法程序返回调银行家算法程序显示：进程申请的资源量超过系统拥有总量YNYN资源分配模拟算法总框图Y开始顺序选择一个就绪进程作为现运行进程系统现有资源量不少于该进程的当前申请量?假定对申请资源的进程分配资源将分配后系统剩余的资源数量与各进程的剩余需求量比较寻找一个系统你能满足某需求的进程找到了吗？检查是否还有未执行完，且标志尚未设置的进程找到了吗？分配安全，可对进程进行实际的资源分配该进程已得到全部资源了吗？设置该进程为完成态标志，并让归其还全部资源系统现存资源量加该进程归还量有等待进程吗？置能满足资源要求的进程
6、为就绪态还有就绪进程吗？返回置该进程为等待态设置该进程能执行完标志，并假定其归还了全部资源分配不安全，申请资源的进程等待NYYNYNNYNYN四、源代码#include #include#includeusing namespace std;const int TASK_RUNNING=0;const int TASK_SUCCEED=1;const int TASK_WAITTING=2;const int TASK_RLength=10;int Rcs-left=RLength;ofstream ff(result.txt);class pcbpublic:int p_pid;int p_
7、stat;int p_apply;int p_occupy;bool p_issuc;int p_require;pcb(int id, int require)p_pid=id;p_require=require;p_stat=TASK-RUNNING;p_occupy=0;p_issuc=false;p_apply=0;friend ostream & operator(ostream&cout,const pcb&p)contp.p_pidtp.p_stattp.p_requiretp.p_occupyendl;return cout;void rand (vector&resource
8、,vector&pgrp);void banker(vector&resource,vector&pgrp);int main()vectorresource;vectorpgrp;vector:iterator r;vector:iterator p;coutENTER THE MAX NUMBER FOR THE REQUESTED RESOURCE:endl;coutIDtREQUESTEDendl;ffENTER THE MAX NUMBER FOR THE REQUESTED RESOURCE:endl;ffIDtREQUESTEDendl;int id,qty;for(int i(
9、1);i=4;i+)docoutit;ffiqty;ffqtyRcs_left|qty1);pgrp.insert(pgrp.begin(),pcb(i,qty);/输入各进程申请资源的总量，以及初始化各进程；coutALOGRITHMendl Random(R)t Banker(B)endl ANY OTHER KEY TO QUITendl;ffALOGRITHMendl Random(R)t Banker(B)endl ANY OTHER KEY TO QUITchoice;ffchoiceendl;if(choice=R|choice=r ) rand(resource,pgrp);e
10、lse if(choice=B|choice=b) banker(resource,pgrp);else return(0);rerurn(1);void rand (vector&resource,vector&pgrp); vector:iterator p,q; vector:iterator current; vector:iterator r; int temp; coutNOW-BANKER ALOGRITHMendl; ffNOW-BANKER ALOGRITHMp_apply=0) coutENTER THE APPLY FOR THE PROCESSnp_pidt; ffEN
11、TER THE APPLY FOR THE PROCESSnp_pidtemp; fftempp-p_require-p-p_occupy) coutbeyond the real need!endl; coutENTER THE APPLY FOR THE PROCESSnp_pidt; ffbeyond the real need!endl; ffENTER THE APPLY FOR THE PROCESSnp_pidtemp; fftempp_apply=temp; /input the apply for the current process; if(current-p_apply
12、 Rcs_left) /has problem /apply too much,please wait- current-p_stat=TASK_WAITTING; coutendlp_pidis waittingn; ffendlp_pidp_stat=TASK_RUNNING) break; if(p=pgrp.end() coutLOCKED!endl; ffLOCKED!p_apply,current-p_pid); couttemptresources are accepted forp_pidendl; coutendl; fftemptresources are accepted
13、 forp_pidendl; ffp_apply; current-p_occupy+=current-p_apply; current-p_occupy=0; /看该进程是否已满足 if(current-p_occupyp_require) pcb proc(*current); pgrp.erase(current); pgrp.insert(pgrp.end(),proc); /current-p_apply=0; /delete current and insert into the end continue;/go on and should select another proce
14、ss /succeed coutendlprocesstp-p_pidthas succeed!endl; ffendlprocesstp-p_pidthas succeed!p_apply; resource.clear(); current-p_stat=TASK_SUCCEED; / current-p_occupy=0; for (p=pgrp.begin();p!=pgrp.end();p+) if(p-p_stat=TASK_WAITTING) break; if(p=pgrp.end() for(q=pgrp.begin();q!=pgrp,end();q+) if(q-p_st
15、at=TASK_RUNNING) break; if(q=pgrp,end() coutSUCCEED!endl; ffSUCCEED!p_stat=TASK_WAITTING&Rcs_left=p-p_apply) break; if(p!=pgrp.end() p-p_stat=TASK_RUNNING ; pcb proc(*p); pgrp.erase(p); pgrp.insert(pgrp.end(),proc); continue; else coutLOCKED!endl; ffLOCKED!endl; exit(1); void banker(vector&resource,
16、vector&pgrp); vector:iterator p; vector:iterator r; vector:iterator current,q; vector:iterator r; pcb proc(0,0); int length; coutNOW-BANKER ALOGRITHMendl; ffNOW-BANKER ALOGRITHMp_stat=TASK_RUNNING) current=p; break; if(current-p_apply =0) coutENTER THE APPLY FOR THE PROCESSnp_pidt; ffENTER THE APPLY
17、 FOR THE PROCESSnp_pidcurrent-p_apply; ffp_applyp_applycurrent-p_requirecurrent-p_occupy) coutcoutENTER THE APPLY FOR THE PROCESSnp_pidt; ffcoutENTER THE APPLY FOR THE PROCESSnp_pidcurrent-p_apply; ffp_applyp_applyRcs_left; current-p_stat=TASK_WAITTING; proc=*current; pgrp.erase(current); pgrp.inser
18、t(pgrp.end(),proc); coutendlp_pidis waiting!endl; ffendlp_pidis waiting!p_occupy+=current-p_apply; length-=current-p_apply; if(current-p_occupy=current-p_require) length-=current-p_require current-p_issuc=true; for(p=pgrp.begin();p!=pgrp.end();p+) if(p-p_stat=TASK_SUCCEED) CONTINUE; if(p=current&p-p
19、_issuc=true) continue; if(p-p_require-p-p_occupy)length) continue; else p-p_issue=true; length+=p-p_occupy; continue; /检查是否还有标志位未设置的进程 for(p=pgrp.begin();p!=pgrp.end();p+) if(p-p_issuc=false&p-p_stat!=TASK_SUCCEED) break; if(p!=pgrp.end() current-p_occupy=backup.p_occupy; current-p_stat=TASK_WAITTIN
20、G; coutendlp_pidis waiting.endl; ffendlp_pidis waiting.p_issuc=false; continue; /分配安全，可对程序进行实际的分配 resource.insert(resource.end(),current-p_apply,current-p_pid); Rcs_left-=current-apply; coutendlp_pidgetp_applyresource(s)!endl; ffendlp_pidgetp_applyresource(s)!p_apply=0; if(current-p_occupyp_require)
21、 proc=*current; pgrp.erase(current); pgrp.insert(pgrp.end(),proc); for(p=pgrp.begin();p!=pgrp.end();p+) p-p_issuc=false; continue; current-p_stat=TASK_ SUCCEED current-p_occupy=0; coutendlp_pidhas finished!endl; ffendlp_pidhas finished!p_require; for(p=pgrp.begin();p!=pgrp.end();p+) if(p-p_stat=TASK
22、_WAITTING) break; if(p=pgrp.end() for(p=pgrp.begin();q!=pgrp.end();q+) if(q-q_stat=TASK_RUNNING) break; if(q=pgrp.end() coutendlSUCCEED!endl; ffendlSUCCEED!p_stat=TASK_RUNNING; continue; 五、系统测试及调试1、实际测试数据 /*程序演示结果如下：*/ ENTER THE MAX NUMER FOR THE REQUESTED RESOURCE: ID REQUESTED 1 3 2 5 3 7 4 9 ALOG
23、RITHM Random(R) Banker(B) ANY OTHER KEY TO QUIT r NOW-BANKER ALOGRITHM ENTER THE APPLY FOR THE PROCESS 4 2 2 resourceare accepted for 4 ENTER THE APPLY FOR THE PROCESS 3 3 3 resourceare accepted for 3 ENTER THE APPLY FOR THE PROCESS 2 5 5 resourceare accepted for 2 process 2 has succeed! ENTER THE A
24、PPLY FOR THE PROCESS 1 2 2 resourceare accepted for 1 ENTER THE APPLY FOR THE PROCESS 4 4 4 is waiting ENTER THE APPLY FOR THE PROCESS 3 2 2 resourceare accepted for 3 ENTER THE APPLY FOR THE PROCESS 1 2 beyond the real need! ENTER THE APPLY FOR THE PROCESS 1 1 1 resourceare accepted for 1 process 1 has succeed! LOCKED! */2、预期的结果3、系统测试结论六、心得体会七、主要参考文献1、张丽芬 刘利雄 王全玉 操作系统实验教程 清华大学出版社2006,32、张尧学.史美林. 计算机操作系统教程.清华大学出版社 2000第2版3、尤晋元.史美林.陈向群. Windows操作系统原理（重点大学计算机教材）.清华大学出版社 2001年8月第1版4、蒋东兴.Windows Sockets网络程序设计大全.清华大学出版社 1999年4月第1版