⏰

偽りの目覚め（condition_variable の待機状態が勝手に解除される件）

2022/10/28に公開

今、C++ のスレッドサポートライブラリについて色々調べてるんだけど、condition_variable の使い方を調べてたら spurious wakeup を考慮すべしとか書いてあって「？？？」ってなったのでメモ。
誰も起こしてないのに勝手に起きちゃうとか遠足前の子供かよっ！しかも spurious wakeup って名前が付いてるくらいに普通のことになってて、そりゃまぁ子供なら普通なんだけど、コンピュータがそれで良いのかって話。

Spurious Wakeup

Wikipedia の Spurious wakeup にはこう書いてある。

A spurious wakeup happens when a thread wakes up from waiting on a condition variable that's been signaled, only to discover that the condition it was waiting for isn't satisfied. It's called spurious because the thread has seemingly been awakened for no reason.

（以下、筆者による超訳）

Spurious wakeup とは、条件変数を待機していたスレッドが待機条件を満たしていないのに起きてしまう現象。理由もなく目覚めたように見えるため、名前に「スプリアス（偽りの）」が付いている。

いやいやいやいや……これダメでしょ。

Raymond Chen 氏のブログによると、Win32 では起こすべきスレッドを管理する領域に制限があって、限られた領域を超えるような数のスレッドを起こさなきゃいけなくなったら「えーい、全員起こしちゃえー」みたいなことをするんだとか。
しかも、Win32 の conditon valiables は spurious wakeup の発生を明示的に認めていて、「だから雑に管理しても大丈夫なんだ、はっはっはー」なんて言ってる始末。（かなりの誇張）

確かに Microsoft の公式資料を見ると、

Condition variables are subject to spurious wakeups (those not associated with an explicit wake) and stolen wakeups (another thread manages to run before the woken thread). Therefore, you should recheck a predicate (typically in a while loop) after a sleep operation returns.

と spurious wakeup についても書かれていて、「起きたら条件をもう一回チェックしてね」って注意してる。結構テキトーなのね……。これ、知らないと絶対ハマるやつだ……。

condition_variable

まずは C++ が spurious wakeup の存在を認めているかどうかを確認……発見。
condition_variable の wait (N4861 32.6.3/8.3) と、condition_variable_any の wait (N4861 32.6.4.1/1.3) に、

The function will unblock when signaled by a call to notify_one() or a call to notify_all(), or spuriously.

と書かれてる。notify_one() か、notify_all() か、spuriously に unblock されるんだとさ。2つの関数と同列の spurious さん……。

実験

あとは実際に発生するところまで見てみたいねってことで、実験。

#include <iostream>
#include <thread>
#include <condition_variable>
#include <mutex>
#include <chrono>
#include <atomic>
#include <vector>
#include <memory>

int main()
{
    // mutex, condition_variable, 状態（この3つはセット）
    std::mutex mtx;
    std::condition_variable cv;
    int waiting = 0;

    std::atomic_bool active = true; // 終了通知用
    constexpr size_t NUM_THREADS = 20;
    std::vector<std::shared_ptr<std::thread>> ths; // スレッドを保持
    std::vector<int> ns(NUM_THREADS); // 呼ばれた回数を保持
    for (size_t i = 0; i < ns.size(); ++i) {
        // スレッドの作成と開始
        ths.emplace_back(new std::thread([&](size_t idx) {
            while (active) { // 通知されるまでは延々と動き続ける
                std::unique_lock<std::mutex> lk(mtx); // lock
                ++waiting; // 待ち人数を増やす
                cv.wait(lk); // lock を解除しつつ wait
                ++ns[idx]; // 呼ばれた回数を記録
            }
        }, i));
    }

    // メインスレッドの処理
    for (int i = 0; i < 100000000; ++i) { // ビジーループだけど許して
        std::unique_lock<std::mutex> lk(mtx); // lock
        if (waiting > 0) { // 待ってる人がいるなら
            --waiting; // 待ち人数を減らして
            cv.notify_one(); // １人だけ起こす
        }
        else { // 誰も待ってなければ
            --i; // リトライ
        }
    }

    // 結果の表示
    int total = 0;
    for (size_t i = 0; i < ns.size(); ++i) {
        std::cout << "n[" << i << "] = " << ns[i] << std::endl;
        total += ns[i]; // 各スレッド毎の呼び出し回数を加算
    }
    std::cout << "total = " << total << std::endl; // 合計

    // ここから先は後始末
    active = false; // フラグで終了を通知
    cv.notify_all(); // 全員起こす
    for (auto& th : ths)
        th->join(); // 一人ずつ終了を確認する
}

今回はスレッドを20個作って試してみた^[1]。寝てる人数を waiting で管理して、寝てる人がいたら叩き起こすだけの簡単なコード。
メインスレッド側のループ回数が叩き起こす回数で、それぞれのスレッドは自分が何回叩き起こされたかをカウントしている。各スレッドの回数を合計するとループ回数に等しくなるはず。

実行結果

n[0] = 5306788
n[1] = 5266129
n[2] = 4758452
n[3] = 4741110
n[4] = 5311387
n[5] = 5254247
n[6] = 4758207
n[7] = 4747415
n[8] = 5243335
n[9] = 5253771
n[10] = 4750279
n[11] = 4702742
n[12] = 5211078
n[13] = 5230736
n[14] = 4741935
n[15] = 4740350
n[16] = 5281945
n[17] = 5244816
n[18] = 4718718
n[19] = 4736564
total = 100000004

100000000回ループを回して100000004回スレッドが起きてるから、このケースでは spurious wakeup が4回発生してるってことになる。
頻度としては低いんだけど、逆に言えば滅多に発生しない謎のバグの原因になり得るから、この頻度の低さはむしろ凶悪とも言えるかな。

これはたぶん spurious wakeup が発生しない処理系を作ることも可能なんだろうけど、コストがかかりすぎるから「許して」ってなってて、周りも「しょーがないなぁ……」って言いながら運用でカバーしてる優しい世界。

参考

Spurious wake-ups in Win32 condition variables (The Old New Things)
Condition Variables (Microsoft Learn)
条件変数とspurious wakeup (yohhoyの日記)

脚注

私の環境ではスレッド数を10個に減らすと spurious wakeup は（数回試した限りでは）発生しなかった。スレッドが多すぎると管理しきれなくて雑になる説が有力か？ ↩︎

Spurious Wakeup

condition_variable

実験

参考

Discussion