相互排他

2026年10月11日 #MutualExclusion #Mutex #Semaphore

1. 概要

相互排他 (mutual exclusion) またはミューテックス (mutex) は、一貫性のために同時に実行されてはならないコード領域を一度にたかだか 1 つのプロセスしか実行しないように制御する同期である。並行プログラミングにおいて最初に定式化された同期問題であり [5]、一般にロック (lock) と呼ばれる広く認知されている同期機構である。

相互排他の仕様は 60 年前から変わっていないが、その実装は時代によって大きく変わっている。現代のプロセッサは CAS (compare and swap) などのアトミックな read-modify-write (RMW) 命令を備えており、相互排他を read/write のみで組む必要はない。一方で、性能は命令数ではなくキャッシュコヒーレンスのトラフィックによって律速され、正しさを決めるのは命令の並びではなくメモリモデルである。このページでは相互排他問題の定義から開始し、現代の環境で実際に使われるロックの構造 (TTAS, ticket, MCS/CLH, futex による spin-then-park) を扱う。古典的な read/write レジスタによるアルゴリズムは歴史的背景に記述する。

1. 概要
2. 相互排他問題
3. 現代的なハードウェア機構
4. スピンロック
5. ブロッキングロック
6. 実務での設計と使用
7. read/write レジスタのみによる解法 (歴史的背景)
8. 相互排他の限界
9. まとめ
10. 参考文献

2. 相互排他問題

2.1. クリティカルセクション

一貫性を保証するために、一度に 1 つのプロセスしか実行してはならないコード片 $A$ 、あるいは複数のコード片 $A, B, C, \ldots$ をクリティカルセクション (critical section) と呼ぶ。これは、あるプロセスが $B$ を実行している間、他のプロセスが $A,B,C$ のいずれも実行できない制約を持つことを意味する。あるデータを操作する複数のコード片が互いに排他されなければならない範囲である。

相互排他は、クリティカルセクションを囲む範囲の入口プロトコル (entry protocol) ${\rm acquire}()$ と出口プロトコル (exit protocol) ${\rm release}()$ を実装する問題である。クリティカルセクションを実行したいプロセスは必ず ${\rm acquire}()$ 、クリティカルセクション、 ${\rm release}()$ の順に実行すること (well-formed であること) を仮定する。Java の synchronized ブロックや Rust の MutexGuard、C++ の std::lock_guard は、この仮定を言語機構で強制する。

プロセスは非同期 (asynchronous) であり、ある状態遷移から次の状態遷移までの時間に上限を設けないと仮定する。プロセス数よりプロセッサ数が少ない場合はスケジューラが介在して実行順を決定する。公平なスケジューリングの仮定下では、すべてのプロセスがいつかは実行機会を得る。ただし、公平なスケジューリングの下であっても、OS がプロセスを一時停止したり、仮想化環境で vCPU の実行を止めたりすることがあり、ロック保持者が停止すると待機中のプロセスはロックが解放されるまでスピンし続けるため、後述のようにスピンロックの性能に影響する。

2.2. 安全性と活性

非同期環境下での問題は安全性 (safety) と活性 (liveness; または生存性) によって定義される。安全性とは「悪いことが起こらない」ことで、通常は不変条件 (invariant) として表現できる。相互排他における安全性の不変条件は「一度にたかだか 1 つのプロセスしかクリティカルセクションのコードを実行しない」ことのみである。

ただし、どのプロセスにもクリティカルセクションを許可しないアルゴリズムが相互排他を満たすことから、安全性の不変条件だけでは相互排他の機構としては不十分である。相互排他の活性のためには以下の不変条件が必要である。

デッドロックフリー (deadlock-freedom): 1 つ以上のプロセスが ${\rm acquire}()$ を呼び出し、そのいずれも呼び出しを終了していない (ロックの獲得に成功していない) ならば、有限時間内に待機中のいずれかのプロセスが呼び出しを終了する。ただし、どのプロセスが呼び出しを終了するかは保証されず、特定のプロセスが待ち続ける可能性はある。
飢餓フリー (starvation-freedom): ${\rm acquire}()$ を呼び出したどのプロセスも、最終的に呼び出しが終了する (ロックを獲得する)。これはあるプロセスが他のプロセスに追い越される回数が有限であること (finite bypass) と同じ意味である。この条件は待機中のどのプロセスも実行機会が与えられていることを保証するが、即時実行や待ち時間に上限があることは保証していない。
有界バイパス (bounded bypass): あるプロセスの ${\rm acquire}()$ 呼び出しが終了するまでに (ロックを獲得するまでに)、他のプロセスが先にロックを獲得できる回数の上限が $f(n)$ である。ここで $f(n)$ はプロセス数 $n$ に対する関数である。

FIFO は先に ${\rm acquire}()$ を要求したプロセスから順に呼び出しを終了させる性質である。有界バイパスは「要求順に獲得する」という保証ではない点で FIFO とは異なる。

これらの間には:

有界バイパス

\Rightarrow

飢餓フリー

\Rightarrow

デッドロックフリー

という包含関係が成り立つ [1, 4]。例えば 3 つのプロセス $p_1, p_2, p_3$ が競合しており、 $p_1$ と $p_2$ が交互にロックを獲得する状況では $p_3$ が永遠に待たされる。この実行はデッドロックフリーだが飢餓フリーではない。

デッドロックフリーは、ロックを待つプロセスのいずれかがいつかはクリティカルセクションに入ることを保証する。つまり、誰かが進行できるというシステム全体の性質である。一方、飢餓フリーはロックを要求した各プロセスがそれぞれいつかはクリティカルセクションに入ることを保証する。これは自分が進行できるという個々のプロセスの性質である。

Test and Set や Compare and Swap を繰り返してロックを獲得する方式では、特定のプロセスが何度も競争に負けてロックを獲得できない飢餓状態になる実行がありうる。待ち続けるプロセスがないことを保証したい場合、ticket ロックやキューロックのように明示的に獲得する構造が必要になる。どの程度の公平性が得られるかは、ロックの方式や実装によって異なる。

2.3. ロックオブジェクト

ロックオブジェクト (lock object) は解放 (free) とロック (locked) の 2 つの状態を持ち、 ${\rm acquire\_lock}()$ と ${\rm release\_lock}()$ の 2 つの操作を提供するオブジェクトである。 ${\rm acquire\_lock}()$ はロックが開いていれば獲得し、使用中であれば空くまで待つ。ロックの獲得に成功した場合、呼び出し側は ${\rm release\_lock}()$ でロックを解放する。

