处理机调度模拟设计——短作业先调度先来先服务调度最高响应比调度算法

1、衡阳师范学院操作系统课程设计  题 目处理机调度模拟设计短作业先调度、先来先服务调度、最高响应比调度算法专 业计算机科学与技术班 级1001班学 号10190134 10190136姓 名张德旺 屈金指导教师王玉奇2012年12月日目 录1、概述11.1、设计目的11.2、设计内容11.3、开发环境11.4、任务分配12、需求分析22.1、死锁概念：22.2、关于死锁的一些结论：22.3、资源分类：22.4、产生死锁的四个必要条件：32.5、 死锁的解决方案32.5.1 产生死锁的例子3死锁预防:42.6安全状态与不安全状态53、数据结构设计53.1、定义全局变量53.2、函数声明5

2、3.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、设计内容 利用银行家算法来实现资源的分

3、配。先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。1.3、开发环境 操作系统编译环境生成文件Windows7Visual C+6.0Bank.exeWindows7Code blocks 10.05Bank.exe源文件：Bank.cpp 1.4、任务分配设计人员设计任务刘新宇负责主要代码编写丁正宁负责程序意见提取和进度安排谭琼斐课程设计报告主要的书写王正香心得与体会的书写2、需求分析2.1、死锁概念：在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadloc

4、k),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 2.2、关于死锁的一些结论： a 参与死锁的进程最少是两个（两个以上进程才会出现死锁） b 参与死锁的进程至少有两个已经占有资源 c 参与死锁的所有进程都在等待资源 d 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统

5、崩溃。  2.3、资源分类： 永久性资源： 可以被多个进程多次使用（可再用资源） a 可抢占资源 b 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请分配使用释放”模式   2.4、产生死锁的四个必要条件：1、互斥使用（资源独占） 一个资源每次只能给一个进程使用 2、不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配） 4、循环等待 存在一个进程等待队列

6、 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

7、资源分配不当导致死锁产生 2.5.2死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 2.6安全状态与不安全

8、状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的) 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。 3、数据结构设计3.1、定义全局变量const int x=50,y=100; /定义常量，便于修改int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量i

9、nt 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(); /安

10、全性算法函数void bank(); /银行家算法函数void showdata(); /函数showdata,输出当前资源分配情况void sign(); /签名函数3.3、主函数结构int main() system("color 06f"); /设置当前窗口的背景色和前景色 0 = 黑色 8 = 灰色 cout<<endl<<endl; cout<<"tt="<<endl; cout<<"tt| |"<<endl; cout<<"tt|

11、 模拟银行家算法 |"<<endl; cout<<"tt| |"<<endl; cout<<"tt| 作者：lxy |"<<endl; cout<<"tt| |"<<endl; cout<<"tt="<<endl<<endl<<endl<<endl; chushihua(); /初始化函数调用 cout<<endl<<endl; showd

12、ata(); /输出初始化后的状态/=判断当前状态的安全性= safe(); /安全性算法函数调用 if (l<n) cout<<"n当前状态不安全，无法申请,程序退出!"<<endl; cout<<endl; system("pause"); sign(); /调用签名函数 return 0; / break; else int i; l=0; cout<<"n安全的状态!"<<endl; cout<<"安全序列为: " cout<

13、;<endl<<"进程"<<"("<<p0<<")" /输出安全序列，考虑显示格式，先输出第一个 for (i=1; i<n; i+) cout<<"=>>"<<"进程"<<"("<<pi<<")" for (i=0; i<n; i+) Finishi=0; /所有进程置为未分配状态 cout<<endl&l

14、t;<endl; bank(); /银行家算法函数调用 return 0;4、算法的实现4.1、初始化 调用函数 chushihua()，输入进程数量，资源种类，各资源可用数量，各进程已分配、最大需求各资源数量等。4.2、银行家算法 调用bank()函数，输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。4.3、安全性检查算法 调用函数safe()检查当前资源分配状态。 （1）设置两个临时变量。FINISHN记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可设为1，也可设为其它非零值以表示执行的先后次序。WORKM记录模拟执行中资源

15、的回收情况，初值为AVAILABLEM的值。（2）在进程中查找符合以下条件的进程。条件1：FINISHI=0条件2：NEEDIJ=WORKJ（3）如果查找成功则进行资源的模拟回收，语句如下：WORKJ=WORKJ+ALLOCATIONIJ；FINISHI=1 或查找到的顺序号；（4）如果查找不成功，则检查所有进程的FINISH，如果有一个为0，则系统不为0，返回不成功标志。否则返回成功标志。4.4、程序模块划分本程序共有以下六个模块： 4.4.1、字符判断模块：判断输入的字符是否为数字，如果不是则提示出错并重新输入，主要处理输入为非数字时程序出现运行错误现象。此模块功能由数字判断函数（ int

