Wikipedia

ロック (計算機科学)

（ロック (情報工学)から転送）

計算機科学におけるロック (英: lock) とは、計算機システム内に複数の動作主体（プロセスやスレッドなど）のある環境で、データやデバイスなどの計算資源（リソース）へのアクセス制限を課す同期機構。ロックは並行性制御ポリシーを実施する手法のひとつである。アクセス制限を課す動作を「ロックする」、「ロックを取得する」などと表現する。また対義語として、制限を解除することをアンロック（英: unlock）という（ロック解放、ロック解除とも）。

概要編集

ロックは、複数の動作主体が同一のリソースに対して状態を変更する動作を行うとき、不整合な状態が起こらないように制御する並行性制御において用いられる手法の一つである。ある動作主体がロックしたリソースへは、基本的には他の主体による利用は妨げられる。実際には、完全に利用をさせないロックは性能低下が著しいため、複数の主体が取得可能なロックや、他者の読み出しのみ許可するなど、複数のモード（レベル）のロックを用意し必要に応じて使い分ける。

一言でロックといった場合でも、他主体の動作を妨げる基本的機能だけを指す場合、妨げられた主体の待ち動作を含む場合とさまざまである。

動作主体としてプロセスの場合、プロセス間ロック機構がOSによって提供される。スレッドであれば、スレッドライブラリやスレッドを制御するスレッド機構により提供される。動作主体がトランザクションであれば、トランザクションモニターにより提供される。あるいは、リソースがファイルであればファイルロックとなる。

スレッドにおけるロック編集

種類編集

スレッドの場合、関連付けられたデータにアクセスする前にロックを獲得するよう各スレッドが協力するものであって、ロックに強制力はない（これを助言ロック; 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つロックしなければならないときなどはデッドロックに注意しなければならない）。

言語によっては構文規則上ロックをサポートしていることもある。C#での例を以下に示す。 

/// <summary>
/// 口座のモニター。
/// </summary>
class Account {
  long val = 0;
  readonly object thisLock = new object();
  public void Deposit(long x) {
    // 一度に1スレッドしか、このブロックを実行できない。
    lock (thisLock) {
      val += x;
    }
  }

  public void Withdraw(long x) {
    // 一度に1スレッドしか、このブロックを実行できない。
    lock (thisLock) {
      val -= x;
    }
  }
}

lock (this) は、そのインスタンスにパブリックにアクセスできる場合、問題を生じる[1]。

Javaと同様、C#もメソッド全体を同期させることができ、MethodImplOptions.Synchronizedという属性を使用する[2][3]。 

[MethodImpl(MethodImplOptions.Synchronized)]
public void SomeMethod() {
    // 何かを実行する。
}

粒度編集

ロックの粒度 (Granularity) を説明する前に、ロックに関する3つのコンセプトを説明する。

ロックのオーバヘッド
ロックそのものに要するメモリ領域などの追加のリソース、ロックの初期化などにかかるCPU時間、ロック操作にかかるCPU時間など。プログラムがロックを多数使えば使うほど、オーバヘッドも大きくなる。
ロックの競合
他のプロセスやスレッドが獲得しているロックを獲得しようとすることをロックの競合という。ロックを細分化すれば、プロセス/スレッド間で競合が発生する可能性は小さくなる。例えば、配列全体ではなく行単位、あるいは要素単位にロックするといったことである。
デッドロック
上述の問題。何らかの処置をしないと複数のタスクがずっと待ち続けることになる。

従って、同期のためのロックの数を決定する際に、ロックのオーバヘッドとロックの競合がトレードオフの関係にある。

ロックの重要な特性として粒度 (Granularity) がある。粒度とは、ロックが保護するデータの大きさである。一般に粗い粒度（ロック数が少なく、各ロックが大きなデータ領域を保護する）ではロックのオーバヘッドは小さいが、複数プロセスが並行動作するときの性能は低下する。これは粗い粒度ではロックの競合が発生し易いためで、ロックによってプロセスがブロックされる確率が非常に高くなる。反対に細かい粒度（ロック数が多く、各ロックが非常に小さなデータを保護する）ではロック自体のオーバヘッドは増大するが、ロックの競合は低減する。また、ロック数を増やすとデッドロックの危険性が増す。

データベース管理システムでは、ロックは粒度によって、レコード単位、データページ単位、テーブル全体などを保護対象とする。テーブル全体などの粗い粒度のロックはシングルユーザーで性能向上させるのに有利であり、レコード単位などの細かい粒度のロックは複数ユーザーでの性能向上に有利である。