相互排他の仕様では、この振る舞いは逐次処理として定義される。すなわち、外部の観測者からは成功したすべての操作が次の順序で実行されたように見えることを要求する: ${\rm acquire\_lock}() \to {\rm release\_lock}() \to {\rm acquire\_lock}() \to {\rm release\_lock}() \to \ldots$ 実際には複数のプロセスの呼び出しが同時に進行することがあるが、それでもあるプロセスがロックを獲得してから解放するまで他のプロセスはロックを獲得できないと説明できれば相互排他の仕様を満たしている。したがって、相互排他アルゴリズムを作ることはロックオブジェクトを実装することと同じである。

3. 現代的なハードウェア機構

現代の共有メモリ環境では、相互排他はソフトウェアだけで実現するのではなく、プロセッサが提供するアトミック操作とメモリ順序の保証を組み合わせて実装する。こうした命令はロック獲得を正しく行う土台になるが、競合時の性能はキャッシュ間の通信や待機方法の影響も受ける。このセクションでは、相互排他に関する代表的なハードウェア機構について説明する。

3.1. アトミック read-modify-write プリミティブ

ほぼすべての共有メモリマルチプロセッサは、ハードウェアで実装された同期のためのアトミック操作を提供している。いずれも読み出しと書き込みをアトミック (分割不能) な 1 ステップで行う点で古典的な read/write レジスタと異なる。

${\rm test\_and\_set}(X)$ : $X$ に 1 を設定し、以前の値を返す。 ${\rm reset}(X)$ は $X$ を 0 に戻す。2 値に特化した最も単純なプリミティブ。
${\rm swap}(X, v)$ : $X$ に $v$ を代入し、以前の値を返す。 ${\rm fetch\_and\_store}$ とも呼ばれる。キューロックの基礎になる。
${\rm fetch\_and\_add}(X,v)$ : $X$ に $v$ を加算し、以前の値を返す。ticket ロックやアトミックカウンターの基礎になる。
${\rm compare\_and\_swap}(X,{\it old}, {\it new})$ : $X = {\it old}$ であれば $X$ に ${\it new}$ を書き込んで真を返し、そうでなければ何もせず偽を返す。これは条件付き書き込みであり、書き込みが成功したかを呼び出し元に返す。これは x86 の CMPXCHG 命令にあたる。
${\rm LL}$ / ${\rm SC}$ (load-linked / store-conditional): 読み出しと条件付き書き込みを組み合わせる操作である。 ${\rm LL}(X)$ は $X$ の値を読み出すと同時に、そのアドレスを監視対象として記録する。続く ${\rm SC}(X,v)$ は、監視が有効なままであれば $X$ に $v$ を書き込んで成功を返す。 ${\rm LL}$ と ${\rm SC}$ の間に別の書き込みがあると監視が無効になり、 ${\rm SC}$ は書き込みを行わず失敗を返す。ただし、競合の有無にかかわらず実装上の理由で ${\rm SC}$ が失敗することがあるため、通常は失敗時に ${\rm LL}$ からやり直す。ARM の LDXR/STXR と RISC-V の LR/SC が代表例である。細かな失敗条件は命令セットによって異なる。

これらの計算可能性としての強さは等価ではない。 ${\rm test\_and\_set}$ や ${\rm swap}$ は 2 プロセスまでの合意しか解けないが、 ${\rm compare\_and\_swap}$ と ${\rm LL}$ / ${\rm SC}$ は任意個のプロセスの合意を解くことができる。この差はコンセンサス数 (consensus number) として定式化されており、どのプリミティブがあれば任意の並行オブジェクトをノンブロッキングに実装できるかを決定する。相互排他を解くだけならどれでも十分だが、ロックを使わない実装を目指すときにはこの差が決定的になる [2]。

${\rm compare\_and\_swap}$ の ABA 問題とは、値が $A \to B \to A$ と変化したときに ${\it old} = A$ の比較が成功してしまい、間に変更があった事実を検出できないというものである。ロックの実装では状態が 2 値 (解放/ロック) であるため問題になりにくいが、ポインタを扱うノンブロッキングデータ構造では致命的になる。 ${\rm LL}$ / ${\rm SC}$ はアドレスの監視によってこれを原理的に回避する (ただし実際のプロセッサでは無関係な書き込みやコンテキストスイッチなどによって ${\rm SC}$ が失敗することがある)。

3.2. キャッシュコヒーレンスと RMR 計算量

現代のマルチコアプロセッサにおいてロックの性能を決めるのは、実行した命令の数ではなく、キャッシュコヒーレンスプロトコルが発動した回数である。キャッシュコヒーレンス (cache coherence; キャッシュ一貫性) とは、複数のプロセッサコアが同じメモリアドレスをそれぞれキャッシュしているとき、書き込みの順序や読み出し結果に矛盾が生じないようにする性質である。具体的には、あるコアが共有メモリの変数を書き換えた後、別のコアがその変数を使うときに書き換え前の古い値を使い続けないようにする。

キャッシュコヒーレンスプロトコル (cache coherence protocol) は、この性質を維持するためにキャッシュ間でどのような通知や状態変更を行うかを定めた規則である。例えば、あるコアが書き込むときに他のコアの該当キャッシュラインを無効化する方式がある。共有メモリへの書き込みが多いと、こうした通知や無効化の通信が増えて性能に影響する。ロックを待つプロセスがすべて同じ変数を読んでいると、ロックが解放されるたびにすべてのプロセスのキャッシュが無効化され、全員が同時にメモリアクセスを発生させる。この現象をサンダリングハード (thundering herd) と呼ぶ。

RMR 計算量 (remote memory reference complexity) はこうした通信コストを「リモートメモリ参照の回数」で定式化した指標である。例えばキャッシュコヒーレント (CC) モデルでは、必要なデータがローカルキャッシュになく、取得のためにメモリや他コアとの通信が必要になる参照を数える。分散共有メモリ (DSM) モデルでは、別ノードにあるメモリへのアクセスを数える。ローカルで完結する参照は数えない。つまり RMR は実行時間そのものではなく、共有メモリシステムで通信がどれほど発生するかを見るための理論上の尺度である [3]。

この尺度の下では、待機方法の違いがそのままコストの違いになる。待機プロセスのすべてが同じ変数上でスピンするロックは、解放のたびに全員のキャッシュラインが無効化されるため、1 回のクリティカルセクション通過あたり $O(n)$ の RMR を要する。一方、各プロセスが自分専用の変数上でスピンし、解放側がそのうち 1 つだけを書き換えるロックは $O(1)$ で済む。キューロックは後者を実現する。

