from mosaic import *
OS2023(6)

6. 并发控制基础

Changelog & 反馈

• L0 & M1 都已经发布
  • 框架代码存在缺陷，请 3.7 18:00 前下载框架代码的同学重新下载
  • 校外无法访问 git.nju.edu.cn 是暂时的 (优先保证上课同学的体验)
• 增加了 🌶️ 的标记 (扩展内容)
• 修复了 lecture notes 的 bugs
• 其他内容会慢慢实现/修复 😂

背景回顾：虽然 “线程库” 入门简单，但多处理器编程 + 编译优化会给我们带来很多意想不到的惊喜。在编写多线程程序时，们必须放弃许多对顺序程序编程时的基本假设，这也是并发编程困难的原因。

本讲内容：并发编程困难不代表我们只能摆烂——我们还可以创造出新的手段，帮助我们编写正确的并发程序：

• 互斥问题和 Peterson 算法
• Peterson 算法的正确性和模型检验
• Peterson 算法在现代多处理器系统上的实现
• 实现并发控制的硬件和编译器机制

slideshow('6.1')

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

 1def T1():
 2  while heap.lock != '✅':
 3    sys_sched()
 4  sys_sched()
 5  heap.lock = '❌'
 6  sys_write('❶')
 7
 8def T2():
 9  while heap.lock != '✅':
10    sys_sched()
11  sys_sched()
12  heap.lock = '❌'
13  sys_write('❷')
14
15def main():
16  heap.lock = '✅'
17  sys_spawn(T1)
18  sys_spawn(T2)
19
20# Outputs:
21# ❶❷
22# ❷❶

上面的代码展示了两个线程同时试图获得锁时同时进入临界区的行为。注意 $T_1$ 和 $T_2$ 都没有释放锁，因此如果互斥实现正确，我们应该只能看到 ❶ 或 ❷。如果我们修改代码，会发现第 4 行和 第 11 行的 sys_sched() 对于触发同时进入临界区是必不可少的：如果没有这个 sys_sched，检查 heap.lock 是否锁定和设置锁定状态就在模型中成为了不可打断的原子操作。

slideshow('6.2')

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

 1def T1():
 2  while True:
 3    heap.x = '🏴'
 4    sys_sched()
 5    heap.turn = '❷'
 6    sys_sched()
 7    while True:
 8      t = heap.turn
 9      sys_sched()
10      y = heap.y != ''
11      sys_sched()
12      if not y or t == '❶':
13        break
14    sys_sched()
15    heap.cs += '❶'
16    sys_sched()
17    heap.cs = heap.cs.replace('❶', '')
18    sys_sched()
19    heap.x = ''
20    sys_sched()
21 
22def T2():
23  while True:
24    heap.y = '🏁'
25    sys_sched()
26    heap.turn = '❶'
27    sys_sched()
28    while True:
29      t = heap.turn
30      sys_sched()
31      x = heap.x
32      sys_sched()
33      if not x or t == '❷':
34        break
35      sys_sched()
36    sys_sched()
37    heap.cs += '❷'
38    sys_sched()
39    heap.cs = heap.cs.replace('❷', '')
40    sys_sched()
41    heap.y = ''
42    sys_sched()
43
44def main():
45  heap.x = ''
46  heap.y = ''
47  heap.turn = ''
48  heap.cs = ''
49  sys_spawn(T1)
50  sys_spawn(T2)

Peterson 算法比那些 “玩具” 的例子复杂得多，“随时随地” 都有发生线程切换的可能性。这些可能性对于手工枚举来说，已经有些太过琐碎了——这也是在很长一段时间里，大家给出错误互斥算法的原因。而诸如 “x, y, turn”、“0、1” 这些抽象的数值，进一步增加了人脑在思考这些问题时的负担。我们使用 Emoji 来缓解这一点——例如用 🏴 表示第一个线程举起旗子希望进入临界区。这比 x = 1 要更直观。

即便如此，你在阅读模型检查器的输出时依然感到很琐碎。状态图的可视化还有很大改进的空间。

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

对于 “到底哪一个 barrier 是不可缺少” 这个问题已经超出了本门课程的讨论范围。我们试图用这个例子向大家传递一个思想：除非你对多处理器并发有足够的理解，请不要自作主张写聪明的并发程序。在 99.9% 的情况下，你都可以在不触及此类底层行为的前提下优化你的代码。

slideshow('6.3')

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

Take-away Messages

并发编程 “很难”：想要完全理解并发程序的行为，是非常困难的——我们甚至可以利用一个 “万能” 的调度器去帮助我们求解 NP-完全问题。因此，人类应对这种复杂性的方法就是退回到不并发。通过互斥实现 stop/resume the world，我们就可以使并发程序的执行变得更容易理解——而只要程序中 “能并行” 的部分足够多，串行化一小部分也并不会对性能带来致命的影响。

课后习题/编程作业

1. 阅读材料

继续阅读教科书 Operating Systems: Three Easy Pieces 第 5 次课布置的阅读材料：

• 第 25 章 - Dialogue on Concurrency
• 第 26 章 - Concurrency and Threads
• 第 27 章 - Thread API

2. 编程实践

确保你运行、理解课堂上的示例代码。完成编程实验。

---

   苏 ICP 备 2020049101 号