Operating Systems Notes 04: Process and Thread Scheduling

1. 进程/线程调度问题分析#

1.1 When and How (调度时机与原因)#

调度这件事儿什么时候做？做的理由有哪些？#

调度时机 (When):

操作系统需要在特定事件发生时决定哪个进程接下来应该占用CPU。这些时机主要包括：

1. 进程创建 (Process Creation): 当一个新进程被创建时 (例如，通过fork()系统调用) ，需要决定是运行父进程还是子进程，或者其他进程。
2. 进程终止 (Process Termination): 当一个进程执行完毕或被终止时 (例如，调用exit()) ，它占用的CPU必须分配给其他就绪的进程。
3. 进程阻塞 (Process Blocking): 当一个进程因等待某个事件 (如I/O操作完成、等待信号量、等待用户输入等) 而无法继续执行时，它会进入阻塞状态，此时调度器需要选择另一个进程来运行。
4. I/O中断发生 (I/O Interrupt): 当一个I/O操作完成，产生中断时，原先等待该I/O的进程可能会从阻塞态变为就绪态。这时，调度器可能需要重新评估，决定是继续运行当前进程，还是切换到刚刚变为就绪的、可能优先级更高的进程。
5. 时钟中断发生 (Clock Interrupt): 在分时系统中，为了防止某个进程长时间独占CPU，操作系统会设置一个定时器。当定时器中断发生时，当前运行进程的时间片 (Time Slice/Quantum) 可能已用完，调度器会介入，决定是继续运行该进程 (如果时间片未用完或没有其他就绪进程) ，还是切换到另一个就绪进程 (抢占式调度) 。

调度的理由 (Why):

调度的根本目的是有效、公平地管理和分配有限的CPU资源给多个并发执行的进程。具体理由包括：

1. 提高CPU利用率: 尽量让CPU保持忙碌状态，减少空闲时间。当一个进程等待I/O时，可以让其他就绪进程使用CPU。
2. 提高系统吞吐量 (Throughput): 单位时间内完成的进程数量。好的调度算法可以在满足其他目标的同时，尽可能多地完成任务。
3. 减少周转时间 (Turnaround Time): 指一个进程从提交到完成所花费的总时间 (等待进入内存、在就绪队列等待、CPU执行、I/O执行的总和) 。
4. 减少等待时间 (Waiting Time): 指进程在就绪队列中等待CPU所花费的总时间。
5. 减少响应时间 (Response Time): 对于交互式系统尤其重要，指从用户发出请求到系统首次产生响应 (而非完成任务) 所花费的时间。
6. 确保公平性 (Fairness): 保证每个进程都能获得合理的CPU时间份额，防止某些进程被饿死 (Starvation) 。
7. 满足实时性要求 (Real-time Constraints): 对于实时系统，调度必须保证关键任务在它们的截止时间 (Deadline) 之前完成。

如果没有可被调度的进程，系统做什么呢？#

如果当前没有用户进程或系统核心任务进程处于就绪状态 (Ready State) ，CPU不能完全停止。操作系统通常会执行一个特殊的空闲进程 (Idle Process) 或称为系统空闲任务 (System Idle Task)。

• 作用: 这个进程拥有最低的优先级。当没有其他任何事情可做时，调度器就会选择它来运行。
• 行为:
  • 它通常执行一个无限循环。
  • 在这个循环中，它可以执行一些低优先级的系统维护任务。
  • 更重要的是，在许多架构上 (如x86) ，它可以执行一个特殊的指令 (如HLT - Halt) ，使CPU进入低功耗状态，直到下一个中断 (如时钟中断、I/O中断) 唤醒CPU。这有助于节能和降低温度。
• 目的: 确保CPU总是有事可做 (即使是“等待”) ，并提供一个合法的状态供调度器切换，同时优化能源使用。

上下文切换的过程？有哪些开销？#

上下文切换 (Context Switch) 是指操作系统保存当前正在运行进程的状态 (上下文) ，并加载另一个进程的状态，以便让后者开始或继续运行的过程。这是实现多任务处理的基础。

过程:

1. 中断/系统调用触发: 调度发生 (如时间片用完、进程阻塞等) 。
2. 保存当前进程上下文:
   • 保存程序计数器 (Program Counter, PC) 和其他CPU寄存器 (通用寄存器、状态寄存器等) 的值。这些值通常保存在该进程的进程控制块 (Process Control Block, PCB) 中。
   • 保存当前进程的栈指针。
   • 更新进程状态 (例如，从 “Running” 变为 “Ready” 或 “Blocked”) 。
   • 可能需要保存内存管理相关信息 (如页表基址寄存器) 。
3. 执行调度算法: 操作系统调度器代码运行，根据调度策略选择下一个要运行的进程。
4. 加载新进程上下文:
   • 从选定进程的PCB中恢复其状态。
   • 加载新进程的程序计数器和CPU寄存器。
   • 恢复新进程的栈指针。
   • 更新新进程的状态 (通常是从 “Ready” 变为 “Running”) 。
   • 恢复内存管理信息 (可能需要刷新TLB - Translation Lookaside Buffer) 。
5. 跳转执行: CPU跳转到新进程被中断时的下一条指令地址 (或其入口点，如果是首次运行) 开始执行。

开销:

上下文切换本身并不执行任何有用的用户工作，它是一种纯粹的开销 (Overhead)。开销主要包括：

1. 直接开销 (Direct Costs):

   • 保存和加载寄存器: CPU需要时间来读写寄存器和PCB。
   • 执行调度器代码: 选择下一个进程也需要CPU时间。
   • 更新PCB和其他数据结构: 维护进程队列等操作需要时间。
   • MMU操作: 可能需要加载新的页表基址，这可能导致TLB被刷新 (TLB flush) ，增加后续内存访问的延迟。

2. 间接开销 (Indirect Costs):

   • 缓存污染 (Cache Pollution): 当新进程开始运行时，CPU缓存 (L1, L2, L3 Cache) 中很可能包含的是前一个进程的数据和指令。新进程运行时会发生大量的缓存未命中 (Cache Miss) ，需要从内存中重新加载数据，这会显著降低执行速度，直到新进程的“工作集” (Working Set) 被加载到缓存中。这是上下文切换最主要的性能影响之一。
   • CPU流水线冲刷: 切换可能导致CPU的指令流水线被清空和重建。

最佳实践: 频繁的上下文切换会显著降低系统整体性能。因此，调度算法和系统设计 (如时间片大小的选择) 需要在响应时间和系统吞吐量/效率之间找到平衡。

关于调度算法，我们都关心什么？#

我们在评估和选择调度算法时，主要关心以下几个性能指标 (Performance Metrics) 或目标 (Goals)：

• CPU 利用率 (CPU Utilization): CPU处于忙碌状态的时间百分比。越高越好，但100%可能意味着没有冗余，响应性可能变差。
• 系统吞吐量 (Throughput): 单位时间内完成的进程 (或作业) 数量。越高越好。
• 周转时间 (Turnaround Time): 从进程提交到完成的总时间。越短越好 (平均周转时间、最差周转时间) 。
• 等待时间 (Waiting Time): 进程在就绪队列中等待CPU的总时间。越短越好 (平均等待时间、最差等待时间) 。
• 响应时间 (Response Time): 从提交请求到产生第一个响应的时间 (交互式系统关键) 。越短且越稳定越好。
• 公平性 (Fairness): 每个进程获得合理的CPU份额，防止饿死。
• 可预测性 (Predictability): 对于实时系统，执行时间的可预测性比平均性能更重要。
• 满足截止时间 (Meeting Deadlines): 对于实时系统，这是硬性或软性要求。
• 优先级处理 (Priority Handling): 系统能否有效处理不同优先级的进程。
• 资源平衡 (Resource Balance): 尽量保持所有资源 (CPU, I/O设备) 都处于忙碌状态。

不同类型的操作系统都适用同一种调度算法吗？#

不适用。 不同类型的操作系统有着不同的设计目标和用户需求，因此需要采用不同的调度策略。

• 批处理系统 (Batch Systems):
  • 目标：最大化吞吐量和CPU利用率，减少平均周转时间。用户通常不直接与系统交互。
  • 适用算法：先来先服务 (FCFS)、最短作业优先 (SJF)、最高响应比优先 (HRRN)。公平性和响应时间相对不重要。
• 交互式系统 (Interactive Systems / Time-Sharing Systems):
  • 目标：最小化响应时间，提供良好的用户体验，兼顾公平性。
  • 适用算法：轮转法 (Round Robin, RR)、优先级调度、多级队列调度 (Multi-level Queue)、多级反馈队列调度 (Multi-level Feedback Queue, MLFQ)。
• 实时系统 (Real-Time Systems, RTOS):
  • 目标：满足任务的截止时间要求，可预测性至关重要。分为硬实时 (必须满足) 和软实时 (尽量满足) 。
  • 适用算法：速率单调调度 (Rate Monotonic Scheduling, RMS - 用于静态优先级)、最早截止时间优先 (Earliest Deadline First, EDF - 用于动态优先级)、优先级调度 (配合精确的优先级分配) 。

