Scheduling 2: Case Studies, Real Time, and Forward Progress

How to Handle Simultaneous Mix of Diff Types of Apps?

考虑交互式和高吞吐量应用的混合情况：

应该在服务器、工作站、平板电脑和手机上相同地安排应用程序集吗？

许多调度程序中编码的假设：

很难表征应用程序：

Multi-Level Feedback Scheduling

image-20240327130158168

利用过去行为的另一种方法（首次在CTSS中使用）

调整每个作业的优先级如下（细节有所不同）

结果近似于SRTF：

必须在队列之间进行调度

Scheduling Details

对策：用户行为可能破坏操作系统设计者的意图

奥赛罗程序的例子：

Case Study: Linux O(1) Scheduler-based linux 2.6

image-20240327140610196

基于优先级的调度器：共140个优先级，Linux2.6版本使用的这种调度算法，目前已经弃用这种方法，当前Linux系统采用的是CFS调度算法：

两个独立的优先级队列：“活动”和“已过期”

时间片取决于优先级-线性映射到时间片范围

image-20240327141437906

如上图所示，每个大的队列中都有所有优先级目前正在活跃的/休眠的进程，若当前Active queue中的时间用尽后，会交换队列，让之前等待的queue中的人物得以执行。

O(1) Scheduler Continued

启发式

实时任务

这种依赖于启发式规则的策略，只要稍加改动可能就会导致一系列的奇怪行为，因此Linux系统放弃了这种调度方法，目前在用的是CFS调度算法。

Multi-Core Scheduling

在算法上，多核调度并没有与单核调度有很大的区别

在实现上，拥有每个核心的调度数据结构很有帮助

亲和调度：一旦一个线程在一个CPU上调度，操作系统会尽量在同一个CPU上重新调度它

So, Does the OS Schedule Processes or Threads?

许多教科书使用“旧模型”——每个进程一个线程。

通常情况下实际上是：线程（例如，在Linux中）。内核调度的单位大多数情况下是线程。

需要注意的一点是：切换线程与切换进程会产生不同的成本：

然而，回顾一下：同时多线程: Simultaneous Multithreading （或“超线程“Hyperthreading”）

Recall：Spinlocks for multiprocessing

自旋锁实现：

int value = 0; // 空闲
Acquire() {
    while (test&set(&value)) {}; // 忙等待
}
Release() {
    value = 0; // 原子存储
}

自旋锁不会让调用线程进入睡眠状态 - 它只是忙等待:

每个 test&set() 都是一次写操作，这使得值在core的local cache之间来回跳动（使用了大量内存！）。

正如我们在第 7 讲中讨论的那样，额外的读操作消除了 ping-ponging 问题：

// test&test&set() 的实现：
Acquire() {
    do {
        while(value); // 等待可能会释放锁，除非value是空闲的（0），否则一直进行读取
    } while (test&set(&value)); // 如果获得锁则退出
}

ping-pong between core-local caches

在多核处理器上使用不断地进行test&set操作可能会导致内存带宽的浪费和性能下降的问题。这种情况发生的原因包括：

  1. 缓存一致性问题：当一个核心对共享变量进行test&set操作时，它会在自己的缓存中修改该变量的值。然后，其他核心可能会尝试读取该变量，但由于缓存中的值已经被修改，它们需要从内存中重新加载该变量的最新值。这会导致缓存行的无效化和重新加载，增加了内存带宽的使用。

  2. 总线竞争：频繁的test&set操作会导致多个核心之间竞争访问共享内存，从而增加了总线的负载和竞争。这可能会导致性能下降，并且在高负载情况下可能会产生瓶颈。

  3. 上下文切换开销：如果一个核心不断地尝试获取锁（或修改共享变量），但由于其他核心正在使用该锁，它不得不不断地进行上下文切换以等待锁的释放。这种上下文切换会带来额外的开销和延迟，降低了系统的整体性能。

为了避免这些问题，需要采取合适的同步机制和优化策略，例如减少对共享变量的访问频率、使用更高效的锁算法、减少锁的粒度，以及设计并发数据结构来减少对共享状态的依赖等。