データベースのロック編集

データベースでは、ロックはトランザクションの同時性を保証する手段として使うことが出来る。すなわち、トランザクション処理が並行して行われるとき（インタリービング式トランザクション）、ツーフェーズロックを使ってトランザクションの並行実行が直列化されたトランザクションと等価であることを保証する。しかし、データベース内のロックの副作用としてデッドロックが発生することがある。デッドロックはロック順序を事前に定義しておくことで防いだり、待ち状態グラフ（英語版）を使って検出したりする。データベースの一貫性のためにロックを使う以外の手段として、完全に順序が決定されるグローバルなタイムスタンプを使用することでデッドロックを防ぐこともある。

データベース上の複数のユーザーの同時並行的要求に対応するための機構があり、更新をしそこなったり不正な情報を読み取らせることを防ぐことを目的としている。この場合のロックは悲観的ロックと楽観的ロックに分けられる。

悲観的ロック (Pessimistic locking)
あるユーザーがあるレコードを読み、それを更新しようとして、そのレコードに排他ロックを置き、他のユーザーがそのレコードを操作することを防ぐ。すなわち、他のユーザーはそのロックが解放されるまで当該レコードを操作することができない。この方式には排他が長時間にわたるという欠点があり、システム全体の応答性が悪くなる。
データの競合が激しい環境で主に使用する。ロックによってデータを保護することによるコストが、衝突が起きてトランザクションをロールバックするコストより低い場合である。ロックをかけている時間は短いほどよい。
楽観的ロック (Optimistic locking)
複数のユーザーが同時にデータベースにアクセスしたとき、各ユーザーは最初に読み取ったレコード内容のコピーを保持する。あるユーザーがそのレコードを更新しようとしたとき、そのレコードを読み取ってから更新しようとするまでの間に他のユーザーがそのレコードを更新しなかったかどうかを調べる。もし他者によって更新されていたら、今回の更新要求は無視されエラーが返され、更新のやり直しを促される。ロックの必要な区間が短いので、データベースの性能が向上する。更新することが少ないデータベースでは効率的である。更新が同時に要求されることが多いと頻繁に更新が失敗するという欠点がある。
データの競合が少ない環境に適している。.NET では、長期間ロックを保持するのが現実的でないモバイルアプリケーションなどでこの戦略をよく使っている[4]。レコードロックを保持している間はデータベースサーバとのコネクションを維持する必要があるが、モバイル環境ではそれを保証できないためである。

ロックにまつわる問題編集

ロックによるリソース保護とスレッド/プロセスの同期には以下のような問題がある:

  • ブロックする方法であるため、スレッド/プロセスは他が確保しているロックが解放されるのを待たなければならない。
  • ロックは保守的な手法である。何故なら、スレッドは競合が発生すると予想される場合には常にロックを確保しなければならず、実際には競合が発生することは滅多にない。保守的手法であるがゆえに不必要なオーバヘッドが生じる。
  • ロックは故障や障害に無防備である。あるスレッドがロックを獲得したまま終了すると、他のスレッドはそのロックを獲得しようとして永遠に待ち続けるかもしれない。
  • ロックを使用したプログラミングはデッドロックなどのバグを作りこみやすい。
  • 優先順位の逆転。低優先度のスレッド/プロセスがロックを獲得しているために高優先度のスレッド/プロセスがブロックされるという現象が発生する。
  • あるスレッドがロックを獲得した状態でタイムスライスを使い切るとかページフォールトなどで状態が変化すると、ロック確保期間が長期化して他のスレッドが待たされる。
  • デバッグが困難。ロックに関わるバグは時系列のイベントに左右されるため、再現させるのが難しい。
  • ロック機構が正しく機能するにはその状態を保持できるだけのリソースが確保されている必要がある。リソースが確保できない場合、クラッシュするよりは失敗するほうがよいが、例えばロック機構が「（何らかの理由で）ロックを獲得できませんでした」とエラーを返してくる可能性があるなら、アプリケーションはその状況にうまく対処できなければならない。そのためにはアプリケーションの論理設計の段階から考慮する必要がある。

ロックを避ける並行性制御戦略としてブロックしない同期手法を使うことがあげられる。例えば、lock-freeプログラミング技法やトランザクショナルメモリなどがある。しかし、そういった技法を使ったとしてもロックにまつわる問題を全て完全に回避できるわけではない。