对于一个调度算法，应该追求什么样的目标？#

一个调度算法应该追求的目标组合取决于具体的系统类型和应用场景。通常需要在多个 (有时是相互冲突的) 目标之间进行权衡 (Trade-off)。

• 通用目标 (All Systems):
  • 公平性: 防止饿死。
  • 策略强制: 确保系统设定的策略 (如优先级) 得到执行。
  • 平衡: 保持系统的各个部分都处于活动状态 (例如，CPU密集型和I/O密集型进程交替运行) 。
• 批处理系统目标:
  • 高吞吐量
  • 低周转时间
  • 高CPU利用率
• 交互式系统目标:
  • 快速响应时间
  • 低响应时间方差 (稳定性)
  • 满足用户期望 (感觉流畅)
• 实时系统目标:
  • 满足截止时间
  • 高可预测性

最佳实践: 没有“万能”的调度算法。选择或设计算法时，必须明确系统的主要目标，并接受在其他方面可能存在的不足。例如，追求极低响应时间可能会牺牲一些吞吐量。

选进程时都考虑了哪些点？单一因素还是多因素？#

选择下一个要运行的进程时，调度算法可能考虑单一因素或多个因素。

• 单一因素:

  • FCFS: 只考虑进程到达就绪队列的时间。
  • SJF (非抢占式): 只考虑预估的下一个CPU脉冲 (burst) 长度。
  • 简单优先级调度: 只考虑静态分配的优先级。

• 多因素: 现代操作系统和更复杂的调度算法通常是多因素的。

  • 优先级调度 (带老化): 考虑静态优先级，但也考虑进程等待时间 (老化机制，aging) ，提高等待过久进程的优先级以防饿死。
  • RR: 考虑到达时间和时间片轮转。
  • MLFQ: 考虑优先级、进程行为 (CPU密集型 vs I/O密集型) 、等待时间等，动态调整进程在不同队列间的移动。
  • HRRN: 考虑等待时间 (W) 和服务时间/脉冲长度 (S)，计算响应比 (W+S)/S。
  • Linux CFS: 考虑进程的虚拟运行时间 (virtual runtime)，旨在给每个进程公平的CPU时间比例。它间接考虑了进程的等待时间和已运行时间。
  • Windows调度: 考虑基础优先级、动态优先级提升 (如完成I/O、处于前台窗口) 、时间片消耗情况等。

结论: 简单算法可能只关注单一因素，但为了在复杂环境中平衡多个目标 (如响应时间、公平性、吞吐量) ，现代通用操作系统广泛使用多因素调度算法。

1.2 How (调度算法详解)#

适用批处理系统的调度算法有哪些？#

主要目标是效率 (吞吐量、CPU利用率) 和整体完成时间 (周转时间) 。

1. 先来先服务 (First-Come, First-Served, FCFS):
   • 实现：按进程到达就绪队列的顺序进行调度。使用FIFO队列。
   • 优点：简单，易于实现，公平 (按到达顺序) 。
   • 缺点：平均等待时间可能很长，尤其当短进程排在长进程之后时 (护航效应 Convoy Effect) 。不适合交互式系统。是非抢占式的。
2. 最短作业优先 (Shortest Job First, SJF):
   • 实现：选择预计CPU执行时间 (下一个CPU burst) 最短的进程。可以是抢占式 (SRTF - Shortest Remaining Time First) 或非抢占式。
   • 优点：理论上具有最优的平均等待时间和平均周转时间。
   • 缺点：
     • 需要预测下一个CPU burst长度，这很难精确做到 (通常基于历史数据估计) 。
     • 可能导致长作业饿死 (Starvation)，即长时间得不到CPU。
     • 非抢占式SJF不适合交互系统。抢占式SRTF开销较大。
3. 最高响应比优先 (Highest Response Ratio Next, HRRN):
   • 实现：非抢占式。计算每个进程的响应比 R = (等待时间 W + 服务时间 S) / 服务时间 S，选择R最高的进程。
   • 优点：结合了FCFS和SJF的优点。短作业容易被选中 (S小，R大) 。同时，等待时间长的进程其响应比也会增加，避免了饿死。
   • 缺点：仍需要预测服务时间S。计算响应比有额外开销。

适用交互式系统的调度算法有哪些？#

主要目标是提供快速响应和用户满意度。

1. 轮转法 (Round Robin, RR):

   • 实现：类似于FCFS，但增加了时间片和抢占。每个进程被分配一个固定的时间片 (Quantum) ，运行时间超出时间片后会被强制切换 (抢占) ，放回就绪队列尾部。
   • 优点：公平，响应时间相对较短 (特别是对于短请求) ，简单。
   • 缺点：
     • 性能对时间片大小非常敏感。太小则上下文切换频繁，开销大；太大则退化为FCFS，响应时间变长。
     • 平均周转时间通常比SJF长。
     • 没有考虑优先级。
   • 最佳实践: 时间片大小通常选择比平均交互响应所需时间稍长，但足够短以保证多个交互进程能快速轮换。

2. 优先级调度 (Priority Scheduling):

   • 实现：为每个进程分配一个优先级，调度器总是选择就绪队列中优先级最高的进程。可以是抢占式或非抢占式。
   • 优点：可以明确区分重要任务和次要任务。
   • 缺点：
     • 可能导致低优先级进程饿死。
     • 优先级的确定可能是个问题 (静态 vs 动态) 。
   • 改进:
     • 老化 (Aging): 随时间增加等待进程的优先级。
     • 动态优先级: 根据进程行为 (如I/O等待) 调整优先级。

3. 多级队列调度 (Multi-level Queue Scheduling):

   • 实现：将就绪队列划分为多个独立的队列，每个队列有自己的优先级和调度算法 (如：前台交互队列用RR，后台批处理队列用FCFS) 。进程被永久分配到一个队列。
   • 优点：可以为不同类型的进程应用不同的调度策略。开销较低。
   • 缺点：缺乏灵活性，进程无法在队列间移动。低优先级队列可能饿死。

4. 多级反馈队列调度 (Multi-level Feedback Queue, MLFQ):

   • 实现：允许多个队列，并且进程可以在队列之间移动。这是目前通用操作系统中最常用的调度方法之一。
   • 规则示例：
     • 新进程进入最高优先级队列。
     • 如果在时间片内完成，离开系统；如果用完时间片，则降级到下一个较低优先级队列。
     • 在较低优先级队列中等待时间过长的进程可以被提升到较高优先级队列 (防止饿死，即老化) 。
     • I/O密集型进程 (经常阻塞放弃CPU) 通常会停留在较高优先级队列，保证响应性。CPU密集型进程会逐渐下降到较低优先级队列。
   • 优点：非常灵活，自适应。能同时照顾到交互式和批处理式需求，兼顾响应时间、周转时间和公平性。
   • 缺点：设计和调优复杂 (队列数量、各队列调度算法、时间片大小、升级降级策略) 。

适用实时系统的调度算法有哪些？#

主要目标是满足时间约束 (截止时间) 。

1. 速率单调调度 (Rate Monotonic Scheduling, RMS):
   • 类型：静态优先级，抢占式。
   • 原理：周期性任务的优先级与其执行频率 (速率) 成正比。周期越短 (频率越高) ，优先级越高。
   • 优点：简单，易于实现，是最佳的静态优先级调度算法 (如果任务集可调度，RMS就能找到调度方案) 。可进行理论上的可调度性分析 (例如，利用率测试) 。
   • 缺点：只适用于周期性任务；对任务特性有较强假设；CPU利用率上限不如动态优先级算法高。
2. 最早截止时间优先 (Earliest Deadline First, EDF):
   • 类型：动态优先级，抢占式。
   • 原理：当前就绪任务中，绝对截止时间最早的任务拥有最高优先级。
   • 优点：理论上是最优的动态优先级调度算法。只要任务集的总CPU利用率不超过100%，EDF就能找到调度方案 (对于可抢占、独立任务等理想情况) 。可以处理周期性和非周期性任务。
   • 缺点：实现比RMS复杂；可能出现多米诺骨牌效应 (一个任务错过截止时间可能导致后续任务也错过) ；动态优先级变化导致上下文切换可能更频繁。
3. 基于优先级的抢占式调度:
   • 通用方法：给实时任务分配高优先级，使用标准优先级调度器。可以通过精心设置优先级来模拟RMS或EDF的行为。常用于软实时系统或硬实时系统中与其他任务共存的情况。
   • 需要确保高优先级任务能抢占低优先级任务，并且优先级反转 (Priority Inversion) 问题得到处理 (如使用优先级继承 Priority Inheritance 或优先级天花板 Priority Ceiling Protocol) 。

怎样理解抢占式和非抢占式？#

