yohhoyの日記（別館）

もうちょい長めの技術的メモをしていきたい日記

C++ MIX #5に参加しました

C++

2019/9/4に開催されたイベント C++ MIX #5 にて、“20分くらいでわかった気分になれるC++20コルーチン” というタイトルで20分ほど話す機会をいただきました。（Boost.勉強会を含めると5年6ヶ月(！)ぶり3回目）

スライド資料

www.slideshare.net

感想とか

C++20導入予定のコルーチン機能について、C++プログラマの期待値とは異なるであろう実態説明を主題としました。C++標準仕様へのコルーチン導入議論は、古くは2012～2013年頃から長い歴史が積み重ねられており、さまざまな議論があったうえでC++20では現行仕様におちつきました。C++プログラマが広くコルーチンを活用できるのは未来のお話（早くとも2023年以降）になりますが、まずはC++標準ライブラリのコルーチン対応を検討するための基礎固めを優先したのだと思われます。

C++20コルーチン対応は、仕様書の文面からのみではその全体像や利用方法を理解しづらい機能の部類と思います。また議論の歴史が長いぶん関連する提案文書が大量に残っており、最終的には採用されなかった対抗仕様や改善提案も多岐にわたるため、どれを追えばよいかも判別しづらくなっています。C++20コルーチンを使ってみようと思い立ったときに、本資料が最初の取っ掛かりとなるようであれば幸いです。

Twitter上での皆さんのコメントをみるに、スタックレス(Stackless)／スタックフル(Stackful)への関心が高かったように思います。C++20コルーチンは軽量だがユーザの自由度は低い “スタックレスコルーチン” であり、より使いやすい “スタックフルコルーチン” いわゆるファイバー(Fiber)はまだ検討段階*1にあります。現時点でスタックフルコルーチンを必要とするときは、Boost.Coroutine2やBoost.Fiberなどの外部ライブラリ*2が候補となります。

提案文書

