阅读《现代操作系统原理与实现》一书的笔记。xv6中的调度-part_one和调度-part_two更多的讲的是进程/线程切换以及生命周期，这里的调度则偏向于现实世界中操作系统如何选择进程/线程进行切换的机制，或者说如何对进程/线程使用系统资源的分配使用机制。
介绍
调度中的一些概念：
- 优先级（priority）
- 时间片（time slice）：每个请求一次可以占用多长时间的资源
- 截止时间（deadline）：任务最晚应该被完成的时刻
CPU、内存、磁盘I/O等资源都需要系统调度进行管理：
- 任务调度：也就是CPU调度，负责调度可执行任务对CPU的使用
- I/O调度：负责应该以何种顺序向存储设备发起I/O请求进行调度
- 内存管理：当需要使用的虚拟内存容量超过物理内存容量时，换页机制就是一种调度
内核中调度器无法感知用户态程序的具体语义，因而无法做出最优的调度决策。同时，应用程序对性能的需求不断提高，这促使越来越多用户态的程序也开始实现自己的调度器，例如Golang和K8s。
调度器会通过维护运行队列的方式来管理任务，Linux使用调度器会使用红黑树实现运行队列。
常用的调度指标：
- 性能相关指标：
- 吞吐量：批处理任务
- 周转时间：批处理任务
- 响应时间：交互式任务
- 非性能指标：
- 公平性
- 资源利用率
- 实时性：实时任务
- 能耗：移动设备上的操作系统调度
批处理任务：执行时无需与用户交互，其目标就是尽可能快的完成，主要调度指标为任务处理的吞吐量（单位时间内处理的任务数量）和周转时间（任务从发起直至执行结束所需的时间）
虽然上面有众多的调度指标，但是在实际针对不同的应用场景时需要进行权衡。
调度机制
进程调度根据职责的不同，具体可分为以下三类：
- 长期调度：决定当前真正可被调度的进程的数量，避免短期调度的开销过大
- 短期调度：实际做出调度决策的调度，主要负责进程在预备状态、运行状态、阻塞状态间的转换
- 中期调度：换页机制的一部分，避免内存使用过多；如果系统内存使用量过大，触发换页机制，中期调度将预备状态或阻塞状态的进程挂起后，会对应地将进程设置为挂起预备状态或挂起阻塞状态
根据进程使用的资源类型，进程可分为计算密集型（CPU-bound）和I/O密集型。前者主要使用CPU进行长时间计算，性能受处理器计算性能的限制；后者等待I/O请求完成会占用该类进程的大部分时间，同时它们会不间断地在短时间内占用CPU以处理I/O请求
任务调度总览
长期调度触发间隔较长，粗粒度地决定是否将一个新进程纳入调度管理，负责增加系统中可被调度的进程数量。
中期调度触发相对频繁，监控内存资源的使用，负责限制系统中可被调度的进程的数量。
短期调度触发最为频繁，负责细粒度地控制进程的执行。
调度策略
任务的到达时间用于表示该任务何时被发起并处于预备状态；而任务的运行时间表示该任务从开始执行到结束总共花费的时间；任务的周转时间则表示任务完成时间与任务到达时间的时间间隔；任务的响应时间指用户发起请求到任务响应用户所需的时间。
经典调度
下面的主要是针对批处理任务的策略，主要关注的调度指标是周转时间。
先到先得（FCFS）/先进先出（FIFO）
- 优点可能就只有简单直观了，很难背直接应用于复杂系统中
- 在长短任务混合场景下对短任务不友好（前面全是长任务，短任务在后面）
- 对I/O密集型任务不太友好，I/O资源的利用率低，可能会导致I/O密集型任务长时间内无法执行
最短任务优先（SJF）
- 必须预知任务的运行时间
- 严重依赖于任务到达时间点（例如短任务在后面到达，调度器已经执行前面到达的长任务了，那样和FIFO就差不多了）
最短完成时间优先（STCF）
前面两个调度算法中，调度器必须等一个任务执行完或者主动退出执行才能开始下一个调度，称为非抢占式调度，STCF可以被看作是SJF的抢占版本。
- 同SJF一样必须预知任务的运行时间
- 长任务饥饿，当有大量的短任务和少量的长任务时，这个系统的长任务很可能无法占用CPU资源，一直处于饥饿状态
针对交互型任务的调度策略，主要关注响应时间。
时间片轮转（RR）
为了定时响应用户，需要为任务设置时间片，限定任务每次执行的时间，当当前任务执行完时间片后，就切换到运行队列中的下一个任务。对于RR策略，一个关键点是时间片大小应该如何选取，需要考虑调度器的调度开销和任务切换上下文的开销，需要开发者对整个应用场景有明确的认知。
- 在任务运行时间相似的场景下平均周转时间高
优先级调度
为了保持良好的用户体验，调度器应尽量避免交互式任务被批处理任务阻塞。为此，调度器引入了优先级的概念。
一个直接的设置优先级的方式是根据任务在系统中的重要程度分配优先级：
- 拥有明确截止时间的实时任务，为其分配最高优先级，尽量保证实时任务在截止时间以前完成
- 交互式任务分配较高的优先级，响应时间影响用户体验，避免用户体验较差
- 批处理任务优先级最低
多级队列（MLQ）
每个任务都会分配预先设置的优先级，并存储在对应的优先级队列中，每个优先级对应一个队列。对于不同优先级（队列）的任务，调度器优先调度优先级高的任务。一个任务必须等到所有优先级比它高的任务调度完才可以被调度。对于相同优先级（队列）的任务，内部的调度方式没有统一标准，可以针对性地为不同队列采用不同的调度策略。
- MLQ适合静态的应用场景
- 设置MLQ中任务的优先级时，将I/O密集型任务的优先级提高，这样可以避免I/O资源利用率低下，并且I/O密集型任务消耗CPU资源少
- 可能造成低优先级任务饥饿
- 可能会出现优先级反转问题，解决方案是优先级继承
多级反馈队列（MLFQ）
MFQ可以在无法预知任务信息且任务类型动态变化（任务模式会在计算密集型与I/O密集型间转换）的场景下，既能达到类似STCF策略的周转时间，又能像RR策略一样尽可能的降低任务的响应时间（相同优先级的任务采用RR策略）。MLFQ策略在MLQ策略的基础上，增加了动态设置任务优先级的策略。
- 短任务拥有更高的优先级，MLFQ会统计每个任务已经执行了多长时间，并根据此判断该任务是短任务还是长任务。任务进入系统时，MLFQ会假设该任务为短任务，并设置最高优先级。然后MLFQ会为每个任务队列设置任务的最大运行时间（总时间，非时间片），若运行时间超过这个时间，该任务的优先级减一
- 低优先级的任务采用更长的时间片，减少调度切换带来的开销
- 定时的将所有任务的优先级提升至最高，避免低优先级任务饥饿
公平共享调度
公平共享调度会量化任务对系统资源的占用比例，实现对资源的公平调度，通过份额来量化对CPU时间的使用。份额支持层级化的分配方式，为了方便管理，可以将任务分组，以组为单位分配份额，任务会在组内进一步分摊该组所拥有的份额。
彩票调度
在彩票调度中，彩票数代表了进程占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。假设有两个进程A和B，A拥有75张彩票，B拥有25张。因此我们希望A占用75%的CPU时间，而B占用25%。通过不断且定时地抽取彩票，彩票调度从概率上获得这种份额比例。抽取彩票的过程很简单：调度程序知道总共的彩票数（在我们的例子中，有100张）。调度程序抽取中奖彩票，这是从0和99之间的一个数，拥有这个数对应的彩票的进程中奖。假设进程A拥有0到74共75张彩票，进程B拥有75到99的25张，中奖的彩票就决定了运行A或B。调度程序然后加载中奖进程的状态，并运行它。彩票调度利用了随机性，这导致了从概率上满足期望的比例。随着这两个工作运行得时间越长，它们得到的CPU时间比例就会越接近期望。
一些基于彩票调度的优化方法：
- 彩票转让，类似于优先级继承
- 彩票货币
- 彩票通胀
彩票调度是通过随机数实现的一个简单并且近似于公平共享的调度器，如果调度次数过少，不一定能保证公平。
步幅调度
引入了一个“虚拟时间”的概念。任务的运行时间片（实际时间）相同，但是每次调度后增加相应的虚拟时间。调度器选择调度所有任务中虚拟时间最少的任务。虚拟时间比也就反映了CPU资源分配的比例。
比如让两个任务使用的CPU时间之比为5：6，首先调度每个任务的时间片大小是相同的，任务A每次被调度虚拟时间增加6，任务B每次被调度时间增加5，我们让虚拟时间“短”的任务追赶时间“长”的，即虚拟时间短的任务优先。
对于真实情况，一个进程进入调度队列时，虚拟时间应该设置成当前队列任务中虚拟时间的最小值，而不是零。
实时调度
实时操作系统是指需要实时处理任务请求的操作系统，例如车控系统、机器人控制系统、音响系统等。在实时操作系统上运行的任务主要为实时任务，实时任务有非常高的时效性，必须对请求和事件立刻做出反应，往往会有一个明确的截止时间。
根据任务超过截止时间所造成的后果，实时任务的分类：
- 硬实时任务：必须在截止时间前完成，否则系统无法承担任务处理超过截止时间的后果
- 软实时任务：可以偶尔超过截止时间完成，其结果是可接受的
实时任务还可根据触发时间分为三类：
- 周期任务：到达系统时间遵循一定周期的任务
- 偶发任务：不会周期性到达系统的任务，但系统不会在同一时刻处理两个相同的偶发任务
- 非周期任务：到达系统时间随机的任务，相比于偶发任务，系统可以同一时刻处理多个相同的非周期任务
实时操作系统中，**优先级调度（MLQ）是广泛采用的调度策略，通过为不同的实时任务预先设置优先级，从而保证高优先级任务（例如硬实时任务）优先执行 **。
速率单调（RM）：速率单调是一个用于调度周期任务的静态优先级实时调度策略。
最早截止时间优先（EDF）：在单核抢占式场景下，对于一组互相无关的实时任务，EDF被证明是理论最有的动态优先级实时调度，被应用在许多实时系统中，Linux中也包含了基于截止时间的实时调度器。
其他调度
借用虚拟时间
多核调度策略
在单核调度策略中，虽然多个任务并发地在一个共享的CPU核心上执行，但是本质上它们仍然是在串行的执行。在进行多核调度时，调度器主要需要考虑下面三个问题：
- 当前应该调度哪个/哪些任务
- 每个调度的任务应该在哪个CPU核心上执行
- 每个调度的任务应该执行多久
负载分担
多核共享一个全局运行队列，当一个CPU核心需要调度任务时，根据给定的调度策略（可以是前面单核调度策略的任意一种）从全局运行队列决定下一个由它执行的任务。
- 设计简单
- 不会出现CPU浪费的情况
- 多核共享一个全局运行队列的同步开销
- 任务在多个CPU核心来回切换的开销
协同调度
协同调度尽可能让一组任务并行执行，避免调度器同时调度有依赖关系的两组任务，同时避免关联任务执行效率降低的问题。适用于关联任务或任务间有依赖关系的场景，适用于并行计算场景，即将任务切分为多个子任务并行执行的场景。在并行计算场景中，整体同步并行计算模型与协同调度非常契合，它将程序的执行分为以下部分：
- 并发计算：每个CPU核心独立计算自己的子任务
- 通信：CPU核心之间通过通信交换数据
- 同步：一个CPU核心在执行到程序设置的某个屏障点时，需要等待其他CPU也到达这个屏障点，才能执行后续代码逻辑
群组调度
将关联任务设置为一组，并以组为单位调度任务在多个CPU核心上执行，使它们的开始时间和结束时间接近相同。
两级调度
为了减少开销，每个任务应尽可能只在一个CPU核心上进行调度。两级调度为每个CPU核心都引入了一个本地调度器，并用它管理对应核心执行的任务。
由于两级调度在任务开始时就指定了它在哪个CPU核心上运行，且没有任务在CPU核心切换的机制，这可能导致多核间的负载不均衡，为了解决这一问题，两级调度引入了负载均衡策略，通过追踪每个CPU核心当前的负载情况，将当前处于高负载的CPU核心管理的任务迁移到低负载的CPU核心上，尽可能保证每个核心的负载大致相同。
如何保证低开销的同时对负载进行精确追踪是调度器实现设计的一大挑战，Linux目前主要使用调度实体粒度负载追踪（PELT）机制。PELT通过记录每个任务的历史执行情况来表示任务的当前负载。
负载均衡
Linux的负载均衡策略通过层级化的方法，Linux在负载均衡中主要使用两个数据结构。调度域（ scheduling domain)是拥有相同特性的CPU核心的集合，这些核心间可以进行负载均衡。一个调度域保存一个或多个调度组( scheduling group)，调度组是一个调度域内进行负载均衡的整体单位。下图展示了Linux 在NUMA架构且开启了超线程的情况下如何管理调度域的例子。在系统中，Core 0 和Core 1实际上是由一个物理核分化而来的两个逻辑核，它们组成了一个逻辑CPU域，该域中有两个调度组，分别对应于Core 0和Core 1。两个物理核组成了一个NUMA节点，对应于一个物理CPU域，该域中同样有两个调度组，分别对应于次一级的逻辑CPU域管理的一个物理核。同样地，两个物理CPU域组成了一个NUMA域，其两个调度组分别对应于次一级的物理CPU域管理的一个NUMA节点。在本例中，NUMA域就是系统中最顶层的调度域了，因此其调度组包含了系统中所有的CPU核心。由于计算机架构在运行时不会改变，因此可以认为调度域与调度组是只读的，每个CPU核心都为上述数据结构维护了一份只读的本地拷贝。
Linux通过自下而上的方式层级式地进行负载均衡，并且为了设计简单，只允许触发负载均衡的CPU核心拉取其他CPU核心的任务到本地。如果当前CPU核心触发负载均衡逻辑，首先在最底层调度域(逻辑CPU域)内的调度组（逻辑核)间进行均衡，然后依次进入更高一级的调度域(物理CPU域/NUMA域)，并对其管理的调度组（物理核/NUMA节点）进行负载均衡。由于在越高层级的调度域间进行负载均衡的开销越大，所以Linux为不同层级的调度域设置了不同的负载均衡触发频率与阈值(只有当两个调度组的负载相差超过一定阈值才会触发负载均衡)。Linux负载均衡通过将CPU核心进行层级化的划分，并为不同层级设置不一样的参数，尽量减少了负载均衡的开销。
能耗感知调度
针对移动、嵌入式设备。
本小节将介绍Linux的能耗感知调度（Energy Aware Scheduling，EAS)。EAS在Linux当前使用的完全公平调度器(Completely Fair Scheduler，CFS)的基础上进行了扩展。当一个任务从阻塞或睡眠状态被唤醒时，需要被放入某一CPU核心的运行队列中。在混合处理器架构中，任务被放置在不同CPU核心上所带来的能耗开销是不同的。为了在保证性能的同时达到最低的系统整体能耗，调度器通过EAS决定任务在哪个CPU核心上执行。为了解每个CPU核心的处理能力和能耗信息，EAS需要使用当前处理器架构的能耗模型（ energy model)。具体地，EAS通过能耗模型了解每个CPU核心的容量(处理能力)和功率。
调度进阶机制
根据任务的特性，可以区分为不同的种类，包括批处理、交互式、实时任务等。由于不同任务对调度的要求不同，单一的调度策略很难满足所有任务的需求。因此，Linux支持多种调度策略和调度器，允许程序根据不同场景进行选择。如表6-7所示，Linux主要提供宗全公平调度器(Completely Fair Scheduler，CFS)、实时调度器(Real-Time scheduler，RT）和截止时间调度器（ DeadLine scheduler，DL)。Linux也支持对不同的任务设置不同的调度策略。
