03 · 调度与并发同步：CPU 分给谁，共享数据谁先动

这篇有两个主题，它们其实是同一件事的两面：调度决定"谁用 CPU"，同步决定"谁用共享数据"。

一句话本质

• 调度：CPU 只有一个（或几个），程序有一堆，按什么规则排队。
• 同步：多个执行流要改同一份数据，怎么保证不出错且不太慢。

生活类比：餐厅后厨

概念	餐厅
调度器	排号叫号的服务员
时间片	每桌限时 10 分钟，到点必须让位
优先级	有预约的客人可以插队
互斥锁	灶台只有一口锅，谁占了别人只能等
自旋锁	站着一直盯着锅，不坐下（不释放 CPU）
读写锁	菜谱可以多人同时看（读），但要改菜谱必须清场（写）
死锁	厨师 A 拿着刀等锅，厨师 B 拿着锅等刀
条件变量	等汤炖好，先睡一会，好了叫你

核心机制

一、调度算法（只要记住"为什么演进"）

FCFS（先来先服务）
  +- 问题：一个长任务堵在前面，后面全等 >  convoy effect（护航效应）
      v 改进：谁短谁先
SJF（短作业优先）
  +- 问题：长任务可能永远排不上（饥饿）；而且"运行时间"根本预知不了
      v 改进：给个时间片，轮着来
RR（时间轮转）
  +- 问题：所有进程一视同仁，交互式任务和后台批处理没区别
      v 改进：分优先级 + 动态调整
多级反馈队列（MLFQ）
  +- 新进程进最高优先级队列，用完时间片就降级；
     高优先级队列时间片短，低优先级时间片长；
     定期把所有人提回最高优先级（防饥饿）

MLFQ 是实际系统的主流思路（Linux 的 CFS 是另一种：按"已用 CPU 时间"排序，用红黑树维护，谁用得少谁先上，追求公平而非优先级）。

必考点：抢占 vs 非抢占

• 抢占式：时间片到、或有更高优先级任务到达，立即切换。现代系统都是抢占式。
• 非抢占式：进程自己让出才切换。实现简单，但一个死循环能卡死整个系统。

二、锁：三种粒度

① 互斥锁（Mutex）—— 抢不到就睡
   线程 A 拿锁 > 线程 B 来抢 > B 被挂起，进等待队列 > A 释放 > 唤醒 B
   优点：不浪费 CPU
   缺点：挂起/唤醒要走内核，开销约 1~2 微秒

② 自旋锁（Spinlock）—— 抢不到就转圈
   线程 B：while (锁没拿到) { }   < 一直占着 CPU 空转
   优点：没有内核开销，锁持有时间极短时更快
   缺点：空转烧 CPU；单核上毫无意义（占着 CPU 别人没法释放锁）

③ 读写锁（RWLock）—— 读读并行，读写/写写互斥
   适合"读多写少"。但写操作可能被源源不断的读饿死（需公平策略）

怎么选：临界区极短（几十条指令）用自旋；可能阻塞（有 IO、可能等很久）用互斥。这也是为什么内核里大量用自旋锁（临界区都是纯内存操作），用户态程序几乎只用互斥锁。

三、死锁：四个必要条件 + 四种处理策略

四个条件（必须同时满足才会死锁）：

① 互斥      资源不能被共享，一次只能一个占
② 持有并等待 占着一个，同时还在等另一个
③ 不可剥夺   别人不能强行抢走我占的资源
④ 循环等待   存在一个环：A 等 B，B 等 A

破一个就能破死锁，这决定了四种策略：

策略	做法	现实中的例子
预防	破坏某个条件。最常用是破坏"循环等待"：所有资源按全局顺序申请	数据库规定"按主键顺序加锁"
避免	分配前算一下"给了会不会不安全"（银行家算法）	实际很少用，要预知最大需求
检测+恢复	定期查资源分配图有没有环，有就回滚/杀进程	数据库的死锁检测（超时 + 等待图）
鸵鸟策略	假装看不见，死锁概率极低就不管	大多数 OS 的选择

