多处理器调度

一、概述

多处理器调度（multiprocessor scheduling）是操作系统在多核或多CPU系统上分配任务的核心机制。随着多核处理器（multicore）的普及，个人设备普遍具备多个CPU核，但这引入了新的调度挑战。

1.1 背景

• 多核普及：多核处理器因单核性能提升受限（功耗问题）而成为主流，广泛应用于PC、笔记本和移动设备。
• 挑战：
  • 应用并行化：传统单线程程序无法利用多核，需重写为多线程程序以分散任务。
  • 调度复杂性：单处理器调度策略需扩展到多CPU，需解决新问题（如负载均衡、缓存亲和度）。
• 关键问题：如何在多CPU上调度任务？现有技术是否适用？需要哪些新思路？

二、多处理器架构与新问题

2.1 硬件缓存与单处理器

• 缓存作用：
  • 缓存是小型、快速存储，保存内存中热点数据的副本，加速访问（几纳秒vs.内存数十至数百纳秒）。
  • 基于局部性：
    • 时间局部性：最近访问的数据可能再次访问（如循环变量）。
    • 空间局部性：访问某地址后可能访问附近地址（如数组遍历）。
• 单CPU缓存：
  • 程序首次读取数据从内存加载到缓存，后续访问从缓存获取，显著提升性能。

2.2 多处理器缓存一致性

• 问题：
  • 多CPU共享内存，每个CPU有独立缓存，可能导致数据不一致。
  • 示例：
    • CPU 1读取地址A的值D到缓存，修改为D'但未写回内存。
    • CPU 2读取A，从内存获取旧值D，非预期值D'。
  • 称为缓存一致性（cache coherence）问题。
• 硬件解决方案：
  • 总线窥探（bus snooping）：
    • 各缓存监听内存总线，发现数据更新时作废（invalidate）或更新本地副本。
    • 回写缓存（延迟写内存）增加复杂性，但硬件确保一致性。

2.3 同步问题

• 必要性：
  • 尽管硬件保证缓存一致性，应用程序和操作系统仍需同步访问共享数据。
  • 多CPU并发访问（如共享队列）若无同步，可能导致数据错误。

• 示例：共享链表删除：

  c int List_Pop() { Node_t *tmp = head; int value = head->value; head = head->next; free(tmp); return value; }

  • 问题：两线程同时执行，均保存同一head，可能重复删除同一元素或释放内存出错。
  • 解决：加锁（如pthread_mutex_t），在函数首尾加lock()和unlock()，确保原子性。
  • 挑战：
  • 锁保证正确性，但随CPU增加，锁争用降低性能。
  • 替代方案如无锁数据结构复杂，需深入并发知识（见并发章节）。
  • 提示：多处理器调度需结合锁机制，注意性能瓶颈。

2.4 缓存亲和度

• 定义：进程在同一CPU上运行可利用缓存中的状态（如热点数据），提高性能；在不同CPU上运行需重新加载数据，性能下降。
• 目标：调度应尽量让进程保持在同一CPU，维护缓存亲和度。
• 挑战：多CPU调度可能频繁迁移进程，破坏亲和度。

三、单队列多处理器调度（SQMS）

3.1 原理

• 方法：复用单处理器调度架构，使用单一共享队列存放所有任务，多个CPU从队列获取任务。
• 示例：5个任务（A、B、C、D、E），4个CPU，队列顺序A→B→C→D→E，各CPU轮流取任务运行。
• 调度策略：可采用轮转、MLFQ等单处理器策略，选择最优任务（如优先级最高或最短任务）。

3.2 优点

• 简单性：直接扩展单处理器调度，无需大幅修改。
• 负载均衡：单一队列天然平衡任务分配，CPU利用率高。

3.3 缺点

• 可扩展性差：
  • 访问共享队列需加锁确保原子性，随CPU增加，锁争用开销激增，降低性能。
  • 示例：大量CPU竞争队列锁，系统时间多耗费在锁管理而非任务执行。
• 缓存亲和度差：
  • 任务随机分配到CPU，频繁迁移破坏缓存状态。
  • 示例：任务A在CPU 1运行后迁移到CPU 2，需重新加载数据，性能下降。
• 优化尝试：
  • 引入亲和度机制，优先将任务分配到上次运行的CPU。
  • 示例：A、B、C、D固定在4个CPU，E迁移以均衡负载。
  • 挑战：亲和度与负载均衡冲突，需复杂策略权衡。

四、多队列多处理器调度（MQMS）

4.1 原理

• 方法：每个CPU拥有独立调度队列，任务分配到某队列后由对应CPU调度。
• 分配策略：新任务通过启发式规则分配（如随机或选择最空队列）。
• 调度策略：各队列独立运行单处理器调度（如轮转、MLFQ）。
• 示例：4个任务（A、B、C、D），2个CPU，A、B在CPU 0队列，C、D在CPU 1队列，各自轮转调度。

