第 18 讲：临界区、信号量、管程与 IPC

并发问题的根并不是“两个程序同时存在”，而是它们对共享可变状态的操作可以相互穿插。解题时要先找出共享状态和必须保持的不变式，再选锁或信号量；不是先随便写几个 P/V 再猜。

临界资源与临界区

  • 临界资源：同一时刻只允许有限执行流访问的资源；
  • 临界区：程序中访问该共享资源的代码区段；
  • 互斥：不允许多个执行流同时进入相关临界区；
  • 同步：因为合作逻辑，一个执行流必须等另一个到达某个状态或先完成某事。

互斥管“不能同时”，同步管“必须按某个先后”。生产者—消费者同时需要两者：操作缓冲区时互斥，空/满状态之间同步。

正确的临界区管理要求

  1. 互斥：同时最多一个执行流在临界区；
  2. 空闲让进/有限进展：临界区空闲且有人申请时，不能无限拖延；
  3. 有限等待：一个申请者不能永远被后来者插队；
  4. 不对进程相对速度作不现实假设；
  5. 临界区内不应停留无限时间。

“忙则等待”本身不规定是自旋还是阻塞；那是后续机制的选择。

纯软件互斥：Peterson 为什么有两个变量

对两个执行流 i,ji,j，Peterson 算法的概念伪代码：

want[i] = true
turn = j
while want[j] && turn == j:
    wait

critical section

want[i] = false
  • want[i] 表达“我想进”；
  • turn=j 表达“如果我们同时想进，先让对方”。

只有 want 时，双方可同时看到对方想进而永久礼让；只有 turn 又会强制严格轮流，即使对方根本不想进也阻塞。两者结合才在冲突时破对称。

Peterson/Dekker 的课件证明建立在对共享读写顺序的假设上。在现代编译器和弱内存序多核上，真正实现还需原子类型与内存序，不能把普通 C 变量代码当现代锁。

Bakery 算法：把两人礼让扩展到 nn 人

每个进程先“取号”：

number[i]=1+max⁡jnumber[j].number[i]=1+\max_j number[j].

再按字典序 (number[i],i)(number[i],i) 等待：号小者先；号相同时进程 ID 小者先。choosing[i] 表示进程 ii 正在取号，其他人要等它把号码完整公布，避免读到一个半完成状态。

它展示了用纯读写构造 nn 进程互斥的思路，但软件自旋开销与内存模型问题使实用系统更常用硬件原子原语。

硬件原子原语和自旋锁

为什么不能只“先检查再写”

if lock == 0:   # 两个 CPU 都可能读到 0
    lock = 1    # 然后都写成 1

检查与写入之间可被插入，所以需要一条不可分割的读—修改—写操作：

  • test-and-set 返回旧值并同时把锁设为已占用；
  • swap/xchg 原子交换寄存器与锁字；
  • MIPS LL/SC 先建立保留，只有期间未被其他写破坏时条件写成功；
  • CAS 只在内存值仍等于预期值时替换。

自旋锁得不到锁就循环重试，不发生阻塞/唤醒切换，适合持锁极短且多核上锁很快会释放的场景。等待时间长或单核上持锁者尚未运行时，自旋只会浪费 CPU。

关中断可防止单 CPU 上当前内核执行流被本地中断打断，但不能阻止其他 CPU 同时访问，也不能把关中断权限给用户程序。

信号量：用阻塞代替长时间忙等

课件将一般信号量理解为整数 value 加等待队列。一种常见定义是：

P(S):
    S.value--
    if S.value < 0:
        block current process on S.queue

V(S):
    S.value++
    if S.value <= 0:
        wake one process from S.queue

这两个操作自身必须是原子的。在这套语义下：

  • value > 0 表示还有多少个可用资源/token；
  • value == 0 表示暂无余量、但尚无等待者；
  • value < 0 的绝对值表示等待队列中的进程数。

有些教材把计数值始终保持非负，另外记等待队列；做题要先确认采用哪套 P/V 定义，不要混用不变式。

AND 型与一般信号量集

若进程必须同时拿到多类资源，逐个 P 可能形成“各拿一部分再互等”。课件的 AND 型信号量集把一组条件作为一次原子申请：所有资源都够才一起扣减，否则一项也不占并阻塞。一般信号量集再允许每个资源指定“至少达到多少才可执行”以及“一次扣减多少”，把互斥、有限并发和批量资源申请统一描述。

它能避免申请过程中的请求并保持，但不是万能死锁消除器：程序在信号量集之外已经持有的锁、释放次序以及其他条件仍可能构成环；实现还需原子检查多项并维护等待队列，成本高于单个信号量。

二元信号量做互斥

semaphore mutex = 1

P(mutex)
critical section
V(mutex)

P 必须在进临界区前，V 必须在离开后；不能在持有一把锁时无边界等另一个可能由同类执行流释放的条件。

Rendezvous：两边都到了才走

要求 a1 在 b2 之前，b1 在 a2 之前：

