专业课程设计银行家算法报告.doc

操作系统课程设计 题 目解决机调度模仿设计短作业先调度、先来先服务调度、最高响应比调度算法专 业班 级学 号姓 名指引教师年月日目 录1、概述11.1、设计目11.2、设计内容11.3、开发环境11.4、任务分派12、需求分析22.1、死锁概念：22.2、关于死锁某些结论：22.3、资源分类：22.4、产生死锁四个必要条件：32.5、死锁解决方案32.5.1 产生死锁例子32.5.2死锁防止:42.6安全状态与不安全状态53、数据构造设计53.1、定义全局变量53.2、函数声明53.3、主函数构造64、算法实现74.1、初始化74.2、银行家算法74.3、安全性检查算法74.4、程序模块划分84.5 程序运营成果显示94.6、各算法流程图114.7、源程序清单125、心得与体会：226、参照文献221、概述1.1、设计目（1）理解多道程序系统中，各种进程并发执行资源分派。 （2）掌握死锁产生因素、产生死锁必要条件和解决死锁基本办法。 （3）掌握防止死锁办法，系统安全状态基本概念。 （4）掌握银行家算法，理解资源在进程并发执行中资源分派方略。 （5）理解死锁避免在当前计算机系统不常使用因素。1.2、设计内容 运用银行家算法来实现资源分派。先对顾客提出祈求进行合法性检查，再进行预分派，运用安全性检查算法进行安全性检查。1.3、开发环境操作系统编译环境生成文献Windows7Visual C+6.0Bank.exeWindows7Code blocks 10.05Bank.exe源文献：Bank.cpp1.4、任务分派设计人员设计任务刘新宇负责重要代码编写丁正宁负责程序意见提取和进度安排谭琼斐课程设计报告重要书写王正香心得与体会书写2、需求分析2.1、死锁概念：在多道程序系统中，虽可借助于各种进程并发执行，来改进系统资源运用率，提高系统吞吐量，但也许发生一种危险死锁。所谓死锁(Deadlock),是指各种进程在运营中因争夺资源而导致一种僵局(Deadly_Embrace),当进程处在这种僵持状态时，若无外力作用，它们都将无法再向前推动。一组进程中，每个进程都无限等待被该组进程中另一进程所占有资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。2.2、关于死锁某些结论： a参加死锁进程至少是两个（两个以上进程才会浮现死锁） b参加死锁进程至少有两个已经占有资源 c参加死锁所有进程都在等待资源 d参加死锁进程是当前系统中所有进程子集 注：如果死锁发生，会挥霍大量系统资源，甚至导致系统崩溃。 2.3、资源分类： 永久性资源： 可以被各种进程多次使用（可再用资源） a 可抢占资源 b不可抢占资源 暂时性资源：只可使用一次资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请分派使用释放”模式 2.4、产生死锁四个必要条件：1、互斥使用（资源独占） 一种资源每次只能给一种进程使用 2、不可强占（不可剥夺） 资源申请者不能强行从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、祈求和保持（某些分派，占有申请） 一种进程在申请新资源同步保持对原有资源占有（只有这样才是动态申请，动态分派） 4、循环等待 存在一种进程等待队列 P1 ，P2 ， ，Pn， 其中P1等待P2占有资源，P2等待P3占有资源，Pn等待P1占有资源，形成一种进程等待环路 2.5、死锁解决方案 2.5.1 产生死锁例子 申请不同类型资源产生死锁 P1： 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 P2： 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 申请同类资源产生死锁（如内存） 设有资源R，R有m个分派单位，由n个进程P1,P2,Pn（n m）共享。假设每个进程对R申请和释放符合下列原则： * 一次只能申请一种单位 * 满足总申请后才干使用 * 使用完后一次性释放 m=2，n=3 资源分派不当导致死锁产生 2.5.2死锁防止： 定义:在系统设计时拟定资源分派算法，保证不发生死锁。详细做法是破坏产生死锁四个必要条件之一 破坏“不可剥夺”条件 在容许进程动态申请资源前提下规定，一种进程在申请新资源不能及时得到满足而变为等待状态之前，必要释放已占有所有资源，若需要再重新申请 破坏“祈求和保持”条件 规定每个进程在运营前必要一次性申请它所规定所有资源，且仅当该进程所要资源均可满足时才予以一次性分派 破坏“循环等待”条件 采用资源有序分派法： 把系统中所有资源编号，进程在申请资源时必要严格按资源编号递增顺序进行，否则操作系统不予分派。2.6安全状态与不安全状态 安全状态： 如果存在一种由系统中所有进程构成安全序列P1，Pn，则系统处在安全状态。一种进程序列P1，Pn是安全，如果对于每一种进程Pi(1in），它后来尚需要资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处在安全状态 (安全状态一定是没有死锁发生) 不安全状态:不存在一种安全序列，不安全状态一定导致死锁。3、数据构造设计3.1、定义全局变量const int x=50,y=100；/定义常量，便于修改int Availablex；/各种资源可运用数量int Allocationyy；/各进程当前已分派资源数量int Maxyy；/各进程对各类资源最大需求数int Needyy；/还需求矩阵int Requestx；/申请各类资源数量int Workx；/工作向量，表达系统可提供应进程运营所需各类资源数量int Finishy；/表达系统与否有足够资源分派给进程，0为否，1为是int py；/存储安全序列int i,j；/全局变量，重要用于循环语句中int n,m；/n为进程数量,m为资源种类数int l=0,counter=0;3.2、函数声明int shuzi(int sz)；/数字判断函数void chushihua()；/系统初始化函数void safe()；/安全性算法函数void bank()；/银行家算法函数void showdata()；/函数showdata,输出当前资源分派状况void sign()；/签名函数3.3、主函数构造int main() system(color 06f)；/设立当前窗口背景色和前景色 0 = 黑色 8 = 灰色 coutendlendl; couttt=endl; couttt| |endl; couttt| 模仿银行家算法 |endl; couttt| |endl; couttt| 作者：lxy |endl; couttt| |endl; couttt=endlendlendlendl; chushihua()；/初始化函数调用 coutendlendl; showdata()；/输出初始化后状态/=判断当前状态安全性= safe()；/安全性算法函数调用 if (ln) coutn当前状态不安全，无法申请,程序退出!endl; coutendl; system(pause); sign()；/调用签名函数 return 0；/ break; else int i; l=0; coutn安全状态!endl; cout安全序列为：; coutendl进程(p0)；/输出安全序列，考虑显示格式，先输出第一种 for (i=1；in；i+) cout进程(pi); for (i=0；in；i+) Finishi=0；/所有进程置为未分派状态 coutendlendl; bank()；/银行家算法函数调用 return 0;4、算法实现4.1、初始化调用函数 chushihua()，输入进程数量，资源种类，各资源可用数量，各进程已分派、最大需求各资源数量等。4.2、银行家算法 调用bank()函数，输入顾客祈求三元组（I，J，K），为进程I申请K个J类资源。4.3、安全性检查算法调用函数safe()检查当前资源分派状态。（1）设立两个暂时变量。FINISHN记录进程模仿执行结束状态，初值为0，如果可以模仿执行结束，则可设为1，也可设为其他非零值以表达执行先后顺序。WORKM记录模仿执行中资源回收状况，初值为AVAILABLEM值。（2）在进程中查找符合如下条件进程。条件1：FINISHI=0条件2：NEEDIJ=WORKJ（3）如果查找成功则进行资源模仿回收，语句如下：WORKJ=WORKJ+ALLOCATIONIJ；FINISHI=1 或查找到顺序号；（4）如果查找不成功，则检查所有进程FINISH，如果有一种为0，则系统不为0，返回不成功标志。否则返回成功标志。4.4、程序模块划分本程序共有如下六个模块： 4.4.1、字符判断模块：判断输入字符与否为数字，如果不是则提示出错并重新输入，重要解决输入为非数字时程序浮现运营错误现象。此模块功能由数字判断函数（ int shuzi(int sz)；）实现。 4.4.2、程序初始化模块：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可运用数量、各进程各种资源已分派数量、各进程对各类资源最大需求数等。此模块功能在系统初始化函数（void chushihua()；）中实现。 4.4.3、当前安全性检查模块：用于判断当前状态安全性，依照不同地方调用提示解决不同，在安全性算函数（void safe()；）中实现。 4.4.4、银行家算法模块：进行银行家算法模仿实现模块，调用其她各个模块进行银行家算法模仿过程，在银行家算法函数（void bank();）中实现。 4.4.5、显示分派模块：显示当前资源分派详细状况，涉及：各种资源总数量(all)、系统当前各种资源可用数量、各进程已经得到资源数量、各进程还需要资源量，在显示分派状况函数（void showdata()；）中实现。 4.4.6、签名模块：用于程序结束时显示程序版权声明签名等，在签名函数（void sign()；）中实现。4.5 程序运营成果显示4.6、各算法流程图 开始清除所有进程“能运营完毕”标志系统剩余资源数与“能运营完”标志为0进程尚需资源数比较，找出一种系统能满足规定进程。对申请者预分派找到?设立该进程“能运营完”标志并假设它归还所有资源。检查与否有“能运营完”标志尚未设立进程。有?分派不安全不能分派Y分派安全进行实际分派N结束4.7、源程序清单#include #include #include #include #include using namespace std;/=定义全局变量=const int x=50,y=100；/定义常量，便于修改int Availablex；/各种资源可运用数量int Allocationyy；/各进程当前已分派资源数量int Maxyy；/各进程对各类资源最大需求数int Needyy；/还需求矩阵int Requestx；/申请各类资源数量int Workx；/工作向量，表达系统可提供应进程继续运营所需各类资源数量int Finishy；/表达系统与否有足够资源分派给进程，0为否，非0为是int py；/存储安全序列int i,j;int n,m；/n为进程数量,m为资源种类数int l=0,counter=0;/=数字判断函数=int shuzi(int sz) /输入数据并判断与否为数字 char *temp; temp=new char；/暂时指针，存储输入字符 int len；/存储取字符长度 sz=0 ；/清零 char s；/ do /输入赌注，只能输入数字 cintemp; len=strlen(temp)；/取字符长度 for(int i=0；ilen；i+) s= *(temp+i); if(s9) cout 笨蛋，输错了！你输入是数字吗?！nn; cout请重新输入：; break; while(s9); for(int i=0；ilen；i+) /输入字符串转化为整形数字 int t=1; for(int j=1；jlen-i；j+) t*=10; sz+=(*(temp+i)-48)*t; return sz;/=系统初始化函数=void chushihua() /=系统初始化输入= cout% 程序开始，系统初始化输入 %endl；/endl cout=endlendl; cout请输入进程数量：;/从此开始输入关于数据 n=shuzi(n); cout请输入资源种类数：; m=shuzi(m); coutendlendl请输入各种资源可运用数量( m 种)：endl; coutendl; for (j=0；jm；j+) cout 输入资源 j 可运用数量Availablej：; Availablej=shuzi(Availablej); Workj=Availablej；/初始化Workj coutendl; cout请输入各进程当前已分派资源数量Allocationnm：endlendl; for (i=0；in；i+) for (j=0；jm；j+) cout 请输入进程 i 当前已分派资源 j 数量：; Allocationij=shuzi(Allocationij); coutendl; Finishi=0;/初始化Finishi coutendlendl; cout请输入各进程对各类资源最大需求数Maxnm：endlendl; for (i=0；in；i+) for (j=0；jm；j+) cout 请输入进程 i 对资源 j=Allocationij) Needij = Maxij-Allocationij；/计算还需求量 else Needij=0;/最大需求量不大于已分派量时还需求量为0,即此类资源已足够不需再申请 coutendl; coutendl% 初始化完毕！%endl;/=安全性算法函数=void safe() l=0; for (i=0；in;) /i+ if (Finishi=0) /寻找Finishi=0进程 条件一 counter=0；/记数器 /* 算法一： for (j=0；j=Needij) /可用不不大于等于需求 counter=counter+1;/记数 if(counter=m) */ /算法二： for (j=0；j=Needij)；/可用不不大于等于需求 else counter=1; break; if(counter!=1) /进程每类资源量都符合条件Workj=Needij 条件二 pl=i；/存储安全序列 Finishi=1；/标志为可分派 for (j=0；j=Needij i= -1；/从第一种进程开始继续寻找满足条件一二进程 i+；/for循环继续寻找 /=显示分派状况函数 =void showdata() /函数showdata,输出当前资源分派状况 int i,j；/局部变量 int Ally；/各种资源总数量 int l2；/局部变量 l1, cout=endlendl; cout% 系统当前状态如下：%endlendl; cout% 各种资源总数量(all):endl; for (j=0；jm；j+) cout 资源j：; Allj=Availablej；/初始化 先赋值加上可运用量 for (i=0；in；i+) Allj+=Allocationij；/再加上每个进程已分派量计算J类资源总量 coutAllj ; if (j+1)%5=0 ) coutendl；/每行显示五个 & j!=0 coutendlendl; cout% 系统当前各种资源可用数为(available):endl; for (j=0；jm；j+) cout 资源j：Availablej ; if(j+1)%5=0) coutendl；/每行最多显示五个 & j!=0 coutendlendl; cout% 各进程已经得到资源量(allocation)：endl; / l1=0；/归零 for(i=0；i=m/5；i+) /设计每行最多显示五种资源 for (j=i*5；ji*5+5 & jm；j+) cout 资源j; coutendl; for(l2=0；l2n；l2+) cout进程l2:; for (j=i*5；ji*5+5 & jm；j+) coutAllocationl2j ; coutendl; coutendl; cout% 各进程还需要资源量(need):endl; /l1=0; for(i=0；i=m/5；i+) /设计每行显示五种资源 for (j=i*5；ji*5+5 & jm；j+)cout 资源j; coutendl; for(l2=0；l2n；l2+) cout进程l2:; for (j=i*5；ji*5+5 & jm；j+)coutNeedl2j ; coutendl; coutendl; cout=endl; coutendl; system(pause)；/ 暂停/=签名函数 =void sign() system(cls)；/ 清屏 coutendlendlendlendlendlendl; couttt =endl; couttt = =endl; couttt = 本程序由刘新宇制作 =endl; couttt = 谢谢你使用 =endl; couttt = 版权没有，随便复制 =endl; couttt = =endl; couttt = 衡阳师院 12.5 =endl; couttt = =endl; couttt =endl; coutendlendlendlendlendlendlendlendlendl; / getch()；/等待键盘输入，不返回任何值，用于设立程序运营界面 system(pause);/暂停 比较两种方式 /* 通过在不同编辑器中调试发现,不同调试器对函数执行顺序有差别 如在此处使用 getch() 和 system(pause) 函数时,在visual c+6.0中先执行此函数再显示, 而在dev-c+ 中则按顺序执行 对此问题我在诸多地方搜索查找均未找到满意答案,本次换用调试器才发现理解-4.29 本次调试格式时，将换行命令 n 改为 endl 时，发现 system(pause) 函数执行变为顺序 执行，由此领悟到 n 命令和system(pause)调用了同样系统函数，在调用顺序上system(pause) 优先因此它就先执行了 查找了一下有关协助： 在OSTREAM.H中有这样一种inline函数： inline _CRTIMP ostream& _cdecl endl(ostream& _outs) return _outs n flush； 也就是说 endl= return _outs n flush; endl除了写n进外，还调用flush函数，刷新缓冲区，把缓冲区里数据写入文献或屏幕， 如果考虑效率就用n */ coutttt ;/=银行家算法函数=void bank() cout=endlendl; cout% 如下开始为进程进行资源分派申请 %endlendl; /=申请资源= int k=0;/用于输入进程编号 bool r=false；/ 初值为假，输入Y继续申请则置为真 do /输入祈求 cout请输入申请资源进程编号(输入0-n-1之间)：; k=shuzi(k); coutn-1) /输入异常解决 coutendl您输入了错误进程号，请重新输入!endl; coutendl请输入申请资源进程编号(输入0-n-1之间)：; k=shuzi(k); coutendl; coutendl请输入该进程申请各类资源数量：endl; for (j=0；jm；j+) do /dowhile 循环判断申请输入状况 cout进程 k 申请资源j数量:; Requestj=shuzi(Requestj); coutNeedkj) /申请不不大于需求量时出错，提示重新输入（贷款数目不容许超过需求数目） cout申请不不大于需要量!endl; cout您申请资源j数量为Requestj,不不大于进程k对该资源需求量Needkj。endl; cout请重新输入!Availablej) /申请不不大于可运用量， 应当阻塞等待 coutn没有那么多资源，当前可运用资源j数量为Availablej,本次申请不成功，进程等待!Needkj)； /RequestjAvailablej| /变化Avilable、Allocation、Need值 for (j=0；jm；j+) Availablej = Availablej-Requestj; Allocationkj = Allocationkj+Requestj; Needkj = Needkj-Requestj; Workj = Availablej; /判断当前状态安全性 safe()；/调用安全性算法函数 if (ln) l=0; coutn当前状态不安全,不予分派!endl; /恢复数据 for (j=0；jm；j+) Availablej = Availablej+Requestj; Allocationkj = Allocationkj-Requestj; Needkj = Needkj+Requestj; Workj = Availablej; for (i=0；in；i+) Finishi=0；/进程置为未分派状态 else l=0; coutn申请资源成功!endl;/= /* /如果该进程所有需要资源都已申请到，即NEEDkj均为零，则进程可以执行，执行完后需释放其所有拥有资源 /算法一： for(j=0;jm;j+) if(Needkj=0) l=l+1; if(l=m) /此处借用 l 做下计数器 for (j=0;jm;j+