Yanyan's Wiki 操作系统 (2023)

并发控制：同步

本讲阅读材料

教科书 (Operating Systems: Three Easy Pieces, OSTEP) 第 30-31 章。教材的条件变量和信号量讲得非常棒，因此请大家仔细阅读。

1. 理解线程同步

所谓 “同步” 就是在某个时刻，两个线程达成一个 “互相认同” 的状态，典型的场景：

  • (一起去约会) NPY: 等我洗个头就出门/等我打完这局游戏就来
  • (一起去吃饭) 舍友：等我写完这段代码就吃饭
  • (一起搞科研) 导师：等我出差回来就讨论这个课题

而在计算机中，实现同步最好的办法，就是让先到的线程等待：

  • NPY: 先洗完头的女生等男生玩玩游戏；先打完游戏的男生等女生洗完头 (矛盾的来源)
  • 舍友：先发起吃饭请求的要等舍友写完代码
  • 导师：同学你等等我啊啊啊啊啊啊

通常，实现忙等待 (spinning) 的同步 (等待) 通常都是非常简单的，你需要一个变量 done，然后不断询问条件是否发生即可。如果希望实现 threads.h 中线程的同步 (main 等待所有线程返回)，只需用一个 flag 变量，main_thread不断地 spin 这个变量，直到读出它是 1：

int done[nworkers];

void worker(int tid) {
  done[tid] = 1;
  __sync_synchronize();
}

int main() {
  for (int tid = 0; tid < nworkers; tid++)
    while (!done[tid]);
}

还记得编译优化的故事吗？

我们又回来了：

for (int i = 0; i < N; i++)
    sum++;

这么个简单的循环，在 -O0, -O1, -O2 的时候有截然不同的行为，那上面那个 spin loop…… 呢？

如果你定义 int done[];，gcc 会毫 (非) 不 (常) 客 (开) 气 (心) 地把这个循环优化成：

%eax = done[tid];
while (%eax == 0) ;

也就是说，如果在循环开始前 done[tid] 还没有准备好，这个循环就陷入了死循环。这是因为编译器在进行优化时，是默认只有线程本地的数据流 (data flow) 的——如果假设有线程间的任意数据流，那么几乎任何优化都不正确了。

正确的解决办法是把 done 定义成 int volatile done[]; 禁止编译器优化对 done 的读写。volatile 和 const一样，都是 C 语言标准的一部分，有些公司在面试系统编程岗位的时候也会问这样的问题：

面试题：C 语言的特性

int f(void(* volatile const g)(int));是什么？

看起来是个非常无聊的面试题，就是考那些犄角旮旯里的没用的特性。但如果我再追加一句：在系统软件中，这样的 volatile 表达式可以用来实现什么有用的特性？如果你能答上，那就是个不小的加分项了。

2. 条件变量

留意到这里有一个 “条件”——同步几乎总是 “等待某个条件发生”，因此条件变量对大家来说就变得非常自然了。为了减少忙等待造成的浪费，我们需要一些额外的 API，能在线程需要等待的时候进入睡眠状态，并在合适的时候唤醒——考虑到我们几乎总是 “等待某件事” 发生，设计 “等待某个条件” 这件事就显得非常合理了。

2.1. 避免忙等待：条件变量

使用自旋虽然能正确解决同步问题，但仍然没有完美地解决好：为了等待 worker threads 的结束，主线程在一个 spin loop 里，白浪费了很多 CPU 资源。因此自然会想，如果库函数/操作系统能帮助我们实现这样的同步机制就好了——条件变量 (condition variables, CV)：

:::C
int pthread_cond_wait(pthread_cond_t *, pthread_mutex_t *mutex);
  // Unlock the specified mutex, wait for a condition, and relock the mutex.
int pthread_cond_broadcast(pthread_cond_t *cond);
  // Unblock all threads currently blocked on the specified condition variable.
int pthread_cond_signal(pthread_cond_t *cond);
  // Unblock at least one of the threads blocked on the specified condition variable.