Gang Scheduling and Parallel Applications

当多个线程在多核系统上协同工作时，尝试将它们一起调度

另一种方法：操作系统告知并行程序其线程在多少个处理器上调度（调度器激活）

Real-Time Scheduling（实时调度）

目标：性能的可预测性！

硬实时：用于时间关键的安全型系统

软实时：用于多媒体

image-20240328102957278

EDF Feasibility Testing

即使是EDF，如果任务太多的话E，DF也不起作用

对于 𝑛 个具有计算时间 𝐶 和截止期限 𝐷 的任务，如果存在一个可行的调度，则应满足以下条件： \([\sum_{i=1}^{n}{(C_i/D_i)}] <= 1\) 很明显，因为每个任务在给定周期Di内必须完成Ci次计算，如果所有的利用率加起来<=1，说明CPU有足够的资源可以调度他们（不考虑上下文切换的开销）；如果大于1，说明CPU无法兼顾所有的线程，无论怎么调度，总会有线程无法在DDL内完成本次计算。

Starvation

饥饿：线程在无限期的时间内无法取得进展

饥饿（这节课） ≠ 死锁（下一节课），因为在适当的情况下，饥饿可能会得到解决。死锁是饥饿的一种，但是饥饿并不总是死锁。

饥饿的原因：

让我们探讨可能遇到的问题类型以及如何避免它们…

problem1：Priority Inversion

我们之前探讨过的基于优先级队列的调度器：在优先级调度器中，始终运行具有最高优先级的线程。

但是，还存在更严重的问题，即优先级反转（priority inversion）：

image-20240328110054012

如上图所示，Job1刚开始在执行，并且已经获得了一把锁，但是此时有更高优先级的Job2和Job3到来，Job3需要获取Job1的锁，但是发现无法获得，因此他会休眠，之后由Job2接替：

One Solution: Priority Donation/Inheritance

调度器实现优先级继承机制以防止优先级反转。作业1可以继承作业3的优先级，以继续运行释放锁，这意味着当作业1持有锁时，它继承作业3的优先级，以防止其他低优先级任务抢占它。一旦作业1释放锁，它恢复其原始优先级，下面是具体步骤：

  1. 优先级捐赠：
    • 当作业3（高优先级任务）需要运行但被阻塞时，因为作业1（低优先级任务）持有锁，它可以暂时将其优先级捐赠给作业1。这意味着作业1将使用作业3的优先级运行，直到它释放锁。
  2. 关键部分执行：
    • 作业1现在以作业3的更高优先级运行，可以及时执行其关键部分。一旦完成关键部分，它释放锁。
  3. 调度器处理：
    • 调度器在检测到作业1释放锁时，可以重新评估所有等待任务的优先级。由于作业3现在由于优先级捐赠而

通过实施这些机制，调度器可以确保高优先级任务（如作业3）不会被持有锁的低优先级任务不必要地延迟，从而提高系统响应性，并避免优先级反转问题。

Cause for Starvation: Priorities?

SRTF和MLFQ调度算法都会有饥饿问题，本质上是因为定义了优先级，高优先级的永远会被优先执行。

调度中的饥饿问题确实可能是由优先级引起的。通常在调度中遵循的策略是优先考虑某些作业，这可能会导致非优先考虑的作业被饿死，特别是在优先考虑的作业不断入队的情况下，会抢占低优先级作业的执行。

然而，优先级本身并不是饥饿的根本原因。优先级只是实现更广泛目标的手段，例如在普通硬件上有效地服务混合的CPU密集型、I/O密集型和交互型作业。

调度的最终目标是确保资源分配的公平性和效率，考虑到不同类型作业的需求：

  1. I/O密集型作业：这些作业需要CPU时间来发出I/O操作，然后等待这些操作完成（例如从或写入慢速存储设备）。对这些作业分配足够的CPU时间是至关重要的，以便它们能够在不受过度延迟的情况下取得进展。

  2. 交互式作业：这些作业涉及人类交互，并需要及时响应。它们还需要CPU时间来处理输入并回应用户，即使它们可能花费大部分时间等待用户输入。确保交互式作业的及时响应性可以增强用户体验。

  3. CPU密集型作业：这些作业主要消耗CPU资源，可能不太依赖于I/O操作或用户交互。它们需要持续的CPU执行时间来高效完成任务。

