OSTEP [并发] Chapt. 30 - 条件变量

分类:Operating System, 发布于:2019-04-15 14:00:00, 更新于:2019-04-19 00:09:40。 评论

很多情况下,线程希望某个条件满足的情况下再继续执行。如父进程希望子进程完成任务后再继续执行代码。

可以使用一个共享变量,但父进程自旋等待浪费CPU资源,非常低效。更好的做法是让父进程睡眠,直到某个条件满足再唤醒它。

定义

线程可以利用条件变量来等待某个条件直到它满足为止。

A condition variable is an explicit queue that threads can put themselves on when some state of execution (i.e., some condition) is not as desired (by waiting on the condition); some other thread, when it changes said state, can then wake one (or more) of those waiting threads and thus allow them to continue (by signaling on the condition).

当线程调用wait()时,线程进入睡眠状态;调用signal()时,唤醒某个等待这个信号的线程。

在POSIX标准中,等待和发信的函数调用为

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);

wait()函数还需要一个互斥锁作为参数。wait()会解开锁并且让调用者进入睡眠状态(这是一个原子操作)。当调用者被唤醒时,它(wait())必须重新上锁,然后才能返回到调用者。

这个设计的目的是为了防止当线程进入睡眠状态时出现竞争。

  • 如果父进程先执行,那么父进程上锁,发现done == 0,进入睡眠状态等待唤醒并同时解锁;子进程开始执行。子进程结束后父进程被唤醒且重新上锁,发现done == 1,继续执行。
  • 如果子进程先执行,父进程执行时done == 1已经成立,父进程不进行等待。

如果删除了done:子进程先运行,父进程进入睡眠状态,永远无法唤醒。

如果删除了互斥锁:父进程获取数据的同时子进程修改了数据,产生竞争,父进程随即进入睡眠状态,永远无法唤醒。

设计指南:永远上锁。无论是signal()还是wait(),都要保证调用者持有锁,来避免问题发生。

生产者/消费者问题

在上面的实现中包含了一个信号变量cond和一个互斥锁mutex

当生产者想要填充缓冲区时,必须等待缓冲区清空(p1-p3);同样的,消费者需要等待缓冲区填满(c1-c3)。当生产者/消费者均只有一个时,上面的代码是正确的。但如果生产者或者消费者超出了1个,就会产生两个关键问题:

第一个问题是:消费者$C_1$先运行,发现没有商品,进入睡眠。当生产者$P$运行,发出信号唤醒消费者$C_1$时,消费者$C_2$横空出世清空了缓冲区,$C_1$线程仍然认为有商品可以消费,发生错误。

造成这个问题的原因是:发出信号代表状态发生了改变,并且会将等待它的线程唤醒;但信号并不保证唤醒了的线程运行时状态仍然是它(等待者)所期待的状态。这种解释被称为Mesa semantics;相反的,另一种要求保证被唤醒线程立即执行的解释叫做Hoare semantics。几乎所有的系统都是基于Mesa语意的。

通过将if修改为while(感谢谢逸纠正),我们可以解决上面遇到的问题。修改后的代码如下:

Mesa语意的启示:总是使用while循环来处理条件变量。多检查一次总是更安全,just do it and be happy。

此时我们考虑第二个问题:$C_1$$C_2$发现没有商品,都进入了睡眠状态。然后生产者开始执行,往缓冲区塞了一个商品,并唤醒了一个消费者(比如$C_1$)。接着生产者继续循环(解锁、上锁),发现缓冲区满了,也进入睡眠状态,等待消费者消费。现在,消费者$C_1$准备执行,$C_2$$P$处于睡眠状态。

$C_1$wait()函数中返回,重新检查缓冲区中商品的个数,发现有1个,然后清空缓冲区。接着,在c5行处,$C_1$唤醒下一个睡眠的线程。如果它唤醒了$C_2$$C_2$就会继续执行,再次检查缓冲区,发现没有商品,然后也进入了睡眠状态。最后,三个线程全部进入睡眠,没有线程可以被唤醒。

此时我们需要信号去唤醒线程,但信号的对象必须明确:消费者不能唤醒消费者,只能唤醒生产者,反之亦然。

使用两个信号变量即可解决问题。修改后的代码如下:

生产者/消费者问题的正解

生产者和消费者仍然需要支持并发性:需要多个商品缓冲区,可以一次生产/消费多个商品。

在上面的代码中,生产者只会在所有缓冲区都满的情况下进入睡眠;消费者只会在所有缓冲区都空的情况下进入睡眠。

虚假唤醒(spurious wakeups):在某些线程实现中,可能一次信号会同时唤醒多个线程,每个线程都应该使用while而不是if来检查等待的条件是否满足。

Covering condition:假设有两个线程需要内存,一个需要10,另一个需要100;现释放了50的内存,该唤醒哪个等待的线程呢?

Lampson和Redell推荐将pthread_cond_signal()替换为pthread_cond_broadcast(),唤醒所有的睡眠线程,全部线程都进行判断,即可唤醒该唤醒的进程,其他进程检查失败后继续回到睡眠状态。

但是,这并不是唯一的方案。如果你发现不把signal改成broadcast的话程序就出错,那么你的程序就肯定有bug。

评论