16、 shuzi(int sz); ）实现。 4.4.2、程序初始化模块：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。此模块功能在系统初始化函数（void chushihua(); ）中实现。 4.4.3、当前安全性检查模块：用于判断当前状态安全性，根据不同地方的调用提示处理不同，在安全性算函数（void safe(); ）中实现。 4.4.4、银行家算法模块：进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程，在银行家算法函数（void bank();）中实现。 4.4.5、显示分配模块：显示

17、当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量，在显示分配情况函数（void showdata(); ）中实现。 4.4.6、签名模块：用于程序结束时显示程序版权声明签名等，在签名函数（void sign(); ）中实现。4.5 程序运行结果显示4.6、各算法流程图 开始清除所有进程“能运行完成”的标志系统剩余资源数与“能运行完”标志为0的进程尚需资源数比较，找出一个系统能满足要求的进程。对申请者预分配找到?设置该进程“能运行完”标志并假设它归还全部资源。检查是否有“能运行完”标志尚未设置的进程。有?分配不安全

18、不能分配Y分配安全进行实际分配N结束4.7、源程序清单#include <iostream>#include <stdio.h>#include <stdlib.h>#include <conio.h>#include <string.h>using namespace std;/=定义全局变量=const int x=50,y=100; /定义常量，便于修改int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int

19、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

20、s; / do /输入赌注，只能输入数字 cin>>temp; len=strlen(temp); /取字符长度 for(int i=0; i<len; i+) s= *(temp+i); if(s<'0' | s>'9') cout<<" 笨蛋，输错了! 你输入的是数字吗?! nn" cout<<"请重新输入：" break; while(s<'0' | s>'9'); for(int i=0; i<len; i+)

21、/输入字符串转化为整形数字 int t=1; for(int j=1; j<len-i; j+) t*=10; sz+=(*(temp+i)-48)*t; return sz;/=系统初始化函数=void chushihua() /=系统初始化输入= cout<<"% 程序开始，系统初始化输入 %"<<endl; /<<endl cout<<"="<<endl<<endl; cout<<"请输入进程的数量: "/从此开始输入有关数据 n=shuz

22、i(n); cout<<"请输入资源种类数: " m=shuzi(m); cout<<endl<<endl<<"请输入各种资源可利用的数量( "<<m<<" 种): "<<endl; cout<<endl; for (j=0; j<m; j+) cout<<" 输入资源 "<<j<<" 可利用的数量Available"<<j<<&quo

23、t;: " Availablej=shuzi(Availablej); Workj=Availablej; /初始化Workj cout<<endl; cout<<"请输入各进程当前已分配的资源数量Allocation"<<n<<""<<m<<": "<<endl<<endl; for (i=0; i<n; i+) for (j=0; j<m; j+) cout<<" 请输入进程 "&l

24、t;<i<<" 当前已分配的资源 "<<j<<" 数量: " Allocationij=shuzi(Allocationij); cout<<endl; Finishi=0;/初始化Finishi cout<<endl<<endl; cout<<"请输入各进程对各类资源的最大需求数Max"<<n<<""<<m<<": "<<endl<<

25、endl; for (i=0; i<n; i+) for (j=0; j<m; j+) cout<<" 请输入进程 "<<i<<" 对资源 "<<j<<" 的最大需求数: " Maxij=shuzi(Maxij); if(Maxij>=Allocationij) Needij = Maxij-Allocationij; /计算还需求量 else Needij=0;/最大需求量小于已分配量时还需求量为0,即此类资源已足够不需再申请 cout<<en

26、dl; cout<<endl<<"% 初始化完成! %"<<endl;/=安全性算法函数=void safe() l=0; for (i=0; i<n;) /i+ if (Finishi=0) /寻找Finishi=0的进程 条件一 counter=0; /记数器 /* 算法一： for (j=0; j<m; j+) if (Workj>=Needij) /可用大于等于需求 counter=counter+1;/记数 if(counter=m) */ /算法二： for (j=0; j<m; j+) if (Wor

27、kj>=Needij); /可用大于等于需求 else counter=1; break; if(counter!=1) /进程的每类资源量都符合条件Workj>=Needij 条件二 pl=i; /存储安全序列 Finishi=1; /标志为可分配 for (j=0; j<m; j+) Workj=Workj+Allocationij; /释放资源 l=l+1; /记数,当L=N时说明满足安全序列,即都符合条件Workj>=Needij i= -1; /从第一个进程开始继续寻找满足条件一二的进程 i+; /for循环继续寻找 /=显示分配情况函数 =void show