这是调度器决定何时进行调度的两种基本模式。

• 非抢占式调度 (Non-preemptive / Cooperative Scheduling):

  • 定义: 一旦CPU分配给某个进程，该进程将一直运行，直到它主动放弃CPU (完成任务、阻塞等待I/O、或显式调用yield) 。调度器不能在进程运行中途强制剥夺其CPU使用权。
  • 优点: 实现简单；上下文切换只在进程自愿放弃CPU时发生，开销相对较小；不会有并发访问内核数据结构的竞争问题 (在单处理器上) 。
  • 缺点: 一个长时间运行或行为不当的进程可以独占CPU，导致其他进程 (特别是需要快速响应的交互式进程) 长时间等待，响应性差；不适合分时和实时系统。
  • 例子: 早期的Windows (如Windows 3.1), 早期的Mac OS, 某些简单的嵌入式系统。

• 抢占式调度 (Preemptive Scheduling):

  • 定义: 操作系统可以强制暂停当前正在运行的进程 (即使它并未主动放弃CPU) ，并将CPU分配给另一个进程。这种抢占通常发生在时钟中断 (时间片用完) 或更高优先级进程变为就绪时。
  • 优点: 能够保证CPU在进程间公平分配；提供更好的响应时间；可以有效处理优先级，防止低优先级任务阻塞高优先级任务 (前提是优先级设置合理) ；是现代多任务操作系统的标准做法。
  • 缺点: 实现更复杂；上下文切换更频繁，开销更大；需要处理内核数据结构的并发访问问题 (需要锁或其他同步机制) 。
  • 例子: Unix/Linux, Windows NT及后续版本, macOS, 大多数现代RTOS。

从哪几方面对调度算法进行比较？#

主要从前面提到的性能指标/目标来进行比较和评估：

1. CPU利用率: 哪个算法更能让CPU保持忙碌？
2. 吞吐量: 哪个算法单位时间内能完成更多任务？
3. 周转时间 (平均/最坏): 哪个算法下进程从提交到完成更快？
4. 等待时间 (平均/最坏): 哪个算法下进程在就绪队列中等待的时间更短？
5. 响应时间 (平均/方差): 哪个算法对交互式请求的响应更快、更稳定？
6. 公平性: 哪个算法更能保证所有进程获得合理的CPU时间，避免饿死？
7. 可预测性/满足截止时间: 对于实时系统，哪个算法更能保证任务按时完成？
8. 算法开销: 算法本身的计算复杂度以及它导致的上下文切换频率和开销如何？
9. 实现复杂度: 算法是否容易实现和调试？
10. 对参数的敏感性: 算法性能是否严重依赖于某些参数 (如时间片大小、优先级设置) ？

比较方法:

• 确定性建模 (Deterministic Modeling): 给定一组特定的进程及其属性 (到达时间、CPU burst) ，模拟运行不同算法，计算性能指标。简单但只反映特定场景。
• 排队论建模 (Queueing Models): 使用数学方法 (基于概率分布描述进程到达和CPU burst) 来分析平均性能。能提供理论洞察但模型可能简化现实。
• 模拟 (Simulation): 编写程序模拟操作系统调度行为，使用随机生成的进程或真实系统负载的轨迹 (trace) 作为输入。灵活且能反映动态行为，是常用的评估方法。
• 实际系统测量 (Implementation & Measurement): 在真实操作系统中实现算法，运行基准测试 (Benchmark) 或实际负载进行测量。最准确但成本最高。

机制和策略分离的原则在调度算法中的应用#

机制与策略分离 (Separation of Mechanism and Policy) 是一个重要的操作系统设计原则，也适用于调度。

• 机制 (Mechanism): 提供如何做 (How) 的基础能力或工具。在调度中，机制包括：

  • 上下文切换的代码 (保存/加载寄存器、切换页表) 。
  • 维护进程状态 (就绪、运行、阻塞) 和PCB的数据结构。
  • 管理就绪队列 (如链表、优先级队列、红黑树) 。
  • 时钟中断处理程序。
  • 提供设置和读取进程优先级的接口。
  • 进程挂起和唤醒的原子操作。

• 策略 (Policy): 决定做什么 (What) 或何时做 (When)。在调度中，策略是指具体的调度算法逻辑：

  • 如何选择下一个运行的进程 (FCFS规则？SJF规则？RR规则？优先级规则？) 。
  • 时间片长度是多少？
  • 优先级如何确定？是静态还是动态调整？如何调整？
  • 何时进行抢占？
  • 如何处理不同类型的进程 (前台/后台，实时/普通) ？

应用与好处:

1. 灵活性与可扩展性: 将调度算法 (策略) 与底层的上下文切换等 (机制) 分开，使得修改或更换调度策略更加容易，而无需改变底层的核心机制代码。例如，Linux内核允许通过sched_setscheduler()系统调用为进程选择不同的调度策略 (如SCHED_FIFO, SCHED_RR, SCHED_NORMAL/CFS) ，但它们都使用相同的底层上下文切换机制。
2. 模块化: 代码结构更清晰，职责分明。调度策略模块可以独立开发、测试和更新。
3. 可定制性: 用户或管理员可以更容易地根据特定需求调整调度策略参数，甚至在某些系统中插入自定义的调度模块。

例子: 调度器的主循环可能是一个通用的框架 (机制) ，它调用一个函数 (策略) 来选择下一个进程。不同的调度算法可以通过实现这个选择函数来插入。上下文切换函数是另一个独立的机制。优先级队列的实现 (如使用堆或链表) 是机制，而如何利用这个队列 (是按优先级取还是按FIFO取) 是策略。

实例操作系统的调度算法都是什么？#

现代通用操作系统通常采用复杂且混合的调度策略，以平衡各种需求。

1. Linux:

   • 主要调度器 (针对普通进程): 完全公平调度器 (Completely Fair Scheduler, CFS)，自内核2.6.23起引入。
     • 目标：为所有运行中的任务提供尽可能公平的CPU时间份额。
     • 机制：不再基于固定时间片，而是维护每个任务的虚拟运行时间 (vruntime)。总是选择vruntime最小的任务来运行。任务运行会增加其vruntime。I/O等待的任务vruntime增长慢，因此返回时更容易被选中。
     • 实现：使用红黑树来高效地找到vruntime最小的任务。
   • 实时调度策略:
     • SCHED_FIFO: 静态优先级的先来先服务 (非时间片轮转) 。相同优先级的任务按到达顺序执行，直到阻塞、退出或被更高优先级抢占。
     • SCHED_RR: 静态优先级的轮转法。同SCHED_FIFO，但增加了时间片，同一优先级任务轮流运行。
   • 优先级：实时任务优先级高于普通任务。普通任务也有优先级 (nice值) ，但CFS主要通过vruntime实现公平性，nice值影响vruntime增长的速度。

2. Windows (NT内核及以后):

   • 采用基于优先级的抢占式调度算法，结合了多级反馈队列的思想。
   • 优先级：分为32个优先级。0为系统空闲线程，1-15为可变优先级类 (Variable Priority Classes) ，16-31为实时优先级类 (Real-time Priority Classes) 。内核线程可能使用更高的内部优先级。
   • 动态调整：
     • 对于可变优先级类，系统会动态提升线程的优先级 (Priority Boost) ，例如：
       • 当线程完成I/O操作时。
       • 当等待事件/信号量被满足时。
       • 前台窗口的线程优先级通常会被提升，以改善交互响应。
       • 短时间片用完后，优先级可能会暂时降低。
     • 长时间消耗CPU的线程其动态优先级会逐渐衰减回基础优先级。
   • 时间片：不同优先级的线程可能有不同的时间片长度。前台进程的时间片通常比后台进程长且可变。
   • Quantum：Windows中称为Quantum，不是固定的，可以根据系统设置和前后台状态调整。

3. macOS:

   • 基于XNU内核 (混合了Mach微内核和BSD Unix) 。
   • 调度也采用基于优先级的抢占式模型，具有多级反馈特性。
   • 线程优先级分为几个主要波段 (bands)：内核模式、系统高优先级、用户交互 (UI响应关键) 、用户启动、后台任务等。
   • 动态调整：系统会根据线程的行为 (如CPU使用情况、是否阻塞等待I/O、是否与用户界面交互) 动态调整其优先级，类似于Windows。
   • 也使用了类似Mach的线程调度原语和概念，例如时间片捐赠 (Time-sharing donation) 等机制来优化性能。
   • 近年来引入了服务质量 (Quality of Service, QoS) 类的概念，让开发者可以指定任务的意图 (如用户交互、后台数据处理、维护任务) ，系统据此进行更智能的资源 (包括CPU调度) 管理。

总结: 现代主流操作系统都使用抢占式、基于优先级的调度框架，并结合动态优先级调整、多级队列/反馈机制，以及针对公平性 (如Linux CFS) 或服务质量 (如macOS QoS) 的特定优化，以适应通用计算环境中复杂多变的需求。

