2025-11-20

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

C++

2025/10/17に開催されたイベント C++ MIX #16にて、“C++26 std::execution” というタイトルで30分ほど話す機会をいただきました*1。（8ヶ月ぶり5回目）

スライド資料

感想とか

次期C++26標準ライブラリへ追加予定とされる、実行制御ライブラリ(execution control library)の概要を紹介しました。汎用的な非同期処理フレームワークの導入を試みる大規模アップデートとなっており、新しい基本概念や基本操作を実現する機能群が数多く追加されます。同フレームワークに則った機能追加カスタマイズを可能とする仕組みも備えますが、あまりに複雑な機構のため今回スライドではバッサリと省略しています。

今回はC++MIX都合あわんかったけど次回以降になんか考えるか executionだと時間無制限になりそ（ムリ
— yoh (@yohhoy) 2025年7月14日

実行制御ライブラリの機能詳細に興味がある方は、下記の記事群もあわせて参照ください。

*1:実際のプレゼンテーションは5分以上超過していたと思います。m(__)m

2025-02-24

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

C++

2025/2/21に開催されたイベント C++ MIX #13にて、“サンプルコードによるC++23ジェネレータの紹介” というタイトルで20分ほど話す機会をいただきました。（5年5ヶ月ぶり4回目）

スライド資料

サンプルコードによるC++23ジェネレータの紹介 by @yohhoy

感想とか

C++23標準ライブラリに追加されたstd::generatorおよび関連機能を紹介しました。コルーチン機能は標準ライブラリ仕様記述から読み取れる情報だけでは不十分なことが多く、コードスニペットを用いた機能概要の解説を試みています。

std::generatorのボトムアップ的説明：まずはC++20 Coroutinesを(ほぼ)全部理解しましょう
同トップダウン的説明：co_yield書いてみましょうからのテンプレートパラメータの選び方についてアレコレ https://t.co/MwE96jVCrY
— yoh (@yohhoy) 2022年12月30日

C++23 std::generator標準入りでようやく普通のC++プログラマ向けのコルーチンが登場したのでZennあたりに紹介記事でも書いてみるかとも思ったけど blogとcpprefjpに既に書き下した内容とそう変わらない気もしてきてモチベーションが微妙
— yoh (@yohhoy) 2024年2月23日

C++コルーチン動作の落とし穴として紹介した “キャプチャ付きジェネレータコルーチン・ラムダ式” は、事前想定どおり最も理解されづらかったようです。スライドではC++ Core Guidelines紹介にとどめて簡易説明で済ませましたが、技術詳細は記事「コルーチン×ラムダ式キャプチャ＝鼻から悪魔」を参照ください。

2019-09-06

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

C++

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

スライド資料

20分くらいでわかった気分になれるC++20コルーチン from yohhoy

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年

*N3328 Resumable Functions

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++標準へのスタックフルコルーチン提案を行っています。

2018-03-08

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

C++

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

github.com

ライブラリ概要は “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順でロック獲得すること”を検証します。公平性テストとしては最もシンプルなテストケースです。ね、簡単でしょう？

デバッグ苦労話

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

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

assert文（アサーション記述）
gdb/lldb/windbg（デバッガ）
ログ出力（printfデバッグ）
紙とペン（机上デバッグ）

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

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

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

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

CI環境だと確率的にdeadlockするバグが残ってるぽいけどめんどくせえ...
— yoh (@yohhoy) 2018年2月18日

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

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

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

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

https://t.co/UuFeSBCJk5 きわどいrace condtionバグを直したらもっと根本的な設計問題が浮上してきた...ヽ(ﾟ∀｡)ﾉ
— yoh (@yohhoy) 2018年2月20日

つぶやき

マルチスレッド処理の問題は設計原則を理解してないコード変更が一カ所でもあるとソフトウェア全体の信頼性に壊滅的ダメージを与えることかしら誤りを機械的／人的に検知するのが困難なのに一見すると無害に思える些細な変更のインパクトが大きいこともあったりと厳しい
— yoh (@yohhoy) 2018年1月30日

マルチスレッド(というか共有メモリ型・並列処理)は人類にはきつい論
— yoh (@yohhoy) 2017年8月24日

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

2018-03-04

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

C++

YAMC

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

github.com

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

mutex：基本のミューテックス
timed_mutex：タイムアウト対応
recursive_mutex：再帰ロック対応
recursive_timed_mutex：再帰ロック、タイムアウト対応
shared_mutex：共有ロック対応（C++17で追加）
shared_timed_mutex：共有ロック、タイムアウト対応（C++14で追加）

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スピンロックを推奨します。

spin::basic_mutex：単純なTAS(Test-And-Set)スピンロック。内部実装atomicアクセスは逐次一貫性(seq_cst)を指定。
spin_weak::basic_mutex：単純なTAS(Test-And-Set)スピンロック。内部実装atomicアクセスはリリース一貫性(acquire/release)を指定。
spin_ttas::basic_mutex：CPUキャッシュ同期プロトコルを考慮したTTAS(Test and Test-And-Set)スピンロック。

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

backoff::exponential<N>：ビジーループ待機とスレッド休止(yield)の間隔を、Exponential-backoffアルゴリズムにて自動調整。Nはビジーループ回数の初期値。
backoff::yield：std::this_thread::yieldによるスレッド休止。
backoff::busy：完全なビジーループ待機。ご利用は自己責任で。

公平スケジューリング

一般的に、ミューテックスの内部実装では不公平(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環境構築にもチャレンジしています。

こいつ(自分) いつもMutex作ってんなという気分になってきたので一つのレポジトリにまとめるかな...
— yoh (@yohhoy) 2017年1月16日

諫言と免責事項

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

https://t.co/lSe8T2JHGh 「12.4.8. 自分でmutexを作ると非効率」ぉぅ(I agree) 最近20種類くらい作ったけどそれはそれ
— yoh (@yohhoy) 2017年2月22日

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

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

久しぶりに最下層部品のマルチスレッド処理関連デバッグしたは… mutex排他が機能してないんじゃね的挙動をしててさんざん悩んでたけど壊れてるのは設計の方でしたという妥当なオチやっぱりマルチスレッド処理とか人類には早すぎたんや
— yoh (@yohhoy) 2015年8月18日

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

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

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

yohhoyの日記（別館）

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

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

スライド資料

感想とか

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

スライド資料

感想とか

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

スライド資料

感想とか

提案文書

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

実装デザイン

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

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

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

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

ユニットテスト手法

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

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

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

デバッグ苦労話

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

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

つぶやき

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

YAMC

提供機能の一覧

機能の詳細説明

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

公平スケジューリング

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

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

雑談

モチベーション

諫言と免責事項