操作系统 | 进程管理之调度【思维导图版】

下面是程序锅在寒假期间根据《现代操作系统原理和实现》做的一个思维导图，完整、详细、清晰的文字版本后头会出，因为自己也想出整一套出来。

以下内容是由 XMind 根据上述思维导图的内容自动转换而来。

调度

调度目的

在有限的资源下，通过对多个程序执行过程的管理，尽可能满足系统和应用的指标，提高任务执行的性能和资源利用率，而非拖慢系统的运行。

调度的三个问题

选择调度哪个任务
选择执行该任务的 core
该任务允许运行的时间

调度器的设计

需要达到用户指定的哪些指标，因为不同种类的系统考虑的指标应该是不一样的
选择一个合理的调度策略来满足要求的指标

调度指标

吞吐量
周转时间
响应时间
公平性
资源利用率
实时性
能耗

调度机制

长期调度
中期调度
短期调度

单核调度策略

先到先得（First Come First Served,FCFS）
- 特点
  - 批处理，周转时间，非抢占
- 弊端
  - 长短任务混合的场景下对短任务不友好
  - 对 IO 密集型任务不友好
最短任务优先（Shortest Job First,SJF）
- 特点
  - 批处理，周转时间，非抢占
- 弊端
  - 必须预知任务的运行时间
  - 严重依赖于任务到达时间点
最短完成时间任务优先（Shortest Time-to-Completion First,STCF）
- 特点
  - 批处理，周转时间，抢占
- 弊端
  - 长任务饥饿
时间片轮转（Round Robin,RR）
- 特点
  - 交互式，响应时间，抢占
- 关键
  - 时间片大小如何选取
- 弊端
  - 在任务运行时间相似的场景下平均周转时间高
优先级调度（批处理+交互式，抢占）
- 多级队列（Multi-Level Queue,MLQ）-静态
  - 策略
    - 维护多个优先级队列，任务根据优先级处于不同队列
    - 高优先级任务先于低优先级任务执行
    - 相同优先级队列中的任务，内部的调度方式没有统一标准，可以采用 FCFS，也可以采用 RR。
    - 设置优先级时，将 IO 密集型任务的优先级提高
  - 弊端
    - 低优先级饥饿
    - 优先级反转
      - 优先级继承
- 多级反馈队列（Multi-Level Feedback Queue, MLFQ）-动态
  - 策略
    - 维护多个优先级队列，任务根据优先级处于不同队列
    - 高优先级任务先于低优先级任务执行
    - 相同优先级队列中的任务采用 RR 策略
    - 优先级的动态设置
      - 先假设都是短任务，设置最高优先级->统计每个任务已经执行了多长时间，并且每个任务队列设置任务的最大运行时间->任务运行的总时间超过队列允许的最大时间，优先级降低
      - 让短任务拥有更高的优先级
      - 低优先级的任务采用更长的时间片
      - 定时将所有任务的优先级提升至最高
  - 关键
    - 优先级队列的数量参数调整
    - 每个优先级队列采用的时间片参数
    - 每个优先级队列的最大运行时间
    - 调度器定时提升优先级的时间间隔
  - 弊端
    - 在上升/下降优先级的实现中，假如采启发式确定哪些任务需要被提升/降低时，会存在实现复杂的问题
公平共享调度（资源，公平性，抢占）
- 彩票调度（lottery scheduling）
  - 策略
    - 每个任务分配彩票数
    - 调度时，随机产生一个随机数，如果随机数落在相应任务的范围内，则调度该任务
  - 优化
    - 彩票转让（类似优先级继承）
    - 彩票货币（小明、小红各50张，小明自己可以设置总有有400个货币，A 100 个货币，B 300 个货币）
    - 彩票膨胀（允许任务自己确定自己的份额）
  - 弊端
    - 随机数带来的问题（调度次数少的时候，随机性可能会与预期不同）
- 步幅调度（stribe scheduling）
  - 策略
    - 引入虚拟时间，任务 A B 的份额之比为 5:6，那么运行相同时间之后，A B 增加的虚拟时间分别是 6:5，这样在运行相同的虚拟时间的情况下，实际执行时间为 5:6
    - 选择调度所有任务中虚拟时间最少的任务
    - 新加入的任务的虚拟时间设置为当前所有任务的最小值
实时调度（实时，实时性，抢占）
- 任务分类
  - 根据超过截止时间所造成的后果
    - 硬实时任务
    - 软实时任务
  - 根据被触发的时间
    - 周期任务
    - 偶发任务
    - 非周期任务