決定論的な相互排他アルゴリズムが CC または DSM モデル上で、read/write 操作、compare and swap のような比較に基づく操作、あるいは ${\rm LL}$ / ${\rm SC}$ 操作を使う場合、少なくともひとつの実行では $n$ 個のプロセスが一度ずつクリティカルセクションに入るまでに合計で $\Omega(n \log n)$ の RMR が必要になる。これは RMR の理論上の下限として知られている [19] (ただし、それ以外のケース、例えば swap 操作を使う MCS ロックのようなケースにはそのまま当てはまらない)。

RMR とは別に、偽共有 (false sharing) によって性能が低下することもある。偽共有は、別々のプロセスが別々の変数を使っていたとしても、それらが同じキャッシュライン上に置かれているためにキャッシュ間の不要な通信が起きる現象である。たとえば、プロセス $A$ が変数 countA を、プロセス $B$ が変数 countB をそれぞれ別々に更新したとき、両方が同じキャッシュライン上に配置されていると、一方の書き込みで他方のコアにあるラインのコピーが無効化されることがある。その結果、変数同士は独立しているにもかかわらず、更新のたびにラインの受け渡しが発生して性能が落ちる可能性がある。

頻繁に更新する変数を別々のキャッシュラインに配置する対策として、間に余白を設ける「パディング」が使われる。ただし、パディングはメモリ使用量を増やすため、性能上の問題を計測してから適用すべきである。

3.3. メモリモデルとバリア

古典的な相互排他アルゴリズムを正しく動かすには、共有メモリの read/write がアトミックであるだけでなく、複数の領域へのアクセス全体が単一の順序で起きたように観測される必要がある場合がある。この性質を逐次一貫性 (sequential consistency) と呼ぶ [20, 21]。これは、各プロセス内の操作の順序を維持したまま、全プロセスの操作を一つの順序に並べられ、読み出しはその順番の直前に行われた書き込みの内容を返すように振る舞う。

しかし、通常のメモリアクセスだけでは、コンパイラやプロセッサが操作の順序を変えたり、書き込みが他のコアから見えるまで時間がかかることがある。例えば Peterson のアルゴリズムでは各プロセスが自分のフラグを上げてから相手のフラグを確認する。両方の書き込みがまだ相手に見えない間に読み出しが行われると、双方が「相手は参加していない」と判断して同時にクリティカルセクションへ入る可能性がある。したがって、アルゴリズムの証明で仮定した順序を実装でも保証しなければならない。

メモリバリア (memory barrier) あるいはフェンス (fence) は、メモリアクセスの順序を制御し、コンパイラやプロセッサによる並べ替えを制限する仕組みである。ロック獲得には獲得セマンティクス (acquire) を使って獲得後のデータアクセスがロック獲得より前に移動しないようにする。同様に、ロック解放には解放セマンティクス (release) を使って解放前のデータアクセスがロック解放より後に移動しないようにする。

ロックを解放する前に行った共有メモリ上の更新は、解放後に同じロックを獲得したプロセスから観測できる必要がある。これを保証するため、C++ や Rust ではアトミック操作に acquire/release の順序を指定できる。Java では synchronized や volatile を使ってメモリの可視性とアクセス順序を定める (ただし volatile はロックのように複数の操作を排他制御するものではない)。プログラミング上は言語の規則に従って必要なアクセス順序を指定する。コンパイラはその指定を、対象とするプロセッサに適した命令に変換する。順序の保証はアトミック命令やロック命令自体で得られる場合もあれば、別のメモリバリア命令で得られる場合もある。

Peterson のアルゴリズムは、共有メモリの読み書きが一定の順序で観測できることを前提としている。しかし、現代のプログラミングでは通常の変数を使って書くだけでは同じ順序が保証されるとは限らず、コンパイラやプロセッサの動作によって複数のプロセスが同時にクリティカルセクションへ入る可能性がある。現実的な実装では、まず言語が提供する Mutex を使用する。アトミック操作を使って独自の同期を実装する場合は、言語のメモリモデルに従って適切な順序を指定し、その挙動が正しいことを確認する必要がある。read/write 方式のみであっても同じ注意が必要である。また、アトミック read-modify-write を使う方式が常に最善とは限らないため、性能は実際の環境で測定して判断する必要がある。

4. スピンロック

スピンロック (spin lock) はロックが獲得できるまでループして待ち続ける相互排他の実装の一つである。クリティカルセクションが短く、待ち時間がコンテキストスイッチのコストより短いと期待できる場合 (典型的には数マイクロ秒) に適している。OS カーネルやランタイムの内部、ユーザ空間ロックの初期段階で用いられる。

4.1. TAS ロックと TTAS ロック

Algorithm 1 は Test and Set を使った最も単純なスピンロック実装 (TAS ロック) である。

1.	${\bf operation} \ {\rm acquire}()$
2.	$\hspace{12pt}{\bf while} \ {\rm test\_and\_set}(X) = 1$
3.	$\hspace{24pt}{\bf nop};$
4.	$\hspace{12pt}{\bf end}$
5.
6.	${\bf operation} \ {\rm release}()$
7.	$\hspace{12pt}X \leftarrow 0$

Algorithm 1. TAS ロック。

X

の初期値は 0。

ただし、この単純な TAS ロックは ${\rm test\_and\_set}$ が失敗しても共有メモリに書き込みを行うため、待機中の全プロセスが毎回コヒーレンストラフィックを発生させ、ロック保持者自身のメモリアクセスまで遅くする。Algorithm 2 に示す TTAS ロック (test-and-test-and-set) はそれを改良したものである [13, 14]。

1.	${\bf operation} \ {\rm acquire}()$
2.	$\hspace{12pt}{\bf repeat}$
3.	$\hspace{24pt}{\bf wait} \ X \ne 1$	// 通常の read; キャッシュにヒットするためトラフィックは起きない
4.	$\hspace{12pt}{\bf until} \ {\rm test\_and\_set}(X) = 0 \ {\bf end}$
5.
6.	${\bf operation} \ {\rm release}()$
7.	$\hspace{12pt}X \leftarrow 0$

Algorithm 2. TTAS ロック。

