2、2_4_调度算法:先来先服务、最短作业优先、最高响应比优先_20200905124527.pdf
《2、2_4_调度算法:先来先服务、最短作业优先、最高响应比优先_20200905124527.pdf》由会员分享,可在线阅读,更多相关《2、2_4_调度算法:先来先服务、最短作业优先、最高响应比优先_20200905124527.pdf(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2019/5/16王道考研/1本节内容调度算法先来先服务最短作业优先最高响应比优先王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM知知识识总总览览Tips:各种调度算法的学习思路1. 算法思想2. 算法规则3. 这种调度算法是用于 作业调度 还是 进程调度?4. 抢占式?非抢占式?5. 优点和缺点6. 是否会导致饥饿某进程/作业长期得不到服务2019/5/16王道考研/2王道考研/CSKAOYAN.COM先先来来先先服服务务(FCFS, FirstCome First Serve)FCFS算法思想算法规则用于作业/进程调度是否可抢占?优缺点主要从“公平”的角度考虑(类似于我
2、们生活中排队买东西的例子)按照作业/进程到达的先后顺序进行服务用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,考虑的是哪个进程先到达就绪队列非抢占式的算法是否会导致饥饿王道考研/CSKAOYAN.COM先先来来先先服服务务(FCFS, FirstCome First Serve)例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。进进程程到到达达时时间间运运行行时时间间P107P224P341P454先来先服务调度算法:按照到达的先后顺序调度,事实上就是等待
3、时间越久的越优先得到服务。因此,调度顺序为:P1 P2 P3 P4P1P2P3P40711 1216周转时间 = 完成时间 - 到达时间P1=7-0=7;P2=11-2=9;P3=12-4=8;P4=16-5=11带权周转时间 = 周转时间/运行时间P1=7/7=1;P2=9/4=2.25;P3=8/1=8;P4=11/4=2.75等待时间 = 周转时间 运行时间P1=7-7=0;P2=9-4=5;P3=8-1=7;P4=11-4=7平均周转时间 = (7+9+8+11)/4 = 8.75平均带权周转时间 = (1+2.25+8+2.75)/4 = 3.5平均等待时间 = (0+5+7+7)/
4、4 = 4.75注意:本例中的进程都是纯计算型的进程,一个进程到达后要么在等待,要么在运行。如果是又有计算、又有I/O操作的进程,其等待时间就是周转时间 - 运行时间 -I/O操作的时间2019/5/16王道考研/3王道考研/CSKAOYAN.COM先先来来先先服服务务(FCFS, FirstCome First Serve)FCFS算法思想算法规则用于作业/进程调度是否可抢占?优缺点主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)按照作业/进程到达的先后顺序进行服务用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,考虑的是哪个进程先到达就绪队列非抢占式的算法优点:公
5、平、算法实现简单缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即,FCFS算法对长作业有利,对短作业不利(Eg :排队买奶茶)是否会导致饥饿不会某进程/作业长期得不到服务王道考研/CSKAOYAN.COM短短作作业业优优先先(SJF, ShortestJob First)SJF算法思想算法规则用于作业/进程调度是否可抢占?优缺点追求最少的平均等待时间,最少的平均周转时间、最少的平均平均带权周转时间最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)即可用于作业调度,也可用于进程调度。用于进程调度时称为“短进程优先(SPF, Sh
6、ortest Process First)算法”SJF和SPF是非抢占式的算法。但是也有抢占式的版本最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)是否会导致饥饿2019/5/16王道考研/4王道考研/CSKAOYAN.COM短短作作业业优优先先(SJF, ShortestJob First)例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。进进程程到到达达时时间间运运行行时时间间P107P224P341P454短作业
7、/进程优先调度算法:每次调度时选择当前已到达且运行时间最短的作业/进程。因此,调度顺序为:P1 P3 P2 P4P1P3P2P40781216周转时间 = 完成时间 - 到达时间P1=7-0=7;P3=8-4=4;P2=12-2=10;P4=16-5=11带权周转时间 = 周转时间/运行时间P1=7/7=1;P3=4/1=4;P2=10/4=2.5;P4=11/4=2.75等待时间 = 周转时间 运行时间P1=7-7=0;P3=4-1=3;P2=10-4=6;P4=11-4=7平均周转时间 = (7+4+10+11)/4 = 8平均带权周转时间 = (1+4+2.5+2.75)/4 = 2.5
8、6平均等待时间 = (0+3+6+7)/4 = 4严格来说,用于进程调度应该称为短短进进程程优优先先调调度度算算法法(SPF)8.753.54.75对比FCFS算法的结果,显然SPF算法的平均等待/周转/带权周转时间都要更低王道考研/CSKAOYAN.COM短短作作业业优优先先(SJF, ShortestJob First)例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用抢占式的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。进进程程到到达达时时间间运运行行时时间间P107P224P341P454最短剩余时间优先算法
9、:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度P1P2P3P2P4P1024511抢占式的短作业优先算法又称“最短剩余时间优先算法(SRTN)”需要注意的是,当有新进程到达时就绪队列就会改变,就要按照上述规则进行检查。以下 Pn(m)表示当前 Pn进程剩余时间为 m。各个时刻的情况如下:0时刻(P1到达) : P1(7)2时刻(P2到达): P1(5)、 P2(4)4时刻(P3到达): P1(5)、 P2(2)、 P3(1)5时刻(P3完成且P4刚好到达):P1
10、(5)、 P2(2)、 P4(4)7时刻(P2完成):P1(5)、 P4(4)11时刻(P4完成) :P1(5)7162019/5/16王道考研/5王道考研/CSKAOYAN.COM短短作作业业优优先先(SJF, ShortestJob First)例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用抢占式的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。进进程程到到达达时时间间运运行行时时间间P107P224P341P454最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- _4_ 调度 算法 先来先 服务 作业 优先 最高 响应 _20200905124527
链接地址:https://www.deliwenku.com/p-19243736.html
限制150内