教科书提供了非常详尽的条件变量解释，包括课堂上已经讲过的一些不能正确工作的例子。花一点时间理解这些例子，这是宝贵的并发编程经验——当然，比教科书更好的方式是用状态机 “证明” 程序的正确性 (或否定正确性)。这对于大家理解并发程序也是有很大好处的。状态机的视角帮助大家摆脱 “小作坊” 式的编程方式，正确性全靠运气，而是把程序正确与否的命运掌握在自己手中。

换言之，我们在理解并发程序时，真正做的事情是尝试 (枚举) 各种并发程序可能的调度。在尝试的过程中，你一定会发现以下几个有趣的现象：

  1. “程序是个状态机” 是对计算机系统本质的理解。
  2. 互斥锁极大的降低了理解并发程序执行的难度——我们可以把被锁保护的部分看作一个整体，它们要么执行，要么不执行 (由 lock/unlock 的语义保证)。就像课堂上画的框框——它实现了搜索空间的约减：我们其实找到了状态空间更好的一种表示方法！
  3. 并发程序的全局状态是解开问题的钥匙。一般来说，为了指出并发程序的问题，只需要程序达到某个特定的状态，然后发生一些线程之间的交互。这有点类似于大家做 OJ 的体验：需要尽力枚举各种各样的极端情况。

无论如何，更好地测试并发程序，或是证明并发程序正确都是非常具有挑战性的工作。即便在今天，我们设计的测试算法仍然能够自动检出真实程序中各种奇妙的并发 bug——也就是说，即便是有经验的开发者在写对并发程序这件事上，也许并不比大家做得好。

2.2. 生产者-消费者问题

特别值得一提的是其中的 “生产者-消费者” 问题——这是解决现实中并发问题 (底层实现) 中最有用的模型之一——在这个模型里，生产者和消费者的逻辑实现了解耦，生产者只负责产生对象 (服务请求/计算任务/...)；消费者只负责处理。在很多实际的并发程序中你也能看到类似的模式，例如各种响应请求的 Web/数据库服务器。

我们的课程上对生产者-消费者问题做了一个很有趣的简化：把生产者 (生产请求放入队列) 看作是 printf("(");，把消费者 (取出请求并处理) 看作是 printf(")");，我们把 ( 看成是入队，) 看成是出队，并发程序输出的任意括号序列，如果在一个有限队列的意义上合法，那么就必须满足：

  • 一定是某个合法括号序列的前缀；
  • 括号嵌套的深度不超过队列的大小 n。

在这样一个更干净的数学模型上，我们理解并发程序就变得更容易一些。阅读教课书、课件，确认你掌握了生产者-消费者问题的条件变量解法。

2.3. 万能的条件变量：哲 ♂ 学家吃饭问题

