from mosaic import *
OS2023(10)

10. 并发控制：同步 (2)

Changelog & 反馈

• 反馈：括号模型消灭了并行的可能性？
• 课堂展示 model 代码不再有讨厌的黄线
• thread.h 和 thread-sync.h 可以按任意顺序引用

背景回顾：我们分析了同步的本质需求：两个并发的线程等待某个同步条件达成，完成时间线的 “交汇”。相应地，我们有了条件变量实现同步，并且解决了生产者-消费者问题 (括号打印问题)。

本讲内容：另一种共享内存系统中常用的同步方法：信号量 (E. W. Dijkstra)

• 什么是信号量
• 信号量适合解决什么问题
• 哲 ♂ 学家吃饭问题

slideshow('10.1')

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

model('m/pc-sem.py', check=True)

 1N, Tp, Tc = 2, 3, 3
 2
 3def Tproduce(nm):
 4  while not (heap.empty > 0):  # P(empty)
 5    sys_sched()
 6  heap.empty -= 1
 7  sys_sched()
 8
 9  sys_write('(')
10  sys_sched()
11
12  heap.fill += 1  # V(fill)
13
14def Tconsume(nm):
15  while not (heap.fill > 0):  # P(fill)
16    sys_sched()
17  heap.fill -= 1
18  sys_sched()
19
20  sys_write(')')
21  sys_sched()
22
23  heap.empty += 1  # V(empty)
24
25def main():
26  heap.fill = 0
27  heap.empty = N
28
29  for i in range(Tp):
30    sys_spawn(Tproduce, f'Tp{i+1}')
31  for i in range(Tc):
32    sys_spawn(Tconsume, f'Tc{i+1}')
33
34# Outputs:
35# (()())
36# (())()
37# ()(())
38# ()()()

slideshow('10.2')

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

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

slideshow('10.3')

demo('pc-sem', 'c/philosopher.c', libs=['thread.h', 'thread-sync.h'])

Take-away Messages

信号量是一种特殊的条件变量，而且可以在操作系统上被高效地实现，避免 broadcast 唤醒的浪费：

void P() {
  WAIT_UNTIL(count > 0) {
    count--;
  }
}
void V() {
  atomic {
    count++;
  }
}

同时，我们也可以把信号量理解成袋子里的球，或是管理游泳池的手环，因此它在符合这个抽象时，能够带来优雅的代码。

更重要的是，但凡我们能将任务很好地分解成少量串行的部分和绝大部分 “线程局部” 的计算，那么生产者-消费者和计算图模型就能实现有效的并行。精心设计的分布式同步协议不仅可能存在正确性漏洞，带来的性能收益很可能也是微乎其微的。

课后习题/编程作业

1. 阅读材料

教科书 Operating Systems: Three Easy Pieces:

• 第 31 章 - Semaphores

2. 编程实践

运行示例代码并观察执行结果，有兴趣的同学可以试着用信号量实现条件变量——当然，仅仅有一个实现是不够的，你应当尽可能地压力测试它。

---

   苏 ICP 备 2020049101 号