CSCI3150 L08 Multiprocessor Scheduling
课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L08 Multiprocessor Scheduling，第 4 部分 / 共 4 部分 · 原件 L08-CPU调度-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.45–64 定位：分清缓存一致性、互斥和缓存亲和性，并从单队列、多队列实例推导负载均衡的需要。 前后：上一份 Part III 承接：#L01-06 非原子共享更新
p.45 Part IV分节页。
多个CPU共享什么
多核与缓存局部性（p.46–47）【新】
p.46 The rise of the multicore processor is the source of multiprocessor-scheduling proliferation.
Multicore: Multiple CPU cores are packed onto a single chip.
Adding more CPUs does not make that single application run faster. You’ll have to rewrite application to run in parallel, using threads.
p.47 By keeping data in cache, the system can make slow memory appear to be a fast one
p.47 Small, fast memories
Hold copies of popular data that is found in the main memory.
Utilize temporal and spatial locality
p.47 Holds all of the data
Access to main memory is slower than cache.
p.46强调程序需要可并行执行的工作，增加核心才可能加速。调度器能把多个执行流放到不同核心，不能把有顺序依赖的一条执行流自动拆开。p.47的缓存保存常用内存数据，利用时间局部性（不久后再次用同一数据）与空间局部性（访问相邻数据）。
补充算例（数字是我为演示取的，讲义没给）：一段工作要先算A结果才能算B，A10ms、B10ms，即使两个核心也不能让B在A完成前开始；若是两个相互独立的10ms任务，则可重叠到约10ms，忽略调度开销。
缓存一致性不是程序互斥（p.48–50）
p.48 Consistency of shared resource data stored in multiple caches.
p.50 Bus snooping
Each cache pays attention to memory updates by observing the bus.
When a CPU sees an update for a data item it holds in its cache, it will notice the change and either invalidate its copy or update it.
图（p.48–49）：两个CPU缓存同一共享地址 元素：CPU0先从内存取D到缓存，随后把自己的缓存更新为D′；CPU1从未更新的内存取得D，结果变旧。 看什么：问题在于同一位置的多个副本未协调，CPU1看到旧值，而不是指针指错地址。
p.50的总线嗅探让缓存观察更新，对自己持有的同一数据选择更新副本或使其失效。补充算例（数字是我为演示取的，讲义没给）：把D=1、D′=2，缺少协调时CPU0认为值为2而CPU1读到1；失效协议让CPU1不能继续使用旧的1，需取得有效新版本。课件用嗅探示例讲机制，不意味着所有机器都采用一条共享总线。
删除链表头为什么仍需锁（p.51–53）【延伸 L01 p.18–22】
p.51 When accessing shared data across CPUs, mutual exclusion primitives should likely be used to guarantee correctness.
课件程序与接口（p.51，原页片段）
1 typedef struct __Node_t {
2 int value;
3 struct __Node_t *next;
4 } Node_t;
5
6 int List_Pop() {
7 Node_t *tmp = head; // remember old head ...
8 int value = head->value; // ... and its value
9 head = head->next; // advance head to next pointer
10 free(tmp); // free old head
11 return value; // return value at head
12 }
课件程序与接口（p.52，原页片段）
1 pthread_mtuex_t m;
2 typedef struct __Node_t {
3 int value;
4 struct __Node_t *next;
5 } Node_t;
6
7 int List_Pop() {
8 lock(&m)
9 Node_t *tmp = head; // remember old head ...
10 int value = head->value; // ... and its value
11 head = head->next; // advance head to next pointer
12 free(tmp); // free old head
13 unlock(&m)
14 return value; // return value at head
15 }
p.53 Keep a process on the same CPU if at all possible
A process builds up a fair bit of state in the cache of a CPU.
The next time the process run, it will run faster if some of its state is already present in the cache on that CPU.
p.53 A multiprocessor scheduler should consider cache affinity
when making its scheduling decision.
p.51读取head、取value、推进head、free旧节点，是多步操作。即使缓存完全一致，两个CPU也可能同时读同一head，随后都使用或释放同一节点。p.52用同一把锁包住整个删除序列，使这段逻辑只允许一个执行者进入；只保护其中一行不能保证整段状态变换正确。
补充算例（数字是我为演示取的，讲义没给）：链表头值7、后继值8。T1/T2同时缓存旧head时都返回7，并可能重复free；加锁后T1取7并推进，T2随后取8。此例假设链表非空，实际空表判断也应在相同保护下完成。
p.53的缓存亲和性则是性能问题：同一进程再次在同一CPU运行，更可能复用热缓存。它不等同于一致性，也不是必须永远禁止迁移。
补充：用原代码逐行定位失去互斥的后果。 假定初始链为 H→N→M，节点都有效，下面只用标签演示一种可能交错。
| 顺序 | T1 | T2 | 共享 head |
|---|---|---|---|
| 1 | 执行 tmp=head，保存 H |
— | H |
| 2 | 暂停 | 完整删除 H，返回 H.value，释放 H | N |
| 3 | 执行 value=head->value，这次读的是 N.value |
已结束这次删除 | N |
| 4 | 执行 head=head->next，跳过 N |
— | M |
| 5 | 执行 free(tmp)，tmp 仍是 H |
— | M |
第一处关键分裂发生在第 3 步：源码重新读取共享 head，而不是保证还在读取先前的 H。到第 5 步又尝试释放已被 T2 释放的 H，违反对象生命周期；N 则已从链上摘掉却未由这段代码释放。这里是定位失败路径的推演，不是在含数据竞争的真实 C 程序里承诺一种固定输出。p.52 必须在取 head 之前拿锁，直到推进与释放结束后才解锁，才能使“保存的旧头、读到的值、推进的链接、释放的对象”属于同一次完整删除。
队列结构决定争用与负载分布
单队列与亲和性安排（p.54–55）
p.54 Single queue Multiprocessor Scheduling (SQMS)
p.54 Put all jobs that need to be scheduled into a single queue.
Each CPU simply picks the next job from the globally shared queue.
Cons:
Some form of locking have to be inserted Lack of scalability
Cache affinity
Example:
Possible job scheduler across CPUs:
p.55 Preserving affinity for most
Jobs A through D are not moved across processors.
Only job e Migrating from CPU to CPU.
Implementing such a scheme can be complex.
p.54让所有CPU从一个共享队列取任务，天然便于看见全局工作，但访问队列需要同步，核心越多越容易争用。下面保留图中前五轮安排。
表（p.54）：普通共享队列的示例
| CPU | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | A | E | D | C | B |
| 1 | B | A | E | D | C |
| 2 | C | B | A | E | D |
| 3 | D | C | B | A | E |
p.55改成A固定在CPU0、B在CPU1、C在CPU2、D在CPU3，让E迁移，保住多数任务的亲和性。
表（p.55）：尽量保留缓存亲和性
| CPU | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | A | E | A | A | A |
| 1 | B | B | E | B | B |
| 2 | C | C | C | E | C |
| 3 | D | D | D | D | E |
算一遍：5轮×4核=20个执行槽，A–E各占4槽；份额相同，但A–D只用一个核心。相同的公平份额可以由不同迁移策略实现，缓存效果可能不同。
补充：共享队列的锁保护的是取任务这一刻。 两个 CPU 同时看到队头 A，如果都把“看看有没有任务”和“从队列删掉它”当成独立动作，就可能把同一条执行流派给两核。需要把选择与移除作为受保护的状态改变。取得任务后若还一直持有全局队列锁运行用户代码，其他核就无法取下一任务，反而失去并行收益；锁的范围应覆盖调度数据结构操作，而不是整个时间片。
缓存亲和性是另一项成本。任务迁移后，即使结果仍正确，原核缓存中的工作数据也可能不在新核缓存中；需重新获取的代价会增加。单纯看到两核利用率都100%仍不能判断吞吐最优，因为时间也可能花在锁争用或缓存通信上。
多队列的好处与负载失衡（p.56–58）
p.56 MQMS consists of multiple scheduling queues.
Each queue will follow a particular scheduling discipline.
When a job enters the system, it is placed on exactly one scheduling queue.
Avoid the problems of information sharing and synchronization.
p.57 With round robin, the system might produce a schedule that looks like this:
p.57 MQMS provides more scalability and cache affinity.
p.56每CPU或每组CPU有独立队列，减少集中争用；任务初始放进一个队列，由该队列的策略调度。p.57示例Q0有A/C，Q1有B/D，各自RR，四者各得到半个核心。
p.58 C结束后，A独占CPU0，B/D仍分享CPU1：A得到1核，B/D各0.5核，A份额是各自两倍。A再结束后CPU0空闲，但CPU1仍有两个就绪任务，整机两核只用一核，利用率50%。这不是没有工作，而是工作被困在另一条局部队列。
图（p.57–58）：两个局部队列 元素：Q0从A→C变为A再为空，Q1始终B→D；CPU时间线随之只剩一侧忙。 看什么：局部队列独立高效不保证全局均衡。
迁移、工作窃取与开销（p.59–61）
p.61 Move jobs between queues
Implementation:
A source queue that is low on jobs is picked.
The source queue occasionally peeks at another target queue.
If the target queue is more full than the source queue, the source will “steal” one or more jobs from the target queue.
Cons:
High overhead and trouble scaling
p.59把B或D移到空的CPU0，剩下一个在CPU1，两核恢复并行。p.60在A与B/D不均衡但两核都忙的情况下，通过逐步迁移分摊CPU时间；图中先迁B到CPU0，再迁A到CPU1。迁移是调整归属，不是复制一个进程让它在两核重复执行同一线程。
p.61的work stealing让较空队列查看较忙队列，取走一部分任务。补充：检查过频会增加同步和迁移开销，过稀又让不均衡持续。迁移还可能损失热缓存，所以要在均衡收益与缓存/同步成本之间取舍。
补充：队列长度不是剩余工作量。 两个队列各有一个任务，只能说明任务个数相等；若一个还需很长服务、另一个马上结束，未来负载并不相等。反过来，任务多的一边若大部分处于 I/O 等待，也不能把那些阻塞任务当成可以立刻移过去运行的工作。迁移决策至少要分清就绪与阻塞，以及数量与实际服务需求。
沿 p.58 的原图，C 结束后两核仍都忙，A 与 B/D 的份额不等；A 再结束后才出现一核空闲。这两个时刻的问题不同：前者主要是份额分配，后者还有可避免的空闲。解释“迁移改善了什么”时要指明是哪一个时刻、哪一种指标，而不是只说队列变平均了。
讲义中的Linux历史例子与收束（p.62–64）
p.63 BF Scheduler (BFS)
A single queue approach
Proportional-share
Based on Earliest Eligible Virtual Deadline First(EEVDF)
p.64 CPU Scheduling
Scheduling metrics: Turnaround time, Response time; Fairness
Scheduling Strategy: FIFO, SJF, PSJF, RR, MLFQ
Simple: FIFO, SJF, PSJF, RR
MLFQ
Proportional Share
Multiprocessor scheduling
Cache coherence
Cache affinity
SQMS, MQMS, Load balance
Next: Memory (Chapters 13, 15, 16, 17, 18, 19, 20, 21, 22, 23)
p.62用O(1)说明动态优先级与多队列，用CFS说明确定性的比例份额与多队列；p.63把BFS列为单队列、比例份额并提到EEVDF。这里仅保留2022未核原件的教学陈述，不据此描述当前Linux默认调度器。
p.64总结调度指标、简单算法、MLFQ、比例份额和多处理器问题。最后需要记住三个不同目标：一致性使缓存副本协调，互斥使多步共享操作安全，亲和性使重复运行更容易命中缓存。它们互不替代。
考试角度：（C 级 通识）常见考法是给局部队列画CPU使用情况，计算份额与空闲率，再判断迁移解决负载问题时可能付出的缓存代价。
自测：两核各有一个任务，为什么有时仍应避免频繁互换？
第一层：负载已经均衡，交换没有解决空闲核问题，却可能丢失热缓存。
第二层：亲和性也不能压倒一切。若一个核排了许多可运行任务、另一个核空闲，迁移能增加实际并行服务。判断应比较剩余工作、队列等待、迁移开销和缓存代价。没有这些条件，不能简单断言“总迁移”或“永不迁移”。
本讲核心考点
- 缓存一致性、锁和亲和性解决不同问题（p.48–53，C 级通识考法）。
- SQMS集中共享队列，需处理争用与迁移（p.54–55，C 级通识考法）。
- MQMS降低集中争用但可能留下空闲核心（p.56–58，C 级通识考法）。
- 迁移与工作窃取在均衡、同步和缓存成本间取舍（p.59–61，C 级通识考法）。
附录
本份没有需要移至附录的长推导；计算过程已在对应页正文写全。
来源与证据
-
原件：L08-CPU调度-2022未核.pptx（本地课件）；PDF副本（本地课件） p.45–64。本文页码均为 PDF 页号。
-
考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无
-
2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。