ロック (計算機科学)

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

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

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

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

## スレッドにおけるロック
### 種類
スレッドの場合、関連付けられたデータにアクセスする前にロックを獲得するよう各スレッドが協力するものであって、ロックに強制力はない（これを**助言ロック**; **advisory lock** と呼ぶ）。システムによっては**強制ロック** (**mandatory lock**) を実装しており、ロックされたリソースに許可されていないアクセスを行おうとしたときに例外が発生するようになっている。

（2値の）セマフォは最も単純なロックである。共有モード（リードオンリー）か排他モード（リードライト）かは区別されない。他の方法では、複数のスレッドがリードオンリーアクセスのためにロックを共有する共有モードを用意している。共有 (shared)、排他 (exclusive)、削除目的 (intend-to-exclude)、更新目的 (intend-to-upgrade) などのモードが広く実装されている。

以上のようなロックの種類とは別に、ロックによってスレッドの進行が妨げられたときの動作によっても分類できる。多くのロックは、ロックされたリソースへのアクセスが可能となるまで、プロセスの実行をブロックする。スピンロックは単純にロックを獲得できるまでスレッドが待つ（スピンする）。これは待つ期間が短い場合は効果的で、オペレーティングシステムによるプロセスのスケジューリングのオーバーヘッドもかからない。ただし、長時間ロックされたままの場合は非常に無駄である。

### 実装
スレッドにおいてロックはメモリ上の値を用いて実装される。複数のスレッドが同時に値を取得・変更できない必要があるが、これを効率的に実装するため、ロックは一般にハードウェアによるサポートを必要とする。通常、1つ以上のアトミック命令を使用する（「テスト・アンド・セット」、「フェッチ・アンド・アッド」、「コンペア・アンド・スワップ」など）。これらの命令は、プロセスがロックが獲得されていない（フリーである）ことをチェックするとともに、不可分な（アトミックな）処理としてロックを獲得できる。

プロセッサが1つであれば、割り込みを禁止して命令列を実行することで同等の効果が得られる。しかし、マルチプロセッサではこれでは不十分である。マルチプロセッサ環境でロックをサポートすることはハードウェアとソフトウェアの複雑なサポートを要し、同期の主要な課題でもある。

アトミックな操作が必要とされる理由は、並列処理では複数のタスクが同じロジックを同時に実行している可能性があるからである。例えば、以下のC言語のコードを考えてみよう。


```c
if (lock == 0) {
    /* ロックがフリーなのでセットする */
    lock = myPID; 
}
```


複数のタスクが並行して動作可能なら、上記のコードはロックを獲得できるとは言えない。どちらのタスクもロックがフリーであると判断し、どちらもロックに自身のIDをセットして獲得しようとするが、他のタスクも同時にロックを獲得しようとしていることを知らない。アトミックなロック操作ができないときは、デッカーのアルゴリズムやピーターソンのアルゴリズムで代替することもできる。

ロックの不注意な使用によりデッドロックが生じることがある。これはプロセスがあるロックを獲得した状態で別のロックを獲得しようとしたときに発生する。もし2番目のロックが別のプロセスに獲得されていれば、最初のプロセスはブロックされる。2番目のプロセスが最初のプロセスが獲得済みのロックを獲得しようとすると、システムは「デッドロック」状態となり、どちらのプロセスもブロックされたままとなる。これを防ぐための（あるいは回復するための）様々な戦略が設計時や実行時に採用されている。例えば、各ロックが保護するデータの種類によってロックに優先順位を設定し、順位通りでないとロックを獲得できないようにするなどの対処がある（ただし、同じ種類のデータを2つロックしなければならないときなどはデッドロックに注意しなければならない）。

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


```csharp
/// <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;
    }
  }
}
```


Javaのステートメントと同様、C#のステートメントは同じロックオブジェクトを利用するコードブロックに侵入できるスレッドを1つに制限することで、共有リソースへのアクセスを保護する。使用できるロックオブジェクトは任意の参照型のインスタンスだが、デッドロックやロックの競合が発生しないよう、異なる共有リソースに対して同じロックオブジェクトを使用することは避けるべきである。特に、オブジェクトや`System.Type`インスタンスなどはロックに使用すべきではない。なお、ステートメントは、従来は`System.Threading.Monitor`クラスを内部的に使用するコードに展開されていた。.NET Framework 4では潜在的問題回避のために、`Monitor.Enter()`の呼び出し完了直後に例外が発生した場合も`Monitor.Exit()`が確実に呼ばれるコードに展開されるようになった。.NET 9およびC# 13以降は`System.Threading.Lock`型の式をの対象に使った場合、より効率的なコードに展開されるようになる。

