lock-freeプログラミングとCASとは何ですか。ABA問題と、それをいつ使うべきかを説明してください。

Question

IT Interview Practice · Accepted Answer

**lock-freeプログラミングは、mutexを使わずにスレッドを協調させます。atomicなcompare-and-swap（CAS）ループを用いることで、他のスレッドが止まっても常に少なくとも1つのスレッドが前進します。** どのスレッドも、ロックを保持する別のスレッドによってブロックされることがありません。

## CAS

**compare-and-swap**は、ある場所が依然として期待どおりの古い値を保持している場合にのみ、その場所を新しい値に原子的に設定します。そうでなければ失敗し、リトライします。これはlock-freeなスタック、キュー、カウンタの背後にあるプリミティブです。

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, indivisible
  else: return false
```

```java
// Lock-free increment via CAS retry loop
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // retry if someone else won
```

## ABA問題

CASは値が依然として期待どおりであることだけを確認し、値が一度も変わらなかったことは確認しません。読み取りとCASのあいだに値がA → B → Aと変化していた場合、CASは成功しますが、足元では世界が動いています（例: 解放されて再利用されたノード）。

```text
Thread 1: read A ............... CAS(A→X) succeeds ✗ (but list changed!)
Thread 2:      pop A, push B, push A again
```

**対処**: ポインタをバージョンカウンタ（`AtomicStampedReference`、タグ付きポインタ）と組み合わせ、A-with-tag-1 ≠ A-with-tag-2となるようにするか、メモリ安全性のためにhazard pointerやepoch reclamationを使います。

## いつ使うか

- ロック競合が支配的な、ホットで細粒度の共有状態（カウンタ、single-producerキュー）や、スレッドが決してブロックしてはならない場面（リアルタイム、シグナルハンドラ）では**使う**。
- 既定としては**避ける**: 正しく作るのが難しく、ABAやメモリ順序のバグを入れ込みやすく、競合が低い状況では良いmutexと比べて速くないことも多いです。

## なぜ重要なのか

lock-freeな構造は前進の保証を与え、デッドロックや優先度逆転を避けますが、正しさのハードルは高いです。CAS、ABA、そして回収（reclamation）の問題を知っていることは、あなたがメモリモデルのレベルで考えられること、そして何より、それに手を伸ばす*べきでない*ときを知っていることを示します。

CAS

ABA問題

いつ使うか

なぜ重要なのか

関連する質問