2. 处理器调度的基本概念#

2.1 调度的三个层次#

操作系统中的调度可以发生在不同层面，对应不同的资源管理和时间尺度：

1. 长程调度 (Long-term Scheduling / 作业调度):
   • 时机: 创建新进程时。
   • 决策: 决定是否将新创建的进程纳入当前活跃进程集合 (即是否允许进入内存和就绪队列) 。
   • 目标: 控制系统的并发度 (道数) 。
2. 中程调度 (Medium-term Scheduling / 内存调度):
   • 时机: 内存资源紧张或需要优化内存使用时。
   • 决策: 决定哪些进程的部分或全部从内存换出到外存 (挂起) ，以及何时将挂起的进程换回内存。
   • 目标: 提高内存利用率和系统吞吐量，通过交换 (Swapping) 技术实现。
3. 短程调度 (Short-term Scheduling / CPU调度 / 微观调度):
   • 时机: 发生特定事件 (如中断、系统调用、进程阻塞/唤醒、时间片用完等) 后，需要选择下一个占用CPU的进程时。
   • 决策: 从就绪队列中选择一个进程/线程，将CPU的使用权分配给它。
   • 频率: 非常频繁，通常在毫秒级。
   • 要求: 实现必须高效。

联系: 这三个层次的调度相互关联，共同管理进程从创建到完成的整个生命周期及其资源使用。

2.2 处理器调度的定义与场景#

• 定义: 控制和协调多个进程对CPU资源的竞争。
• 场景: 系统中有 N 个进程处于就绪状态，等待在 M 个CPU (M ≥ 1) 上运行。
• 任务: 调度程序 (内核函数) 根据特定的调度算法，从就绪队列中选择一个进程，并将CPU使用权交给它。
• Idle进程: 如果就绪队列为空 (没有可运行的用户或系统进程) ，系统会调度一个特殊的空闲进程 (idle process) 来运行，它通常执行一些低优先级任务 (如系统监控、节能) 或简单地循环等待中断。

2.3 调度需要解决的核心问题#

1. 调度时机 (When): 何时进行处理器分配决策。
2. 调度算法 (What): 依据何种原则挑选进程/线程。
3. 调度过程 (How): 如何完成CPU的分配，即上下文切换。

2.4 CPU调度的时机#

调度通常在以下事件发生后，内核处理完相应事件并准备返回用户态之前的最后时刻进行：

• 进程生命周期变化:
  • 进程执行完毕并退出 (exit())。
  • 进程因错误或异常而终止 (abort)。
  • 创建新进程 (fork())。
• 进程状态转换:
  • 运行进程因等待I/O或资源而进入阻塞态 (wait())。
  • 阻塞进程被唤醒，回到就绪态 (I/O完成中断)。
  • 运行进程用完分配的时间片，回到就绪态 (时钟中断)。
  • 运行进程主动放弃 CPU (yield())。
• 中断:
  • I/O 中断。
  • 时钟中断 (用于时间片、计时器)。
  • 系统调用返回前。
  • 异常处理后。

流程: 事件发生 → 暂停当前进程 → 硬件响应 → 进入内核处理事件 → 事件处理结束 (可能导致进程状态变化、就绪队列调整) → 执行进程调度 → 选择新进程运行。

2.5 调度过程：上下文切换 (Context Switching)#

• 定义: 将CPU的控制权从一个进程 (或线程) 转移给另一个进程 (或线程) 的过程。这涉及到保存当前进程的状态并加载新进程的状态。
• 上下文 (Context): 进程运行时，其执行状态 (硬件上下文) 保存在CPU的寄存器中 (如程序计数器PC, 程序状态字PSW, 栈指针SP, 通用寄存器等) 。进程不运行时，这些信息保存在其进程控制块 (PCB) 中。
• 主要工作:
  1. 切换地址空间: 修改页目录寄存器 (如CR3 on x86) 以指向新进程的页表，加载新的虚拟地址空间。
  2. 切换内核栈和硬件上下文:
     • 保存当前进程的寄存器值到其PCB或内核栈。
     • 从新进程的PCB或内核栈中恢复其寄存器值到CPU。
     • 内核栈 (Kernel Stack):
       • 每个进程都有自己的内核栈，用于在进程执行内核代码时存储函数调用、局部变量和上下文信息。
       • 当进程从用户态切换到内核态 (如系统调用、中断) 时，CPU会自动切换到该进程的内核栈。
       • 内核栈位于内核地址空间，对用户程序不可见，大小通常是固定的 (如 Linux 中为 8KB 或 16KB) 。
       • 内核栈的地址通常保存在进程的 PCB 中，在上下文切换时需要更新相关寄存器 (如栈指针) 指向新进程的内核栈。
• 具体步骤 (进程A切换到进程B):
  1. 保存进程A的硬件上下文 (寄存器值) 。
  2. 更新进程A的PCB (如状态改为就绪或阻塞，记录PC等) 。
  3. 将进程A移入相应的队列 (就绪队列、等待队列) 。
  4. 选择进程B作为下一个运行进程。
  5. 更新进程B的PCB (状态改为运行) 。
  6. 加载进程B的上下文 (恢复寄存器值，切换地址空间) 。
  7. 开始执行进程B。
• XV6 Context Switch Example (swtch.S): (此处展示汇编代码逻辑，具体代码略)
  • swtch 函数接受两个参数：旧进程上下文指针 (old) 和新进程上下文指针 (new)。
  • 它负责保存 old 进程的callee-saved寄存器到其上下文结构中。
  • 然后，从 new 进程的上下文结构中恢复callee-saved寄存器。
  • 最后，通过 ret 指令返回，此时CPU将跳转到 new 进程之前保存的PC地址， effectively switching execution flow. The key is switching the stack pointer.
• 上下文切换开销 (Cost):
  • 直接开销: 内核执行切换操作所花费的CPU时间。
    • 保存和恢复寄存器。
    • 切换地址空间 (TLB Flush相关指令通常较昂贵) 。
    • 执行调度算法本身的代码。
  • 间接开销: 切换导致缓存性能下降。
    • CPU Cache 失效: 新进程的代码和数据不在缓存中，需要从内存加载。
    • TLB (Translation Lookaside Buffer) 失效: 地址翻译缓存失效，需要重新查询页表。
    • 缓冲区缓存 (Buffer Cache) 可能失效: 文件系统相关的缓存可能对新进程无效。

3. 处理器调度算法的设计#

3.1 不同操作系统类型的调度目标#

调度算法的选择与操作系统的主要应用场景和目标密切相关：

• 批处理系统 (Batch Systems):
  • 特点: 通常运行长任务，无需用户交互。
  • 目标:
    • 高吞吐量 (Throughput): 单位时间内完成的作业数量最大化。
    • 短周转时间 (Turnaround Time): 作业从提交到完成的总时间最小化。
    • 高CPU利用率 (CPU Utilization): 让CPU尽可能处于忙碌状态。
• 交互式系统 (Interactive Systems):
  • 特点: 需要频繁与用户交互，用户等待输入。
  • 目标:
    • 快速响应时间 (Response Time): 从用户输入命令到系统首次给出反馈的时间要短 (通常要求低于50-150ms) 。
    • 均衡性 (Proportionality): 用户感觉系统性能稳定，符合预期。
• 实时系统 (Real-time Systems):
  • 特点: 任务有严格的时间限制 (截止时间, Deadline) 。
  • 目标:
    • 满足最后期限 (Meeting Deadlines): 关键任务必须在规定时间内完成 (硬实时) 或尽可能满足 (软实时) 。
    • 可预测性 (Predictability): 系统行为在时间上是确定的。

3.2 调度算法的设计考量#

设计调度算法时，需在多个目标之间进行权衡 (Trade-off) ：

• 用户角度 (User-oriented):
  • 周转时间 (Turnaround Time): T(completion) - T(arrival)。进程从进入系统到完成的总时间。目标：最小化平均周转时间。
  • 响应时间 (Response Time): 从请求发出到第一次产生响应的时间。目标：最小化响应时间 (对交互式系统尤为重要) 。
  • 最后期限 (Deadline): 实时任务必须在规定时间前完成。目标：确保满足所有 (硬实时) 或重要 (软实时) 的截止时间。
  • 可预测性 (Predictability): 任务运行时间稳定，尤其对实时系统。
• 系统角度 (System-oriented):
  • 吞吐量 (Throughput): 单位时间内完成的进程数量。目标：最大化吞吐量。
  • CPU 利用率 (CPU Utilization): CPU忙于执行有效工作的时间百分比。目标：最大化CPU利用率。
  • 公平性 (Fairness): 各进程获得合理的CPU时间份额，防止饥饿。
  • 均衡性 (Balance): 系统资源 (CPU, I/O设备等) 应保持忙碌，充分利用。
  • 强制优先级 (Enforcing Priorities): 确保高优先级进程优先获得服务。

