典型调度算法课件.ppt

先来先服务调度算法 先来先服务（FCFS）调度算法是一种最简单的调度算法，该调度算法既可以用于作业调度也可以用于进程调度。 在作业调度中，先来先服务调度算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。 在进程调度中，先来先服务调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，该进程一直运行下去，直到完成或某种原因而阻塞时才释放处理机。 弦相躇描傅侗垂铆贡凋漳萧秘专台乍换舒葵尧肖隧馅殆令粹蛊牌王肺智伯典型调度算法课件典型调度算法课件 例1：假设系统中有3个进程P1，P2和P3，它们的运行时间依次是24，3，3（单位为ms）。如果进程P1，P2，P3依次在0,1,2时刻到达，并且采用FCFS调度算法计算其平均等待时间。 24 27 30 0 进程 时间（ms） P1 P2 P3 (a) (b) 3个进程执行的甘特图 酣绎晴渭棘宾她大楼审追氧凸巴闻睬滓赔突结岔开拒替辖蚌喜盯裹蠢突镊典型调度算法课件典型调度算法课件 FCFS调度算法性能表 进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 P1 0 24 0 24 24 1 P2 1 3 24 27 26 8.67 P3 2 3 27 30 28 9.33 平均周转时间=（24+26+28）/3=26 平均带权周转时间=（1+8.67+9.33）/3=6.33 曹宅燎挡贴斜益弄呕颂堪伸恳妈贰株煌变藤寂俄凤魁段痢咸去捧碍亡漳扳典型调度算法课件典型调度算法课件 进程P1的等待时间是0ms，进程P2的等待时间是23ms，P3的等待时间是25ms。这样，平均等待时间是（0+23+25）/3=16ms 如果进程到达的顺序是P2，P3，P1，那么得到的平均等待时间是（4+0+2）/3=2ms。平均等待时间很明显地减少了。因而，FCFS策略下的平均等待时间通常不是最小的，而且如果进程的执行时间有明显的变化时平均时间也会有明显的变化。 FCFS调度算法是非抢占式的。一旦CPU被分配给一个进程，该进程将持有CPU直到它释放CPU（通过终止或请求I/O）。对分时系统来说，FCFS算法尤其糟糕，因为这种系统中的每个用户以有规则的时间间隔共享CPU。允许一个进程长期地占有CPU会产生灾难性的后果。 先来先服务调度算法的特点是算法简单，但效率较低；有利于长作业，但对短作业不利；有利于CPU繁忙型作业，而不利于I/O繁忙型作业 注优填岿谆恢朱狼军奖赶犯债讨遗岭行崖搓馅闰媒吸沾叹劈鳖孟衍抡搭藏典型调度算法课件典型调度算法课件 最短作业优先法 短作业优先（SJF）调度算法用于进程调度时称为短进程优先调度算法，该调度算法主要用于作业调度。其实现思想是：从作业的后备队列中挑选那些需要运行的时间（估计值）最短的作业放入内存。这是一种非抢占式的策略。系统一旦选中某个短作业后，就让该作业投入执行，直到该作业完成并退出系统。如果有四个作业A，B，C，D。它们的预计运行时间分别为6，3，15，8个时间单位，利用最短作业优先法调度，它们的执行顺序是：B-A-D-C。 蚁翁枝钾蜂屏绑铭感艺淹锡傲盼级碾恤赂竿馆胞侠寒铭迪劫中闻烷邻蓬蝴典型调度算法课件典型调度算法课件 例2 假设系统中有4个作业A，B，C，D。下表给出了提交时间和运行时间 作业 提交时间 运行时间/h A 5:00 2 B 6:00 0.5 C 6:30 0.2 D 6:36 0.4 由于作业A的开始时间是5：00，而其余作业均未到达，故先运行作业A，当作业A运行完毕，其余作业均按短作业优先运行。所以作业运行次序为：A，C，D，B。 戈努练湾旱朋巳万抑筋吁鸭掸乃避闯祟赐攘捧乌芥烛丝弊望率尘崭桌突誊典型调度算法课件典型调度算法课件 最短作业优先调度算法的调度性能 作业 提交时间 运行时间/h 开始时间 完成时间 周转时间/h 带权周转时间 A 5:00 2 5:00 7:00 2.0 1 B 6:00 0.5 7:36 8:06 2.1 4.2 C 6:30 0.2 7:00 7:12 0.7 3.5 D 6:36 0.4 7:12 7:36 1.0 2.5 由此：此作业流的平均周转时间为 T=（2.0+2.1+0.7+1.0）/4=1.45h。此作业流的平均带权周转时间为W=（1.0+4.2+3.5+2.5）/4=2.8h。 通过以上分析，虽然这种算法易于实现，且效率也比较高，但未考虑长作业的利益 戳敷几貉彼埠篇胶勘浪赢坦挽怕颈段糟融隧瓣嫉眨快勿凿滓夜忘渗敌亡厄典型调度算法课件典型调度算法课件 轮转法（Round-Robin,RR） 时间片是一个很小的时间