ここで ${\rm wait} \ X \ne 1$ は ${\rm while} \ X = 1; {\rm nop}; {\rm end}$ のスピンロックである。TTAS ロックでは、スピンの大部分がローカルキャッシュ上の read になるため、キャッシュコヒーレンスのためのトラフィックを大幅に減らすことができる。ただしロックが解放された瞬間に全プロセスのキャッシュラインが無効化され、全員が一斉に ${\rm test\_and\_set}$ を発行するため $O(n)$ RMR のサンダリングハードが起きる。スピンループには PAUSE (x86) や YIELD (ARM) といったヒント命令を入れ、投機実行とメモリオーダ違反のペナルティを抑えるのが典型的な実装である。

指数バックオフ (exponential backoff) は TTAS のサンダリングハードを緩和するための古典的な手法である [14]。これは ${\rm test\_and\_set}$ に失敗した後に乱数時間だけ待機し、失敗回数が増えるほど待ち時間の上限を指数的に増やす。実装は数行で済み、競合が多いときの性能が TTAS ロックより大きく改善する。一方、待ち時間の上限と下限がマシンとワークロードに依存するためチューニングが必要であり、公平性はまったく保証されない (直前に失敗したプロセスが最も長く待つため、むしろ不公平になりやすい) という明確な欠点を持つ。またロックが空いているのに誰も待機から復帰していない無駄な時間も生じる。そのため、強い競合や公平性が問題になる場合は、ticket ロックやキューロックも選択肢になる。

4.2. ticket ロック

ticket ロック (ticket lock) は窓口の整理券と同じ概念で、 ${\rm fetch\_and\_add}$ によって割り当てられた番号順でクリティカルセクションへ入ることを許可する。

1.	${\bf operation} \ {\rm acquire}()$
2.	$\hspace{12pt}{\it my\_ticket} \leftarrow {\rm fetch\_and\_add}({\it NEXT\_TICKET},1);$
3.	$\hspace{12pt}{\bf wait} \ {\it NOW\_SERVING} = {\it my\_ticket}$
4.
5.	${\bf operation} \ {\rm release}()$
6.	$\hspace{12pt}{\it NOW\_SERVING} \leftarrow {\it NOW\_SERVING} + 1$

Algorithm 3. ticket ロック。両レジスタの初期値は 0。

ticket ロックは FIFO 順、すなわち有界バイパスであることを保証し、実装が数行で状態も 2 ワードしか使用しないという利点がある。解放側も read-modify-write のような操作を必要とせず、単純なアトミック操作で済む。Linux カーネルのスピンロックも 2008 年から ticket ロックを採用していたが、一部のアーキテクチャは 2015 年に MCS を土台とする qspinlock に置き換えられている。

欠点は待機プロセスのすべてが同一の ${\it NOW\_SERVING}$ をスピンすることである。解放ごとに全員のキャッシュラインが無効化されるため $O(n)$ RMR が起き、コア数が増えると性能が劣化する。加えて FIFO であるため、次の順番のプロセスがスケジューラによって一時停止 (プリエンプト) されると、後続のすべてのプロセスが待たされることになる (head-of-line blocking)。 ${\it NOW\_SERVING}$ と自分の番号の差に比例した時間だけ待つ比例バックオフを加えるとキャッシュコヒーレンスのトラフィックを削減できる。

4.3. キューロック (MCS と CLH)

キューロック (queue lock) は待機するプロセスを順番待ちの列に並べるスピンロックである。単純なスピンロックは待機プロセスすべてが同じ変数を監視する一方で、キューロックでは各プロセスが自身の待機ノードを持ち、列の順に後続へロックを渡す。これにより、待機プロセスすべてが同じキャッシュラインへ一斉にアクセスする状況を回避し、1 回のクリティカルセクション通過に必要な RMR を $O(1)$ に抑えることができる。

MCS ロック [15] は待機プロセスを連結リストとして管理する。各プロセスは専用の待機ノードを用意し、アトミックな swap でロック待機キューの末尾ポインタを自分のノードに置き換える。置き換え前の列が空なら待機プロセスはいないため、そのプロセスがロックを獲得する。先行者がいる場合は、自分のノードをその列の末尾につなぎ、自分のノードの待機フラグが解除されるまで待つ。Algorithm 4 の疑似コードは MCS ロックを表している。現実の実装ではノードの寿命とメモリ順序も適切に管理する必要がある。

1.	${\bf type} \ {\rm Node} = \{\, {\it next}: \text{NodePointer}, \ {\it locked}: \text{Boolean} \,\}$
2.
3.	${\bf operation} \ {\rm acquire}(L, I)$	// $I$ は呼び出しプロセス自身のノード
4.	$\hspace{12pt}I.{\it next} \leftarrow {\rm nil};$
5.	$\hspace{12pt}{\it pred} \leftarrow {\rm swap}(L, I);$
6.	$\hspace{12pt}{\bf if} \ {\it pred} \ne {\rm nil}$
7.	$\hspace{24pt}I.{\it locked} \leftarrow {\bf true};$
8.	$\hspace{24pt}{\it pred}.{\it next} \leftarrow I;$
9.	$\hspace{24pt}{\bf wait} \ I.{\it locked} = {\bf false}$	// 自分のノード上でスピンする
10.	$\hspace{12pt}{\bf end}$
11.
12.	${\bf operation} \ {\rm release}(L, I)$
13.	$\hspace{12pt}{\bf if} \ I.{\it next} = {\rm nil}$	// 後続がいないように見える
14.	$\hspace{24pt}{\bf if} \ {\rm compare\_and\_swap}(L, I, {\rm nil})$
15.	$\hspace{36pt}{\bf return};$
16.	$\hspace{24pt}{\bf end};$
17.	$\hspace{24pt}{\bf wait} \ I.{\it next} \ne {\rm nil}$	// 後続が繋ぎ終わるのを待つ
18.	$\hspace{12pt}{\bf end}$
19.	$\hspace{12pt}I.{\it next}.{\it locked} \leftarrow {\bf false}$

Algorithm 4. MCS ロック。

L

は待機キューの末尾を表し、初期値は

{\rm nil}

である。

MCS はノードをキュー末尾へ追加した順にロックを渡すため FIFO 順となる。各プロセスは自分のノードを監視し、解放側は原則として次の待機者のノードだけを書き換える。したがって、待機プロセスが増えても 1 回のクリティカルセクション通過あたりの RMR は $O(1)$ である。ノードは待機中の各プロセスが保持し、解放後に安全に再利用または回収する。

CLH ロック [16, 17] もアトミックな swap でノードをキュー末尾に追加する。MCS とは異なり、待機プロセスはキューの一つ前のプロセスが使ったノードの待機フラグを監視する。その先行者が解放時にフラグを下げると、次のプロセスが進行する。

