第5章作业调度

1、第第5 5章章 作业调度作业调度 主讲：房道伟主讲：房道伟Daowei_操作系统原理操作系统原理主要内容n作业的状态与处理流程作业的状态与处理流程n作业的调度作业的调度n进程的调度进程的调度n选择调度算法时应考虑的问题选择调度算法时应考虑的问题n调度算法调度算法 在大型通用系统中，可能有数百个批处理作业存放在磁盘的作业队列中，有数百个终端同主机相联接。因此如何从这些作业中挑选作业进入主存运行、如何在作业或进程间分配处理等，问题无疑是操作系统的资源管理功能中的一个重要问题。本章主要讨论处理机分配问题，或称处理机调度。一般来说，处理机调度可以分成三级：(1) 高级调度：高级调度：又称作业调度，其主

2、要功能是按照某种原则从磁盘某些盘区的作业队列中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。(2) 中级调度：中级调度：它决定哪些进程被允许参与竞争处理机资源。中级调度主要只是起到短期调整系统负荷的作用，以平顺系统的操作。其所使用的方法是通过“ 挂起 ” 和“ 解除挂起 ” 一些进程，来达到平顺系统操作的目的。(3) 低级调度：低级调度：又称进程调度，其主要功能是按照某种原则将处理机分配给就绪进程。执行低级调度功能的程序称为进程调度程序，由它实现处理机在进程间的转换。它必须常驻主存，是操作系统内核的主要部分。RUNreadyablockedareadysblokeds后

3、备完成作业后备状态执行内存时间片到I/O请求I/O完成高级调度(作业调度)挂起解挂挂起解挂进程调度低级调度中级调度5.1 作业的状态与处理流程作业的状态与处理流程一、一、 作业状态作业状态提交收容执行完成提交状态后备状态运行状态完成状态 作业从提交给系统直到它完成后离开系统前的整个活动常划分为若干阶段。作业在每一阶段中所处的状况称为作业的状态。系统中的作业通常分为四种状态：(1) 提交状态：提交状态：一个作业被提交给机房后或用户通过终端键盘向计算机中键入其作业时所处的状态为提交状态。(2) 后备状态：后备状态：作业的全部信息都已通过输入机输入，并由操作系统将其存放在磁盘的某些盘区中等待运行，则

4、称为后备状态。(3) 运行状态：运行状态：作业一旦被作业调度程序先中而被送入主存中投入运行，称之为运行状态。(4) 完成状态：完成状态：作业完成其全部运行，释放出其所占用的全部资源，准备退出系统的作业状况称为完成状态。5.2 作业的调度作业的调度 系统中往往有成百个作业被收容在磁盘输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况。因此同进程中的情况类似，系统也为每个作业设置一个作业控制块 (记为JCB)，它记录了作业的有关信息。不同系统的 JCB 所包含的信息有所不同，这取决系统对作业调度的要求。JCB结构 见书P122 图6.8 JCB 是在作业进入系统时由 SPOOL 系统

5、为其建立的。其内容由作业控制卡中得到。同样 JCB 也是作业存在于系统的标志，作业进入系统时，则为之建立 JCB。当作业退出系统时，则其 JCB 也被撤消。 在磁盘输入井中的所有后备作业按作业类型将它们组成一个或多个后备作业队列。所谓后备作业队列是由作业控制块 JCB 用表格或链指针组成的队列。作业队列可按优先数大小和作业到达系统的时间顺序排列。根据系统内所有资源的使用情况， 按照某种调度算法选择一个后备作业进入系统， 并为其创造一个进程。 为此，作业调度还要为选中的作业分配资源，作好作业支行前的准备。完成作业调度功能的程序称为作业调度程序。作业调度程序要完成以下工作：(1) 按照某种调度算法

6、从后备作业队列中挑选作业。(2) 为选中的作业分配主存和外设资源。(3) 为选中的作业建立相应的进程。(4) 构造和填写作业运行时所需的有关表格。(如作业表)(5) 作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进程 (PCB) 和作业控制块 JCB。5.3 进程调度进程调度 作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤消该作业的全部进程。因此作业调度程序要调用操作系统内核所提供的有关的进程管理原语。由于进程只能由其父进程建立，所以在一般系统中，作业调度程序都以进程的形式在系统中存在和活动，称为作业调度进程。作业调度进程可以

7、说是系统中的祖先进程，由它完成作业调度的诸多功能。 一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪进程队列和各种事件的进程等待队列。 进程调度的功能是从就绪队列中挑选一个进程到处理机上运行。负责进程调度功能的内核程序称为进程序调度程序。 所谓作业调度程序挑选作业进主存运行是个宏观的概念，实际上被选进主存运行的作业只是具有了竞争处理机的机会(将来真正在处理机上运行的是该作业的一个进程)。而进程调度程序才是真正让某个就绪进程到处理机上运行。5.4 选择调度算法时应考虑的问题选择调度算法时应考虑的问题 目前比较普遍使用