コルーチンに関連する提案文書を列挙してみました。あまりの数の多さに作業途中で後悔した('A`)

2012年

2013年

2014年

2015年

2016年

2017年

2018年

2019年

凡例：*印はPDF形式、★印は採択(Adopted)を表す

*1:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0876r8.pdf

*2:両BoostライブラリのメンテナOliver Kowalke氏が、C++標準へのスタックフルコルーチン提案を行っています。

C++ミューテックス・コレクション -みゅーこれ- 実装編

C++

マルチスレッド処理にて排他制御を実現する同期プリミティブ、ミューテックス(Mutex) をC++でたくさん実装してみました。ミューテックスを道具として使うのではなく、ミューテックスそのものを作るお話です。

github.com https://github.com/yohhoy/yamc

ライブラリ概要は “C++ミューテックス・コレクション -みゅーこれ- 紹介編” を参照ください。本記事ではライブラリ実装にあたっての実装デザイン、ユニットテスト手法、デバッグ苦労話をつらつらとまとめています。

実装デザイン

ミューテックス型の内部実装

本ライブラリが提供するミューテックス型は、スピンロック(spinlock)ミューテックスを除いて、標準ミューテックスstd::mutexと条件変数std::condition_variableを用いたブロッキング・スタイルで実装されます。ミューテックス型に限らず、あらゆる同期プリミティブオブジェクトはミューテックスと条件変数を用いて実装可能です*1。ミューテックス内部実装の基本構造は下記の通りです。

class mutex {
  std::condition_variable cv_;
  std::mutex mtx_;
  // ＋状態管理メンバ変数

public:
  void lock() {
    std::unique_lock<decltype(mtx_)> lk(mtx_);
    while (!/*ロック獲得可能?*/) {
      cv_.wait(lk);
    }
    // ロック獲得
  }

  bool try_lock() {
    std::lock_guard<decltype(mtx_)> lk(mtx_);
    if (!/*ロック獲得可能?*/)
      return false;
    // ロック獲得
    return true;
  }

  void unlock() {
    std::lock_guard<decltype(mtx_)> lk(mtx_);
    // ロック解放
    cv_.notify_all();
  }
};

公平スケジューリングの実装

タイムアウトをサポートしない公平スケジューリング・ミューテックスyamc::fair::(recursive_)mutexでは、シンプルなトークン(token)管理にて公平スケジューリングを実現します。内部状態として“現在のロック所有カウンタcurr_”と“次のロック所有カウンタnext_”の2つを持ち、両カウンタ値が等しいときミューテックスは非ロック状態となります。ロック獲得処理では次カウンタから要求トークン(request)を払い出し、現在カウンタと比較します。ロック解放処理では現在カウンタを1つ進め、ロック獲得を待機中のスレッドへの通知を行います。ロック獲得／解放処理ロジックのみ抽出したコードは下記の通りです。

//  （fair_mutex.hppより抜粋）
class mutex {
  std::size_t next_ = 0;
  std::size_t curr_ = 0;

public:
  void lock() {
    std::unique_lock<decltype(mtx_)> lk(mtx_);
    const std::size_t request = next_++;
    while (request != curr_) {
      cv_.wait(lk);
    }
  }

  void unlock() {
    std::lock_guard<decltype(mtx_)> lk(mtx_);
    ++curr_;
    cv_.notify_all();
  }
};

たったこれだけの短いアルゴリズムですが、lockメンバ関数呼び出し順とロック獲得順が完全一致するFIFO(First-In-First-Out)スケジューリングを実現できます。疑り深い人は動作をトレースしてみてください。

タイムアウト対応・公平スケジューリングの実装

タイムアウト対応・公平スケジューリング・ミューテックスyamc::fair::(recursive_)timed_mutexでは、より複雑なリンクリスト(linked list)構造にて公平スケジューリングを実現します。残念ながらトークンベース実装では“ロック獲得要求のタイムアウト”、つまりロック獲得待ちスレッド列からの離脱を正しく表現できませんでした（敗北の記録：Issue#5）。

内部状態として二重リンクリスト(doubly linked list)データ構造による“ロック待機キューqueue”と、ロック所有状態を表現する“ロック所有ノードlocked”を持ちます。ロック待機キュー先頭がロック所有ノードのとき、ミューテックスはロック状態にあります。ロック獲得処理では要求ノードrequestをキュー末尾に追加し、同要求ノードがキュー先頭に繰り上げられる（ロック獲得権が回ってくる）まで待機します。ロック獲得要求がタイムアウトした場合は、自身の要求ノードをキューから削除します。ロック獲得できた場合は、キュー先頭からの要求ノード削除とロック所有ノード追加を行います。各ノードはそのアドレスにのみ意味があり、prev/nextポインタ以外のメンバ変数は持ちません。Issue#7 よりアルゴリズム記述擬似コードを引用します。

locked : node  // placeholder node
queue : node   // anchor node (pointer to front/back node)

lock():
  if !queue.empty():
    request : node
    queue.push_back(request)
    while queue.front() != request:
      cv.wait()
    queue.pop_font()  // erase request
  queue.push_front(locked)
  // acquire

try_lock():
  if !queue.empty():
    return false
  queue.push_front(locked)
  return true

try_lock_timeout():
  if !queue.empty():
    request : node
    queue.push_back(request)
    while queue.front() != request:
      if (cv.wait() == timeout):
        if queue.front() == request:
          break
        queue.erase(request)
        return false
    queue.pop_font()  // erase request
  queue.push_front(locked)
  // acquire
  return true

unlock():
  assert (queue.front() == locked)
  queue.pop_front()
  cv.notify_all()
  // release

このアルゴリズムは、リンクリスト・ノードの動的メモリ確保・解放を必要としません。リンクリストに追加される要求ノード(request)は、ロック獲得待機中スレッドのコールスタック(call stack)上に配置、つまりlock, try_lock_{for,until}メンバ関数のローカル変数として確保します。これは要求ノードの生存期間が“自スレッドがロック獲得可能になるまで”で十分であり、その条件を満たすまで自スレッドは条件変数待機でブロックされる（休眠状態）ため、このようなトリッキー実装が可能なのです。Εύρηκα(Eureka)!!!

共有ロック・公平スケジューリングの実装

共有ロック・公平スケジューリング・ミューテックスyamc::fair::shared_(timed_)mutexでは、リンクリスト・データ構造を用いた公平スケジューリングを実現します。リンクリスト・ノード状態として、排他／共有ロック、ロック待機中"waiting"／ロック可能"lockable"、およびロックカウント（ロック所有ノードlocked_のみ）を保持します。共有ロックは複数スレッドから同時所有されるため、ロックカウントが必要になっています。排他ロック中はロックカウント1が最大値です。

//  （fair_shared_mutex.hppより抜粋・調整）
class shared_mutex {
  struct node {
    std::size_t status;
    // bitmask:
    //   (LSB)0: 0=exclusive-lock / 1=shared-lock
    //        1: 0=waiting / 1=lockable(-ing)
    //   MSB..2: number of locking thread (locked_ member only)
    node* next;
    node* prev;
  };

  node queue_;   // q.next = front(), q.prev = back()
  node locked_;  // placeholder node of 'locked' state
  // (以下略)
};

共有ロック獲得処理(lock_shared等)では要求ノードをキュー末尾に追加し、その要求ノード状態が"lockable"に遷移するまで待機します。排他ロック解放(unlock)処理では、キュー中の共有ロック/"waiting"ノードの状態を"lockable"へ変更します。排他ロック獲得要求(lock等)がタイムアウトした場合は、同ロック要求の前後に連なっている共有ロック要求ノードグループのマージ処理を行います。その他の操作はソースコードを直接参照ください。コアロジック記述は200行もありませんから、コードを読めば理解できます。たぶん。

ユニットテスト手法

フレームワーク選定とテストケース構造

本ライブラリのユニットテスト・フレームワークには、スレッドセーフを明記している Google Test(GTest) を選択しました。ミューテックス型の提供機能には包含関係があるため、複数の型に対して同一テストケースを適用する型パラメータテスト(type-parameterized test)を多用しています。例えばmutexに対するテストケースは、全ての他ミューテックス型timed_mutex, recursive_(timed_)mutex, shared_(timed_)mutexに対しても同様に実施します。

各テストケースでは、最初にテスト走行用スレッドを必要数だけ生成(fork)し、テスト対象への操作とアサーション記述を行い、最後に全走行スレッド完了を待機(join)する構造となっています。このFork-Joinモデルはテストケース記述の定型パターンのため、自動スレッドjoinヘルパクラス yamc::test::join_thread やタスク並列実行ヘルパ関数 yamc::test::task_runner を自作しています。

#include "yamc_testutil.hpp"

TEST(/*2スレッド並列処理の雛形*/)
{
  yamc::test::join_thread thd([&]{
    // スレッドT1 処理
  });
  {
    // スレッドT0 処理
  }
}

TEST(/*3スレッド並列処理の雛形*/)
{
  yamc::test::task_runner(3, [&](std::size_t id) {
    switch (id) {
    case 0:
      // スレッドT0 処理
      break;
    case 1:
      // スレッドT1 処理
      break;
    case 2:
      // スレッドT2 処理
      break;
    }
  });
}

テストケースの記述(1)

具体例として、「try_lock操作でロック獲得に失敗する」テストケース(NormalMutexTest.TryLockFail)を取り上げます。該当テストケースにおける初期化(setup)／テスト／終了処理(teardown)は次の通りです。

初期化
2つのスレッドが存在し、スレッドT1が対象ミューテックスのロック所有中。
テスト
スレッドT0が対象ミューテックスのtry_lock()メンバ関数を呼び出し、その戻り値がfalseとなること。
終了処理
スレッドT1が対象ミューテックスのロックを解放し、2つのスレッド完了を待機。

マルチスレッド処理のテストケース記述では、テスト対象操作時の周辺環境セットアップが困難、つまり複数スレッドの実行タイミングを意図通り制御するのが難しいという問題があります。本ライブラリでは合流バリア(Rendezvous Barrier)*2 yamc::test::barrier を自作し、合流ポイントを適宜設定してテスト走行スレッド群の進行状況が必ず揃うよう制御しています。

// （tests/basic_test.cppより抜粋）
TYPED_TEST(NormalMutexTest, TryLockFail)
{
  yamc::test::barrier step(2);
  TypeParam mtx;
  yamc::test::join_thread thd([&]{
    ASSERT_NO_THROW(mtx.lock());
    step.await();  // b1
    step.await();  // b2
    ASSERT_NO_THROW(mtx.unlock());
  });
  {
    step.await();  // b1
    EXPECT_FALSE(mtx.try_lock());
    step.await();  // b2
  }
}

例示テストケースでは2回の合流バリアb1, b2を設定しており、b1より前が初期化処理、b1〜b2間がテスト本体、b2以降が終了処理に対応します。通常のシングルスレッド処理のテストケース記述に比べると、本質的なテスト以外の周辺コードがどうしても肥大化してしまいます。

テストケースの記述(2)

より複雑なテストケースでは、単純な合流バリアではタイミング制御できないパターンも存在します。例えば公平(fair)スケジューリングのテストケース(FairMutexTest.FifoSched)では、初期化として「複数スレッドがある順序でロック獲得待ちを行なっている」状態を作り出す必要があります。テスト走行スレッドが順次lockメンバ関数を呼び出して待機状態へ突入するのですが、テストコードからみるとロック獲得成功までスレッド制御が戻ってこないため、そもそもタイミング制御のための合流バリアに到達できない状態となります。

本ライブラリではフェーズ同期(Phaser)機構*3 yamc::test::phaser を自作し、フェーズ設定とステップ遅延とを組み合わせてタイミング制御を行ないます。合流バリアでは“他スレッドへの到達通知”と“他スレッドからの通知待機”が不可分（await操作）でしたが、フェーズ同期機構では“他スレッドへの到達通知のみで自スレッドは通過”（advance操作）が追加されます。ステップ遅延 EXPECT_STEP マクロは自スレッドを休眠(sleep)し、他のテスト走行スレッド進行を待機します。またカウンタ変数によりステップ通過順序の検証も同時に行なっています。

注意深い方は気づいたかもしれませんが、このテスト手法では100%の状況再現を保証できません。休眠中に他スレッド群が次フェーズまで到達することを期待していますが、システム高負荷などの理由でOSスケジューラが該当スレッドを十分進められなければその仮定は崩れてしまいます。休眠期間を長くとることで信頼性は上がりますが、代償としてユニットテスト所要時間が間延びしていきます。2018年3月時点では、遅延時間200ミリ秒もあれば実用上は確実に動作するようです。

// （tests/fairness_test.cppより抜粋、一部略）
//
// T0: T=1=a=a=====w=4=U.l-----L=7=U
//         |  \   /    |       |
// T1: ....w.2.a.a.l---L=5=U...|....
//         |   |  \        |   |
// T2: ....w.t.w.3.a.l-----L=6=U....
//
//   l/L=lock(request/acquired), U=unlock()
//   T=try_lock(true), t=try_lock(false)
//   a=phase advance, w=phase await
//
TYPED_TEST(FairMutexTest, FifoSched)
{
  yamc::test::phaser phaser(3);
  TypeParam mtx;
  yamc::test::task_runner(3, [&](std::size_t id) {
    auto ph = phaser.get(id);
    switch (id) {
    case 0:
      EXPECT_TRUE(mtx.try_lock());
      EXPECT_STEP(1)
      ph.advance(2);  // p1-2
      ph.await();     // p3
      EXPECT_STEP(4)
      mtx.unlock();
      mtx.lock();
      EXPECT_STEP(7)
      mtx.unlock();
      break;
    case 1:
      ph.await();     // p1
      EXPECT_STEP(2)
      ph.advance(2);  // p2-3
      mtx.lock();
      EXPECT_STEP(5)
      mtx.unlock();
      break;
    case 2:
      ph.await();     // p1
      EXPECT_FALSE(mtx.try_lock());
      ph.await();     // p2
      EXPECT_STEP(3)
      ph.advance(1);  // p3
      mtx.lock();
      EXPECT_STEP(6)
      mtx.unlock();
      break;
    }
  });
}

例示テストケースでは3つのフェーズp1, p2, p3を設定し、フェーズp3後に初期化が完了、つまりスレッドT0がロック所有かつスレッドT1, T2の順にロック獲得を待機しています。ステップ#4経過後にT0はロック解放し、ようやく本題の“T1, T2および再度ロック獲得要求を行なったT0のFIFO順でロック獲得すること”を検証します。公平性テストとしては最もシンプルなテストケースです。ね、簡単でしょう？

デバッグ苦労話

マルチスレッド・デバッグのお供

マルチスレッド処理はデバッグが超辛いことで知られています。知ってくれ。銀の弾などない。本ライブラリの開発では、下記ツールが大いに役立ちました。

アサーション記述による不変条件(Invariant)の表明とデバッガの組み合わせは、複数スレッド相互作用による意図しない状態遷移を効果的に検出できます。Valgrind/HelgrindやClang/Thread Sanitizerといった高度なツールはデータ競合(data race)等の実装バグ発見には有用ですが、設計不具合に対してはデッドロック発生といった最終結果しか示してくれません。不具合修正にはその状況に陥るまでの動作解析が必要不可欠であり、この観点ではprintfデバッグと机上デバッグが最も威力を発揮します。printfデバッグに関する注意点として、問題解析のためにログ出力量を増やすほど不具合自体が再現し難くなることがしばしば起きます（Heisenbugs; ハイゼンバグ）。ログ出力レベルはマクロで切り替えられるように実装しておくべきです。

マルチスレッド処理に起因する不具合のうち、再現可能なバグは（高々有限時間で）修正可能です。再現不可能なバグは、内部・外部要因を変化させて事象再現することを祈りつつ、ひたすら机上デバッグを頑張るしかありません。スレッドはあなたの期待する通りに動きませんし、どんなに確率が低い事象もいつかは発生します。並行処理設計で保証しない限りは、スレッドのあらゆる進行状況を考慮に入れるべきです。

デッドロックの遠隔デバッグ

起きたこと：リモートCI環境でのみユニットテスト走行中に偶発的なデッドロック発生。ローカル環境では全く再現しない。絶望。

解析および修正は Pull Request#20コメント に記録していますが、解決までのステップは下記のようなものでした。前半は手元コード修正commit、push、CI実行、CIログ確認という、“のろし”で遠隔通信しているような感覚です。

  1. デッドロック発生するテストケースの特定（printfデバッグ）
  2. ミューテックス内部状態のトレースログ出力（printfデバッグ）
  3. トレースログからデッドロック発生条件解析（机上デバッグ）
  4. 自己コードレビューおよびバグ修正

デッドロックの直接原因は、イベント順“所有中の排他ロック解放”→“排他ロック要求がタイムアウト”→“共有ロック要求”でのみ生じる内部状態遷移の誤りでした。厄介なことにこのイベント発生順は意図的には再現不可能な順序であり*4、該当テストケースにより偶然摘出された不具合でした。幸運にもCI環境で発生頻度が高かったのは、CPUコア数が多いことで2つのイベントが重なる確率が高かったためのようです。CPUコア数が少ない手元環境ではスレッドが真に並行実行されず、イベント発生が重ならないため不具合が表面化しなかったと推測されます。教訓としては「システム低負荷状態でないと再現しないタイミング問題もある」「確率的とはいえ再現環境の存在は重要」といったところでしょうか。辛い。

オチ：本件以外に、他設計も壊れてた。解決済み。

つぶやき


*1:本文中ではブロッキング動作の同期プリミティブ実装のみを前提としています。ブロッキングを伴わないロックフリー(lock-free)動作の実現には、ミューテックスではなくatomic変数利用が必須になります。

*2:"rendezvous"はフランス語「ランデヴー」。待ち合わせ、会合といった意味。http://d.hatena.ne.jp/yohhoy/20130320 参照。

*3:おそらく「フェーズ同期(Phaser)」はマルチスレッド同期プリミティブとしても一般用語ではないと思います。名称・アイディアはJava言語ライブラリjava.util.concurrent.Phaserからの借用です。概略は http://d.hatena.ne.jp/yohhoy/20140225 参照。

*4:“所有中の排他ロック解放”→“排他ロック要求がタイムアウト”のイベント順が制御できません。通常であれば“所有中の排他ロック解放”後には、排他ロック要求がタイムアウトせずにロック獲得成功してしまいます。このケースでは非常にシビアなスレッド間のタイミング噛み合わせが起きています。

C++ミューテックス・コレクション -みゅーこれ- 紹介編

C++

マルチスレッド処理にて排他制御を実現する同期プリミティブ、ミューテックス(Mutex) をC++でたくさん実装してみました。ミューテックスを道具として使うのではなく、ミューテックスそのものを作るお話です。

YAMC

C++言語ヘッダオンリー・ライブラリ YAMC (Yet Another Mutex Collections) として、MITラインセスで公開中。コンパイラはC++11以降が必須です。

github.com https://github.com/yohhoy/yamc

2018年3月現在、合計で 20種類 のミューテックスが実装されています。全てのミューテックス型はC++標準ライブラリ提供のミューテックス型と同一インタフェースを提供するため、マルチスレッド処理実装におけるミューテックス切り替えを容易に行えます。さらに本ライブラリのミューテックス型では、C++標準ライブラリでは実現できない細かい振る舞いの調整をサポートします。

C++14以降で追加された共有ロック・ミューテックス(shared_(timed_)mutex)も提供するため、C++11環境における前方互換性を実現できます。また、C++14以降のRAIIロック管理用クラステンプレートもあわせて提供します。

  • shared_lock：共有ロックの管理（C++14で追加）
  • scoped_lock：排他ロックの管理（C++17で追加）

提供機能の一覧

本ライブラリが提供するミューテックス型、RAIIロック管理用クラステンプレートの一覧は次の通りです：

  • yamc::spin::mutex
  • yamc::spin_weak::mutex
  • yamc::spin_ttas::mutex
  • yamc::checked::mutex
  • yamc::checked::timed_mutex
  • yamc::checked::recursive_mutex
  • yamc::checked::recursive_timed_mutex
  • yamc::checked::shared_mutex
  • yamc::checked::shared_timed_mutex
  • yamc::fair::mutex
  • yamc::fair::recursive_mutex
  • yamc::fair::timed_mutex
  • yamc::fair::recursive_timed_mutex
  • yamc::fair::shared_mutex
  • yamc::fair::shared_timed_mutex
  • yamc::alternate::recursive_mutex
  • yamc::alternate::timed_mutex
  • yamc::alternate::recursive_timed_mutex
  • yamc::alternate::shared_mutex
  • yamc::alternate::shared_timed_mutex
  • yamc::shared_lock<Mutex>
  • yamc::scoped_lock<Mutexes...>

ミューテックス型ではC++標準ライブラリ互換の排他制御動作に加えて、下記の追加機能を提供します。（括弧内は名前空間）

  • TAS(Test-And-Set)スピンロック
    • 強いメモリ順序制約(yamc::spin)／弱いメモリ順序制約(yamc::spin_weak)
    • 待機ポリシー指定: Exponential-backoff, Yield, Busy-loop
  • TTAS(Test and Test-And-Set)スピンロック(yamc::spin_ttas)
    • 待機ポリシー指定: Exponential-backoff, Yield, Busy-loop
  • 公平スケジューリング(yamc::fair)
  • 共有ロック(yamc::alternate)
    • スケジューリング・ポリシー指定：Reader-prefer, Writer-prefer
  • 公平スケジューリング共有ロック(yamc::fair)
    • スケジューリング・ポリシー指定：Task-fairness, Phase-fairness
  • 検査機構付き(yamc::checked)
    • 事前条件の違反検知、デッドロック検知
    • 違反検知動作の切替：例外送出, abort呼出

機能の詳細説明

スピンロックと待機ポリシー

他スレッドがミューテックスのロック所有している状況で、自スレッドからlock関数でロック獲得要求を行うと、自スレッドはロック獲得できるまで待機状態に入ります。C++標準ライブラリ提供のミューテックスでは待機状態で自スレッドを休眠(sleep)させ、他スレッドの処理進行を強く促します*1。一方のスピンロック・ミューテックスでは、スレッド休眠を行わず実行中(running)のままロック獲得を待機します。

局所的にみるとスピンロックはCPU時間を浪費していますが、ミューテックスによる排他制御区間が非常に短く、すぐに次のロック獲得が期待できる状況では並列処理スループットが向上する可能性があります。ただし、スレッド数がCPUコア数よりも多い状況（オーバー・サブスクリプション; Oversubscription）ではロック所有中スレッドの進行機会が減少するため、標準ミューテックスよりもシステム負荷が高くなり並列処理パフォーマンスが悪化するリスクもあります。スピンロックの有効性判断では、必ず実プログラムで性能計測を行なってください。

本ライブラリでは3種類のスピンロック・アルゴリズムと、それぞれに対して3種類の待機ポリシー(yamc::backoff)を提供します。待機ポリシーはクラステンプレートbasic_mutexのテンプレートパラメータとして与えるため、計9種類のスピンロック実装から選択できます。既定の待機ポリシーにはExponential-backoffアルゴリズムを利用します。

// TASスピンロック
#include "naive_spin_mutex.hpp"
yamc::spin::mutex       // 既定の待機ポリシー
yamc::spin::basic_mutex<yamc::backoff::exponential<N>>
yamc::spin::basic_mutex<yamc::backoff::yield>
yamc::spin::basic_mutex<yamc::backoff::busy>
yamc::spin_weak::mutex  // 既定の待機ポリシー
yamc::spin_weak::basic_mutex<yamc::backoff::exponential<N>>
yamc::spin_weak::basic_mutex<yamc::backoff::yield>
yamc::spin_weak::basic_mutex<yamc::backoff::busy>

// TTASスピンロック
#include "ttas_spin_mutex.hpp"
yamc::spin_ttas::mutex  // 既定の待機ポリシー
yamc::spin_ttas::basic_mutex<yamc::backoff::exponential<N>>
yamc::spin_ttas::basic_mutex<yamc::backoff::yield>
yamc::spin_ttas::basic_mutex<yamc::backoff::busy>

各クラステンプレートのアルゴリズムは下記の通りです（名前空間yamcは省略）。通常利用ではTTASスピンロックを推奨します。

待機ポリシーの振る舞いは下記の通りです（名前空間yamcは省略）。通常利用ではExponential-backoffアルゴリズムを推奨します。

公平スケジューリング

一般的に、ミューテックスの内部実装では不公平(unfair)スケジューリング戦略が採用されます。C++標準ライブラリ提供のミューテックスでロックが競合(Lock Contention)した場合、次にロック獲得に成功するスレッドはOSスケジューラ依存となっています*2。不公平ミューテックスでは各スレッドからのlock関数によるロック獲得要求の順序と、実際にロック獲得できるスレッド順序の間に相関はありません。つまり高いロック競合状態にある場合、いつまでたってもロック獲得できないスレッドが発生するリスクがあります。

一方の公平(fair)スケジューリングでは全ての待機スレッドに対して均等にロック獲得の機会を与えるため、不公平スケジューリングのようにあるスレッドが不公平に扱われることはありません。ただし均等機会の実現には追加のオーバーヘッドを伴うため、ロック獲得処理そのものはコスト高になります。スケジューリング戦略の選択では、対象プログラムの性能計測に基づいた選択をお勧めします。（通常は非公平スケジューリングで十分なはずです。）

本ライブラリでは、FIFO(First-In-First-Out)順の公平スケジューリング・ミューテックスを提供します。これらのミューテックス型では、ロック獲得順がlock呼出順に完全一致することを保証します。FIFO順実現のため追加オーバーヘッドは存在しますが、動的メモリ確保は行いません。

// 公平スケジューリング・ミューテックス
#include "fair_mutex.hpp"
yamc::fair::mutex
yamc::fair::recursive_mutex
yamc::fair::timed_mutex
yamc::fair::recursive_timed_mutex

共有ロックとスケジューリング戦略

共有ロックはReaders-Writerロックとも呼ばれ、複数Readerスレッドからの同時読み取り操作と単一Writerスレッドの書き込み操作との排他制御を実現します。C++標準ライブラリではC++14から導入されましたが、Reader／Writerスレッド間でロック獲得が競合した場合の振る舞いは規定されていません。共有ロック競合時の振る舞いとして、非公平(unfair)スケジューリングと公平(fair)スケジューリングのアルゴリズムがいくつか存在します。

一般に非公平スケジューリングの方がオーバーヘッドが小さくて済み、一般的な共有ロックの利用ケースでは好ましいスケジューリング戦略です。一方でロック競合頻度が高くなるにつれ、Reader／Writerスレッド間のロック獲得機会が偏りが大きくなります。このような状況下では公平スケジューリング・共有ロックが有効な選択肢となりえます。最適なスケジューリング戦略は利用ケース毎にまちまちですから、対象プログラムの性能計測に基づいた選択をお勧めします。（通常は非公平スケジューリングで十分なはずです。）

本ライブラリでは2種類の共有ロック・ミューテックスと、それぞれに対して非公平スケジューリング2種類および公平スケジューリング2種類を提供します。スケジューリングポリシーはクラステンプレートbasic_shared_(time_)mutexのテンプレートパラメータとして与えるため、計8種類の共有ロック実装から選択できます。既定のスケジューリングポリシーにはReader-preferおよびPhase-fairnessを利用します。

// 不公平スケジューリング・共有ロック・ミューテックス
#include "alternate_shared_mutex.hpp"
yamc::alternate::shared_mutex        // 既定の不公平スケジューリング
yamc::alternate::shared_timed_mutex  // 既定の不公平スケジューリング
yamc::alternate::basic_shared_mutex<yamc::rwlock::ReaderPrefer>
yamc::alternate::basic_shared_mutex<yamc::rwlock::WriterPrefer>
yamc::alternate::basic_shared_timed_mutex<yamc::rwlock::ReaderPrefer>
yamc::alternate::basic_shared_timed_mutex<yamc::rwlock::WriterPrefer>

// 公平スケジューリング・共有ロック・ミューテックス
#include "fair_shared_mutex.hpp"
yamc::fair::shared_mutex        // 既定の公平スケジューリング
yamc::fair::shared_timed_mutex  // 既定の公平スケジューリング
yamc::fair::basic_shared_mutex<yamc::rwlock::TaskFairness>
yamc::fair::basic_shared_mutex<yamc::rwlock::PhaseFairness>
yamc::fair::basic_shared_timed_mutex<yamc::rwlock::TaskFairness>
yamc::fair::basic_shared_timed_mutex<yamc::rwlock::PhaseFairness>

スケジューリングポリシーのアルゴリズムは下記の通りです（名前空間yamcは省略）。

  • rwlock::ReaderPrefer：Readerスレッド優先(Reader-prefer)スケジューリング。待機中Readerスレッドがなくなるまで、Writerスレッドは排他ロック獲得を待機。Readerスレッド共有ロック獲得要求が高頻度の場合、Writerスレッドが飢餓状態(Writer Starvation)に陥るリスクがある。
  • rwlock::WriterPrefer：Writerスレッド優先(Writer-prefer)スケジューリング。待機中Writerスレッドがなくなるまで、Readerスレッドは共有ロック獲得を待機。Writerスレッド排他ロック獲得要求が高頻度の場合、Readerスレッドが飢餓状態(Reader Starvation)に陥るリスクがある。
  • rwlock::TaskFairness：タスク公平(Task-fairness)スケジューリング。Readersスレッド群とWriterスレッドの間でFIFOロック獲得順を保証。
  • rwlock::PhaseFairness：フェーズ公平(Phase-fairness)スケジューリング。FIFOロック順に加えてReader／Writerフェーズを交互に切り替え、Readerフェーズ移行時には全ての待機中Readerスレッドを共有ロック獲得可能とする。

公平スケジューリングポリシーの具体例として、4つのReader(R)／Writer(W)スレッドからW1→R2→W3→R4の順でロック獲得要求が起きたと仮定します。

  • タスク公平(Task-fairness)の場合、(1) W1による排他ロック獲得 → (2) R1による共有ロック獲得 → (3) W3による排他ロック獲得 → (4) R4による共有ロック獲得 の順となります。
  • フェーズ公平(Phase-fairness)の場合、(1) Writerフェーズ:W1による排他ロック獲得 → (2) Readerフェーズ:R1およびR4による同時共有ロック獲得 → (3) Writerフェーズ:W3による排他ロック獲得 の順となります。

スケジューリングポリシーの性能目安は https://github.com/yohhoy/yamc/wiki/perf_rwlock-201802 を参照ください。横軸はReader／Writerスレッドの割合を、縦軸は1スレッドあたりの共有／排他ロック獲得回数を表します。あくまで実験室的な計測データである旨に注意ください。

事前条件検査とデッドロック検知

C++標準ライブラリ提供のミューテックス型では、その操作に事前条件が設定されています。例えば再帰ロックをサポートしないstd::mutexに対して、同一スレッドから複数回lock関数を呼び出すことはできません。下記にあげたような事前条件に違反した場合の振る舞いは未定義の動作(Undefined Behavior)とされており、デッドロックやメモリ破壊などの危険な結果をもたらします。また複数ミューテックスのロック順序問題によってデッドロックが発生することもあります。

  • ロック所有しないスレッドからのunlock呼び出し
  • 再帰ロック非対応ミューテックスに対するロック所有スレッドからのlock／try_lockファミリ呼び出し
  • 任意スレッドでロック所有中のミューテックス・オブジェクトの破棄

本ライブラリでは、事前条件検査およびデッドロック検知*3を備えたデバッグ用途のミューテックス型を提供します。既定動作では問題検知時にstd::system_error例外を送出しますが、マクロ定義によりstd::abort関数呼び出しに変更可能です。あくまでデバッグ用途を想定しており、各種検査実現のためのメモリ消費および計算コストが追加されます。

// 検査機構付き・ミューテックス
#include "checked_mutex.hpp"
yamc::checked::mutex
yamc::checked::timed_mutex
yamc::checked::recursive_mutex
yamc::checked::recursive_timed_mutex

// 検査機構付き・共有ロック・ミューテックス
#include "checked_shared_mutex.hpp"
yamc::checked::shared_mutex
yamc::checked::shared_timed_mutex

下記は2スレッド×2ミューテックス間でのデッドロック検知時のエラー出力例です。スレッド0x70000c38c000がMutex#2ロック所有状態でMutex#1ロックを待機し、スレッド0x70000c309000がMutex#1ロック所有状態でMutex#2ロック獲得を待機しているため、相互循環によるデッドロックが生じています。

Thread#0x70000c38c000 wait for Mutex#1 lock
  Mutex#2: owners={0x70000c38c000} waiters={0x70000c309000}
  Mutex#1: owners={0x70000c309000} waiters={0x70000c38c000}

==== DEADLOCK DETECTED ====

雑談

モチベーション

Gist上で自作ミューテックス実装を書き散らかしていたのを、いい加減まとめようというのがライブラリ作成動機です。いっぱしのOSSらしく整理するにあたり、マルチスレッド同期プリミティブのユニットテスト記述とCI環境構築にもチャレンジしています。

諫言と免責事項

C++の最適化について扱う書籍「Optimized C++」にも言及がありますが、一般論としてミューテックスの自作は避けるべきとされます。

同期機構はただでさえ正しく実装するのが難しいことに加え、妥当性テストはさらなる困難と苦痛を伴います。本ライブラリではGCC／Clang／MSVC環境でのユニットテストCIを行いますが、その動作の正しさを保証するものではありません。しかもミューテックスのような基本構成要素の場合、OSカーネルに近い低レイヤで実装される標準ライブラリに比べると、自作ミューテックスの速度性能はさほど良くありません。

じゃあ何故作ったのかと言われると... 趣味？ミューテックスを自作しようと考える方のために、先行して地雷原を踏んでおきました。

*1:ライブラリ仕様ではミューックスの待機方法まで規定しませんが、スレッド休眠を行うC++標準ライブラリ実装が一般的です。

*2:厳密には、C++標準ライブラリ仕様ではロック競合時のスケジューリングについて何も規定しません。公平(fair)スケジューリングの実現には実行時オーバーヘッドが存在するため、特別な外部要件がない限り不公平(unfair)スケジューリング戦略が用いられます。

*3:汎用的なデッドロック検知実装ではなく、本ライブラリ提供のcheckedミューテックス間のみが対象となります。

メモリモデル？なにそれ？おいしいの？

C++

この記事はC++ Advent Calendar 2014の21日目にエントリしています。
内容はC++メモリモデルと逐次一貫性についての概説記事となっています。
f:id:yohhoy:20141221014421j:plain
flickr / nomadic_lass
もくじ

  1. 忙しい人のための「C++メモリモデル」
    1. C++メモリモデル一問一答
  2. ソフトウェアからみた「C++メモリモデル」
    1. “メモリ”という共有リソース
    2. C++ソースコードが実行されるまで
    3. メモリの一貫性と整合性
    4. 逐次一貫性モデル is Easy
  3. ハードウェアからみた「C++メモリモデル」
    1. ハードウェア・メモリ一貫性モデル
    2. C++コンパイラの責任と自由
    3. 強いメモリモデル vs. 弱いメモリモデル
    4. 逐次一貫性モデル is Hard

（本文のみ約9600字）

まえがき

When your hammer is C++, everything begins to look like a thumb.

突然ですが、「メモリモデル(memory model)」という単語を聞いたことはありますか？プログラミング関連の用語として様々な文脈で言及されますが、その正体は曖昧ではっきりせず、まるで神秘のベールに包まれているかのようです。プログラミング言語C++でもマルチスレッド処理が標準サポートされ、同時に「C++メモリモデル」と呼ばれる何かが導入されました。

本記事ではこの「C++メモリモデル」について、大まかな雰囲気を掴めるような概要説明を試みます。C++メモリモデルの細部にまで深入りすると、C++言語仕様の深淵を覗き込む話題になってしまうため、とても詳細な解説までは行えません。そのためhappens-before関係をはじめ形式的な定義への言及を避けながら説明をしていきます。

C++メモリモデルの説明に入る前に、曖昧な単語「メモリモデル」の用法について整理しておきましょう。主に下記4パターンのいずれかで用いられるようです。*1

メモリ・アドレッシング・モデル
低レイヤでのプログラミングにおいて、あるメモリ番地を指定(addressing)する方式。古のIntelプロセッサ・リアルモードや、DSP(digital signal processor)などの文脈で用いられる。
メモリ・マネジメント・モデル
仮想マシン(VM)実装において、オブジェクト配置に関連するメモリ管理(management)の方式。Java VM実装の文脈で用いられる。
ハードウェア・メモリ一貫性モデル
プロセッサ・アーキテクチャにおいて、特にマルチプロセッサ・システムからの共有メモリ・アクセス順序に関するモデル。一般にIntel x86(IA-32, x86-64)やSPARC TSOなどは“強いメモリモデル”、ARMやPower PC, Itanium(IA-64)などは“弱いメモリモデル”と紹介される。
ソフトウェア・メモリ一貫性モデル
プログラミング言語において、特にマルチスレッド・プログラムからの共有メモリ・アクセス順序に関するモデル。主要なところではJava言語[Java1.5以降]*2, C++言語[C++11以降], C言語[C11以降], Go言語、他にもPOSIX Threads(Pthreads), OpenMP, LLVM IRなど、マルチスレッド対応のプログラミング言語ではメモリモデルが定義される。*3

本記事ではメモリモデルという単語を、後者「メモリ一貫性モデル(memory consistency model)」の意で扱います。まずはソフトウェア・メモリ一貫性モデルとしてのC++メモリモデルを説明し、続いてハードウェア・メモリ一貫性モデルとの関連性と相違点をみていきます。

1. 忙しい人のための「C++メモリモデル」

今北産業

C++メモリモデル？
そんなものは
無かった

低レイヤなatomic変数(std::atomic)やミューテックス(std::mutex)、生のC++スレッド(std::thread)も全部忘れて、高レイヤな並列処理ライブラリを活用しましょう！

1.1. C++メモリモデル一問一答

Q. C++でマルチスレッド・プログラムを書くために、C++メモリモデルの知識が必要ですか？
A. いいえ。スレッドもミューテックスも、プログラマが知っている通りに動作します。

Q. atomic変数を使ったロックフリー(lock-free)なアルゴリズム記述には必要ですよね？
A. いいえ。C++メモリモデルを知らなくても、正しく動作するロックフリー処理は記述できます。（もちろん別の知識が要求されますが！）

Q. ミューテックスやatomic変数とC++メモリモデルって無関係なの？
A. いいえ、とても深い関係があります。C++メモリモデルは、あらゆるC++実行環境においてミューテックスや“既定の”atomic変数アクセスが、プログラマの期待通りに振る舞うことを保証します。

Q. “既定の”atomic変数アクセスとは？
A. C++ atomic変数への書き出し／読み取りでは、その振る舞い（memory_order列挙型）を制御できます。ただし、特に何も指定せずatomic変数を使うぶんには、普通のプログラマが考える通りに動作するため、C++メモリモデルを理解している必要はありません。

Q. プログラマが考える通りに動作しないことがある？
A. C++ atomic変数アクセスの振る舞いを変更すると、多くのプログラマの直観とは合致しなくなります。C++メモリモデルでは、既定(memory_order_seq_cst)でないatomic変数アクセスの振る舞いもちゃんと定義しますが、それらを正しく理解し使いこなすのは相当にハードルが高いです。

Q. 結局、C++メモリモデルって誰得なの？
A. OSカーネル開発者や高度にチューニングされた並行／並列処理ライブラリ開発者、C++コンパイラ・バックエンド最適化器の開発者、あとは言語法律家(language lawyer)あたりでしょうか。C++メモリモデルは、C++言語の基盤を支える重要な概念ですが、全てのC++プログラマが理解すべきものではありません。

Q. マルチスレッド・アプリケーションの開発者には、関係ないってこと？
A. はい。C++メモリモデルのような低レイヤについて悩むよりも、高レイヤでの並行／並列処理設計を気に掛けるべきです。

という訳で、本記事の要旨はこれだけです。この先は抽象的で退屈な話題がつづきますが、それでも大丈夫という方は続きをどうぞ。

おことわり：以降の説明では、C++マルチスレッド・プログラミングにおいてミューテックスを適切に使用したり、atomic変数がどのようなものか分かる程度の経験があること、また今どきのプロセッサ・アーキテクチャやメモリ・キャッシュ機構の仕組みを概要程度は理解していること、を前提とします。

2. ソフトウェアからみた「C++メモリモデル」

C++メモリモデルは、C++11でのマルチスレッド処理サポートと同時に導入された、“メモリ”の扱いに関する形式的なルールです。まずは、マルチスレッド・プログラムにおけるメモリの扱いを整理します。つづいて普段はあまり気にかけない、C++ソースコードとC++コンパイラや実行環境との関係、そもそもC++言語仕様では何を定義するかを確認します。最後に、プログラマ視点では最も重要となる「逐次一貫性モデル」を紹介します。

2.1. “メモリ”という共有リソース

マルチスレッド・プログラムはその名前が示す通り、複数の「実行スレッド(thread of execution)」（一般に「スレッド(thread)」と呼ぶ）、つまり同時並行に動作可能な実行主体を複数個もちます。スレッドを軽量プロセスと呼ぶこともありますが、メモリの扱いはプロセスとスレッドで大きく異なります。通常のプロセスはそれぞれ独立したメモリ空間を管理し、互いのメモリ空間に直接干渉することはできません。一方のスレッドでは同じメモリ空間を共有するため、メモリを介したデータ通信や同期制御が可能です。つまり、マルチプロセス処理は分散型メモリ・並行処理システム、マルチスレッド処理は共有型メモリ・並行処理システムと解釈可能です。

マルチスレッド・プログラムにおけるメモリ空間は、概念的には複数スレッドから利用される共有リソースといえます。このようにメモリ空間を1つの共有リソースとみなし、各スレッドからメモリに書き出す値／メモリから読み取る値に関して、スレッド間で共有される“メモリ”というリソースがどのように振る舞うかを定義したものが「ソフトウェア・メモリ一貫性モデル」です。ここでいう“メモリ”とは、1個の変数に対応したメモリ領域のみを指すのではなく、あらゆる変数が配置されたメモリ空間全体を指すことに留意ください。つまり「C++メモリモデル」は、C++で記述されたマルチスレッド・プログラムにおいて、複数の変数アクセスにより書き出す値／読み取る値の振る舞いを定義します。

2.2. C++ソースコードが実行されるまで

C++メモリモデルはC++言語仕様の一部ですが、最初に“C++言語仕様とは何を定義するか”を確認しておくべきでしょう。2014年12月現在のC++言語仕様は、正式名称 ISO/IEC 14882:2011 という国際標準規格にて定義されます*4。GCCやLLVM/ClangやMicrosoft Visual C++など全てのC++コンパイラは、この標準規格が定めるC++言語仕様に則って実装されており*5、入力C++ソースコードから出力機械語プログラムへの変換処理を行います。では、C++言語仕様は“C++ソースコードからどのような機械語へ変換するか”を定義するのでしょうか。C++言語は多種多様なプロセッサ・アーキテクチャを対象としており、このアプローチは現実的ではなさそうです。

実際のC++言語仕様では、まず抽象機械(abstract machine)と呼ばれる仮想的な実行環境を定義し、C++ソースコードが抽象機械上でどのように動作するかを記述します。C++11でマルチスレッド対応したというのは、この抽象機械にスレッドという概念が導入されたことを意味します。この抽象機械上での動作定義は、C++コンパイラによるC++ソースコードから機械語プログラムへの変換処理と、プロセッサ上での機械語プログラムの実行処理の両方を包含します。つまり、C++言語仕様では“入力C++ソースコードはどのように動作すべきか”のみを定義し、具体的な変換処理（コンパイル処理）や実行時処理は、C++コンパイラと対象プロセッサ・アーキテクチャに任せているのです。*6
f:id:yohhoy:20141221005030p:plain

これだけだとコンパイル処理には自由度など無いように聞こえますが、現実のC++コンパイラはさまざまな「最適化」を行います。最適化とは処理の省略や変形によって動作の高速化を図るものですが、C++言語仕様でC++ソースコードのあるべき動作が決められているのに、どこに省略や変形の余地が残っているのでしょうか。実は抽象機械による動作定義には続きがあり、“最終結果が同じである限りどんな変形を行ってもよい”という特別ルールが設けられています（通称、as-ifルールと呼ぶ）。抽象機械上でのマルチスレッド・プログラムの“最終的な結果が等価である”こと、つまり処理の省略や変形を行っても等価なプログラムとは何かということを、厳密に仕様記述するために「C++メモリモデル」が存在します。*7 *8

2.3. メモリの一貫性と整合性

異なるスレッドから“同時に”アクセス可能なのはatomic変数に限られており、C++マルチスレッド・プログラム上から通常の変数に同時アクセスした場合は、データ競合(data race)による未定義動作を引き起こします。「C++メモリモデル」では、まさにこの別スレッドからの操作が“同時でなくなる”条件を、各スレッドからの“操作間に順序付け(ordering)が保証される”という形で表現します。「C++メモリモデル」の本質はこの“操作間の順序付け”を定義することであり、atomic変数だけでなくC++標準ライブラリ提供同期プリミティブの振る舞いも包括的に記述します。例えばミューテックス(std::mutex)オブジェクトが排他制御として機能することは、lock／unlock操作間での順序付け保証として表現されます。*9

「C++メモリモデル」はソフトウェア・メモリ一貫性モデルであると説明してきましたが、似た意味の単語"Coherency"と"Consistency"との違いを明確化しておきましょう。辞書によっては両者とも“一貫性”と訳されてしまいますが、C++メモリモデルでは下記の通り区別されます。なお、整合性は一貫性の議論対象を限定したものとみなせ、一般にメモリ一貫性モデルは整合性に関する定義を内包します。

整合性(Coherency)
異なるスレッドから単一のatomic変数にアクセスしたとき、各スレッドが書き出す値／読み取る値の関係を定義する。
一貫性(Consistency)
異なるスレッドから異なるatomic変数にアクセスしたとき、各スレッドが書き出す値／読み取る値の関係を定義する。

“整合性(Coherency)”は同一atomic変数(M)からの読み／書きを対象とし、その振る舞いは下記リストの通りとなります。少し読みづらいと思いますが、一度は丁寧に追ってみてください。

  • A:M = 1 → B:M = 2 と順序付けられるとき、最終的なMの値は Bで書き出した値2 となる。
  • A:r0 = M → B:M = 2 と順序付けられるとき、最終的なMの値は Bで書き出した値2 となる。なお、Aでは Bで書き出した値2 を読み取ることはない。
  • A:r0 = M → B:r1 = M と順序付けられるとき、Bでは Aが読み取った値r0 を再び読み取る。
  • A:M = 1 → B:r1 = M と順序付けられるとき、Bでは Aで書き出した値1 を読み取る。

あまりに当然のことで退屈に感じるでしょうが、このようにプログラマが当然期待するメモリ・アクセスの振る舞いを、C++メモリモデルでは形式的に定義していきます。*10

2.4. 逐次一貫性モデル is Easy

“整合性(Coherency)”では単一atomic変数が対象でしたが、“一貫性(Consistency)”の対象は複数atomic変数へと拡大されます。マルチスレッド・プログラム頭の体操ということで、下記コードの実行結果がどうなるか考えてみてください。関数th1, th2は異なるスレッドからそれぞれ1回だけ呼ばれるものとします。

#include <atomic>
std::atomic<int> x = 0;
std::atomic<int> y = 0;
int r1, r2;

void th1() {
  y = 1;
  r1 = x;
}
void th2() {
  x = 1;
  r2 = y;
}
// 各スレッドが読み取った r1, r2 の値は？

正解は{r1,r2}＝{0,1}, {1,0}, {1,1}の3パターンのいずれかです。マルチスレッド・プログラムでは、このように実行結果が一意に定まらない（非決定的動作）ことがあるため、ちゃんと3パターンとも回答してくださいね*11。では{0,0}という実行結果は起こりえるでしょうか？

“結果{0,0}なんて起きるわけないだろ！”と考えた方、おめでとうございます。あなたはもう「逐次一貫性(sequential consistency)」を理解しています。そんな自覚は無かったというなら、無意識に逐次一貫性モデルを適用したのです。“いや、もしかしたらありえるかも”と考えたあなたは、…天が落ち地が崩れるのを心配するタイプですか？杞の国の人は別にして、このように逐次一貫性モデルはプログラマの直感とよく合致しており、「C++メモリモデル」では“既定の”atomic変数アクセスの振る舞いが逐次一貫性モデルに従うことを保証しています。

逐次一貫性モデルに従って、前掲マルチスレッド・プログラムの実行結果を確認してみましょう。Wikipediaでは逐次一貫性を次のように説明しています。（Lamport氏オリジナル論文からの引用訳）

どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること。

本記事ではC++メモリモデルの議論にあわせて、下記説明に改変します。*12

マルチスレッド並行処理の結果は、各スレッド上のatomic変数操作をシングル・スレッドで任意にインターリーブ実行した結果と一致すること。

この説明なら少しは分かり易くなったでしょうか。3パターンの結果を導くインターリーブ実行例を挙げてみます。

// {r1,r2}={0,1}のインターリーブ実行例
y = 1;   // th1-1
r1 = x;  // th1-2
x = 1;   // th2-1
r2 = y;  // th2-2

// {r1,r2}={1,0}のインターリーブ実行例
x = 1;   // th2-1
r2 = y;  // th2-2
y = 1;   // th1-1
r1 = x;  // th1-2

// {r1,r2}={1,1}のインターリーブ実行例
y = 1;   // th1-1
x = 1;   // th2-1
r1 = x;  // th1-2
r2 = y;  // th2-2

f:id:yohhoy:20141221005652p:plain

結果{0,0}が生じるには、最初にatomic変数x, yからの読み取りが行われる必要がありますが、これだと関数th1, th2内でのオリジナル処理順序を壊しています。

// NG: 逐次一貫でない
r1 = x;  // th1-2
r2 = y;  // th2-2
y = 1;   // th1-1
x = 1;   // th2-1

f:id:yohhoy:20141221005709p:plain
上記のような入れ替えは直感的にも許されませんし、もちろん逐次一貫性モデルでも許容されません。このように「C++メモリモデル」が“既定の”atomic変数アクセスに対して逐次一貫性を保証するため、プログラマは安心してatomic変数を使ったマルチスレッド処理を記述できます。

ところで“既定でない”atomic変数アクセスでは一体何が起きるのでしょう？前掲サンプルコードを少し変更してみます。*13

#include <atomic>
std::atomic<int> x = 0;
std::atomic<int> y = 0;
int r1, r2;

void th1() {
  y.store(1, std::memory_order_release);
  r1 = x.load(std::memory_order_acquire);
}
void th2() {
  x.store(1, std::memory_order_release);
  r2 = y.load(std::memory_order_acquire);
}
// 各スレッドが読み取った r1, r2 の値は？

この変更後コードの実行結果は、{r1,r2}＝{0,1}, {1,0}, {1,1}, {0,0}の4パターンのいずれかになります。“既定の”atomic変数アクセスでは起こりえなかった{0,0}も含まれる通り、逐次一貫性よりも“弱い”順序付けの振る舞いは、プログラマの直観とは合致しない結果をもたらします！

さて、本当の「C++メモリモデル」の話題はここから始まるのです。…が、これ以上は本記事の範囲（と私の理解度と説明力）を超えています。あしからずご了承ください。

では、説明内容をまとめておきましょう。「C++メモリモデル」とは：

  • メモリ空間全体を複数スレッド間での共有リソースとみなします。
  • 複数スレッドからメモリへの書き出し／読み取りの振る舞いを定義します。
  • C++ソースコードが抽象機械でどのように動作するかを定義します。
  • as-ifルールに基づく等価なプログラム変換（許される最適化）を定義します。
  • 操作が“同時でない”とは何かを順序付けにより定義します。
  • 同期プリミティブの振る舞いを順序付けにより記述します。
  • 単一のatomic変数に対するアクセスの整合性を保証します。
  • 複数のatomic変数に対する既定アクセスの逐次一貫性を保証します。



3. ハードドウェアからみた「C++メモリモデル」

ここまで「C++メモリモデル」をソフトウェア視点で説明してきましたが、C++言語で書かれたプログラムは実在のプロセッサで動く以上、ハードウェア視点でも見ていく必要があるでしょう。プロセッサ・アーキテクチャは固有のハードウェア・メモリ一貫性モデルを持つため、まずは「C++メモリモデル」との関係性を整理します。また、いわゆる“強いメモリモデル”や“弱いメモリモデル”のプロセッサ・アーキテクチャと、C++メモリモデルが既定で提供する逐次一貫性モデルとの関係を説明します。

3.1. ハードウェア・メモリ一貫性モデル

マルチプロセッサ・システムでは各プロセッサがメインメモリに直結されるのではなく、一般的には何段かのメモリ・キャッシュ機構を経由します。さらに単体プロセッサのスループット性能を向上させるため、命令発行順序を入れ替えるアウト・オブ・オーダー(OoO; Out-of-Order)実行も行います。これらの技術によって処理性能向上が図られてきましたが、一方で機械語プログラムに“書いてある順序”でメモリ・アクセスが行われなくなるという問題を引き起こします。さすがに何の保証もされないシステムでは正しいプログラムが成立しえないため、プロセッサ・アーキテクチャとしてメモリ・アクセス順序に関する一定の保証、つまり「ハードウェア・メモリ一貫性モデル」が必要とされます。このような順序保証を与えるために、メモリ・ストア(store)やロード(load)命令に順序付け制約効果を持たせたり、命令発行順序の入れ替えを禁止するメモリバリア(memory barrier)命令などが提供されています。

「C++メモリモデル」が定義する順序付けと、ハードウェア・メモリ一貫性モデルが定義する順序付けでは、その意味合いが少し異なります。C++メモリモデルでは、異なるスレッド上でのメモリ・アクセス操作間に対して、維持すべき順序関係を定義します。ハードウェア・メモリ一貫性モデルでは、同一スレッド上のメモリ・ストア／ロード命令間で、先行命令の追い越し禁止を表現します。前者は抽象的な操作の関係性に着目し、後者は具体的な制限事項に落とし込んだ定義といえます。

3.2. C++コンパイラの責任と自由

C++ソースコードがマルチプロセッサ・システムで実行されるまでのステップは、ご存知のようにコンパイル処理と実行時処理に分割されています。既に説明した通り、各ステップではメモリ・アクセスに関する順序入れ替えが発生します。

コンパイル処理
C++コンパイラによるC++ソースコードから機械語プログラムへの変換。コンパイラの最適化により命令配置順序の入れ替えが行われる。
実行時処理
マルチプロセッサ・システムによる機械語プログラムの解釈実行。メモリ・キャッシュ機構やOoO実行によりメモリ・アクセス順序の入れ替えが行われる。

f:id:yohhoy:20141221012549p:plain
「C++メモリモデル」は、C++言語仕様という仮想世界の抽象機械に対してメモリ・アクセスの振る舞いを定義しており、対応する現実世界ではコンパイル処理および実行時処理のメモリ・アクセスの振る舞いにそれぞれ影響を及ぼします。「C++メモリモデル」により記述される自由度と制約条件に従って、C++ソースコードから機械語プログラムへの変換時に、C++コンパイラは命令配置順序の並び替えやメモリバリア命令挿入を行います。マルチプロセッサ・システムは自身のハードウェア・メモリ一貫性モデルに従って、C++コンパイラが生成した機械語プログラムを解釈実行します。そして、このコンパイル処理と実行時処理の組合せによって得られる最終結果は、as-ifルールの下で抽象機械の動作結果と一致しなければなりません。

プロセッサによる機械語プログラムの解釈実行ステップでは、元のC++ソースコードが表現していた順序付け関係を直接知ることはできません。C++コンパイラの責任とは、C++ソースコードが表現するプログラム動作セマンティクスを維持できるよう、ハードウェア・メモリ一貫性モデルに従う機械語プログラムへと翻訳することなのです。一方、as-ifルールの下でプログラム動作セマンティクスが等価である限り、コンパイル時のあらゆるメモリ・アクセス命令の入れ替え（最適化）や、実行時のメモリ・キャッシュ機構やOoO実行によるメモリ・アクセス順序入れ替えが許容されるとも言えます。

3.3. 強いメモリモデル vs. 弱いメモリモデル

世の中には多様なプロセッサ・アーキテクチャが存在しており、それぞれが固有のハードウェア・メモリ一貫性モデルを持ちます。よく強いメモリモデル／弱いメモリモデルと分類されますが、これはメモリ・アクセス命令が持っているメモリ・アクセス順序保証の度合いを強弱で言い表したものです。強いメモリモデルでは順序保証の度合いが強く、ほぼ機械語プログラムに記載された順番のままメモリ・アクセスが行われます。弱いメモリモデルでは、実行時のメモリ・アクセス順序が機械語プログラム中のメモリ・アクセス命令順と一致するとは限りません。つまり「ハードウェア・メモリ一貫性モデル」とは、そのプロセッサ・アーキテクチャで最低限保証されるメモリ・アクセスの振る舞いに関する順序保証を表します。たとえ弱いメモリモデルであっても、明示的なメモリバリア命令と組み合わせれば順序保証を行えることに留意ください。

一般的なプロセッサ・アーキテクチャのハードウェア・メモリ一貫性モデルは、「C++メモリモデル」が既定で提供する逐次一貫性よりも“弱い”順序保証しか与えません。強いメモリモデルを持つと言われるIntel x86アーキテクチャ・ファミリ(IA-32, x86-64)でさえ、マルチプロセッサ・システムでは逐次一貫性モデルよりも“弱い”メモリモデルなのです。これはプロセッサ・アーキテクチャで逐次一貫性を実現するには、追加のオーバーヘッドを伴うことを意味します。特にマルチプロセッサ・システムではメモリ・キャッシュ機構の存在が問題となります。

3.4. 逐次一貫性モデル is Hard

マルチプロセッサ・システムで全てのプロセッサがメインメモリに直結されると仮定した場合、あるプロセッサからのメモリ書き出し／読み取りはすぐに他プロセッサから“見える”ため、逐次一貫性を実現するのは難しくありません。実際にはメモリとプロセッサの間にメモリ・キャッシュ機構が介在し、メモリ書き出し／読み取りではメインメモリ内容と“全ての”プロセッサのメモリ・キャッシュ内容の辻褄を合わせる（キャッシュ・コヒーレンシ制御）必要があります。このようなメモリ・キャッシュの制御は、プロセッサとメモリを物理的につなぐインターコネクトやバス上での通信によって実現されます。マルチプロセッサ・システムのような共有型メモリ・並行処理システムでは、プロセッサ数が増えると通信量が指数的に増大してしまうため、現実のマルチプロセッサ・システムにとって逐次一貫性モデルを保証するのはコストが大きいのです。

ソフトウェア視点での結論とは逆に、ハードウェア視点では残念な結論となってしまいましたが、メジャーなプロセッサ・アーキテクチャ固有の話も少しだけ言及しておきます。*14

Intel x86(IA-32, x86-64)
逐次一貫性にかなり近いハードウェア・メモリ一貫性モデルのため、追加のオーバーヘッドはほとんどありません。atomic変数への書き出し処理だけが若干のペナルティを受けます(lock xchg命令)。
ARM(ARMv7, ARMv8)
弱いメモリモデルのハードウェア・メモリ一貫性モデルのため、逐次一貫性の実現にはメモリバリア命令発行が必要です(dmb命令)。ARMv8では専用のメモリ・ストア／ロード命令が追加され(stlr/ldar命令)、メモリバリア命令発行が不要になります。

弱いメモリモデルを持つマルチプロセッサ・システム性能を最大限引き出すには、対象プロセッサ・アーキテクチャのハードウェア・メモリ一貫性モデルを理解し、かつC++ atomic変数アクセスにおいて逐次一貫性より“弱い”順序付けを指定する必要があります。とはいえ一般にマルチスレッド・アプリケーションでは、そもそもatomic変数のような低レイヤ同期プリミティブを頻繁には利用しません。OSカーネル開発者や並行／並列処理ライブラリ開発者を別にすれば、アプリケーション・プログラマがこの領域まで踏み込む必要はないと思います。

おわりに

本記事では「C++メモリモデル」が何のためにあり、どのような意義を持つかをトップダウン式アプローチで説明しました。C++言語仕様では厳密かつ形式的な定義を行いますが*15、ボトムアップにそれらを理解するのは骨の折れる作業です。本記事がこれからC++言語仕様を読んでみようというイカれた暇人知的好奇心旺盛な方への参考情報となれば幸いです。

C++ Advent Calendar 2014 は 22日目 hgodai さんの記事へと続きます。
f:id:yohhoy:20141221014550j:plain
flickr / ed_welker

はしがき：昨年に引き続いて、手書き画像には"Paper by FiftyThree"を使いました。ズーム機能があることに気付いたので、今年の方が文字は読みやすいかも？（そもそも字が汚いのはアレ）

*1:Internet上でのオレオレ調査による。各用語は本記事のために独自定義しており、対象文脈における一般的な用語とは異なる可能性があります。

*2:プログラミング言語におけるソフトウェア・メモリ一貫性モデルの重要性は、Java 1.4以前での“Double-Checked Locking問題”を発端に見直されました。後発のC++メモリモデル定義は、Java言語での実績や改善を反映したものとなっています。

*3:C#言語（別名 ECMA-334）もマルチスレッド対応した主要プログラミング言語といえますが、2014年12月現在もそのメモリモデルは言語仕様として厳密定義されておらず、Microsoft CLR実装＝マルチスレッド動作仕様というお寒い状況のようです。

*4:本記事では2014-12-21現在の標準規格を“C++14”ではなく“C++11”としています。2014年8月にはisocpp.org記事"We have C++14!"とアナウンスがありましたが、ISO公式サイトによると2014-12-17付けでStage 60.00(International Standard under publication)であり、国際標準規格としては正式発行の寸前という状況のようです。2014年内に間にあうんですかね？

*5:もちろん、各コンパイラベンダによる独自仕様拡張や、標準規格への準拠度合いの違いはあります。

*6:本文中ではC++ソースコードから機械語プログラムに変換するC++コンパイラを前提としていますが、C++ソースコードから直接実行するC++インタプリタも存在しえます。C++言語仕様はどちらの実装形態も許容します。

*7:過去のC++言語仕様においても、副作用完了点(sequence point)という形で「C++メモリモデル」相当の定義は存在します。ただしC++03時点ではスレッドという概念が存在しないため、C++マルチスレッド・プログラムの意味はC++コンパイラベンダ依存や、POSIX Threadsなどの外部システム依存とされていました。

*8:C++言語仕様に沿った厳密な解釈をすると、一般に「C++メモリモデル」と呼ばれる言い回しは正確ではありません。C++11言語仕様でメモリモデルを探すと1.7節 The C++ memory model [intro.memory]が見つかりますが、ここは“バイト(byte)”や“メモリ位置(memory location)”を定義しているに過ぎません。本記事では「C++メモリモデル」＝ソフトウェア・メモリ一貫性モデルと解釈していますので、対応する規格文面は1.9節 Program execution [intro.execution]、1.10節 Multi-threaded executions and data races [intro.multithread]、およびatomic変数を定義する29章 Atomic operations library [atomics]が該当します。

*9:C++標準ライブラリ提供のミューテックス仕様では、“前のunlock操作からlock操作へのsynchronize-with関係が成立する”とだけ記述されます。この簡素な定義とC++メモリモデルをもとに解釈すると、プログラマが期待する通りの排他制御が実現されます。

*10:単一atomic変数アクセスに関する整合性は、最も弱い順序付けであるrelaxdアクセスを含む全てのmemory_orderで保証されます。

*11:たまに誤解されていますが、マルチスレッド・プログラムでは必ず非決定的動作(indeterminate behavior)となるわけではありません。並列処理設計によっては、入力値に対応した一意な結果が求まる“決定的動作のマルチスレッド処理”を構築可能です。なお、データ競合による未定義動作(undefined behavior)とマルチスレッド処理の非決定的動作には直接的な関係はありません。データ競合を一切含まないマルチスレッド・アプリケーションであっても、例示コードのように非決定的動作になることはあります。一方でデータ競合を含むマルチスレッド・アプリケーションでは、C++言語仕様上は何ら保証がされないものの、未定義動作による現実の帰結として非決定的動作となるケースがあります。

*12:Lamport定義に照らし合わせると、「すべてのプロセッサがある順序で逐次的に実行」＝シングル・スレッドで任意にインターリーブ実行、「個々のプロセッサの処理順序がプログラムで指定された通り」＝関数内でのオリジナル処理順序は維持される、という対応付けになっています。

*13:C++標準ライブラリatomicクラステンプレートでは演算子オーバーロードを行うため、“既定の”atomic変数アクセスであれば通常変数と同じように取り扱うことができます。atomic変数アクセスの振る舞いを指定するときは、明示的にstore／loadメンバ関数を呼び出さなければなりません。

*14:情報源： http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

*15:C++メモリモデルではあらゆる順序付けについて厳密な定義を行いますが、それでもmemory_order_relaxedによるout-thin-air-value問題や、memory_order_consumeと関連属性に関する合意などの未解決課題が残っています。

条件変数 Step-by-Step入門

C++ C POSIX Boost

多くのプログラミング言語では、マルチスレッド処理向け同期プリミティブとして「ミューテックス(mutex)」と「条件変数(condition variable)」を提供しています*1 *2。ミューテックスは排他制御機構として有名ですし、その動作もロック(lock)／アンロック(unlock)と比較的理解しやすいため、不適切に利用されるケースはあまり無いと思います*3。一方、条件変数の動作仕様はしばしば誤解され、不適切な利用による並行性バグに悩まされるケースが多いようです。

本記事では、スレッドセーフなFIFO(First-In-First-Out)キューを段階的に実装していく事例を通して、条件変数の適切な使い方について説明していきます。例示コードではC++11標準ライブラリを用いますが、Pthreads(POSIX Threads)やC11標準ライブラリへは単純に読み替え可能です（→Pthreads/C++11/C11対比表）。また、C++11標準ライブラリからBoost.Threadライブラリへの対応関係は自明なはずです。

本記事中のソースコードはBoost Software License 1.0で公開しています。

Pthreadsに馴染みがある人向けの補足：pthread_cond_signal→notify_one、pthread_cond_broadcast→notify_allへと読み替えてください。

さっそく

次の仕様を満たす、スレッドセーフ・FIFOキューmt_queueを実装していきます。

クラス仕様
int型要素を最大10個まで格納可能なFIFO操作コンテナ。各メンバ関数を異なるスレッドから同時に呼び出してもよい（スレッドセーフ）。*4
push操作
キューに新しい要素を1つ追加する。キューに空き容量が無ければ、空きができるまで呼び出し元スレッドをブロッキングする。
pop操作
キューから最も古い要素を1つ取り出す。キュー内に要素が存在しなれば、要素が追加されるまで呼び出し元スレッドをブロッキングする。

とりあえずロジックだけ実装すると、下記のような感じでしょうか。

#include <queue>

class mt_queue {
  static const int capacity = 10;
  std::queue<int> q_;
public:
  void push(int data) {
    while (q_.size() == capacity)
      ;
    q_.push(data);
  }
  int pop() {
    while (q_.empty())
      ;
    int data = q_.front();
    q_.pop();
    return data;
  }
};

このコードはマルチスレッド動作について一切考慮していないため、異なるスレッドからpush()/pop()メンバ関数が同時に呼び出されると、データ競合(data race)により正常に動作しません（データ競合についてはこちらの記事も参照下さい）。偶然に正常動作する可能性もゼロではありませんが、本質的に“壊れた”コードであると認識すべきです。マルチスレッド処理プログラミングでは並行処理設計が何よりも重要です。1万回に1回といった低頻度でのプログラムクラッシュ、システム高負荷状態でのみ発生するデッドロック、デバッグビルドは問題無いのにリリースビルドだと処理ストールといった、ステキなデバッグ体験をしたいのでない限り、“とりあえず動けばOK”という方針はお勧めできません。

Step0: ミューテックス＋ビジーループ

マルチスレッド処理プログラミングでは、ミューテックスによる排他制御が全ての基本となります。複数スレッドから同時更新される可能性のある変数アクセスは、ミューテックスによるロックで全て保護する必要があります。まずは、最も単純なビジーループ(busy-loop; busy-wait)方式で仕様通り実装してみましょう。［mt_queue0.cpp］

// mt_queue0.cpp抜粋
#include <mutex>

class mt_queue {
  //...
  std::mutex mtx_;  // ★ミューテックスを導入
public:
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);  // ロック獲得
    while (q_.size() == capacity) {
      lk.unlock();  // ロック一時解放
      std::this_thread::yield();
      lk.lock();    // ロック再獲得
    }
    q_.push(data);
  }  // ロック解放
  int pop() {
    std::unique_lock<std::mutex> lk(mtx_);  // ロック獲得
    while (q_.empty()) {
      lk.unlock();  // ロック一時解放
      std::this_thread::yield();
      lk.lock();    // ロック再獲得
    }
    int data = q_.front();
    q_.pop();
    return data;
  }  // ロック解放
};

