《操作系统调度.ppt》由会员分享，可在线阅读，更多相关《操作系统调度.ppt（46页珍藏版）》请在课桌文档上搜索。
1、第六章 处理机调度,6.1 调度类型,6.2 进程调度的算法及评价,6.3 作业的调度,6.4 作业调度算法,一、处理机的3级调度,6.1 调度类型,在大型通用系统中，可能有数百个批处理作业存放在磁盘的作业队列中，有数百个终端同主机相联接。因此如何从这些作业中挑选作业进入主存运行、如何在作业或进程间分配处理等，问题无疑是操作系统的资源管理功能中的一个重要问题。本章主要讨论处理机分配问题，或称处理机调度。,6.1 调度类型,一般来说，处理机调度可以分成三级：(1)高级调度：又称作业调度，其主要功能是按照某种原则从磁盘某些盘区的作业队列中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的
2、善后工作。(2)中级调度：它决定哪些进程被允许参与竞争处理机资源。中级调度主要只是起到短期调整系统负荷的作用，以平顺系统的操作。其所使用的方法是通过“挂起”和“解除挂起”一些进程，来达到平顺系统操作的目的。,6.1 调度类型,(3)低级调度：又称进程调度，其主要功能是按照某种原则将处理机分配给就绪进程。执行低级调度功能的程序称为进程调度程序，由它实现处理机在进程间的转换。它必须常驻主存，是操作系统内核的主要部分。,6.1 调度类型,二、作业的状态与处理流程,6.1 调度类型,宏观上：作业调度微观上：进程调度,作业和进程的状态转换图,6.1 调度类型,作业从提交给系统直到它完成后离开系统前的整个
3、活动常划分为若干阶段。作业在每一阶段中所处的状况称为作业的状态。系统中的作业通常分为四种状态。,6.1 调度类型,提交状态 当用户提交作业给系统管理员，将作业存入外存时，是一暂时性的状态。系统尚感知不到作业。后备状态 收容状态。系统收到一作业的全部信息后，为其建立作业控制块JCB，将JCB排在后备队列中。此时，作业已具备进入运行状态的条件，等待作业调度。运行状态 后备队列中作业被作业调度程序按一定算法选中，程序和数据被调入内存，OS为其建立PCB，一新进程建立。此时，系统管理由作业调度进入进程调度。完成状态 作业运行结束，处于完成状态，是暂时性状态。系统为该作业做收尾工作。,6.2 进程调度的
4、算法及评价,作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤消该作业的全部进程。因此作业调度程序要调用操作系统内核所提供的有关的进程管理原语。由于进程只能由其父进程建立，所以在一般系统中，作业调度程序都以进程的形式在系统中存在和活动，称为作业调度进程。作业调度进程可以说是系统中的祖先进程，由它完成作业调度的诸多功能。,6.2 进程调度的算法及评价,一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪进程队列和各种事件的进程等待队列。进程调度的功能是从就绪队列中挑选一个进程到处理机上运行。
5、负责进程调度功能的内核程序称为进程调度程序。,6.2 进程调度的算法及评价,所谓作业调度程序挑选作业进主存运行是个宏观的概念，实际上被选进主存运行的作业只是具有了竞争处理机的机会(将来真正在处理机上运行的是该作业的一个进程)。而进程调度程序才是真正让某个就绪进程到处理机上运行。,一、先来先服务(FCFS)调度算法,6.2 进程调度的算法及评价,基本思想：从就绪队列中选择一个最先进入该队列的进程，将CPU分配给该进程，进入执行状态，一直运行到完成或发生某事件而让出CPU。,6.2 进程调度的算法及评价,对“先来先服务”调度算法的评价：最简单的一种调度算法。有利于长进程，不利于短进程有利于CPU繁
6、忙的作业（科学计算），不利于I/O繁忙的作业（事务处理）。若不因I/O中断，则可一直运行到结束。,6.2 进程调度的算法及评价,用进程周转时间来评价 性能。进程周转时间：从进程进入就绪队列开始，到进程完成为止的时间间隔。平均周转时间：系统中多个进程的周转时间的平均值。用户期望自己的周转时间最短。系统管理员希望平均周转时间最短，则系统整体性能较好。,6.2 进程调度的算法及评价,例：3个进程A、B、C先后（几乎又是同时）进入就绪队列，其分别需运行24ms、3ms、3ms。左图显示了按“先来先服务”算法，各进程运行的先后及周转时间。可见：B等了24ms，而C等了27ms才得运行。平均周转时间：(2
7、4+27+30)/3=27ms若进程按B、C、A顺序来到就绪队列，参见右图。可见：平均周转时间：(3+6+30)/3=13ms。,24,27,30,30,3,6,二、时间片轮转(RR)调度算法,6.2 进程调度的算法及评价,基本思想：使就绪队列中所有进程，在一给定的时间内，均能获得一个时间片的CPU执行时间。在使用完一个时间片后，即使进程还没有运行完毕，也要强迫它释放CPU，让给另一进程使用。而该进程回到就绪队列末尾，排队等待下一次调度的到来。,6.2 进程调度的算法及评价,时间片大小的确定，对机器性能有很大影响。系统响应时间：T=Nq N:用户进程数，q:时间片首先要满足系统对响应时间的要求
8、，不能太长，不然用户就会有等待的感觉（一般响应时间应在3秒以下）。进程数一定，时间片长短与系统响应时间成正比。系统处理能力，应保证在1个时间片内，将用户键入的常用命令能处理完毕，否则无法得到满意的响应时间。该算法多用于分时操作系统。,三、优先级调度算法,6.2 进程调度的算法及评价,基本思想：为系统中每一个进程规定一个优先级，就绪队列中具有高优先级的进程有优先获得CPU的权利；如果几个进程的优先级相同，则按先来先服务算法调度。,6.2 进程调度的算法及评价,确定优先级的一些因素：(1)按进程的类型。系统进程还是用户进程。(2)按程序的性质。CPU繁忙的进程影响系统整体效能，优先级较低，而I/O
9、繁忙的进程则优先级较高。(3)按用户的请求。进程优先级可分动态和静态两类。静态优先级：在创建进程时确定，并在整个运行期间保持不变。动态优先级：在创建时赋予的优先数，随进程的推进而改变，以获得更好的调度性能。,四、多级队列调度算法,6.2 进程调度的算法及评价,又称多级反馈队列调度算法。该算法是时间片算法与优先级算法的结合。系统安排情况：有多个就绪队列，每个就绪队列具有不同的优先权，可获得不同长度的时间片。参见图例：S1队列优先权最高，所获时间片最短。Sn队列优先权最低，所获时间片最长。,6.2 进程调度的算法及评价,6.3 作业的调度,系统中往往有成百个作业被收容在磁盘输入井中，为了管理和调度
10、作业，就必须记录已进入系统的各作业的情况。因此同进程中的情况类似，系统也为每个作业设置一个作业控制块(记为JCB)，它记录了作业的有关信息。不同系统的 JCB 所包含的信息有所不同，这取决系统对作业调度的要求。,一、作业控制块(JCB),6.3 作业的调度,每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见右图。,6.3 作业的调度,JCB 是在作业进入系统时由 SPOOL 系统为其建立的。其内容由作业控制卡中得到。同样 JCB 也是作业存在于系统的标志，作业进入系统时，则为之建立 JCB。当作业退出系统
11、时，则其 JCB 也被撤消。在磁盘输入井中的所有后备作业按作业类型将它们组成一个或多个后备作业队列。所谓后备作业队列是由作业控制块 JCB 用表格或链指针组成的队列。作业队列可按优先数大小和作业到达系统的时间顺序排列。,6.3 作业的调度,根据系统内所有资源的使用情况，按照某种调度算法选择一个后备作业进入系统，并为其创造一个进程。为此，作业调度还要为选中的作业分配资源，作好作业执行前的准备。作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进程(PCB)和作业控制块 JCB。完成作业调度功能的程序称为作业调度程序。,作业调度程序,二、选择调度算法时应考虑问题,6.
12、3 作业的调度,作业调度程序按一定的算法，负责挑选后备队列中的一些作业进入运行状态。目前比较普遍使用的几种调度算法，对于作业调度和进程调度大致上都是适用的。,在设计系统的调度程序时，首先要决定选择何种调度算法，依据此算法来编制相应的调度程序。而调度算法实际上就是系统所采取的调度策略，选择时所要考虑的因素很多。,(1)公平对待后备队列中每一个作业，顾及各种类型作业的情况。例如:个别用户可能要求使用系统中的几乎全部外设，却只要求很少的主存。系统若满足这类用户的愿望，势必影响主存利用率，从而降低系统效率，所以一般都不得不推迟这种作业的运行时间，等到有要求内存多而外设少的作业与之搭配运行。但是我们选择
13、的算法也不应使一个作业的运行被无限制地推迟。(2)均衡使用系统资源，克服资源忙闲不均情况出现。在考虑设计目标的前提下应充分发挥各种资源的效能，最大限度地使它们忙碌。科学计算型作业和数据处理型作业搭配运行就是一种方法。(3)提高整个系统的吞吐能力。,6.3 作业的调度,在批处理系统中，系统吞吐能力是衡量算法的主要着眼点，通常用作业的“周转时间”来定量判断。周转时间：作业提交作业完成之间的时间 Ti=Wi-Si Si：作业i 提交给系统的时间 Wi：作业i完成的时间 带权周转时间：Wi=Ti/运行时间平均周转时间：n个作业的平均周转时间 T=（T1+T2+.+Tn）/n平均带权周转时间:W=（W1
14、+W2+.+Wn）/n,一、先来先服务调度算法,6.4 调度算法,基本思想：以作业进入后备队列的先后为依据。从后备队列选一个或多个最先进入队列的作业将作业调入内存、分配资源、创建进程放入进程就绪队列,6.4 调度算法,例：三个作业按表中顺序同时提交系统，采用先来先服务作业调度算法。求出每个作业的周转时间和它们的平均周转时间。分析：三作业同时提交系统，可看作到达时间都为0，Si=0解:T1=W1-S1=24-0=24 T2=W2-S2=(24+3)-0=27T3=W3-S3=(24+3+3)-0=30T=(T1+T2+T3)/3=(24+27+30)/3=27,0,24,27,30,6.4 调度
15、算法,例：5个作业提交系统，采用先来先服务作业调度算法。求出每个作业的周转时间和它们的平均周转时间。解:T=(T1+T2+T3+T4+T5)/5=(0.7+1+1.2+1.5+1.6)/5=1.2,.1,10,10.8,.3,.5,.7,.6,11.3,11.7,12.1,12.3,6.4 调度算法,例：,6.4 调度算法,平均周转时间 T=6.90/4=1.725(小时)平均带权时间 W=27.5/4=6.875,6.4 调度算法,从表面上来说，对于所有进程和作业都是公平的，并且一个作业的等待时间是可以预先估计的。另一方面来说这个方法也不见得公平，当一个大作业先到达系统时就会使许多小作业等待
16、很长时间，增加了平均作业周转时间，会使许多小作业的用户不满。先来先服务算法已很少作主要的调度策略，常被结合在其它的调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对许多具有相同优先级的进程，使用先来先服务的原则。,二、短作业优先调度算法,6.4 调度算法,基本思想：作业调度程序在后备队列中选择一个或多个估计运行时间最短的作业。作业运行时间的多少由用户估计，并与作业一起提交给系统管理员。,6.4 调度算法,例：三个作业按表中顺序同时提交系统，采用短作业优先作业调度算法。求出每个作业的周转时间和它们的平均周转时间。分析：三作业同时到达系统，作业调度顺序见表。解:T1=W1S1=30-0
17、=30T2=W2S2=3-0=3T3=W3S3=6-0=6T=(T1+T2+T3)/3=(3+6+30)/3=13,0,3,6,30,6.4 调度算法,.1,10,10.8,.3,.5,.7,.6,11.4,11.8,12.3,平均周转时间：T=(T1+T2+T3 T4+T5)/5=1.02,11,6.4 调度算法,T=6.20/4=1.55(小时)W=20.6/4=5.15,优:比FCFS，T下降、W下降缺:有的作业始终得不到运行,6.4 调度算法,与先来先服务算法比较，平均周转时间有下降，有效地降低作业的等待时间，提高了系统的吞吐量。评价：不利于长作业，有利于短作业。,三、高响应比优先调度
18、算法,6.4 调度算法,作业的响应比Rp：Rp=作业响应时间/要求运行时间=(作业已等待时间+要求运行时间)/要求运行时间=1+作业已等待时间/要求运行时间作业调度程序每当挑选作业时，先计算当时后备队列中各作业的响应比，然后选择其中响应比最高的作业进入运行状态。,6.4 调度算法,分析：初始仅作业1，选择作业1。作业1在时间10.0时完成，计算这时其余各作业的响应比，最高者为作业3。选择作业3。,当前CPU时间=10.0,6.4 调度算法,响应比的计算:,第一步:,6.4 调度算法,当前CPU时间=10.1,作业3在时间10.1时完成，计算这时其余各作业的响应比，最高者为作业2。选择作业2。作
19、业2在时间10.6时完成，,第二步:,系统中仅剩作业4，选作业4。作业4在时间10.8时完成。各作业的周转时间见表。,平均周转时间:T=6.50/4=1.625平均带权周转时间：W=22.7/4=5.675,6.4 调度算法,响应比=1+（已等待时间/所需CPU时间）算法既照顾短作业，又考虑作业到达先后，并且还兼顾到长作业，是一种折中算法。算法首先有利于短作业。要求服务时间越小，则响应比越大。当要求服务时间相同时，则响应比取决于等待时间。则满足了先来先服务。当等待时间足够长，响应比上升很高，长作业也照顾到了。缺点：每次调度要计算响应比，增加了系统时间开销。,8.0,10,9.0,8.5,10.1,10.6,9.5,10.8,操作系统术语 6,24、调度：Scheduler25、响应时间：Response Time26、最短作业优先：Shortest Process Next27、最高响应比优先：Highest Response Ratio Next 28、时间片轮转：Round-Robin,