8、的几种调度算法，对于作业调度和进程调度大致上都是适用的。 在设计系统的调度程序时，首先要决定选择何种调度算法，依据此算法来编制相应的调度程序。而调度算法实际上就是系统所采取的调度策略，选择时所要考虑的因素很多。如系统各类资源的均衡使用；对用户公平并使用户满意；用户作业到达系统的时间；作业的优先数；对主存和外设的要求；以及整个系统的效率等。 设计时应将那些对系统运行影响较大的关键因素作为调度算法考虑的主要依据。(1) 设计目标：设计目标：目标不同，系统的设计要求自然不同。如批处理系统所追求的是充分发挥和提高计算机的效率；实时系统所关心的是不要丢失实时信息并及时给以处理；而分时系统则侧重于保证用户

9、的请示及时给予响应；计算中心要求系统吞吐量在大等等。(2) 资源利用率：资源利用率：在考虑设计目标的前提下应充分发挥各种资源的效能，最大限度地使它们忙碌。科学计算型作业和数据处理型作业搭配运行就是一种方法。(3) 均衡地处理系统和用户的要求：均衡地处理系统和用户的要求：例如个别用户可能要求使用系统中的几乎全部外设，却只要求很少的主存。系统若满足这类用户的愿望，势必影响主存利用率，从而降低系统效率，所以一般都不得不推迟这种作业的运行时间，等到有要求内存多而外设少的作业与之搭配运行。但是我们选择的算法也不应使一个作业的运行被无限制地推迟。(4) 在使用优先级的系统中，每个进程都有一个优先数，调度算

