yohhoyの日記(別館)

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

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

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

YAMC

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

github.com

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アルゴリズムを推奨します。

  • backoff::exponential<N>:ビジーループ待機とスレッド休止(yield)の間隔を、Exponential-backoffアルゴリズムにて自動調整。Nはビジーループ回数の初期値。
  • backoff::yieldstd::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呼び出し
  • 再帰ロック非対応ミューテックスに対するロック所有スレッドからのlocktry_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ミューテックス間のみが対象となります。