操作系统概述(2.2处理机调度)

操作系统——2.2 处理机调度

一、基本概念

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

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

一些概念的介绍：

• 作业：一个具体的运行任务
• 用户向系统提交一个作业 ≈用户让操作系统启动一个程序（来处理一个具体的任务）

1.1高级调度（作业调度）

按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入会建立PCB，调出时才撤销PCB。

• 简单理解就是：好几个程序需要启动，这个调度方式要确定先调度哪个。
• ***作业控制块（JCB）：**操作系统想用户提供的一组作业控制语言，用户将这种语言写作业说明书，然后程序、数据和作业一起交给系统操作员。
• *多道批处理系统通常配有作业调度，其他系统中通常不需要配置作业调度。

1.2 中级调度（内存调度）

按照某种策略决定将那个处于挂起状态的进程重新调入内存。

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

• 内存不够时，可将那些暂时用不上的进程调度至外存等待，等内存空闲或者进程需要运行的时候再重新调入内存。

• 此时进程状态为挂起态，被挂起的进程PCB会被组织成挂起队列。

中级调度实际上是存储器管理中的对换功能。

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

1.3 低级调度（进程调度 / 处理机调度）

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

这是一种最基本的调度，调用频率最高。

1.4 进程的挂起

被挂起的进程称为 挂起态（suspend）

挂起态可以进一步分为就绪挂起和阻塞挂起。

• 进程在就绪态可以挂起为就绪挂起，就绪挂起可以激活为就绪态
• 进程在阻塞态可以挂起为阻塞挂起，阻塞挂起可以激活为阻塞态
• 阻塞挂起可以在事件出现的时候变成就绪挂起
• 并且，在创建态和运行态的进程，也可以直接挂起为就绪挂起

！挂起和阻塞的区别：

• 两种状态都是参数不能获得CPU的服务的
• 挂起态是将进程调到外存去了，阻塞态下的进程还在内存中。
• 有的操作系统会把就绪挂起，阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同，把挂起队列细分为多个队列。

调度	调度发生在	发生频率	对进程状态的影响
高级调度（作业调度）	外存->内存（面向作业）	最低	无->创建态->就绪态
中级调度（内存调度）	外存->内存（面向进程）	中等	挂起态->就绪态（阻塞挂起->阻塞态）
低级调度（进程调度）	内存->CPU	最高	就绪态->运行态

二、进程调度方式

2.1进程调度的时机

！什么时候需要进程调度

• 当前运行的进程主动放弃处理机

  • 进程终止
  • 运行过程中发生异常而终止
  • 进程主动请求阻塞（如：等待IO）
  • 有的系统中，只允许进程主动放弃处理机

• 当前运行的进程被动放弃处理机

  • 分给进程的时间片用完
  • 有更紧急的事需要处理（如：IO中断）
  • 有更高优先级的进程进入就绪队列
    • 有的系统中，当有更紧急的任务需要处理的时候，也会强行剥夺处理机（被动放弃）

！什么时候不能进程调度

• 处理中断的过程中：处理中断过程复杂，与硬件密切相关，很难在冲段处理的时候进行进程切换
• 进程在操作系统内核程序临界区中。但是进程在普通临界区中是可以进行调度和切换的。
• 在原子操作过程中（原语）。原子操作不可中断（如修改PCB中进程状态标志，并放置在相应队列）

！eg：进程在操作系统内核临界区中不能进行调度切换（√）

！eg：进程处于临界区时不能进行处理机调度（×）

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

**！临界 区：**访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如说进程的就绪队列（由各个就绪进程的PCB组成）

• 举个栗子：

比如有一个内核进程，要访问就绪队列

graph LR
A(进程) -->B(就绪队列)

那就需要先锁住🔒就绪队列 。如果还没退出临界区（还没解锁）就进行进程调度，但经常调度相关程序也需要访问就绪队列，此时就绪队列又被锁住了，因此有无法顺利进行进程调度。

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

• 再举个栗子：

有一个进程要控制打印机，在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但是打印机是慢速的设备，如果一直不允许进程调度，会导致CPU一直空闲。

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

2.1 进程调度的方式

非剥夺方式（非抢占方式）

只允许进程主动放弃处理机，如果运行过程中有更紧迫的任务到达，当前进程还会继续使用处理机，直到该进程终止或主动进入阻塞态。

• 实现简单，系统开销小，但无法及时处理紧急任务。适用早期的批处理系统。

剥夺方式（抢占方式）

当一个进程正在处理机上执行时，如果有一个更重要的任务到达，则立即暂停正在执行的进程，将处理机分配给那个紧迫的进程。

• 可以优先处理更紧急的进程，也可以让各个进程按时间片轮流执行的功能（通过使用时钟中断）。适用于分时操作系统，实时操作系统。

细分进程调度

• 狭义的进程调度：从就绪队列中选中一个要运行的进程

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

  • 对原来运行的进程的数据进行保存
  • 对新进程的数据恢复（通常这些信息保存在PCB）
  • ！进程切换是有代价的。因此如果过于频繁的进行进程调度、切换，必然会降低整个系统的运行效率。并不是调度越频繁、并发度越高