10、法应优先运行高优先级进程。(5) 在使用优先数的系统中，调度策略还分为“ 可抢占 ” 和“ 不可抢占 ” 两种方式。抢占策略通常使用于需要迅速响应高优先级进程的系统中。1. 目标目标: 每天运行尽可能多的作业 选择短作业(吞吐量) 使处理机保持“ 忙” 选择大运输量(I/O少) 使I/O保持“ 忙” 选大I/O效率效率:5.5 调度算法调度算法 公平性 FCFS(先来先服务) 对所有进程公平2. 调度算法的衡量调度算法的衡量尽量缩短周转时间周转时间: 作业提交作业完成之间的时间(1) 作业平均周转时间:nTTnii)(1其中 n 作业流中的作业数Ti 第i个作业周转时间Ti= tci tsi其

11、中 tsi 作业i提交时间tci 作业i完成时间(2) 平均带权周转时间:ntTnwwniRiinii)()(11其中: tRi 作业i的实际运行时间wi 作业i的带权周转时间3. 作业调度算法及衡量作业调度算法及衡量 (1) FCFS 先来先服务先来先服务 先来先服务算法是最简单的调度方法。其基本原则是按照作业到达系统或进程进入就绪队列的先后次序来选择。FCFS 策略是属于不可抢占策略不可抢占策略。作业提交时间运行时间开始时间完成时间周转时间带权周转时间ts(时)tR(时)tB(时)tC(时)ti(时)Wi(Z)12348.008.509.009.502.000.500.100.208.00

12、10.0010.5010.6010.0010.5010.6010.802.002.001.601.306.901.004.0016.006.5027.50平均周转时间 T=6.90/4=1.725(小时)平均带权时间 W=27.5/4=6.875 从表面上来说，对于所有进程和作业都是公平的，并且一个作业的等待时间是可以预告估计的。另一方面来说这个方法也不见得公平，当一个大作业先到达系统时就会使许多小作业等待很长时间，提高了平均的作业周转时间，会使许多小作业的用户不满。 先来先服务算法已很少作主要的调度策略，常被结合在其它的调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对许多具有相

13、同优先级的进程，使用先来先服务的原则。(2) 优先级调度算法优先级调度算法 按照进程的优先级大小来调度，使高优先级进程得到优先的处理的高度策略称为优先级调度算法。 但在许多采用优先级调度的系统中，通常采用动态优先数策略。进程的优先级不是固定的，往往随许多因素的变化而变化。尤其随作业（进程）的等待时间、已使用的处理机时间或其它资源的使用情况而定。优先级调度方法又可分为： 非抢占的优先级调度法：即一旦某个高优先级的进程占有了处理机，就一直运行下去，直到由于其自身的原因而主动让出处理机时(任务完成或等待事件)才让另一高优先级进程运行。 可抢占的优先级调度法：任何时刻都严格按照高优先级进程在处理机上运

14、行的原则进行进程的调度。例：某些I/O繁忙型的进程，它们大部分时间是在等待I/O操作完成，对于这一类进程，当它们要求CPU运行时，应立即给予满足，以便让它们开始下一个I/O操作和其它计算型的进程并行工作。否则，这些I/O繁忙型的进程将长时间占据存储器，降低系统并行度。一个行之有效的算法是在进程每次获取CPU运行后，重新指定该进程的优先级为 1/f。这里的f表示进程上次在CPU上实际运行时间与时间片之比。例如，若时间片为100毫秒，进程上次在CPU上的实际运行时间为2毫秒，则它的优称级为50；若它上次实际运行时间为50毫秒，则它的优级为2。由于I/O繁忙型的进程每次在CPU上运行的时间很短，依此

15、算法，它们的优先级将较高，从而优先得到服务。(3) 时间片轮转法时间片轮转法 轮转法是最简单又最公平的进程调度算法，因此也是使用得最多的算法之一。 轮转法分配给每一进程在CPU上运行的时间长度，称之为时间片。诸进程以此时间片为限制，轮流使用CPU。如果时间片到期时，进程尚未完成运行，调度程序将剥夺它正在使用的CPU，转让给另一进程使用；如果进程在使用完它的某一时间片之前已经完成运行或已阻塞，CPU也立即转让给另一进程使用。 轮转法在实现上也很容易，调度程序只要维护一个先进先出的队列数据结构，将就绪进程排队，每当一个进程的时间片运行完后，便把它从原来的队头位置移到队尾，然后把现在处于队头位置的进

16、程调度到CPU上运行。时间片的计数则可通过定时中断实现。 轮转法的性能取决于时间片长度的选择，进程间的CPU上的切换需要时间。若一次切换时间为5毫秒，时间片长度选择为20毫秒，则20的CPU时间花费于进程调度程序。为了改善CPU的利用率，可以增大时间片，比如说为500毫秒，此时CPU利用率达99之多，但每一进程的响应时间也因之增大。若就绪队列中共有10个进程，则每一进程需要等待5秒钟，才能在CPU上服务一次。 通常来说，选择时间片为100毫秒左右比较适宜。 实际中，优先级算法常和轮转法结合使用，也就是按优先级将进程分组，组间采用优先级调度算法，而组内优先级相同的进程则按轮转法调度。显然，若优先

17、级不动态地进行调整，则优先级低的就绪进程就可能饿死。轮转法轮转法 (Round Robin) 简单轮转法 分配给就绪队列，每一进程一个时间片(每一进程在CPU上运行的时间长度)轮流执行。时间qT = N q就绪队列q足够大到每一进程执行完，FCFC (先到先服务)q 适当 进程均匀执行q 太小 开销太大，有切换时间，CPU利用率低。例：切换t = 5ms, q = 20ms, 则CPU利率率80，有20花费在进程调度程序。 决定q 大小因素：响应时间T (进程等待时间)、队列长度N、轮换时间 (切换时间)、CPU能力 (运算速度)。例：上例中为改善CPU的利用率，可增大时间片，设q = 500

18、ms，此时CPU利用率为99之多，但每个P 的相应时间也因而增大。若N = 10，则每个P 的相应时间需等5秒，才能在CPU上服务一次。 考虑上述条件，选择时间片为100ms左右比较适宜。 固定周期轮转法q 为时间片， T 为周期， N 为进程数固定T ：maxNTq 固定T，N q，开销减少(4) SJF最短作业优先的调度算法最短作业优先的调度算法 要求运行时间最短的作业作为下一次服务的对象对于上述作业流，作业1运行结束后，后备作业表中已有作业2， 3， 4， 因为作业3要求运行时间最短， 故选3， 4， 2。tstRtBTiWi12348.008.509.009.502.000.500.1

19、00.208.0010.3010.0010.102.002.301.100.806.201.004.6011.004.0020.60T = 1.55 W=5.15优: 比FCFS， T W缺: 有的作业始终得不到运行tc10.0010.8010.1010.30作业提交时间运行时间开始时间完成时间周转时间带权周转时间(5) 最短剩余时间优先调度算法最短剩余时间优先调度算法 最短剩余时间优先调度算法是把最短作业优称算法使用于分时环境中的变型。其基本思想是让运行到作业完成时所需的运行时间最短的进程优先得到处理，其中包括新进入系统的进程。在最短作业优先策略中，一个作业一旦得到处理机就一直运行到完成（或等待事件）而不能被抢占（除非主动让出处理机）。而最短剩余时间优先策略是可以被一个新进入系统的，并且其运行时间少于当前运行进程的剩余运行时间的进程所抢占。 本策略的优点是可以用于分时系统，保证及时响应用户要求。缺点是系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小。其次，抢占本身也要消耗处理机时间。这个策略使短作业一进入系统就能立即得到服务，从而降低作业的平均等待时间。(6) 响应比高者优先响应比高者优先(HRN)算法算法响应比作业运行时间作业等待时间作业运行时间作业响应时间1pR上题: 顺序1-3-2-412