メンバ関数実装のwhileループ中で、ロック一時解放lk.unlock()→ロック再獲得lk.lock()を忘れずに記述しましたか？このロック一時解放を行わないと、push()/pop()の同時呼び出しでデッドロックが発生します。例えば、1)キューが空っぽのときpop()呼び出し→2)ロックを保持したままwhile (q_.empty())ループ→3)別スレッドのpush()呼び出し先頭で永久にロック獲得待ちという状況です。もう1パターン自明なデッドロックシナリオがありますが、こちらは練習問題として考えてみて下さい。ヒント：push/popの状況を逆転
また、ロック一時解放領域でyield()を呼び出していますが、この処理を省略してもmt_queueクラスは仕様通り動きます。処理系によってはyield()の有無で動作性能が改善するでしょうが、ビジーループがCPUリソースを浪費する非効率な方式であることに変わりはありません。（ビジーループが常に不適切ということではなく、OSカーネルやハードウェア制御ドライバなどの低レイヤ・プログラミングでは有用なケースもあります。ただし、通常のアプリケーションプログラミングでは基本的に避けるべきでしょう。）

Step1: 条件変数による待機／通知処理

それでは、さっそく条件変数を使っていきましょう。排他制御用のミューテックスはそのままに、新しく条件変数を追加することに注意してください。ここはよく誤解されるポイントなのですが、セマフォのようにそれ単体で機能する同期プリミティブと異なり、条件変数は必ずミューテックスと紐付けて利用しなければ意味をなしません。［mt_queue1.cpp］

