メインコンテンツまでスキップ

JUC 復習（その二）ロックを知る

· 約11分
tanzhuo

ロックは並行プログラミングにおいて避けて通れないテーマです。今回はフェアロックや読み書きロックから CAS、AQS まで、代表的なロックの概念をまとめて振り返ります。JUC 復習シリーズの第 2 回です。

ロックの基本概念​

ロック機構によって、マルチスレッド環境において同一の時間・空間内でクリティカルセクションのコードに入れるスレッドを 1 つに限定でき、クリティカルセクション内で操作されるデータの一貫性が保証されます。

代表的なロック​

1) フェアロック​

特定のスレッドが飢餓状態に陥ること、つまり CPU タイムスライスが割り当てられずに命令をいつまでも実行できなくなることを防ぎます。公平性を保証するにはスレッドの状態を追加で管理する必要があり、スレッドのコンテキストスイッチが増えてオーバーヘッドが大きくなり、スループットは低下します。ReentrantLock は初期化パラメータでフェアロックに設定できますが、Synchronized はデフォルトで非フェアロックであり、フェアロックに変更することはできません。

2) 非フェアロック​

計算リソースを直接奪い合うため、スレッドの飢餓が発生しやすくなります。その一方でスループットは高く、スレッドの切り替えも頻繁ではありません。先に CPU タイムスライスを獲得したスレッドが実行されます。

3) リエントラントロック​

再帰ロックとも呼ばれ、すでに取得済みのロックオブジェクトを再度取得でき、ある程度デッドロックを回避できます。ReentrantLock と Synchronized はどちらもリエントラントロックです。

4) 非リエントラントロック​

スレッドが実行中にロックを取得した後、同期ブロック内で同じロックを再度取得しようとするとデッドロックになります。非リエントラントロックは同期ブロック内で 1 回しか取得できません。

5) ミューテックスロック（相互排他ロック）​

あるスレッドがリソースを占有している間、他のスレッドはサスペンドされ、CPU リソースを消費しません。ロックが解放されると、CPU がサスペンド中のスレッドをスケジューリングします。高頻度で操作されないリソースに適しており、そうでない場合はスレッドの頻繁なスケジューリングにより効率が低下します。

6) 読み書きロック​

ReentrantReadWriteLock 読み書きロックは、読み取りロックと書き込みロックの 2 つの部分で構成され、読み取りロックと書き込みロックは互いに排他的です。共有リソースを読み取るだけなら読み取りロックを、共有リソースを変更する必要があるなら書き込みロックを使います。読み取りが多く書き込みが少ないシナリオに適しています。書き込みロックがどのスレッドにも保持されていない場合、複数のスレッドが読み取りロックを並行して保持できますが、書き込みロックがスレッドに保持されると、他のスレッドによる読み取りロック・書き込みロックの取得操作はすべてブロックされます。

**書き込み優先：**書き込みスレッドが書き込みロックを取得し続けると、読み取りスレッドが「飢餓」に陥ります。

**読み取り優先：**読み取りスレッドが読み取りロックを取得し続けると、書き込みスレッドは永遠にロックを取得できず、書き込みスレッドが「飢餓」に陥ります。

7) フェア読み書きロック​

フェア読み書きロックの比較的シンプルな実現方法は、ロックを取得するスレッドをキューで並ばせることです。書き込みスレッドか読み取りスレッドかを問わず、先入れ先出しの原則に従ってロックを取得させます。これにより読み取りスレッドは引き続き並行実行でき、「飢餓」現象をある程度緩和できます。

8) スタンプ付きロック​

StampedLock は ReentrantReadWriteLock よりも高速なロックで、楽観的読み取り、悲観的読み取りロック、書き込みロックをサポートします。ReentrantReadWriteLock と異なり、StampedLock は複数のスレッドが楽観的読み取りを申請している最中でも、1 つのスレッドによる書き込みロックの申請を許可します。

並行同期を捉える視点​

以下の「ロック」は具体的なロック実装ではなく、並行同期を捉える視点、あるいはロックの状態を表すものです。

1) 楽観的ロック​

バージョン番号や CAS アルゴリズムで実現でき、競合の発生確率が低いことを前提とします。その動作方式は、リソースを変更する際に自分だけが変更していると仮定し、変更完了後に検証を行い、問題があれば再度変更するというものです。なお「ロック」と呼ばれてはいますが、楽観的ロックは一切ロックをかけないため、ロックフリープログラミングとも呼ばれます。

2) 悲観的ロック​

複数のスレッドがリソースを変更することを前提とし、変更のたびにロックをかけます。一般にデータベース自体のロック機構は悲観的ロックの仕組みをベースに実装されています。

3) セグメントロック​

セグメントロックの設計目的は、ロックの操作粒度を細かくすることです。たとえば配列全体を更新する必要がなく、配列内の 1 要素だけを更新する場合は、その要素にだけロックをかければ十分です。JDK1.7 の ConcurrentHashMap はセグメントロックの形で並行操作を実現しており、Segment に対してロックをかけることでより高い並行効率を達成していましたが、JDK1.8 では CAS アルゴリズムに置き換えられました。

4) バイアスロック​

ある同期コードが常に 1 つのスレッドからのみアクセスされる場合、そのスレッドが自動的にロックを取得するようにして、ロック取得のコストを下げる仕組みです。

5) 軽量ロック​

現在のロックがバイアスロックの状態で別のスレッドからアクセスされると、バイアスロックは軽量ロックに昇格します。他のスレッドはスピンによってロックの取得を試み、ブロックされることはありません。

6) 重量ロック​

