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

衡阳师范学院衡阳师范学院 操作系统操作系统课程设计课程设计 题题 目目 处理机调度模拟设计处理机调度模拟设计短作业先调短作业先调 度、先来先服务调度、最高响应比调度、先来先服务调度、最高响应比调 度算法度算法 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 1001 班班 学学 号号 10190134 10190136 姓姓 名名 张德旺张德旺 屈金屈金 指导教师指导教师 王玉奇王玉奇 2012 年12 月日 目目 录录 1 1、概述、概述1 1 1.1、设计目的.1 1.2、设计内容.1 1.3、开发环境.1 1.4、任务分配.1 2 2、需求分析、需求分析2 2 2.1、死锁概念：2 2.2、关于死锁的一些结论：2 2.3、资源分类：2 2.4、产生死锁的四个必要条件：3 2.5、 死锁的解决方案.3 2.5.1 产生死锁的例子3 2.5.2 死锁预防: .4 2.6安全状态与不安全状态5 3 3、数据结构设计、数据结构设计5 5 3.1、定义全局变量5 3.2、函数声明5 3.3、主函数结构6 4 4、算法的实现、算法的实现7 7 4.1、初始化7 4.2、银行家算法7 4.3、安全性检查算法7 4.4、程序模块划分8 4.5 程序运行结果显示.9 4.6、各算法流程图11 4.7、源程序清单12 5 5、心得与体会：、心得与体会：2222 6 6、参考文献、参考文献2222 1 1 1、概述、概述 1.11.1、设计目的、设计目的 （1）了解多道程序系统中，多个进程并发执行的资源分配。 （2）掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。 （3）掌握预防死锁的方法，系统安全状态的基本概念。 （4）掌握银行家算法，了解资源在进程并发执行中的资源分配策略。 （5）理解死锁避免在当前计算机系统不常使用的原因。 1.21.2、设计内容、设计内容 利用银行家算法来实现资源的分配。先对用户提出的请求进行合法性检查，再进行预 分配，利用安全性检查算法进行安全性检查。 1.31.3、开发环境、开发环境 操作系统编译环境生成文件 Windows7Visual C+6.0Bank.exe Windows7Code blocks 10.05Bank.exe 源文件：Bank.cpp 1.1.4 4、任务分配、任务分配 设计人员设计任务 刘新宇负责主要代码编写 丁正宁负责程序意见提取和进度安排 谭琼斐课程设计报告主要的书写 王正香心得与体会的书写 2 2 2、需求分析、需求分析 2.12.1、死锁概念：、死锁概念： 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率， 提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock),是指多个进 程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态 时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被 该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死 锁，这一组进程就称为死锁进程。 2.22.2、关于死锁的一些结论：、关于死锁的一些结论： a 参与死锁的进程最少是两个（两个以上进程才会出现死锁） b 参与死锁的进程至少有两个已经占有资源 c 参与死锁的所有进程都在等待资源 d 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 2.32.3、资源分类：、资源分类： 永久性资源： 可以被多个进程多次使用（可再用资源） a 可抢占资源 b 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请分配使用释放”模式 3 2.42.4、产生死锁的四个必要条件：、产生死锁的四个必要条件： 1、互斥使用（资源独占） 一个资源每次只能给一个进程使用 2、不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动 态分配） 4、循环等待 存在一个进程等待队列 P1 , P2 , , Pn, 其中 P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，Pn 等待 P1 占有的资源，形 成一个进程等待环路 2.52.5、 死锁的解决方案死锁的解决方案 2.5.1 产生死锁的例子 申请不同类型资源产生死锁 P1： 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 4 P2： 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 申请同类资源产生死锁（如内存） 设有资源 R，R 有 m 个分配单位，由 n 个进程 P1,P2,Pn（n m）共享。假设每个 进程对 R 的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 m=2，n=3 资源分配不当导致死锁产生 2.5.2 死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的 四个必要条件之一 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而 变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源 均可满足时才给予一次性分配 破坏“循环等待”条件 5 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否 则操作系统不予分配。 2.62.6安全状态与不安全状态安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列 P1，Pn，则系统处于 安全状态。一个进程序列P1，Pn是安全的，如果对于每一个进程 Pi(1in），它 以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j “ #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; i9) cout9); for(int i=0; i=Allocationij) Needij = Maxij-Allocationij; /计算还需求量 else Needij=0;/最大需求量小于已分配量时还需求量为 0,即此类资源已足 够不需再申请 cout=Needij) /可用大于等于需求 counter=counter+1;/记数 if(counter=m) */ /算法二： for (j=0; j=Needij); /可用大于等于需求 else counter=1; break; if(counter!=1) /进程的每类资源量都符合条件 Workj=Needij 条件二 pl=i; /存储安全序列 15 Finishi=1; /标志为可分配 for (j=0; j=Needi j i= -1; /从第一个进程开始继续寻找满足条件一二的进程 i+; /for 循环继续寻找 /=显示分配情况函数 = void showdata() /函数 showdata,输出当前资源分配情况 int i,j; /局部变量 int Ally; /各种资源的总数量 int l2; /局部变量 l1, coutn-1) /输入异常处理 coutNeedkj) /申请大于需求量时出错，提示重新输入（贷 款数目不允许超过需求数目） coutAvailablej) /申请大于可利用量， 应该阻塞等待 coutNeedkj); /RequestjAvailablej| /改变 Avilable、Allocation、Need 的值 for (j=0; j“b; cout“进程“(“pi“)“; for (i=0; in; i+) Finishi=0; /所有进程置为未分配状态 coutendlendl; bank(); /银行家算法函数调用 return 0; 5、心得与体会：心得与体会： “银行家算法的模拟实现”是本学期操作系统课程唯一的课程设计。在设计此程序的 过程中，我遇到过许多问题，也学到了很多东西。本程序的设计实现主要是用 C+语言实 现，通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设 计过程中的问题的考虑解决，在 C+学习上也有了很大的进步。程序设计过程中开始遇到 的最大的问题是算法的结构设计问题，课本上只给了设计要求及简单的算法，要真正实现 还需要考虑很多方面。在算法的数据结构设计上考虑了很长时间。在程序设计中先后参考 了很多网络资料，也参考了一些别人写的的程序，综合这些算法思想和自己的思路对程序 做了很好的设计方式，对一些算法的优越性等也作了一些考虑。此外考虑最多的就是异常 错误处理的设计。一个好的程序必须能在各种环境下都有其相应的处理方式，至少能应对 一些常见的可能发生的错误。比如一般的要求输入为数字时，如果输入了一个非数字字符， 程序就会立即出错无法继续运行，本程序针对这个问题设计了一个 shuzi();函数进行处理， 处理方式为：接受键盘输入的字符为字符串，然后对字符串的每个字符进行判断是否为数 字，如果有非数字字符出现则提示出错并要求重新输入。又如在判断是否继续时要求输入 Y/N 时，按一般的方式，如果输入为多个字符，则多余的字符会保存在缓冲区，到下次要 求输入时输入而导致出错，对此问题设计处理方式为接受输入字符保存为串然后只取其首 字符进