// mt_queue1.cpp抜粋
#include <mutex>
#include <condition_variable>
 
class mt_queue {
  //...
  std::mutex mtx_;
  std::condition_variable cv_;  // ★条件変数を追加
public:
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    while (q_.size() == capacity) {
      cv_.wait(lk);    // 要素数変更があるまで待機
    }
    q_.push(data);
    cv_.notify_all();  // 要素数変更を通知
  }
  int pop() {
    std::unique_lock<std::mutex> lk(mtx_);
    while (q_.empty()) {
      cv_.wait(lk);    // 要素数変更があるまで待機
    }
    int data = q_.front();
    q_.pop();
    cv_.notify_all();  // 要素数変更を通知
    return data;
  }
};

このコードでは条件変数オブジェクトcv_を、「キュー内の要素数に何らかの変更があった」イベントの待機／通知処理に利用しています。このときCPUリソース利用の観点からは、条件変数を用いた待機ループwhile (条件式) { cv_.wait(lk); }は、ビジーループの効率的な実装と解釈できます。つまりクラス利用者の視点からは、ビジーループ実装と条件変数実装とでFIFOキューの動作仕様に違いはなく、プログラム実行時の振る舞いだけが異なるものとなります。

// Step0(mt_queue0.cpp)
while (条件式) {
  lk.unlock();
  std::this_thread::yield();
  lk.lock();
}

