Java 並行プログラミング（6）｜並行処理の応用：CAS、ロックのエスカレーション


並行処理の応用

  • はじめに
  • 一般的なロック戦略
    • [楽観ロック VS 悲観ロック](#楽観ロック VS 悲観ロック)
    • [ヘビーウェイトロック VS ライトウェイトロック](#ヘビーウェイトロック VS ライトウェイトロック)
    • [スピンロック VS サスペンド・アンド・ウェイトロック](#スピンロック VS サスペンド・アンド・ウェイトロック)
    • 読み書きロック
    • [再入可能ロック VS 再入不可能ロック](#再入可能ロック VS 再入不可能ロック)
    • [フェアロック VS 非フェアロック](#フェアロック VS 非フェアロック)
    • [synchronized ロックの戦略](#synchronized ロックの戦略)
  • CAS
    • CASの理解
    • CASの応用
      • アトミッククラスの実装
      • スピンロックの実装
    • CASのABA問題
  • [synchronizedの原理](#synchronizedの原理)
    • ロックのエスカレーション
    • ロックの解消
    • ロックの粗化
  • まとめ
  • [? シリーズ記事ナビゲーション](#? シリーズ記事ナビゲーション)

はじめに

本記事は、前回の『4大並行処理の実践：シングルトン、ブロッキングキュー、タイマー、スレッドプール』に続き、Javaの並行処理における低レベルのロックメカニズムとロックレスCASプログラミングを深く掘り下げます。面接で必ず問われる各種ロックの区別、CASの原子操作、synchronizedの3大最適化（ロックの昇格／ 排除／粗化）を網羅し、すべてに擬似コードと実行可能な実践例を添えて、基盤となる原理や面接の核心となる出題ポイントを徹底的に理解できるようにしています。

一般的なロック戦略

楽観ロック VS 悲観ロック

これは「ロックの一つの特性」です。

ここでの「悲観」と「楽観」は、その後のロック競合が激しくなるかどうかに対する予測を指します。

  1. 楽観ロック：今後のロック競合の確率が低いと予測されるため、処理を最小限に抑えることができます。
  2. 悲観ロック：今後のロック競合の確率が高いと予測されるため、より多くの処理を行う必要があります。

ヘビーウェイトロック VS ライトウェイトロック

  1. ヘビーウェイトロック：ロックのオーバーヘッドが比較的大きい。
  2. ライトウェイトロック：ロックのオーバーヘッドが比較的小さい。

楽観ロックは通常、ライトウェイトロックであり、悲観ロックは通常、ヘビーウェイトロックである。

スピンロック VS サスペンド・アンド・ウェイトロック

  1. スピンロック：軽量ロックの典型的な実装の一つ。
    （1）多くの場合、純粋なユーザーモードで実装される。
    （2）例えば、whileループ内で、現在のロックが解放されたかどうかを絶えずチェックし、解放されていなければループを継続する。解放されればロックを取得し、ループを終了する。ビジー待ちであり、CPUを消費するが、その代わりに応答速度が向上する。
  2. サスペンド・アンド・ウェイト・ロック：ヘビーウェイト・ロックの典型的な実装です。
    （1）システムAPIを利用して実装する必要があります。
    （2）ロック競合が発生すると、カーネル内で一連の処理がトリガーされます。例えば、そのスレッドをブロック状態にさせ、一時的にCPUスケジューリングから除外します。ブロックによるオーバーヘッドは大きいです。

読み書きロック

読み書きロックは、ロックを「読み取りロック」と「書き込みロック」の2種類に分類する

  1. 読み取りロック：読み取り時には、読み取りは可能だが、書き込みはできない。
  2. 書き込みロック：書き込み時には、読み取りも書き込みもできない。
  3. 2つのスレッドがロックを取得する過程：
    （1）読み取りロック同士の間では、競合は発生しない；
    （2）読み取りロックと書き込みロックの間では、競合が発生する；
    （3）書き込みロック同士の間では、競合が発生する。

再入可能ロック VS 再入不可能ロック

  1. 再入可能ロック：1つのスレッドが同一のロックに対して連続して2回ロックを取得しても、デッドロックは発生しない。
  2. 再入不可ロック：1つのスレッドが同一のロックに対して連続して2回ロックを取得すると、デッドロックが発生する。

フェアロック VS 非フェアロック

多くのスレッドが同一のロックを取得しようとした場合、あるスレッドがロックを取得すると、他のスレッドはブロックされて待機することになる。最初のスレッドがロックを解放した後、次にどのスレッドがロックを取得できるだろうか？

  1. フェアロック：先着順。
  2. 非フェアロック：残りのスレッドは均等な確率でロックを再競合する。

OSが提供するロックAPIは、デフォルトで非フェアロックである。

synchronized ロックの戦略

  1. 楽観ロック VS 悲観ロック：適応型；
  2. 軽量ロック VS 重量級ロック：適応型；
  3. スピンロック VS サスペンド待ちロック：適応型。
  4. 適応型：
    （1）初期状態では、synchronizedは現在のロック競合の確率が低いと予測し、この時は楽観的ロックモードで動作する（軽量ロック、スピンロック方式で実装）
    （2）実際の使用中にロック競合が頻繁に発生することが判明した場合、synchronizedは悲観的ロック（重量級ロック、サスペンド・アンド・ウェイト方式で実装）にアップグレードされる
  5. 読み書きロックではなく、再入可能ロックであり、非公平ロックです

CAS

CASについて

  1. CAS（Compare and swap）：比較・交換の対象はメモリとレジスタです。
  2. 例えば、メモリMと2つのレジスタA、Bがあるとします
  3. CAS(M,A,B)：MとAの値が同じ場合、MとBの値を交換し、同時に操作全体がtrueを返します。そうでない場合は何も起こらず、操作全体がfalseを返します。交換の本質は、Bの値をMに代入することです。
  4. CASは実際にはCPU命令の一つです。個々のCPU命令はアトミックであるため、CASを使用して一部の操作を実行し、さらにロックを代替することができます。
  5. CASに基づいてスレッドセーフを実現する方法は「ロックフリープログラミング」と呼ばれます。

CASの応用

アトミッククラスの実装

public class Demo {

public static AtomicInteger count=new AtomicInteger(0);

public static void main(String[] args) throws InterruptedException {
// TODO 自動生成されたメソッドのスタブ
Thread t1=new Thread(()->{
for(int i=0;i<50000;i++) {
count.getAndIncrement(); // count++
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 50000; i++) {
count.getAndIncrement();
}
});
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(count.get());
}

}

アトミッククラスはCASに基づいて実装されています。

擬似コードによる実装：

class AtomicInteger {
 private int value;
 public int getAndIncrement() { 
     int oldValue = value;
  	
while ( CAS(value, oldValue, oldValue+1) != true) { //ここでの判定は、他のスレッドが割り込んできたかどうかを確認するものです
         oldValue = value; 
     } 
     return oldValue;
 }
}

ロックはブロッキング方式で割り込み実行を回避し、CASは再試行方式で実行を回避します

スピンロックの実装

疑似コード：

public class SpinLock {
 private Thread owner = null;
 public void lock(){
 // CAS を使用して、現在のロックがどのスレッドによって保持されているかを確認する。 
 // このロックが他のスレッドによって保持されている場合、スピン待ちを行う。
 
// このロックが他のスレッドによって保持されていない場合は、ownerを現在ロックを試みているスレッドに設定する。 
 while(!CAS(this.owner,null,Thread.currentThread())){ 
     } 
 }
 public void unlock (){ 
     this.owner = null; 
 }
}

CASのABA問題

CAS操作の鍵：「値に変化がない」ことを「他のスレッドが割り込んで実行されていない」という判定基準とするが、この判定方法は厳密ではなく、極端な場合、別のスレッドが割り込んで、値がA→B→Aとなる可能性がある。最初のスレッドにとっては値は変わっていないように見えるが、実際には割り込み実行が起きていたことになる。

解決策：

  1. 判定対象の値を一定の方向にのみ増加させ、増減を繰り返さないようにする（増減があるとABAが発生する）。
  2. 追加の変数（バージョン番号）を導入し、変更のたびにバージョン番号を1ずつインクリメントするように規定します。これにより、CASによる判定では値そのものではなくバージョン番号を判定対象とし、バージョン番号が変化したかどうかを確認します。バージョン番号が変わっていなければ、スレッドが割り込んで実行されていないことを意味します。

synchronizedの原理

ロックのエスカレーション

synchronizedの状態変化：ロックなし -> バイアスロック -> スピンロック（軽量ロック） -> ヘビーウェイトロック。

  1. ロックのエスカレーションは一方向であり、降格することはできない。
  2. バイアスロック：真のロックではなく、単なるマーキングであり、完全に実行時の最適化戦略です。ロック競合が発生すると、バイアスロックは軽量ロックにエスカレートし、そこで初めて真のロックがかけられます。
  3. ロックのエスカレーションプロセスは、パフォーマンスとスレッドセーフティの間で可能な限りバランスを取るものです。

ロックの除去

  1. コンパイラは、記述されたロック付きコードに対して自動的に判定を行い、そのシナリオでロックが不要であると判断した場合、記述されたsynchronizedを最適化して削除します。
  2. 例：StringBuilderにはsynchronizedが含まれていませんが、StringBufferにはsynchronizedが含まれています；
    synchronizedを記述しても、必ずしもスレッドセーフになるとは限りません；
    単一スレッド内でStringBufferを使用する場合、コンパイラはsynchronizedを最適化して削除します；
  3. コンパイラは、非常に確信がある場合にのみロック除去を行います
  4. ロック除去：コンパイル時のロック除去；実行時のロック除去。
  5. ロックを保守的に保持：synchronizedロックに対するコンパイラの処理戦略。
  6. 要点：コンパイル時には実行時のスレッド競合状況を予測できないため、プログラムの正しさを保証するために、コードロジックを勝手に削除・変更することはなく、ロックのセマンティクスをバイトコードに完全に保持する

ロックの粒度粗化

ロックの粒度：synchronized内において、コードが少なければ少ないほどロックの粒度は粗いとみなされ、コードが多ければ多いほどロックの粒度は細かいとされる。

for(...) {
sync(lock){
n++ ;
} //ロックの粒度が細かい
}
 
sync(lock){
for(...) {
n++ ;
} //ロックの粒度が粗い
}

ロックの粒度が細かい場合、並行して実行できるロジックが多くなり、CPUリソースを十分に活用しやすくなります。

粒度の細かいロックが繰り返しロック・アンロックされる場合、実際には粒度の粗いロックよりも効果が劣る可能性があります（頻繁なロック競合が発生するため）。

全文のまとめ

本記事では、並行処理の基盤となる核心的な面接対策ポイントを網羅的に解説しています：

  1. 6種類のロック戦略の区別、および各ロックが適用されるビジネスシナリオの把握；
  2. CAS（ロックレスプログラミング）の低レベルCPU命令の原理、アトミッククラスの実践、スピンロックの自作、およびABA問題の解決策；
  3. synchronizedの低レベルにおける3大最適化：一方向ロックのアップグレード、コンパイル時のロック除去、ロックの粗化、JVMのロック性能最適化ロジックの理解。

今後、JUC ユーティリティクラスやスレッドセーフなコレクションに関する実践的なコンテンツを順次更新予定です。ぜひ「いいね」や「ブックマーク」をお願いします。コメント欄で面接対策や学習の感想を共有しましょう！

? シリーズ記事ナビゲーション

本記事は「Java 並行プログラミングシリーズ」の連載記事です。リンクをクリックしてシリーズ全編をご覧ください：

? 前の記事：Java 並行プログラミング（5）｜4大並行処理の実践：シングルトン、ブロッキングキュー、タイマー、スレッドプール

? 「Java 並行プログラミング」コラム集へ直接アクセス