操作系统【五】

三、处理机调度


操作系统学习笔记-9:调度

WHAT:按什么原则分配CPU—进程调度算法

WHEN:何时分配CPU —进程调度的时机

HOW:如何分配CPU —CPU调度过程(进程的上下文切换)

1、处理机调度的层次和调度算法的目标

一个作业,从进入系统并驻留在外存的后备队列上开始,直至作业运行完毕,可能要经历下面三级调度

  • 高级调度(High Scheduling,作业调度)

    • 作业调度也即高级调度,这个阶段可以看作是准备阶段。主要任务是按照一定的规则从外存上处于后备队列的作业中挑选一个或多个作业,为其分配内存,建立 PCB(进程) 等,使它们具备竞争处理机的能力。

      这个阶段进程的状态变化是:无 –> 创建态 –> 就绪态

  • 中级调度(Intermediate-Level Scheduling,提高内存使用率)

    • 内存调度也即中级调度,这个阶段可以看作是优化阶段。主要任务是将暂时不能运行的进程对换到外存中,使它们挂起;而当挂起的进程具备运行条件时,它们会被重新对换回内存,得到激活。这个阶段的主要目的是提高内存利用率和系统吞吐量。

      这个阶段进程的状态变化是: 静止就绪态 –> 活动就绪态,静止阻塞态 –> 活动阻塞态

  • 低级调度(Low Level Scheduling,进程调度)

    • 进程调度即低级调度,这个阶段让进程真正运行起来。主要任务是按照某种算法,从就绪队列中选取一个进程,分配处理机给它。进程调度是最基本、次数最频繁的阶段。

      这个阶段进程的状态变化是: 就绪态 –> 活动态

2、作业与作业调度

作业 是一个比程序更加广泛的概念,它不仅包含了通常的程序和数据,而且还应配有一份作业说明书,系统根据该说明书来对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存的。**

作业步:在作业运行期间每个作业都必须经过若干个相对独立又相互关联的的顺序加工步骤才能得到结果,我们把其中每一个加工步骤称为一个作业步。例如程序作业分为编译、链接、运行作业步。

(1)几个概念

周转时间——指作业提交给系统开始,到作业完成为止的这段时间间隔

  • 周转时间通常作为评价批处理系统性能、选择作业调度方式与算法的准则。

多道程序度:即允许多少个作业同时在内存中运行。

  • 允许多少个作业同时在内存中运行,取决于多道程序度。作业太多 服务质量下降 作业太少 资源利用率低。需要适当的折衷

吞吐量:是指在单位时间内系统所完成的作业数(或工作量)。

(2)进程调度方式

非抢占式:“非抢占”即“不能抢占”。一旦把处理机分配给某个进程后,除非该进程终止或者主动要求进入阻塞态,否则会一直运行下去,不允许其它进程抢占自己占有的处理机。

抢占式:把处理机分配给某个进程 A 后,如果有一个更重要、更紧急的进程 B 需要用到处理机,那么进程 A 会立即暂停,把处理机交给进程 B。

3、调度算法

  • CPU 利用率:忙碌的时间 / 总时间
  • 系统吞吐量:完成作业量 / 总时间
  • 周转时间:作业完成时间 - 作业提交时间 = 作业实际运行的时间 + 等待时间
  • 平均周转时间: 各作业周转时间之和 / 作业数
  • 带权周转时间:周转时间 / 作业实际运行的时间
  • 平均带权周转时间:各作业带权周转时间之和 / 作业数
  • 等待时间:进程或者作业处于等待处理机状态的时间之和,即 周转时间 - 作业实际运行的时间
    • 对于进程来说,等待时间指的是进程建立后等待被服务的时间之和(由于等待 I/O 完成的期间也属于被服务时间,所以这个时间不计入等待时间)
    • 对于作业来说,除了进程建立后的等待时间,还包括作业在外存后备队列中等待的时间
  • 平均等待时间:各作业等待时间之和 / 作业数
  • 响应时间:从用户提交请求到首次产生响应所用的时间

(1) FCFS 算法