// Step1(mt_queue1.cpp)
while (条件式) {
  cv_.wait(lk);
}

条件変数に対する待機cv_.wait(lk)は、内部的には“ロック一時解除lk.unlock()＋条件変数へ通知があるまで自スレッドを休止＋ロック再取得lk.lock()”処理を行います。ビジーループ版では他スレッドに実行機会のヒントを与える(yield())だけの処理が、条件変数版では論理的に意味のあるイベントが起きるまで、つまり明示的に条件変数への通知が行われるまで自スレッドを休止状態とし、CPUリソースを他スレッドへ明け渡す処理となります。*5

Step2: 実行時オーバーヘッドの削減

Step1では待機処理に条件変数を利用する事で、CPUリソースの浪費を抑えることができました。Step2では、より効率的な条件変数の利用について検討しましょう。ここでは下記4つを順番に適用していきます。

  1. イベント種別に応じた条件変数の分離
  2. 冗長な条件変数通知の削減
  3. 条件変数通知先スレッドの限定
  4. 条件変数待機を述語(Predicate)版に書き換え

Step2-1: 条件変数の分離

Step1では条件変数オブジェクトcv_を、「キュー内の要素数に何らかの変化があった」イベントに対応付けていました。この設計では、あらゆるキュー操作によって条件変数への通知が発生するため、必要のない冗長な通知処理が行われています。push操作は「キューが満杯でない」状態を／pop操作は「キューが空でない」状態を待機すれば良いので、両イベントに直接対応する条件変数に分離しましょう。新しい設計では1つのミューテックスmtx_に対して、2つの条件変数オブジェクトcv_nofull_, cv_noempty_を紐付けます。