28、data() /函数showdata,输出当前资源分配情况 int i,j; /局部变量 int Ally; /各种资源的总数量 int l2; /局部变量 l1, cout<<"="<<endl<<endl; cout<<"% 系统当前状态如下：%"<<endl<<endl; cout<<"% 各种资源的总数量(all):"<<endl; for (j=0; j<m; j+) cout<<" 资源"&

29、lt;<j<<": " Allj=Availablej; /初始化 先赋值加上可利用量 for (i=0; i<n; i+) Allj+=Allocationij; /再加上每个进程已分配量计算J类资源总量 cout<<Allj<<" " if (j+1)%5=0 ) cout<<endl; /每行显示五个 && j!=0 cout<<endl<<endl; cout<<"% 系统目前各种资源可用的数为(available):&quo

30、t;<<endl; for (j=0; j<m; j+) cout<<" 资源"<<j<<": "<<Availablej<<" " if(j+1)%5=0) cout<<endl; /每行最多显示五个 && j!=0 cout<<endl<<endl; cout<<"% 各进程已经得到的资源量(allocation): "<<endl; / l1=0; /归零

31、for(i=0; i<=m/5; i+) /设计每行最多显示五种资源 for (j=i*5; j<i*5+5 && j<m; j+) cout<<" 资源"<<j; cout<<endl; for(l2=0; l2<n; l2+) cout<<"进程"<<l2<<":" for (j=i*5; j<i*5+5 && j<m; j+) cout<<Allocationl2j<<

32、;" " cout<<endl; cout<<endl; cout<<"% 各进程还需要的资源量(need):"<<endl; /l1=0; for(i=0; i<=m/5; i+) /设计每行显示五种资源 for (j=i*5; j<i*5+5 && j<m; j+)cout<<" 资源"<<j; cout<<endl; for(l2=0; l2<n; l2+) cout<<"进程&quo

33、t;<<l2<<":" for (j=i*5; j<i*5+5 && j<m; j+)cout<<Needl2j<<" " cout<<endl; cout<<endl; cout<<"="<<endl; cout<<endl; system("pause"); / 暂停/=签名函数 =void sign() system("cls"); / 清屏 cout&l

34、t;<endl<<endl<<endl<<endl<<endl<<endl; cout<<"tt ="<<endl; cout<<"tt = ="<<endl; cout<<"tt = 本程序由刘新宇制作 ="<<endl; cout<<"tt = 谢谢你的使用 ="<<endl; cout<<"tt = 版权没有，随便复制 =&qu

35、ot;<<endl; cout<<"tt = ="<<endl; cout<<"tt = 衡阳师院 12.5 ="<<endl; cout<<"tt = ="<<endl; cout<<"tt ="<<endl; cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<end

36、l<<endl; / getch(); /等待键盘输入，不返回任何值，用于设置程序运行界面 system("pause");/暂停 比较两种方式 /* 经过在不同的编辑器中调试发现,不同的调试器对函数执行的顺序有差别 如在此处使用 getch() 和 system("pause") 函数时,在visual c+6.0中先执行此函数再显示, 而在dev-c+ 中则按顺序执行 对此问题我在很多地方搜索查找均未找到满意的答案,本次换用调试器才发现理解-4.29 本次调试格式时，将换行命令 "n" 改为 endl 时，发现 sys

37、tem("pause") 函数执行变为顺序 执行，由此领悟到 "n" 命令和system("pause")调用了一样系统函数，在调用的顺序上system("pause") 优先所以它就先执行了 查找了一下相关帮助： 在OSTREAM.H中有这样的一个inline函数： inline _CRTIMP ostream& _cdecl endl(ostream& _outs) return _outs << 'n' << flush; 也就是说 endl= retu

38、rn _outs << 'n' << flush; endl除了写'n'进外，还调用flush函数，刷新缓冲区，把缓冲区里的数据写入文件或屏幕， 如果考虑效率就用'n' */ cout<<"ttt "/=银行家算法函数=void bank() cout<<"="<<endl<<endl; cout<<"% 以下开始为进程进行资源分配申请 %"<<endl<<endl; /=申请资源

