【计算机操作系统】2-2-调度

处理机调度的概念、层次

  • 基本概念
  • 三个层次
    • 高级调度(作业调度)
    • 中级调度(内存调度)
    • 低级调度(进程调度)
  • 三层调度的联系、对比
  • 补充知识
    • 进程的“挂起态”
    • 七状态模型

调度的基本概念

当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则决定处理这些任务的顺序,这就是“调度”研究的问题。

在多道程序系统中,进程的数量往往是多于处理机的个数的,这样不可能同时并行地处理各个进程。

处理机调度,就是从就绪队列中按照一定的算法选择一个进程将处理机分配给它运行,以实现进程的并发执行。

调度的三个层次——高级调度

由于内存空间有限,有时无法将用户提交的作业全部放入内存,因此就需要确定某种规则来决定将作业调入内存的顺序。

高级调度(作业调度)。按一定的原则从外存上处于后备队列的作业中挑选一个(或多个)作业,给他们分配内存等必要资源,并建立相应的进程(建立PCB),以使它们获得竞争处理机的权利

高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次,调出一次。作业调入时会建立相应的PCB,作业调出时才撤销PCB。高级调度主要是指调入的问题,因为只有调入的时机需要操作系统来确定,但调出的时机必然是作业运行结束才调出。

调度的三个层次——中级调度

引入了虚拟存储技术之后,可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时,再重新调入内存。

这么做的目的是为了提高内存利用率系统吞吐量

暂时调到外存等待的进程状态为挂起状态。值得注意的是,PCB并不会一起调到外存,而是会常驻内存。PCB中会记录进程数据在外存中的存放位置,进程状态等信息,操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。

**中级调度(内存调度)**,就是要决定将哪个处于挂起状态的进程重新调入内存。

一个进程可能会被多次调出、调入内存,因此中级调度发生的频率要比高级调度更高

补充知识:进程的挂起状态与七状态模型

暂时调到外存等待的进程状态为挂起状态(挂起态,suspend)

挂起态又可以进一步细分为就绪挂起阻塞挂起两种状态。

注意“挂起”和“阻塞”的却别,两种状态都是暂时不能获得CPU的服务,但挂起状态是将进程映像调到外存去了,而阻塞态下进程映像还在内存中。

有的操作系统会把就绪挂起、阻塞改期分为两个挂起队列,甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

调度的三个层次——低级调度

**低级调度(进程调度)**,其主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它。

进程调度是操作系统中最基本的一种调度,在一般的操作系统中都必须配置进程调度。

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

三层调度的联系、对比

要做什么 调度发生在什么时候 发生频率 对进程状态的影响
高级调度(作业调度) 按照某种规则,从后备队列中选择合适的作业将其调入内存,并为其创建进程 外存->内存(面向作业) 最低 无->创建态->就绪态
中级调度(内存调度) 按照某种规则,从挂起队列中选择合适的进程将其数据调回内存 外存->内存(面向进程) 中等 挂起态->就绪态(阻塞挂起->阻塞态)
低级调度(进程调度) 按照某种规则,从就绪队列中选择一个进程为其分配处理机 内存->CPU 最高 就绪态->运行态

进程调度的时机、切换与过程调度方式

  • 时机
    • 什么时候需要进程调度
    • 什么时候不能进行进程调度
  • 切换与过程
    • “下一的调度”与“切换”的区别
    • 进程切换的过程需要做什么?
  • 方式
    • 非剥夺调度方式(非抢占式)
    • 剥夺调度方式(抢占式)

进程调度的时机

进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

  • 需要进行切换调度与切换的情况
    • 当前运行的进程主动放弃处理机
      • 运行正常终止
      • 运行过程中发生异常而终止
      • 进程主动请求阻塞(如等待I/O)
    • 当前运行的进程被动放弃处理机
      • 分给进程的时间片用完
      • 有更紧急的事需要处理(如I/O中断)
      • 有更高优先级的进程进入就绪队列
  • 不能进行进程调度与切换的情况
    1. 处理中断的过程中。中断处理过程复杂,与硬件模切相关,很难做到在中断处理过程中进行进程切换。
    2. 进程在操作系统内核程序临界区中。一定是内核程序临界区!!!
    3. 在**原子操作过程中(原语)。原子操作不可中断,要一气呵成(如之前讲过的修改PCB中进程状态标志,并把PCB放到相应队列)。

