计算机操作系统课后习题答案第三章(第四版)
第三章处理机调度与死锁 1,高级调度与低级调度的主要任务是什么?为什么要引入中级调度? 【解】(1)高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存,并为它们创建进程,分配必要的资源,然后再将新创建的进程排在就绪队列上,准备执行。(2)低级调度主要任务是决定就绪队列中的哪个进程将获得处理机,然后由分派程序执行把处理机分配给该进程的操作。(3)引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。为此,应使那些暂时不能运行的进程不再占用宝贵的内存空间,而将它们调至外存上去等待,称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件,且内存又稍有空闲时,由中级调度决定,将外存上的那些重又具备运行条件的就绪进程重新调入内存,并修改其状态为就绪状态,挂在就绪队列上,等待进程调度。 3、何谓作业、作业步和作业流? 【解】作业包含通常的程序和数据,还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。 作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流;在操作系统的控制下,逐个作业进程处理,于是形成了处理作业流。 4、在什么情冴下需要使用作业控制块JCB?其中包含了哪些内容? 【解】每当作业进入系统时,系统便为每个作业建立一个作业控制块JCB,根据作业类型将它插入到相应的后备队列中。 JCB 包含的内容通常有:1) 作业标识2)用户名称3)用户账户4)作业类型(CPU 繁忙型、I/O芳名型、批量型、终端型)5)作业状态6)调度信息(优先级、作业已运行)7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等 5.在作业调度中应如何确定接纳多少个作业和接纳哪些作业? 【解】作业调度每次接纳进入内存的作业数,取决于多道程序度。应将哪些作业从外存调入内存,取决于采用的调度算法。最简单的是先来服务调度算法,较常用的是短作业优先调度算法和基于作业优先级的调度算法。 7.试说明低级调度的主要功能。 【解】(1)保存处理机的现场信息(2)按某种算法选取进程(3)把处理机分配给进程。 8、在抢占调度方式中,抢占的原则是什么? 【解】剥夺原则有:(1)时间片原则各进程按时间片运行,当一个时间片用完后,便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统,以及要求较高的批处理系统。(2)优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时,如果其优先权比正在执行进程的优先权高,便停止正在执行的进程,将处理机分配给优先权高的进程,使之执行。(3)短作业(进程)优先原则当新到达的作业(进程)比正在执行的作业(进程)明显地短时,将剥夺长作业(进程)的执行,将处理机分配给短作业(进程),使之优先执行。 9、选择调度方式和调度算法时,应遵循的准则是什么? 【解】应遵循的准则有(1)面向用户的准则:周转时间短,响应时间快,截止时间的保证,优先权准则。(2)面向系统的准则:系统吞吐量高,处理机利用率好,各类资源的平衡利用。 10、在批处理系统、分时系统和实时系统中,各采用哪几种进程(作业)调度算法? 【解】 批处理系统:FCFS算法、最小优先数优先算法、抢占式最小优先数优先算法 2 分时系统:可剥夺调度、轮转调度 实时系统:时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占的优先权调度算法、立即抢占的优先权调度。 11、何谓静态和动态优先权?确定静态优先权的依据是什么? 【解】静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。动态优先权是指,在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。确定静态优先权的依据是:(1)进程类型,通常系统进程的优先权高于一般用户进程的优先权。(2)进程对资源的需要。(3)用户要求,用户进程的紧迫程度及用户所付费用的多少来确定优先权的。 12、试比较FCFS和SPF两种进程调度算法。 【解】FCFS算法按照作业提交或进程变为就绪状态的先后次序,分派CPU。当前作业或进程占有CPU,直到执行完或阻塞,才让出CPU。在作业或进程唤醒后,并不立即恢复执行,通常等到当前作业或进程让出CPU。FCFS比较有利于长作业,而不利于短作业;有利于CPU繁忙的作业,而不利于I/O繁忙的作业。SPF有利于短进程调度,是从就绪队列中选出一估计运行时间最短的进
操作系统+磁盘调度算法
目录 目录 ........................................................ 错误!未定义书签。1.课程设计目的.............................................. 错误!未定义书签。 编写目的................................................. 错误!未定义书签。2.课程设计内容.............................................. 错误!未定义书签。 设计内容................................................. 错误!未定义书签。3.课程设计方案.............................................. 错误!未定义书签。 模块划分................................................. 错误!未定义书签。 模块调用关系图........................................... 错误!未定义书签。 子模块程序流程图......................................... 错误!未定义书签。4.测试数据和结果............................................ 错误!未定义书签。 测试数据................................................. 错误!未定义书签。 测试结果................................................. 错误!未定义书签。 测试抓图................................................. 错误!未定义书签。5.参考文献.................................................. 错误!未定义书签。6.总结...................................................... 错误!未定义书签。 设计体会................................................. 错误!未定义书签。 结束语................................................... 错误!未定义书签。7.程序使用说明书............................................ 错误!未定义书签。8.程序源代码................................................ 错误!未定义书签。
操作系统短作业优先调度算法
课程设计 采用短作业优先调度算法调度程序 学号: 姓名: 专业: 指导老师: 日期:
目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13)
摘要 在多道程序环境下,主存中有着多个进程,其数目往往多于处理机数目。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源,提高处理机的利用率及改善系统性能(吞吐量、响应时间),在很大程度上取决于处理机调度性能的好坏,因而,处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中,一个作业被提交后必须经过处理机调度后,方能获得处理机执行。对于批量型作业而言,通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业,根据作业控制块的信息,按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的,短作业优先(SJF)便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。
一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节,它为学生提供了一个既动手又动脑,将课本上的理论知识和实际有机的结合一起,独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB,其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据(要求存放在外部文件中)进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态:就绪、执行(由于不要求设置互斥资源与进程间同步关系,故只有两种状态) 5. 采用可视化界面,可在进程调度过程中随时暂停调度,查看当前进程的状态以及相应的阻塞队列
几种操作系统调度算法
保证调度算法 基本思想:向用户做出明确的性能保证,然后去实现它.如你工作时有n个用户的登录,则你将获得cpu处理能力的1/n 算法实现:跟踪计算各个进程已经使用的cpu时间和应该获得的cpu时间,调度将转向两者之比最低的进程 五,保证调度算法 思想:向用户做出明确的性能保证,然后去实现它. 算法:容易实现的一种保证是:当工作时己有n个用户登录在系统,则将获得CPU处理能力的1/n.类似的,如果在一个有n个进程运行的用户系统中,每个进程将获得CPU处理能力的1/n. 实现方法:OS应记录及计算,各个进程在一定时间段内,已经使用的CPU时间和应该得到的CPU时间,二者之比小者优先级高. 5. 保证调度 一种完全不同的调度算法是向用户作出明确的性能保证,然后去实现它。一种很实际并很容易实现的保证是:若用户工作时有n个用户登录,则用户将获得CPU处理能力的1/n。类似地,在一个有n个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得1/n的CPU时间。看上去足够公平了。 为了实现所做的保证,系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间,即自创建以来的时间除以n。由于各个进程实际获得的CPU时间是已知的,所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。比率为0.5说明一个进程只获得了应得时间的一半,而比率为2.0则说明它获得了应得时间的2倍。于是该算法随后转向比率最低的进程,直到该进程的比率超过它的最接近竞争者为止。 彩票调度算法 基本思想:为进程发放针对系统各种资源(如cpu时间)的彩票;当调度程序需要做出决策时,随机选择一张彩票,持有该彩票的进程将获得系统资源 合作进程之间的彩票交换 六,彩票调度算法 彩票调度算法: 为进程发放针对各种资源(如CPU时间)的彩票.调度程序随机选择一张彩票,持有该彩票的进程获得系统资源. 彩票调度算法的特点: 平等且体现优先级:进程都是平等的,有相同的运行机会.如果某些进程需要更多的机会,可被给予更多彩票,增加其中奖机会. 易计算CPU的占有几率:某进程占用CPU的几率,与所持有的彩票数成正比例.该算法可实现各进程占用CPU的几率. 响应迅速 各个进程可以合作,相互交换彩票. 容易实现按比例分配如图象传输率,10帧/s,15帧/s,25帧/s
操作系统第2阶段练习题
江南大学现代远程教育第二阶段练习题 考试科目:《操作系统》第5章至第7章(总分100分) ______________学习中心(教学点)批次:层次: 专业:学号:身份证号: 姓名:得分: 一、名词解释(12分) 1、死锁 2、逻辑地址 3、物理地址 4、地址重定位 二、试举例说明死锁?(6分) 三、采用静态资源分配预防死锁时,有哪些缺点?(6分) 四、有序资源分配法破坏的是产生死锁必要条件中的什么条件?(5分) 五、作业调度和进程调度的任务各是什么?(6分) 六、进程调度的时机有哪几种?(5分) 七、为什么要进行逻辑地址到物理地址的转换?(6分) 八、某系统的进程状态变迁图如图所示(该系统的进程调度方式为非剥夺方式),请说明: (20分) (1)一个进程发生变迁3的原因是什么?发生变迁2、变迁4的原因又是什么? (2)下述因果变迁是否会发生,如果有可能的话,在什么情况下发生? (3)(a)2→1;(b)3→2;(c)4→5;(d)4→2;(e)3→5 (4)根据此状态变迁图叙述该系统的调度策略、调度效果。 九、在单道批处理系统中,有下列三个作业用先来先服务调度算法和最短作业优先调度算法 进行调度,哪一种算法调度性能好些?请完成下表中未填写的各项。(8分)
十、 分区分配方法中的主要缺点是什么?如何克服这一缺点?(6分) 十一、 如图,主存中有两个空白区,现有这样一个作业序列: 作业1 要求50KB 作业2 要求60KB 作业3 要求70KB 若用首次适应算法和最佳适应算法来处理这个作业序列,试问哪一种算法可以分配得下,为什么?(10分) 十二、 选择填空题(10分) 1、死锁的四个必要条件是__________、不剥夺条件、__________和环路条件。 2、在分区存储管理中,最佳适应算法要求对空闲区表项按( )进行排列。 A.地址从大到小 B.地址从小到大 C.尺寸从大到小 D.尺寸从小到大 3、进程调度又称为( ) A 、线程 B 、宏观 C 、微观 D 、作业 4、段式存储管理中的地址格式是( )地址。 A .线性 B .一维 C .二维 D .三维 参考答案 一、 名词解释 015KB 25KB
操作系统之调度算法和死锁中的银行家算法
操作系统之调度算法和死锁中的银行家算法习题答案
1. 有三个批处理作业,第一个作业 10:00 到达,需要执行 2 小时;第二个作业在 10:10 到达,需要执行 1 小时;第三个作业在 10:25 到达,需要执行 25 分钟。分别采用先来先服务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少? 解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间周转时间=结束时间-到达时间=等待时间+执行时间) 按到达先后,执行顺序:1->2->3 作业到达 时间 结束 时间 等待 时间 执行 时间 周转 时间 平均周 转时间 1 10:00 12:00 0m 120m 120m 156.7m 2 10:10 13:00 110m 60m 170m 3 10:25 13:25 155m 25m 180m 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时 间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行;
3)最后执行作业2 作业到达 时间 结束 时间 等待 时间 执行 时间 周转 时间 平均周 转时间 1 10:00 12:00 0m 120m 120m 145m 3 10:25 12:25 95m 25m 120m 2 10:10 13:25 135m 60m 195m 最高响应比优先: 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 3)执行作业2 作业到达 时间 结束 时间 等待 时间 执行 时间 周转 时间 平均周 转时间 1 10:00 12:00 0m 120m 120m
操作系统原理第四章 处理机调度习题
第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1.某系统采用了银行家算法,则下列叙述正确的是()。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2.银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need,下列选项正确的是()。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3.下列进程调度算法中,()可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4.在下列选项中,属于预防死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5.在下列选项中,属于检测死锁的方法是()。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6.在下列选项中,属于解除死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.银行家算法 D.资源静态分配法 7.为了照顾紧迫型作业,应采用()。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8.在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则
操作系统磁盘调度算法
操作系统课程设计任务书 题目: 磁盘调度算法 院系: 专业: 班级: 姓名: 学号: 指导教师: 设计时间:2018.1.1-2018.1.5 指导教师评语
目录 1、需求分析?4 1.1课题描述 (4) 1.2课题目的 (4) 1.3理论依据?7 2、概要设计?8 2.1设计方法 ............................................................................................... 82.2技术?8 2.3运行环境?8 3、详细设计?9 3.1流程图 (11) 3.2程序主要代码? 13 14 4、运行结果及分析? 4.1运行结果? 15 4.2结果详细分析?6 1 16 5、总结和心得? 7 1 6、参考文献? 2 7、附录:程序源代码? 3
1、需求分析 1.1课题描述 这次课程设计我研究的题目是:磁盘调度算法。具体包括三种算法分别是:先来先服务算法(FCFS)、最短寻道时间优先算法(SSTF)、扫描算法(电梯调度算法)(SCAN)。 1.2课题目的 通过这次实验,加深对磁盘调度算法的理解,进一步掌握先来先服务FCFS,最短寻道时间优先SSTF,扫描SCAN算法的实现方法。 1.3理论依据 设备的动态分配算法与进程调度相似,也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中,低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中,对磁盘的访问要求来自多方面,常常需要排队。这时,对众多的访问要求按一定的次序响应,会直接影响磁盘的工作效率,进而影响系统的性能。访问磁盘的时间因子由3部分构成,它们是查找(查找磁道)时间、等待(旋转等待扇区)时间和数据传输时间,其中查找时间是决定因素。因此,磁盘调度算法先考虑优化查找策略,需要时再优化旋转等待策略。 平均寻道长度(L)为所有磁道所需移动距离之和除以总的所需访问的磁道数(N),即:L=(M1+M2+……+Mi+……+MN)/N
操作系统作业调度算法
操作系统上机测试作业调度算法算法 一、实验目的和要求(供参考) 1.掌握作业调度功能和调度程序常用算法。 2.掌握利用C语言设计实现不同调度策略的作业调度算法。 3.验证不同作业调度算法对性能的影响。 二、实验环境(供参考) 1.知识准备:学过进程管理、作业管理、处理机调度等章节的内容。 2.开发环境与工具: 硬件平台——个人计算机。 软件平台——C语言开发环境。 三、实验内容 用“先来先服务(FCFS)”算法和“最短作业优先(SJF)”算法模拟作业调度。 要求:按作业的到达顺序输入各作业需要的运行时间,按算法调度输出平均周转时间。 例如(FCFS),输入:8(到达时间0),5(到达时间2),7(到达时间3),1(到达时间6)J1 J2 J3 J4 0 8 13 20 21 输出:aver=(8+(13-2)+(20-3)+(21-6))/4=51/4 例如(SJF),输入:8(到达时间0),5(到达时间2),7(到达时间3),1(到达时间6)J1 J4 J2 J3 0 8 9 14 21 输出:aver=(8+(9-6)+(14-2)+(21-3))/4=42/4 注:输入的格式任意,只要输出平均周转时间即可。
四、代码(带注释) 1、先来先服务 实验结果(截图呈现) 代码: #include using namespace std; class Fcfs { private: int num[10]; //作业编号 double arriveTime[10]; //到达时间 double startTime[10]; //开始时间,进内存时间 double workTime[10]; //工作时间 double finishTime[10]; //完成时间 double cirTime[10]; //存放每一个作业的周转时间 //double freeTime[10]; //上一个作业已结束,但下一个作业还未到,存放这一段空闲时间 public: Fcfs(int n) //n为作业数目 { cout<<"默认第一个作业的到达时间为0。"<操作系统实验 第五讲 磁盘调度算法
操作系统 实验报告 哈尔滨工程大学 计算机科学与技术学院
第六讲磁盘调度算法 一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的 (1)通过学习EOS 实现磁盘调度算法的机制,掌握磁盘调度算法执行的条件和时机; (2)观察EOS 实现的FCFS、SSTF和SCAN磁盘调度算法,了解常用的磁盘调度算法; (3)编写CSCAN和N-Step-SCAN磁盘调度算法,加深对各种扫描算法的理解。 3. 实验类型 验证性+设计性实验 4. 实验内容 (1)验证先来先服务(FCFS)磁盘调度算法; (2)验证最短寻道时间优先(SSTF)磁盘调度算法; (3)验证SSTF算法造成的线程“饥饿”现象; (4)验证扫描(SCAN)磁盘调度算法; (5)改写SCAN算法。 二、实验环境 在OS Lab实验环境的基础上,利用EOS操作系统,由汇编语言及C语言编写代码,对需要的项目进行生成、调试、查看和修改,并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。 三、实验过程 1. 设计思路和流程图 (1)改写SCAN算法 在已有SCAN 算法源代码的基础上进行改写,要求不再使用双重循环,而是只遍历一次请求队列中的请求,就可以选中下一个要处理的请求。算法流程图如下图所示。
图 3.1.1 SCAN算法IopDiskSchedule函数流程图 (2)编写循环扫描(CSCAN)磁盘调度算法 在已经完成的SCAN算法源代码的基础上进行改写,不再使用全局变量ScanInside确定磁头移动的方向,而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时,磁头立即移动到最外的被访问磁道,即将最大磁道号紧接着最小磁道号构成循环,进行扫描。算法流程图如下图所示。 图 3.1.2 CSCAN算法IopDiskSchedule函数流程图 (3)编写N-Step-SCAN磁盘调度算法 在已经完成的SCAN 算法源代码的基础上进行改写,将请求队列分成若干个长度为N 的子队列,调度程序按照FCFS原则依次处理这些子队列,而每处理一个子队列时,又是按照SCAN算法。算法流程图如下图所示。
操作系统磁盘调度算法(C++)
#include #include #include using namespace std; const int MaxNumber=100; int TrackOrder[MaxNumber]; int MoveDistance[MaxNumber]; //----移动距离; int FindOrder[MaxNumber]; //-----寻好序列。 double AverageDistance; //-----平均寻道长度 bool direction; //-----方向true时为向外,false为向里 int BeginNum; //----开始磁道号。 int M; //----磁道数。 int N; //-----提出磁盘I/O申请的进程数 int SortOrder[MaxNumber]; //----排序后的序列 bool Finished[MaxNumber]; void Inith() { cout<<"请输入磁道数:"; cin>>M;
cout<<"请输入提出磁盘I/O申请的进程数:"; cin>>N; cout<<"请依次输入要访问的磁道号:"; for(int i=0;i>TrackOrder[i]; for(int j=0;j>BeginNum; for(int k=0;k=0;i--) for(int j=0;j操作系统:调度算法
操作系统:调度算法 例题:四个作业进入系统,分别用FCFS、SJF、HRRF算法求:平均周转时间,带权平均周转时间。 作业到达时间运行时间 A 8:00 120 B 8:50 50 C 9:00 10 D 9:50 20 周转时间:从作业提交算起,直到执行完毕这段时间 带权周转时间:作业的周转时间与系统为其提供服务的服务时间之比1、先来先服务算法:(FCFS) 作业到达时间运行时间开始时间结束时间周转时间 A 8:00 120 8:00 10:00 120 B 8:50 50 10:00 10:50 120 C 9:00 10 10:50 11:00 120 D 9:50 20 11:00 11:20 90 平均周转时间=(120+120+120+90)/4=112.5 带权平均周转时间=(120/120+120/50+120/10+90/20)/4=4.975 2、最短作业优先调度算法:(SJF) 作业到达时间运行时间开始时间结束时间周转时间 A 8:00 120 8:00 10:00 120 B 8:50 50 10:30 11:20 150 C 9:00 10 10:00 10:10 70 D 9:50 20 10:10 10:30 40 平均周转时间=(120+150+70+40)/4=95 带权平均周转时间=(120/120+150/50+70/10+40/20)/4=3.25 3、最高相应比优先算法(HRRF)
作业到达时间运行时间开始时间结束时间周转时间 A 8:00 120 8:00 10:00 120 B 8:50 50 10:10 11:00 130 C 9:00 10 10:00 10:10 70 D 9:50 20 11:00 11:20 70 平均周转时间=(120+130+70+70)/4=97.5 带权平均周转时间=(120/120+130/50+70/10+70/20)/4=3.525 习题: 设有四道作业,他们到达的时间和运行时间如图: 作业到达时间运行时间 A 8:00 80 B 8:30 35 C 9:00 20 D 9:20 25 假设一次调一个作业运行,使用最短作业优先调度算法,求其平均周转时间和平均带权周转时间(以分钟为单位) 作业到达时间运行时间开始时间结束时间周转时间 A 8:00 80 8:00 9:20 80 B 8:30 35 10:05 10:40 130 C 9:00 20 9:20 9:40 40 D 9:20 25 9:40 10:05 45 平均周转时间=(80+130+40+45)/4=73.75 带权平均周转时间=(80/80+130/35+40/20+45/25)/4=2.129 许可 2015.6.7
操作系统实验-FCFS和短作业优先SJF调度算法模拟
题目先来先服务FCFS和短作业优先SJF进程调度算法 姓名: 学号: 专业: 学院: 指导教师:林若宁 二零一八年十一月
一、实验目的 模拟单处理器系统的进程调度,分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法,以加深对进程的概念及进程调度算法的理解. 二、实验内容 1. 短作业优先调度算法原理 短作业优先调度算法,是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法,是从后备队列中选择一个或若干个运行时间最短的作业,将它们调入内存运行。短进程优先调度算法,是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。 2. 先来先服务调度算法原理 先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 三、程序设计 1.概要设计 程序包括主函数、FCFS算法函数、SJF算法函数、输出函数;主函数流程:输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果 2.算法流程
SJF算法流程图:
3.详细设计 (1)定义一个结构体 typedef struct PCB { char job_id[10]; //作业ID float Arr_time; //到达时刻 float Fun_time; //估计运行时间 float Wait_time; //等待时间 float Start_time; //开始时刻 float Fin_time; //完成时刻 float Tur_time; //周转时间 float WTur_time; //带权周转时间 int Order; //优先标记 }list; (2)先来先服务算法函数 void fcfs(list *p,int count) //先来先服务算法 { list temp; //临时结构体变量int i; int j;
操作系统之调度算法和死锁中的银行家算法习题答案
1. 有三个批处理作业,第一个作业 10:00 到达,需要执行 2 小时;第二个作业在 10:10 到 达,需要执行 1 小时;第三个作业在 10:25 到达,需要执行 25 分钟。分别采用先来先服务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少? 解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间) 按到达先后,执行顺序:1->2->3 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行; 最高响应比优先: 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中,一组作业的提交时刻和运行时间如下表所示。试计算一下三种作业调度算法的平均周转时间 T 和平均带权周转时间 W。 ( 1)先来先服务;( 2)短作业优先( 3)高响应比优先
解: 先来先服务: 短作业优先: 作业顺序: 1)8:00只有作业1,所以执行作业1; 2)9:00有作业2和3,作业3短,所以先执行3; 3)9:12有作业2和4,作业4短,所以先执行4; 高响应比优先: 作业顺序: 1)8:00只有作业1,所以执行作业1; 2)9:00有作业2和3 作业2等待时间=9:00-8:30=30m,响应比=1+30/30=2; 作业3等待时间=9:00-9:00=0m,响应比=1+0/12=1; 所以执行作业2; 3)9:30有作业3和4 作业3等待时间=9:30-9:00=30m,响应比=1+30/12=3.5; 作业4等待时间=9:30-9:06=24m,响应比=1+24/6=5;