排他制御せずに i と i+1 という2つのノードを同時に連結リストから外す操作を行うと、結果として i+1 のノードが外れないという状態になりうる。
排他制御（はいたせいぎょ）とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他（mutual exclusion）ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。
換言すれば1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが並行プログラミング制御における問題の解法に付いて扱った論文で扱ったのが最初である[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つのプロセスしか成功しない。失敗したプロセスはノード追加処理が成功するまで試行し続ける。各プロセスはこのデータ構造のローカルなコピーを保持でき、連結リストを走査でき、リストのローカルコピー上の各操作を実行できる。
ソフトウェアによる方式[編集]
ハードウェアサポートを必要とする方式とは別に、ビジーウェイトを使ってソフトウェアのみで排他制御を実現する方式も存在する。例えば、次のようなものがある。
これらのアルゴリズムはアウト・オブ・オーダー実行が働くプラットフォーム上では動作できない(但し、メモリバリアを実現する機械語命令を持っているCPUプラットフォームの場合は除く)。アルゴリズム実施中、メモリ操作はプログラミングした通りに行われなければならない[4]。
OSのマルチスレッドライブラリが同期機構を提供しているなら、それを使う方が望ましい。ハードウェアによる方式が利用可能ならばそれを使って実装されているだろうし、そうでないならばソフトウェアによる方式を利用しているだろう。たとえばOSのライブラリを使い、スレッドが他者が既に獲得しているロックを獲得しようとしたとき、OSはそのスレッドを中断させてコンテキストスイッチし動作可能な他のスレッドを動作させたり、動作可能な他のスレッドがなければプロセッサを省電力状態にしたりといったことをする可能性がある。したがって、ほとんどの現代の排他制御技法はキューイングとコンテキストスイッチを使いレイテンシとビジーウェイト時間を削減しようとする。しかし、スレッドを中断させて再開させるのにかかる時間がスレッドがロックを獲得できるまでの待ち時間より長い場合に限り、スピンロックの方が適しているといえる。
高度な排他制御[編集]
これまでに説明した方式を使い、次のような同期プリミティブが構築できる。
排他制御の多くの形式には副作用がある。例えば、古典的セマフォはデッドロックを引き起こしうる。あるプロセスがあるセマフォを獲得し、別のプロセスが別のセマフォを獲得した状態で、互いに相手の獲得したセマフォが解放されるのを待ち続けることが考えられる。よくある副作用としてリソーススタベーションがあり、その場合プロセスは処理を完遂するのに十分な資源を決して得られない。また、優先順位の逆転は低優先度のスレッドのせいで高優先度のスレッドが待たされる現象であり、レイテンシが長くなり、割り込みへの反応が悪くなる。
排他制御に関する研究の多くはそういった副作用を排除することを目的としており、例えばLock-freeとWait-freeアルゴリズムはブロッキングされずに処理が進行することを保証する。完璧な方法はまだ見つかっていない。
留意すべき現象と性質[編集]
排他制御によりロックされた資源に他のユーザからアクセス要求が出された時、両者は互いに使用中の資源が解放されるのをブロック状態で待つという状況が発生することがある。2つ以上のユーザ間で生じるが、この状態ではどのユーザも資源の解放を待ったまま処理が進まずに停止状態となる。
このような状態をデッドロックという。
ライブロック（livelock）[編集]
デッドロックと同様、排他制御によりロックされた資源に、複数のユーザからアクセス要求が出されたときに、お互いに資源が解放されるのをビジー状態で待つという状況が発生する。デッドロックでは個々のユーザにおける資源獲得のための処理が進行しないのに対し、ライブロックでは資源獲得の処理が進行しているにも拘らず、どのユーザも資源が獲得できない状況である。
例えば、狭い道を歩いていて対面した歩行者2名が、お互いに相手が避けようとした方向に動いてしまい、避けられないという事が有る。次に、逆の方向に避けようして避けられない。このような状況が続いて、何時まで経ってもすれ違うことができないという状況にあたる。(リソーススタベーション参照)
フェアネス（fairness）[編集]
「共有資源を利用したいユーザが、いつかは共有資源を利用できる」という、排他制御アルゴリズムが満たすべき性質。
フェアネスが満たされない場合の例であるが、駅の切符売り場に3台の券売機があって、各券売機に行列が出来ているとき、並んだ行列の進みが遅い場合に他の行列の後尾に並びなおす戦略を採用すると、運が悪ければ何時まで経っても券を購入できないということが起こりうる。
k-バイパス（k-bypass）[編集]
共有資源へのアクセス要求を出したユーザが、後から要求を出した最大k個のユーザによって、先に資源を使われてしまう可能性があるということを表す、フェアネスの度合いを計る指標である。
あるプロセスがロックを獲得したにもかかわらず、そのプロセスが現にCPU上で実行されていないため、実質的にどのプロセスやCPUもクリティカルセクション内の処理を実行していない状態。ロックの目的に照らし合わせると無駄な状態である。ロックの獲得からクリティカルセクション内の処理を開始するまでに遅延が発生したりコンテキストスイッチの回数が増加するため、システムの応答遅延増加や全体性能の劣化を招く。
ロックを解放したプロセスが、そのロックを待ってスリープしているプロセスのいずれかへロックの所有権を直接渡してしまう実装になっていると発生しやすくなる。対策として、ロックを獲得したいプロセスは必ず自分自身でロック獲得を試みる実装にすることにより問題が軽減される。典型例はスピンロックで、ロックを獲得したいプロセスは仕様上決してスリープしない。逆にロック待ちのプロセスがスリープする場合は、スリープ終了からロック獲得までの手順によってはコンボイに陥りやすくなる。
優先度上限プロトコルは優先度がサポートされている環境下にて、優先度継承はロック所有中のプロセスよりも優先度が高いプロセスがロックを獲得しようとした場合に、それぞれこの問題を優先度に依存した別々のアプローチで解決しようとする。ただし、コンボイの本質は「プロセスが現にCPU上で実行中ではないにもかかわらずロックを獲得してしまう」ことにあり、優先度の有無には関係ないため、両者とも問題を直接解決するものではない。[5]スピンロックがコンボイの問題を逃れていることから明らかなように、「プロセスが自力でロックを獲得する」実装に制限することが本質的な解決となる。
- ^ E. W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM, 8(9), page 569, September, 1965.
- ^ a b Taubenfeld. The Black-White Bakery Algorithm. In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56-70, 2004
- ^ L. Lamport. A new solution of Dijkstra’s concurrent programming problem. Communications of the ACM, 17(8):453–455, August 1974.
- ^ Holzmann, G.J. Bosnacki, D. “The Design of a Multicore Extension of the SPIN Model Checker”, Software Engineering, IEEE Transactions on, vol. 33, no. 10, pp.659-674, Oct. 2007
- ^ 優先度上限プロトコルは、ロックを獲得したいプロセスがすべて上限いっぱいの優先度であると機能しない。優先度継承は、ロック獲得中のプロセスよりも優先度が高いプロセスがロックを獲得しようとするまで動作しない。
- 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