临界资源:一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区:访问临界资源的那段代码。

内核程序临界区一般用来访问某种内核数据结构的,比如进程的就绪队列(由各就绪进程的PCB组成)

如果还没退出临界区(还没解锁)就进行进程调度,但是进程调度相关的程序也需要访问就绪队列,因此又无法顺利进行进程调度。

内核程序临界区访问的临界资源如果不尽快释放的话,极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。

在打印机打印完成之前,进程一直处于临界区内,临界资源不会解锁。但打印机又是慢速设备,此时如果一直不允许进程调度的话就会导致CPU一直空闲

普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

进程调度的方式

非剥夺调度方式

又称非抢占方式。即,只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。

实现简单,系统开销小但是无法及时处理紧急任务,适合于早起的批处理系统。

剥夺调度方式

又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或者更紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的那个进程。

可以优先处理更紧急的进程,也可以实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统。

进程的切换与过程

“狭义的进程调度”与“进程切换”的区别:

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程),进程切换是指一个进程让出处理机,由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了:

  1. 对原来运行进程各种数据的保存
  2. 对新的进程各种数据的恢复

(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息,这些信息一般保存在进程控制块)

注意:进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少。

调度算法的评价指标

  • CPU利用率
  • 系统吞吐量
  • 周转时间
    • 周转时间、平均周转时间
    • 带权周转时间、平均带权周转时间
  • 等待时间
  • 响应时间

CPU利用率

由于早期的CPU造价及其昂贵,因此人们会希望让CPU尽可能多地工作

CPU利用率:指CPU“忙碌”的时间占总时间的比例。

利用率=忙碌的时间/总时间

系统吞吐量

对于计算机来说,希望能用尽可能少的时间处理完尽可能多的作业

系统吞吐量:单位时间内完成作业的数量

系统吞吐量=总共完成了多少道作业/总共花了多少时间

周转时间

对于计算机的用户来说,他很关心自己的作业从提交到完成花了多少时间。

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

它包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个过程中,可能发生多次。

周转时间=作业完成时间-作业提交时间

对于用户来说,更关心自己的单个作业的周转时间。

平均周转时间=各作业周转时间之和/作业数

对于操作系统来说,更关心系统的整体表现,因此更关心所有作业周转时间的平均值。

带权周转时间

带权周转时间=作业周转时间/作业实际运行的时间=(作业完成时间-作业提交时间)/作业实际运行的时间

带权周转时间必然>=1

带权周转时间与周转时间都是越小越好

对于周转时间相同的两个作业,实际运行时间长的作业在相同时间内被服务的时间更多,带权周转时间更小,用户满意度更高。

对于实际运行时间相同的两个作业,周转时间短的带权周转时间更小,用户满意读更高。

等待时间

计算机的用户希望自己的作业尽可能少的等待处理机

等待时间,指进程/作业处于等待处理机状态时间之和,等待时间越长,用户满意度越低。

作业调入内存后,建立对应的进程。这个进程会被CPU服务、会被I/O设备服务,当然也会有等待被服务的时候。

对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,等待I/O完成的期间其实进程也是在被服务的,所以不计入等待时间。

对于作业来说,不仅要考虑建立进程后的等待时间,还要加上作业在外存后备队列中等待的时间

一个作业总共需要被CPU服务多久,被I/O设备服务多久一般是确定不变的,因此调度算法其实只会影响作业/进程的等待时间。当然,与前面指标类似,也有“平均等待时间”来评价整体性能。

响应时间

对于计算机用户来说,会希望自己的提交的请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应。

响应时间,指从用户提交请求首次产生响应所用的时间。

调度算法

  • 先来先服务(FCFS)

  • 短作业优先(SJF)

  • 高响应比优先(HRRN)

  • 各种调度算法的学习思路

    1. 算法思想
    2. 算法规则
    3. 这种调度算法是用于 作业调度 还是 进程调度?
    4. 抢占式?非抢占式?
    5. 优点和缺点
    6. 是否会导致饥饿(某进程/作业长期得不到服务)