現在のロックが軽量ロックの状態で、別のスレッドが一定回数スピンしてもロックを取得できない場合、軽量ロックは重量ロックに昇格し、他のスレッドをブロックします。

7) スピンロック​

ロックを取得しようとするスレッドがすぐにはブロックされず、ループしながらロックの取得を試みる方式です。ただし CPU リソースをより多く消費します。つまり空回りし続けるわけです。通常はスピン回数を設定し、指定回数に達するとスレッドをサスペンドします。

8) デッドロック​

デッドロックはロックの一種ではなく、現象です。実行中の 2 つのスレッドが、互いに相手が保持しているロックを取得しなければ命令を続行できない状態になると、デッドロックが発生します。プログラムがフリーズし、処理を先に進められなくなります。デッドロックは jstack コマンドで調査できます。まず jps -l コマンドでアプリケーションの pid（プロセス番号）を取得し、次に jstack <プロセス番号> でデッドロックを調査します。また jconsole コマンドで UI ツールを開いてデッドロック情報を確認することもできます。

CAS アルゴリズムとは​

CAS は Compare And Swap の略で、その名のとおり比較と交換を意味します。このアルゴリズムはロックフリーアルゴリズムの一種で、ロックをかけずにスレッドセーフを保証できます。つまりスレッドをブロックすることなく変数の同期を実現するため、ノンブロッキング同期の範疇に属します。

CAS アルゴリズムには 3 つのオペランドが関わります。メモリ値 V、比較値 A、交換値 B です。具体的な操作手順は、V が A と等しい場合に限り、CAS アルゴリズムがアトミックに B で V を置き換え、そうでなければ何も実行しない、というものです。一般に CAS アルゴリズムはスピン操作であり、成功するまで繰り返しリトライします。

CAS アルゴリズムには次の特徴があります。ABA 問題、スピンによるオーバーヘッド、単一の共有変数に対するアトミック操作しか保証しないこと、です。

  • ABA 問題。変数 V を最初に読み取ったときの値が A で、代入直前の確認でも A のままだったとしても、他のスレッドに変更されていないとは言い切れません。その間に別の値に変更され、その後 A に戻された可能性があるからです。この場合、CAS アルゴリズムは一度も変更されていないと誤認してしまいます。これが CAS アルゴリズムの ABA 問題と呼ばれるものです。実際の利用シーンでは判断が必要で、ABA 問題の影響が小さいシーンでは対処しなくても構いません。そうでなければ、変更のたびにバージョン番号を付与する方式で ABA 問題を解決するか、あるいは悲観的ロックを採用します。
  • スピンによるオーバーヘッド。前述のとおり、CAS アルゴリズムはスピン操作であり、壁にぶつかっても引き返さない精神で、失敗すると成功するまでリトライし続けます。しかしこのスピンが長時間続くと CPU に大きな負担がかかります。これがいわゆるスピンのオーバーヘッドです。
  • 単一の共有変数に対するアトミック操作しか保証しないこと。CAS アルゴリズムは単一の共有変数に対してのみ有効で、複数の共有変数にまたがる操作では同期を保証できません。解決方法の一つは、それらの共有変数を 1 つのオブジェクトにまとめてから CAS アルゴリズムで処理することです。

低レイヤーのアセンブリ命令は lock cmpxchgl で、このうち lock プレフィックスが特に重要です。その命令の説明は次のとおりです。

1）メモリに対する読み取り・変更・書き込み操作がアトミックに実行されることを保証します。Pentium およびそれ以前のプロセッサでは、lock プレフィックス付きの命令は実行中にバスをロックし、他のプロセッサが一時的にバス経由でメモリにアクセスできなくなります。当然これは高価なオーバーヘッドをもたらします。Pentium 4、Intel Xeon、および P6 プロセッサ以降、Intel は従来のバスロックをベースに非常に意義のある最適化を行いました。lock プレフィックス命令の実行中に、アクセス対象のメモリ領域（area of memory）がすでにプロセッサ内部のキャッシュでロックされており（つまり、そのメモリ領域を含むキャッシュラインが排他状態または変更済み状態にある）、かつそのメモリ領域が単一のキャッシュライン（cache line）内に完全に収まっている場合、プロセッサはその命令を直接実行します。命令の実行中はそのキャッシュラインがロックされ続けるため、他のプロセッサはその命令がアクセスするメモリ領域を読み書きできず、命令実行のアトミック性が保証されます。この操作過程はキャッシュロック（cache locking）と呼ばれ、lock プレフィックス命令の実行コストを大幅に削減します。ただし、マルチプロセッサ間の競合が激しい場合や、命令がアクセスするメモリアドレスがアラインされていない場合は、依然としてバスがロックされます。

2）この命令と、その前後の読み取り・書き込み命令とのリオーダリングを禁止します。

3）ライトバッファ内のすべてのデータをメモリにフラッシュします。

AQS とは​

Abstract Queued Synchronizer（抽象キュー同期器）のことで、JUC 内のすべての Lock インターフェース実装クラスは AQS 抽象クラスをベースに実装されています。

まとめ​

今回は代表的なロックの概念を一度に整理しました。フェア・非フェア、リエントラント・非リエントラントはロックの振る舞いの特性であり、読み書きロックと StampedLock は読み取りが多く書き込みが少ないシナリオ向け、そして楽観的ロック・悲観的ロック、バイアスロックから重量ロックへの昇格は、むしろ並行同期を捉える視点やロックの状態を表すものです。CAS は JUC のロックフリープログラミングの礎であり、その 3 つのオペランドと ABA 問題を理解しておくことは非常に重要です。AQS については、JUC の各種 Lock 実装に共通する骨格であり、その内部実装は別の記事で改めて掘り下げる価値があります。

COMMENTS