Operating System——Processor Dispatching

Posted by Sakura on June 24, 2018

操作系统——处理机调度

前言

操作系统原理是武汉大学计算机学院软件工程专业大二下半学期所学习的一门专业课,教材为西安电子科技大学出版社的计算机操作系统第4版,这个专题的博客为该课程的学习笔记,该博客的主要内容是处理机调度和相关的调度算法


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

处理机调度的层次

1.高级调度(作业调度、长程调度、宏观调度)(周期长,频率低)

按照系统预定的调度策略决定把后备队列作业中的哪些作业调入主存,为它们创建进程并启动它们运行。在作业完成后,进行必要的善后处理。

高级调度主要用于多道批处理系统中,在分时系统和实时系统中不设置高级调度。

2.低级调度(进程调度、短程调度、微观调度)(频率最高)

按照某种策略从就绪队列中选择一个进程,把处理机分配给它。

3.中级调度(内存调度、对换调度、中程调度)

内存中暂时不运行或不能运行的进程被换出至外存,这时这个进程处于挂起状态,当进程具备了运行条件,且主存又有空闲区域时,再由中级调度决定把一部分这样的进程重新调回主存工作。

引入中级调度的目的是提高内存利用率和系统吞吐量。

中级调度的运行频率介于进程调度和作业调度两者之间。

P.S.所有的系统都必须配备低级调度。

P.S.并非所有的系统都需要作业调度、中程调度。

处理机调度算法的目标

处理机调度的主要任务是按一定的调度算法选择进程(作业),并使它们运行。

由于操作系统的类型及目标不同,因此选择的调度方式和调度算法也不同。

选择调度算法有以下准则:

  • 面向用户的准则:
    • 周转时间短:指从作业提交到作业完成的时间间隔。批处理系统用户看重
    • 响应时间快:指从用户提交请求到系统产生响应的时间间隔。分时系统用户看重
    • 截止时间的保证:截止时间是指某任务必须开始执行或必须完成的最迟时间。实时系统用户看重
    • 稳定性:对某用户的作业而言,调度策略不应使其响应时间和周转时间变化太大。
  • 面向系统的准则:
    • 系统吞吐量高:吞吐量指单位时间内所完成的作业数。批处理系统看重
    • CPU利用率好:大中型主机看重,对微机和实时系统不太重要
    • 各类资源的平衡利用:让各类资源都忙碌。大中型主机看重,对微机不太重要

分时系统的目标:响应时间快、均衡性(系统响应时间的快慢应与用户所请求服务的复杂性相适应).

实时系统的目标:截止时间的保证(开始执行的最迟时间或必须完成的最迟时间)、可预测性

相关概念介绍

资源利用率:为提高系统的资源利用率,应使系统中的处理机和其他所有资源都尽可能保持忙碌状态。 example

周转时间 作业的周转时间是指从作业提交到作业完成之间的时间间隔。即:周转时间=完成时刻-提交时刻

实际上,它是作业在系统里的等待时间与实际运行时间之和。

平均周转时间是指多个作业的周转时间的平均值。即n个作业的平均周转时间:

example (其中Ti为作业 i 的周转时间)

周转时间包括四部分时间:

  • 作业在外存后备队列上等待作业调度的时间
  • 进程在就绪队列上等待进程调度的时间
  • 进程在CPU上执行的时间
  • 进程等待I/O操作完成的时间

(后三项在一个作业的整个处理过程中,可能发生多次)

带权周转时间是指作业周转时间与作业实际运行时间的比。

平均带权周转时间是指多个作业的带权周转时间的平均值。即n个作业的平均带权周转时间:

example (其中Ti为作业 i 的周转时间,TSi为作业 i 的实际运行时间。)


作业调度

作业调度的主要任务

作业调度的主要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业进入内存,并为作业做好运行前的准备工作。作业完成后进行善后工作。

作业调度需要决定:

  • 接纳多少作业:取决于多道程序度
  • 接纳哪些作业:取决于调度算法
  • 作业调度的运行频率较低,通常为几分钟一次。

作业调度算法

1.先来先服务调度算法First-Come First-Served,FCFS(非抢占式)

FCFS算法总是选择最先到达的作业或进程。

在进程调度中,从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。

特点:

  • 算法简单,易于实现,
  • 有利于长作业,不利于短作业
  • 有利于CPU繁忙型作业,不利于I/O繁忙型作业 ,可能导致I/O设备和CPU利用率低
  • 未考虑作业的紧迫程度

2.短作业优先调度算法 Shortest Job/Process First,SJF或SPF

该算法总是选择估计运行时间最短的作业或进程。

非抢占式若无特别说明,通常是指非抢占式的算法。

抢占式->进化为最短剩余时间调度算法

特点:

  • 算法调度性能较好
  • 缺点是对长作业不利;未考虑作业的紧迫程度;需要估计运行时间。