假设 5 个哲 ♂ 学家在 (Symposium on Systems' Philosophy, SOSP) 研讨会上碰面了，他们排成一个圆桌吃饭；吃饭时需要同时获得左手和右手的叉子；叉子被别人拿走时需要等待。假设每个哲学家对应一个线程，如何正确实现它们对两个叉子的互斥访问？你一定会听说过这个大名鼎鼎的线程同步问题。

想试试如何解决？

为了理解哲学家吃饭问题的难处，不妨考虑以下使用互斥锁的算法，它的 safety 没有问题——必须获得两把叉子的锁才能吃饭。但这个算法的 liveness 是由问题的。为什么？提示：所有哲学家同时拿起左手的叉子……

// 为每一个叉子设置一把锁
int philosopher(int id) {
  mutex_lock(&locks[lhs(id)]);
  mutex_lock(&locks[rhs(id)]);
  ...
  mutex_unlock(&locks[lhs(id)]);
  mutex_unlock(&locks[rhs(id)]);
}

如果要实现正确的线程同步，不妨可以用以下 “万能” 手段。当一个线程需要同步，等待某件事发生时，我们用一个 while 循环 spin (类似于之前的忙等待，只是在条件不满足时会发生睡眠，不再浪费 CPU 时间执行)：

mutex_lock(&mutex);
while (!cond) {
  wait(&cv, &mutex);
}
assert(cond); // 顺序：while 循环退出时循环条件为假
              // 并发：mutex 保证了 cond 检查和此处的原子性
mutex_unlock(&mutex);

而当任何时候条件可能满足时，都小心地用互斥锁保护好条件的更新，并唤醒所有等待的线程 (注意是 broadcast; 如果只是 signal 唤醒一个线程，正确性是得不到保证的——可能被唤醒的线程恰好发现条件不满足，继续睡眠)：

// 当条件可能满足时
mutex_lock(&mutex);
// 更新 cond 相关的数据
broadcast(&cv); // 唤醒所有等待的线程
mutex_unlock(&mutex);

用这个万能的方法，实现哲 ♂ 学家吃饭问题就易如反掌了：

  • cond 是 free[lhs(id)] && free[rhs(id)] (左手和右手的叉子都可用)
    • 在条件满足且临界区没有结束时，立即设置 free[lhs(id)] = free[rhs(id)] = 0;
    • 在放下叉子时令 free[lhs(id)] = free[rhs(id)] = 1;

只要互斥锁使用得当，条件变量就是一个 “带睡眠/唤醒的 spin loop”，不但性能不错，正确性还能得到保证。

潜在的性能问题

Premature optimization is the root of all evil. —— D. E. Knuth

如果系统中有很多线程时，使用 broadcast 唤醒所有线程可能会导致性能问题。但通常我们可以通过好的设计来避免——例如拆分为多个条件变量，每个只管理一部分叉子。事实上，对于复杂的同步问题，只要任务划分得当，甚至 master/slave 集中管理同步都是可取的——尤其是在现代分布式系统中，用少量的元数据服务器主管同步，而容易并行的任务分布到多台计算机上执行。

3. 信号量

3.1. 信号量 = 互斥锁 + 条件变量 + 计数器

复习我们之前实现生产者/消费者问题时使用的工具：

  • 互斥锁 mutex 用来保证代码的原子性；
  • 条件变量 empty 和 fill 用来表示是否有空/满的缓冲区；
  • count 计数器用来维护当前空余的缓冲区的数量。

信号量就是 “合三为一” 的线程同步手段，因为自带计数器，因此管理 “数量型” 的资源非常方便。信号量也是一个结构体 sem_t，内部包含一个计数器 count，它的行为是：

P (原子) 操作时，count 减 1，如果计数器数值小于零则线程睡眠等待。

void P(sem_t &sem) {
  sem->count--;
  if (sem->count < 0) {
    push(sem->queue, current);
    suspend();
  }
}

V (原子) 操作时，count 加 1，同时如果有正在睡眠的线程，则把睡眠的线程唤醒。

void V(sem_t &sem) {
  sem->count++;
  if (!empty(sem->queue)) {
    wakeup(pop(sem->queue));
  }
}

用条件变量、互斥锁和计数器实现信号量

信号量的 P/V 操作能够很自然地用条件变量 cond、互斥锁 mutex 和计数器 count 实现。你可以试试：你的实现最好能在条件变量被 “假唤醒” 的前提下仍然正确。

实际上，信号量可以理解成一个锁 (手环) 的 “池子”，计数器就是锁的数量。然后把 P/V 操作直观地理解：

  • P 操作就是从池子里取走一把锁。如果取成功，线程继续执行，否则就必须等待。
  • V 操作就是把一把锁放进池子里。如果有线程在等锁，它可以立即取走这把锁执行。

池子里的 “锁” 就是用来同步的资源。如果 count 的初始值为 1，我们可以直接把 P/V 当作互斥锁来使用——池子里只有一把锁，进入临界区必须取得锁，临界区结束后归还。

信号量可以说是为生产者/消费者问题量身定制的同步原语 (producer-consumer.c)

#include <threads.h>
sem_t fill, empty;

void producer() { while (1) { P(&empty); printf("("); V(&fill);  } }
void consumer() { while (1) { P(&fill);  printf(")"); V(&empty); } }

int main() {
  SEM_INIT(fill,  0);
  SEM_INIT(empty, 6);
  for (int i = 0; i < 4; i++) create(producer);
  for (int i = 0; i < 4; i++) create(consumer);
  join(NULL);
}

这就搞定了！如果我们用刚才锁的池子的方式来理解，就是生产者必须从 empty 里取得一把锁，即保证缓冲区中有空位，然后向 fill 归还一把锁；而消费者则执行完全对称的操作，实现 P(empty) -> V(fill) -> P(fill) -> V(empty) -> ... 的生产-消费循环。同时因为池子里的锁总共只有 n 把，因此缓冲区操作总是成功。

当然在上面的例子里，还有一个潜在的问题：所有的 printf 都可能是并发的。因为 libc 保证了 printf 的线程安全性，所以上述打印括号序列的代码是正确的。然而如果你在生产者-消费者问题中使用了缓冲区 (例如队列)，那就需要格外小心队列 push 和 pop 的线程安全性。

3.2. 信号量：实现 Master/Slave

信号量使用比较方便的场景像是 “不配对” 的互斥锁——请求的资源任何时候存在时，就使用 V 操作唤醒一个需要资源的线程；如果此时没有等待的线程，资源对应的 token 也会保留下载，下次需要资源的线程可以直接获得。

例如，用信号量很容易实现课程上提到的 master/slave 结构，为每个线程设置一个 “放行” 的信号量，在发出请求后立即执行 P 操作等待这个信号量；在允许放行时执行 V 操作。无论双方谁先到达，都能正确实现同步。

void master() {
  while (1) {
    P(request);
    req = dequeue(req_queue);
    tid = schedule();
    V(ready_to_go[tid]);
  }
}

void slave(int tid) {
  while (1) {
    enqueue(req_queue, my_request);
    P(read_to_go[tid]); // 如果不收到允许就不能执行
    ...
  }
}

在操作系统实验 (L2) 中，我们会自己动手实现自旋锁和信号量，并且在自己的操作系统中使用——很酷吧！先要把 kalloc/kfree 做对哦！

4. 动手实践

一看就懂，一做就错？

对于初次熟悉并发编程的同学来说，练习是不可少的。并发编程从本质上就和过去的思维方式不同——“编程” 一般指的是顺序编程，大家只需要考虑状态机 “一条线” 的执行即可，但并发却要考虑 “所有可能的执行”。因此，请大家务必用 pthread API (mutex, conditional variable, semaphore) 自己动手实现一些互斥问题，例如生产者-消费者问题，或是上课提到的 Building H2O 等。

另一个推荐的练习是用 threads.h 中增加条件变量的封装 (参考对信号量的封装)。在《计算机系统基础》和《操作系统》课中，大家一定已经体会到，做好基础设施对于后续 “做点什么” 来说实在是太重要了。

然后，你可以使用你的代码框架实现一些有趣的线程同步问题，例如下面也是一个往年的考题：

  • 系统中有四种线程，分别打印 [, (, ], )，并且打印的输出满足：
    • 一定是某个合法括号序列的前缀
      • 不允许 )(, (())][, [(])
    • 括号嵌套的深度不超过 $k$
      • $k = 3$ 时，不允许 [[((
    • 不能出现中括号嵌套在小括号里的情况
      • 允许：[[(())()()]()]
      • 不允许：([])

这个问题存在信号量的解法，但相当 subtle。遇到复杂的同步问题，用条件变量或是 master/slave 才是更可靠的。和 “编程” 一样重要的是，你需要编写一个 checker 来检查程序的输出是否合法 (你的程序很可能很小概率才出错)，例如 ./a.out | ./checker。

Creative Commons License    苏 ICP 备 2020049101 号