《第三章处理机调度摘要》由会员分享，可在线阅读，更多相关《第三章处理机调度摘要（55页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度,本章内容,3.1 三级调度体系 3.2 进程调度目标和调度方式 3.3 调度算法的评价准则 3.4 典型进程调度算法 3.5 线程调度算法 3.6 实时调度算法,3.1 三级调度体系,3.1.1 高级调度 1高级调度（high-level scheduling）又称作业调度或长程调度，它是根据某种算法将外存上处于后备作业队列中的若干作业调入内存，为作业分配所需资源并建立相应进程。 2作业通常分成若干个既相对独立又互相关联的加工步骤，每个步骤称为一个作业步。每个作业步可能对应一个或多个进程。,3.1.1 高级调度,作业一般要经历“提交”、“后备”、“执行”和“完成”四个状态。
2、,3.1.1 高级调度,高级调度决定允许哪些作业可进入内存，参与竞争CPU和系统其他资源，将一个或一批作业从后备状态变为运行状态。,3.1.1 高级调度,在多道批处理系统中，为了管理和调度作业，系统为每个作业设置了一个作业控制块(JCB)，它记录作业的相关信息。,3.1.1 高级调度,3.1.2 中级调度,中级调度(middle-level scheduling)又称内存调度，它是进程在内存和外存之间的对换。 具有中级调度的系统中，进程除了具有三个基本状态外，还具有静止就绪和静止阻塞两个状态。,3.1.3 低级调度,低级调度（low-level scheduling）又称进程调度、短程调度，它
3、决定哪个就绪态进程获得处理机，即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机。 低级调度是三级调度中的最终调度，又称底层调度。在这级调度中真正实现了处理机的分配，它是系统不可缺少的最基本调度。,3.1.3 低级调度,进程调度的功能主要包括以下两部分： 选择就绪进程 进程切换,3.1.4 三级调度关系,分级调度系统中，各级调度分别在不同的调度时机进行。对于一个用户作业来说，通常要经历高级调度、中级调度和低级调度才能完成整个作业程序的运行。,3.1.4 三级调度关系,3.2 进程调度目标和调度方式,3.2.1 进程调度目标（1）公平性 （2）
4、高效率 （3）低响应时间 （4）高吞吐量 （5）特殊应用要求,3.2 进程调度目标和调度方式,不同类型的操作系统有不同的调度目标。 (1)多道批处理操作系统多道批处理系统强调高效利用系统资源和高作业吞吐量。 (2)分时操作系统分时系统更关心多个用户的公平性和及时响应性，它不允许某个进程长时间占用处理机。 (3)实时操作系统实时操作系统必须保证实时进程的请求得到及时响应，往往不考虑处理机的使用效率。其调度算法的最大特点是可抢占性。,3.2.2 进程调度方式,进程调度有两种基本方式：非抢占方式和抢占方式。 （1）非抢占方式（Nonpreemptive） 进程一旦获得处理机执行，其他进程就不能中断它
5、的执行，即使当前等待进程中出现了优先级更高的请求进程也不允许该进程抢占处理机。直到执行态进程完成或发生某个事件主动放弃处理机，才能调度其他进程获得处理机执行。 这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统。但它难以满足实时任务的要求，在要求比较严格的实时操作系统中，一般不宜采用此类调度方式。,3.2.2 进程调度方式,（2）抢占方式（Preemptive） 抢占式调度是指在进程并发执行中，如果就绪进程中某个进程优先级比当前运行进程的优先级还高，无论当前正在运行的进程是否结束，允许高优先级进程抢占当前运行进程的处理机并立即执行。抢占式调度可确保高优先级进程立即获得处理机。抢占
6、式调度在实际系统中具有重要意义。,3.2.2 进程调度方式,支持抢占式调度的系统中，一般的抢占原则如下： 优先权原则就绪的高优先权进程有权抢占低优先权进程的CPU。 短作业优先原则就绪的短作业有权抢占长作业的CPU。 时间片原则一个时间片用完后，系统重新进行进程调度,3.3 调度算法的评价准则,3.3.1 面向用户的评价准则 (1) 作业周转时间所谓作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。 平均周转时间： 平均带权周转时间：,3.3.1 面向用户的评价准则,(2) 响应时间响应时间是指从进程输入第一个请求到系统给出首次响应的时间间隔。用户请求的响应时间越短，用户的
7、满意度越高。响应时间通常由三部分时间组成：进程请求传送到处理机的时间、处理机对请求信息进行处理的时间、响应信息回送到显示器显示的时间。,3.3.1 面向用户的评价准则,(3)截止时间截止时间是指用户或其他系统对运行进程可容忍的最大延迟时间。在实时系统中，通常用该准则衡量一个调度算法是否合格。在实际系统评价中，主要考核的是开始截止时间和完成截止时间。 (4) 优先权准则在批处理、分时和实时系统中选择调度算法时，为保证某些紧急作业得到及时处理，必须遵循优先权准则。因此，系统对不同进程设立优先级，高优先级进程优先获得处理机的使用权。,3.3.2 面向系统的评价准则,对计算机系统而言，在保证用户请求被
8、高效处理的基础上，尽量使计算机系统中的各类资源得到充分利用。面向系统的调度指标有：(1) 系统吞吐量(2) 处理机利用率(3) 各类资源均衡利用(4) 调度算法实现准则,3.4 典型进程调度算法,3.4.1 先来先服务调度算法 3.4.2 短作业（进程）优先调度算法 3.4.4 时间片轮转调度算法 3.4.5 优先级调度算法 3.4.6 高响应比优先调度算法 3.4.7 多级反馈队列调度算法,重点,3.4.1 先来先服务调度算法,FCFS( First Come First Service)算法按照进程就绪的先后顺序调度进程，越早到达的进程，越先执行。FCFS算法的优缺点： 有利于长进程，不利
9、于短进程，排在长进程后边的短进程往往等待的时间较长，导致其周转时间过长，没有体现出短进程优先原则。 有利于处理机繁忙的进程，不利于输入输出繁忙的进程。 算法简单，易于实现，系统开销小。,3.4.2 短作业（进程）优先调度算法,“短作业优先”SJF 又称为“短进程优先”SPF(Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。 其思想是：对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。,SJ(P)F的特点,优点： 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间； 提高系统的吞吐量； 缺点： 对
10、长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。,3.4.4 时间片轮转调度算法,时间片轮转算法（RR，Round Robin）依据公平服务的原则，将处理机的运行时间划分成等长的时间片，轮转式分配给各个就绪进程使用。 采用此算法的系统中，所有就绪进程按照先来先服务的原则排成一个队列，每次调度时将处理机分派给队首进程。如果进程在一个时间片内没执行完，那么调度程序强行将该进程中止，进程由执行态变为就绪态并把处理机分配给下一个就绪进程。该算法能保证就绪队列中的所有进程在一给定的时间段内均能获得处理机运行。,3.
11、4.4 时间片轮转调度算法,时间片轮转法的原理见图所示。,图 轮转法调度,3.4.5 优先级调度算法,优先级调度算法（Priority Scheduling）为每个进程赋予一个整数，表示其优先级。就绪进程按照优先级的大小顺序排队，调度程序选择优先级最高的进程获得CPU。该算法常被用于批处理系统中。 为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。 此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。 当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。 当用于进程调度时，该
12、算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。,1优先级调度算法的类型,1) 非抢占式优先权算法 系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。 这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。 2) 抢占式优先权调度算法 系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给
13、新到的优先权最高的进程。 显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。,2优先级的类型,对于最高优先权优先调度算法，其关键在于：它是使用静态优先权，还是用动态优先权，以及如何确定进程的优先权。 1) 静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的。 确定进程优先权的依据有如下三个方面： (1) 进程类型。 (2) 进程对资源的需求。 (3) 用户要求。,2优先级的类型,2) 动态优先级 动态优先权是指在创建进程时所赋予的优先权
14、，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,3.4.6 高响应比优先调度算法,最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡。响应比R定义为系统对作业的响应时间与作业要求运行时间的比值。 一个作业或进程的响应比RHRRF调度程序开始调度时，首先计算各个后备作业或各个就绪进程的响应比 ,然后选择 值最大的作业或进程。,重点回顾,线程 在引入线程之后，进程作为资源分配的基本单位，而线程作为独立调度和运行的基本单位,重点回顾,高级调度（high-level scheduling）又称作业调度或长程调度，它是根据某种算法将外存上处于后备作业队列中的若干
15、作业调入内存，为作业分配所需资源并建立相应进程。 中级调度(middle-level scheduling)又称内存调度，它是进程在内存和外存之间的对换。 低级调度（low-level scheduling）又称进程调度、短程调度，它决定哪个就绪态进程获得处理机，即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机。,重点回顾,典型进程调度算法 先来先服务调度算法 短作业（进程）优先调度算法 时间片轮转调度算法 高响应比优先调度算法 优先级优先调度算法,举例,例：假定在一个处理机上执行以下五个作业：作业号 A B C D E到达时间 0 1 2
16、 3 4运行时间 4 3 5 2 4优先数 1 4 2 5 3(优先数越大代表优先级越高)分别采用FCFS、SJF、RR（时间片1），HRRF (响应比高者优先)和静态优先权优先五种调度算法时，试做： （1） 计算每个作业的周转时间和带权周转时间 ； （2） 计算平均周转时间和平均带权周转时间。,2.1,1.5,1,8,3,4,6 ,4 ,SJF,2.8,3.5,5.5,2,2,1,带权周转时间,9,14,11,10,6,4,周转时间,18 ,14 ,12 ,7 ,4 ,完成时间,FCFS,图3-5 qq=1和qq=4时的进程运行情况,4 3 5 2 4,3.29,11.6,2.38,8.4,作业号 A B C D E 到达时间 0 1 2 3 4 运行时间 4 3 5 2 4 优先数 1 4 2 5 3(优先数越大代表优先级越高),