4.2 优点

• 可扩展性强：
  • 队列数随CPU增加，减少锁争用和缓存冲突。
  • 各CPU独立调度，降低同步开销。
• 缓存亲和度好：
  • 任务固定在单一CPU，充分利用缓存状态。
  • 示例：A、B始终在CPU 0运行，缓存数据保持有效。

4.3 缺点

• 负载不均（Load Imbalance）：
  • 队列任务量不均导致CPU利用率差异。
  • 示例：
    • CPU 0队列仅A，CPU 1队列有B、D，A独占CPU 0，B、D共享CPU 1，A获双倍CPU时间。
    • 更糟情况：CPU 0队列为空，CPU 1有B、D，CPU 0闲置。
• 挑战：需动态调整任务分配以均衡负载。

4.4 负载均衡解决方案：工作窃取

• 方法：
  • 工作窃取（Work Stealing）：轻负载CPU定期检查重负载CPU队列，若任务显著较多，从中“窃取”任务。
  • 示例：
    • CPU 0空闲，CPU 1有B、D，CPU 0窃取D，双方各运行一个任务。
    • A独占CPU 0，B、D共享CPU 1，定期迁移B到CPU 0，实现均衡。
• 实现：
  • 轻负载CPU周期性检查其他队列，基于任务量差异决定迁移。
  • 迁移需保存任务状态（如寄存器、栈），通过上下文切换完成。
• 挑战：
  • 检查频率：
    • 过频：增加检查和迁移开销，降低可扩展性。
    • 过稀：负载不均持续，影响公平性和效率。
  • 阈值设置：任务量差异阈值需经验调优，属“黑魔法”。
• 提示：工作窃取需平衡迁移成本与负载均衡收益，避免频繁迁移破坏缓存亲和度。

五、Linux多处理器调度实践

5.1 概述

• Linux未统一多处理器调度方案，存在三种主要调度器：
  • O(1)调度器：多队列，优先级驱动。
  • 完全公平调度器（CFS）：多队列，比例份额。
  • BF调度器（BFS）：单队列，复杂比例调度。

5.2 调度器特点

• O(1)调度器：
  • 方法：基于MLFQ，动态调整优先级，优先调度高优先级任务。
  • 特点：强调交互性，快速选择任务（O(1)复杂度）。
  • 适用：通用工作负载，注重响应时间。
• CFS（Completely Fair Scheduler）：
  • 方法：多队列，类似步长调度，按比例分配CPU。
  • 特点：确保公平性，基于虚拟运行时间（vruntime）选择任务。
  • 适用：追求公平分配的场景。
• BFS（Brain Fuck Scheduler）：
  • 方法：单队列，基于最早最合适虚拟截止时间优先（EEVEF）。
  • 特点：复杂比例调度，优化交互性和公平性。
  • 适用：高交互性需求系统。

5.3 启示

• 单队列（如BFS）和多队列（如O(1)、CFS）均可成功，关键在于优化同步、亲和度和负载均衡。
• 不同调度器针对不同目标（如交互性、公平性），需根据工作负载选择。

六、总结与扩展

6.1 调度方法对比

方法	优点	缺点	适用场景
SQMS	简单，负载均衡好	可扩展性差，缓存亲和度差	小规模多核系统
MQMS	可扩展性强，缓存亲和度好	负载不均需迁移解决，迁移策略复杂	大规模多核系统，注重扩展性

6.2 设计哲学

• 缓存亲和度：优先保持任务在同一CPU，减少缓存失效。
• 可扩展性：多队列降低同步开销，适合多核系统。
• 负载均衡：工作窃取动态调整任务分配，需权衡迁移成本。
• 同步管理：锁确保正确性，但需优化以减少性能瓶颈。
• 黑魔法调优：阈值（如工作窃取频率）依赖经验，需自适应机制。

6.3 扩展与进一步学习

• 调度优化：
  • 研究Linux CFS实现，理解vruntime和红黑树在多核中的应用。
  • 探索实时多核调度（如PREEMPT_RT补丁）。
• 并发与体系结构：
  • 深入学习MESI协议，理解缓存一致性实现。
  • 研究无锁数据结构在多核调度中的应用。
• 性能分析：
  • 使用perf工具测量多核系统锁争用和缓存失效。
  • 分析迁移对TLB和分支预测器性能的影响。
• 源码实践：
  • 阅读Linux内核调度代码（如sched/目录），理解CFS和O(1)实现。
  • 模拟多队列调度，测试工作窃取策略。
• 应用场景：
  • 研究云计算（如Kubernetes）中的多核调度。
  • 探索GPU并行调度与CPU调度的协同。