三、调度算法的评价指标

1 CPU利用率：

• CPU处于忙碌的时间占总时间的比例。

$$
利用率 = \frac{有效工作的时间}{总时间 – 空闲+工作的时间}
$$

2 系统吞吐量：

• 单位时间内完成的作业数量

$$
系统吞吐量 = \frac{总完成的作业数量}{总共花费的时间}
$$

3 周转时间：

• 作业提交给系统开始，到作业完成为止的时间间隔

包括四个部分：

• 作业在外存后备队列等待调度的时间（高级调度）
• 进程在就绪队列上等待调度的时间（低级调度）
• 进程上CPU执行的时间
• 进程等待I/O操作完成的时间
  • 其中后三项在作业整个处理的过程中，可能发生多次

$$
作业周转时间 = 作业完成时间 - 作业提交时间 \\
平均周转时间 = \frac{\sum_{i=1}^n作业n的周转时间}{作业数} \\
带权周转时间 = \frac{作业周转时间}{作业实际运行时间} \\ = \frac{作业完成时间 - 作业提交时间}{作业实际运行时间}\\
平均带权周转时间 = \sum_{i=1}^n 作业n的带权周转时间
$$

其中，带权周转时间可以理解为：周转时间比运行时间大多少倍。如果带权周转时间太大，说明原本只需要少量时间让CPU为其服务，却让他等待了很长的时间。

4 等待时间：

• 指进程/作业处于等待处理机窗台时间之和。等待时间越长，用户满意度越低。

因为处理机调度算法不影响作业执行或者I/O时间，只影响作业在就绪队列中等待所花的时间。

因此，衡量一个调度算法的优劣，只需要简单的看等待时间。

• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和。等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
• 对于作业来说，不仅要考虑建立进程后等待的时间，还要加上作业在外存后备队列中等待的时间。
• 一个作业总共需要被CPU服务多久，被I/O设备服务多久，一般情况下，是确定不变的。调度算法值影响作业、进程的等待时间。我们也可以使用平均等待时间来评价整体性能。

5 响应时间

• 指用户提交请求到首次产生响应所使用的时间

四、调度算法

1、先来先服务——FCFS

1 算法思想

主要从公平的角度去考虑（类比食堂排队打饭的例子）

2 算法规则

按照作业/进程到达的先后顺序进行服务

3 用于作业/进程调度

作业调度：考虑的是哪个作业先到达后备队列

进程调度：考虑的是哪个进程先到达就绪队列

4 是否可抢占

使用非抢占式算法

5 优缺点

• 优点：公平，实现简单
• 缺点：排在长作业/进程后面的短作业需要等待很长的时间，带权周转时间很大，对短作业用户来说，体验不好。
• 总结：FCFS对长作业有利，对短作业不利。

6 是否会导致饥饿

不会。排在前面的作业总会处理完。

• 饥饿的概念：某个作业或者进程长时间得不到服务

2、短作业优先——SJF

1 算法思想

追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间

2 算法规则

最短的作业/进程优先得到服务（指要求服务的时间最短）

3 用于作业/进程调度

两种都可以用。对进程来说，叫**短进程优先（SPF，shortest process first）**算法

4 是否可抢占

SJF和SPF是非抢占式的算法。但也有抢占式的版本，叫最短剩余时间优先算法（SRTN Shortest Remaining Time Next）

• SRTN：当有进程加入就绪队列改变时就需要调度。如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机。当前运行进程重新回到就绪队列。

  ! 另外，当一个进程完成时^[1]也需要用这种算法进行调度。

  • [1] 进程主动放弃处理机的时候

• 细节：

  • 平时讨论短作业优先默认是SJF / SPF，是非抢占式的

  • 其实SRTN比SJF的平均的等待时间，平均周转时间要更少。

    应该说：在所有进程同时可运行时，或者在所有进程都几乎同时到达的时候，采用SJF调度算法的平均等待时间，平均周转时间最少。

  • 一般来说，SJF的平均等待时间和平均周转时间，比除了SRTN以外的算法（如FCFS）要更少。

  • 不过说SJF是平均等待时间，平均周转时间最少，仍然是不够严谨的

5 优缺点

• 优点：“最短的” 平均等待时间、平均周转时间
• 缺点：
  • 不公平。对短作业有利，对长作业不利。可能产生饥饿现象。
  • 作业/进程的运行时间，是由用户提供的，并不一定完全准确，不一定真正可以实现短作业优先。
  • 该算法完全没有考虑作业的紧迫程度，不能保证紧迫性作业会被及时处理。

6 是否会导致饥饿

会。如果源源不断有大量短作业/进程到来，可能会使长作业很长时间都得不到服务。产生饥饿现象。

如果一直得不到服务，则称之为 “饿死”。

3、高响应比优先——HRRN

1 算法思想

综合考虑 作业/进程 的等待时间和要求服务的时间。

2 算法规则

在每次调度时，先计算各个 作业/进程 的响应比，选择响应比最高的 作业/进程 为其服务。
$$
响应比 = \frac{等待时间+要求服务时间}{要求服务时间}
\geq 1
$$

