第四章处理机调度

1、引言： 1、在早期的计算机系统中，对CPU的管理十分简单，因那时CPU和其他资源一样，为一个作业独占，不存在处理机分配和调度问题。 2、随着多道程序设计技术和各种不同类型的os的出现，各种不同的CPU管理方法得到启用，不同的CPU管理方法为用户提供不同性能的os。 A、在多道批处理系统中，为了提高处理机效 率和作业的吞吐量，当调度一批作业组织多 道运行时，要尽可能使作业搭配合理； B、在分时系统中，由于用户使用交互会话的工作方式， 系统必须要有较快地响应时间，使每个用户均感到如 同只有他一个人在使用计算机，因此系统在调度作业 时，要考虑每个用户作业得到处理机的均等性。 3、衡量调度策略的指标：

2、 （1）周转时间：只讲一个作业提交给计算机后到作业的 结果返回给用户所需的时间； （2）吞吐量（率）：在给定时间内，一个计算机系统所 完成的总工作量； （3）响应时间：从用户向计算机发出一条命令开始到计 算机把相应结果返回给用户所需的时间； （4）设备利用率：指I/O的使用情况。一、作业状态及其转换： 1、多级调度：一个作业从用户提交开始到真正占有处理机而被执行，则要有系统经过多级调度才能实现。 2、作业状态：一个作业从提交给计算机系统开始到返回执行结果为止，一般要经历提交、收容、执行、完成四个状态。 （1）提交状态：一个作业在其处于从输入设备进入外部存储设备的过程。 （2）收容状态（后备状态

3、）：作业内容全部进入外存输入井，但该作业还未被作业调度程序 选中时所处的状态； （3）执行状态：作业调度程序从后背作业队列中选择若 干个作业投入运行，它为被选中作业建立进程并分配 必要资源，这些被选中的作业处于执行态。 （4） 完成态：当作业运行完毕，但它所占有的资源还 未全部释放时所处的状态。二、调度的层次：P82 1、作业调度：又称宏观调度（高级调度），其主要任务 是按一定的原则对外存输入井中的大量后备作业进行 选择，给选出的作业分配内存、输入输出设备等资源， 并建立相应进程，以使该作业的进程获得竞争CPU的权 利，另外，当作业执行完毕，还负责回收系统资源。 2、交换调度：也叫中级调度，其

4、主要任务是按照给定的 原则和策略，将处于外存交换区中的就绪进程调入内存， 或把处于内存就绪状态或内存等待状态的进程交换到外 村交换区。 3、进程调度：又叫微观调度或低级调度。其主要任务是 按照某种策略和方法选取一个处于就绪状态的进程占用 处理机。在确定了占用处理机的进程后，系统必须进行 进程上下文的切换以建立与占用处理机进程相应的执行 环境。 4、线程调度：其主要任务是选择一个适当的线程到处理 机上去执行并进行描述标的切换。 （1）线程的调度状态：六个状态 a、就绪状态：已具备执行条件以等待CPU执行，线 程调度程序只从线程就绪池中选择线程进入备用状 态。 b、备用状态：系统中每个处理机只能有

5、一个线程处 于备用状态，处于备用状态的线程被选定为某一特 定处理机的下一个执行对象。当条件合适时，调度 程序为该线程进行描述表切换。 c、运行状态：一旦调度程序对线程执行完描述表切 换，线程便进入运行状态。 d、等待状态：以下情况便可使线程进入等待状态： 线程等待一对象，同步他的执行；因等待I/O设备； 环境子系统导致线程自己挂起。当线程等待结束， 就回到就绪状态。 e、转化状态：如果线程已准备好执行，但由于资源 为不可用，从而成为转化状态。当资源为可用时， 线程便由转化状态进入就绪状态； f、终止状态：线程完成了他的执行。 （2）引起线程调度的时机： a、当线程进入就绪状态时； b、当线程的

6、时间片用完或线程终止时； c、当调度程序或执行体改变线程优先级时； d 、当执行体或应用程序改变正在运行的处理机族时。 （3）线程描述表：是用于描述现行线程的现场，包括： 程序计数器、处理机状态寄存器、其他寄存器内容、 用户栈和核心栈指针、线程运行的地址空间的指针。三、作业与进程的关系（P83） 1、作业可被看作用户向计算机提交任务的任务实体，而 进程则是计算机为了完成用户任务实体而摄制的执行实 体，是系统分配资源的基本单位。 2、一个作业由一个或多个进程组成： 第一步：系统为一个作业创建一个根进程； 第二步：在执行作业控制语句时，根据任务要求，系统 或根进程为其建立相应的子进程； 第三步：系