先来先服务(FCFS)

  • 算法思想
    • 主要从“公平”的角度考虑
  • 算法规则
    • 按照作业/进程到达的先后顺序进行服务
  • 用于作业/进程调度
    • 用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,考虑的是哪个进程先到达就绪队列
  • 是否可抢占?
    • 非抢占式的算法
  • 优缺点
    • 优点:公平、算法实现简单
    • 缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。
  • 是否会导致饥饿
    • 不会

短作业优先(SJF)

  • 算法思想
    • 追求最少的平均等待时间,最少的平均周转时间、最少的平均带权周转时间
  • 算法规则
    • 最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)
  • 用于作业/进程调度
    • 即可用于作业调度,也可用于进程调度。用于进程调度时称为“短进程优先(SPF)算法”
  • 是否可抢占
    • SJF和SPF是非抢占的算法。但是也有抢占式的版本——最短剩余时间优先算法(SRTN)
  • 优缺点
    • 优点:“最短的”平均等待时间、平均周转时间
    • 缺点“不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先。
  • 是否会导致饥饿
    • 会。如果源源不断地有短作业/进程到来,可能使长作业/进程长时间得不到服务,产生“饥饿”现象。如果一直得不到服务,则称为“饿死”。

最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度

  • 几个小细节:
    1. 如果题目中未特别说明,所提到的“短作业/进程优先算法”默认非抢占式的。
    2. 很多书上会说“SJF调度算法的平均等待时间、平均周转时间最少”。严格来说,这个表述是错误的,不严谨的。短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。应该加上一个条件“在所有进程同时可运行时”,采用SJF调度算法的平均等待时间、平均周转时间最少;或者说“在所有进程都几乎同时到达时,采用SJF调度算法的平均等待时间、平均周转时间最少”;如果不加上述前提条件,则应该说“抢占式的短作业/进程优先调度算法(最短剩余时间优先,SNRT算法)的平均等待时间、平均周转时间最少”
    3. 虽然严格来说,SJF的平均等待时间、平均周转时间并不一定最少,但相比于其他算法(如FCFS),SJF依然可以获得较少的平均等待时间、平均周转时间。
    4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选线,那最好判断其他选项是不是有很明显的错误,如果没有更合适的选项,那也应该选择该选项。

对FCFS和SJF两种算法的思考

FCFS算法是在每次调度的时候选择一个等待时间最长的作业(进程)为其服务。但是没有考虑到作业的运行时间,因此导致了对短作业不友好的问题

SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间,因此导致了对长作业不友好的问题,甚至还会造成饥饿问题。

高响应比优先(HRRN)

  • 算法思想
    • 要综合考虑作业/进程的等待时间和要求服务的时间
  • 算法规则
    • 在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务
    • 响应比=(等待时间+要求服务时间)/要求服务时间
    • 响应比必然>=1
  • 用于作业/进程调度
    • 也可用于进程调度
  • 是否可抢占?
    • 非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时,才需要调度,才需要计算响应比。
  • 优缺点
    • 综合考虑了等待时间和运行时间(要求服务时间)
    • 等待时间相同时,要求服务时间短的优先(SJF的优点)
    • 要求服务时间相同时,等待时间长的优先(FCFS的优点)
    • 对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题
  • 是否会导致饥饿
    • 不会

高响应比优先算法:非抢占式的调度算法,只有当前运行的进程主动放弃CPU时(正常/异步完成,或主动阻塞),才需要进程调度,调度时计算所有就绪进程的响应比,选响应比最高的进程上处理机。


这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急成都,因此对于用户来说,交换性很糟糕。因此这三种算法一般适合用于早起的批处理系统,当然,FCFS算法也常结合其他的算法使用,在现在也扮演着很重要的角色。

调度算法

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

  • 优先级调度算法

  • 多级反馈队列调度算法

  • 各种调度算法的学习思路

    1. 算法思路
    2. 算法规则
    3. 这种调度算法是用于 作业调度 还是 进程调度
    4. 抢占式?非抢占式?

