进程调度策略

## :stopwatch: 调度机制

1. 一个操作系统会同时管理大量的进程，数量远远超过计算机的 CPU 核心数量，他们使用的内存也可能会超过可用的内存总量。
2. 为了 **协调多个进程对 CPU 和内存的使用**，操作系统使用了进程调度机制，主要负责进程在 [不同状态](https://notebook.ricear.com/project-26/doc-327) 的切换。
3. 进程调度根据 **职责** 的不同，可以分为 **长期**、**中期** 和 **短期** 调度，从而对 CPU、内存、I/O 资源的使用进行管理。

### :clock6: 长期调度

1. 即使用户已经向操作系统提交了执行某个程序的请求，系统也 **不会立即处理** :no_good: 该请求，这一决策是由操作系统中的 **长期调度** :clock12: 负责的。

> :information_desk_person: 假如每一个程序尝试运行时，操作系统都立即为其创建对应的进程，并将进程状态设置为预备状态，那么会导致大量进程在短时间内被创建出来，会造成调度决策（即后面会介绍的 **短期调度**）需要考虑的进程数量剧增、调度开销变大的问题 ❌ 。

2. 当长期调度为某个程序 **创建** 了进程并将其状态设置为 **预备状态** 后，会由 **短期调度** 进一步管理该进程（例如做出调度决策），因此，长期调度决定了当前 **真正可被调度的进程的数量**。

> :information_desk_person: 长期调度就像一个 **阀门**，用于 **限制** 系统中真正被短期调度管理的进程数量，避免短期调度的开销过大。

3. 长期调度可以根据当前系统中的 CPU、I/O 利用率情况，选取合适的 **计算密集型** 或 **I/O 密集型** 进程，交由短期调度管理，这样，可以有效地控制系统中的 **资源利用** 情况，避免出现激烈的 **资源竞争** 或某项资源的利用率过低的情况。

> :thinking: 什么是『计算密集型』和『I/O 密集型』进程？
   >
   > - 计算密集型进程主要利用 **CPU** 进行长时间的计算，因此其性能受 **处理器计算性能** 的限制。
   > - I/O 密集型进程 **等待 I/O 请求完成** 会占用该类进程的大部分时间，同时他们会不间断地在 **短时间内占用 CPU** 以处理 I/O 请求。

### :clock12: 短期调度

1. 实际做出 **调度决策** 的是 **短期调度**。
2. 短期调度主要负责进程在预备状态、运行状态、阻塞 **状态间的转换**：
   1. 在短期调度决定执行一个进程时，会将该进程从 **预备状态** 设置为 **运行状态**。
   2. 处于预备状态的进程需要被短期调度允许才能运行，而处于运行状态的进程可能会被 **短期调度** 打断，避免占用 CPU 时间过长，影响调度的公平性。
   3. 如果 **运行状态** 的进程发起 I/O 请求、等待用户输入或睡眠，则会主动进入 **阻塞状态**，当 I/O 事件完成后再重新进入 **预备状态**。

### :clock3: 中期调度

> :thinking: 为什么需要中期调度？
>
> - 长期调度与短期调度一般会从 **CPU**、**I/O** 资源的角度做出调度决策，然后，操作系统中的 **内存资源** 还没有被考虑。
> - 虽然长期调度已经限制了被短期调度管理的进程数量，但是他们的内存使用量在运行时仍然有可能超出系统中的内存总量，此时，操作系统需要将 **内存使用情况** 也纳入考量，避免内存使用过多，这是由 **中期调度** 来负责的。

1. 中期调度实际上是 [换页机制](https://notebook.ricear.com/project-26/doc-342) 的一部分：
   1. 如果当前系统中的进程已经 **占用了大量内存**，中期调度会根据某些策略 **挂起** 系统中被短期调度管理的进程（例如 **频繁触发缺页异常** 的进程、**长时间未响应** 的进程等），该进程会被设置为对应的 **挂起** 状态，标志着他 **不会再被调度执行**。
   2. 同时，换页机制会倾向于选择 **被挂起的进程** 所使用的的内存页替换入磁盘。
   3. 中期调度也会监控当前内存使用情况，并 **在适当的时机激活此前挂起的进程**。

## :train2: 调度策略

### :atom_symbol: 单核调度策略

> 下面将介绍一些常见的、经典的调度策略，这些调度策略都假设当前系统 **只有一个可用的 CPU 核心**，每个任务都有自己的到达时间和运行时间。另外，不考虑任务调度开销，所有调度都是即时完成的。

#### 经典调度

##### 先到先得

1. 先到先得（First Come First Served, FCFS）策略会在系统中维护一个 **运行队列**，这个队列中的元素是处于 **预备状态**、等待执行的任务。

2. 在决定需要执行的任务时，FCFS 策略会选取运行队列中的 **第一个任务**，将其 **移出运行队列并执行**，当一个任务 **执行完成** 后，他会被再次放入 **运行队列的队尾**。

> :information_desk_person: 运行队列能够起到为多个任务 **确定顺序** 的作用，保证任务的执行顺序与其进入运行队列的顺序一致。

3. FCFS 策略的 **优点**：

1. **简单直观**：
      1. 开发者只需要维护一个队列就可以实现 FCFS 策略，同时，FCFS 策略不需要预知任务信息，也没有需要开发者手动调试的参数。

4. FCFS 策略的 **缺点**：

1. 在 **长短任务混合** 的场景下 **对短任务不友好**：

> 假设从第 0 秒起，一共有三个计算密集型任务 $A$、$B$、$C$ 准备被处理，且他们不会发起 I/O 请求。
      >
      > ![image-20220724160714087](https://notebook.ricear.com/media/202207/2022-07-24_160719_9130110.09143457590494597.png)
      >
      > 虽然任务 $A$、$B$、$C$ 的到达时间点都为第 0 秒，但假定他们进入队列的顺序为 $A$、$B$、$C$。下图展示了上面的任务场景基于 FCFS 策略的执行流，可以看到他们执行的顺序同样是 $A$、$B$、$C$。
      >
      > ![image-20220724160922080](https://notebook.ricear.com/media/202207/2022-07-24_160927_5220990.15080912853305262.png)
      >
      > 下表展示了任务的完成时间点和周转时间（周转时间 = 完成时间点 - 到达时间点）：
      >
      > ![image-20220724161220452](https://notebook.ricear.com/media/202207/2022-07-24_161226_0863720.9762634020976079.png)
      >
      > 1. 对于任务 $A$，他的周转时间与运行时间之比为 1 : 1，一般用户会根据任务的运行时间预估大致的周转时间，因此 1 : 1 代表周转时间符合用户预期，是理想的调度情况。
      > 1. 对于任务 $B$ 和 $C$，他们的周转时间与运行时间之比高达 6 : 1、7 : 1，这时由于调度器首先调度任务 $A$，而任务 $A$ 的运行时间较长，任务 $B$ 和 $C$ 不得不等待较长的时间才能开始运行，由于任务 $B$ 和 $C$ 的运行时间相对于 $A$ 较短，他们的周转时间会显著收到任务 $A$ 的影响，可以想象，如果任务 $A$ 的运行时间变得更长，那么这一问题会更加严重。
      > 1. 因此，在短任务与长任务混合的应用场景下，FCFS 策略可能会导致短任务的周转时间与运行时间之比过大，对短任务不友好，从而使得用户体验很差。

2. **对 I/O 密集型任务不友好** ：

1. I/O 密集型任务通常会 **花费大部分时间等待 I/O**，仅有 **少量时间被用在 CPU 中以处理请求**。
      2. FCFS 策略 **对计算密集型任务更加友好**，但可能 **会导致 I/O 密集型任务长时间内无法执行**。

> 假设系统中有两个任务 $A$ 和 $B$：
      >
      > - 任务 $A$ 是一个 **计算密集型** 任务，他需要执行 40 秒。
      > - 任务 $B$ 是一个 **I/O 密集型** 任务，先于任务 $A$ 到达系统，他会将以下步骤循环两次：
      >   - 使用 5 秒的 CPU 时间。
      >   - 发起并等待一个耗时 15 秒的 I/O 请求。
      >
      > 下图展示了这个例子基于 FCFS 策略的执行流。
      >
      > ![image-20220724171258281](https://notebook.ricear.com/media/202207/2022-07-24_171303_9637820.9580488850581617.png)
      >
      > - 虽然 I/O 密集型任务 $B$ 可以先执行，但是在其第一次等待 I/O 请求并变为阻塞状态后，计算密集型任务 $A$ 会一直执行直到结束。
      > - 因此，任务 $B$ 即使在完成 I/O 请求之后也不能执行，只能延后发起下一轮的 I/O 请求，使得 I/O 资源的利用率降低。

##### 最短任务优先

> 针对 FCFS 策略所面临的 **短任务等待时间过长** 的问题，我们应该寻找另一种调度策略，他应让短任务立即执行，这也就是我们下面要讲到的 **最短任务优先**（Shortest Job First, SJF）策略。

1. SJF 策略在调度时会选择 **运行时间最短** 的任务执行。

> 下表给出了上面的场景在 SJF 策略下的任务执行信息和执行流。
      >
      > ![image-20220724172810906](https://notebook.ricear.com/media/202207/2022-07-24_172816_7411570.5168883417977074.png)
      >
      > ![image-20220724172837401](https://notebook.ricear.com/media/202207/2022-07-24_172842_8404550.6696039136136666.png)
      >
      > 从上面的图中可以看出，在 SJF 策略下，任务的平均周转时间相较于 FCFS 策略更短。

1. SJF 策略的 **缺点**：

1. **必须预知任务的运行时间**：

1. SJF 策略能够选取最短运行时间或最短完成时间的任务的前提是 **系统需要预知任务所需的运行时间**。
         2. 对于一些比较固定的应用场景，这个前提是合理的，但是在更多的场景下，系统很难预知将要处理的任务确切的运行时间，因为这取决于当前系统的状态和其他影响程序执行性能的因素，这一前提条件也限制了 SJF 的应用场景。

2. **其表现严重依赖于任务到达时间点**：

> 上面的例子中三个任务的到达时间点都是第 0 秒，现在，让我们对这个场景进行一定的修改，任务 $A$、$B$、$C$ 的到达时间点分别被设定为第 0 秒、第 1 秒和第 2 秒，运行时间不变，在这种场景下任务在 SJF 策略下的执行信息和执行流如下图所示：
         >
         > ![image-20220724174124786](https://notebook.ricear.com/media/202207/2022-07-24_174130_4457000.5381962265428694.png)
         >
         > - 虽然任务 $B$ 和 $C$ 仅仅晚到几秒，但是由于调度器在第 0 秒进行调度时并不知晓他们的存在，所以选择调度长任务 $A$。
         > - 当任务 $B$ 和 $C$ 到达时，调度器已经无法重新做出选择，现在的执行流与上面使用 FCFS 的执行流一样，任务 $B$ 和 $C$ 仍必须等待任务 $A$ 执行完。

##### 最短完成时间任务优先

> SJF 策略面临的问题是『迟到』的短任务时无法受益于 SJF 策略的，为了解决这个问题，一个直接的思路是，是否可以让调度器在任务 $B$ 和 $C$ 到达时对其进行调度，按照这个思路产生了 SJF 策略的 **抢占式** 版本，即 **最短完成时间任务优先**（Shortest Time-to-Completion First, STCF）。

1. 在 FCFS 策略和 SJF 策略中，调度器必须等待一个任务执行完或者主动退出执行才能开始下一个调度，因此被称为 **非抢占式调度**。

2. 而 STCF 策略在 **任务到达系统** 时也会进行调度，有可能会中断当前正在执行的任务，转而执行其他任务，因此被称为 **抢占式调度**。

> 下图是上面的例子在 STCF 策略下的执行流。
   >
   > ![image-20220724211340391](https://notebook.ricear.com/media/202207/2022-07-24_211346_3274790.9443944481394245.png)
   >
   > - 由于任务 $A$ 在第 0 秒首先到达系统，所以任务 $A$ 执行了 1 秒。
   > - 在第 1 秒时，任务 $B$ 到达系统，由于其所需的完成时间少于任务 $A$，所以任务 $B$ 可以立即抢占任务 $A$ 并执行。
   > - 而当任务 $C$ 在第 2 秒到达时，任务 $B$ 已经运行了 1 秒，任务 $B$ 所需的剩余运行时间小于任务 $C$ 的运行时间，所以任务 $C$ 不会抢占任务 $B$ 的执行，而是会等到任务 $B$ 结束再开始执行。

3. STCF 策略的 **缺点**：

1. **长任务饥饿**：
      1. STCF 极端倾向于完成时间较短的任务，因此当一个系统中有 **大量的短任务** 和 **少量的长任务** 时，这个系统的长任务很可能会 **无法占用 CPU 资源**，一直处于饥饿中，即 **永远无法被调度**。
      2. 在某些系统中，通常会有 **后台服务**（例如网络服务、数据库服务）随开机启动，并一直执行，他们的运行时间相比于其他任务长很多，SJF 策略和 STCF 策略几乎不会让他们获得执行机会，而这 **对于整个系统调度的公平性是不利的**。

##### 时间片轮转

> 之前讨论的策略主要是针对 **批处理任务** 的策略，他们主要关注的调度指标是 **周转时间**。
>
> 随着操作系统的发展，**交互式程序**（如终端）逐渐普及，与用户的交互为调度带来了新的调度指标，即 **响应时间**。响应时间指的是 **从用户发起请求到任务响应用户所需的时间**。
>
> 在生活中，相比于任务能否快速完成，用户可能更在意任务能否快速响应用户的请求：
>
> - 例如一个程序需要一次性花 30 秒完成某项工作，但是过程中没有任何提示；同样的工作量，另一个程序可能要花费 40 秒完成，但是会每隔 1 秒告知用户当前的进度。
> - 在使用前者时，用户的耐心会随着时间逐渐流逝，并最终倾向于认为这个程序不能响应。
> - 相对地，在使用后者时，用户会有更好的体验，而前者由于他的『冷淡』，不会受到用户的青睐。

1. 前文讨论的策略只有在任务到达和结束时才会进行调度，如果一段时间内没有新的任务到达或当前任务没有执行完，那么调度器就无法进行调度，因此 **非运行状态** 的任务也 **无法定时地响应用户**。

2. 为了 **定时响应用户**，需要为任务设置 **时间片**，**限定任务每次执行的时间**，当前任务**执行完时间片**后，就切换到 **运行队列中的下一个任务**，这一思想的体现就是 **时间片轮转**（Round Robin, RR）策略。

> 下图展示了三个任务 $A$、$B$、$C$ 在 RR 策略下的执行流。
   >
   > ![image-20220724215049156](https://notebook.ricear.com/media/202207/2022-07-24_215054_9075200.6514582216772327.png)
   >
   > - 该 RR 策略使用 1 秒的时间片，以 3 秒为一个循环执行这三个任务。
   > - 由于时间片一般会设得足够小，所以所有任务都可以在一定时间内执行并响应用户，从而将响应时间限定在一个可接受的范围内。
   > - 相比于 SJF 策略和 STCF 策略，RR 策略不仅无须预知任务的运行时间，而且也不会出现长任务饥饿的情况。

3. 对于 RR 策略，一个关键点是他的 **时间片大小** 该如何取：

1. 理想情况下，时间片选取得越小，任务的响应时间就越快。
   2. 但是，之前的讨论分析是基于抽象的模型进行的，没有考虑以下因素：
      1. 调度器的**调度开销**。
      2. 任务切换所导致的 **上下文切换开销**。
   3. 在实际场景中，：
      1. **过小的时间片**反而会 **引入大量开销**，**让任务的调度成为严重的性能瓶颈**。
      2. 如果**时间片过长**，比如 100 秒，RR 策略不仅无法满足用户对于响应时间的需求，还很可能 **产生与 FCFS 策略相同的负面效果**。
   4. 因此，如何将时间片降低到一个合理的值对于开发者是一大挑战，他要求开发者对整个应用场景有着明确的认知。

4. RR 策略的 **缺点**：

1. 在 **任务运行时间相似** 的场景下 **平均周转时间高**。

> 以上面的场景为例，假设 $A$、$B$、$C$ 三个任务的运行时间都是 3 秒，那么他们会分别在第 7 秒、第 8 秒、第 9 秒完成。
      >
      > 这个执行流代表了每个任务都在最后时刻完成，他们的平均周转时间非常高。
      >
      > RR 策略一定程度上保证了每个任务之间的 **公平性**（每个任务都能在一定时间内被调度到），同时也可获得 **良好的响应时间**，但是，在 **特定场景下**（如每个任务运行时间相似），任务的 **平均周转时间可能较差**。

#### 优先级调度

> 现在假设有以下场景：
>
> - 小明在一个单核计算机上通过多个后台程序处理他准备的大数据集，这些后台程序会在指定的文件目录中输出中间结果文件。小明希望通过命令行的 `ls` 指令看到数据处理的进度。
> - 我们假设系统使用 RR 策略进行调度，现在系统中有 $N$ 个批处理任务和一个命令行的交互式任务，基于 RR 策略的调度不会对管理的任务进行区分，因此单位时间内命令行只会占用 $\frac{1}{N + 1}$ 的 CPU 时间，大部分时间下，后台程序都会阻塞 `ls` 指令的执行。
> - 此时小明会感觉整个系统被卡死，就连 `ls` 都需要很长时间才能响应，如果小明脾气不好，他很有可能马上通过 `kill` 指令将他的后台程序终止。
> - 因此，为了保持良好的用户体验，调度器应尽量避免交互式任务被批处理任务阻塞。

1. 如果操作系统可以区分 **交互式任务** 和 **批处理任务**，那么他就可以设置一个让交互式任务优先执行的调度策略，为此，调度器引入了 **优先级** 的概念：
   1. 优先级是一个很直接、有效的概念，通过为每个任务指定一个优先级，调度器可以确定哪些任务应该优先执行。
   2. 通过设置交互式任务的优先级高于批处理任务，操作系统可以为用户提供更好的体验。
2. 为任务确定优先级需要考虑很多因素，一个直接的设置优先级的方式是，根据 **任务在系统中的重要程度** 分配优先级：
   1. 对于 **拥有明确的截止时间的实时任务**，我们应该为其分配 **最高优先级**，尽量保证实时任务可以在截止时间以前完成。
   2. **交互式任务** 的响应时间直接影响用户体验，为了避免用户体验较差，我们需要为其分配 **较高的优先级**。
   3. **批处理任务** 一般不像实时任务与交互式任务那样对时延、响应时间有较高要求，所以这类任务的优先级较低。
3. 下面我们将介绍一个直观的静态优先级调度策略，即 **多级队列**，基于该策略的任务会严格根据预设的优先级进行调度。基于对该调度策略的观察，后面会逐步给出一些关于设置优先级的启发经验。最后，我们会介绍一个经典的基于多级队列的动态优先级调度策略，即 **多级反馈队列**。

##### 多级队列

> 首先，我们可以试想一个真实的生活场景：
>
> - 在机场有一架航班准备起飞，我们将需要登机的人员分为三类：
>   - 第一类是飞行员、空乘、维护人员。
>   - 第二类是购买商务舱机票的 VIP 乘客。
>   - 第三类是普通乘客。
> - 在飞机允许登机以前，第一类的工作人员会在专用场所等待，VIP 乘客一般会在 VIP 候机室等待，其他乘客则会在候机大厅等待。
> - 在飞机到达后，工作人员需要立即登机进行飞机的维护、检查、临起飞工作，可以理解为他们的登机优先级最高。当工作人员准备好以后，后两类乘客可以开始登机。而在登机时，一般是先等待 VIP 乘客全部登机完，普通乘客才开始登机。
> - 我们将这个场景与操作系统调度进行类比：
>   - 工作人员就是实时任务，他们负责在规定时间内确保飞机可以按时起飞；VIP 乘客与交互式任务一样有着相对较高的优先级；而其他乘客则与批处理任务类似，其优先级低于实时任务和交互式任务。
>   - 以上三类人员被分在不同的场所等待，就好像操作系统将不同优先级的任务放在不同的任务队列中；另外，对于优先级相同的人员，他们的登记顺序并没有明确要求，工作人员只需要比乘客先行登机，按时做好准备工作即可，乘客一般采用排队（即先到先得）的方式决定相互之间的登机顺序。

1. **多级队列**（Multi Level Queue, MLQ）策略就是以上面类似的思想进行设计的：

![image-20220725163810567](https://notebook.ricear.com/media/202207/2022-07-25_163818_3612650.10028675379274943.png)

1. 每个任务会被分配 **预先设置好的优先级**，**每个优先级对应一个队列**，任务会被存储在对应的 **优先级队列** 中。
   2. 如果 **优先级不同** 的任务同时处于预备状态，那么调度器应该倾向于调度 **优先级较高** 的任务，因此 **一个任务必须等到所有优先级比他高的任务调度完才可以被调度**。
   3. 处于 **相同优先级** 队列的任务，他们内部的调度方式 **没有统一标准**，可以针对性地为不同队列采用不同调度策略，例如 FCFS 策略 或 RR 策略。

2. MLQ 策略适合 **静态** 的应用场景，这类场景下 **任务信息**（例如任务的大致运行时间、资源使用情况等）**可以在执行前告知**，根据任务信息，可以生成对应的调度模型，并进而计算出每种任务适合的优先级以进行调度。

3. 在设置 MLQ 策略的任务优先级时，需要注意 **将 I/O 密集型任务的优先级提高**。

> 我们可以试想一种计算密集型与 I/O 密集型任务混合运行的场景，假设计算密集型任务优先级比 I/O 密集型任务优先级高，那么就很可能遇到以下情况：
   >
   > - 大量的高优先级的计算密集型任务优先于 I/O 密集型任务执行，而 I/O 密集型任务一直没有机会发起 I/O 请求，必须等到所有计算密集型任务完成才可以执行，最终造成 I/O 资源利用率低下。
   >
   > 由于 I/O 密集型任务一般不会消耗大量 CPU 资源，完成可以提高其优先级，率先发起 I/O 请求，充分利用空闲的 I/O 资源。

4. MLQ 策略的 **优点**：

1. MLQ 策略是一种 **高效** 的优先级调度策略。

> 由于队列的数量一般是预先确定的，调度器可以在 $O(1)$ 时间内（相对于任务总量 $N$）找到所有非空队列中优先级最高的一个，并选取其队列头的任务进行调度。

5. MLQ 策略的 **缺点**：

1. **低优先级任务饥饿**。

> 在任务调度时，很有可能出现以下情况：
      >
      > ![image-20220725170214256](https://notebook.ricear.com/media/202207/2022-07-25_170221_0950120.7069557050334421.png)
      >
      > - 一个低优先级的任务一直在等待执行，但是大量高优先级的任务不断进入系统，造成低优先级的任务无法被调度，即 **低优先级任务饥饿**。
      > - 如果调度器需要保证一定的 **公平性**，避免 MLQ 策略引起的饥饿，需要额外的机制 **监控任务等待时间**，**为等待时间过长**（如超过一定阈值）**的任务提升优先级**。

2. **优先级反转**：

1. 优先级反转是由于 [同步](https://notebook.ricear.com/project-26/doc-325) 导致 **线程执行顺序违反预设优先级** 的问题。

2. **高优先级的任务被低优先级任务阻塞**，导致**高优先级任务迟迟得不到调度**，但其他**中等优先级的任务却能抢到 CPU 资源**。

3. 从现象上来看，**好像是中优先级的任务比高优先级任务具有更高的优先权**。

>   - 假定一个进程中有三个线程 Thread1（高）、Thread2（中）、Thread3（低），考虑下图的执行情况。
         >
         >     ![](https://notebook.ricear.com/media/202105/2021-05-18_091611.png)
         >
         >     - `T0` 时刻，`Thread3` 运行，并获得同步资源`SYNCH1`。
         >     - `T1` 时刻，`Thread2` 开始运行，由于优先级高于`Thread3`，`Thread3` 被强占（**未释放同步资源 `SYNCH1`**）。
         >     - `T2` 时刻，`Thread1` 抢占`Thread2`。
         >     - `T3` 时刻，`Thread1` 需要同步资源`SYNCH1`，但`SYNCH1` 被更低优先级的`Thread3` 所拥有，`Thread1` 被挂起等待该资源。
         >     - 而此时线程`Thread2` 和`Thread3` 都处于可运行状态，`Thread2` 的优先级大于`Thread3` 的优先级，`Thread2` 被调度执行，最终的结果是高优先级的`Thread1` 迟迟无法得到调度，而中优先级的`Thread2` 却能抢到`CPU` 资源。
         >
         >   - 上述现象中，优先级最高的`Thread1` 要得到调度，不仅需要等`Thread3` 释放同步资源（这个很正常），而且还需要等待另外一个毫不相关的中优先级线程`Thread2` 执行完成（这个就不合理了），会导致调度的实时性很差。

4. **解决方法**：

1. **优先级继承**：

1. 优先级继承是指**当高优先级进程（$P_1$）请求一个已经被低优先级进程（$P_3$）占有的临时资源时，将低优先级进程（$P_3$）的优先级临时提升到与高优先级进程（$P_1$）一样的级别，使得低优先级进程能更快的运行，从而可以更快的释放临界资源，当优先级进程离开临界区后，其优先级恢复至原本的值**。

> ##### 
               >
               > ![](https://notebook.ricear.com/media/202105/2021-05-18_094617.png)
               >
               > 1. 与上图相比，到了`T3` 时刻，`Thread1` 需要`Thread3` 占用的同步资源`SYNCH1`，操作系统检测到这种情况后，就把`Thread1` 的优先级提高到`Thread1` 的优先级。
               > 2. 此时处于可运行状态的进程`Thread2` 和`Thread3` 中，`Thread3` 的优先级大于`Thread2` 的优先级，`Thread3` 被调度执行。
               > 3. `Thread3` 执行到`Thread4` 时刻，释放了同步资源`SYNCH1`，操作系统恢复了`Thread3` 的优先级，`Thread1` 获得了同步资源`SYNCH1`，重新进入可执行队列。
               > 4. 处于可运行状态的进程`Thread1` 和`Thread2` 中，`Thread1` 的优先级大于`Thread2`，所以`Thread1` 被调度执行。

2. **存在问题**：

1. **潜在死锁**。

> 1. 以下图为例，高优先级任务`T1` 请求被低优先级任务`T2` 占有的临界资源`S2` 时，进入阻塞状态，此时会把`T2` 优先级提升到`T1` 的水平。
                  > 2. `T2` 运行一段时间后，当请求被`T1` 占有的邻接资源`S1` 时，也会进入死锁状态，此时死锁形成。
                  >
                  > ![](https://notebook.ricear.com/media/202105/2021-05-18_101704.png)

2. **链阻塞**。

> 1. 以下图为例，高优先级任务`T1` 请求临界资源`S1` 时，中优先级任务`T2` 被提升，获得`CPU` 执行权，执行完成之后，释放`S1`，`T1` 继续往前执行。
                  > 2. 当请求临界资源`S2` 时，低优先级任务`T3` 优先级被提升，获得`CPU` 执行权，执行完成之后，释放`S2`，`T1` 继续往前执行。
                  > 3. 在这个例子中，`T1` 被阻塞了两次，更极端的例子，`T1` 会被阻塞很多次，这个叫**链阻塞**。
                  >
                  > ![](https://notebook.ricear.com/media/202105/2021-05-18_103337.png)

2. **优先级天花板**：

1. 优先级天花板是指**将申请资源的任务的优先级提升到可能访问该资源的所有任务中最高优先级任务的优先级**。

2. 当一个进程**获取到临界资源**，就将该进程的优先级**提升到优先级天花板**，这样，该**进程不会被其它可能使用该临界资源的进程抢占**，从而得到**更快执行**，**更快地释放临界资源**，**释放临界资源后，恢复优先级**。

> 1. 如下图所示，进程 $[P_1,P_3]$ 会访问临界资源 $S_1$，因此 $S_1$ 的优先级天花板为 1，同理可得，$S_2$ 的优先级天花板也为 1.
               > 2. 首先 $P_3$ 成功占有临界资源 $S_1$，此时 $P_3$ 的优先级被提升至 1，顺利执行完临界区代码，恢复优先级。
               > 3. 然后 $P_2$ 抢占 $P_3$，同理，$P_2$ 的优先级被提升至 1，$P_2$ 也可以顺利执行完临界区代码，恢复优先级。
               > 4. 最后，$P_1$ 抢占 $P_2$，此时，临界资源 $S_1$ 和 $S_2$ 皆已释放，$P_1$ 可以一口气执行到底，可见，这里不存在链阻塞问题。
               >
               > ![](https://notebook.ricear.com/media/202105/2021-05-18_112000.png)

> 优先级继承和优先级天花板的区别？
               >
               > 1. 优先级继承只有当**高优先级任务请求一个被阻塞的低优先级占有的临界资源**时才会提升低优先级任务的优先级。
               > 2. 优先级天花板是只要**有任务去申请临界资源**，就会提升该任务的优先级。

##### 多级反馈队列

> 随着计算机的发展，操作系统中任务的需求变得越来越复杂，任务可能同时希望有 **较低的周转时间与响应时间**，并且任务的 **运行时间无法预知**。前面介绍的 STCF 策略和 RR 策略都无法同时满足上述需求。因此，寻找一个综合全面的、适应动态应用场景的调度策略，成为当时研究的目标之一。
>
> 图灵奖获得者 [Corbató](https://en.wikipedia.org/wiki/Fernando_J._Corbat%C3%B3) 于 1962 年提出了 [多级反馈队列](https://en.wikipedia.org/wiki/Multilevel_feedback_queue)（Multi-Level Feedback Queue, MLFQ），其设计目标是 **在无法预知任务信息且任务类型动态变化**（任务行为模式会在计算密集型与 I/O 密集型间转换）**的场景下**，**既能达到类似 STCF 策略的周转时间**，**又能像 RR 策略一样尽可能降低任务的响应时间**，为此，MLFQ 策略在 MLQ 策略的基础上，增加了 **动态设置任务优先级** 的策略。

1. 与 MLQ 策略类似，MLFQ 策略也会维护多个优先级队列，任务根据优先级存于 **不同队列** 中，**高优先级任务先于低优先级任务执行**，处于 **相同优先级** 的任务则采用 **RR 策略执行**。

2. MLFQ 策略的一大创新是实现了 **优先级的动态配置**，具体策略如下：

1. **短任务拥有更高的优先级**：

> :thinking: 给短任务更高的优先级有什么好处？
      >
      > - 第一，在介绍 SJF 策略时已经提到，优先调度短任务可以有 **更好的平均周转时间**。
      > - 第二，I/O 密集型任务一般在 CPU 中执行的时间很短，给短任务提高优先级也相当于提高 I/O 密集型任务的优先级，有利于 **提高系统的 I/O 资源利用率**。
      > - 第三，交互式任务一般是短任务，提高其优先级有助于 **降低这些任务的响应时间**。

1. MLFQ 策略会首先 **对任务的运行时间进行评估**，预计运行时间较短的任务会放入 **优先级较高的队列** 中，但是，在真实系统中，可能无法准确追踪任务的完成时间和剩余完成时间，这也是 SJF 策略和 STCF 策略的一大限制，为此，MLFQ 会 **统计每个任务已经执行了多长时间**，并据此 **判断该任务是短任务还是长任务**：
         1. 首先，当任务进行系统时，MLFQ 会假设该任务是 **短任务**，为其设置 **最高优先级**，这有利于交互式任务达成 **较短的响应时间** 以及 I/O 密集型任务 **充分利用 I/O 资源**。
         2. 然后，MLFQ 会为每个任务队列设置任务的 **最大运行时间**（任务多次运行的总时间，而非时间片），如果任务在当前队列多次运行的总时间最终 **超过了队列允许的最大时间**，MLFQ 策略会认为该任务是运行时间较长的任务，进而将该任务的 **优先级减一**。
         3. 凭借该方法，MLFQ 就可以大致适配任务的优先级，即动态评估任务的运行时间。由于短任务一般都可以在预设的时间片内完成，因此可以一直保留在优先级较高的队列中；相对地，长任务的优先级则会随着执行次数的增多逐渐降低。

2. **低优先级的任务采用更长的时间片**：

1. 为了尽量 **减少任务的调度次数**，MLFQ 根据预估的任务执行时间，给与一个合适的调度时间片，**优先级越低** 的任务，其 **时间片越长**。
      2. 由于 MLFQ 策略 **支持抢占式调度**，所以无须担心低优先级的任务阻塞新进入系统的任务。

3. **定时地将所有任务的优先级提升至最高**：

> 与 MLQ 策略类似，上面两种 MLFQ 策略也有可能造成 **低优先级任务饥饿**：
      >
      > - 当一个 **长任务** 经过一定时间的运行后，他最终会被分配到 **最低的优先级**。
      > - 如果此时一直有短任务需要调度，那么长任务就无法执行，造成饥饿现象。
      >
      > 在某些场景下，一个任务原本可能是 **计算密集型任务**，因而被放入 **最低优先级队列**，但在一定时间后，**用户希望与其交互**，该任务则变成了一个对响应时间有要求的 **交互式任务**。
      >
      > 因此，MLFQ 策略会**在一定时间周期后将系统内所有任务的优先级重新提升至最高级**，**保证不会有任务饥饿**。

> 下图展示了三个任务 $A$、$B$、$C$ 基于 MLFQ 策略的执行流：
   >
   > ![image-20220725205234992](https://notebook.ricear.com/media/202207/2022-07-25_205242_9306870.8328747716638062.png)
   >
   > 1. 任务 $A$ 是一个长任务，而任务 $B$ 和 $C$ 的运行时间相对较短。
   > 2. 在初始阶段，任务 $A$ 和 $B$ 进入系统，并且被分配最高的优先级。
   > 3. 当他们在队列 0（最高优先级队列）中执行至最大运行时间后，调度器会降低他们的优先级，将他们移至队列 1。
   > 4. 任务 $B$ 在队列 1 执行结束，而任务 $A$ 一直执行，因此 $A$ 会因为优先级被进一步降低而被移至队列 2。
   > 5. 当任务 $A$ 在队列 2 执行到第 2 个时间片时，任务 $C$ 进入系统，他被调度器分配最高的优先级，抢占任务 $A$ 的执行。
   > 6. 过了一段时间后，到达调度器定式提升任务优先级的时间间隔，任务 $A$ 和 $C$ 都被移至队列 0 执行。任务 $C$ 随后在队列 0 的第一个时间片结束自己的执行，而长任务 $A$ 继续执行，并最终再次回到最低优先级的队列 2。

3. MLFQ 的 **优点**：

1. MLFQ 策略通过记录任务运行时间的方式，动态地调配任务的优先级，可以达到与 SJF 策略和 STCF 策略类似的 **低平均周转时间**，同时还能 **保证任务的响应时间**，且能 **避免任务饥饿**。

4. MLFQ 的 **缺点**：

1. **实现复杂**。

> - 在 MLFQ 策略的具体实现中，就有许多调度参数需要调整，例如 **优先级队列的数量**、**每个优先级队列采用的时间片**、**任务在每个优先级队列的最大运行时间**、**调度器定时提升优先级的时间间隔**。
      > - 如果参数使用不当，就可能达不到与其的调度效果：
      >   - 如果提升优先级的时间间隔过短，那么所有任务都会保持在最高优先级的队列中，MLFQ 策略退化成 RR 策略。
      >   - 如果提升优先级的时间间隔过长，很可能会导致长任务保持在最低优先级队列中，很长时间内无法执行。

#### 公平共享调度

> - 当用户共享服务器时，一个默认的假设是 **用户使用的资源数**（例如 CPU 时间）**与所付出的资金是成正比的**。
>
> - 假设小明和小红合租了一台云计算平台上的 **单核服务器**，他们商定平分 CPU 时间，并且小明同时开启三个任务（任务 $A$、$B$、$C$），而小红只开启一个任务（任务 $D$）。那么有什么调度策略能够保证小明的三个任务和小红的一个任务平分 CPU 时间呢？
>   - 假设这些任务的优先级相同，并且采用 RR 策略进行公平调度，那么由于此时小明开启了三个任务，他会占据 75% 的 CPU 时间，而小红则只能使用剩下的 25%，因此 RR 策略不能满足两人平分 CPU 资源的约定。
>   - 小明和小红决定尝试优先级调度，小明的三个任务优先级被设置为 1（低优先级），而小红的一个任务优先级被设置为 3（高优先级），这样的优先级分配从数值上体现了用户对资源占比的预期（小明与小红的 CPU 时间占比为 （1 + 1 + 1）：3）。然而实际调度中，在没有防止低优先级任务饥饿的机制的情况下，小红的任务会持续执行直到结束。我们发现，优先级的数值仅仅是用于比较优先级高低而存在的，他无法反映单位时间内一个任务可以占用的 CPU 时间比例。因此优先级调度也无法保证任务对资源使用的实际比例。
> - 在考虑资源的使用情况时，用户看重的已经不再是平均周转时间或者响应时间，而是自己 **在总资源中的占有比例**，用户希望：
>   - 优先级为 3 的任务占有的 CPU 时间是 优先级为 1 的任务的 3 被，是优先级为 6 的任务的一半。
>   - 支持以用户或一组任务为粒度进行系统资源的分配。
> - 为了满足以上需求，**公平共享调度**（Fair-Share Scheduling）应运而生，这类调度器会 **量化任务对系统资源的占有比例**，从而实现对资源的 **公平调度**。

1. 公平共享调度以 **份额** 来量化每个任务对 CPU 时间的使用。

> 下图给出了小明和小红决定使用份额的例子，假设当前 CPU 核心只负责处理他们两人的请求。
   >
   > ![image-20220726170923977](https://notebook.ricear.com/media/202207/2022-07-26_170935_7898080.8707678572525932.png)
   >
   > - 从小明和小红的视角来看，每人都拥有 40 的份额，即每人使用一半的 CPU 时间。
   > - 任务的份额并非系统直接给定的，而是两人从自己的份额中选取一部分交给各自的任务。
   >
   > 下图根据以上例子，给出了理想情况下的公平共享调度应达到的 CPU 时间占比。
   >
   > ![image-20220726171539344](https://notebook.ricear.com/media/202207/2022-07-26_171548_2601460.9599879002310546.png)
   >
   > - 小明的份额占了系统总份额的 50%，而任务 $B$ 的份额占了小明总份额的 50%，因此任务 $B$ 的实际 CPU 占比是 50% $\times$ 50% = 25%。

2. 以上例子反映了用户不同于此前的需求，他们可能需要一个直接或间接的 **参数** 能够 **控制任务的资源使用情况**，而份额支持 **层级化** 的分配方式，可以直观地体现每个任务的理论资源使用情况。在实际场景中，为了方便管理，可以将任务 **分组**（称为 **任务组**），**以组为单位分配份额**，任务会在组内进一步分摊该组所拥有的份额。

> :thinking: 在优先级调度策略和公平共享调度策略中，优先级和份额都体现了任务的重要性，他们之间有什么区别与联系？
>
> - 优先级与份额都表示了任务在系统中的重要程度，但是他们的目的是不同的：
>   - 优先级调度是为了 **优化任务的周转时间**、**响应时间和资源利用率** 而设计的，不同任务的优先级只能用于 **相互比较**，表明 **任务执行的先后**。
>   - 基于份额的公平共享调度是为了 **让每个任务都能使用他应获得的系统资源**，份额的值明确对应了任务应使用的 **系统资源比例**，下面我们将会介绍两个经典的公平共享调度策略，分别为 **彩票调度** 和 **步幅调度**。

##### 彩票调度

> 假设现在班级里举行抽奖活动，小明和小红分别拥有 3 张和 6 张彩票，而班级里其他同学一共拥有 21 张彩票，将在这 30 张彩票中随机抽取一张，被抽中彩票的归属者中奖。可以算出小明和小红单次抽奖的中奖概率分别为 10% 和 20%。如果将抽奖的次数上调，那么他们的中奖次数与总抽奖次数的比例也将趋近于 10% 和 20%。

1. 彩票调度策略的思想与实际的彩票抽奖类似：

1. 在该策略中，**份额** 就相当于 **每个班级同学同学拥有的彩票数**。
   2. 在每次调度时，会根据 **随机数**（彩票开奖）确定任务是否被调度，任务所占的份额越大，随机数就越有可能落在他的份额之内，因此他就越有可能会被调度。
   3. 随着调度（开奖）的次数不断增加，任务被调度的次数占总调度次数的比例也将趋近于该任务所拥有的的份额占总份额的比例。

> 下面的代码片段展示了彩票调度的伪代码：
   >
   > ~~~c++
   > R = random(0, total_tickets);
   > sum = 0;
   > foreach(task in task_list) {
   > sum += task->ticket;
   > if (R > sum) {
   >  schedule();
   >  break;
   > }
   > }
   > ~~~
   >
   > - 调度器保留了当前的总彩票数（`total_tickets`）；所有任务存储在一个队列（`task_list`）中，每个任务记录了自己占有的彩票数（`ticket`）；在调度时，调度器在总彩票数的范围内随机地生成一个中奖彩票号码（`R`）。
   > - 接着，调度器会遍历任务列表中的元素，并使用一个计数器（`sum`）记录已经遍历的任务的彩票数总和（包括当前正在遍历的任务的份额）。
   > - 如果这个总和超过了随机数，则选择当前任务进行调度（`schedule()`）。

> 下面以随机数为 41 为例展示彩票调度的过程：
   >
   > ![image-20220726211346860](https://notebook.ricear.com/media/202207/2022-07-26_211358_1761050.027503799702170983.png)
   >
   > - 调度器从列表头部开始，首先遍历到任务 $A$，因为任务 $A$ 的彩票数为 10，所以计数器的值从 0 变为 10，但是仍然小于 41，因此调度器继续遍历列表。
   > - 当遍历到任务 $B$ 时，计数器的值变为 40，仍然小于 41。
   > - 最后，当调度器遍历到任务 $C$ 时，计数器的值变为 80，大于 41，因此调度器选择任务 $C$ 进行调度。
   > - 类似地，当随机数为 35 时，彩票调度策略将选择任务 $B$ 进行调度。

2. 彩票调度策略一般不要求列表中的任务按照持有的彩票数量排序，因为 **影响任务被调度概率的因素是每个任务持有的份额**，而非任务在列表中的顺序，不过，如果将任务按照持有的份额数量从高到低进行排序，可以 **减少决策时列表的查找次数**。

> 假设上面的例子中产生的随机数为 35：
   >
   > - 如果列表按份额数量从低到高排序，则需要两次列表查找才能确定要调度的是任务 $B$。
   > - 如果列表按份额数量从高到低排序，则任务应以 $C$、$B$、$A$ 的顺序存储在列表中，此时通过一次查找就可以确定要调度的是任务 $C$。

3. 除了彩票调度的基本算法外，彩票调度还给出了一些基于彩票的 **优化** 方法，用于解决不同的问题：

1. **彩票转让**：

1. 在系统实际运行中，份额大的任务 $A$ 可能在等份额小的任务 $B$ 所持有的锁，彩票调度会让 $A$ 有更高的概率运行，然而任务 $A$ 申请不到任务 $B$ 的锁，会造成 CPU 资源的浪费。
      2. 针对该问题，任务 $A$ 可以将自己的份额 **转让** 给任务 $B$，在转让后，任务 $B$ 将拥有更高的 CPU 占比份额，减少资源浪费。

> :information_desk_person: 彩票转让的思想与 **优先级继承** 类似。

2. **彩票货币**：

1. 用户或者任务组在分配自己的彩票给子任务时，可以采用自己的计算方式，类似于发行自己的货币。

> - 假设现在小明和小红分别有 60 张和 40 张彩票，且他们各自的任务分别组成了一个任务组。
         > - 小明可以设置自己总共有 400 货币，并进一步把自己的 100 货币分配给任务 $A$，另外 300 货币分配给任务 $B$，那么任务 $A$ 的实际彩票数为 $\frac{100}{400} \times 60 = 15$ 张，而任务 $B$ 则为 45 张。

> :thinking: 为什么不直接将 15 张和 45 张彩票分配给两个任务，还要多此一举呢？
         >
         > - 试想如果此时小明的 20 张彩票被转让给了小红，在没有彩票货币机制的情况下，为了保证任务 $A$ 和任务 $B$ 的彩票数之和为 40，就需要专门去修改他们记录的彩票数量。
         > - 而在使用彩票货币的情况下，由于任务 $A$ 和任务 $B$ 对应的彩票货币数不变，因此无须对任务 $A$ 和任务 $B$ 进行修改，只需要对小明的任务组持有的彩票数进行修改即可。
         > - 通过添加一层彩票货币的抽象，可以让任务组更加灵活地修改自己持有的份额，避免影响从属于他们的任务。

3. **彩票通胀**：

1. 彩票通胀的思想是给任务一定 **自由度**，允许任务根据任务当前对 **CPU 资源的需求** 决定自己的 **份额**。
      2. 这种动态调整份额的方式可以应对 **变化的应用场景**，让需要资源的任务动态地申请更多的资源，而不需要资源的任务则可以释放自己的资源。
      3. 但是，彩票通胀需要多个任务间 **互相信任**，如果有任务恶意地提升自己的彩票量，那么最坏情况下他会占用绝大部分的 CPU 时间。

> :thinking: 彩票调度中的随机数可能会带来哪些问题？
>
> - 彩票调度通过使用随机的方式实现了一个简单并且近似于公平共享的调度器，然而，随机数会导致某一任务占用 CPU 时间的比例，需要在该任务经历 **多次调度** 后，才能趋近于该任务的份额在所有任务总份额的比例，即只有调度次数足够多，彩票调度的效果才接近公平。
>
> - 假设在同一时间，两位用户分别发起了一个任务，并期望平分 CPU 时间，那么理论上两个任务被调度次数的比例应该近似为 1 : 1（假设两个任务的时间片相同），下图展示了在模拟的彩票调度中，随着总调度次数的增加，两个任务被调度次数的比例：
>
>   ![image-20220727210025480](https://notebook.ricear.com/media/202207/2022-07-27_210037_3183120.5721424984599366.png)
>
>   - 在该模拟图中，当总调度次数小于 16 时，比例一直与理想的 1 : 1 相差较多；当总调度次数大于或等于 16 时，比例近似于 1 : 1，但仍然有一定波动。
>   - 对于运行时间比较短的任务，如果调度次数过少，彩票调度实际分配给任务的 CPU 份额可能因为随机性而与预期不同，不一定能保证公平。

##### 步幅调度

1. 步幅调度与彩票调度非常相似，也会使用 **份额** 的概念为每个任务分配占用 CPU 时间的比例，其不同点在于，步幅调度采用 **确定性** 的方式调度任务，核心概念是 **步幅**。

> :thinking: 假设在一台机器上存在任务 $A$ 和任务 $B$，他们的份额之比为 5 : 6，那么该怎么使这两个任务使用的 CPU 时间之比也是 5 : 6 呢？
   >
   > - 这里我们引入 **虚拟时间** 的概念（虚拟时间与任务真实执行的物理时间没有直接关联）：
   >
   >   - 为了让虚拟时间短的任务能够 **追赶** 虚拟时间长的任务，使用虚拟时间的调度策略一般会选择调度所有任务中 **虚拟时间最少** 的任务。
   >   - 每个任务都会 **记录他已经执行的虚拟时间**，并且 **仅在任务调度时更新其虚拟时间**，同时，将他们的运行时间片设置为相同的 $T$ 秒，任务 $A$ 每次调度时其虚拟时间加 6 秒（步幅为 6），任务 $B$ 每次被调度时其虚拟时间加 5 秒（步幅为 5）。
   >
   > - 下图是上述例子的示意图，每个方框代表了任务执行的虚拟时间长度，方框内的数字代表了任务被真实执行时的调度次序：
   >
   >   ![image-20220727213524344](https://notebook.ricear.com/media/202207/2022-07-27_213534_1250680.6887579992882047.png)
   >
   >   - 步幅调度告诉系统 **在某一时刻应该调度哪个任务**，并且这个调度是可以保证 **公平共享** 的，即每当这两个任务的虚拟时间增加 30 秒，他们被调度的次数之比为 5 : 6，所使用的 CPU 时间之比也是 $ 5T : 6T $，即 5 : 6。
   >   - 通过步幅计算任务的虚拟时间，可以保证 **任务被调度的次数与份额成正比**，由于所有的计算都是确定性的，因此最终的调度也是确定性的。

2. 步幅调度通过设置虚拟时间的方式，让任务在每次调度时增加一定的虚拟时间，即 **步幅**，**经历虚拟时间相同**的任务，他们**使用的 CPU 时间之比就是步幅倒数之比**，即 任务的 **份额之比** 正对应了任务的 **步幅的倒数之比**。

3. 步幅调度的伪代码如下：

~~~c++
   // 选择并移除运行队列中虚拟时间最小的任务
   task = remove_queue_min(q);
   // 调度该任务并让其执行一个时间片
   schedule(task);
   // 使用该任务的步幅计算调度后的虚拟时间
   task->pass += task->stride;
   insert_queue(q, current);
   ~~~

1. 步幅调度为每个任务维护一个 `pass` 变量，表示任务 **经历的虚拟时间**。
   2. 使用 `stride` 变量保存每个任务的 **步幅**，为了让 `stride` 能够是一个整数，会设置一个极大的整数 `MaxStride`（为了直观，设置 `MaxStride` 为任务 $A$ 和 $B$ 的份额的最小公倍数），并设置 `stride = MaxStride / ticket`，其中 `ticket` 就是 **份额**。
   3. 首先选取当前 **虚拟时间最小** 的任务调度并将该任务 **从运行队列移除**，在调度结束后 **按步幅增加其虚拟时间**，并将该任务重新 **加入运行队列** 中。

> 在真实系统中需要注意的是，由于任务可能在任意时间进入系统，因此任务的 `pass` 不能够简单地从 0 开始设置，而应该设置为 **当前所有任务的最小 `pass` 值**，否则，可能会导致 **新进入的任务长时间占有 CPU**。

### :soccer: 多核调度策略

> 在上面讨论的单核调度策略中，虽然多个任务 **并发** 地在 **一个** 共享的 CPU 核心上执行，但是本质上他们仍然是在串行地执行。而在多核系统中，任务会同时在 **多个** CPU 核心上 **并行** 地执行，相比于单核调度策略，多核调度策略需要考虑的因素更加复杂。

#### 负载分担

1. 我们首先沿用单核调度策略的思路，设想多核共享一个 **全局运行队列**，当一个 CPU 核心需要调度任务时，根据 **给定的调度策略**，决定全局运行队列中下一个由他执行的任务，给定的调度策略可以是任意一种 **单核调度策略**，这种方法也被称为 **负载分担**，因为 **系统的负载是被所有 CPU 核心分担的**。

![image-20220728160009123](https://notebook.ricear.com/media/202207/2022-07-28_160021_1982130.42524383922076636.png)

2. 负载分担的 **优点**：

1. **设计实现简单**。

> - 通过使用负载分担，可以将多核调度问题 **规约为单核调度问题**，使用已有的单核调度策略和单核调度器，就可以实现一个多核的全局调度器。

2. 每个 CPU 核心都会 **分担系统的负载**，不会出现 CPU 资源浪费的情况。

> 一个 CPU 核心执行完当前任务后，他会从全局任务队列中再选取一个任务执行，因此，只要系统当前还有可以执行的任务，每个 CPU 核心都能够获取到任务执行。

3. 负载分担的 **缺点**：

1. 多核共享一个全局运行队列的 **同步开销**。

> 前文假设任务的切换调度没有开销，但是该假设在多核调度器中是不合理的，因为多核之间的 [同步问题](https://notebook.ricear.com/project-26/doc-325) 可能导致调度开销变得不可忽视。

2. 任务在 **多个 CPU 核心间来回切换的开销**。

> - 假设全局有 4 个任务 $A$、$B$、$C$ 和 $D$，他们的运行时间足够长，使用 RR 策略对他们进行调度。
         >
         > - 因此在任务执行完一个时间片后，CPU 核心会从全局运行队列中选取下一个任务进行执行，并将当前任务插到全局运行队列的队尾。
         > - 不难看出，每个任务在前后两个时间片执行时所处的 CPU 核心是不相同的，而任务在不同 CPU 核心间切换会导致大量开销，包括 **重新载入缓存**、[TLB 刷新](https://notebook.ricear.com/project-26/doc-340/#2-4-2-%E5%88%B7%E6%96%B0)等。
         >
         > ![image-20220728163324367](https://notebook.ricear.com/media/202207/2022-07-28_163346_4991510.14520972760102424.png)

#### 协同调度

> 多线程程序为了利用多核处理器，通常会将一个工作量较大的任务 **切分成多个子任务**，并将每个子任务交给 **不同的 CPU 核心** 完成，这些子任务之间可能会有 **依赖关系**，另外，某些子任务倾向于 **同时执行**：
>
> - 假设小明想使用 `Makefile` 编译一个程序，该程序涉及 4 个源文件 `file1.c ~ file4.c`。
> - 小明为了利用系统中的多个 CPU 核心，输入了 `make -j 4`，使用 4 个线程并行编译：
>   - 编译器第一步会把 `.c` 文件编译成对应的 `.o` 文件，第二步将所有 `.o` 文件编译成可执行文件。
>   - 如果前 3 个文件的第一步已经完成，编译器不能并行地编译第 4 个 `.o` 文件和生成可执行文件，因为编译器只有当第一步完成（生成全部 4 个文件对应的 `.o` 文件）时，才能开始第二步（生成可执行文件）。
>   - 因此，虽然第二步的任务已经可以被调度到某个 CPU 核心上开始执行，但是由于第一步和第二步的任务之间存在依赖关系，他依然需要等待第一步对应的任务全部完成，因而造成 CPU **资源的无端消耗**。
>   - 在这个例子中，只有当第一步的 4 个任务全部完成才能执行第二步的任务，因而认为第二步的任务对第一步的任务存在依赖。
>
> 在需要 **相互通信** 的线程中也可能出现无端消耗 CPU 的情况：
>
> - 假设两个线程 $A$ 和 $B$ 对应于程序的子任务，在一个时间片内他们可以进行多轮通信（$A$ 将请求发送给 $B$ 然后 $B$ 返回结果，这样算是一轮通信）。
> - 但此时，由于调度器并不知晓他们的关联，$A$ 和 $B$ 虽然在不同的 CPU 核心上却无法同时执行，其结果是在第一个时间片内 $A$ 只能发送一个请求给 $B$，在第二个时间片内 $B$ 收到来自 $A$ 的请求并返回，在第 3 个时间片内 $A$ 才能收到来自 $B$ 的返回结果，大大降低了程序的执行效率。
>
> 为了满足对 **一组任务** 进行调度的需求，**协同调度** 的概念应运而生，协同调度的目的是 **尽可能让一组任务并行执行**，**避免调度器同时调度有依赖关系的两组任务**（对应于 `Makefile` 例子中第一步的任务与第二步的任务），**同时避免关联任务**（倾向于同时执行的一系列任务，比如需要相互通信的任务）**执行效率低的问题**。

##### 群组调度

1. 协同调度的一个经典策略是 **群组调度**，其基本思想是 **将关联任务设置为一组**，**并以组为单位调度任务在多个 CPU 核心上执行**，**使他们的开始时间和结束时间接近相同**。

2. 为了保证一组任务同时执行，群组调度会 **在多个 CPU 核心上同时进行调度**。

> - 假设一个多核系统上共有 5 个 CPU 核心，4 组任务 $A$、$B$、$C$ 和 $D$，组内的任务都是关联任务，需要同时执行，采用群组策略进行调度。
   >
   > - 组 $A$ 有 5 个任务，调度器一次性调度这 5 个任务一起执行。组 $B$ 和 $C$ 分别有 2 个任务，因此在一个时间片后，这些任务会被调度器调度。此时还有一个 CPU 核心空闲，调度器决定让组 $D$ 的 6 个任务中的一个率先执行。又一个时间片过后，调度器让组 $D$ 的剩下 5 个任务同时执行。以 3 个时间片为周期，群组调度策略会一直进行如下图所示的调度。
   >
   >   ![image-20220728175638789](https://notebook.ricear.com/media/202207/2022-07-28_175650_1013930.8255454240624392.png)

3. 通过将任务以组为单位在多核处理器上进行调度，群组调度策略可以 **提升特定应用场景的任务执行性能**，然而，如果在应用场景不匹配的情况下，群组调度策略可能并不是最优的，因为他会要求无关联的任务必须同时进入或退出 CPU 核心，**无关联任务之间的的相互等待可能造成 CPU 资源的浪费**。

#### 两级调度

1. 在前面我们介绍到 **全局调度器** 会使得任务在不同 CPU 核心上切换执行，造成切换开销，为了减少开销，每个任务应 **尽可能只在一个 CPU 核心上进行调度**。因此，新的调度策略改为每个 CPU 核心都引入一个 **本地调度器**。

2. 这种调度策略使用全局调度器和本地调度器，构成了 **层级化结构**，一般称之为 **两级调度**。

> 一个两级调度的示意图如下图所示。
   >
   > ![image-20220728195634724](https://notebook.ricear.com/media/202207/2022-07-28_195647_8108180.6306563101362485.png)
   >
   > - 当一个任务进入系统时，**全局调度器** 根据系统的当前信息，诸如每个 CPU 核心的负载情况，决定该任务应该被哪个 CPU 核心执行。
   > - 当一个任务被分配到给定的 CPU 核心时，他将一直被该核心的 **本地调度器** 管理，不会迁移到其他 CPU 核心上执行。同时，每个本地调度器可以使用 **任意单核调度策略** 来调度任务。
   > - 在两级调度中，线程无须在 CPU 核心间来回切换，从而 **提高了缓存局部性**，**减少了数据竞争的冲突**。同时，这种层级化的设计 **将设计单核策略与支持多核调度进行了解耦**，使得调度器的设计实现更加 **灵活**。

> 以 Linux 为代表的一系列操作系统会为每个 CPU 核心分配一个 **本地运行队列**，即可以理解为每个 CPU 核心有一个本地调度器。

#### 负载追踪与负载均衡

> - 两级调度策略通过将任务绑定到特定的 CPU 核心上进行调度执行，**避免了任务在多核间切换**，因而在多核调度时有良好的性能。
> - 不过，由于两级调度在 **任务开始时** 就指定了他在哪个 CPU 核心上运行，且没有任务在 CPU 核心间切换的机制，这可能会导致 **多核间的负载不均衡**，例如一个 CPU 核心的利用率为 100%，而剩余 CPU 核心的利用率都为 0%。
> - 为了解决这一问题，两级调度引入了 **负载均衡策略**，其思想是 **通过追踪每个 CPU 核心当前的负载情况**，**将处于该负载的 CPU 核心管理的任务迁移到低负载的 CPU 核心上**，**尽可能地保证每个核心的负载大致相同**。

##### 调度实体粒度负载追踪

1. 负载均衡面临的一大挑战是 **应该如何确定当前任务的负载情况**，对当前任务的负载信息描述得越准确，对应的负载均衡策略就越有效。

2. 在大部分场景中，一个任务的执行负载是动态变化的，因此系统必须 **动态追踪** 系统当前的负载情况，这会造成一定的 **性能开销**。

3. 所以，如何保持 **在保持低开销的同时对负载进行精确追踪** 是调度器设计实现的一大挑战。

> - 在 Linux 3.8 版本以前，内核以每个 CPU 核心的 **运行队列** 为粒度来计算负载，认为运行队列长的负载越高，导致负载追踪 **不够精确**。
   >
   > - 当调度器决定从一个高负载的运行队列中选取一个任务迁移到低负载的运行队列时，由于他 **缺乏每个任务的信息**，因此 **无法选出合适的任务进行迁移**。
   > - 所以，**以运行队列为粒度的负载追踪并不能够适应负载均衡的要求**。

4. 在 Linux 3.8 版本以后，Linux 使用了 **以调度实体**（单个任务）**为粒度** 的负载计算方式，做到了 **更细粒度** 的负载追踪。

1. 调度实体粒度负载追踪（Per-Entity Load Tracking, PELT）**通过记录每个任务的历史执行状况来表示任务的当前负载**。

> - 调度器会以 1024 微秒为一个周期，记录任务处于 **可运行状态**（包括正在运行的以及等待被运行的）**的时间**，记为 $x$ 微秒。
      > - 该任务在**第 $i$ 个周期**（$T_i$）**内对当前 CPU 的利用率为** $\frac{x}{1024}$，而**对应的负载** $L_i = scale\_cpu\_capacity \times \frac{x}{1024}$，其中 $scale\_cpu\_capacity$ 是 **CPU 容量**（用于归一化系统中的 CPU 处理能力），可以理解为 **对应 CPU 核心的处理能力**。

2. 在收集到任务每个周期内的负载后，PELT 需要计算 **一段时间内任务所有周期的累计负载**，记为$L$。

> - 一种简单计算 $L$ 的方法是 **将所有周期的负载直接累加**。
      >
      > - 然而，一个任务可能运行一天甚至更久，对于计算任务当前负载的 PELT 来说，过于久远的历史负载信息没有太大参考意义，因此应该记录 **一定周期范围内的累计负载**。
      >
      > - 距离当前时间点越近的周期所记录的负载更有可能反映任务的当前执行负载，所以应该对累计负载有更大的贡献，因此，PELT 采用的计算任务累计负载的方式是 **通过衰减系数 $y$ 来衰减之前周期的负载**，具体公式如下：
      >   $$
      >   L = L_0 + L_1 * y + L_2 * y^2 + L3 * y^3 + \cdots
      >   $$
      >   其中，$L_i$ 代表第 $i$ 个周期的负载。该计算公式不仅考虑了 **不同周期的权重**，**开销也很低**。
      >
      > - PELT 无须保存任务每个周期内的负载，只需要维护累计负载 $L$。当需要计算新的累计负载时，PELT 只需要 **用衰减系数 $y$ 衰减原累计负载 $L$ 并与当前周期 $T_n$ 的负载 $L_n$ 相加** 即可：
      >   $$
      >   L^{'} = L \times y + L_n
      >   $$
      >
      > - 通过计算每个任务的负载 $L$，PELT 就可以进而统计出 **每个运行队列的负载**，**便于调度器做出有效的迁移决策**。

3. 总体来说，PELT 的好处是他的 **开销很小**，且 **能够帮助调度器更细粒度**、**更精确地监测任务的负载**，**对于预测负载均衡策略的效果有很大帮助**。

##### 负载均衡

> 在追踪了每个任务以及每个 CPU 核心上的负载后，需要开始考虑 **多核间的负载均衡**，即 **将任务从负载高的 CPU 核心迁移到负载低的 CPU 核心上**。

1. 随着当前计算机上的 CPU 核心数量越来越多，系统架构越来越复杂，负载均衡策略不能简单地对全部 CPU 核心进行均衡。

> - 一方面，考虑大量 CPU 核心的负载均衡会引入很大的开销，负载均衡策略 **做出决策的开销应该尽量小**。
   >
   > - 另一方面，由于 CPU 核心间不是对等的，任务在多核间迁移的开销也是不一样的，负载均衡策略应让任务 **尽量在迁移开销较小的 CPU 核心间迁移**。

> 以 **非一致内存访问**（Non-Uniform Memory Access, NUMA）的多核处理器为例：
   >
   > - 在 NUMA 架构下，多个 CPU 核心组成一个 NUMA 节点，一个 NUMA 节点拥有 **本地内存**，也可以访问其他 NUMA 节点的 **远端内存**，但远端内存的访问时延要明显高于本地内存。
   > - 如果操作系统将一个任务从一个 NUMA 节点迁移到了另一个节点，会严重影响任务的执行效率。
   >
   > 又以 **超线程** 为例：
   >
   > - 一个 **物理核** 会被逻辑上分为两个 **逻辑核**。
   > - 任务在同属于一个物理核的两个逻辑核切换的开销，会比在不同物理核的两个逻辑核间切换的开销小很多。

2. Linux 的负载均衡策略通过 **层级化** 的方法解决了上述问题。

1. 下面首先介绍 Linux 在负载均衡中使用的两个数据结构：

1. **调度域是拥有相同特性的 CPU 核心的集合**，这些核心间可以进行负载均衡。
      2. 一个调度域保存一个或多个 **调度组**，调度组是一个调度域内 **进行负载均衡的整体单位**。

2. 下图展示了 Linux 在NUMA 架构且开启了超线程的情况下如何管理调度域的例子：

![image-20220729211707228](https://notebook.ricear.com/media/202207/2022-07-29_211722_5857510.7513526931048867.png)

1. 在系统中，Core 0 和 Core 1 实际上是由一个 **物理核** 分化而来的两个逻辑核，他们组成了一个 **逻辑 CPU 域**，该域中有两个调度组，分别对应于 Core 0 和 Core 1。
      2. 两个物理核组成了一个 **NUMA 节点**，对应于一个 **物理 CPU 域**，该域中同样有两个调度组，分别对应于次一级的逻辑 CPU 域管理的一个物理核。
      3. 同样地，两个物理 CPU 域组成了一个 **NUMA 域**，其两个调度组分别对应于次一级的物理 CPU 域管理的一个 NUMA 节点。

> 在本例中，NUMA 域就是系统中 **最顶级的调度域** 了，因此其调度组 **包含了系统中所有的 CPU 核心**。由于计算机架构在运行时不会改变，因此可以认为 **调度域与调度组是只读的**，每个 CPU 核心都为上述数据结构维护了一份 **只读的本地拷贝**。

3. Linux 通过 **自下而上** 的方式 **层级式** 地进行负载均衡，并且为了设计简单，**只允许出发负载均衡的 CPU 核心拉取其他 CPU 核心的任务到本地**。

> - 如果当前 CPU 核心触发负载均衡逻辑：
   >   - 首先在 **最底层调度域**（逻辑 CPU 域）内的调度组（逻辑核）间进行均衡。
   >   - 然后依次进入 **更高一级的调度域**（物理 CPU 域 / NUMA 域），并对其管理的调度组（物理核 / NUMA 节点）进行负载均衡。
   > - 由于在 **越高层级** 的调度域间进行负载均衡的 **开销越大**，所以 Linux 为不同层级的调度域设置了不同的 **负载均衡触发频率与阈值**（只有当两个调度组的负载相差超过一定阈值才会触发负载均衡），以此来 **减少负载均衡的开销**。

## 参考文献

1. 《现代操作系统：原理与实现》