- 常见的实时算法
  - 速率单调（Rate Monotonic，RM）
    - RM 在所有基于静态优先级的实时调度策略中是最优的。基于 RM 策略无法在截止时间前完成的一组任务，也无法被其他基于静态优先级的实时调度策略在截止时间前完成。
    - 策略
      - 在预知任务周期 T 的情况下，根据周期的倒数（1/T）静态地为任务分配相应的优先级，T 越小，优先级越高。
      - RM 支持抢占，高优先级可以抢占低优先级
      - RM 调度 N 个任务时，最坏情况下的 CPU 利用率是 N*(2^(1/N)-1)，当 N 个任务的 CPU 利用率（C 是运行时间，T 是周期，所有任务的 C/T 相加就是总的 CPU 利用率）小于最坏情况下的利用率时，那么一定 RM 策略一定可以满足这些任务的截止时间。如果超过，RM 就不一定可以满足了。
    - 优点
      - 优先级固定，实现简单，所有带来了比较稳定的任务时延。
      - RM 是最优的静态优先级实时调度策略
    - 缺点
      - RM 策略中可能会出现所有任务的 CPU 利用率小于等于 1，但不能在截止时间前完成的情况
  - 最早截止时间优先（Earliest Deadline First, EDF）
    - 在单核抢占式场景下，对于一组互相无关的实时任务，EDF 是理论最优的动态优先级实时调度策略。

如果一组任务的截止时长等于周期，且他们的 CPU 利用率小于等于1，EDF 一定能够在这些任务的截止时间前完成这些任务。（所有任务的 CPU 利用率小于等于 1 的充分必要条件时 EDF 可以在任务的截止时间前完成任务）
- 策略

			- 只需要知道任务的截止时间这一信息，并根据任务的截止时间来确定优先级。

		- 缺点

			- 在所有任务的 CPU 利用率大于1时，会因为一个任务错过截止时间，而导致大量后续任务级联地错过截止时间，即多米诺效应。

借用虚拟时间（Borrowed Virtual Time，BVT）
- 基本思想：
  允许任务向自己的未来借用一定虚拟时间。也就是允许在短时间内将自己的虚拟机时间降低，从而达到被优先调度的目的。

当然为了防止任务无端地借用未来的虚拟时间，BVT 策略需要限制一个任务最大可以借用的虚拟时间量，并规定一定物理时间后必须将借用的虚拟时间归还。
- 优点

	- 通过统一的虚拟时间抽象调度批处理、交互式和实时任务，既保证了公平共享调度又保证了实时任务的实时性。

多核调度策略

负载分担
- 基本思想：
  多核共享一个全局运行队列，每个核心根据自己的调度策略（任意一种单核调度策略），从全局运行队列中选择一个任务来执行。
- 优点
  - 设计简单
  - CPU 资源不会浪费
- 缺点
  - 多核共享一个全局运行队列的同步开销
  - 任务可能会在多个 CPU 核心之间来回切换
协同调度
- 基本思想：
  尽可能让一组任务并行执行，避免调度器同时调度有依赖关系的两组任务，同时避免关联任务执行效率较低的问题。
- 适用并行计算场景
  - BSP(Bulk Synchronous Parallelism,BSP) 计算模型（整体同步并行）将程序分成这三个部分
    - 并行计算：每个 CPU 核心独立计算自己的子任务
    - 通信：CPU 核心之间通过通信交换数据
    - 同步：一个 CPU 核心在执行到程序设置的某个屏障点时，需要等待其他 CPU 核心也到达这个屏障点，才能执行后续代码
- 实现策略
  - 群组调度
    - 基本思想：
      将关联任务设置为一组，并以组为单位调度任务在多核 CPU 核心上执行，使它们的开始时间和结束时间接近相同。
    - 优先
      - 可以提升特定应用场景的任务执行性能。
    - 缺点
      - 在应用场景不匹配的情况下，群组调度策略可能并不是最优的，因为它要求无关联的任务必须同时进入或退出 CPU 核心，无关联任务之间的相互等待可能会造成 CPU 资源的浪费。
两级调度
- 基本思想：
  每个 CPU 核心有一个自己的本地调度器，管理对应核心上的任务。还有一个全局调度器，在任务进入系统时，全局调度器根据系统当前的信息，诸如每个 CPU 核心的负载情况，决定该任务被放到哪个 CPU 核心上执行。
  当任务被分配到给定的 CPU 核心上时，它将一直被该核心的本地调度器管理。每个本地调度器可以使用单核调度策略来调度任务。（其实说来说去就是多队列）
