一般的な鍵の分類

ロックの分類#

再入可能 / 不可再入ロック#

参考リンク: 再入可能ロックとは何か

広義の再入可能ロックは、繰り返し再帰的に呼び出すことができるロックを指し、外側でロックを使用した後、内側でも使用でき、デッドロックが発生しない（前提は同じオブジェクトまたはクラスであること）。
Java ではReentrantLockとsynchronizedはどちらも再入可能ロックであり、違いは次の通りです：

Synchronizedは JVM の実装に依存しているのに対し、ReentrantLockは JDK の実装です。
ReentrantLockは公平ロックか非公平ロックかを指定できますが、Synchronizedは非公平ロックのみです。

ReentrantLock における再入可能ロックの実装#

実装原理: AQS 内で private volatile int state を維持して再入回数をカウントし、頻繁な保持と解放の操作を避けることで、効率を向上させ、デッドロックを回避します。

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    // 実装原理
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // オーバーフロー
            throw new Error("最大ロック数を超えました");
        // setStateはAbstractQueuedSynchronizerでfinalに定義された不変メソッドです
        setState(nextc);
        return true;
    }
    return false;
}

公平ロック / 非公平ロック#

公平ロックは、マルチスレッド環境で各スレッドがロックを取得する順序を保証し、先に到着したスレッドが優先的にロックを取得します（FIFOキューを維持することで実現）。一方、非公平ロックはこの保証を提供できません。ReentrantLockやReadWriteLockはデフォルトで非公平モードです。非公平ロックはスレッドの停止の可能性を減少させ、後から来たスレッドが停止のコストを回避する可能性があります。コードを見てみましょう：

// 非公平ロック
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
      // 違いの重点はここを見てください
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // オーバーフロー
            throw new Error("最大ロック数を超えました");
        setState(nextc);
        return true;
    }
    return false;
}

// 公平ロック
protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        // hasQueuedPredecessorsメソッドが最大の違いです
        // ロックを取得する前に、待機キューが空であるか、自分がキューの先頭にいるかを確認し、その条件を満たさなければロックを取得できません
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("最大ロック数を超えました");
        setState(nextc);
        return true;
    }
    return false;
}

読み書きロック#

参考リンク: 読み書きロック ReentrantReadWriteLock の深い理解

読み書きロックはどのように読み書き状態を記録するのか#

同期状態変数 state の上位 16 ビットは読み取りロックが取得された回数を示し、下位 16 ビットは書き込みロックの取得回数を示します。

/** countで表される共有保持の数を返します  */
// 読み取りロックは共有ロックです
static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
/** countで表される排他保持の数を返します  */
// 書き込みロックは排他ロックです
static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

書き込みロックはどのように取得および解放されるのか#

書き込みロックの取得#

書き込みロックは排他ロックであり、同時に複数のスレッドが取得することはできません。書き込みロックの同期セマンティクスは、AQS 内の tryAcquire メソッドをオーバーライドすることで実現されています：

主なロジックは、読み取りロックが読み取りスレッドによって取得されているか、書き込みロックが他の書き込みスレッドによって取得されている場合、書き込みロックの取得は失敗します。そうでなければ、取得に成功し、再入をサポートし、書き込み状態を増加させます。

書き込みロックの解放#

書き込みロックの解放は、AQS の tryRelease メソッドをオーバーライドすることで行われます。

protected final boolean tryRelease(int releases) {
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
	//1. 同期状態から書き込み状態を減算
    int nextc = getState() - releases;
	//2. 現在の書き込み状態が0であれば、書き込みロックを解放
    boolean free = exclusiveCount(nextc) == 0;
    if (free)
        setExclusiveOwnerThread(null);
	//3. 0でなければ、同期状態を更新
    setState(nextc);
    return free;
}

読み取りロックはどのように取得および解放されるのか#

読み取りロックの取得#

書き込みロックが他のスレッドによって取得されている場合、読み取りロックの取得は失敗します。そうでなければ、CAS を利用して同期状態を更新します。また、現在の同期状態には SHARED_UNIT を加える必要があります。理由は、同期状態の上位 16 ビットが読み取りロックが取得された回数を示すためです。CAS が失敗したり、すでに読み取りロックを取得しているスレッドが再度取得しようとする場合は、fullTryAcquireShared メソッドを利用して実現します。

読み取りロックの解放#

読み取りロックの解放の実装は主に tryReleaseShared メソッドを通じて行われます。ソースコードは以下の通りです：

protected final boolean tryReleaseShared(int unused) {
    Thread current = Thread.currentThread();
	// 前の部分はgetReadHoldCountなどの新機能を実現するためです
    if (firstReader == current) {
        // assert firstReaderHoldCount > 0;
        if (firstReaderHoldCount == 1)
            firstReader = null;
        else
            firstReaderHoldCount--;
    } else {
        HoldCounter rh = cachedHoldCounter;
        if (rh == null || rh.tid != getThreadId(current))
            rh = readHolds.get();
        int count = rh.count;
        if (count <= 1) {
            readHolds.remove();
            if (count <= 0)
                throw unmatchedUnlockException();
        }
        --rh.count;
    }
    for (;;) {
        int c = getState();
		// 読み取りロックの解放は、同期状態から読み取り状態を減算するだけです
        int nextc = c - SHARED_UNIT;
        if (compareAndSetState(c, nextc))
            // 読み取りロックの解放はリーダーには影響を与えませんが、
            // 読み取りロックと書き込みロックの両方が現在自由であれば、
            // 待機中のライターが進行できる可能性があります。
            return nextc == 0;
    }
}

楽観ロック / 悲観ロック#

参考リンク: 面接必須の楽観ロックと悲観ロック

楽観ロック#

常に最良の状況を仮定し、データを取得する際には他の人が変更しないと考え、ロックをかけませんが、更新時にはその間に他の人がデータを更新したかどうかを確認します。バージョン番号メカニズムとCASアルゴリズムを使用して実現できます。
楽観ロックは多読のアプリケーションタイプに適しており、スループットを向上させることができます。

楽観ロックの欠点（CAS アルゴリズムの欠陥）#

ABA 問題（JDK 1.5 以降のAtomicStampedReferenceクラスが解決）
循環時間が長くコストが高い：スピン CAS、つまり成功するまで常にループ実行し続けるため、長時間成功しない場合、CPU に非常に大きな実行コストをもたらします。
共有変数の原子操作のみを保証：CAS は単一の共有変数に対してのみ有効であり、複数の共有変数にまたがる操作には無効です。JDK 1.5 以降、AtomicReferenceクラスが提供され、参照オブジェクト間の原子性を保証します。複数の変数を 1 つのオブジェクトにまとめて CAS 操作を行うことができます。

悲観ロック#

データを取得する際には常に他の人が変更する可能性があると考え、データを取得するたびにロックをかけます。これにより、他の人がこのデータを取得しようとすると、ロックを取得するまでブロックされます（共有リソースは毎回 1 つのスレッドにのみ使用され、他のスレッドはブロックされ、使用後にリソースを他のスレッドに転送します）。

伝統的な関係データベースでは、このようなロックメカニズムが多く使用されています。例えば、行ロック、テーブルロック、読み取りロック、書き込みロックなど、操作の前にロックをかけます。

Java のsynchronizedやReentrantLockなどの排他ロックは、悲観ロックの思想を実現しています。