// Step1(mt_queue1.cpp)
std::mutex mtx_;
std::condition_variable cv_;

// Step2-1
std::mutex mtx_;
std::condition_variable cv_nofull_;   // 満杯でなくなった
std::condition_variable cv_noempty_;  // 空キューでなくなった

条件変数の設計では、待機側でどんなデータ状態を満たすべきかに基づいて抽出することをお勧めします。

Step2-2: 冗長な条件変数通知の削減

push()実装の通知処理に着目すると、Step1では条件変数への通知を無条件に行っていました。本質的には、push操作では「キューが空でなくなった＝少なくとも1個要素が存在する」イベントのみをpop操作へ通知すれば十分なため、通知の発火条件を限定することで無駄な処理を減らし、より効率的な実装とできます。同様にpop操作では「キューが満杯でなくなった＝少なくとも1要素を追加できる」イベントのみを通知すれば十分です。

// Step1: push()メンバ関数
q_.push(data);
cv_.notify_all();  // 要素数変更を通知

// Step2-2: push()メンバ関数
bool do_signal = q_.empty();  // 操作前が空キューのときのみ
q_.push(data);
if (do_signal)
  cv_noempty_.notify_all();   // 「空キューでなくなった」通知

条件変数への通知処理は、待機側の条件式を満足するよう変更を行ったタイミングを抽出すると、実行時オーバーヘッドを最小化することができます。