- 优点
  - 任务无须在 CPU 核心之间来回切换
  - 单核调度策略与支持多核调度进行了解耦（因为每个核只需要管理自己的任务，所以相当于不需要锁来进行同步等，也就是独立开来了），使得调度器的设计实现更加灵活
- 实例
  - Linux 调度的实现，每个 CPU 核心都有一个运行队列，每个 CPU 核心有一个本地调度器。
- 负载追踪与负载均衡
  - Motivation
    - 任务开始时就指定了它在哪个核心上运行，且没有任务在 CPU 核心切换机制，那么这样会导致 CPU 核心间的负载不均衡。
  - 基本思想
    - 通过追踪每个 CPU 核心当前的负载情况，将处于高负载的 CPU 核心管理的任务迁移到低负载的 CPU 核心上，尽量保证每个核心的负载大致相同。
  - 调度实体粒度负载追踪（Per-Entity Load Tracking，PELT）---Linux 目前使用
    - Linux 3.8 之后，使用以调度实体为粒度的负载计算方式，做到了更细粒度的负载追踪（3.8 以前是以每个 CPU 核心的运行队列为粒度来计算负载）。
      基本思想是：通过记录每个任务的历史执行状况来表示任务的当前负载。
    - 首先，调度器以 1024 微妙为一个周期，记录任务在该周期内处于可运行状态的时间，记为 x 微秒，那么这个周期内的 CPU 利用就是 x/1024，对应的负载 Li=scale_cpu_capacity*x/1024（scale_cpu_capacity 是 CPU 容量）。
    - 之后，PELT 需要计算一段时间内任务所有周期的累计负载 L = L0+L1y+L2y^2+...，其中 y 是衰减系数，这么计算是因为距离当前时间越远的历史负载信息并没有太大的参考意义。实际中，计算这段时间内新的累计负载可以只需要保持累计负载 L，那么新的累计负载 L‘ = L*y +Ln
  - 负载均衡---以 Linux 为例
    - 首先，Linux 使用调度域和调度组两个概念。调度域是指拥有相同特性的 CPU 核心的集合。一个调度域可以保存一个或多个调度组，调度组是一个调度域内进行负载均衡的整体单位。
    - 之后，Linux 通过从下至上的方式层级式地进行负载均衡，并且只允许触发负载均衡的 CPU 核心拉取其他 CPU 核心上的任务到本地。具体地，当前 CPU 核心触发了负载均衡逻辑，首先在最底层调度域（逻辑 CPU 域）内的调度组（逻辑核）之间进行均衡，然后依次进入更高一级的调度域（物理 CPU 调度域）进行管理，以此类推。

需要注意的是，越高层级的调度域间进行负载均衡的开销越大。所以 Linux 为不同层级的调度域设置了不同的负载均衡触发频率和触发阈值。

- 处理器亲和性

	- Motivation

		- 负载均衡使得任务可以在 CPU 核心之间进行迁移，然而有时候任务在一个 CPU 核上运行会有更好地性能，这就是亲和性。

	- 实现

		- 操作系统提供了处理器亲和性的机制，允许程序对任务可以使用的 CPU 核心进行配置。

能耗感知调度
- 混合处理器架构为调度器提供了优化系统能耗的机会，比如大小核。
- 实例
  - Linux 的能耗感知调度（Energy Aware Scheduling，EAS），EAS 是当前 Linux 使用的 CFS 的扩展。

[[实例]]

Linux 的调度策略设置
- 截止时间调度器
  - SCHED_DEADLINE，类似 EDF 的调度策略
- 实时调度器
  - SCHED_FIFO
  - SCHED_RR
- 完全公平调度器
  - SCHED_OTHER
  - SCHED_BATCH
  - SCHED_IDLE
Linux 调度器
- O(n) 调度器，Linux 2.4 之前
  - 基本策略
    - 一个基于 RR 策略并且是全局的运行队列（所有任务都被存储在一个全局的运行队列中）
    - 如何决定下一个要调度的任务？

Linux 会在调度下一个任务时，遍历全局队列并计算动态优先级，且保证实时任务的动态优先级高于非实时任务的动态优先级，非实时任务的动态优先级会考虑该任务剩余的时间片长度、历史执行情况等。