7、统为子进程分配资源和调度各子进程完成作 业要求的任务。一、作业调度的功能： 1、记录系统中各作业的状态。 系统为每个作业建立一个作业控制块(JCB)来对作业进行控制管理并记录作业在运行过程中的状态。 （1）JCB的建立：作业进入后备状态时为该作业 建立相应的JCB，从而使该作业能被系统感 知； （2）JCB的撤销：当作业执行完毕进入完成状态后，系 统撤销其JCB而释放有关资源并撤销该作业； （3）JCB内容：作业名，作业类型，资源要求，资源使 用情况等 2、从后备作业队列中选出一部分作业投入运行。 3、为被调度选中的作业做好执行前的准备工作。 4、在作业执行结束时作善后处理工作。主要是输出作业

8、 管理信息，例如执行时间；回收该作业所占用的资源； 撤销与该作业有关的进程和JCB。 P85图4.3二、作业调度目标与性能衡量： 1、调度目标 （1）对所有作业应是公平的； （2）应使设备有高的利用率； （3）每天执行尽可能多的任务； （4）有快的相应时间。 2、调度算法优劣的衡量： 批处理系统-用作业的平均周转时间或平均带权周转 时间衡量； 分时系统、实时系统-用作业周转时间或平均带权周 转时间及平均相应时间衡量。 （1）周转时间：指作业从提交时刻开始到完成时刻为止 所经历时间。即：Ti=Tei-Tsi 平均周转时间：T=(T1+Tn)/n （2）带权周转时间：指作业周转时间和作业执行时间的

9、 比值，即 Wi=Ti/Tri 平均带权周转时间： W=(W1+Wn)/n 在计算机系统运行过程中，进程数一般多于处理机树目，从而导致进程对处理机的竞争，进程调度即按一定策略，动态地把处理机分配给处于就绪状态的进程，使之能被执行。一、进程调度的功能： 指操作系统中的进程调度程序按照某种调 度算法，从就绪进程队列中选择一个进程将他 移出就绪队列并置为运行态， 同时启动CPU立即执行 该进程。具体描述为： （1）记录系统中所有进程的执行情况； a、进程管理模块将系统中各进程状态和状态特征记 录在PCB中； b、根据进程的状态特征和资源需求，将系统中所 有进程PCB组织成多个队列。 （2）选择占有处

10、理机的进程； 根据不同的系统设计目标，有各种各样的选 择策略，如：静态优先数调度法、轮转法等。 （3）进行进程上下文切换： a、进程上下文：包括进程的状态、有关变量、数据 结构的值，硬件寄存器的值及PCB和有关程序； b、一个进程的执行实质上是在其上下文中执行； c、当出现进程调度时系统要做上下文的切换。二、进程调度的时机 1、引起进程调度的原因 a、正在执行的进程执行完毕； b、进行中的进程自己调用阻塞原语将自己阻塞起来， 进入睡眠等待状态； c、执行中进程调用了P原语操作，从而因资源不足而 被阻塞，或调用了V原语激活了等待资源的进程队 列； d、执行中进程提出了I/O请求后被阻塞； e、在

11、分时系统中时间片已经用完； f、在执行完系统调用后，在系统程序返回用户程序时， 可认为系统进程执行完毕，从而调度选择一新的进 程执行； g、就绪队列中进程的优先级变得高于当前执行进程的 优先级，从而引起进程调度。 2、处理机调度的时机： 当系统出现提上七种情况之一时，即发生处理机 调度。 3、处理机调度的方式： （1）可剥夺式：即就绪队列中一旦有优先级高于当前进 程的优先级时，便立即发生进程调度，转让处理机； （2）非剥夺方式：即使在就绪进程队列存在优先级高于 当前当前正在执行的进程的优先级时，当前进程仍 将继续占用处理机，直到该进程因自己调用某原语 或等待I/O而进入阻塞状态、或时间片用完时

