yohhoyの日記（別館）

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

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