ロック (情報工学)
出典: フリー百科事典『ウィキペディア（Wikipedia）』
情報工学におけるロック（lock）とは、多くのスレッドのある環境でのリソースへのアクセス制限を課す同期機構。ロックは並行性制御ポリシーを実施する手法のひとつである。
目次 |
[編集] 種類
一般に、関連付けられたデータにアクセスする前にロックを獲得するよう各スレッドが協力するものであって、ロックに強制力はない（これを助言ロック; Advisory lock と呼ぶ）。システムによっては強制ロック（Mandatory lock）を実装しており、ロックされたリソースに許可されていないアクセスを行おうとしたときに例外が発生するようになっている。
(2値の)セマフォは最も単純なロックである。共有モード（リードオンリー）か排他モード（リードライト）かは区別されない。他の方法では、複数のスレッドがリードオンリーアクセスのためにロックを共有する共有モードを用意している。共有(shared)、排他(exclusive)、削除目的(intend-to-exclude)、更新目的(intend-to-upgrade)などのモードが広く実装されている。
以上のようなロックの種類とは別に、ロックによってスレッドの進行が妨げられたときの動作によっても分類できる。多くのロックは、ロックされたリソースへのアクセスが可能となるまで、プロセスの実行をブロックする。スピンロックは単純にロックを獲得できるまでスレッドが待つ（スピンする）。これは待つ期間が短い場合は効果的で、オペレーティングシステムによるプロセスのスケジューリングのオーバヘッドもかからない。ただし、長時間ロックされたままの場合は非常に無駄である。
[編集] 実装
ロックは一般に効率的な実装をするにはハードウェアによるサポートを必要とする。通常、1つ以上のアトミック命令を使用する（「テスト・アンド・セット」、「フェッチ・アンド・アッド」、「コンペア・アンド・スワップ」など）。これらの命令は、プロセスがロックが獲得されていない（フリーである）ことをチェックするとともに、不可分な（アトミックな）処理としてロックを獲得できる。
プロセッサが1つであれば、割り込みを禁止して命令列を実行することで同等の効果が得られる。しかし、マルチプロセッサではこれでは不十分である。マルチプロセッサ環境でロックをサポートすることはハードウェアとソフトウェアの複雑なサポートを要し、同期の主要な課題でもある。
アトミックな操作が必要とされる理由は、並列処理では複数のタスクが同じロジックを同時に実行している可能性があるからである。例えば、以下のC言語のコードを考えてみよう。
if (lock == 0) lock = myPID; /* ロックがフリーならセットする */
複数のタスクが並行して動作可能なら、上記のコードはロックを獲得できるとは言えない。どちらのタスクもロックがフリーであると判断し、どちらもロックに自身のIDをセットして獲得しようとするが、他のタスクも同時にロックを獲得しようとしていることを知らない。アトミックなロック操作ができないときは、デッカーのアルゴリズムやピーターソンのアルゴリズムで代替することもできる。
ロックの不注意な使用によりデッドロックが生じることがある。これはプロセスがあるロックを獲得した状態で別のロックを獲得しようとしたときに発生する。もし2番目のロックが別のプロセスに獲得されていれば、最初のプロセスはブロックされる。2番目のプロセスが最初のプロセスが獲得済みのロックを獲得しようとすると、システムは「デッドロック」状態となり、どちらのプロセスもブロックされたままとなる。これを防ぐための（あるいは回復するための）様々な戦略が設計時や実行時に採用されている。例えば、各ロックが保護するデータの種類によってロックに優先順位を設定し、順位通りでないとロックを獲得できないようにするなどの対処がある（ただし、同じ種類のデータを2つロックしなければならないときなどはデッドロックに注意しなければならない）。
[編集] 粒度
ロックの粒度(Granularity)を説明する前に、ロックに関する3つのコンセプトを説明する。
- ロックのオーバヘッド: ロックそのものに要するメモリ領域などの追加のリソース、ロックの初期化などにかかるCPU時間、ロック操作にかかるCPU時間など。プログラムがロックを多数使えば使うほど、オーバヘッドも大きくなる。
- ロックの競合: 他のプロセスやスレッドが獲得しているロックを獲得しようとすることをロックの競合という。ロックを細分化すれば、プロセス/スレッド間で競合が発生する可能性は小さくなる。例えば、配列全体ではなく行単位、あるいは要素単位にロックするといったことである。
- デッドロック: 上述の問題。何らかの処置をしないと複数のタスクがずっと待ち続けることになる。
従って、同期のためのロックの数を決定する際に、ロックのオーバヘッドとロックの競合がトレードオフの関係にある。
ロックの重要な特性として粒度(Granularity)がある。粒度とは、ロックが保護するデータの大きさである。一般に粗い粒度（ロック数が少なく、各ロックが大きなデータ領域を保護する）ではロックのオーバヘッドは小さいが、複数プロセスが並行動作するときの性能は低下する。これは粗い粒度ではロックの競合が発生し易いためで、ロックによってプロセスがブロックされる確率が非常に高くなる。反対に細かい粒度（ロック数が多く、各ロックが非常に小さなデータを保護する）ではロック自体のオーバヘッドは増大するが、ロックの競合は低減する。また、ロック数を増やすとデッドロックの危険性が増す。
データベースマネジメントシステムでは、ロックは粒度によって、レコード単位、データページ単位、テーブル全体などを保護対象とする。テーブル全体などの粗い粒度のロックはシングルユーザーで性能向上させるのに有利であり、レコード単位などの細かい粒度のロックは複数ユーザーでの性能向上に有利である。
[編集] データベースのロック
データベースでは、ロックはトランザクションの同時性を保証する手段として使うことが出来る。すなわち、トランザクション処理が並行して行われるとき（インタリービング式トランザクション）、ツーフェーズロックを使ってトランザクションの並行実行が直列化されたトランザクションと等価であることを保証する。しかし、データベース内のロックの副作用としてデッドロックが発生することがある。デッドロックはロック順序を事前に定義しておくことで防いだり、待ち状態グラフを使って検出したりする。データベースの一貫性のためにロックを使う以外の手段として、完全に順序が決定されるグローバルなタイムスタンプを使用することでデッドロックを防ぐこともある。
[編集] ロックにまつわる問題
ロックによるリソース保護とスレッド/プロセスの同期には以下のような問題がある:
- ブロックする方法であるため、スレッド/プロセスは他が確保しているロックが解放されるのを待たなければならない。
- ロックは保守的な手法である。何故なら、スレッドは競合が発生すると予想される場合には常にロックを確保しなければならず、実際には競合が発生することは滅多にない。保守的手法であるがゆえに不必要なオーバヘッドが生じる。
- ロックは故障や障害に無防備である。あるスレッドがロックを獲得したまま終了すると、他のスレッドはそのロックを獲得しようとして永遠に待ち続けるかもしれない。
- ロックを使用したプログラミングはデッドロックなどのバグを作りこみやすい。
- 優先順位の逆転。低優先度のスレッド/プロセスがロックを獲得しているために高優先度のスレッド/プロセスがブロックされるという現象が発生する。
- あるスレッドがロックを獲得した状態でタイムスライスを使い切るとかページフォールトなどで状態が変化すると、ロック確保期間が長期化して他のスレッドが待たされる。
- デバッグが困難。ロックに関わるバグは時系列のイベントに左右されるため、再現させるのが難しい。
ロックを避ける戦略としてブロックしない同期手法を使うことがあげられる。例えば、lock-freeプログラミング技法やtransactional memoryなどがある。
[編集] C# の lock
C#言語には、lock という予約語があり、他のスレッドに邪魔されずに実行可能なコードブロックを定義する。Java言語の予約語 synchronize と似ている。