3 用于作业/进程调度

都可以使用

4 是否可抢占

非抢占式算法，只有当前运行中的作业或进程主动放弃处理机时，才需要调度，才需要计算响应比。调度时计算所有就绪进程的响应比，选中响应比最高的进程上处理机。

5 优点

• 综合考虑了等待时间和运行时间（要求服务时间）
• 等待时间相同时，要求服务时间短的优先（SJF的优点）
• 要求服务时间相同时，等待时间长的优先（FCFS的优点）
• 对于长作业来说，随着等待时间越来越久，其响应比夜壶越来越大，从而避免了长作业饥饿的问题。

6 是否会导致饥饿

不会

• 以上三种算法总结

这几种算法主要关心对用户的公平性，平均周转时间，平均等待时间等评价系统性能的指标。但是不关心 “响应时间” ，也不区分任务的紧急程度。

因此，对用户来说，交互性很差，这三种算法一般适用于早期的批处理系统。

当然，FCFS也常结合其他算法使用。

4、时间片轮转（RR, Round-Robin）

1 算法思想

公平地、轮流地为各个进程服务，让每个进程在一定时间内都可以得到响应

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

2 算法规则

按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。

若进程未在一个时间片内执行完，则剥夺处理机，将进程程序放到就绪队列队尾重新排队。

！时间片划分需要注意：

• 如果时间片太大：

  使每个进程在一个时间片内就可以完成。则该算法会退化成FCFS（先到先服务）算法，并增大进程响应时间。

• 如果时间片太小：

  会导致进程切换过于频繁，系统要花大量的时间来处理进程切换。从而导致实际用于进程执行的时间比例减少。

• * 一般来说设计时间片时需要让切换进程的开销比例不超过 1%。

3 用于作业/进程调度

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

4 是否可抢占

抢占式算法。

若进程未能在时间片内运行完，将被强制剥夺处理机使用权。

由时钟装置发出的时钟中断来通知CPU时间片已到时。

5 优缺点

• 优点：

  公平，响应快，适用于分时操作系统

• 缺点：

  • 由于高频率的进程切换，因此有一定的开销

  • 不区分任务紧急程度

6 是否会导致饥饿

不会

5、优先级调度算法

1 算法思想

实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。

2 算法规则

给每一个 作业/进程 各自的优先级，调度的时候选择优先级最高的 作业/进程 。

3 用于作业/进程调度

可用于作业调度、进程调度、以及I/O调度。

4 是否可抢占

抢占式&非抢占式。

区别：

• 非抢占式只需在进程主动放弃处理机时进行调度即可
• 抢占式还需在就绪队列变化时，检查是否会发生进程之间的抢占

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

• 优先级

  • 静态优先级：光剑进程时候确定的，之后一直不变

    • 通常来说：

      • 系统进程优先级 高于 用户进程

      • 前台进程优先级 高于 后台进程

      • 操作系统更偏好I/O型进程（I/O繁忙型进程）

        I/O设备可以和CPU设备并行工作。

        让I/O设备尽早投入工作，资源利用率、系统吞吐量会得到提升。

      • 与I/O型进程先对的是计算型进程（CPU繁忙进程）

  • 动态优先级：创建的时候有个初始值，之后会根据情况动态地调整优先级

    • 如果进程在就绪队列中等待很长时间，就可以适当提升优先级
    • 如果进程占用处理机很长时间，则可以适当降低优先级
    • 如果发现一个进程频繁地进行I/O操作，则可以适当提升优先级

5 优缺点

• 优点：

  用优先级区分任务紧急程度。适用于实时操作系统。可以灵活地调整对各个 作业/进程 的偏好程度

• 缺点

  如果源源不断的有高优先级的进程进来，可能会导致饥饿

6 是否会导致饥饿

会

6、多级反馈队列

1 算法思想

对其他调度算法的整理集中

2 算法规则

1. 设置多个就绪队列

   各级队列优先级 从高到低，时间片 从小到大

2. 新进程到大时，先进入1级队列，按FCFS原则排队等待被分配。

   若用完时间片进程还未结束，则进入下一级队列的队尾。

   如果此时已经在最下级的队列，则重新放回该队队尾。

3. 只有第k级队列为空时，才会为k+1级的队列分配时间片

3 用于作业/进程调度

用于进程调度

4 是否可抢占

抢占式算法。

在k级队列的进程运行过程中，若更上级的队列中进了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

5 优缺点

• 优点：

  • 对各类型进程相对公平（FCFS的优点）

  • 每个新到达的进程都苦很快得到响应（RR的优点）

  • 短进程只用较少的时间就可以完成（SPF的优点）

  • 不比实现估计进程的运行时间（避免用户提供的运行时间不准确）

  • 可以灵活地调整对各类进程的偏好程度，比如CPU密集型进程，I/O密集型进程

    （可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高的优先级）

• 缺点：

  可能会导致饥饿

6 是否会导致饥饿

会

如果源源不断有短进程进入队列，可能会导致饥饿

• 后三种算法适用于交互式的系统（比如Unix就是使用多级反馈队列调度算法）