为了减轻饥饿并有效地实现这些目标，调度策略应旨在在不同类型作业之间平衡CPU资源的分配。这可能涉及根据作业特性动态调整优先级、实现公平排队机制，或者采用多级反馈队列等技术，以在防止任何单一类型垄断资源的同时，为每种类型的作业提供足够的CPU时间。

Key Idea: Proportional-Share Scheduling

background

我们迄今所研究的策略是：

相反，我们可以按比例分享CPU

比如我们之前讲到的Lottery Scheduling。给定一组作业（即混合），为每个作业提供一定比例的资源份额，例如，为作业A分配CPU的50%，作业B分配30%，作业C分配20%。

但是即使两个运行时间相同的作业A和B，因此他们会被各分配50%的票，但是根据实验研究，当作业长度变大时，反而不公平概率会递增：

image-20240329101133915

因此这种方法也是存在不公平性的。即使作业A和B的长度相同，并且它们各自被分配了相同比例的票据，但实际上随着作业长度的增加，不公平性递增的原因可能如下：

  1. 作业完成时间不同：即使两个作业被分配了相同比例的票据，但是实际上它们的执行时间可能会有所不同。在相同的时间片内，如果作业A和B完成的工作量不同，那么在整个运行过程中，完成工作量较多的作业将获得更多的CPU时间，从而导致不公平性。
  2. 调度器的干预：即使CPU每次获取到任何一方的票的概率都是50%，但是调度器可能会有一些策略来调整实际的运行情况。例如，如果调度器更倾向于执行某个作业，或者某个作业具有更高的优先级，那么它在被选择执行的频率就会更高，导致不公平性。
  3. 竞争环境：在实际运行中，作业之间可能会存在其他资源竞争，如内存访问、I/O操作等。这些因素可能会影响作业的执行速度，进而导致不公平性的增加。

综上所述，尽管理论上每个作业都应该获得相同比例的CPU时间，但实际上由于多种因素的影响，作业长度增加可能会导致不公平性递增。这也说明了调度算法设计中需要考虑到实际情况的复杂性，并采取相应的措施来保证公平性和效率。

Stride Scheduling

为了实现比例份额调度而不借助随机性，并克服“小数法则”问题，可以采用以下方法：

通过这种方法，可以实现比例份额调度，确保不同作业按照其票数的比例获得CPU时间，并且不会依赖于随机性。同时，低步幅的作业将更频繁地运行，从而实现了公平性。

Linux Completely Fair Scheduler (CFS)

目标：每个进程获得大体相同的CPU Quantum数量（虚拟运行时间，在每个线程权重相同时，每个CPU Quantum代表相同的实际运行时间）。

一般来说，真实硬件无法完全实现这一目标。

ideas

基本思想：跟踪每个线程的CPU Quantum数量，并调度线程以匹配平均执行速率。 调度决策：

使用类似堆的调度队列…

睡眠线程不会增加它们的CPU时间，因此当它们再次唤醒时会得到提升…

Linux CFS: Responsiveness/Starvation Freedom

除了公平性外，我们还希望低响应时间和避免饥饿。

约束1：目标延迟

目标延迟：20毫秒，4个进程

目标延迟：20毫秒，200个进程

Linux CFS: Throughput

目标：吞吐量

约束2：最小粒度

Aside: Priority in Unix – Being Nice

20世纪60年代和70年代的工业操作系统给予了优先级，以执行所需的使用策略。

“nice”值范围从-20到19，这对应了Linux2.4版本之前的O(1)调度器中，用户有40个优先级的设定：

调度程序使较高nice值（优先级较低）的任务睡眠更多…

这个想法如何转化到CFS（完全公平调度）？

Linux CFS: Proportional Shares