可以证明:多个作业同时到达时,短作业优先调度算法的平均周转时间最小。

3.优先权调度算法

选择优先权最高的作业或进程。

优先权通常用优先数来衡量。在某些系统中,优先数越大优先权越高;而在另一些系统中,优先数越大优先权越小。

  • 非抢占式优先权算法:系统一旦将处理机分配给就绪队列中优先权最高的进程后,该进程便一直运行下去,直到完成或因发生某事件使该进程放弃处理机时,系统才将处理机分配给另一个更高优先权的进程。
  • 抢占式优先权调度算法:将处理机分配给优先权最高的进程,使之运行。在进程运行过程中,一旦出现了另一个优先权更高的进程时,进程调度程序就停止原运行进程,而将处理机分配给新出现的高优先权进程。

优先权的类型:静态优先权和动态优先权

  • 静态优先权是在创建进程时确定的,确定之后在整个进程运行期间不再改变。
    • 确定静态优先权的依据有:
      • 进程类型:系统,用户
      • 进程对资源的需求:执行时间,资源数量
      • 用户要求:紧迫程度
      • 到达时间:先到则优先权高
    • 特点:简单易行,系统开销小,但不精确,可能出现低优先权进程长期不被调度的情况。
  • 动态优先权是指在创建进程时,根据进程的特点及相关情况确定一个优先权,在进程运行过程中再根据情况的变化调整优先权。

调整动态优先权的原则有:

  • 占用CPU时间越长,优先权越低
  • 等待时间越长,优先权越高

4.最高响应比优先调度算法

引入动态优先级:优先级随等待时间延长而增加。

算法特点:

  • 有利于短作业—如果等待时间相同,短作业优先;
  • 考虑等待时间—如果作业长度相同,等待时间长的作业优先运行;
  • 不会饥饿—对于长作业,等待的时间足够长时,响应比升高,从而可以获得处理机。

进程调度

进程调度的主要任务

进程调度的主要任务是协调进程对CPU的竞争,即按照某种策略(调度算法)从就绪队列中选取一个进程,将处理机分配给它。

进程调度是操作系统最为核心的部分,进程调度策略的优劣直接影响到整个系统的性能。

进程调度的运行频率很高,一般几十毫秒要运行一次。

进程调度的方式:非抢占方式和抢占方式

  • 非抢占方式:又称非剥夺方式、不可剥夺方式、不可抢占方式。这种调度方式是指一旦将处理机分配给某进程后,便让该进程一直执行,直到该进程完成或发生某事件而进入阻塞状态,才把处理机分配给其他进程。
    • 特点:简单,系统开销小,但无法处理紧急任务。
  • 抢占方式:又称剥夺方式、可剥夺方式。这种调度方式是指允许调度程序根据某种原则去停止正在执行的进程,将已分配给该进程的处理机重新分配给其他进程。
    • 抢占原则有:优先权、短作业优先、时间片等。
    • 特点:系统响应性高,但增加系统开销

进程调度算法

1.(时间片)轮转调度(RR)算法

将所有就绪进程按 FCFS 的原则排成一个队列,每次调度时分配一个 CPU 时间片给队首进程。当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程。

轮转调度算法中,效率和时间片大小有很大关系。时间片小意味着频繁执行进程调度和进程上下文的切换,增加系统开销;时间片长则退化为 FCFS 算法,无法满足短作业和交互式用户的需求。

example example example

example example

2.优先级调度算法

把处理机分配给就绪队列中优先级最高的进程。又可以分为非抢占式和抢占式两种。

3.多队列调度算法

将进程就绪队列拆分为多个,不同的就绪队列采用不同的调度算法,也可以设置不同的优先级。

4.多级反馈队列(multileved feedback queue)调度算法(2015级操作系统考试最后一道大题

设置多个就绪队列,并为每个队列赋予不同的优先级。第1个队列的优先级最高,第2队列次之,其余队列的优先级逐次降低。

同一队列中进程执行的时间片大小相同,不同队列时间片大小不同,队列的优先级越高,其相应的时间片就越短。

当一个新进程进入系统时,首先将它放入第1个队列的末尾,按先来先服务的原则排队等待调度。如果进程在一个时间片结束时尚未完成,调度程序便将该进程转入下一队列的末尾,再同样地按先来先服务原则等待调度执行。如此下去,最后一个队列中使用基本的时间片轮转调度算法(即时间片结束未完成的进程仍加到本队列末尾)。

仅当第1个队列为空时,调度程序才调度第2队列中的进程运行;仅当第1个至第(i-1)个队列均为空时,才会调度第i个队列中的进程运行。

当处理机正在为第i个队列中的某进程服务时,若又有新进程进入优先级较高的队列中,则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在执行进程放回第i个队列末尾,重新将处理机分配给新进程。

example example example