FCFS 算法即“先来先服务”算法,类似于我们生活中的排队,谁先来,谁就先享受服务。对于作业调度,它指的是谁先到达后备队列,谁就先出队,进而先被执行;对于进程调度,它指的是谁先到达就绪队列,谁就先出队,进而先被执行。

  • FCFS 算法是非抢占式的算法,不存在某个进程在执行的时候被其它进程抢占处理机的情况。
  • 它的优点是公平、算法实现简单,并且不会导致饥饿(不管等多久,所有进程最后都会运行,不存在某个进程永远得不到处理机的情况)
  • 缺点是对长作业有利、对短作业不利 —— 对于长作业,如果它先到,那么它自然无需做过多的等待,而即使是后到,它等待短作业的时间也是不足挂齿的,所以长作业怎么都不亏;对于短作业,如果它先到,自然也无需做过多等待,但是如果它后到,那么它不得不花很长的时间去等待长作业完成,然而它自己运行所需的时间却是很短的,所以说这个算法对短作业不利。在这种情况下,短作业的带权周转时间会很大,也即周转时间远远大于实际运行时间,表示有大量时间用于等待。
  • 有时候也说 FCFS 算法对 CPU 繁忙型作业有利,对 I/O 繁忙型作业不利。这是因为 CPU 繁忙型作业的特点是需要大量的 CPU 时间进行计算,而很少请求 I/O 操作,通常视作长作业。
  • 适用于批处理系统,不适于分时系统

(2)短作业(进程)优先调度算法SJ(P)F

短作业(进程)优先调度算法SJ(P)F,以要求运行时间长短进行调度,即启动要求运行时间最短的作业。==每次调度时选择当前已到达且运行时间最短的作业/进程.==

可以分别用于作业调度和进程调度

短作业优先(SJF)的调度算法,是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行;

短进程优先(SPF)调度算法,则是从就绪队列中选出一估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时,再重新调度。

SJF平均周转时间和平均带权周转时间明显改善

  • SJF 算法的优点在于,它拥有“最短的”平均等待时间和平均周转时间
  • 缺点在于,虽然这次顾及了短作业,但是没有顾及长作业,对长作业是不利的。因为一旦短作业源源不断进入,那么它们就会不断跑在长作业前面,导致长作业永远无法运行,产生“饥饿”甚至“饿死”现象。
  • 另外一个缺点是,在实际实现中,要做到真正意义上的短作业优先,具有一定难度.由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。

(3)高优先权优先(HPF,Highest Priority First)调度算法

非抢占式优先权调度算法

  • 系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成,或因发生某事件使该进程放弃处理机时,系统才将处理机重新分配给另一优先权最高的进程
  • 主要用于批处理系统中,也可用于某些对实时性要求不严的实时系统中

抢占式优先权调度算法

  • 把处理机分配给优先权最高的进程,但在执行期间,只要出现另一个优先权更高的进程,则进程调度程序就立即停止当前进程的执行,并将处理机分配给新到的优先权最高的进程
  • 注意:只要系统中出现一个新的就绪进程,就进行优先权比较

优先权的类型

  • 静态优先权
    • 静态优先权在创建进程时确定,且在进程的整个运行期间保持不变。
    • 一般地,优先权是利用某一范围内的一个整数来表示的,例如,0-7或0-255,又把该整数称为优先数
    • 确定进程优先权的依据有如下三个方面:
      • (1) 进程类型。 系统进程的优先权高于一般用户进程。
      • (2) 进程对资源的需求。 如进程的估计执行时间及内存需要量少的进程,应赋予较高的优先权
      • (3) 用户要求。 由用户进程的紧迫程度和用户所付费用的多少来确定优先权。
    • 系统开销小、不够精确、一般用在要求不高的系统中
    • 问题:用户将优先权设的较高,对其他进程不利!!短进程优先对长进程不利!!
  • 动态优先权
    • 随进程的推进或随其等待时间的增加而改变,以获得更好的调度性能
    • 可规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高
    • 具有相同优先权初值的进程,则最先进入就绪队列,其将因其动态优先权变得最高而优先获得处理机,此即FCFS算法
    • 具有各不相同的优先权初值的就绪进程,则优先权初值低的进程,在等待了足够的时间后,其优先权便可能升为最高,从而可以获得处理机
    • 当采用抢占式优先权调度算法时,如果再规定当前进程的优先权以速率b下降,则可防止一个长作业长期地垄断处理机

(4)高响应比优先调度算法(HRF)

是FCFS和SJF的结合,克服了两种算法的缺点

调度策略:响应比最高的作业优先启动

==响应比(优先权) = ( 等待时间+实际服务时间 )/ 实际服务时间 =响应时间/实际服务时间= 等待时间 / 实际服务时间 + 1==

==注意这里“要求服务的时间”就是实际需要运行的时间,等待时间则是从进程到达就绪队列的那一刻起,到发生进程调度这一段所花费的时间。==