どんな並行性制御戦略でも、OSのより基礎的なレベルでの実際のロック機構の実装を必要とし、単にアプリケーションのレベルで実装の詳細をロックを必要としないように見せているだけである。「問題」は依然として存在するが、それを扱うのはアプリケーションではない。実際、ロック機構は最終的にはCPUハードウェアの提供する不可分操作技法に依存している。

言語サポート編集

「バリア (計算機科学)」も参照

プラットフォーム（OS）やプログラミング言語によっては、様々なロックをサポートしている。

  • POSIXスレッドAPIはロックサポートを提供する[5]。Microsoft WindowsはWindows APIによってスレッド間およびプロセス間のロックサポートを提供する。
  • CとC++はプラットフォーム（OS）固有のロック機能やAPIに容易にアクセス可能であるが、C99までのISO/IEC標準では、スレッドや排他制御のための標準APIは存在しなかった。C11以降はPOSIXスレッドベースのスレッドライブラリを標準化したが、必須ではなくオプション扱いである。C++03までのISO/IEC標準でも、同様にスレッドを標準サポートしていなかったが、C++11以降はBoost C++ライブラリをベースに標準化されたスレッディング機能をサポートしている。OpenMP標準は一部コンパイラがサポートしており、プラグマを使ってクリティカルセクションを指定できる。Visual C++ ではコードに synchronize 属性を付与でき、同期しなければならないメソッドを指定できるが、Windowsアーキテクチャと Visual C++ コンパイラにおける「COMオブジェクト」固有である[6]。
  • Java は synchronized という修飾子を提供しており、コードのブロックであるメソッドまたはオブジェクトに対してロックを配置でき[7]、並行性セーフなデータ構造を特徴とするライブラリも提供している。
  • C#言語には、lock という予約語があり、他のスレッドに邪魔されずに実行可能なコードブロックを定義する。
  • VB.NET では SyncLock という予約語があり、C# の lock とほぼ同様である。
  • Python にはそのような予約語はないが、ロックの取得・解放のための低レベルな排他制御機構を使用可能である。[8]
  • Ruby も同期のための予約語を提供していないが、低レベル排他制御オブジェクトを明示的に使用することは可能である。[9]
  • x86のアセンブリ言語では、LOCK というプレフィックスを配することで不可分操作であることを保証でき、他のプロセッサが途中で干渉してくるのを避けることができる。
  • Objective-C では "@synchronized" という予約語[10]でコードブロックにロックを配することができ、また NSLock[11]、NSRecursiveLock[12]、NSConditionLock[13]というクラスや NSLocking[14] というロック用プロトコルも提供している。

脚注編集

  1. ^ “lock Statement (C# Reference)”. 2012-0712閲覧。
  2. ^ “ThreadPoolPriority, and MethodImplAttribute”. MSDN. p. ??. 2011年11月22日閲覧。
  3. ^ “C# From a Java Developer's Perspective”. 2011年11月22日閲覧。
  4. ^ “Designing Data Tier Components and Passing Data Through Tiers”. Microsoft (2002年8月). 2008年5月30日閲覧。
  5. ^ Marshall, Dave (1999年3月). “Mutual Exclusion Locks”. 2008年5月30日閲覧。
  6. ^ “Synchronize”. msdn.microsoft.com. 2008年5月30日閲覧。
  7. ^ “Synchronization”. Sun Microsystems. 2008年5月30日閲覧。
  8. ^ Lundh, Fredrik (2007年7月). “Thread Synchronization Mechanisms in Python”. 2008年5月30日閲覧。
  9. ^ “Programming Ruby: Threads and Processes” (2001年). 2008年5月30日閲覧。
  10. ^ “Apple Threading Reference”. Apple, inc. 2009年10月17日閲覧。
  11. ^ “NSLock Reference”. Apple, inc. 2009年10月17日閲覧。
  12. ^ “NSRecursiveLock Reference”. Apple, inc. 2009年10月17日閲覧。
  13. ^ “NSConditionLock Reference”. Apple, inc. 2009年10月17日閲覧。
  14. ^ “NSLocking Protocol Reference”. Apple, inc. 2009年10月17日閲覧。

関連項目編集

外部リンク編集

「https://ja.wikipedia.org/w/index.php?title=ロック_(計算機科学)&oldid=85756804」から取得