12、才发 生调度出让处理机。三、进程上下文切换（P88） 1、进程上下文的内容： 2、进程上下文切换的步骤： （1）决定是否做上下文切换及其是否允许做上下文切换； （2）保存当前执行进程的上下文； （3）选择一个就绪状态进程； （4）恢复或装配所选进程上下文，将CPU控制权交给所 选进程。四、进程调度性能评价： 1、定性评价：进程调度性能的衡量可分为定性和定量两 种。在定性衡量方面，首先考虑调度的可能性包括一 次进程调度是否引起数据结构的破坏，这要求对调度 时机的选择和保存CPU现场十分谨慎；其次，简洁性 也是衡量进程调度的一个重要指标，由于调度程序的 执行涉及到多个进程和必须进行上下文的切换，

13、如 果调度过于频繁，将会耗去较大的系统开销。 2、定量评价：包括CPU利用率，进城在就绪队列中的等 待时间与执行时间之比。1、先来先服务调度算法(FCFS) （1）方法思想：按照进程进入就绪队列的先后次序选择 进程投入 运行。该法也可以用于作业调度。 （2）特点： 优点：实现简单、公平。 缺点： a、计算机效率可能不高，如系统中的进程偏向于需求某 一类资源，导致有的资源高度繁忙，有的资源可能长 期不用； b、对短进程可能不利，不能很好地满足用户的需求。 （3）例：设P1,P2,P3为三个进程，他们的本次CPU周期 时值分别是21ms,6ms,3ms，且以P1,P2,P3的次序 进入就绪队列中，

14、则在（1）不剥夺方式下执行 序列为：P1P2P3,且 平均周转时间T=(21+27+30)/3=26ms 平均等待时间W=(0+21+27)/3=16ms 平均带权周转时间T1=(21/21+27/6+30/3) （2）在分时系统中，若时间片为6ms，分析 这三个进程的执行情况。 2、最短者优先(SJF,SPF) （1）思想：以进程的本次CPU时间长短作为调度的依据 来选择进程投入运行。 （2）例：设P1,P2,P3为三个进程，他们的本次CPU周期 时值分别是21ms,6ms,3ms，分析他们的执行情 况及有关指标的计算。 （3）性能分析： a、采用最短进程优先调度算法，可以降低平均周转 时间