semaphore aArrived = 0
semaphore bArrived = 0

Thread A:                 Thread B:
    a1                        b1
    V(aArrived)               V(bArrived)
    P(bArrived)               P(aArrived)
    a2                        b2

初值必须为 0，因为“到达事件”初始尚未发生。先 V 自己已到，再 P 等对方，避免双方都先等对方造成死锁。

Barrier：nn 个线程都到达

用 count 统计已到达线程，修改 count 必须互斥。第 nn 个到达者打开闸门，再让所有线程通过。如果 barrier 要重复使用，还必须在下一轮前将 count 安全归零并关闭闸门，单个信号量的一次性方案不能直接循环复用。

信号量顺序为什么重要

有界缓冲区中，生产者若先拿 mutex，再等 empty：

P(mutex)
P(empty)

当缓冲区已满，生产者持有 mutex 后阻塞在 empty；消费者要消费并产生 empty，却进不了 mutex，死锁。正确顺序是先等待数量条件，再拿缓冲区互斥锁。

经典问题一：生产者—消费者

容量 NN 的有界缓冲区：

semaphore empty = N
semaphore full = 0
semaphore mutex = 1

Producer:                  Consumer:
    produce item               P(full)
    P(empty)                    P(mutex)
    P(mutex)                    remove item
    insert item                 V(mutex)
    V(mutex)                    V(empty)
    V(full)                     consume item

不变式是 empty + full = N。mutex 只保护对缓冲区结构的短操作，真正生产/消费的长时间计算应在锁外，否则并发度被白白降低。

经典问题二：读者—写者

要求读—读可并发，读—写和写—写互斥。读者优先方案：

int readcount = 0
semaphore rmutex = 1     # 保护 readcount
semaphore resource = 1   # 保护共享数据

Reader:
    P(rmutex)
    readcount++
    if readcount == 1: P(resource)
    V(rmutex)

    read

    P(rmutex)
    readcount--
    if readcount == 0: V(resource)
    V(rmutex)

Writer:
    P(resource)
    write
    V(resource)

第一个读者替整个读者群占有 resource，最后一个读者释放。这套方案可能让写者饥饿；写者优先又可能延迟新读者。题目如果要求公平，需再加排队/入口闸门，不能只写“一把读锁一把写锁”。

经典问题三：哲学家就餐

每个人先拿左筷、再拿右筷，五人可能各拿一支后形成环路死锁。课件给出的思路包括：

  • 最多只允许 4 个哲学家同时尝试拿筷子；
  • 规定所有人按筷子统一编号递增申请；
  • 某一人反向拿，破坏对称环；
  • 一次原子地申请两支，不成功就一支都不占。

这些方法本质上分别破坏死锁所需的请求保持或循环等待条件。

管程：把共享状态和同步约束放在一起

管程封装：

  • 共享数据；
  • 操作这些数据的过程；
  • 互斥进入机制；
  • 用于条件同步的 condition variable。

对条件变量 x：

  • x.wait() 必定使当前执行流在 x 的队列上阻塞，并释放管程的互斥权；
  • x.signal() 唤醒某个等待者；条件变量不累积“唤醒次数”，没人等时的 signal 不会留下 token。

这与信号量不同：信号量 V 可以提前增加计数，之后的 P 消耗它而不阻塞。Hoare 管程语义中，signal 唤醒的进程立即接管管程，发 signal 者暂时等待；其他管程语义可能是 signal-and-continue，程序要重新检查条件。

裸 sleep/wakeup 若“检查条件”和“真正入睡”不是原子的，会发生 lost wakeup：唤醒恰好落在两者之间，随后进程睡下却再无人唤它。信号量的原子 P、条件变量在持锁状态下的 wait，都在解决这个检查—排队—释放锁不可分割的问题。

IPC：同步不等于传数据

信号量和管程擅长传递状态/协调顺序，但进程间还需要传递大量数据：

机制关键性质
无名管道半双工字节流，常用于有亲缘关系进程
命名管道/FIFO有文件系统名称，无亲缘进程也可打开
消息传递/消息队列内核维护消息边界与排队，send/receive
共享内存多进程页表映射同一页框，拷贝少，但必须自行同步

共享内存快不代表它自动正确。它只解决“两个进程都能看到这些字节”，并不解决“谁何时可写、读到的是否完整”。

同步题的稳定解法

  1. 写出共享状态和容量/计数不变式；
  2. 区分互斥约束与先后/数量同步约束；
  3. 每个独立条件用独立信号量，初值是当初已存在的资源/token 数；
  4. 先等数量条件，再持有短临界区互斥锁；
  5. 为每个 P 找到可能执行对应 V 的路径，检查环路等待；
  6. 模拟边界情况：缓冲区空/满、第一/最后读者、所有人同时到达。

写完伪代码后还要问：是否互斥？是否可能死锁？是否有饥饿？是否把长计算放进了临界区？四个问题都过，方案才不只是“看起来有 P/V”。

评论