Javaにおけるメソッド宣言に対する修飾と同様、C#もメソッド全体を同期させることができ、`MethodImplOptions.Synchronized`という属性を使用する。インスタンスメソッドの場合はインスタンスをロックし、同じインスタンスに対するメソッド呼び出しが排他制御される。メソッドの場合は型をロックし、同じ型に対するメソッド呼び出しが排他制御される。インスタンスメソッドに対するこの属性指定は、メソッドの内容をブロックで囲むことに相当するため、前述の理由からこの属性の使用は避けるべきとされている。


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


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

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

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

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

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

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

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

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

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

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

## 言語サポート

プラットフォーム（OS）やプログラミング言語によっては、様々なロックをサポートしている。
* POSIXスレッドAPIはロックサポートを提供する。POSIXミューテックスは通例スレッド間の排他制御のみに使用され、プロセス間の排他制御のサポートは実装依存だが、POSIXセマフォはスレッド間だけでなくプロセス間の排他制御に使用することもできる。
* Microsoft WindowsはWindows APIによってスレッド間およびプロセス間のロックサポートを提供する。クリティカルセクションオブジェクトやミューテックスオブジェクトなどは同期オブジェクト (synchronization object) と総称されている。
* CとC++はプラットフォーム（OS）固有のロック機能やAPIに容易にアクセス可能であるが、C99までのISO/IEC標準では、スレッドや排他制御のための標準APIは存在しなかった。C11以降はPOSIXスレッドベースのスレッドライブラリを標準化したが、必須ではなくオプション扱いである。C++03までのISO/IEC標準でも、同様にスレッドを標準サポートしていなかったが、C++11以降はBoost C++ライブラリをベースに標準化されたスレッディング機能をサポートしている。なお、C++はデストラクタを利用したRAIIにより、ロックオブジェクトの変数定義を含むコードブロックを脱出する際にロックを確実に解放させることができ、`std::lock_guard`クラスなどに応用されている。これはスレッドが標準化される前、MFCライブラリの`CSingleLock`クラスなどで古くから使われていた技法でもある。
* OpenMP標準は一部のC/C++コンパイラがサポートしており、プラグマディレクティブを使ってクリティカルセクションを指定できる。
* Visual C++ではコードに`synchronize`属性を付与でき、同期しなければならないメソッドを指定できるが、WindowsアーキテクチャとVisual C++コンパイラにおける「COMオブジェクト」固有である。
* Javaはというキーワードを提供しており、メソッドの内部でステートメントに任意のオブジェクトを指定し、任意のコードブロックに対してロックを配置したり、メソッド全体を修飾して大粒度の排他制御を簡潔に記述したりすることができる。Javaクラスライブラリでは、並行性セーフなデータ構造を特徴とする各種クラスも標準提供している。Java 1.5では、より柔軟なロック操作を提供するクラスが追加された。
* C#にはというキーワードがあり、他のスレッドに邪魔されずに実行可能なコードブロックを定義する。
* VB.NETにはというキーワードがあり、C#のとほぼ同様である。
* Python にはそのような予約語はないが、ロックの取得・解放のための低レベルな排他制御機構を使用可能である。
* Ruby も同期のための予約語を提供していないが、低レベル排他制御オブジェクトを明示的に使用することは可能である。
* x86のアセンブリ言語では、LOCK というプレフィックスを配することで不可分操作であることを保証でき、他のプロセッサが途中で干渉してくるのを避けることができる。
* Objective-Cではというディレクティブでコードブロックにロックを配することができ、また NSLock、NSRecursiveLock、NSConditionLockというクラスや NSLocking というロック用プロトコルも提供している。

## 脚注
### 注釈

### 出典

## 関連項目
* 排他制御
* スレッドセーフ
* セマフォ
* モニター (同期)
* ミューテックス
* Lock-freeとWait-freeアルゴリズム
* クリティカルセクション
* ファイルロック
* スピンロック

## 外部リンク
* Tutorial on Locks and Critical Sections Parallel Programming: Understanding the impact of Critical Sections