3.3 调度算法的关键决策点#

设计或选择调度算法时，需要考虑以下几个方面：

1. 进程优先级 (Priority):

   • 优先数: 用于表示优先级的数值 (数值越大优先级越高或越低，取决于系统定义) 。
   • 静态优先级 (Static Priority): 进程创建时指定，运行期间不变。简单，但可能不适应进程行为变化。
   • 动态优先级 (Dynamic Priority): 进程优先级在运行过程中可以调整。例如，可以提升长时间等待的进程的优先级 (老化, Aging) ，或降低长时间占用CPU进程的优先级。更能适应系统变化。
   • PCB记录: PCB中需要包含优先级信息。

2. 就绪队列组织 (Ready Queue Organization):

   • 单一队列: 所有就绪进程放在一个队列中，按某种顺序 (如FCFS、优先级) 排列。
   • 多级队列 (Multiple Queues): 按进程属性 (如优先级、类型) 划分多个队列。不同队列可采用不同调度策略。
     • 按优先级排队: 每个优先级一个队列。调度器先服务高优先级队列。
     • 按类型排队: 如前台 (交互) 进程队列、后台 (批处理) 进程队列。

3. 抢占 vs. 非抢占 (Preemptive vs. Non-preemptive):

   • 非抢占式 (Non-preemptive / 不可剥夺): 一旦进程获得CPU，它将一直运行，直到它自愿放弃 (完成、阻塞、yield) 。适用于批处理，简单，但响应性差。
   • 抢占式 (Preemptive / 可剥夺): 当前运行的进程可以被更高优先级的就绪进程或时钟中断强制中断，CPU被分配给新进程。适用于交互式和实时系统，响应性好，但有上下文切换开销。

4. I/O密集型 vs. CPU密集型进程 (I/O-bound vs. CPU-bound):

   • I/O密集型: 进程大部分时间在等待I/O操作完成，CPU计算时间短。
   • CPU密集型 (计算密集型): 进程大部分时间在进行CPU计算，很少I/O操作。
   • 调度倾向: 现代系统通常倾向于优先调度I/O密集型进程，以保持I/O设备忙碌，提高系统整体吞吐量和响应性。让I/O进程尽快发出下一个I/O请求，然后在其等待时运行CPU密集型进程。

5. 时间片 (Time Slice / Quantum):

   • 定义: 在抢占式调度 (特别是轮转RR) 中，分配给进程一次连续运行的最大CPU时间。
   • 选择: 时间片大小的选择是一个重要的权衡：
     • 太长: 接近非抢占，长任务会阻塞短任务，交互式响应变慢。退化为FCFS。
     • 太短: 频繁发生上下文切换，系统开销增大，有效工作比例下降。
     • 合适的大小: 通常需要在几十到几百毫秒之间，取决于系统负载、CPU速度、上下文切换开销和对响应时间的要求。应略大于典型的一次交互所需CPU时间。
   • 固定 vs. 可变: 时间片可以是固定的，也可以根据进程优先级或行为动态调整。

4. 典型的处理器调度算法#

4.1 批处理系统调度算法#

主要目标：高吞吐量、低周转时间、高CPU利用率。

• 先来先服务 (FCFS - First Come First Serve):

  • 策略: 按进程到达就绪队列的顺序进行调度。非抢占式。
  • 优点: 公平 (按到达顺序) 、简单易实现。
  • 缺点:
    • 平均周转时间和平均等待时间可能很长，特别是当短进程排在长进程之后时 (护航效应, Convoy Effect) 。
    • 不利于I/O密集型进程 (长CPU进程运行时，I/O进程等待；I/O进程运行时，CPU空闲) 。
    • 对交互式用户不友好。
  • 例子: 进程P1(24s), P2(3s), P3(3s) 按 P1, P2, P3 顺序到达。
    • 执行顺序: P1 -> P2 -> P3
    • 完成时间: P1(24), P2(27), P3(30)
    • 周转时间: P1(24), P2(27), P3(30) -> 平均 27s
    • 若按 P2, P3, P1 顺序调度:
      • 执行顺序: P2 -> P3 -> P1
      • 完成时间: P2(3), P3(6), P1(30)
      • 周转时间: P2(3), P3(6), P1(30) -> 平均 13s (显著改善)

• 最短作业优先 (SJF - Shortest Job First):

  • 策略: 选择预计运行时间最短的进程投入运行。
  • 版本:
    • 非抢占式 SJF: 当前进程一直运行直到结束或阻塞。
    • 抢占式 SJF (最短剩余时间优先, SRTN - Shortest Remaining Time Next): 当一个新进程到达，其预计总运行时间比当前进程的 剩余 运行时间还短时，抢占当前进程。
  • 优点: 理论上可证明，在所有进程同时到达时，SJF(非抢占)具有最低的平均周转时间。SRTN通常比非抢占SJF的平均周转时间更短。
  • 缺点:
    • 需要预测未来: 如何准确知道进程的运行时间？通常基于历史数据进行估计，可能不准。
    • 饥饿 (Starvation): 长进程可能永远得不到CPU，如果总有短进程到来。
    • 不公平: 明显偏袒短进程。
  • 例子 (SRTN):

    进程	到达时刻	运行时间
    P1	0	7
    P2	2	4
    P3	4	1
    P4	5	4

    • 0: P1 运行 (剩余 7)
    • 2: P2 到达 (剩余 4) < P1 (剩余 5)，P2 抢占 P1。P2 运行 (剩余 4)
    • 4: P3 到达 (剩余 1) < P2 (剩余 2)，P3 抢占 P2。P3 运行 (剩余 1)
    • 5: P3 完成。P4 到达 (剩余 4)。比较 P1(剩余 5), P2(剩余 2), P4(剩余 4)。P2 剩余时间最短，P2 运行 (剩余 2)
    • 7: P2 完成。比较 P1(剩余 5), P4(剩余 4)。P4 剩余时间最短，P4 运行 (剩余 4)
    • 11: P4 完成。只剩 P1，P1 运行 (剩余 5)
    • 16: P1 完成。
    • 执行序列: P1(0-2) -> P2(2-4) -> P3(4-5) -> P2(5-7) -> P4(7-11) -> P1(11-16)

• 最高响应比优先 (HRRN - Highest Response Ratio Next):

  • 策略: 综合考虑等待时间和运行时间，选择响应比最高的进程。非抢占式。
  • 响应比 R = (等待时间 + 预计运行时间) / 预计运行时间 = 1 + (等待时间 / 预计运行时间)
  • 优点:
    • 试图在SJF和FCFS之间取得平衡。
    • 短进程：预计运行时间小，响应比增长快，容易被选中 (类似SJF) 。
    • 长进程：等待时间足够长后，响应比会提高，最终能获得CPU，避免了饥饿。
  • 缺点: 仍需预测运行时间。计算响应比有额外开销。
  • 抢占式HRRN? 理论上可以，但每次事件 (如新进程到达) 都需要重新计算所有就绪进程的响应比并排序，开销较大。

4.2 交互式系统调度算法#

主要目标：快速响应时间、均衡性、公平性。

• 时间片轮转 (RR - Round Robin):

  • 策略: 将所有就绪进程按FCFS排成队列。调度器选择队首进程，分配一个时间片 (quantum) 。进程用完时间片后，若未完成或阻塞，则移到队尾。抢占式。
  • 优点:
    • 公平：每个进程都能获得运行机会。
    • 响应时间快：短进程能较快完成或得到响应。非常适合分时系统。
  • 缺点:
    • 上下文切换开销：时间片过短会导致开销过大。
    • 性能与时间片长度密切相关。
    • 对周转时间不一定最优。对于运行时间相近的进程，RR的平均周转时间可能比FCFS差。
  • 例子 (时间片 q=20): P1(53), P2(8), P3(68), P4(24)
    • 执行序列: P1(0-20) -> P2(20-28) -> P3(28-48) -> P4(48-68) -> P1(68-88) -> P3(88-108) -> P4(108-112) -> P1(112-125) -> P3(125-145) -> P3(145-153)
    • 平均等待时间 = ( (68-20)+(112-88) + (20-0) + (28-0)+(88-48)+(125-108) + (48-0)+(108-68) ) / 4 = (72 + 20 + 85 + 88) / 4 = 66.25 ms (假设到达时间为0)

• 虚拟轮转 (Virtual RR - VRR):

  • 动机: RR对I/O密集型进程可能不公平。I/O进程经常在时间片未用完时就阻塞，返回就绪队列时排在队尾，下次获得CPU可能要等很久。
  • 策略: 维护一个辅助就绪队列 (如AUX队列) 。当一个进程因I/O阻塞完成而返回时，不放入主RR队列尾部，而是放入AUX队列头部。调度器优先检查AUX队列，若非空则调度AUX队首进程，给其一个较短的时间片 (通常是其上次阻塞时剩余的时间片) ；若AUX队列为空，则按标准RR调度主队列。从AUX队列运行完时间片的进程回到主RR队列尾部。
  • 目标: 给I/O密集型进程更多机会运行，提高I/O设备利用率。