可以说它同时综合了 FCFS 算法和 SJF 算法的优点。为什么优先调度响应比高的进程?因为当两个进程的等待时间一样时,响应比越高的进程,它的实际运行时间越短,这一点类似于 SJF 算法,优先顾及运行时间短的进程;而当两个进程的实际运行时间一样时,响应比越高的进程,它的等待时间越长,等待时间越长说明该进程越先到达,这一点类似于 FCFS 算法,优先顾及先到达的进程。

  • 等待时间相同的作业,则要求服务的时间愈短,其优先权愈高,——对短作业有利
  • 要求服务的时间相同的作业,则等待时间愈长,其优先权愈高, ——是先来先服务
  • 长作业,优先权随等待时间的增加而提高,其等待时间足够长时,其优先权便可升到很高, 从而也可获得处理机,——对长作业有利

是一种折衷,既照顾了短作业,又考虑了作业到达的先后次序,又不会使长作业长期得不到服务。

(5)简单的时间片轮转法(RR—Round Robin)

系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便停止该进程的执行,并将其放就绪队列尾;然后,再把处理机分配给就绪队列中新的队首。时间片的大小从几ms到几百ms

  • 优点:公平。保证就绪队列中所有进程在一给定的时间内,均能获得一时间片的处理机执行时间
  • 缺点:紧迫任务响应慢。UNIX中采用:时间片+优先权

(6)多级反馈队列调度算法

设置多个就绪队列,并为各个队列赋予不同的优先级第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低该算法赋予各个队列中进程执行时间片的大小也各不相同在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。例如,第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍

  • 有多个级别的就绪队列,各级队列优先级从高到低,时间片从小到大
  • 每次有新进程到达,都会首先进入第一级队列,并按 FCFS 算法被分配时间片。如果时间片用完了而进程还没执行完,那么该进程将被送到下一级队列队尾。如果当前已经是最后一级,则重新放回当前队列队尾
  • 仅当第1~(i-1) 队列均空时,才会调度第i队列中的进程运行
  • 第i队列中某进程正在运行时,该进程因等待事件发生而进入阻塞队列,等待事件发生后,调度程序把进程放回到第i队列的末尾
  • 第i队列中某进程正在运行时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,调度程序把正在运行的进程放回到第i队列的末尾

多级反馈队列调度算法具有较好的性能,能较好的满足各种类型用户的需要。

终端型作业用户。大多属于较小的交互性作业,只要能使作业在第一队列的时间片内完成,便可令用户满意。

短批处理作业用户。周转时间仍然较短,至多在第二到三队列即可完成。

长批处理作业用户。将依次在1~n级队列中轮转执行,不必担心作业长期得不到处理。

习题

调度算法

关于多道程序调度。

关于如何画表,确实没找到太好的方法。

思路1:按照每一段小阶段进行思考划分

  • 原因:只有前一段配合成功且完毕了,后面才能顺序执行下去。且不会有矛盾。
  • 优点:画出来就结束,无需修改前面的部分。
  • 缺点:小阶段的时间段不一致,需要考虑空闲时间是否会发生占领CPU。这样就需要往下考虑一个阶段。破坏了按照每个阶段思考划分的规矩。
    • 方法1:按照每个小阶段的最大时间段划分,将不足的进程小阶段后面的时间段切割为两部分拨给前面一部分的作为补充。
    • 缺点:数量多了容易造成切割多份,增加数量麻烦度。而且造成大量挪移问题。不推荐。

思路2:按照优先级从高到底划分思考,

  • 原因:优先级高的CPU不会被抢占,只会抢占别人CPU,所以先画优先级高的避免CPU线上的的修改。
  • 优点:这样做CPU不需要每次修改了,若低优先级CPU发现使用段中有高优先级CPU,只需要将低优先级分割开,将剩下的部分画到高优先级运行后的空闲段即可。
  • 缺点:若低优先级IO段出现在了高优先级某个IO段开始的前面,需要将高优先级IO段以及后面的小阶段后推。因为IO无法抢占,低优先级的IO先到就使用IO。

思路3:结合使用。将各个小阶段划分为组,每组优先级从高到低,将每组画完。

  • 优点:使得思路2中若有IO出现在前面使得相应进程的之后所有阶段需要后挪的问题中,我们需要挪移的小阶段变少。同时兼顾无需修改CPU的优点。

因为题目不会很复杂使你需要挪很多。所以做题常用思路2,若出现IO挪移问题则使用思路3。

黑笔画表,铅笔涂改。

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~