15、，平均带权周转时间、平均等待时间。 b 、该算法实现简单。 缺点：一般情况具有公平性，但是当系统中长进程 较少而短进程较多时，对长进程失去公平性。 3、最高相应比者优先(HRN=highest reponse ration next） （1）当需要从就绪队列中选择进程投入运行时，先计算 个进程的相应比，选择相应比最高的进程运行。（2）例：设有四个作业：J1,J2,J3,J4，他们的进入时间 分别为8:00,8:50,9:00,9:50，运行时间分别为 2:00,0.50,0.10,0.20，分析执行情况。 (略) （3）性能： a、该算法较复杂，系统开销大； b、性能评价参数有升高趋势； c、

16、克服了FCFS、 SPF各自的缺点。4、轮转法（RR=round robin） （1）思想：系统将所有就绪进程按先进先出原则组织成 队列，调度程序每次选择队首进程投入运行，并 按规定的时间片S值设置时钟，以便S到限时产生 中断。若现行进程的CPU周期时值小于S值，则当 该进程完成时就进入重新调度，S的剩余量交还给 系统；如果当前CPU周期时值大于或等于S值，则 当时间片中断发生时便进入剥夺态，将现行进程 送至就绪队列尾部，而当前CPU周期剩余量放到下 一轮再执行，同时选择队首进程投入运行。 2）例：针对前面提到的P1,P2,P3三个进程，利用轮转法， 分析他们的执行情况。 （略） （3）关于时

17、间片： a、长短适中，如太长，则使每一个进程均能在一个 时间片内完成，RR算法褪化成了FCFS；若太短， 导致频繁的时间片中断和调度，CPU额外开销大。 b、时间片S可以采用基本时间片法和变长时间片法。 c、S的选取公式： S=RT/N 其中RT为系统响应时间上限，N为系统中进程 数目上限。 （4）性能： a、具有公平性； b、易于实现，算法简单； c、CPU存在较大的额外开销，用于进程切换和 调度。 5、最高优先级法： （HPF=highest priority first） （1）思想：在进行进程调度时，选择优先级最高者头投 入运行，而忽略等待时间、运行时间等因素。 a、优先级的表示方法：

18、用一个整数表示，该数称为 优先数，有的系统规定优先数越小，优先级越高。 b、优先级的设置方法： 静态优先级法：由系统在建立进程时确定一个优先 数，它在整个生命期内保持不变：进程的优先 数可以根据其类型、功能、资源需求等确定； 动态优先数：在创建一个进程时，根据该进程的基 本特性设置一个初始优先数，而后在进程运行 过程中，随着时间推移和运行环境的变化而动 态地改变优先级， P=Po-at。 （2）例：设有5个进程P1,P2,P3,P4,P5它们各自的本次 CPU时值、初始化优先级及进入就绪队列相对时 刻如下： 进程 CPU时值 优先数 进入时刻 P1 32 5 0 P2 4 3 0 P3 8 5

19、 0 P4 2 6 0 P5 16 4 16 （1）分析在静态优先级调度算法下的有关指标：平 均等待时间、平均周转时间、平均带权周转时间。 （2）在剥夺式的动态优先级方法中，设现行进程每 连续运行10毫秒以上后，优先数加1，而就绪进程每 40毫秒后进程优先数减1，分析执行情况。（3）性能： a、静态优先级法简单，但缺点是公平性差，可能会 造成优先级低的长期等待； b、动态优先级法资源利用率高，公平性好，缺点是 系统开销较大，实现复杂。 6、多级反馈队列： （1）思想： a、系统按优先级别设置若干n个就绪进程队 列，第一 级队列的优先级最高，以下逐级降低，第n级队列的 优先级最低； b、每个就绪

20、队列对应一个时间片Si(i=1,2,n)，且 有S1S2Sn，一般有Si+1=2Si c、除对第n级队列按RR调度外，对其余各级均按 FCFS调度； d、当现行进程正在运行它的CPU周期时，如果有时 间片中断或有进程进入更高级的就绪队列时将引起 剥夺，对前一种情况，先行进程将进入下一级队列， 对后一种情况，先行进程进入本级队列尾部，当一 进程被唤醒时，它进入原来离开时的队列。 （2）特点： a、复杂，实现困难； b 、是FCFS，RR，HPF的综合应用。 补充：调度的实现 进程调度室内核原语，当发生了引起调度的某种事件时，由有关的内核程序转入。 采用HPF算法的进程调度程序大致描述如下： pr

21、ocedure scheduler; begin if RQ=nil then start(idler); outqueue(RQ,I,HPF); if EXENIL then begin if I.priorityEXE.priority then begin save(EXE); EXE.start:=ready; EXE.queue:=RQ; insert(RQ.EXE); end; else begin insert(RQ,i); return end; end; start(i); end;一、实时系统的特点及功能 （一）特点 1、有限等待时间（确定性）：与分时系统 的多个进程的并发

22、执行特性相比，分时系 统中并发执行的进程具有不确定性，其执 行顺序与执行环境有关。而实时系统则不 然，他要求所有进程在处理事件时，都必 须在有限时间内开始处理。 2、有限响应时间： 指从系统响应外部事件 开始，必须在有限时间内处理完毕。 3、用户控制：指用户可以控制进程的优先级并选择 相应的调度算法，从而达到对进程执行先后顺序 的控制。 4、可靠性：要求很高 5、系统出错处理能力： 要求系统在出错时，既能处理发生的错误， 又不影响当前正在执行的用户进程。 （二）实时系统的功能： 1、很快的进程或线程切换速度 与分时系统不同，公平性和最小平均响应时 间指标在实时系统中并不重要，实时系统中调度 算法的设计原则是满足所有硬实施任务的处理时 限和尽可能多地满足软实时任 务的处理时限。 2、快速的外部中断响应能力 3、基于优先级的随机抢先式调度策略，有四种： （1）优先级+时间片轮转调度策略 （2）基于优先级的非抢占式调度策略 （3）基于优先级的固定点抢先式调度策略 （4）基于优先级的随时抢先式调度策略二、实时调度算法的分类： （1）静态表格驱动类 （2）静态优先级驱动抢先式调度算法类 （3）动态计划调度算法