• 优先级调度 (Priority Scheduling):

  • 策略: 选择就绪队列中优先级最高的进程运行。可以是抢占式或非抢占式。
  • 优点: 实现简单，能满足不同进程的紧急程度需求 (如系统进程>用户进程，前台>后台，I/O型>CPU型) 。
  • 缺点:
    • 饥饿: 低优先级进程可能永远无法运行。
    • 优先级反转 (Priority Inversion): 一个低优先级进程持有高优先级进程所需的资源 (如锁) ，导致高优先级进程被迫等待低优先级进程。更糟的是，如果此时有一个中等优先级的CPU密集型进程就绪，它会抢占低优先级进程，使得高优先级进程的等待时间变得更长甚至不可预测。
  • 优先级反转解决方案:
    • 优先级继承 (Priority Inheritance): 当高优先级进程等待低优先级进程持有的资源时，暂时将低优先级进程的优先级提升到与高优先级进程相同，使其能尽快运行并释放资源。
    • 优先级天花板协议 (Priority Ceiling Protocol): 给每个资源预设一个优先级上限 (等于可能使用该资源的所有进程中的最高优先级) 。当一个进程获得资源时，将其优先级提升到该资源的优先级上限。这能预防死锁并限制阻塞时间。
    • 中断禁止: 在临界区执行期间禁止中断 (简单粗暴，在通用操作系统中通常不可取，但用于某些嵌入式或实时内核) 。

• 多级队列调度 (Multilevel Queue Scheduling):

  • 策略: 将就绪队列划分为多个独立的队列，每个队列有自己的调度算法和优先级。例如：
    • 系统进程队列 (最高优先级, RR 或 FCFS)
    • 交互式进程队列 (中优先级, RR)
    • 批处理进程队列 (最低优先级, FCFS)
  • 调度器首先处理高优先级队列中的所有进程，然后才处理次高优先级队列，以此类推。队列之间通常是抢占式的 (高优先级队列进程可抢占低优先级队列进程) 。
  • 优点: 灵活性高，可以为不同类型的进程定制调度策略。
  • 缺点: 进程通常被固定分配到一个队列，缺乏灵活性；低优先级队列可能饥饿。

• 多级反馈队列调度 (Multilevel Feedback Queue Scheduling - MFQ):

  • 策略: 结合了多级队列和动态优先级调整。进程可以在不同队列之间移动。
  • 典型实现:
    1. 设置多个优先级队列 (Q0, Q1, …, Qn)，优先级 Q0 > Q1 > … > Qn。
    2. 不同队列分配不同的时间片长度，优先级越高的队列时间片越短 (如 Q0=q, Q1=2q, Q2=4q…) 。
    3. 新进程进入最高优先级队列 Q0。
    4. 调度器总是先运行最高非空队列中的进程，同队列内通常用RR。
    5. 如果进程在一个队列中用完了其时间片但未完成，它会被 降级 到下一个较低优先级队列。
    6. 如果进程在时间片未用完前因 阻塞 (如等待I/O) 而放弃CPU，当它再次就绪时，通常会回到 原来的 队列 (或有时提升一级) ，以优待I/O密集型进程。(讨论点： 回到原队列还是队首/队尾？提升吗？具体策略不同系统可能不同。)
    7. 最低优先级队列通常采用FCFS或很长的时间片RR。
    8. (可选) 可以加入 老化 (Aging) 机制：在低优先级队列等待过久的进程可以被提升到较高优先级队列，防止饥饿。
  • 优点: 非常灵活，能同时满足交互式 (响应快) 和批处理 (吞吐量) 的需求，能自动适应进程行为，是最常用的调度算法之一。
  • 缺点: 设计和调优 (队列数量、时间片大小、升级降级策略) 比较复杂。

• 其他交互式算法 (简述):

  • 公平共享调度 (Fair-share Scheduling): 不仅考虑单个进程，还考虑进程所属的用户或用户组，确保CPU时间在用户/组之间公平分配。
  • 保证调度 (Guaranteed Scheduling): 向用户承诺每个进程将获得 CPU 时间的 1/n (如果有n个进程) ，并跟踪进程实际获得的CPU时间，优先运行获得时间最少的进程。
  • 彩票调度 (Lottery Scheduling): 给每个进程分配一定数量的“彩票”，调度器随机抽取一张彩票，持有该彩票的进程获得CPU。进程持有的彩票越多，获得CPU的机会越大。优先级可以通过分配不同数量的彩票来体现。简单，易实现概率公平。

4.3 实时系统调度算法#

主要目标：满足任务截止时间、可预测性。

• 可调度性分析: 对于周期性实时任务，需要判断系统是否能在所有任务的截止时间内完成它们。

  • 若有 m 个周期任务，任务 i 的周期为 Pi，每次执行需 Ci 的CPU时间，则一个简单的 (充分非必要) 可调度条件是： Σ (Ci / Pi) ≤ 1 (CPU利用率不超过100%)
  • 更精确的条件取决于具体算法 (如RM, EDF) 。

• 速率单调调度 (Rate-Monotonic Scheduling - RM):

  • 类型: 静态优先级，抢占式。
  • 策略: 任务的优先级根据其 周期 (Rate) 设定：周期越短 (频率越高) ，优先级越高。
  • 适用: 周期性实时任务。
  • 优点: 简单，理论成熟，可进行精确的可调度性分析 (Liu & Layland 条件：Σ(Ci/Pi) ≤ n(2^(1/n)-1))。
  • 缺点: 仅适用于周期任务，对任务集利用率上限有要求 (不是100%)。

• 最早截止时间优先 (Earliest Deadline First - EDF):

  • 类型: 动态优先级，抢占式。
  • 策略: 调度器在每次调度时，选择就绪队列中 绝对截止时间 (Deadline) 最早的任务运行。
  • 适用: 周期性和非周期性实时任务。
  • 优点: 理论上是最优的动态优先级算法，只要系统总利用率 ≤ 1，EDF就能找到一个可行的调度 (如果存在的话) 。CPU利用率上限可达100%。
  • 缺点: 实现比RM复杂 (需要跟踪每个任务的截止时间) ，可能出现瞬时过载导致多米诺骨牌效应 (一个任务错过deadline可能导致后续任务都错过) 。

4.4 各种调度算法比较总结#

(表中 w: 等待时间, s: 总服务时间, e: 已执行时间)

5. 调度中的重要原则与实践#

5.1 机制与策略分离 (Mechanism vs. Policy Separation)#

• 原则: 将调度的具体实现 (机制，如何进行上下文切换、如何管理队列等) 与调度的决策逻辑 (策略，选择哪个进程运行、优先级如何确定等) 分离开。
• 为什么?
  • 灵活性: 更容易修改或替换调度策略，而无需改变底层机制。
  • 可扩展性: 方便添加新的调度策略。
  • 模块化: 代码结构更清晰，易于理解和维护。
• 怎么做? 操作系统内核提供通用的调度框架 (机制，如优先级队列、上下文切换函数) ，而具体的调度算法 (策略) 作为可配置或可插拔的模块实现。例如，Linux 的 sched_class 结构就体现了这种思想。

5.2 线程调度 (Thread Scheduling)#

• 背景: 现代操作系统多数支持内核级线程。调度单元从进程变为线程。
• 用户级线程 vs. 内核级线程:
  • 用户级线程: 调度由用户空间的线程库管理，内核只看到一个进程。切换快，但一个线程阻塞会导致整个进程阻塞。无法利用多核。
  • 内核级线程: 调度由内核管理，每个线程有自己的上下文。切换开销比用户级线程大，但比进程切换小。一个线程阻塞不影响其他线程。可以并发运行在多核上。
• 调度对象: 内核调度器直接调度内核级线程。对于用户级线程，内核调度的是其所属的进程 (或承载用户线程的内核线程LWP) 。

6. 实例：操作系统调度算法#

6.1 典型系统采用的算法概览#

• UNIX (早期): 动态优先级，基于nice值和CPU使用情况调整。
• 5.3BSD: 多级反馈队列算法。
• Windows: 基于优先级的抢占式多任务调度 (细节见下) 。
• Linux: 抢占式调度，主要使用CFS (普通进程) 和实时调度策略 (实时进程) (细节见下) 。
• Solaris: 综合调度算法，支持多种调度类 (实时、分时、交互、系统等) 。

6.2 Windows 线程调度#

• 调度单位: 线程 (内核级线程)。
• 核心算法: 基于 动态优先级 的 抢占式 调度，结合 时间配额 (Quantum) 调整。
• 就绪队列: 维护多个优先级队列 (0-31) 。系统总是选择当前最高非空优先级队列中的线程运行。
• 同优先级调度: 同一优先级队列内部，线程按 时间片轮转 (RR) 方式调度。
• **多处理器:**允许多个线程在不同处理器上并行运行。
• 调度触发条件:
  • 线程创建、终止。
  • 线程状态改变 (运行->阻塞, 阻塞->就绪, 运行->就绪) 。
  • 线程优先级改变。
  • 线程改变其处理器亲和性 (Affinity)。
  • 时间片用完。
  • 主动放弃 (yield)。