时间片轮转(RR)

  • 算法思想
    • 公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应
  • 算法规则
    • 按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列对位重新排队。
  • 用于作业/进程调度
    • 用于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)
  • 是否可抢占?
    • 若进程未能在时间片内运行完,将被强心剥夺处理机使用权,因此时间片轮转调度算法属于抢占式算法。由时钟装置发出时钟中断来通知CPU时间片已到。
  • 优缺点
    • 优点:公平;响应快,适用于分时操作系统。
    • 缺点:由于高频率的进程切换,因此有一定开销;不区分任务的紧急程度。
  • 是否会导致饥饿
    • 不会

常用于分时操作系统,更注重“响应时间”。

如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法将退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大

另一方面,进程调度、切换是有时间代价的(保存、恢复运行环境),因此如果时间片太小,会导致进程切换过于频繁,系统会话大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小

优先级调度算法

  • 算法思想
    • 随着计算机的发展,特别是实时操作系统的出现,越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
  • 算法规则
    • 每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程。
  • 用于作业/进程调度
    • 即可用于作业调度,也可用于进程调度。甚至,还会用于在之后会学习的I/O调度中。
  • 是否可抢占
    • 抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可,而抢占式还需在就绪队列变化时,检查是否会发生抢占。
  • 优缺点
    • 优点:用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
    • 缺点:若源源不断地有高优先级进程到来,则可能导致饥饿。
  • 是否会导致饥饿

抢占式的优先级调度算法:每次调度时选择当前已到达优先级最高地进程。当前进程主动放弃处理机时发生调度。另外,当就绪队列发生改变时也需要检查是否会发生抢占。

就绪队列未必只有一个,可以按照不同优先级来组织。另外,也可以把优先级高的进程排在更靠近队头的位置。

根据优先级是否可以动态改变,可将优先级分为静态优先级动态优先级两种。

  • 静态优先级:创建进程时确定,之后一直不变。

  • 动态优先级:创建进程时有一个初始值,之后会根据情况动态地调整优先级。

  • 通常

    • 系统进程优先级高于用户进程
    • 前台进程优先级高于后台进程
    • 操作系统更偏好I/O型进程(或称I/O繁忙型进程)

注:与I/O型进程相对的是计算型进程(活成CPU繁忙型进程)

I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话,则越有可能让I/O设备尽早地投入工作,则资源利用率、系统吞吐量都会得到提升。

  • 可以从追求公平、提升资源利用率等角度考虑
    • 如果某进程在就绪队列中等待了很长时间,则可以适当提升其优先级
    • 如果某进程占用处理机运行了很长时间,则可适当降低其优先级
    • 如果发现一个进程频繁地进行I/O操作,则可适当提升其优先级

多级反馈队列调度算法

  • 算法思想
    • 对其他调度算法的这种权衡
  • 算法规则
    1. 设置多级就绪队列,各队列优先级从高到低,时间片从小到大
    2. 新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾。
    3. 只有第K级队列为空时,才会为K+1级队头的进程分配时间片
  • 用于作业/进程调度
    • 用于进程调度
  • 是否可抢占?
    • 抢占式的算法。在k级队列的进程运行过程中,若更上级的队列(1~k-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回k级队列队尾。
  • 优缺点
    • 对各类型进程相对公平(FCFS的优点)
    • 每个新到达的进程都可以很快就得到响应(RR的优点)
    • 短进程只用较少的时间就可完成(SPF的优点)
    • 不必实现估计进程的运行时间(避免用户作假)
    • 可灵活地调整对各类进程的偏好程度,比如CPU密集型进程、I/O密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列,这样I/O型进程就可以保持较高优先级)
  • 是否会导致饥饿

设置多级就绪队列,各级队列优先级高到底时间片小到大

新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经在最下级的队列,则重新放回最下级队列队尾。

只有第k级队列为空时,才会为k+1级队头的进程分配时间片

被抢占处理机的进程重新放回原队列队尾。


比起早期的批处理操作系统来说,由于计算机造价大幅降低,因此之后出现的交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIX使用的就是多级反馈队列调度算法)