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 的读写。volatileconst一样,都是 C 语言标准的一部分,有些公司在面试系统编程岗位的时候也会问这样的问题:

面试题:C 语言的特性

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

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

2. 条件变量

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

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

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

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);

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

  • condfree[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 用来保证代码的原子性;
  • 条件变量 emptyfill 用来表示是否有空/满的缓冲区;
  • 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 的线程安全性,所以上述打印括号序列的代码是正确的。然而如果你在生产者-消费者问题中使用了缓冲区 (例如队列),那就需要格外小心队列 pushpop 的线程安全性。

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 号