各プロセスは先行ノードをローカル変数 pred に保存する。解放時にそのノードを次回使う自分のノードへ切り替える。キュー末尾 $L$ は、フラグが解除されたダミーノードで初期化する。

1.	${\bf operation} \ {\rm acquire}(lock, I):$
2.	$\hspace{12pt}I.locked \leftarrow {\bf true}$
3.	$\hspace{12pt}pred \leftarrow {\rm swap}(lock.tail, I)$
4.	$\hspace{12pt}{\bf wait} \ pred.locked = {\bf false}$
5.	$\hspace{12pt}{\bf return} \ pred$
6.
7.	${\bf operation} \ {\rm release}(I, pred):$
8.	$\hspace{12pt}I.locked \leftarrow {\bf false}$
9.	$\hspace{12pt}I \leftarrow pred$	// 次回の獲得で再利用するノード

Algorithm 5. CLH ロック。tail はフラグが解除されたダミーノードで初期化する。

Java の AbstractQueuedSynchronizer は CLH に着想を得た待機キューを使うが、ここで示した CLH スピンロックそのものではない。AbstractQueuedSynchronizer 自体は待機スレッドをブロックするための同期の基礎であり、ReentrantLock や Semaphore などに使われる。

4.4. スピンロックの選択

CLH と MCS はいずれもキューロックアルゴリズムだが、待機中に監視するノードが異なる。この違いによるメモリアクセスのコストを評価するモデルに DSM (分散共有メモリ) と CC (キャッシュコヒーレント) がある。DSM モデルでは、各プロセッサのローカルメモリと、他のプロセッサのメモリへのリモート参照を区別する。各プロセスのノードをそのプロセスのローカルメモリに置いたとき、MCS は自身のノードを監視するため待機中の読み取りはローカルとなる。一方、CLH は先行プロセスのノードを監視するため、その読み取りがリモートになる場合がある。この点では、DSM モデルの観点で MCS のほうが待機中の通信を抑えやすい。一方、CC モデルの観点ではキャッシュ間の通信や無効化も性能に関わるため、この違いだけで実機上の優劣が決まるわけではない。

実測を前提とした上での一般的な傾向は次のとおりである。

競合がほぼない状況では、獲得が read-modify-write 1 回で済み、追加の状態もない TTAS が最良である。
競合が中程度で、コア数が少ない状況では ticket ロックが良い。追加で FIFO の特性も持つ。
競合が高い、またはコア数が多い状況では、 $O(1)$ RMR の効果により MCS/CLH が良い。
待ち時間が長い可能性がある状況では、スピンではなくブロッキングロックにする。

キューロックでは、待機列に登録したプロセスがタイムアウトやキャンセルで途中離脱するときに、前後のノードを安全につなぎ直す必要がある。そのためキャンセル可能な実装はより複雑になる。

5. ブロッキングロック

スピンロックはロックを獲得するまで CPU を使って状態を確認し続ける。クリティカルセクションが短ければすぐにロックを獲得できるが、待ち時間が長いと CPU 時間を消費し、ロックを確保したプロセスが実行される機会まで減らすことがある。このような状況では、待機中のプロセスを実行可能な状態から外し、ロックが空いたときに再開するブロッキングロック (blocking lock) 方式が有利である。

5.1. 短くスピンしてから待機

spin-then-park はスピンロックを少しの間だけ試行し、すぐに獲得できなければプロセスを停止させる。ロックがすぐに獲得できれば停止と再開のコストを避けられ、待機が長引けばスピンを続けず CPU を他の処理に譲る。この方針は多くのブロッキングロック実装で採用されている。スピンを続ける時間は、固定値にする場合も、過去の待機時間から調整する場合もある。

待機プロセスがいないときはロックの獲得と解放をユーザー空間のアトミック操作だけで完了できる実装が多い。競合して待つ必要が生じたとき、プロセスの停止や再開のために OS の機能を使用する。したがって、ロックのたびに必ずカーネルへ切り替わるわけではない。

5.2. futex

Linux の futex (fast userspace mutex) は、ユーザー空間での高速なロック操作と、競合時のカーネル待機を組み合わせるための仕組みである。通常、ロック状態そのものはユーザー空間のメモリに置かれ、ロックを獲得できる場合はユーザー空間のアトミック操作で完結する。待機が必要な場合は FUTEX_WAIT を使ってカーネルが指定アドレスの値を確認する。値が期待値と異なれば停止せずに戻るため、値を確認してから待機に入るまでにロックが解放される競合において、プロセスがそのまま停止し続けるのを防ぐことができる。解放側は必要に応じて FUTEX_WAKE で待機プロセスを再開する [18]。

pthread のミューテックスなどは、このような競合のない処理をユーザー空間で完結し、待機が必要な場合だけカーネル機能を使う設計を採ることがある。具体的な実装は OS やランタイムによって異なる。

5.3. 公平性と再入

公平性 (fairness) は待機しているプロセスにどの順でロックを渡すかという性質である。FIFO を保証するのであれば後から来たプロセスが先に何度もロックを獲得することを防ぎやすい。一方、次に実行するプロセスを指定して再開する方式では、そのプロセスが実行を再開するまでロックを使えないことがあり、処理全体のスループットが下がる場合がある。公平性を厳密に保証せず、再開したプロセス以外にも獲得を許す方式では、後から来たプロセスが先に獲得することがある。Java の ReentrantLock は既定ではこのような非公平モードを使用しており、new ReentrantLock(true) で公平モードを選択できる。どちらが適切かは遅延やスループットなどの要件による。

再入可能性 (reentrancy) とは、ロックを保持しているプロセスが同じロックをもう一度獲得できる性質である。再入可能なロックは、保持プロセスと獲得回数を記録し、同じプロセスによる再獲得を許す。再入可能性は再帰呼び出しなどで役立つ一方、ロックを保持したまま別の処理へ進む設計を見えにくくし、デッドロックの原因になることもある。Java の synchronized は再入可能であり、すでにオブジェクトのモニターを保持しているスレッドがさらにそのオブジェクトのモニターを取得できる。一方で Rust 標準の Mutex は再入可能ではなく、ロックを保持中に同じスレッドが再度ロックを要求するとデッドロックする。

5.4. ロック待ちを長引かせる要因

ブロッキングロックでもロックを保持しているプロセスが進行しなければ待機プロセスはロックを獲得できない。ロックを保持しているプロセスが OS によって一時停止されたり、I/O などで長く待ったりするとロックの解放も遅れる。

