アトミック変数とノンブロッキング同期化

1時半就寝、7時40分起床。

CAS (Compare And Swap)

これは前に読んだ記憶があるぞ。Atomicクラスの実装に使われている手法だったような。
アトミックなread-modify-writeをロックを使わずに実装したい場合、CASで実現可能。実行性能はロックよりも良好。
CASの基本的な態度としては、「とにかくやってみて、失敗したら再度挑戦する」。ある値を更新する際、その値が予想通りの値なら処理を続行して更新を行い、異なればすぐにリトライする。

public class CasCounter {

	private SimulateCAS value;

	public int get() {
		return value.get();
	}

	public int increment() {
		int v;
		do {
			v = value.get();
		} while (v != value.compareAndSwap(v, v + 1));
		return v + 1;
	}

	private static class SimulateCAS {
		private int value;

		public synchronized int get() {
			return value;
		}

		public synchronized int compareAndSwap(int expectedValue, int newValue) {
			int oldValue = value;
			// 予想通りなら入れ替え
			if (oldValue == expectedValue) {
				value = newValue;
			}
			return oldValue;
		}

	}

}

パフォーマンスは実際のCASと異なるが、おおよそこのような処理を行っている。
このように実装は複雑なので、実行性能は良好だが実際にはパフォーマンスが気になる箇所でのみ使う感じになるのかな。

ノンブロッキング・アルゴリズム

ロックを使うアルゴリズムは、生存事故の危険性を持つ。ロックを持っているスレッドがエラーを起こしたり遅延すると、他のスレッドも前進出来なくなる可能性がある。
スレッドのエラーや中断が他のスレッドのエラーや中断を起こさないなら、そのアルゴリズムを「ノンブロッキング」と呼ぶ。CASを使えばノンブロッキング・アルゴリズムにすることが出来る。