条件变量

现实中,我们经常会碰到一种场景,那就是希望等待某个条件满足的时候被通知。

条件变量的概念就从此来了。这篇的分析也比较长,请大家耐心。

定义

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

这个概念是由迪杰斯特拉(Dijkstra)提出的。

POSIX 库的系统调用原型,

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

void pthread_cond_signal(pthread_cond_t *c);

下面是一个例子,Parent Waiting For Child by Using A Condition Variable
01

wait 函数的作用是释放当前锁且让当前线程休眠。

The responsibility of wait() is to release the lock and put the calling thread to sleep (atomically).

上图有两点要注意的地方,

  1. the parent creates the child thread but continues running itself,意思是说等到 thr_join() 执行了,子线程才 run 起来。这时候,主线程先会 acquire 这个 lock,然后发现自己得去 wait;接着,子线程 run 起来了,把 done 设为了 1 且通过条件变量 c 唤醒了主线程,此时主线程退出
  2. 子线程先于 主线程的 thr_join() 执行了,这时候毫不犹豫的把 done 设为 1,且通过条件变量试图唤醒沉睡的进程,然而此时主进程没有执行 thr_join(),也就没有沉睡,然后子线程执行完了,轮到主线程的 thr_join() 执行了,然而这时候根本不用 sleep,此时主线程退出

下面我们修改下代码:
02

执行结果会怎样?答案是,会出问题的。原因在于上面提到的第 2 点。如果子线程先于主函数执行完毕了(因为子线程的线程体完全置于锁的控制范围嘛),然后也没有唤醒任何线程(因为此时主线程没有沉睡),接着轮到主线程执行 thr_join(),问题出来了,主线程此时无条件 pthread_cond_wait(),因此主线程会无休止的休眠下去。

讲到这里,我一直没理解通篇和开头的 “定义” 提到的 队列(Queue)有什么联系,因为前面有一篇《锁》有提到为了减轻操作系统有可能出现的错误调度问题而导致的浪费资源,会在锁的数据结构中维护一个队列,而原文开篇也提到了 A condition variable is an explicit queue,但是没有展开讲解这两者的区别和联系

生产者/消费者问题

生产者/消费者问题也是由迪杰斯特拉提出的。

03

版本 1:一个残缺的设计

04

为啥是不 work 的设计呢,我们看下面的线程可能的执行序列。两个消费者 Tc1、Tc2,一个生产者 Tp
05

  1. 程序开始,消费者线程 Tc1 连着运行 c1-c3 的代码,发现此时没有东西可给它消费,就释放了锁并且休眠了
  2. 接着,生产者 P 获得了 CPU 的运行机会,此时它会一直运行 p1-p6,期间唤醒了消费者 Tc1,然后又意识到此时 buffer 已经满了,没办法自己去休眠
  3. 问题就出在此时,此时两个消费者 Tc1 和 Tc2 都是 ready 状态的,如果 Tc2 先获得了 CPU 的运行权,消费了 buffer,然后接着 Tc1 才获得继续运行的机会,它从 c3 处继续运行,结果却发现,get() 不到任何东西,程序此时 assert 失败了

问题的原因很简单,从 Tc1 被唤醒之后到 Tc1 能获得 CPU 运行机会之前,buffer 的状态被 Tc2 偷偷修改了。

版本2:修复版本 1 的 Bug

把 c2 行的 if 改成 while
06

然而,上面的代码还是有 bug。
07

  1. 程序开始,消费者线程 Tc1 和 Tc2 轮流获得 CPU 运行机会,但通通都在 c3 释放了锁并休眠
  2. 接着,消费者线程启动,生产了一个值放入 buffer,然后就释放了锁、唤醒消费者线程并休眠
  3. 假设此时被唤醒的消费者线程 Tc1 获得了运行机会,重新检查 buffer 是否可取,此时是可取的,就消费它然后释放锁、唤醒等待队列的线程并休眠
  4. 接着,问题出现了,如果此时获得运行机会的是消费者线程 Tc2(这是可能的),它醒来发现 buffer 是空的,就释放锁(c2)、休眠了(c3),但是此时,它并没有去唤醒沉睡着的生产者线程 Tp,而另外一个消费者线程 Tc1 此时也是沉睡着的。因此,程序卡主了。

版本3:最终版

通过上面的分析,我们知道了,消费者和生产者所需要接收的条件通知是不一样的,消费者需要在 empty 的时候沉睡,在 fill 的时候被唤醒,生产者需要在 fill 的时候沉睡,*empty* 的时候被唤醒,因此用两个条件变量就好啦!

最终版本的代码:
08

条件变量的使用场景

内存分配的时候,一个线程想要分配内存,必须得等到有空闲内存给它的时候才能继续,否则就休眠;一个线程释放了内存的时候就要唤醒其他想要内存的线程

总结

我在读这篇的中间提出过一个疑问,现在文章结束了,书中还是没有解决我的疑问,我只能去 Google 了。

引用

《Condition Variables》

Comments
Write a Comment