from mosaic import *
OS2023(7)

7. 并发控制：互斥

Changelog & 反馈

• 修复了 rvemu.c 中的 sext bug (感谢报告的同学；但我找不到消息记录了 😂)
• M2 & Online Judge 上线
• Model checker 阅读体验提升：能够正确显示线程/进程名/进程终止

背景回顾：互斥 (Peterson 算法)：为了掌控并发程序的复杂行为，使程序退回到 “串行执行” 的 lock & unlock。

本讲内容：现代多处理器系统上的互斥实现：

• 互斥问题的定义和假设
• 自旋锁
• 互斥锁和 Futex

slideshow('7.1')

slideshow('7.2')

model('m/spinlock.py', check=True)

 1def Tworker(enter, exit):
 2  for _ in range(2):
 3    while True:
 4      seen = heap.table
 5      heap.table = '❌'
 6      sys_sched()
 7      if seen == '✅':
 8        break
 9    sys_sched()
10    sys_write(enter)
11    sys_sched()
12    sys_write(exit)
13    sys_sched()
14    heap.table = '✅'
15    sys_sched()
16
17def main():
18  heap.table = '✅'
19  sys_spawn(Tworker, '(', ')')
20  sys_spawn(Tworker, '[', ']')
21
22# Outputs:
23# ()()[][]
24# ()[]()[]
25# ()[][]()
26# []()()[]
27# []()[]()
28# [][]()()

demo('sum-spinlock', 'c/sum-spinlock.c', libs=['thread.h'])

slideshow('7.3')

demo('cmpxchg', 'c/cmpxchg.c', libs=['thread.h'])

slideshow('7.4')

demo('sum-scalability', 'c/sum-scalability.c', libs=['thread.h', 'thread-sync.h'])

demo('sum-mutex', 'c/mutex', libs=['thread.h', 'thread-sync.h'])

Take-away Messages

为了实现现代多处理器系统上的互斥，我们首先需要理解 “原子操作” (例如 atomic_xchg) 的假设：

1. 操作本身是原子的、看起来无法被打断的，即它真的是一个 “原子操作”；
2. 操作自带一个 compiler barrier，防止优化跨过函数调用。这一点很重要——例如我们今天的编译器支持 Link-time Optimization (LTO)，如果缺少 compiler barrier，编译优化可以穿过 volatile 标记的汇编指令；
3. 操作自带一个 memory barrier，保证操作执行前指令的写入，能对其他处理器之后的 load 可见。

在此假设的基础上，原子操作就成为了我们简化程序执行的基础机制。通过自旋 (spin)，可以很直观地实现 “轮询” 式的互斥。而为了节约共享内存线程在自旋上浪费的处理器，我们也可以通过系统调用请求操作系统来帮助现成完成互斥。

课后习题/编程作业

1. 阅读材料

教科书 Operating Systems: Three Easy Pieces:

• 第 28 章 - Locks

教科书补充了很多课堂上没有的细节，包括锁更详细的实现；因此阅读教科书是非常重要的。

2. 编程实践

我们鼓励大家参考课堂上调试并发程序的代码 (包括 init.gdb)，自己是使用 GDB 调试并发程序的执行。你可能需要同时阅读 GDB 的文档。

---

   苏 ICP 备 2020049101 号