最后选择所有任务中动态优先级最高的任务进行调度（所以时间复杂度是 O(n)）。
- 调度器会将时间分为多个调度时间段。每个时间段内，每个任务都会被重新分配时间片。当经过一个时间段（每个任务都执行完一个时间片）后，调度器会遍历运行队列并更新所有任务的时间片，如果有任务的时间片没有执行完，其剩余时间片的一半会被加入到下一个时间片中。

	- 缺点

		- 调度开销过大
		- 多核扩展性差

- O(1) 调度器，Linux 2.6.0 开始

	- 基本策略

		- 采用两级调度的思想，每个核心维护一个本地运行队列，让任务只在同一个核心上被调度。每个本地运行队列实际上是由两个多级队列：激活队列和过期队列组成的，分别用于管理仍有时间片剩余的任务和时间片耗尽的任务。每个多级队列都有 140 个优先级（高优先级[0,100)对应实时任务，[100,140) 对应非实时任务），并且维护着一个位图（所以时间复杂度是 O(1)）。
		- 当一个任务的时间片被耗尽之后，它会被加入过期队列。调度时，调度器会根据位图找到激活队列中第一个不为空队列，并调度该队列的第一个任务（时间复杂度为 O(1)），如果激活队列中没有任务了，那么会将两个队列的角色互换，开始新一轮调度。
		- 交互式任务在时间片用完之后，仍人会被加入激活队列中，这是为了避免交互式任务在时间片用完后就要等待所有其他任务的时间片都用完才能再次执行的情况。
		- 为了防止交互式任务过于激进，使得过期队列中的任务无法执行。当过期队列中的任务等了很长时间后，调度器会把交互式任务添加到过期队列中。

	- 缺点

		- 判断一个任务是否是交互式任务的算法过于复杂
		- 非实时任务的时间片是静态的。任务数量增加时，调度时延也会上升

- 完全公平调度器，Linux 2.6.23

	- 基本思想

		- 每个任务根据自己所占的份额共享 CPU 时间，类似于公平共享调度策略中的步幅调度。

CFS 调度器只关心非实时任务对 CPU 时间的公平共享，并且通过调度周期、动态地设定时间片，来减少任务的调度时延不会过高。

	- 策略

		- CFS 中的 vruntime 代表该任务经过的虚拟时间，Linux 也静态地设置了 Niceness 与任务权重（weight）之间的对应关系，Niceness 越低任务的权重越高，可被分配的 CPU 时间越多。
		- CFS 调度器的动态时间片

			- 调度周期

				- 每经过一个调度周期，运行队列中的任务都会被调度一次。
				- 调度周期 sched_period 的默认值是 sched_latency 为 6ms，当任务数过多之后，调度周期为当前任务数与 sched_min_granularity 的乘积。

			- 动态时间片

				- 那么运行队列中，第i个任务的动态时间片为 time_slice_i = sched_period * (weight_i/weight_rq)，weight_rq 是运行队列中的任务权重之和。
				- 任务每次执行后对 vruntime 的更新也要进行缩放，vruntime=vruntime+weight_nice0/weight_i*real_time（其中weight_nice0是Niceness为0的任务的权重）。通过这样缩放之后，CFS 使得不同动态时间片的任务执行完自己的时间片后，它们虚拟时间的增幅是一样的。

		- CFS 调度器使用红黑树作为运行队列

			- CFS 使用 vruntime 作为红黑树的索引键，使用调度实体作为值。
			- 红黑树根据索引键的插入操作时间复杂度是 O(logN)，而队列是 O(N)。 
			- CFS 的红黑树维护了最小索引键的缓存，从而可以 O(1) 地查找最小索引键和调度实体。
			- CFS 的红黑树仅维护当前正在运行和可运行的任务，不记录其他任务的状态，减少了红黑树的开销。

		- CFS 阻塞任务唤醒

			- 一个任务由于阻塞或者睡眠而没有运行，那么此时 vruntime 是不会增加的。当再一次进入可运行状态后，调度器会将任务的虚拟时间 vruntime 设置为运行队列中最小虚拟时间和 vruntime 的较小值，从而确保阻塞后的任务可以第一时间被调度。

macOS/ios 调度器
- GCD 中的任务不再是内核中的线程了，而是可以在用户态进行切换的更加轻量级的单元，可以理解为纤程。GCD 会维护多个队列，用户程序将任务分发到相应队列中即可。那么 GCD 会调用线程池中的线程来处理相应的任务（所以mac 中的线程模型是多对多的）