yohhoyの日記

2012-03-31

Windows XP向けの条件変数の実装方法と実例

Windows XP以前のWindows APIでは同期プリミティブとしての条件変数(condition variable)が提供されない。セマフォ(semaphore)やミューテックス(mutex)/クリティカルセクション*1を組み合わせて、条件変数プリミティブを実装するアルゴリズムおよびコード実例のメモ。

実装方法

条件変数プリミティブのメジャーな実装アルゴリズムとして Alexander Terekhov's "Algorithm 8a" がある。2008年頃のcomp.programming.threads上での議論がベースとなっている。

このアルゴリズムでは、条件変数プリミティブの内部実装に“2つのセマフォ、2つのミューテックス、3つの整数型変数”を利用する。Windows APIにはタイムアウト付きセマフォ待機関数(WaitForSingleObject)が存在するため、タイムアウト付き条件変数待機も含めてPOSIX相当の機能を実装可能。

  • wait / timedwait
  • signal / broadcast


実例いろいろ

様々なオープンソースプロジェクト内におけるWindows APIによる条件変数プリミティブ実装コードをいくつか列挙する。★マークは前述"Algorithm 8a"を直接実装しているプロジェクト(自分調べ)。

おまけ

"Algorithm 8a"を用いたC11標準スレッドのエミュレーションライブラリ。(Boost Software License 1.0)

*1:ここではWindows API用語としてのCRITICAL_SECTIONを指す。同一プロセス限定のスレッド間同期用ミューテックスオブジェクト。