ロック保持プロセスのプリエンプション: OS がロック保持プロセスの実行を一時停止すると、待機プロセスはロックが解放されるまで待つことになる。スピンロックであれば待機プロセスも CPU を使い続けるため、ブロッキングロックよりも影響が大きくなることがある。仮想化環境で保持プロセスに vCPU が割り当てられない場合もロックの解放が遅れる。
優先度逆転 (priority inversion): 低優先度のプロセスがロックを保持し、その実行が中優先度のプロセスに妨げられると、そのロックを待機している高優先度のプロセスも進めなくなる。優先度継承はこれを緩和する方法で、ロック保持プロセスの優先度を待機プロセスに合わせて一時的に上げる。Linux の PI futex や POSIX の PTHREAD_PRIO_INHERIT はそのための仕組みを提供する。
コンボイ (convoy): ロック保持プロセスの停止などで待機列ができ、その後もプロセスが列の順序でしか進行できず処理が滞り続ける状態を指す。

複数のロックを組み合わせて使うと、それぞれのロックが単独では正しくても、全体でデッドロックすることがある。複数のロックを獲得する場合、取得順序を統一するなどコード全体で守る規約が必要になる。

6. 実務での設計と使用

安全なロックを使用するにはアルゴリズムを知るだけでは足りない。実務では「何を保護するか」「どの範囲でロックを保持するか」「条件待ちをどう表すか」を設計し、ロックが守る不変条件を一貫して維持することが重要である。

6.1. 保護対象と不変条件

不変条件の明示: ロックが保護するデータと、そのデータが常に満たすべき条件を定義する。関連する複数の値を一貫して更新するのであれば、それを読むプロセスが途中状態を観測しないよう同じロックで保護する。
全アクセスで同じ規約を守る: 共有メモリへの読み書きは、原則として同じロックを保持して行う。一部のアクセスだけロックを外すと、保護の前提が崩れる。アトミック変数を併用する場合も、その値だけで不変条件を保てるか検討する。
ロックの外へ参照を持ち出さない: 保護中のデータへのポインタや参照をロック解放後も使うと同期を迂回して競合するおそれがある。所有権や寿命を API で表し、ロックの範囲を越えた利用を防ぐ。

6.2. クリティカルセクションを短く保つ

ロックを保持する範囲は不変条件を保つために必要な最小限にする。ロック中の I/O、ネットワーク呼び出し、長い計算、別プロセスの完了待ち、ユーザ提供のコールバックは、待ち時間を予測しにくくし、デッドロックや遅延の連鎖を招くことがある。可能であれば、ロック内で必要な状態をコピーし、ロックを解放してから時間のかかる処理を行う。ただし、解放後に状態が変化しうる場合は、再確認やバージョン検証が必要になる。

ロックを細分化すると並行性は高まる一方で、複数ロックの取得や不変条件の維持が難しくなる。ロックをまとめると設計は単純になる一方、今度は競合が増える。まず、正しい保護範囲を作り、計測で競合を確認してから分割やストライピングを検討する。

6.3. デッドロックとロック順序

複数のロックを異なる順序で取得すると循環待機が起こりうる。たとえば、一方が $L_1$ を獲得してから $L_2$ を待機し、他方が $L_2$ を獲得してから $L_1$ を待機する場合である。対策の基本はすべてのコードでロックに一貫した順序を定めその順に取得することである。複数のロックをまとめて獲得する API がある場合はそれを利用する方法もある。

ロック取得中に別のロックやコールバックへ進行するケースを洗い出し、ロック順序をコードレビューで確認できるようにする。タイムアウトや try-lock は待機し続ける状況を検出・回避する手段にはなるが、誤った順序や不変条件を自動的に正すものではない。

6.4. 条件変数と述語

条件変数 (condition variables) は、共有状態がある特定の条件を満たすまでプロセスを一時的に待機させ、別のプロセスからの通知によって処理を再開させるための同期メカニズムである。たとえばブロッキングキューについて考える。キューが空の間は項目を取り出せないため、消費側のプロセスはキューを保護するロックを使って状態を確認し、空なら条件変数で待機する。生産側のプロセスが項目を追加して通知すると、消費側プロセスは再開してロックを取り直し、キューを確認する。通知を受けても、別のプロセスが先に項目を取り出していることがあるため、条件を確認して待機する処理を条件が満たされるまで繰り返す必要がある。

6.5. Read-Write ロックと代替手段

Read-Write ロックは、読み取りを複数プロセスで並行実行でき、書き込みを単一のプロセスで排他的に行えるようにする機構である。読み取りが多い場合に有効なことがあるが、通常のミューテックスより管理コストが高く、書き込み待ちの公平性も実装によって異なる。読み取りが多いというだけで Read-Write ロックを選択せずに、競合率、保持時間、待ち時間を測って判断すべきである。

共有状態を不変データとして扱う、メッセージや所有権をプロセス間で受け渡す、更新を単一プロセスに集約するといった方法で、ロック自体を減らせる場合もある。ロックフリーが常に速いとは限らず、再試行による CPU 消費や実装の複雑さも含めて比較する必要がある。

6.6. 検証と診断

競合状態は通常のテストで再現しないことがある。並行実行を検査するサニタイザーやプロセス解析ツールを使い、ロック順序、保持時間、待ち時間を計測することができる。性能調査では、平均値だけでなく、長い待ちの割合やテールレイテンシも観測すべきである。ログ出力はタイミングを変えて問題を隠すことがあるため、計測器や再現可能な負荷試験と併用する必要がある。

7. read/write レジスタのみによる解法 (歴史的背景)

1960 年代から 1980 年代にかけて、アトミックな read/write だけで相互排他を解くアルゴリズムの研究が盛んに行われた。当時のマシンにアトミック read-modify-write 命令がなかったという実務的な理由もあったが、より本質的には「共有メモリの読み書きという最小の手段で何ができるか」という計算可能性の研究だった。前述のとおり、これらの成果を現代の実装にそのまま使うことはないが、現在も使われる概念として残っている。

7.1. Dekker と Peterson のアルゴリズム

Dijkstra は 1965 年に相互排他問題を定式化し [5]、Dekker による 2 プロセス解を導入した。より簡潔な形として広く知られているのが Peterson のアルゴリズム [7] である。これは単独では誤っている 2 つの部品の合成として理解することができる。入りたいことを表明し相手のフラグが下がるのを待つ「フラグのみ方式」は両者が同時にフラグを上げるとデッドロックし、 ${\it AFTER\_YOU}$ に自分の名前を書いて相手の名前に変わるのを待つ「譲り合いのみ方式」は単独のプロセスが永久に待機する。しかし両方を順に行うことで、どちらかの条件が満たされれば進むようにすると正しく機能する。