如果我们想在CFS中给一些线程更多的CPU时间，而给其他线程较少的CPU时间（比例份额）?

使用权重！关键思想：为每个进程I分配一个权重wi来计算切换量Qi

image-20240329103134692

重新利用nice值来反映份额，而不是优先级

因此，我们使用“虚拟运行时间”而不是CPU时间来计算CFS中的相对优先级和切换量。我们的调度目标仍然是每个线程大致得到相同的CPU Quantum数量（虚拟运行时间），但是每个虚拟运行时间代表的实际物理运行时间是不同的，即代表的实际运行速率不同，如此一来，我们就实现了不同比例的CPU分配。绝妙！

Linux CFS: Proportional Shares

image-20240329103405330

跟踪线程的虚拟运行时间而不是实际的物理运行时间

调度器的决策基于虚拟CPU时间，因为基于上述的份额机制，nice值不同的线程会被分配到代表不同实际运行时间的CPU Quantum，但是我们的调度是基于

使用红黑树来保存所有可运行的进程，按照vruntime变量排序

Linux Completely Fair Scheduler (CFS) summary

Linux系统现在采用的CFS调度算法（Completeness Fairness Scheduling），核心思想保证每个线程都得到大致相同的CPU Quantum（可以认为是虚拟运行时间 ）数量，采用红黑树管理当前的调度队列，在队列首的一定是当前得到CPU Quantum数量最少的。O(1)调度器中所有复杂的启发式规则都被这个虚拟调度时间的思想所取代，太妙了。

注意这里我们用了CPU Quantum数量这个概念，每个CPU Quantum代表了一定长度的执行时间，至于为什么没有用具体时间，下面讲到比例份额的时候就明白了，在此基础上，加入了以下机制，从而形成了了CFS算法：

  1. 并在此基础上添加机制（RR调度、规定最小时间片），从而在一定程度上兼顾了响应时间和吞吐量，因为频繁的上下文切换会导致吞吐量降低。
    • 比如说，我们设定Target Latency=20ms，一共有4个线程，那么在没有权重的情况下，20ms的CPU时间会平均分给4个线程，即每个线程的CPU Quantum都是4ms。
  2. 在上述基础上加入了优先级的支持，高优先级的线程会得到更多的执行机会，但每次执行的时间会少；低优先级的线程的执行机会较少，但是每次的执行时间较长。因此线程之间的总CPU Quantum数量总是相同的。

到此，CFS算法的虚拟运行时间=物理运行时间，之后，我们加入了权重思想，那么虚拟运行时间代表的实际物理运行时间就不同了，权重高的线程，一个Vruntime Quantum意味着更多物理执行时间，权重低的线程，一个Vrumtime quantum意味着更少的物理执行时间：

  1. 支持按照比例分配CPU时间，在上面的描述中，我们认为每个线程得到的CPU Quantum数量都是相同的，这时我们重用nice值为每个线程分配权重（nice值越高，得到的权重越低），之后根据每个线程的权重值的比例，为其分配CPU Quantum值，即每次执行实际上会执行多少时间。
  2. CFS的核心调度思想仍然是让每个线程可以得到大致相同的CPU Quantum-虚拟运行时间单位，但是实际上优先级高的线程会得到更多的实际运行时间。

Conclusion

How to Choosing the Right Scheduler

image-20240329102132508

A Final Word On Scheduling

image-20240329104521734

调度策略和公平性的细节真正重要的时候是在资源不足时。当资源不足以满足所有任务的需求时，如何合理地分配资源就显得尤为重要。

什么时候应该购买更快的计算机呢？或者更快的网络链接，或者扩建道路等等。

这条曲线的一个有趣推论是：

Summary (1 of 2)

调度目标：

轮转调度（Round-Robin Scheduling）：

最短作业优先（SJF）/剩余时间最短优先（SRTF）：

多级反馈调度（Multi-Level Feedback Scheduling）：

实时调度器（如EDF）：

抽奖调度（Lottery Scheduling）：

Linux CFS调度器：CPU的公平份额