排他制御
排他制御（はいたせいぎょ）とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他（mutual exclusion）ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。
換言すれば1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが Solution of a problem in concurrent programming control（並行プログラミング制御における問題の解法）と題した論文で扱ったのが最初である[1][2]。
排他制御の重要性を示す例として、片方向連結リストがある（右図）。このような連結リストからノードを削除するには、1つ前のノードにある次のノードを指すポインタを削除したいノードの次のノードを指すように書き換える（例えば、ノード i を削除するには、ノード i-1 のnextポインタをノード i+1 を指すよう書き換える）。このとき、その連結リストを複数プロセスが共有しているなら、2つのプロセスがそれぞれ別のノードを削除しようとして次のような問題を生じる可能性がある。
- 2つのプロセスはそれぞれノード i と i+1 を同時に削除しようとする。どちらのノードも連結リストの途中にあり、先頭でも最後尾でもないとする。
- ノード i-1 のnextポインタはノード i+1 を指すよう書き換えられ、ノード i のnextポインタはノード i+2 を指すよう書き換えられる。
- 両方の削除処理が完了した状態を見ると、ノード i-1 がノード i+1 を指すよう書き換えられたために、ノード i+1 は連結リストに残ってしまう。
この問題は排他制御を施して複数の状態更新処理が同時に行われないようにすれば解決する。
目次
排他制御の実施
排他制御を実施する手段はハードウェアによるものとソフトウェアによるものがある。
ハードウェアによる方式
シングルプロセッサシステムでは、あるプロセスがクリティカルセクションにあるとき割り込みを禁止するというのが最も単純な排他制御である。その間、いかなる割り込みハンドラも動作できない（それによって実質的にプリエンプションを防ぐ）。この方式は効果的だが、同時に様々な問題もはらんでいる。クリティカルセクションが長い場合、クロック割り込みが処理されないためにシステム時刻が徐々に遅れていくという事態が発生しうる。また、クリティカルセクション内でプロセスが停止すると、他のプロセスに制御を渡せなくなり、結果としてシステム全体が停止することになる。μITRONなどでは、タスク切り替え（プリエンプションとディスパッチ）を禁止するという操作もある。より上品な方式としてビジーウェイトで相互排他する方式もある。
ビジーウェイトはシングルプロセッサでもマルチプロセッサでも有効である。共有メモリと不可分なテスト・アンド・セット命令を使うことで、排他制御を実現する。プロセスは共有メモリ上の特定位置について値を調べて新たな値をセットするという操作を不可分に実施でき、それによって一度に1つのプロセスだけがフラグをセットできることを保証する。フラグをセットできなかったプロセスは別の処理を行って後で再試行するか、プロセッサを他のプロセスに明け渡して後で再試行するか、フラグをセットできるまでループして再試行を繰り返すといった動作が可能である。プリエンプションは可能なので、この方式ではプロセスがフラグ（ロック）を保持したまま停止してもシステム全体は機能し続ける。
不可分操作命令は他にもいくつかの実装があり、どれもデータ構造の排他制御に使える。よく見られるのはコンペア・アンド・スワップ (CAS) である。CAS命令を使えば wait free と呼ばれる排他制御を任意の共有データに実施できる。そのためには連結リストを作り、各ノードが実行したい操作を表すようにする。CAS命令はその連結リストに新しいノードを挿入する際に使用する。ノードの挿入はCAS命令を使えば一度に1つのプロセスしか成功しない。失敗したプロセスはノード追加処理が成功するまで試行し続ける。各プロセスはこのデータ構造のローカルなコピーを保持でき、連結リストを走査でき、リストのローカルコピー上の各操作を実行できる。
ソフトウェアによる方式
ハードウェアサポートを必要とする方式とは別に、ビジーウェイトを使ってソフトウェアのみで排他制御を実現する方式も存在する。例えば、次のようなものがある。
- デッカーのアルゴリズム
- ピーターソンのアルゴリズム
- ランポートのパン屋のアルゴリズム[3]
- Szymanskiのアルゴリズム（en）
- Taubenfeld の Black-White Bakery Algorithm[2]
これらのアルゴリズムはアウト・オブ・オーダー実行が働くプラットフォーム上では動作できない。アルゴリズム実施中、メモリ操作はプログラミングした通りに行われなければならない[4]。
OSのマルチスレッドライブラリが同期機構を提供しているなら、それを使う方が望ましい。ハードウェアによる方式が利用可能ならばそれを使って実装されているだろうし、そうでないならばソフトウェアによる方式を利用しているだろう。たとえばOSのライブラリを使い、スレッドが他者が既に獲得しているロックを獲得しようとしたとき、OSはそのスレッドを中断させてコンテキストスイッチし動作可能な他のスレッドを動作させたり、動作可能な他のスレッドがなければプロセッサを省電力状態にしたりといったことをする可能性がある。したがって、ほとんどの現代の排他制御技法はキューイングとコンテキストスイッチを使いレイテンシとビジーウェイト時間を削減しようとする。しかし、スレッドを中断させて再開させるのにかかる時間がスレッドがロックを獲得できるまでの待ち時間より長い場合に限り、スピンロックの方が適しているといえる。
高度な排他制御
これまでに説明した方式を使い、次のような同期プリミティブが構築できる。
排他制御の多くの形式には副作用がある。例えば、古典的セマフォはデッドロックを引き起こしうる。あるプロセスがあるセマフォを獲得し、別のプロセスが別のセマフォを獲得した状態で、互いに相手の獲得したセマフォが解放されるのを待ち続けることが考えられる。よくある副作用としてリソーススタベーションがあり、その場合プロセスは処理を完遂するのに十分な資源を決して得られない。また、優先順位の逆転は低優先度のスレッドのせいで高優先度のスレッドが待たされる現象であり、レイテンシが長くなり、割り込みへの反応が悪くなる。
排他制御に関する研究の多くはそういった副作用を排除することを目的としており、例えばLock-freeとWait-freeアルゴリズムはブロッキングされずに処理が進行することを保証する。完璧な方法はまだ見つかっていない。
留意すべき現象と性質
デッドロック
テンプレート:Main 排他制御によりロックされた資源に他のユーザからアクセス要求が出された時、両者は互いに使用中の資源が解放されるのをブロック状態で待つという状況が発生することがある。2つ以上のユーザ間で生じるが、この状態ではどのユーザも資源の解放を待ったまま処理が進まずに停止状態となる。 この様な状態をデッドロックという。
ライブロック（Livelock）
デッドロックと同様、排他制御によりロックされた資源に、複数のユーザからアクセス要求が出されたときに、お互いに資源が解放されるのをビジー状態で待つという状況が発生する。デッドロックでは個々のユーザにおける資源獲得のための処理が進行しないのに対し、ライブロックでは資源獲得の処理が進行しているにも拘らず、どのユーザも資源が獲得出来ない状況である。
例えば、狭い道を歩いていて対面した歩行者2名が、お互いに相手が避けようとした方向に動いてしまい、避けられ無いという事が有る。次に、逆の方向に避けようして避けられない。このような状況が続いて、何時まで経ってもすれ違うことが出来ないという状況にあたる。(リソーススタベーション参照)
フェアネス（公平性、Fairness）
「共有資源を利用したいユーザが、いつかは共有資源を利用できる」という、排他制御アルゴリズムが満たすべき性質。 フェアネスが満たされない場合の例であるが、駅の切符売り場に3台の券売機があって、各券売機に行列が出来ているとき、並んだ行列の進みが遅い場合に他の行列の後尾に並びなおす戦略を採用すると、運が悪ければ何時まで経っても券を購入できないということが起こりうる。
k-バイパス（k-Bypass）
共有資源へのアクセス要求を出したユーザが、後から要求を出した最大k個のユーザによって、先に資源を使われてしまう可能性があるということを表す、フェアネスの度合いを計る指標である。
脚注
参考文献
- Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
- Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
- Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
- Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6
関連項目
外部リンク
- "Common threads: POSIX threads explained - The little things called mutexes" by Daniel Robbins
- Mutual exclusion algorithm discovery
- Mutual Exclusion Petri Net
- Mutual Exclusion with Locks - an Introduction
- Mutual exclusion variants in OpenMP
- The Black-White Bakery Algorithm
