Condition Variable

问题引入

首先考虑这样一个问题，对于一个被若干线程并发访问的共享变量x，我们希望实现一个这样的函数：当x满足一定条件时，进行一次某种操作（比如，x>10时在屏幕上输出okay!），借助互斥锁，我们是可以这样实现：

Check condition using only lock

int x = 0; 
mutex m;
void f() {
    m.lock();
    while(!(x>10)) {
        m.unlock();
        Sleep(100);
        m.lock();
    }
    cout << "okay!" << endl;
    m.unlock();
}

其中最tricky的部分在于，若Sleep的时间太短，则程序会在busy waiting中消耗大量的CPU资源；若Sleep的时间太长，则会造成函数f的响应时间过长。条件变量就致力于解决这一问题。

什么是条件变量

条件变量（condition variable），顾名思义，在逻辑上对应了某种条件（如上面的例子中的x>2）。以C++中的std::condition_variable为例，它提供了如下三个基本方法：

void wait( std::unique_lock<std::mutex>& lock );原子地releaselock，将本线程加入*this对象的等待队列中，并阻塞，直至被notify_one或notify_all唤醒后再次requirelock，并退出；
void notify_one() noexcept; 若有线程在*this对象上等待，就唤醒其中的一个；

void notify_all() noexcept;将在*this上等待的所有线程唤醒；使用条件变量解决上面的问题：

Check condition using condition variable and lock

int x = 0;
mutex m;
condition_variable cond;
void f() {
    unique_lock<mutex> lock(m);
    while(!(x>10)) {
        cond.wait(lock);
    }
    cout << "okay!" << endl;
    lock.unlock();
}

并在改变了变量x的函数中加入notify_all即可。条件变量使得程序在等待条件变化期间无需占用CPU资源，又能在条件变化后及时被唤醒。实践中，一般条件变量对应的条件较为宽泛（是“x的值发生了改变”，而不是x>2，因为过细的条件会给notify的调用者带来过多的麻烦），所以在wait返回后仍需要检查自己的条件是否被满足。而C++同样为这种常见的写法提供了一种wait重载:

template< class Predicate > void wait( std::unique_lock<std::mutex>& lock, Predicate stop_waiting ); 其行为等价于：

1
2
3

while(!stop_waiting()) {
	wait(lock);
}

使用此重载，可以进一步简化上面的程序：

Simplified version

int x = 0;
mutex m;
condition_variable cond;
void f() {
    unique_lock<mutex> lock(m);
    cond.wait(lock, [&]{return x>2;})
    cout << "okay!" << endl;
    lock.unlock();
}

另一个视角

假设OS实现了另一种sleep(chan)——使当前线程处于sleep状态，直至被chan上的信号唤醒，那么unlock-sleep-lock是否就没有问题了呢？答案是否定的：这样的设计会出现所谓lost wakeup问题：试想：当线程A执行了unlock但还没执行sleep(chan)，此时线程B执行了wakeup ，那么这个wakeup不会唤醒任何线程，而线程Asleep后可能也不会再被唤醒，系统就陷入了停滞状态。所以cond.wait中的unlock和sleep必须是atomic的。这部分理解来自于6.S081的lecture 13。引用3

为什么条件变量需要和mutex一起使用？

条件变量的行为模式就是在模仿并改进条件等待问题中的互斥锁解决方案，wait方法就是对unlock-Sleep-lock序列的上位替代，因此需要接收lock参数。从解耦的思想上看，mutex解决互斥访问问题，condition_variable解决的条件等待问题，一个mutex可以对应多个condition_variable，将二者分开更加灵活。

条件变量的应用

bustub使用条件变量实现了读写锁；
bustub使用条件变量实现了LockManager中的行锁