Step2-3: 通知先スレッドの限定

Step1では条件変数への通知処理にnotify_all()(broadcast)を用いていました。空キューへの1回のpush操作によって、pop操作を待機中の全スレッドが起こされますが、実際に要素の取り出しに成功するのは1スレッドだけで、それ以外のpop操作要求スレッドは全て待機処理に再突入します。つまり、push操作が通知すべきpop操作待機スレッドは1つで十分であり、それ以上のスレッドへ通知が行われても冗長ということです。このようなケースではnotify_one()(signal)を利用することで、通知先スレッドを限定して実行効率の改善をはかることができます。

// Step1: push()メンバ関数
cv_.notify_all();  // 待機中の全スレッドへ通知

// Step2-3: push()メンバ関数
cv_noempty_.notify_one();  // pop()待機中の任意の1スレッドへ通知

このようなnotify_all()からnotify_one()への変更は、i)通知先が最大で1スレッド かつ ii)通知を受信するスレッドの待機条件を常に満たす場合 にのみ安全に行えます。本記事で設計したFIFOキューの場合、push操作からの通知を受信した任意のpop操作スレッドは、必ず待機ループを抜けてpop操作を完了すると保証できるため、notify_one()へと安全に変更できます。特に条件ii)を正しく考慮していないと、デッドロックといった並行性バグの原因となるため十分注意してください。*6

