tags:
- OS
- CPU Scheduling
第一课 Uniprocessor Scheduling
当今的现代操作系统都调度内核级的线程，但许多资料仍然使用如“作业调度”或“进程调度”这样的名词。在本阶段的内容中，不区分相关名词的具体含义。无论是作业调度、进程调度还是线程调度，都是指操作系统在不同时间段内分配CPU资源给不同任务的过程。
1.1 Scheduling
在OS中，调度(Scheduling) 是指管理和分配计算机处理器给不同进程的过程。调度通常分为：长程调度(Long-term scheduling)、中程调度(Medium-term scheduling)、短程调度(Short-term scheduling) 和 I/O调度(I/O scheduling)。
1.1.1 Long-Term Scheduling
长程调度，或称高级调度(high-level scheduling) 和 作业调度(job scheduling)，决定了哪些作业(jobs)进入系统（内存）并加入到就绪队列准备运行。涉及到进程从new state到ready state的转换。通常在批处理系统中使用，用于控制系统的负载和作业的流入速度。长程调度的主要目标是保证系统资源的合理利用，避免系统的过载。
我们使用的PC中，长程调度并不常见。作为用户，我们可以决定去运行哪个程序。有时候可能会有per-user的限制（比如 100 processes/user）。除了批处理，长程调度在服务器中也很常见。当服务器满载时，新加入的客户端可能会收到服务器的提示信息（比如游戏服务器的排队提醒）。
在Android等移动操作系统上，进程调度可能会非常激进。当系统资源紧张时，操作系统会优先保证前台应用的运行，而将后台进程杀掉以释放内存和CPU资源。这种机制被称为“杀后台”。
1.1.2 Mid-Term Scheduling
中程调度，或称中级调度(mid-level scheduling)，负责进程在内存和外存之间的调度，如换入和换出。这种调度用于内存管理，以便内存不足时将不活跃的进程暂时换出，从而腾出内存空间给其他进程使用。中程调度的主要目标是优化内存使用，提高系统的整体性能。
相比于长程调度和短程调度，中程调度的频率很低，因为I/O操作很费时间。甚至在有的操作系统中，当内存不足时会强制终止任务的执行。（Android）
1.1.3 Short-Term Scheduling
短程调度，或称低级调度(low-level scheduling) 和 CPU调度(CPU scheduling)。长程调度/中程调度可能很久才发生一次，单短程调度可是时时刻刻都在发生。短程调度就相当于是“我们现在要做什么？”。阻塞、运行、预备态都是在短程调度中发生的。在短程调度中，调度器(dispatcher)会使用一些调度算法管理选择哪个进程可以占用CPU。
在多任务操作系统中，（短程）调度器负责不断地将进程放在CPU中执行，以确保系统的高效运行。调度程序选择下一个要在CPU中运行的进程后，调度器就会执行相关的上下文切换，然后跳转到适当的内存位置执行相应的指令。
由调度器所消耗的时间成为调度延迟。这种延迟可能会变成系统的性能瓶颈，所以设计调度器时应当确保其时间复杂度尽可能的低。
1.1.4 I/O Scheduling
详见I/O系统。
1.2 Evaluation Criteria for Scheduling Algorithms
不同的CPU调度算法具有不同属性，一个特定算法的选择可能会对某一个或几个进程更有利。为了选择以应对特定情境的算法，我们需要考虑各个准则综合评估。这些准则包括：
- CPU使用率(CPU utilization)
CPU利用率是指CPU十几倍使用的事件百分比。对于一个实际系统，CPU利用率不宜太低，一般为40%（轻负载系统）到90%（重负载系统）。 - 吞吐量(Throughput)
吞吐量时系统一个单元时间内进程完成的数量。 - 周转事件(Turnaround time)
周转时间是进程从提交到完成的这段时间。周转时间是所有时间段之和，包括等待进入内存、就绪队列中的等待、CPU中执行和I/O执行。 - 响应事件(Responce time)
响应时间是指从提交请求到系统首次响应的时间(例如:当你进行键盘输入，从按下一个键到屏幕显示这个字符的时间)。对于交互式系统，低响应时间至关重要，因为它直接影响用户体验。调度策略应确保系统对用户请求的响应尽可能快。 - 等待事件(Waiting time)
等待时间是指一个进程在就绪队列中等待处理器分配所花费的时间。调度策略应尽量减少进程的等待时间，从而提高系统的整体性能。
- 公平性(Fairness)
公平性是指调度策略应确保所有进程得到公平的处理器时间，不应让某些进程长期得不到处理器资源。公平的调度策略可以防止饥饿现象(starvation)，即某些进程长时间等待却无法执行。
- 优先级(Priority)
某些系统中，进程可能具有不同的优先级。调度策略需要根据优先级分配处理器时间，确保高优先级进程能及时得到处理。这对于实时系统和需要紧急处理的任务尤为重要。 - 折中与权衡(Trade-offs)
在实际应用中，不同评估标准之间往往存在冲突。例如，优化周转时间可能会增加等待时间，或者提高吞吐量可能会降低公平性。因此，选择调度策略时需要在这些标准之间进行折中和权衡，以实现系统的最佳性能。
1.2.1 Process Behavior
在系统中运行的进程根据其行为模式可以被分为不同的类型。根据进程主要消耗CPU资源还是I/O资源，我们将进程分为CPU密集型和I/O密集型。此前，我们先明晰burst的概念。
1.2.1.1 CPU Burst and I/O Burst
CPU burst指的是进程在一段时间段内连续使用CPU。在这段时间里，进程主要执行使用CPU的计算任务，不进行I/O操作。
I/O burst就是进程在时间段内连续进程I/O操作，而不进行使用CPU的计算任务。
1.2.1.2 CPU Bound and I/O Bound
CPU密集型和I/O密集型进程的判断实际上就是通过CPU burst和I/O burst的相对时长判断的。CPU密集型进程的CPU burst时间较长，而I/O burst时间较短。而I/O密集型进程则相反。
由于I/O密集型进程因为所需要的CPU时间并不多，所以被称为短作业或短进程。类似的，CPU密集型进程也被称为长作业或长进程。
第二课 Scheduling Algorithms
2.1 First Come, First Serve
先来先服务算法是最简单的CPU调度算法。采用FCFS，OS的调度程序会按照进程进入就绪队列的先后顺序分配CPU时间。
若采用非抢占式(non-preemptive) 的先来先服务算法，每个进程会一直占用CPU知道执行结束或主动放弃，然后调度程序会选择就绪队列中的下一个进程继续执行。
因为FCFS可以通过FIFO队列的方式轻松实现，因而也称为FIFO算法。
2.1.1 Advantages of FCFS
- FCFS算法是最易于理解和实现的调度算法，这是它最大的优点。
- 此外，得益于先进先出的性质，FCFS算法是公平的。
- FCFS一般适用于批处理系统。
2.1.2 Disadvantages of FCFS
- 由于算法非常简单，没有优化策略，所以FCFS的效率不高。
- 等待时间和周转时间受进程顺序影响大，可能导致车队效应(convoy effect)。
- 此外，由于后来的进程往往需要等待前面所有进程的结束，这会导致靠后进程的饥饿。
（车队效应容易发生在IO密集型进程队列中。这类进程只用很短的时间在CPU上执行。如果有一个 CPU 密集型进程在队列的前面，它会占用 CPU 很长时间，导致后面的 I/O 密集型进程不得不等待。这会导致 CPU 和 I/O 设备的利用率降低，系统效率下降。）
2.2 Round-Robin Scheduling
RR调度算法是增加抢占的FCFS算法。它定义了一个较小的时间片(time slice) 或 时间量(time quantum) ，通常是10~100ns。将就绪队列作为循环队列，CPU调度器循环整个就绪队列，为每个进程分配不超过一个时间片的CPU。RR算法是专门为分时系统设计的，也是最常作为核心使用的调度算法。
2.2.1 Advantages of RR
- 简单、易于实现且对于就绪队列的每个进程都是公平的。
- CPU使用率高：若时间片大小合适，RR算法通常可以保持较高的CPU使用率。
2.2.2 Disadvantages of RR
- 低吞吐量：由于每个进程都要以相同的时间片循环共享CPU资源，因此可能会导致比FCFS更小的吞吐量(下同)。
- 高等待时间和高响应时间。
- 在进程调度过程中有上下文切换(Context switching)，当时间片设置的过小时，频繁的上下文切换会占用大量CPU资源。
2.2.3 Virtual Round-Robin
虚拟轮转(Virtual Round Robin, VRR)是传统轮转调度（Round Robin, RR）的改进版本。虚拟轮转调度的主要目的是解决传统轮转调度在处理I/O密集型进程时的效率问题。
在传统轮转调度中，每个进程都会被分配一个固定的时间片，当时间片用完时，进程会被切换到队列的末尾。然而，这种方法对I/O密集型进程不太友好，因为这些进程通常会在时间片用完之前就进入等待I/O操作的状态，导致它们频繁地被切换，增加了系统的开销。
虚拟轮转调度通过引入一个虚拟队列(auxiliary queue)来解决这个问题。当一个进程进入等待I/O操作的状态时，它会被移到虚拟队列中，而不是直接切换到主队列的末尾。当I/O操作完成后，进程会被重新放回主队列的适当位置，以便尽快获得CPU的使用权。
2.3 Shortest Job First Scheduling
最短优先调度算法将每个进程与下次CPU执行长度关联起来。当CPU空闲时，调度器会将CPU资源赋给最短CPU执行时间的进程。短作业优先算法可以是抢占式的，称为最短剩余时间优先(Shortest Remaining Time First)。通常情况下SJF特指非抢占式调度。
由于最短时间的进程总是先执行，所以系统的平均等待时间和平均周转时间总是最优的。但是最短优先算法不可避免的会导致长进程的饥饿。而且最短作业优先的策略很难实现，因为CPU无从开始时得知每个进程要使用多长的CPU时间，因此SJF是很难实现的。
2.3.1 Advantages of SJF
- SJF is an optimal algorithm, which uses the best way of CPU and I/O devices.
2.3.2 Disadvantages of SJF
- 算法很难实现。
- 在执行过程中到达的更短进程得不到及时的响应。
- 会导致长进程的饥饿。
2.4 Smallest Remaining Time
SRTF是最短作业优先的抢占式版。在这种算法下，最短剩余时间的进程总会先于其他进程执行。
2.4.1 Advantages
- 吞吐量大：短进程会被即时响应。
- 系统开销小：由于SRTF算法只在进程完成或添加新进程时才做出调度决策，因此系统的管理开销很小。
2.4.2 Disadvantages
- 算法很难实现。
- 会导致长进程的饥饿现象。
2.5 Highest Priority Scheduling
优先级调度算法会根据每个进程的优先级来分配CPU时间。在这种调度算法中，每个进程都会被赋予一个优先级，CPU总是将资源分配给优先级最高的进程。
- 优先数(Priority)：描述进程重要性和紧急程度的一个属性。
- 优先数(Priority number)：用于量化优先级的一个数值，一般而言，优先数越低，优先级越高。
- 优先级调度算法有抢占式(preemptive)和非抢占式(non-preemptive)版本。
2.5.1 Aging
相比于轮转调度算法，优先级调度算法显然不算是一个公平的算法，因为低优先级的进程往往需要忍受饥饿。但是我们可以通过老化的方法解决这个问题。
- 通常而言，系统会设置一个时间间隔。每经过一个时间间隔，系统就会随着时间的推移增加等待进程的优先级。
- 系统需要平衡优先级提升和实际需求，确保高优先级进程的响应时间不会因为频繁提升低优先级进程的优先级而收到太大影响。
2.5.2 Reverse Aging
除了动态提升进程的优先级外，还可以通过降低高优先级进程的优先级来防止饥饿问题。
- 时间片耗尽：当一个高优先级进程消耗完它被分配的时间片后，其优先级可能自动被降低。
- 资源占用检测：如果一个进程在一定时间内占用了过多CPU时间，系统可能会动态调整其优先级。
2.6 Highest Response Ratio Next，NRRN
在高响应比优先算法中，调度器需要计算就绪队列中所有进程的响应比(Response ratio)，并选择响应比最高的进程分配CPU时间。响应比的计算公式是：
S表示进程的预计服务时间（运行时间）。
我们可以看出，这种算法是对SJF算法的改进版，使得长进程经过一段时间的等待（W增加，RR变大）以可以获得CPU。HRRN算法综合等待时间和运行时间，防止长进程饥饿，提供较为公平的调度。通常情况下，该算法默认使用非抢占式。
2.7 Multilevel Queue, MLQ
多级队列调度算法将就绪队列中的不同进程按照类型划分成多个不同的队列中：
- 队列分类：按照进程的需求和行为特性，将进程分类到不同的队列中，例如按进程类型（交互式、批处理、系统级等）进行分类。
- 优先级设置：在MLQ调度中，可以将每个队列设置为不同的优先级，一般的优先级排序为：
- 调度策略：每个队列可以采用最适合其进程特性的调度策略。如，前台交互式进程通常采用RR策略，后台批处理进程则可能再用FCFS策略。
- 调度执行顺序：调度器首先会检查高优先级的队列是否有可运行的进程，若没有，调度器才会检查下一优先级的队列。
- 抢占和非抢占
2.7.1 Compatible Time-Sharing System: IBM 7094
2.8 Multilevel Feedback Queue, MLFQ
多级反馈队列调度算法综合了静态优先级和时间片轮转算法的特点，实现了动态调整进程优先级来优化CPU时间段分配。
- 进程队列：系统设置多个队列，每个队列具有不同的优先级。通常而言，优先级排序为
- 调度策略：每个队列均采用时间片轮转算法，队列的优先级越低，队列分配的时间片越长。
- 调度执行顺序：新就绪的进程首先进入最高优先级队列（
- 抢占和非抢占
Note：尽管多级队列调度算法和多级反馈队列调度算法都划分了很多队列对进程进行划分。但它们在进程调度上有着本质的区别。
- 在MLF中，进程一旦被分配到某个队列，就会在完成前一直待该队列中。这会必定的导致某些进程的饥饿。
- 在MLFQ中，进程可以在不同的队列间”移动“。因而，采用MLFQ的OS可以根据进程长短动态地调整进程在长进程队列还是短进程队列。克服了SJF不能预测进程长短的缺点。保持CPU不空闲的前提下实现了较短进程优先，所以MLFQ的效率相较于MLQ要高。
2.9 Garanteed Scheduling
Garanteed scheduling的调度算法不同于前面注重于效率的多中调度算法，这种算法旨在确保每个用户公平地获得相等的CPU时间。比如系统内有 n 个用户，那么每个用户将获得 1/n 的CPU时间。或者 m 个进程，每个进程获得 1/m 的CPU时间。这种算法可能不是最高效的，但是相对公平的。
为了实现Guaranteed Scheduling，系统需要跟踪每个用户或进程所用的CPU时间。具体来说，系统会计算每个进程的实际CPU时间与预期CPU时间之间的差异。如果某个进程的实际CPU时间少于预期CPU时间，系统会优先分配更多的CPU时间给该进程，以确保公平性。
2.10 Lottery
Lottery scheduling是一种随机化的调度算法。每个进程根据其优先级或需求在某种资源上获得一定数目的“彩票(lottery tickets)”。资源调度时，调度器会随机抽取一张彩票，持有该彩票的进程将获得资源。
在Lottery Scheduling中，假如某资源总彩票数量为 T，某个进程拥有 f 张该类型的彩票，那么这个进程获得该资源的概率大约为 f/T。当进程被创建或终止时，系统会调整彩票的数量，以确保资源分配的公平性。
2.11 Advanced Considerations in Scheduling
2.11.1 The Idel Task/Thread
当没有事情可做时，调度算法会调度什么呢？因为调度器并不能自己生成一个进程去运行，在这种情况下，调度器会加载idel task去运行。Idle Task 没有任何依赖关系（dependencies），即它不依赖于其他任务或资源来执行。由于无事可做的状态任何时候都可能发生，所以idel task不可以被阻塞，以确保随时都可以被加载。
在不同的系统里，idel task的实现可能是不同的，可以是重复地唤起调度器，也可能是做一些无意义的加法运算，或是执行一堆的NOP指令。当执行idle task时，CPU会被 halt/switch 到低功耗模式。它的主要目的是确保CPU始终有任务可执行，从而避免系统进入空闲状态。
这些无用功好像毫无意义，但是idel task还是有它的存在意义的：
- 防止了调度器无事可做，避免调度器返回状态异常。
- 提供了任务运行时间的会计信息，以便我们能够知道系统处于空闲状态的时长。
2.11.2 Priority Inversion
Priority Inversion 是一种调度问题，描述了一种高优先级进程等待低优先级进程释放资源的情形。当一个低优先级的任务持有一个高优先级任务所需的资源时，高优先级任务被迫等待，导致系统性能下降。这种情况通常发生在多任务操作系统中，尤其是在实时系统中。
想象这样一种情形，高优先级任务
2.11.2.1 Solution-1: Priority Inheritance
为了解决Priority Inversion问题，可以使用Priority Inheritance协议。当低优先级任务持有高优先级任务所需的资源时，低优先级任务会暂时继承高优先级任务的优先级，直到释放资源为止。这可以确保高优先级任务尽快获得所需资源，减少等待时间。
2.11.2.2 A Real-Life Example: Mars Pathfinder Rover
1997年，NASA的Mars Pathfinder探测器在火星上运行时，遇到了一个严重的问题：系统频繁重启，导致数据传输中断。这个问题的根源在于Priority Inversion。具体来说，火星车有这样三个任务：
- 低优先级任务：获取一个信号量，对information bus进行加锁。
- 中优先级任务：处理通信（communication）。
- 高优先级任务：需要使用information bus。
当低优先级任务加锁时，高优先级任务进入阻塞状态。这时，中优先级任务开始运行，并抢占了CPU资源，从而低优先级任务也被阻塞，同时并不释放信号量。由于中优先级任务一直运行，高优先级任务一直得不到锁，系统会认为高优先级任务运行错误（task failure）。
高优先级作业一直被阻塞会让系统认为发生了严重的死锁。为了尽快恢复高优先级作业的运行，系统会进行Armageddon的死锁解决方案，即reboot。这就意味着一些数据的丢失。
2.11.2.3 Solution-2: Priority Ceiling
和优先级继承的解决思路类似。优先级天花板会将为每个共享资源分配一个优先级天花板来防止低优先级任务阻塞高优先级任务。
2.12 Scheduling Algorithm Evaluation
第三课 Multiple-Processor Scheduling
当我们的视界迈入多处理器的时刻，我们的世界发生了巨变，同时，复杂度会迈上一个新的台阶。当前，我们可以考虑的多处理器系统主要有三类：
- Distributed System：服务器多采用的处理器架构，系统中的处理器通过网络连接。
- Functionally Speciallized：处理器的功能特化。一个CPU用于图像处理，另一个用于数据处理。
- Tightly Coupled：系统中的处理器共享内存和资源，通常通过高速总线连接。
本节课，我们聚焦于紧耦合型的系统，这也是当前个人PC上常见的多 die 多核心CPU的类型。
3.1 Intro to Multiple-Processor Scheduling
简单起见，一般认为每个处理器只有一个核心。本文部分内容作为补充介绍多 die 多核心 CPU。
在之前的讨论中，我们仅仅将讨论范围放在了单核心处理器(single-core processor) 的调度策略上面。然而，由于主频发展的瓶颈，要提高CPU的性能，我们需要增加CPU的核心数，即多核心处理器(multicore processor)。当下，多核心处理系统在大多数计算机上得到了广泛的应用，在服务器上，处理器的核心数甚至能够达到144核心（Intel Sierra Forest-SP）。
在单核系统中，所有的进行共享同一个处理单元，调度器只需要决定下一个要执行的进程是哪个。而在多核系统中，由于调度器需要在多个核心之间分配任务，调度复杂性大大增加。我们下面从三个方面举例其相比单处理器的复杂性：
- 并行性(Parallelism)：由于在单处理器系统中我们只有一个核心，所有进程必须串行执行，系统能够并发但没有并行。由于核心数的增加，多核系统能够在任务一占据核心0的同时任务一占据核心1同时执行。为系统带来了并行性。
- 负载均衡(Loading Balancing)：在单核心处理器上，CPU资源十分珍贵，我们想让处理器时时刻刻都保持高负荷的状态。在多核心处理器中，我们需要考虑负载均衡，即如何将任务均匀地分配给各个核心。如何保证每个核心都运行在最佳的状态才是我们要关心的。
3. 核心亲和性(Core Affinity)：在计算机组成的Memory hierarchy中，我们学习了Cache的分级。其中，每个核心都会对应一个L1 Cache和一个L2 Cache。这些缓冲中存储着最近在当前核心上运行过任务的数据和指令。如果进程频繁切换或混乱调度，就会造成每次核心的调度都会造成缓存失效，性能降低。
3.1.1 Granularity and Instructions Interval
在并行计算中，粒度(granularity)，或“谷粒大小”（grain size)，描述了并行计算中任务的规模大小。系统能够进行并行任务的规模越大，粒度就越大。细粒度(fine-grained) 的任务通常较小，可以均匀地分配到多个处理器或核心上运行。粗粒度(coarse-grained) 的任务较大，不易均匀分配任务，可能导致负载不均衡。所以细粒度的任务一般部署在同一台主机上，而粗粒度的任务可以部署到多处理器系统或分布式系统上。
指令间隔(Instruction Interval) 指的是处理器执行指令之间的时间间隔。这种时间间隔包含了指令之间可能存在的等待时间、访存时间和同步通信所用的时间等。
粒度大小和指令间隔大小息息相关。一般来说，粒度越大，指令间隔就越大。下面是几种系统，其中粒度和指令间隔逐步增大：
-
单处理器系统(Single Processor System)：
- 粒度：最小
- 指令间隔：通常较短，因单处理器执行所有任务，无需并行通信和同步。
-
功能特化的多处理器系统(Functionally Specialized Multiprocessor System)
- 粒度：小
- 指令间隔：适中，因特化处理器执行特定任务，但需要一些同步和通信。
-
多处理器系统(Multiprocessor System)
- 粒度：中等
- 指令间隔：适中，因多个处理器并行执行任务，需要更多的同步和通信。
-
功能特化的分布式系统(Functionally Specialized Distributed System)
- 粒度：较大
- 指令间隔：较大，因不同系统节点执行特化功能，需频繁通信和同步。
-
分布式系统(Distributed System)
- 粒度：最大
- 指令间隔：最大，因任务在不同节点分布，网络延迟和同步开销较大。
细粒度由于任务较小，同步和通信往往只局限在同一台主机上的不同核心上，同步通信的开销较低，因此细粒度系统的指令间隔较小。粗粒度系统由于任务较大，通信和同步的开销较大，所以指令间隔可能非常大。
3.1.3 Multi-Core Processor
3.1.3.1 CPU Manufacturing
多核CPU？多CPU？如果你为这两个名词所困扰，我们不妨先了解一下CPU是如何制造的。高纯度硅经过切割之后我们得到一个个晶圆(wafer)，晶圆经过光刻等制造出许多个相同的电路图案，每个图案切割后我们就得到了一个die(裸片)。而die功能越复杂（面积越大），die的良品率就会越低。即die越大，成本越高，但是性能好。
如果我们有一个48核心CPU，我们该如何权衡利弊？我们可以将48个核心集成到一个die上封装成单die多核心CPU；还可以将48个核心分别集成在4个die上，每个die对应12个核心封装成多die多核心CPU。在第二种方案上，我们不额外考虑外围电路和总线的封装细节。第二种方案显然成本更小，也有很多实用性，每个die就对应着我们的一个处理器(CPU)。这也是多处理器调度的单位。
3.1.3.2 What Multi-Scheduling Really Are?
了解了CPU如何制造，现在，你应该能明白多处理器调度的实质其实就是多核心调度。但是这些核心被封装到了不同的die中了。这样带来的问题就是die内数据的传输是会快于die之间的数据传输的，而且多个die还要考虑总线冲突的问题。
除此之外，在x86类型的系统上，L1和L2的cache是每个处理器一个的，而L3 cache是所有处理器共享的。当进程
3.1.4 Architectures are Everywhere
3.1.4.1 AMP
非对称多处理器(Asymmetric Multi-Processing)：在AMP中，处理器的职责不对称。通常有一个主处理器负责系统调度和IO操作，其他从处理器则仅负责执行分配给它们的任务。主处理器在整个系统中占据主导地位，所有进程调度和系统调用都由它处理，从处理器则不直接参与调度决策。
- 硬件架构简单，主从职责分明。
- 主处理器的性能可能成为瓶颈，扩展性不佳。
3.1.4.2 SMP
对称多处理器(Symmetric Multi-Processing)：在SMP中，每个处理器共享同一个主存、IO设备以及操作系统，并且它们具有对等的访问权限。每个处理器都有同样的权利参与任务调度，并执行相同的操作。由于所有处理器可以访问共享的资源，调度器的任务是将进程公平地分配给各个处理器，使得系统负载均衡。
- 处理器平等共享资源，简化了设计。
- 处理器之间需要共享内存和I/O总线，这可能会导致瓶颈。
现代操作系统大多采用SMP结构，因为SMP系统能够更好地利用多核处理器的并行计算能力，并且更适合现代通用计算环境中的高并发和负载均衡需求，比如Linux、Windows、macOS等。而AMP更多用于嵌入式、实时系统等特定场景中。
3.1.4.3 NUMA-Aware Scheduling
非一致性内存访问(Non-Uniform Memory Access) 是一种多处理器内存架构，用于优化多处理器系统中的内存访问效率。在NUMA架构中，系统中的多个CPU被划分成不同的节点（Node），根据CPU和主存的链接方式，每个node访问不同内存区域的速度并不一致。根据这种差异，我们说每个节点有自己的本地内存和资源。
内存、IO和CPU的链接方式使得每个节点的CPU可以快速访问本地内存和IO，但访问其他节点的内存或IO会有较高的延迟。
在NUMA系统上编写程序时，尽量将线程绑定到对应的CPU，并从该CPU的本地内存分配内存，以最大化性能。使用工具如numactl可以查看和设置NUMA相关的信息，优化程序的内存访问模式。
3.2 Multiprocessor Scheduling
3.2.1 Load Balancing
如果我们有4个处理器，如果其中一个处理器的利用率是 100% 而其他三个处理器无事可做，这种情况在我们看来是不理想的，因为所有任务都在一个处理器上运行可能会导致L1和L2 cache频繁的发生cache miss。
负载均衡就意味着系统的工作负载相对均衡，每个处理器的利用率都相当。相比于所有的处理器共享一个全局的任务队列，负载均衡在每个处理器有自己的私有任务队列的情况下更加重要。因为任务最初是分配到各个处理器的私有队列中的。如果某个处理器的队列过载，而另一个处理器的队列较空闲，那么负载就不再均衡。这时就需要通过负载均衡策略（如PUSH和PULL迁移）来重新分配任务，以确保所有处理器的负载均衡。
- PUSH migration：当某个处理器的任务队列过载，调度器会主动将任务从这个处理器上PUSH到其他负载较轻的处理器上。PUSH migration是一种主动的负载均衡策略，适用于避免个别处理器过载的问题。
- PULL migration：当某个处理器负载过轻，处理器就会从其他负载中的处理器那里PULL任务。PULL migration是一种被动的负载均衡策略，用于确保处理器不闲置，始终保持忙碌状态。
3.2.2 Processor Affinity
多处理器系统引入处理器亲和性策略使得进程尽可能在同一个处理器上连续运行。这可以最大限度地保持进程数据在处理器的本地缓存(Cache)中，减少由于进程迁移而导致的缓存未命中开销，以及减少处理器间的缓存一致性开销，从而提升系统性能。
- 硬亲和性(Hard Affinity)：规定进程只能在某个特定处理器上运行，调度器不会将其迁移到其他处理器。
- 软亲和性(Soft Affinity)：尽量使进程在某个处理器上运行，但在特定情况下，调度器可以将其迁移到其他处理器。
Linux中有关于两种处理器的亲和性的选项，我们可以使一个进程只在一个处理器上运行的同时让另一个进程尽量在另一个处理器上运行。
3.2.3 Conflicts Between Two Approaches
负载均衡调度是从全局视角进行的优化，期望进程能够自由地在不同的处理器之间迁移。然而这种频繁的迁移可能会导致缓存命中率直线下降的问题，降低缓存的利用效率。
另一方面，处理器亲和性注重局部的优化，期望进程尽可能地留在一个处理器上，以便提高缓存的命中率的同时也减少缓存的一致性问题。但这样可能带来处理器负载不均匀的问题。
Extension: Hyper Threading
超线程技术(Hyper-Threading Technology，HTT)是英特尔公司开发的一种技术，旨在提高处理器的并行处理能力。通过在每个物理处理器核心上创建多个逻辑处理器，超线程技术使得单个处理器能够同时处理多个线程，从而提高了处理器的利用率和整体性能。
超线程技术通过在一个物理核心上运行多个线程，可以在一个线程发生memory stall时，切换到另一个线程继续执行，从而减少处理器的空闲时间，提高处理器的利用率。这种技术在多任务处理和高并发应用中尤为有效，因为它能够更好地利用处理器资源，减少内存访问延迟对性能的影响。
我们知道CPU可以处理算数和逻辑运算，有了超线程技术，我们不再把CPU看作单一不可划分的资源。举个例子，我们有线程 1 和线程 2，我们通过超线程可以实现在线程 1 使用CPU算数运算的同时线程 2 使用逻辑运算。
第四课 Real-Time Scheduling
4.1 Real-Time Operating System
本课作为简单补充实时调度并对实时操作系统进行简短的介绍。简单来说，实时调度就是实时操作系统上进行的调度。那什么是实时系统？我们从它的实时性来源——墙上时钟时间来进行介绍。
4.1.1 Wall-Clock Time and Deadline Guarantee
对于实时操作系统而言，任务必须在严格的时间限制内完成。这个时间基准就是由墙上时钟时间来提供的。时间限制就意味着deadline，在实时系统中，对missing deadline没有任何容忍。如果任务没有在严格的截止时间前完成的话，就意味着系统故障。
常见的操作系统（如Windows、Linux、MacOS）并不能怎么匹配实时操作系统，主要原因在于它们对超时截止时间没有保证(guarantee)。这些操作系统设计的初衷是为了通用性和多任务处理，而不是为了满足严格的实时性要求。
在Windows上，即使你在任务管理器中将任务设置为实时优先级(Real-time priority)，系统也不保证任务能够在严格的时间限制内完成。这是因为Windows的调度机制并不是为硬实时任务设计的，系统中的其他因素（如内存管理、中断处理等）仍可能导致任务无法按时完成。
相比之下，实时操作系统(Real-Time Operating Systems, RTOS)专门设计用于满足实时性要求。它们具有更严格的调度机制和时间管理，以确保任务在规定的时间内完成。例如，RTOS会使用优先级调度、最早截止时间优先(EDF)等算法来确保任务按时完成，并处理硬实时任务的严格时间限制。
4.1.2 Tasks in RTOS
不同于前面调度中对“快”的追求，实时系统中安全和时效是最主要的（可预测性(Predictablity)）。最重要的任务必须尽早地完成，并且在相应的时间内完成。在实时系统中，对于不同的任务，我们有不同的解决方案。我们可以把实时任务分成这三种：
- 硬实时任务(Hard Real-Time Tasks)：硬实时对错过截止时间没有任何容忍度，任何延迟都会被视为系统失败。所以硬实时任务必须在严格的时间限制内完成，否则就会导致系统的故障。例如，对即将到来的导弹轨道进行计算拦截，即便延迟仅仅0.1秒钟，都可能相差数百米，这显然不是我们能够接受的。
- 固实时任务(Firm Real-Time Tasks)：固实时任务也需要在截止时间内完成，但如果偶尔错过截止时间，系统不会立即出现故障。然而，错过截止时间会影响系统的性能和可靠性。例如，在线交易系统中，偶尔的延迟可能不会导致系统崩溃，但会影响用户体验。
- 软实时任务(Soft Real-Time Tasks)：软实时任务在”时间限制“上的管理相对更松弛，允许在一定范围内的时间延迟。比如天气预报15分钟后下雨，但是现在已经下雨了，虽然带来的错误的信息，但是代价也许是我们能接受的。
实时任务要求实时的可预测性，这就是为什么Java这类解释型语言不适宜作为实时系统中的工作语言。更何况Java虚拟机在进行垃圾回收(Garbage Collection, GC)时，JVM会暂停JVM中的所有应用程序线程执行，直到垃圾回收完成。这肯定不符合RTOS对可预测性的要求。
4.1.3 Real-Time Failure
在实时系统中，实时失败(Real-Time Failure) 是指系统未能在规定的时间内完成任务，导致系统无法满足其时间约束。这种失败可能会导致严重的后果，特别是在硬实时系统中。
4.1.3.1 Hard Real-Time Failure
如果任务是硬实时的，我们有两种任务无法在截止时间内完成的场景：
- 调度太晚：例如，需要两小时完成的任务在距离截止时间还有一小时的时候才开始调度运行。
- 任务执行中断：调度开始运行时，任务是可以完成的。但是由于某种原因（如高优先级的任务被调入），完成任务变得不太可能。
第一种情况下，系统可能会拒绝任务的开始请求，或是永远也不会调度任务运行。因为没有必要在浪费CPU时间在一个不能按时完成的任务上面。第二种情况呢？有没有什么办法使得任务能按时完成的同时尽量减少对系统造成的影响？当然有，这就是我们为什么引入实时调度的原因。
4.2 Real-Time Scheduling
4.2.1 Properties of RTOS
实时系统在以下五个关键方面具有其独特性：
- 确定性(Determinism)
- 响应性(Responsiveness)
- 用户控制(User Control)
- 可靠性(Reliability)
- 故障软处理(Fail-Soft Operation)
4.2.1.1 Determinism
确定性预示着操作可预测，以确保任务能够在规定的时间内完成。完美的确定性(determinism)并不存在。在实时操作系统上，有时候我们只是希望得到一个保证，即不管怎么样，实时系统都能尽量确保任务按时完成。这种保证不一定是绝对的，但必须能够在大多数情况下满足系统的时间约束。
尽管我们在实时系统上追求这种determinism，但是这并不意味这non-determinism是不好的。一个典型的例子就是caching，通过一些优秀的置换算法，cache可以大大提升系统的性能。在一些嵌入式系统上，可能并不会配备cache，通过单一的主存结构，实际上你可以得到更好的determinism。因为任何任务访问主存的时间都是相近的。
4.2.1.2 Responsiveness
Responsiveness并不简单地指系统响应所需要的时间。determinism相当于告诉我们当任务发出请求之后，系统多久才能接收到请求，这需要规定在一个确切的值。而responsiveness指系统收到请求后开始响应事件(handle the event)的时间间隔。由于中断还可能被高优先级的任务中断嵌套，responsiveness并不仅仅涵盖从接收到请求到执行中断服务例程(interrupt handler)的时间，还要把执行到高优先级中断服务例程的时间加到一起。
4.2.1.3 User Control
Administrator control对于系统的影响是巨大的，毕竟每个系统最终的服务对象都是人嘛。在实时系统中，我们可以适当的增加系统的实时性（完全的硬实时系统），也可以减弱实时性的存在，如果操控得当，你得到的实时系统可能会类似于typical OS。
尽管我们的可操作空间很大，但由于操作对象是实时系统，有些地方是不能修改的。在实时系统中，我们可以使用以下两种策略：
- 不做修改，系统以原汁原味地方式提供操作。
- 根据需要做适当的修改：作为administrator，我们确实能在系统上做很多修改。比如调整任务的优先级、实时类型（硬实时、固实时、软实时），甚至选择系统的调度策略。因为操作系统并不能判断哪个任务是实时的，哪个是general purposes的。
4.2.1.4 Reliability & Fail-Soft
4.2.2 Scheduling is Central
不同于典型系统中调度影响性能不同，实时系统中，调度直接影响着系统的成与败。当你选择了一个很差的调度策略，系统可能会忽略掉高优先级任务的运行请求，系统出现故障，“保证”无法得到保证。通过这些方面的介绍，你可能也能感受到了任务调度在实时系统中的地位。
对于实时系统，我们要确保在规定时间内完成所有的硬实时任务，同时尽量完成尽可能多的软实时任务。不同调度算法的选择可能会导致系统中截然不同的任务完成情况。请记住，在实时系统中，保证重要任务的按时完成是首要任务，“效率”并不是我们首要考虑的。
在调度策略的选择上，所有的非抢占式调度算法都不能有效地发挥作用。一旦有硬实时任务未能按时完成，系统就会出现故障。同样，分时系统也不适用于实时系统，因为你不能让高优先级的任务等待低优先级任务的时间片完成。调度越是干脆利落，对实时于系统的稳定性和可靠性就越好。
4.2.3 Different Tasks
在实时系统中，我们可以将执行的任务分成下面这四种：
4.2.3.1 Fixed-Instance Tasks
望名生意，fixed-instance的任务只在固定的、预先定义的一段时间内运行。它们有固定的执行实例，通常用在那些特定时间执行操作的场景中，一般只会运行一次。比方说系统启动时初始化系统的任务、数据库的初始化等。
4.2.3.2 Periodic Tasks
这些任务在固定的周期内重复执行。它们在每个周期结束时被重新调度，广泛用于定期检查、传感器数据采集等场景。例如，每隔一秒钟读取一次传感器数据。周期性任务有两个相关的属性：
由此，我们可以得到下面的公式：
那我们只要选择合适的调度策略，保证系统内
4.2.3.3 Aperiodic Tasks
Aperiodic任务没有固定的执行周期，这些任务的触发是随机的，且没有最小的时间间隔限制。这就使得当一个aperiodic硬实时任务运行时，如果有更高优先级的硬实时任务到达，我们可能无法保证前一个aperiodic任务按时完成。
Aperiodic任务一般用于处理非周期性的事件，例如用户的请求或外部事件。任务的执行时间可能是不确定的，但仍需要在合理的时间范围内完成。如何调度这些任务，以及用什么顺序完成任务的调度，是值得我们思考的问题。
4.2.3.4 Sporadic Tasks
这些任务类似于aperiodic任务，但它们有最小的时间间隔限制(Minimum Inter-Arrival Time)。这意味着在任务之间必须保持一定的间隔时间（比如说
4.2.4 Estimation
在正式的进入实时调度策略的学习之前，我们还需要思考一个问题。之前的学习中，我们能发现在实时系统中"deadline"到处都是，那怎么才能知道任务大概需要多长时间执行呢？不管在之前的学习中还是生活中，预知未来一直都是一个很困难的事情。但是在实时系统中，我们需要这样的事件来保证系统的determinism。
4.2.4.1 Worst Case Scenario
在周期性的任务小节中，我们见过这个公式：
- 源代码分析(Source code analysis)
- 实证测试(Empirical testing)
4.2.4.2 Code Analysis
软件要运行，就要按照其源码一行一行地执行。为了得到
为了使得预测具有可行性，市面上有很多我们可以遵循的标准。例如，在 NASA/JPL 指南下：
- 代码中不可以出现递归和
goto语句； - 如果代码出现循环语句，循环边界必须是固定的；
- 在软件初始化之后，不允许再出现动态内存分配。
虽然这些指南提供了一个框架来确保代码的可预测性和稳定性，但它们并不是绝对的规约。如果你能够有效地控制动态内存分配所带来的时间开销，那么在代码的任何位置使用malloc进行内存动态分配是可行的。（使用binary buddy system）
源代码分析通常适用于代码量较小的任务，因为在这种情况下，分析和预测每条指令的执行时间相对简单。然而，当代码量变得庞大和复杂时，源代码分析的难度会显著增加。这就像估算从宿舍走到食堂的时间和从宿舍走到家里的时间，显然这两者的复杂度不在一个层面。在这种情况下，我们可能需要另一种预测方法——实证测试。
4.2.4.3 Empirical Observation
除了源代码分析，我们还有另一种更简单和直接的办法：把程序从头到尾地跑一遍，看看执行时间有多长。这种办法就是实证测试。实证测试的预测方法除了能够应对绝大多数情况下的任务外，还能够简单地预估一下系统的性能，同样的任务，通过比较在不同机器上运行的时长，我们就可以大致得出两个系统的性能。
通过一遍遍地模拟任务在系统内的运行时长，我们可以统计这些信息来设置一个最坏运行时间。利用统计到的模拟运行时间，我们可以使用置信区间(confidence interval)的概念来设置最坏运行时间。例如，当我们模拟的运行时间 99% 的置信区间是 [10s, 20s]，我们就可以设置最坏运行时间为 21s 或 22s。
第五课 Real-Time Scheduling Algorithms
前面我们简单地提到了实时系统和典型操作系统的不同，了解了一下为什么非抢占和分时的调度算法都不在适用于实时系统，我们补充了timeline的相关概念和调度思想。在本节课中，我们将开始介绍单处理器和多处理器上的实时调度算法。
5.1 Real-Time Scheduling in Uni-Processor
没有最优的调度策略，有的是相对于某个环境下最优的调度策略。
5.1.1 Earliest Deadline First(Optimal Algorithm)
EDF，最早截止时间优先算法，算得上是学生们最熟悉也是世界上最常被人类应用的算法。毕竟有句话是这样说的：“DDL是第一生产力”。学生们的想法是不管三七二十一，哪个作业最先截止，就先完成哪个作业。即无论任务的优先级如何，哪个任务离它的时间期限最近，就率先完成哪个任务。
如果一个任务正在执行的同时另一个更急迫的任务到了，那正在运行的任务就会被挂起以运行新的那个任务。这就意味着有的periodic任务可能被aperiodic/sporadic的任务给抢占掉（urgent call is coming），对于一些硬实时任务可能不是非常友好，因为有的软实时任务离deadline可能更近。
在未过载的系统中，我们有能力完成所有的任务，软实时硬实时并无大碍，只要完成所有的任务就好。但是在过载的系统中，有的硬实时任务就可能被更紧急的软实时任务抢占CPU，从而造成系统故障。尽管系统设计者在设计系统时需要避免过载(overloading)的发生，但是在现实中我们不能指望系统永远步发生故障。为了避免过载带来的系统故障，我们需要做一些改变。
5.1.1.1 Deadline Interchange
和我们之前提到过的优先级继承(priority inheritance)很像，为了避免软实时任务抢占硬实时任务的CPU，Deadline Interchange 允许在任务的截止时间之间进行交换，以优化任务的调度顺序，让优先级更高的硬实时任务优先进行调度。这种方法可以最大化系统资源的利用率的同时确保高优先级任务能够按时完成，减少系统过载带来的故障风险。
5.1.2 Least Slack Time First
Slack time is how long a task can wait before it must scheduled to meet a deadline.
执行剩余时间算法(LSTF)，是我们要学习的另一种实时调度算法。和EDF有些类似，只是将离比较的时间从
LSTF其实就是在EDF的基础上进行了微调，他们的缺点是相同的，都没有对优先级进行考虑。我们提到过，这可能会使一些硬实时任务miss its deadline，从而导致系统的故障。
5.1.3 Rate Monotonic Scheduling
Rate-monotonic调度引入了优先级的概念，主要用于周期性任务的调度。任务优先级的确定基于任务的周期长度：周期越短的任务，优先级越高。RMS的优先级一旦确立，在运行时不会再改变。RMS适用于周期性任务的调度，但是并不算是最优的算法(not optimal)，在
例如我们有一下三个任务，他们的
5.1.4 Deadline Monotonic Scheduling
这个算法是rate monotonic的变体，将deadline作为优先级的确定的依据。在DMS下，距离deadline最近的任务的优先级最高。
5.1.5 Aperiodic Server
由于EDF（Earliest Deadline First）算法是最优算法，因此在实现调度器时，我们希望尽量向EDF靠拢。我们之前提到过，EDF调度器无法区分任务是软实时还是硬实时，这可能导致系统内任务不能预期完成。一种解决方法是让非周期性任务和软实时任务的优先级永远低于硬实时或固实时任务的优先级，但这种做法可能会导致任务间抢占可能会变得更加频繁、平均任务完成时间的增加，这对于调度算法来说，可能并不是我们想要的结果。
5.1.5.1 Polling Server
为了简化调度并优化这种解决方案，在实时系统的理论中，我们使用Polling Server来解决这一问题。polling server相当于一个携有多个非周期性任务的“容器”，polling server本身是一个有着固定执行时间的周期性硬实时任务。它会在固定的时间间隔内检查是否有非周期性任务需要处理，并在需要时分配资源进行处理。这种方法可以有效地将非周期性任务与周期性任务结合起来，保证系统的响应性和稳定性。
Polling server是aperiodic server的一种实现方式（periodic version）。我们举个现实中的例子，polling server就相当于午休时间，一般可能是12：00-2：00。你可以在这两小时中做你想做的任何事。相当于polling server在运行时调度一些非周期性的任务。在polling server运行的时间内，非周期性的软实时任务会被调度运行。通过定期分配处理时间给非周期性任务和软实时任务，确保它们能够及时得到处理，同时不会影响硬实时任务的调度。这种方法在保证系统整体性能的同时，减少了非周期性任务和软实时任务的等待时间。
5.1.5.2 Multiple Server
我们还可以拥有多个server来服务各种各样类别的任务。相较于aperiodic server，multiple server可以进行更细粒度的任务管理。比如一个服务器处理硬实时任务，一个服务器处理非周期性任务等。
5.1.5.3 Variant 1: Deadline-Deferrable Server
DDS是对polling server的进阶。在polling server中，当期限内全部的非周期性任务执行完毕了，server就会将剩余的时间片丢掉，立即结束本次周期。这就相当于午休时间没事儿做了就去工作了一样。而DDS会保留剩余的时间，以便同周期未来的某一时刻使用。还是午休的类比，如果在午休时间内没有事情做，可以把这段时间留到以后使用，比如下午或晚上。DDS这种安排方式既不浪费时间，又能在需要时迅速处理紧急任务。但是这种保留的时间仅限于今天（同周期内）。
5.1.5.4 Variant 2: Deadline-Sporadic Server
比起polling server那样在一个周期内分配一大块空间的方式，DSS将这一大片时间分成多个小块(time chunks)，这样做有什么好处呢？我们以等公交为例，polling server相当于30分钟的前2分钟过去3趟公交车，DSS相当于每10分钟一趟公交。虽然平均下来两种方式都是10min/bus，但是第二种方式的公交车载人数往往更多。通过分散时间片，DSS能更均匀地分配资源和负载，避免资源的浪费和系统负载的突发。这类似于每10分钟来一趟公交，可以更均匀地分配乘客流量。
在实现上，DSS并不像公交车的例子那样严格地按照每趟10分钟的方式执行，而是相当于一种chunk credit的方式工作。具体来说，DSS 会为非周期性任务分配一个时间片信用额度。这些信用可以在任务需要时使用，而不是在固定时间间隔内强制执行。当一个非周期性任务到达时，如果DSS有足够的chunk credit，该任务会立即得到处理。如果credit unavailable，任务则会被延迟到下个周期。
5.2 Multi-Processor Real-Time Scheduling
又是时候从单处理器的世界中跳出来了，在本节中，我们介绍有关多核实时调度的相关知识。在本节里，我们先区分这两个概念：
- Task（任务）：这是需要完成的工作或操作的描述。一个任务可以是任何需要处理的事情，比如计算一个复杂的数学公式、处理一段音频数据，或者控制一个设备。任务本身定义了应该做什么以及如何做，但不包括具体的执行实例。
- Job（作业）：这是一个任务的具体实例。每次任务被执行时，都会生成一个作业。比如，如果一个任务是每分钟读取一次传感器数据，那么每次读取操作就是一个作业。作业可以有不同的执行时间、资源需求和截止日期（deadline）。
当我们的视角不再局限于单处理器，多处理器给我们带来了更好的性能。我们思考这几个问题：
- 抢占是否允许？
- 作业的迁移(migration)是否允许？
- 作业的并行化(parallelism)是否允许？
5.2.1 Preemptive is Needed
多处理器能够一次性允许多个作业，那么抢占的算法还需要么？或者说是抢占是否允许呢？从典型操作系统的单处理器调度中，我们就学习到optimal algorithm是需要抢占式的调度的，而且在实时系统中，没有抢占有可能会造成某些作业影响硬实时任务的执行，我们当然需要抢占。
5.2.2 Migration: Good or Bad?
作业迁移是指将一个正在执行的作业从一个CPU迁移到另一个CPU。我们提到过，作业的迁移就意味着cache misses，对于CPU dedication scheduling approach（作业1在固定CPU1上完成，作业2固定在CPU2上完成。如：partitioned scheduling），作业的迁移就是不允许的。然而，完全不允许作业的迁移就可能会使得某个作业因为CPUx缺少CPU时间而不能在deadline前完成（其他的CPUy和CPUz可能空闲）。
对任务队列的管理上，我们有global scheduling和partitioned scheduling。前者是指所有CPU共享同一个任务队列，后者指每个CPU都有自己的任务队列。对于migration，global scheduling为了能够实现更好的负载均衡，调度器可以动态地将任务分配给最空闲的处理器。Partitioned scheduling则不允许job migration，一旦任务分配到某个处理器，即使其他处理器空闲，也不能进行迁移。
这两种approach都会以不同的方式浪费相同的处理器。我们需要更好的方案。在调度的实现上，我们将两者进行结合诞生出另一种调度方式：semi-partitioned scheduling。在任务的初始分配上，任务首先被分配到特定的处理器的任务队列上，类似于 partitioned scheduling。然而，在某些处理器过载时，semi-partitioned scheduling又允许允许少量的任务迁移到其他处理器上执行，以实现负载均衡。这种approach即实现了负载均衡，又使得调度开销相应地降低。
5.2.3 Job Parallelism
作业并行化是指将一个作业分解成多个可以独立执行的部分，并让多个CPU同时处理这些部分，从而加速作业的完成过程。
5.2.4 P-Fair Scheduling Algorithm
第六课 Scheduling in Modern Computer Systems
6.1 Windows and Unix Scheduling(Single User vs. Multi-Users)
6.1.1 Tradition UNIX Scheduling
早期传统的UNIX调度有如System V R3和BSD 4.3，这时的系统对实时性并不支持。在后面版本SVR4才对一些实时性进行了支持。本小节中，我们所讨论的都是多级反馈调度系统，其中每个队列都使用轮转算法(Round Robin)进行时间片的切换。
传统的UNIX系统虽然有时间片的概念，但是时间片间隔非常长，原始版本的默认值长达1s（一般为100ms-300ms左右）。这就意味着如果进程没有在这1s内被阻塞或完成任务，那么这个进程就会被抢占。这这个时期，系统的优先级经由进程类型和之前的执行情况得出。
CPU的利用率可以经由下面的公式得出：
此外，进程的优先级可以由下面的公式得出：
那个时期的计算机很稀缺，没有人想要将宝贵的时间片让给其他人。所以 "nice" 实际上是给系统管理员使用的。nice值通常从-20到19之间调整，默认的初始值为0，但admin可以在初始时用 nice 命令在启动进程时设置 nice 值，也可以在运行时用 renice 命令让一个进程变得 nicer 一点。
在传统的UNIX系统里，一旦一个进程被分到某个进程优先级队列中去，系统会避免进程迁移到其他的队列中。系统会先满足自己所需要的，之后才会尽可能利用好剩下的资源。根据任务类型的不同，优先级由高到低的顺序分为：
- Swapper (move process to and from disk)
- Block I/O device control
- File manipulation
- Character I/O device control
- User processes
正如你所见，用户进程的优先级最低。然而，这种方式并不算最优，因为所有的I/O密集型进程运行速度较慢，但它们的优先级却高于用户进程。在I/O密集型进程进行I/O操作时，应将CPU让给CPU密集型进程。
6.1.2 Upgrading: SVR4
在System V Release 4版本的Unix操作系统中，由于引进了实时性，系统将最高的优先级给了实时进程，然后是内核，最后是用户进程。相比之前的系统，SVR4最大的不同是增加了更多的优先级，现在我们有160种不同的优先级，我们还把他们划分为三大类别。而且引入了抢占点。
6.1.3 FreeBSD
Berkeley Software Distribution是UNIX的一个变种，而FreeBSD是BSD的一个变种。它和SVR4很类似，相比SRV4，它的优先级更多，有256种。并且将进程划分为五个大类。SVR4并不支持多处理器，而在FreeBSD则实现了对多处理器的拓展支持。
FreeBSD通过一种交互性评分机制来判别一个线程是否是交互式线程。原理也很简单，如果一个线程经常地被阻塞(blocked)，那就说明这是一个交互式的线程。我们定义有一个最大的交互分
如果睡眠时间大于运行时间，那么交互分数就是：
6.1.3.1 Affinity and Load-Balancing
在前面我们已经学过了亲和性和负载均衡了。FreeBSD也有Push和Pull机制。
Pull: bit mask to indicate it's idle.
Push: twice per second tasks to equalize highest and lowest CPUs
6.1.4 Windows Scheduling
Windows使用基于优先级的抢占调度算法来调度线程。确保拥有最高级优先级的线程运行，而优先级又随着程序的执行发生变化，确保每个线程都能够获取CPU而避免饥饿问题。这个选择线程运行的程序在Windows中被称作 dispatcher。
如果高优先级的线程被unblocked，他就会抢占低优先级的线程。Windows有32种不同的优先级，其中包括regular(1-15)和实时类别(16-31)。优先级为0运行的是一个内存管理任务。Dispatcher在每种优先级中都维护一个队列。当没有任务运行的时候，系统的 Idle 进程就会运行。
Windows将这些任务划分为六类优先级，分别是：
- Realtime
- High
- Above Normal
- Normal (A process usually in this class)
- Below Normal
- Low
当进程的时间片到达，线程执行就会被中断。如果任务是实时的，那么它的优先级就会被降低。
当一个进程被阻塞时，其优先级确实会暂时提升，以便在阻塞事件完成后能够更快地恢复执行。这个优先级提升的幅度取决于阻塞事件的类型。例如，等待键盘输入的进程会获得比等待磁盘操作的进程更大的优先级提升。
此外，为了提供更好的体验，系统还会为运行在前台(foreground)的进程提供额外的优先级。
6.2 Linux Scheduling
Linux有两种调度模式：实时的和非实时的。即使你使用实时调度器，系统中仍然可以存有非实时线程被调度。Linux调度器根据不同的调度类(scheduling classes)来进行调度。Linux 2.6.23版本之前，根据优先级，Linux将系统分为以下三大类：
SCHED_FIFO: 先进先出的实时线程。SCHED_RR: 轮转的实时线程。SCHED_OTHER: 其他（非实时）的线程。（也叫普通调度类SCHED_NORMAL）
其中，每个类别中又有许多不同的优先级。与Windows中优先级越高，数字越高不同。在Linux中，数字越低，优先级越高。实时优先级的范围从[0-99]，其他优先级的范围从[100-139]。也就是说，仅当RR或FIFO队列中没有可调度线程时，SCHED_OTHER才会被调度。
在2.6.23版本后，根据优先级，主要的调度类有下面五种：
SCHED_FIFOSCHED_RRCFS: 取代了SCHED_OTHER，成为当前Linux的默认调度类。SCHED_BATCH: 用于批处理任务，尽量减少对交互任务的SCHED_IDLE: 最低优先级的任务，只有系统空闲时才会执行。
6.2.1 Real-Time Scheduler
6.2.1.1 Real-Time FIFO Scheduling
在FIFO类中，线程的调度有一些需要注意的规则。当以下其中一个条件被满足，系统就会中断当前正在运行的FIFO的线程：
- 更高优先级的FIFO线程准备好了。
- 当前FIFO线程被阻塞。
- 当前FIFO线程让出CPU。
如果相同优先级队列中两个线程同时准备好了，那么等待事件更长的线程就会被选中。
6.2.1.2 Real-Time RR Scheduling
RR类中的线程调度策略和FIFO一样，只不过多了时间片轮转调度。当时间片用完且这时线程还没有执行完毕。那么调度器就会中断当前线程并选择一个更高优先级或相同优先级的线程调度执行。如果此时的线程就是优先级最高的，那么就会有选择这个线程进行调度。
6.2.2 Non-Real-Time Scheduler
6.2.2.1 Backgrounds
在 Linux 2.4 和更早期的版本中，Linux内核使用传统的算法进行非实时调度，造成的结果是时间复杂度很高(O(n))。之后，在2.6.23版本之前，引入了被称为O(1)调度器的调度算法，因为执行时间是一个常数时间(O(1))。O(1)调度器更好的适配了SMP系统，加入了CPU亲和性和负载均衡。
但之后在2.6.23版本，CFS(Completely Fair Scheduler)代替了O(1)调度器。CFS旨在提供一种更加公平和高效的调度机制，通过红黑树数据结构来管理任务，确保每个任务都能公平地获得CPU时间片，从而提高系统的整体性能和响应速度。
在6.6版本之后，默认的调度器被换为EEVDF。
6.2.2.2 Problems with the Traditional Scheduler
Because the traditional scheduling algorithm is a linear time algorithm, the more processes the current system has, the worse the performance becomes. Therefore, with the traditional scheduler, you cannot effectively handle a very large number of processes.
Besides, it does not match with the SMP system and would incur a penalty due to its design:
- A single run queue.
我们之前提到过，每个CPU都有自己的run queue，这是为了CPU亲和性，提高cache的命中率。系统只维护一个run queue对于负载均衡当然是好事，但是cache就很容易被架空。 - A single run queue lock.
系统只有一个run queue lock，这就意味着只用一个mutex lock来保护对run queue的操作。当一个进程想要enqueueing或dequeueing run queue时，其他进程就只能等待。 - An inability to preempt running process.
当低优先级进程运行时，高优先级进程必须等待。并不支持优先级抢占。
6.2.2.3 The O(1) Scheduler
了解如上的传统调度器的问题，我们来学习一下O(1)调度器是如何解决这些问题的。采用O(1)调度器后，内核会为每个处理器（核心）分别维护一个prio_struct数据结构，记录着array中任务的数量、优先级位图和优先级队列。MAX_PRIO指的是最大的优先数，也就是139。
struct prio_array {
unsigned int nr_active; // numbers of tasks in the array
DECLARE_BITMAP(bitmap, MAX_PRIO+1); // priority bitmap, 0 for empty
struct list_head queue[MAX_PRIO]; // priority queues
};
我们知道，Linux中有140种不同的优先级，每个优先级都会维护一个任务队列。优先级位图中的一位bit表示该优先级队列中有任务存在。这样，我们在调度任务的时候就不用遍历整个queue了。
在O(1)调度器中，任务会被分配到两个不同的优先级数组中，active queues和expired queues。调度器会从active数组中选择下一个要运行的任务。当一个任务用完了其时间片，就被移动到expired数组中。当active数组中的所有任务都用完了时间片，调度器会交换active和expired数组（交换指针），这样expired数组中的任务就会重新变为active，并且可以再次被调度执行。
6.2.2.4 Completely Fair Scheduler
CFS调度器是自2.6.23版本之后的内核默认调度器，由 Ingo Molnár 编写，旨在提供公平高效的调度，但可惜它的时间复杂度是O(log n)。CFS通过虚拟运行时间(vruntime)来衡量每个任务的运行时间，确保每个任务都能公平地获得CPU时间。CFS使用红黑树来建模管理就绪队列，最左边的组代表着有最小虚拟运行时间的任务，即优先级最高。获取执行最左边的组的时间复杂度为O(Iog n)。
当任务的时间片用完或被抢占，这个任务就会重新插入就绪队列，并更新其vruntime。这时红黑树就需要进行re-balancing，以确保自平衡的特性。
CFS并不使用固定的时间片长度，而是采用了一个称为“目标延迟”（target latency）的概念。目标延迟就是一个time window，并期待所有的线程都能够在这个窗口内至少运行一次。也就是说，目标延迟越长，任务切换的频率就会越低（CPU的性能越好，目标延迟也会越短）。
6.2.2.5 The vruntime
vruntime，也就是virtual run time，是CFS跟踪任务执行时间的方式。从名字就能看来，vruntime并不等同于实际的运行时间，CFS会根据任务的优先级（nice）和最近的调度情况来调整虚拟运行时间。优先级较高的任务会有较小的虚拟运行时间，而优先级较低的任务会有较大的虚拟运行时间。
比方说，CFS有一个decay factor，最近调度过的任务其实际运行时间的权重会偏大，从而影响其虚拟运行时间。此外，nice值越大，vruntime也会偏离实际运行时间越大。一个nice值为0的线程的vruntime就等于实际的运行时间。
6.2.2.6 CFS: Group Scheduling
6.3 A Decade of Wasted Cores
在2016年，有研究人员发表了 The Linux Scheduler: a Decade of Wasted Cores。这篇文章由Jean-Pierre Lozi、Baptiste Lepers、Justin Funston、Fabien Gaud、Vivien Quéma和Alexandra Fedorova共同撰写，发表在EuroSys 2016的会议上（click here）。
在138次的测试中，研究人员发现这些bug导致了系统性能下降了13%到24%。那多核调度是如何造成如此幅度的系统性能下降的？文章中提到的四种问题，造成了同一种现象：即使系统中仍然存在有等待执行的线程，系统也并不调度这些现象，而是让核心长时间处在空闲状态。核心短时间没有相关线程调度是正常的，毕竟把线程从一个核心上push/pull到另一个核心需要时间。但是，要是线程无缘无故等待很长时间（几百毫秒），那将成为一个问题。
6.3.1 Load Balancing and Cache Misses
在有的系统里，每个核心会被分配一个run queue。如果一个核心上有一个低优先级的任务，而另一个核心上有三个高优先级队列运行，不难发现，高优先级的任务实际上运行的时间反而更短。为了使得调度更加的公平，Linux会周期性地检查这些队列，保证所有核心的负载均衡。这就是我们之前介绍过的负载均衡。
负载均衡意味着额外的性能支出，和一些对于核心而言重新学习的时间支出，负载均衡往往意味着low cache locality和non-uniform memory access，这些都需要代价。我举一个例子，当工厂中有5个人做着不一样的工作，为了使得工人们负载均衡，老板可以每隔一段时间查看一下这些工人负载的情况如何（老板也是一个核心）。老板巡查需要一定的开销，工人A一直做着工作A，而工作A完成了，工人A被调去帮助工人B，然而任务B是工人A之前没有接触过的，所以这就需要工人A先进行学习，再开始工作。
因此，内核将多个硬件有相互关系的核心进行统一管理，组成一个更大的单元/组，我们称之为scheduling domain。比方说如果四个核心共享一个L2 cache，那就将其组织成一个调度域。将任务在同一个scheduling domain中进行push/pull就减少了核心的“学习”成本。
6.3.2 Four Significant Bugs
6.3.2.1 The Group Imbalance Bug
我们将核心分组管理，然而，某个核心可能窃取其他核心的劳动成果。相当于三人组中总有摆烂的那个人。通过组内核心的平均负载来看，数据可能很漂亮，但是有可能某几个核心满负荷而剩下的核心处于空闲状态。“平均”具有误导性。
如何解决呢？我们评估组内最小负载作为我们的衡量指标，即干活最轻的那个核心负载如何决定整个小组的负荷情况。这种方法解决了运行时约13%的性能损失。
6.3.2.2 The Scheduling Group Construction Bug
Linux中我们用taskset命令让某个任务持久的在某个核心上运行，如果调度组并没有按照硬件的相近性进行组织，那么调度组的创建将没有意义。组织这种错误的调度组是因为所有调度组的构建都是从核心0的视角出发进行的。然而这种构建方法跟硬件的拓扑和相似性并无关系。
6.4.2.3 The Overload on Wakeup Bug
我们之前了解过处理器亲和性，但有时候过度亲和并不是一件好事。当一个现象在组1的某个核心上被阻塞，当它被其他线程唤醒时，由于处理器的亲和性，它可能还会在之前运行过的核心上运行，如果核心正忙呢？那就等待。这和我们经常出入一个理发店很类似，可能宁愿等2小时也不愿意去其他理发店里理发。
经过处理器亲和性可能减少cache misses，但是要是其他核心空闲，有等待的时间可能在其他核心上早已结束运行。
6.3.2.4 The Missing Scheduling Domains Bug
导致一个应用上的所有线程都在一个核心上运行。