• 线程优先级:
  • 共32个优先级级别 (0-31)。
  • 实时优先级 (16-31): 优先级固定不变。用于需要紧急响应的任务。最高。
  • 可变优先级 (1-15): 线程有一个基本优先级 (Base Priority)，其当前优先级 (Current Priority) 可以在此基础上动态调整 (提升或降低) 。用于普通用户和系统线程。
  • 系统线程 (1-15中的一部分): 用于操作系统内部任务。
  • 零页线程 (0): 特殊线程，优先级最低，用于在系统空闲时将物理内存页清零。
• 时间配额 (Quantum):
  • 不是绝对时间值，而是以 配额单位 (quantum unit) 的整数表示。系统时钟中断时递减。
  • Quantum 和 QuantumReset 记录在 KTHREAD 结构中。
  • 当线程用完时间配额：
    • 如果 没有 其他同优先级或更高优先级的线程就绪，Windows会 重新分配 一个新的时间配额给该线程，让它继续运行 (避免不必要的切换) 。
    • 如果 有 其他同优先级线程就绪，该线程移到其优先级队列的末尾，调度器选择下一个线程。
    • 如果用完时间配额 且 优先级被降低，则会被抢占。
  • 作用: 调整时间配额 (而非仅优先级) 可以影响进程获得CPU时间的比例，而不会完全饿死其他进程。例如，给前台游戏进程更大配额，使其运行更流畅，同时后台计算任务也能获得一些CPU时间。
• 调度数据结构:
  • 每个进程有默认优先级、亲和性、时间配额。
  • 每个线程有基本优先级、当前优先级、亲和性、时间配额。
  • Dispatcher Ready List: 包含32个就绪线程队列的数组。
  • KiDispatcherReadyListHead: 指向就绪队列的指针数组。
  • Ready Summary (就绪位图): 一个32位掩码，每一位对应一个优先级队列，指示该队列是否为空。调度器通过查找第一个置位的位 (Find First Set bit, FFS) 快速找到最高优先级的非空队列。
  • Idle Summary (空闲位图): (多处理器) 位图，指示哪些处理器当前处于空闲状态。
• 调度策略细节:
  • 主动切换: 进程自愿放弃CPU (阻塞、Yield等) 。
  • 抢占:
    • 更高优先级的线程变为就绪。
    • 当前线程优先级降低，低于另一个就绪线程。
    • 被抢占线程放回其 原 优先级就绪队列的 队首。
    • 实时优先级线程被抢占，下次运行时获得完整时间配额。
    • 可变优先级线程被抢占，下次运行时继续执行剩余时间配额。
  • 时间配额用完:
    • 优先级不降低：若队列无其他线程则重置配额继续，否则移到队尾。
    • 优先级降低：移到新优先级的队列，可能被抢占。
• 线程优先级提升 (Priority Boost):
  • 目的: 改善响应性、解决饥饿、提高吞吐量。仅针对可变优先级线程 (1-15)。
  • 触发情况:
    1. I/O操作完成: 临时提升等待该I/O的线程优先级，幅度由设备驱动程序建议 (与设备响应要求相关) ，使其能快速处理数据。提升后时间配额会减1 (避免不公平利用I/O提升) 。
    2. 等待事件或信号量结束: 线程优先级提升1级 (不超过15) ，以补偿其等待时间。完成提升后的运行后，优先级会逐渐衰减回基本优先级。时间配额减1。
    3. 前台进程中的线程 完成等待操作。
    4. 因 窗口消息 (GUI活动) 而唤醒的线程。
    5. 反饥饿: 系统线程”平衡集管理器” (Balance Set Manager) 定期扫描，将等待过久 (如 > 300时钟中断) 的线程优先级提升到15，并给予4倍时间配额。用完后优先级立即恢复。
• 空闲线程 (Idle Thread):
  • 每个处理器核都有一个对应的空闲线程。优先级为0。
  • 当没有其他可运行线程时，调度器调度空闲线程。
  • 功能: 循环检测是否有工作要做：处理挂起的中断(DPCs)、检查是否有新就绪线程、调用HAL执行电源管理 (如让CPU进入低功耗状态) 。

6.3 多处理器调度 (Multiprocessor Scheduling)#

• 特点: 系统包含多个CPU (核) ，可共享负载。
• 对称多处理 (SMP - Symmetric Multiprocessing):
  • 所有CPU地位平等，都可以运行内核代码和用户进程。
  • 每个CPU通常有自己的调度器实例。
  • 调度器访问共享数据结构 (如就绪队列) 需要同步 (锁、原子操作) 。
• 设计挑战:
  • 进程/线程分配: 决定哪个任务在哪个CPU上运行。
  • 负载均衡 (Load Balancing): 使各CPU负载大致均匀，避免某些CPU过载而其他CPU空闲。
  • 处理器亲和性 (Processor Affinity): 尽量让一个进程/线程连续在同一个CPU上运行，以利用CPU缓存 (L1/L2 cache) 中已加载的数据和TLB条目，减少缓存失效带来的开销。
  • 缓存一致性 (Cache Coherence): 硬件机制 (如MESI协议) 确保多个CPU缓存中共享数据的副本是一致的。
• 进程分配策略:
  • 静态进程分配 (Static Assignment): 进程从创建到结束都绑定在某个特定CPU上。每个CPU有自己的私有就绪队列。调度开销小，易于维护亲和性，但可能导致负载不均。
  • 动态进程分配 (Dynamic Assignment): 进程可以在不同CPU之间迁移。通常有一个全局共享就绪队列，或各CPU有私有队列但允许任务迁移。负载均衡好，但调度开销大 (需要同步、迁移成本) 。
• 多核处理器问题:
  • 缓存一致性: 如上所述，硬件解决。
  • 缓存亲和性: 调度器需要考虑。让任务倾向于留在上次运行的核上。
  • 核间数据共享: 需要高效的同步机制。
  • 负载均衡: 需要策略在CPU间迁移任务。
    • 缓存亲和性 vs. 负载均衡: 这是个权衡。过于强调亲和性可能导致负载失衡；过于频繁地迁移以追求负载均衡则会破坏缓存亲和性，增加开销。
    • 例子:
      • 并行计算/渲染: 任务与数据绑定到核心可利用缓存，但计算量不均时需迁移任务以平衡负载，导致缓存失效。
      • CDN: 内容按地理位置缓存 (亲和性) ，但负载高时请求可能路由到其他节点 (破坏亲和性) 以均衡负载。
    • 工作窃取 (Work Stealing): 一种常见的负载均衡策略。每个CPU维护一个本地任务队列 (通常是双端队列) 。CPU优先执行自己队列的任务。当一个CPU空闲时，它会随机选择另一个CPU，并从其任务队列的 尾部 “窃取” 一个任务来执行。 (被窃取的CPU从头部获取任务) 。
      • 优点: 实现了负载均衡，同时本地任务优先执行保证了一定的缓存亲和性，分布式决策减少了中心瓶颈。
      • 缺点: 仍有通信和同步开销。
      • 实例: Go语言的GMP调度器，Java的ForkJoinPool，Hadoop YARN。

6.4 实时调度 (Real-time Scheduling) (回顾)#

• 目标: 满足时间约束 (截止时间) ，高可靠性，确定性。
• 类型: 硬实时 (必须满足) vs. 软实时 (尽量满足)。周期性 vs. 偶发性 vs. 非周期性任务。
• 关键参数: 时间 (周期、执行时间、截止时间) 。
• 算法: RM (静态优先级, 周期短优先), EDF (动态优先级, 截止时间早优先)。

6.5 OpenEuler 多核调度技术 (简述)#

• 基础: CPU调度是为保证并发性，通过调度程序(Scheduler)按调度策略(Policy)选择进程占用CPU。
• 算法: 结合使用 FIFO, RR, 优先级调度 (用于实时进程) 。
• 普通进程: 主要采用 CFS (Completely Fair Scheduler) 算法，追求公平性，基于虚拟运行时间 (vruntime) 按优先级比例分配CPU时间。
• 多核调度:
  • 早期单队列问题: 所有CPU共享一个队列。
    • 策略一 (简单RR) ：进程在CPU间频繁迁移，破坏缓存亲和性。
    • 策略二 (带亲和性) ：尽量让进程留在一个CPU，但可能牺牲某些进程 (如E) 的公平性或导致负载失衡。
  • 多队列调度: 每个CPU维护自己的就绪队列 (如Q0 for CPU0, Q1 for CPU1) 。
    • 优点: 提高缓存亲和性，减少锁竞争。
    • 问题: 可能导致负载失衡 (如一个队列空了，另一个还很忙) 。
  • 迁移线程 (Migration Thread): OpenEuler 使用迁移线程解决负载不均衡。每个CPU有一个 migration/CPUID 内核线程。当检测到负载不均时 (如CPU0空闲，CPU1忙) ，CPU0可以向CPU1的停机工作队列 (stop machine workqueue) 添加一个任务，唤醒CPU1的迁移线程。该线程优先级很高，会立即执行迁移任务 (如将进程D从CPU1迁移到CPU0) ，从而实现负载均衡。