追記：notify_one()により生じるデッドロックについては、おまけ記事「条件変数とデッドロック・パズル（出題編）（解答編）」も参考にしてください。

Step2-4: 条件変数待機の書き換え

最後に、条件変数の待機処理wait()を述語(Predicate)をとる2引数オーバーロードに書き換えておきます。この変更は効率化とは無関係ですが、条件変数オブジェクトの名前(cv_nofull_, cv_noempty_)と、待機条件式(q_.size() < capacity, !q_.empty())の意味を一致させることができます。また後述Step3でFIFOキュー機能拡張を行うときに、待機条件の論理式を拡張しやすいというメリットもあります。

// Step1: push()メンバ関数
while (q_.size() == capacity) {
  cv_.wait(lk);
}
// Step1: pop()メンバ関数
while (q_.empty()) {
  cv_.wait(lk);
}

// Step2-4: push()メンバ関数
cv_nofull_.wait(lk, [&]{
  return (q_.size() < capacity);
});
// Step2-4: pop()メンバ関数
cv_noempty_.wait(lk, [&]{
  return !q_.empty();
});

Step2のまとめ

Step2での最終的なコードは次の通りです。［mt_queue2.cpp］

// mt_queue2.cpp抜粋
class mt_queue {
  //...
  std::mutex mtx_;
  std::condition_variable cv_nofull_;   // 満杯でなくなった条件
  std::condition_variable cv_noempty_;  // 空キューでなくなった条件
public:
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{     // 「満杯でない」ことを待機
      return (q_.size() < capacity);
    });
    bool do_signal = q_.empty();
    q_.push(data);
    if (do_signal)
      cv_noempty_.notify_one();  // 「空キューでなくなった」通知
  }
  int pop() {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_noempty_.wait(lk, [&]{   // 「空キューではない」ことを待機
      return !q_.empty();
    });
    bool do_signal = (q_.size() == capacity);
    int data = q_.front();
    q_.pop();
    if (do_signal)
      cv_nofull_.notify_one();  // 「満杯でなくなった」通知
    return data;
  }
};

さらなる改善策として、通知処理をミューテックスのロック解放後まで遅延させるという手法もあります。ただし、この変更によりコードが壊れるコーナーケースが存在すること、また処理系の実装品質が十分ならばあまり効果を期待できないため、本記事では適用しないこととします。詳細はこちらの記事を参考にしてください。

Step3: 提供機能の再考

Step2までで、性能面について十分考慮されたスレッドセーフ・FIFOキューを実装できました。Step3では機能面について改めて考えてみましょう。ここでは下記2点を検討します。

  1. データ列の終端処理
  2. 強制的な処理中断

Step3-1: データ列の終端処理

最初に設定したFIFOキュー仕様では、pushデータ列の終端処理について特別の考慮をしませんでした。いくぶん不恰好ですが、例えば-1を特殊な“データ終端マーカ”値とみなすことも出来るでしょう。

// mt_queueクラス利用コード
void producer_thread(mt_queue& mq) {
  for (int i = 1; i <= N; ++i)
    mq.push(i);
  mq.push(-1);  // データ終端を通知
}
void consumer_thread(mt_queue& mq) {
  int v;
  while ((v = mq.pop()) > 0)
    process_data(v);
}

生産者スレッド(producer_thread)と消費者スレッド(consumer_thread)が1つづつのSingle-Producer/Single-Consumerモデルならこの設計でも十分ですが、Multi-Producer/Multi-Consumerモデルでは面倒な問題が浮上します。例えば2生産者スレッド＋3消費者スレッドで動作させた場合、FIFOキューには終端マーカが2個しかpushされないため、3番目の消費者スレッドはデータ終端到達を知ることが出来ません。生産者／消費者スレッド数が動的に変化する場合はもはやお手上げです。
結局、“終端マーカ”方式のようなクラス利用側コード設計に頼るのではなく、FIFOキュー自体に終端到達通知close()メンバ関数を追加するのが良いでしょう。これに伴って、push()は終端到達検知時に例外closed_queueを送出し、またpop()は終端到達状態を返すよう関数シグニチャを変更します。

class mt_queue {
  //...
  bool closed_ = false;  // 終端到達通知を保持
public:
  void close() {  // ★終端到達通知
    std::lock_guard<std::mutex> lk(mtx_);
    closed_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{
      return (q_.size() < capacity) || closed_;  // 条件追加
    });
    if (closed_)
      throw closed_queue();  // 例外送出
    //...
  }
  bool pop(int& data) {      // 関数シグニチャ変更
    std::unique_lock<std::mutex> lk(mtx_);
    cv_noempty_.wait(lk, [&]{
      return !q_.empty() || (q_.empty() && closed_);  // 条件追加
    });
    if (q_.empty() && closed_)
      return false;          // 終端到達を返す
    data = q_.front();
    //...
    return true;             // 終端ではない
  }
};

pop()実装の待機条件では... || (q_.empty() && closed_)、つまり“キューが空でかつ終端通知がされているとき”に始めてデータ終端と判定すべきです。またclose()実装では、全ての条件変数に対してnotify_all()通知が必要になります。

Step3-2: 強制的な処理中断

終端到達通知close()によって通常のデータ終端処理を表現できるようになりましたが、ブロッキング中のpush/pop操作に対する処理中断要求abort()があるとより実用的になります。push()/pop()では中断要求検知時に例外abort_exceptionを送出するよう拡張します。なおclose()はブロッキング操作ではないため、中断すべき処理をもちません。*7

class mt_queue {
  //...
  bool aborted_ = false;  // 処理中断要求を保持
public:
  void abort() {  // ★処理中断要求
    std::lock_guard<std::mutex> lk(mtx_);
    aborted_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{
      return (q_.size() < capacity) || closed_ || aborted_;  // 条件追加
    });
    if (closed_)
      throw closed_queue();
    if (aborted_)
      throw abort_exception();  // 例外送出
    q_.push(data);
    //...
  }
  //...
};

push()実装の待機条件式(q_.size() < capacity) || closed_ || aborted_と、後続の条件分岐式とを比べてみてください。下記の対応関係を読み取れたでしょうか？1つの条件変数オブジェクトに複合的な条件を設定する場合、この構造が基本形となるはずです。

条件変数.wait(lk, [&]{
  return 条件A || 条件B || 条件C;
}):
if (条件A) { 処理A; }
if (条件B) { 処理B; }
if (条件C) { 処理C; }

ゴール！

本記事で実装したスレッドセーフ・FIFOキューの最終コードは次の通りです。［mt_queue3.cpp］

// mt_queue3抜粋
struct closed_queue : std::exception {};
struct abort_exception : std::exception {};

class mt_queue {
  static const int capacity = 10;
  std::queue<int> q_;
  std::mutex mtx_;
  std::condition_variable cv_nofull_;
  std::condition_variable cv_noempty_;
  bool closed_ = false;
  bool aborted_ = false;
public:
  void push(int data)
  {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{
      return (q_.size() < capacity) || closed_ || aborted_;
    });
    if (closed_)
      throw closed_queue();
    if (aborted_)
      throw abort_exception();
    bool do_signal = q_.empty();
    q_.push(data);
    if (do_signal)
      cv_noempty_.notify_one();
  }
  bool pop(int& data)
  {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_noempty_.wait(lk, [&]{
      return !q_.empty() || (q_.empty() && closed_) || aborted_;
    });
    if (q_.empty() && closed_)
      return false;
    if (aborted_)
      throw abort_exception();
    bool do_signal = (q_.size() == capacity);
    data = q_.front();
    q_.pop();
    if (do_signal)
      cv_nofull_.notify_one();
    return true;
  }
  void close()
  {
    std::lock_guard<std::mutex> lk(mtx_);
    closed_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
  void abort()
  {
    std::lock_guard<std::mutex> lk(mtx_);
    aborted_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
};

これでもう条件変数は怖くありません…よね？

*1:スレッド間での通知／待機を行う同期プリミティブとしては、A)「セマフォ(semaphore)」に代表されるイベント変数方式、B)ミューテックス＋条件変数ペアによる方式があり、これらを提供する／しないはライブラリ設計ポリシーに依存します。ただし、比較的新しいライブラリ仕様では方式B)条件変数のみを提供する事が多いようです。例えばBoost.Threadライブラリではその設計論拠に基づき、セマフォ同期プリミティブを提供しません。Boost.Threadをベースに標準化されたC++11標準ライブラリも、同様に条件変数のみを提供します。なお、セマフォを用いて条件変数を実装する／条件変数を用いてセマフォを実装することが可能なため、両同期プリミティブは本質的には互換性があるといえます。

*2:スレッド間の排他制御は2値セマフォ(binary semapohore)を用いても実現可能ですが、一般的にミューテックスではスレッド間“排他”処理という目的に合わせて、スレッドによる“ロックの所有”という概念が導入されます。このため、あるスレッドがミューテックスのロック処理（所有権を獲得）を行った場合、必ず同じスレッドでアンロック処理（ロック所有を解放）を行う必要があります。一方でセマフォには所有権という概念は無く、制約のあるミューテックスよりも便利に思えるかもしれません。しかし、特にマルチスレッド処理プログラミングにおいては、バグ検知可能性や実行時効率などの観点から、セマフォのように自由度の高い原始的な機構よりも、ミューテックスのように目的に特化した専用機構を用いるべきです。

*3:ミューテックスの不適切な利用の一例として、“ロック獲得のFIFO動作を期待したスレッド・スケジューリング”が挙げられます。これは、複数スレッドから同時にロック獲得要求を行い、ロック獲得成功順序がFIFO動作であると仮定し、各スレッドが順次実行されることを期待した処理を指します。通常、ミューテックスのロック獲得はFIFO順を保証しないため(unfair)、このような利用は適切ではありません。

*4:オブジェクト破棄処理をスレッドセーフとするには大きな制限事項を伴うため、通常、スレッドセーフの議論からはクラスのデストラクタを除外します。つまりオブジェクト破棄時には、他のあらゆるメンバ関数と同時に呼び出さないことを、クラス利用側が保証すべきです。

*5:条件変数の動作仕様では“Spurious Wakeup”が起こりうると明記されており、誰も通知を行っていないのに待機が解除されることがあります。本記事のようにビジーループを起点に考えた場合は、既にループ構造＋条件変数の待機処理となっており、Spurious Wakeupも考慮済みとなるため、本文中では特に言及しません。詳細は条件変数とspurious wakeupを参照ください。

*6:具体例：片方は奇数のみを／もう一方は偶数のみを取り出す選択的pop操作に対して、1)pop要求で2スレッドとも待機→2)偶数値をpushし任意1スレッドへ通知→3)奇数待機スレッドが通知受信して再待機→4)偶数待機スレッドは休眠状態のまま。

*7:close処理の内部実装では、ロック獲得のために呼び出しスレッドがブロッキングされる場合があります。この排他制御はFIFOキューのデータ一貫性を維持するため機構であり、いずれのスレッドも有限ステップ内にロック獲得することが保証できます。このため、クラス利用者視点ではcloseメンバ関数はノンブロッキング操作とみなせます。