1.	${\bf operation} \ {\rm acquire}(i, j)$
2.	$\hspace{12pt}{\it FLAG}[i] \leftarrow {\rm up}$
3.	$\hspace{12pt}{\it AFTER\_YOU} \leftarrow i$
4.	$\hspace{12pt}{\bf wait} \ ({\it FLAG}[j] = {\rm down}) \lor ({\it AFTER\_YOU} \ne i)$
5.
6.	${\bf operation} \ {\rm release}(i)$
7.	$\hspace{12pt}{\it FLAG}[i] \leftarrow {\rm down}$

Algorithm 6. Peterson のアルゴリズム (

p_i

のコード、

j

は相手)。

このアルゴリズムは相互排他と $f(n) = 1$ の有界バイパスを満たし、必要な領域は 3 ビットだけである。 ${\rm acquire}$ での ${\it FLAG}[j]$ と ${\it AFTER\_YOU}$ の読み出しが非同期に、任意の順序で行われてもよい点に注意。

このアルゴリズムは弱いメモリモデルの危険性を説明する標準的な教材として今も価値がある。正しさが 2 つの書き込みと 2 つの読み出しの順序に依存しているため、ストアバッファを持つ現実的なマシンでは MFENCE 相当のバリアなしには機能しない。「アルゴリズムとしては正しいが実際のコードとしては機能しない」典型的な例である。

7.2. $n$ プロセスへの一般化とコスト削減

以下はいずれも read/write レジスタのみを用いるアルゴリズムであり [4]、競合がないときのアクセス回数を削減する歴史的な過程を示している。現代の実装で使われることはないが、ここで生まれた概念は後の話題として受け継がれている。

Peterson の $n$ プロセス版: 2 値フラグをレベルに一般化し、各プロセスがレベル $1$ から $n-1$ まで順に勝ち上がる。各レベルで 2 プロセス版と同じ譲り合いを行う。相互排他と飢餓フリーを満たすが、有界バイパスは満たさない。競合がない場合のコストは $(n-1)(n+2)$ 回のアクセスで、 $O(n^2)$ である。ループ上限を $n-k$ に変えるだけで、たかだか $k$ プロセスを許す  $k$ -排他問題の解となる。
トーナメント木 (tournament tree) [6]: $n-1$ 個の 2 プロセスロックを完全二分木に並べ、葉から根まで勝ち上がる。競合がない場合のコストは $O(\log n)$ まで削減できる。有界個の有界なレジスタで完結する。
Lamport の高速相互排他 [10]: 競合がない場合のコストに対し、獲得 5 回 + 解放 2 回 = 7 回のアクセス、つまりプロセス数に依存しない定数を達成した。高速パスと低速パスを持ち、競合時にはデッドロックフリーを保証する。この発想は、コストが実際の参加プロセス数に依存する適応的 (adaptive) アルゴリズムの概念に繋がった。

高速相互排他の中核にある one-shot の設計は現代でも生き残っている唯一の構成要素である。2 つのレジスタ $X, Y$ に対し「 $X$ に自身を書く → $Y$ が空か確認する → $Y$ に自分を書く → $X$ がまだ自分かを確認する」という 4 アクセスの手続きは、競合がなければ必ず成功し、競合があれば「どこで失敗したか」によって呼び出し元を 3 方向に振り分ける。結果を stop, right, left と名付けたものをスプリッタ (splitter) と呼ぶ。 $m$ プロセスが呼び出したとき stop を得るのはたかだか 1 つ、right と left を得るのはそれぞれたかだか $m-1$ であり、この「集団を分割する」性質が wait-free なオブジェクトやリネーミングの構成部品として使われる。

7.3. 原子性を仮定しない解法

ここまでのアルゴリズムは read と write がそれぞれアトミックに行われることを前提としていた。しかし Lamport は、相互排他でより強い原子性を実現するために土台となる操作に原子性が必要ないことを示した。

その結果を見る前に、read/write レジスタが並行アクセスに対してどのような値を返すかを、保証の強さに応じて 3 段階に分ける。ここでは各レジスタへの書き込みは 1 つのプロセスだけが行うものと仮定する。

safe レジスタ: write と重ならない read は最後に書き込まれた値を返す。write と重なる read は定義域に含まれるどの値を返してもよい。
regular レジスタ: safe レジスタの保証に加え、write と重なる read は read の開始時点での値かその read と並行して書き込まれている値のどちらかを返す。ただし、連続した read が一度新しい値を返した後で古い値を返すことはありうる。これを new/old 反転 (new/old inversion) と呼ぶ。
atomic レジスタ: regular レジスタの保証を満たし new/old 反転が起こらない [9]。

safe レジスタは 3 種類の中で最も弱い保証を持つ。読み書きが重なったときに調整する仕組みを仮定せず、読み書きが重ならない場合にだけ値を保証する。Lamport のベーカリーアルゴリズム [8] はこの safe レジスタだけを使って相互排他を実現する。パン屋で整理券を取るように、各プロセスは ${\it MY\_TURN}[i] \leftarrow \max_j {\it MY\_TURN}[j] + 1$ で番号を受理し、番号とプロセス識別子の組 $\langle {\it MY\_TURN}[i], i \rangle$ を辞書順序で比較して入場順を決める。番号を決めている期間 (ドアウェイ) をフラグで示すことで、同時に番号を取ろうとしたプロセス間でも順序が矛盾しないようにする。このアルゴリズムは相互排他を満たし、有界バイパスの上限は $f(n)=n-1$ である。

この要点は、番号を読み取るときに write と重ならないよう手順を組み立てていることである。そのため、並行アクセス中の値を保証しない safe レジスタであっても番号を正しく読み取れる。ベーカリーアルゴリズムの番号は際限なく大きくなるが、Aravind のアルゴリズム [11] はこれを有界化した。この方式では、各プロセスが 1 ビットレジスタ 2 個と有界な日付レジスタを持ち、クリティカルセクション内で日付配列をリセットする。定義域の大きさが $N \ge 2n$ の場合に飢餓フリーを達成する一方で、有界バイパスの上限は $2n-2$ に増えている。

safe, regular, atomic という保証の段階はレジスタを組み立てる問題にもなる。つまり、safe な 1 ビットレジスタから atomic な多値レジスタを構築できるかという問いである。この答えは「可能」である。