6.6 Linux 进程调度#

• 调度单位: 线程 (内核级线程，Linux中称为’进程’或’任务’) 。

• 进程分类与调度策略:

  • 实时进程 (Real-time Processes):
    • 要求：调度延迟最低，立即响应。
    • 策略：SCHED_FIFO (静态优先级，非抢占式，除非更高优先级到达或阻塞)、SCHED_RR (静态优先级，抢占式，带时间片轮转)。优先级范围 1-99。
  • 普通进程 (Normal Processes):
    • 包括交互式进程 (需要快速响应) 和批处理进程 (后台运行，容忍延迟) 。
    • 策略：SCHED_NORMAL (也叫 SCHED_OTHER), SCHED_BATCH, SCHED_IDLE。主要由 CFS (Completely Fair Scheduler) 算法管理。优先级范围 100-139 (对应nice值 -20 到 +19)。

• Linux调度算法演化:

  • Linux 2.4: 简单 O(n) 调度器。基于优先级和时间片。遍历整个运行队列找最高优先级进程。所有进程时间片用完后统一重新计算。对交互式进程通过剩余时间片补偿来提升优先级。缺点: 扩展性差 (高负载时慢) ，交互性优化不完善，非抢占内核。
  • Linux 2.6 (早期): O(1) 调度器 (by Ingo Molnar):
    • 引入 active/expired 两个优先级数组队列。调度只需 O(1) 时间找到最高优先级非空队列。
    • 动态优先级基于静态优先级(nice值)和平均睡眠时间 bonus 计算，试图区分交互式/批处理。
    • 进程时间片用完后移入 expired 队列 (除非是特殊情况) 。active 队列空后，交换 active 和 expired 指针。
    • 缺点: 区分交互式的启发式规则复杂难懂且易失效，代码难维护。
  • Linux 2.6 (中期): SD (Staircase Scheduler by Con Kolivas) / RSDL (Rotating Staircase Deadline Scheduler):
    • 追求公平，抛弃复杂动态优先级。
    • SD: 进程用完时间片后优先级降低一级 (下楼梯) ，到底后回到较高层并获更多时间片。交互进程睡眠时停留在高层，唤醒后响应快。
    • RSDL: 引入 group quota (Tg) 和 expired 数组。高优先级组用完 Tg 后整体降级 (minor rotation) ，保证低优先级任务的可预测等待时间。时间片用完进 expired 队列。active 队列空或到底后触发 major rotation (交换 active/expired)。
    • 影响: 启发了CFS的公平思想。
  • Linux 2.6.23 至今: CFS (Completely Fair Scheduler by Ingo Molnar):
    • 核心思想: 完全公平。理想情况下，每个进程获得 1/n 的CPU时间。不再区分交互式/批处理，不再使用固定时间片。
    • 虚拟运行时间 (vruntime): vruntime 记录进程的加权运行时间。vruntime 增长速度与实际运行时间成正比，与进程权重 (优先级) 成反比。 vruntime ≈ 实际运行时间 * (NICE_0_LOAD / 进程权重) (NICE_0_LOAD 是 nice=0 进程的权重)。
    • 调度决策: 总是选择就绪队列中 vruntime 最小 的进程运行。
    • 数据结构: 使用 红黑树 (Red-Black Tree) 存储就绪进程，按 vruntime 排序。插入、删除、查找最小节点都是 O(log n) 时间。调度器取最左节点运行。
    • 公平性实现: 优先级高的进程权重高，vruntime 增长慢，更容易被选中；优先级低的进程权重低，vruntime 增长快。最终达到按权重比例分配CPU时间的效果。
  • Linux 6.6+ (实验性/可选): EEVDF (Earliest Eligible Virtual Deadline First):
    • 对CFS的改进，旨在解决CFS在极短任务和延迟敏感任务上的一些问题，进一步改善延迟和公平性。它结合了虚拟时间和截止时间的概念。

• CFS 调度器详解:

  • task_struct: Linux 进程/任务描述符。

  • sched_entity: 调度实体，嵌入 task_struct 中，包含CFS调度所需信息 (如 load_weight 权重, rb_node 红黑树节点, vruntime 等) 。一个 sched_entity 可以代表一个任务或一个任务组 (用于组调度) 。

  • sched_class: 调度类结构体，定义了一套调度器操作函数接口 (如 enqueue_task, dequeue_task, pick_next_task) 。CFS, RT(FIFO/RR), Idle 都有自己的 sched_class 实现。内核按优先级顺序查询 sched_class 来决定使用哪个调度器。

  • cfs_rq: CFS 运行队列，每个CPU有一个。包含红黑树 tasks_timeline 和 min_vruntime 等信息。min_vruntime 记录该队列中所有进程的最小 vruntime，作为新进程/唤醒进程 vruntime 计算的基准。

  • 红黑树 (rb_node, rb_root tasks_timeline): 按 vruntime 组织就绪的 sched_entity。

  • CFS 关键情景:

    • 新进程创建 (fork()):
      • vruntime 初始值通常设为当前 cfs_rq->min_vruntime (或略大) ，确保新进程不会立即获得过多优势。
      • 父子 vruntime 交换? 如果设置了sysctl_sched_child_runs_first，且父子在同CPU，父vruntime < 子vruntime，则交换，让子进程优先运行。
      • 插入红黑树。
      • 检查是否需要抢占当前进程。
    • 进程唤醒 (wake_up_process()):
      • 调整 vruntime：通常设为 max(waker->vruntime, cfs_rq->min_vruntime - delta)，其中 delta 是一个小的补偿值。确保进程不会因睡眠获得不公平优势，但也给予一定补偿使其尽快运行。
      • 插入红黑树。
      • 检查是否需要抢占当前进程 (如果唤醒进程 vruntime 足够小) 。
    • 时钟中断 (scheduler_tick()):
      • 更新当前运行进程的 vruntime (actual_runtime * NICE_0_LOAD / weight) 。
      • 更新 cfs_rq->min_vruntime。
      • 检查当前进程是否已运行超过其“理想运行时间” (基于调度周期和权重计算得出) 。如果是，则设置抢占标记 (TIF_NEED_RESCHED)，在中断返回前会调用 schedule()。
    • 主动调度 (schedule()):
      • 当前进程阻塞、yield 或被标记抢占时调用。
      • 更新当前进程 vruntime。
      • 如果当前进程仍是就绪态，将其重新插入红黑树。
      • 调用 pick_next_task() 选择下一个运行进程：
        • 按优先级查询 sched_class (RT -> CFS -> Idle)。
        • CFS 中，通常选择红黑树最左节点 (vruntime 最小者) 。
        • 特殊情况：考虑 cfs_rq->next (上次被抢占者) 和 cfs_rq->last (刚运行完者) 的缓存亲和性，可能优先选择它们。
      • 从红黑树中移除被选中进程的 sched_entity。
      • 执行上下文切换 (context_switch())。

  • CFS 与进程状态转换图示:

    graph TD
        New -- fork() --> Ready(Ready State: In Red-Black Tree);
        Ready -- schedule() selects --> Running(Running State);
        Running -- Block (I/O, wait) --> Blocked(Blocked State);
        Blocked -- Wakeup --> Ready;
        Running -- Timeslice Check in Tick / Preempted --> Ready;
        Running -- exit() --> Terminated(Terminated State);
    
        subgraph CFS Logic
            direction LR
            Ready -- select min vruntime --> Running;
            Running -- update vruntime & re-insert --> Ready;
        end

    mermaid

7. 重点小结#

• 调度基本概念: 层次 (长/中/短程) 、时机、上下文切换 (过程、开销) 。
• 进程行为: I/O密集型 vs. CPU密集型。
• 设计目标: 吞吐量、周转时间、响应时间、公平性、实时性等，需权衡。
• 典型算法:
  • 批处理: FCFS, SJF/SRTN, HRRN。
  • 交互式: RR, Priority (含反转问题), 多级队列, 多级反馈队列。
  • 实时: RM, EDF。
• 关键设计点: 优先级 (静/动) 、队列组织、抢占、时间片。
• 核心原则: 机制与策略分离。
• 实例分析: Windows 线程调度 (优先级、时间配额、提升机制) 、Linux 进程调度 (演化、CFS核心思想、vruntime、红黑树) 。
• 多处理器调度: SMP、负载均衡、缓存亲和性、工作窃取。