为什么"按顺序申请"能破死锁：如果所有人都按 A>B>C 的顺序申请，就不可能出现"A 拿 B 等 A"这种环——因为要形成环，必须有人逆序申请。

四、无锁：CAS 与它的坑

// 伪代码：比较并交换（CPU 提供的一条原子指令）
bool CAS(int* addr, int expected, int new_val) {
    if (*addr == expected) { *addr = new_val; return true; }
    return false;
}

为什么无锁快：没有"挂起/唤醒"的内核开销，失败就重试，纯用户态完成。适合冲突少的场景。

三个坑：

1. ABA 问题：值从 A 改成 B 又改回 A，CAS 以为"没变过"就成功了，但实际上中间状态被改过。解法：加版本号（AtomicStampedReference）。
2. 自旋开销：冲突激烈时，大量线程空转重试，CPU 全烧在失败上。
3. 只能保护单个变量：多个变量要一起改，CAS 做不到（需要锁或事务内存）。

五、条件变量：解决"等"的问题

生产者：
  lock(mutex)
  while (队列满了) wait(cond_not_full, mutex)   < wait 会原子地释放锁并睡眠
  放入元素
  signal(cond_not_empty)                        < 唤醒一个消费者
  unlock(mutex)

消费者：
  lock(mutex)
  while (队列空了) wait(cond_not_empty, mutex)
  取出元素
  signal(cond_not_full)
  unlock(mutex)

两个必考细节：

1. 为什么用 while 不用 if？ 因为被唤醒后，条件可能又被别人改回去了（虚假唤醒 + 竞争）。必须重新检查。
2. wait 为什么要"原子地释放锁"？ 如果先释放锁再睡，中间可能错过 signal（生产者在你睡之前就通知了），导致永久等待。

为什么这么设计

反事实 1：如果不用时间片，会怎样

一个死循环程序会永久占住 CPU，整个系统假死。这就是早期非抢占式系统（如 Windows 3.1）频繁蓝屏/卡死的原因。

反事实 2：如果锁不存在，会怎样

i++ 在汇编层是三步：
  ① 从内存读 i 到寄存器
  ② 寄存器加 1
  ③ 写回内存

两个线程同时执行，可能都读到 i=5，都加 1 写回 6。两次自增，结果只加了 1。这就是"数据竞争"，它的可怕之处是偶发——测试环境跑一万次都对，线上高并发时出错。

反事实 3：如果只有锁、没有 CAS，会怎样

所有并发控制都要走内核挂起/唤醒。高并发下（比如 100 个线程抢一个计数器），大部分时间花在"睡下、被叫醒"上，吞吐量极低。CAS 让"抢不到"变成"重试一下"，在低冲突时几乎零成本。

面试怎么问

Q：死锁的四个必要条件？怎么预防？

四个条件背完，重点在**"破坏哪一个"**：最实用的是破坏循环等待——所有线程按同一全局顺序申请锁。其次是破坏持有并等待——一次性申请所有资源（代价是利用率低）。

Q：自旋锁和互斥锁怎么选？

看临界区长度和是否可能阻塞。 临界区只有几条指令、且确定不会阻塞 > 自旋（省掉内核切换）。 可能等 IO、或者临界区较长 > 互斥（自旋会白烧 CPU）。 单核 CPU 上不要用自旋锁（占着唯一的核，持有者永远没法运行来释放锁）。

Q：CAS 有什么问题？

三个：ABA、自旋开销、只能保护单个变量。ABA 用版本号解决。

Q：为什么 wait 必须放在 while 里？

两个原因：① 虚假唤醒（OS 可能无故唤醒）；② 唤醒后条件可能已不成立（被别的线程抢走了）。用 if 只检查一次，会带着错误的前提继续执行。

追问链：

死锁怎么产生？
  > 四个必要条件是什么？
    > 破坏哪个最实用？（循环等待 > 全局顺序）
      > 数据库怎么处理死锁？（等待图 + 回滚代价最小的那个事务）
        > 那不用锁行不行？（CAS 无锁）
          > CAS 有什么坑？（ABA / 自旋 / 单变量）