7.4. これらが残したもの

read/write のみの相互排他アルゴリズムは実装としては使われなくなったが、次の結果と概念は現在も有効である。

活性の階層: デッドロックフリー、飢餓フリー、有界バイパスの区別。現代のロックを評価するときの指標そのものである。
領域の下限: $n$ プロセスのデッドロックフリーな相互排他を read/write レジスタのみで解くには $n$ 個のレジスタが必要である [12]。つまり、read/write だけを使う場合はレジスタ 1 個の幅を大きくしても必要な個数を $n$ 未満にはできない。一方で compare and swap を使うロックはロック状態を 1 ワードで管理できる。
原子性の非必然性: 高位のアトミック操作を構築するために下位レベルの原子性を必要としない。これはレジスタ構成の理論全体の出発点になる。
スプリッタと適応性: 競合の有無でコストが変わるアルゴリズムという考え方、およびその部品としてのスプリッタ。
メモリモデルの教材: 逐次一貫性を仮定したアルゴリズムが現実的なマシンで機能しないことの最も明確な例である。

8. 相互排他の限界

相互排他は強力だが、原理的な代償が残る。

障害耐性がない: ロックを保持したままプロセスがクラッシュすると、他のすべてのプロセスが永久に進行できなくなる。
最も遅いプロセスに律速される: 保持プロセスのプリエンプションや優先度逆転はこの一般的な現象が顕在化したものである。
合成できない: 個々に正しいロックベースの機構を組み合わせても正しさは保たれず、複数ロックの獲得順序という大域的な規約が必要になる。

これらの限界を回避するための方向性が 2 つある。1 つは、ロックを使わずに「あるプロセスの停止が他のプロセスを妨げない」ｋとを保証する実装、すなわち wait-free や lock-free といった進行条件に基づく機構である。もう 1 つは、同期を手続きとして書かずに宣言的に指定する方向であり、セマフォやモニタ、トランザクショナルメモリがこれにあたる。

9. まとめ

相互排他問題は、安全性 (一度に最大でも 1 プロセスが進行) と活性 (デッドロックフリー、飢餓フリー、有界バイパス) によって定義され、これを解くことはロックを実装することと等価である。

現代の実装では、正しさはアトミック read-modify-write プリミティブとメモリバリアを使って確保し、性能は RMR すなわちコヒーレンストラフィックで評価する。競合が低ければ TTAS、FIFO が必要なら ticket lock、コア数が多ければ MCS/CLH、待ちが長くなりうるなら futex による spin-then-park という選択になる。競合のないパスを read-modify-write 1 回に保ち、カーネルには競合時のみ入るという構造が汎用ミューテックスの共通形である。

read/write レジスタのみによる古典的アルゴリズムは、弱いメモリモデルの下では各アクセスの順序をバリアで保証しなければならない。これは、 $n$ プロセス版では競合がなくても $O(n^2)$ 回のアクセスと $n$ 個のレジスタを要する。これはアトミック read-modify-write を 1 回で完結する実装よりも有利な点がないため、現代の実装としては役目を終えている。しかし活性の階層、領域の下限、原子性が下位レベルで必要でないという結果、そしてスプリッタのような部品は、ロックを使わない同期の理論へ引き継がれている。

10. 参考文献

Michel Raynal. Concurrent Programming: Algorithms, Principles, and Foundations. Springer-Verlag Berlin Heidelberg (2013)
Maurice Herlihy, Nir Shavit, Victor Luchangco, Michael Spear. The Art of Multiprocessor Programming, 2nd Edition. Morgan Kaufmann (2020)
Michael L. Scott, Trevor Brown. Shared-Memory Synchronization, 2nd Edition. Springer Cham (2024)
Gadi Taubenfeld. Synchronization Algorithms and Concurrent Programming. Pearson Education (2006)
Edsger W. Dijkstra. Solution of a Problem in Concurrent Programming Control. Communications of the ACM, Vol. 8, No. 9, p. 569 (1965)
Gary L. Peterson, Michael J. Fischer. Economical Solutions for the Critical Section Problem in a Distributed System. Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), pp. 91-97 (1977)
Gary L. Peterson. Myths About the Mutual Exclusion Problem. Information Processing Letters, Vol. 12, No. 3, pp. 115-116 (1981)
Leslie Lamport. A New Solution of Dijkstra's Concurrent Programming Problem. Communications of the ACM, Vol. 17, No. 8, pp. 453-455 (1974)
Leslie Lamport. On Interprocess Communication, Part I: Basic Formalism, Part II: Algorithms. Distributed Computing, Vol. 1, No. 2, pp. 77-101 (1986)
Leslie Lamport. A Fast Mutual Exclusion Algorithm. ACM Transactions on Computer Systems, Vol. 5, No. 1, pp. 1-11 (1987)
Alex A. Aravind. Yet Another Simple Solution for the Concurrent Programming Control Problem. IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No. 6, pp. 1056-1063 (2011)
James E. Burns, Nancy A. Lynch. Bounds on Shared Memory for Mutual Exclusion. Information and Computation, Vol. 107, No. 2, pp. 171-184 (1993)
Larry Rudolph, Zary Segall. Dynamic Decentralized Cache Schemes for MIMD Parallel Processors. Proceedings of the 11th Annual International Symposium on Computer Architecture (ISCA), pp. 340-347 (1984)
Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 1, pp. 6-16 (1990)
John M. Mellor-Crummey, Michael L. Scott. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems, Vol. 9, No. 1, pp. 21-65 (1991)
Travis S. Craig. Building FIFO and Priority-Queueing Spin Locks from Atomic Swap. Technical Report TR 93-02-02, Department of Computer Science, University of Washington (1993)
Peter S. Magnusson, Anders Landin, Erik Hagersten. Queue Locks on Cache Coherent Multiprocessors. Proceedings of the 8th International Parallel Processing Symposium (IPPS), pp. 165-171 (1994)
Hubertus Franke, Rusty Russell, Matthew Kirkwood. Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux. Proceedings of the Ottawa Linux Symposium, pp. 479-495 (2002)
Hagit Attiya, Danny Hendler, Philipp Woelfel. Tight RMR Lower Bounds for Mutual Exclusion and Other Problems. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 217-226 (2008)
Leslie Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers, Vol. C-28, No. 9, pp. 690-691 (1979)
Sarita V. Adve, Kourosh Gharachorloo. Shared Memory Consistency Models: A Tutorial. IEEE Computer, Vol. 29, No. 12, pp. 66-76 (1996)