39、= int k=0;/用于输入进程编号 bool r=false; / 初值为假，输入Y继续申请则置为真 do /输入请求 cout<<"请输入申请资源的进程编号(输入0-"<<n-1<<"之间): " k=shuzi(k); cout<<endl; while(k>n-1) /输入异常处理 cout<<endl<<"您输入了错误的进程号，请重新输入!"<<endl; cout<<endl<<"请输入申请资源的进

40、程编号(输入0-"<<n-1<<"之间): " k=shuzi(k); cout<<endl; cout<<endl<<"请输入该进程申请各类资源的数量: "<<endl; for (j=0; j<m; j+) do /dowhile 循环判断申请输入的情况 cout<<"进程 "<<k<<" 申请资源"<<j<<"的数量:" Requestj=sh

41、uzi(Requestj); cout<<endl; if(Requestj>Needkj) /申请大于需求量时出错，提示重新输入（贷款数目不允许超过需求数目） cout<<"申请大于需要量!"<<endl; cout<<"您申请资源"<<j<<"的数量为"<<Requestj<<",大于进程"<<k<<"对该资源需求量"<<Needkj<<&qu

42、ot;。"<<endl; cout<<"请重新输入!"<<endl; else /先判断是否申请大于需求量，再判断是否申请大于可利用量 if(Requestj>Availablej) /申请大于可利用量， 应该阻塞等待 cout<<"n没有那么多资源，目前可利用资源"<<j<<"数量为"<<Availablej<<",本次申请不成功，进程等待!"<<endl; Finishk=0; /该进程等

43、待 goto ppp; /goto语句 跳转，结束本次申请 while(Requestj>Needkj); /Requestj>Availablej| /改变Avilable、Allocation、Need的值 for (j=0; j<m; j+) Availablej = Availablej-Requestj; Allocationkj = Allocationkj+Requestj; Needkj = Needkj-Requestj; Workj = Availablej; /判断当前状态的安全性 safe(); /调用安全性算法函数 if (l<n) l=0;

44、cout<<"n当前状态不安全,不予分配!"<<endl; /恢复数据 for (j=0; j<m; j+) Availablej = Availablej+Requestj; Allocationkj = Allocationkj-Requestj; Needkj = Needkj+Requestj; Workj = Availablej; for (i=0; i<n; i+) Finishi=0; /进程置为未分配状态 else l=0; cout<<"n申请资源成功!"<<endl;/=

45、/* /如果该进程所有需要的资源都已申请到，即NEEDkj均为零，则进程可以执行，执行完后需释放其所有拥有的资源 /算法一： for(j=0;j<m;j+) if(Needkj=0) l=l+1; if(l=m) /此处借用 l 做下计数器 for (j=0;j<m;j+) /释放该进程的所有资源 Availablej=Availablej+Maxkj; Allocationkj=0; l=0; /归零 */算法二： （相对第一种算法节省时间） for(j=0; j<m; j+) if(Needkj=0); else /有一种资源还没全部申请到，则该进程不可执行，不能释放拥有

46、的资源 l=1; /置l为1，作为判断标志 break; if(l!=1) /进程可以执行，则释放该进程的所有资源 for (j=0; j<m; j+) Availablej=Availablej+Allocationkj; Allocationkj=0; cout<<"该进程已得到所有需求资源，执行后将释放其所有拥有资源！"<<endl; l=0; /归零/= cout<<"n安全的状态!"<<endl; cout<<"安全序列为: " cout<<end

47、l<<"进程"<<"("<<p0<<")" /输出安全序列，考虑显示格式，先输出第一个 Finish0=0; for (i=1; i<n; i+) cout<<"=>>"<<"进程"<<"("<<pi<<")" Finishi=0; /所有进程置为未分配状态 cout<<endl<<endl; showdat

48、a(); /显示当前状态 ppp: /申请大于可利用量， 应该阻塞等待,结束本次资源申请，GOTO 语句跳转至此 cout<<endl<<"是否继续申请资源(y/n) ?" char* b=new char; /输入y/n，判断是否继续申请 <<endl cin>>b; cout<<endl; cout<<"="<<endl<<endl; cout<<endl; if(*b='y'|*b='Y') r=true; e

49、lse r=false; /输入非 Y 则令 R =false sign(); /调用签名函数 while (r=true);int main() system("color 06f"); /设置当前窗口的背景色和前景色 0 = 黑色 8 = 灰色 cout<<endl<<endl; cout<<"tt="<<endl; cout<<"tt| |"<<endl; cout<<"tt| 模拟银行家算法 |"<<endl; cout<<"tt| |"<<endl; cout<<"tt| 作者：lxy |"<<endl; c