和其他知识的连接

• < 来自 进程与线程：谁在跑，跑的时候带着什么：线程是调度的基本单位，共享堆是加锁的原因
• < 来自 虚拟内存：让每个程序都以为自己独占一台机器：抖动的解法之一是"降低多道程度"，属于调度范畴
• > 影响 IO 模型与零拷贝：等设备的时候，CPU 在干什么：阻塞 IO 让进程进入阻塞态，触发调度；IO 多路复用是"用一次等待处理多个 fd"
• > 影响 隔离级别与 MVCC：MVCC 就是为了减少加锁，用"读旧版本"替代"读时加锁"
• > 影响 锁与死锁：数据库死锁与 OS 死锁同源，但多了"间隙锁"这种粒度
• > 影响 语言层：Java 的 synchronized（管程）、AQS（CLH 队列 + CAS）、Go 的 channel（CSP）都是这套理论的不同包装

自测 3 问

Q1：为什么"按全局顺序申请锁"能避免死锁？

点开看答案

因为死锁的第四条件是"循环等待"，而循环等待要求存在一个环：A 等 B 的资源，B 等 A 的资源。

如果所有人按 A>B>C 的固定顺序申请，那么"持有 B 等 A"这种情况不可能发生（因为拿 B 之前必须先拿到 A）。没有逆序申请，就构不成环。

代价：可能降低并发度（本来可以并行申请的锁，现在必须串行），也可能需要开发者知道全局顺序（跨模块时很难保证）。

Q2：单核 CPU 上用自旋锁为什么没意义？

点开看答案

因为只有一个核。线程 B 自旋时，占着唯一的 CPU 空转，持有锁的线程 A 根本没有机会运行来释放锁。

结果就是 B 一直转到时间片用完，被强制换下，A 才有机会跑。自旋期间 CPU 100% 被浪费。

所以单核上应该用互斥锁（让 B 睡下，把 CPU 让给 A）。自旋锁的前提是"持有者能在另一个核上并行运行"。

Q3：乐观锁和悲观锁，本质区别是什么？

点开看答案

区别在冲突概率的假设，进而决定了"先加锁还是先干活"：

• 悲观锁：假设一定会冲突 > 先加锁再操作 > 冲突时等待。适合写多、冲突多。
• 乐观锁：假设大概率不冲突 > 先操作，提交时用 CAS/版本号检查有没有被别人改过 > 冲突就重试或报错。适合读多、冲突少。

注意：乐观锁不是一种"锁"，它没有任何加锁动作，只是一种"提交时校验"的策略。数据库的 version 字段、Java 的 AtomicInteger 都属于这一类。

类比失效处 / 易错点

• "灶台只有一口锅"会让人以为锁的粒度是固定的。实际上锁可以细到"一个变量"（原子变量）、粗到"整张表"（表锁）。粒度越细并发越高，但管理成本也越高。
• 自旋锁不是"更快的锁"。它只是在特定场景（临界区极短 + 多核）更快，其他场景更慢。
• 死锁 ≠ 饥饿。死锁是"互相等，永远解不开"；饥饿是"一直排不上队，但系统还在动"。活锁又是另一种：大家都在动，但一直互相谦让，谁也没进展。
• volatile 不保证原子性。它只保证可见性和禁止重排序，i++ 依然不安全。这是最经典的面试陷阱。
• "抢占式调度"不代表"随时能抢"。内核态临界区里通常关抢占，否则会破坏内核数据结构。

✅ 验收清单

• 能说出 FCFS > SJF > RR > MLFQ 每一代解决了上一代的什么问题
• 能默写死锁四个必要条件，并对每个条件说出一种破坏手段
• 能说清自旋锁和互斥锁的选择依据（临界区长度 + 是否多核 + 是否可能阻塞）
• 能解释 CAS 的三个坑，并说出 ABA 的解法
• 能解释 wait 为什么必须在 while 里、为什么必须原子地释放锁
• 能用"i++ 三步"讲清数据竞争为什么是偶发的
• 合上书，用自己的话讲 3 分钟，中途不卡壳