《並行プログラミングの芸術》-読書ノート05：javaにおけるロック

『並行プログラミングの芸術』読書ノート第 5 章、図と文の絶妙な組み合わせ

あなたが私をロックし、私があなたをロックし、両者は譲らず、そして行き詰まりに入る、これは恋愛に似ています。

一、Lock インターフェース#

提供された synchronized にはない特性：

非ブロッキングでロックを取得しようとする：tryLock()、メソッドを呼び出した後すぐに戻る
割り込み可能にロックを取得する：lockInterruptibly(): ロックの取得中に現在のスレッドを中断できる
タイムアウトでロックを取得する：tryLock(time,unit)、タイムアウトで戻る

Lock インターフェースの実装は基本的に == 同期器のサブクラスを集約してスレッドアクセス制御を行う。==

使用上の注意

unlockメソッドはfinally内で使用する必要があり、目的はロックを取得した後、最終的に解放されることを保証するため
lockメソッドはtryブロック内に置いてはいけない、なぜならtry catchが例外を投げると、ロックが無駄に解放されるから

二、キュー同期器#

キュー同期器AbstractQueuedSynchronizerはロックや他の同期コンポーネントを構築するための基本フレームワークです。
それはintメンバー変数を使用して同期状態を表し、内蔵のFIFOキューを通じてリソースを取得するスレッドの待機を行います。

同期器の主な使用方法は継承であり、サブクラスは同期器を継承し、その抽象メソッドを実装して同期状態を管理します。同期器は排他型で同期状態を取得することも、共有型で同期状態を取得することもサポートしており、これにより異なるタイプの同期コンポーネント（ReentrantLock、ReentrantReadWriteLock、CountDownLatchなど）を簡単に実装できます。

==同期器== はロックの実装の鍵であり、ロックの実装において同期器を集約し、同期器を利用してロックの意味を実現します。
両者の関係を理解する：

ロックは使用者に向けられており、使用者とロックの相互作用のインターフェースを定義し、実装の詳細を隠します；
同期器はロックの実装者に向けられており、ロックの実装方法を簡素化し、同期状態の管理、スレッドの待機、待機と起床などの低レベルの操作を隠蔽します。

キュー同期器のインターフェースと例#

同期器の設計はテンプレートメソッドパターンに基づいており、つまり、使用者は同期器を継承し、指定されたメソッドをオーバーライドし、その後、同期器をカスタム同期コンポーネントの実装に組み込み、同期器が提供するテンプレートメソッドを呼び出します。これらのテンプレートメソッドは、使用者がオーバーライドしたメソッドを呼び出します。

同期器の指定されたメソッドをオーバーライドする際には、同期器が提供する以下の 3 つのメソッドを使用して同期状態にアクセスまたは変更する必要があります。

getState()：現在の同期状態を取得します。
setState(int newState)：現在の同期状態を設定します。
compareAndSetState(int expect,int update)：CAS を使用して現在の状態を設定します。このメソッドは状態設定の原子性を保証します。

同期器が提供するテンプレートメソッドは基本的に 3 つのカテゴリに分かれます：排他型の同期状態の取得と解放、共有型の同期状態の取得と解放、および同期キュー内の待機スレッドの状況を照会する。カスタム同期コンポーネントは、同期器が提供するテンプレートメソッドを使用して独自の同期意味を実現します。

動作原理#

MUtuxソースコード略

キュー同期器の実装分析#

1. 同期キュー#

FIFO双方向キューを使用して同期状態の管理を行います。現在のスレッドが同期状態の取得に失敗した場合、同期器は現在のスレッドおよび待機状態などの情報を構築してNodeにし、同期キューに追加します。同時に現在のスレッドをブロックします。同期状態が解放されると、先頭ノード内のスレッドが起床し、再度同期状態の取得を試みます。

先頭ノードは同期状態の取得に成功したノードであり、先頭ノードが同期状態を解放する際には、後続ノードを起こし、後続ノードが同期状態の取得に成功した場合には自分自身を先頭ノードとして設定します。

ノードの属性タイプと名前および説明

2. 排他型の同期状態の取得と解放#

 public final void acquire(int arg) {
        if (!tryAcquire(arg) 					&&acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            //もし上記の操作が失敗した場合、スレッドをブロックする
            selfInterrupt();
 }
//上記のコードは主に同期状態の取得、ノードの構築、同期キューへの追加、および同期キュー内でのスピン待機に関連する作業を完了します。

コード分析：
まず同期状態の取得を試み、失敗した場合、排他型の同期ノード（排他型Node.EXCLUSIVE）を構築し、ノードの末尾に追加します。その後、acquireQueuedを呼び出し、ノードが無限ループで同期状態を取得しようとします。取得できない場合は、ノード内のスレッドをブロックします。

2 つの無限ループ：入隊、入隊後

addWaiterとenqメソッド・

「無限ループ」の中で、ノードを末尾ノードに設定するためにCASを通じて成功した場合にのみ、現在のスレッドはこのメソッドから戻ることができます。そうでなければ、現在のスレッドは設定を試み続けます。enq(final Node node)メソッドは、並行してノードを追加するリクエストをCASを通じて「直列化」します。
```
addWaiterメソッドは迅速に追加しようとしますが、並行性のためにノードが正常に追加できない場合（末尾ノード==null）、enqメソッドは無限ループでノードを追加し、ノードを末尾に追加します。
```
acquireQueuedメソッド

・== 前駆ノードが先頭ノードである場合のみ同期状態を取得しようとします ==、理由：
先頭ノードは同期状態を成功裏に取得したノードであり、先頭ノードのスレッドが同期状態を解放すると、後続ノードを起こします。後続ノードのスレッドが起こされると、自分の前駆ノードが先頭ノードであるかどうかを確認する必要があります。
同期キューの FIFO 原則を維持します。ノード間は相互に通信せず、早すぎる通知の処理を容易にします（早すぎる通知とは、前駆ノードが先頭ノードでないスレッドが中断されて起こされることを指します）。

同期状態の解放にはreleaseメソッドを使用します。

public final boolean release(int arg) {
	if (tryRelease(arg)) {
		Node h = head;
		if (h != null && h.waitStatus != 0
            //unparkSuccessor(Node node)メソッドはLockSupportを使用して（後の章で特に紹介します）待機状態のスレッドを起こします
			unparkSuccessor(h);
		return true;
	}
	return false;
}

まとめ：同期状態を取得する際、同期器は同期キューを維持し、状態取得に失敗したスレッドはすべてキューに追加され、キュー内でスピンします。キューから移動する（スピンを停止する）条件は、前駆ノードが先頭ノードであり、同期状態を成功裏に取得したことです。同期状態を解放する際、同期器はtryReleaseメソッドを呼び出して同期状態を解放し、その後、先頭ノードの後続ノードを起こします。

3. 共有型の同期状態の取得と解放#

主な違い：同時に複数のスレッドが同期状態を取得できるかどうか

共有型のリソースアクセスでは、他の共有型のアクセスは許可されますが、排他型のアクセスはブロックされます。排他型のリソースアクセスでは、同時に他のアクセスはすべてブロックされます。

tryAcquireShared(int arg)メソッドの戻り値はint型で、戻り値が0以上であれば、同期状態を取得できることを示します。
releaseShared・メソッドと排他型の主な違いは、tryReleaseShared(int arg)メソッドが同期状態（またはリソース数）をスレッドセーフに解放することを保証しなければならないことです。一般的にはループとCASを通じて保証されます。なぜなら、同期状態の解放操作は複数のスレッドから同時に行われるからです。

ソースコードの詳細はまだ多くが理解できていません
例えば、interruptの配置タイミング、共有時のスレッドセーフ性をどう保証するか、共有取得の同期状態における伝播と信号が何を意味するのかなど。

4. 排他型のタイムアウトでの同期状態の取得#

同期器のdoAcquireNanos(int arg,long nanosTimeout)メソッドを呼び出すことで、タイムアウトで同期状態を取得できます。指定された時間内に同期状態を取得できればtrueを返し、そうでなければfalseを返します。このメソッドは従来のJavaの同期操作（例えばsynchronizedキーワード）にはない特性を提供します。

中断に応じた同期状態の取得プロセス

Java 5 では、同期器はacquireInterruptibly(int arg)メソッドを提供しています。このメソッドは、同期状態の取得を待っている間に現在のスレッドが中断された場合、すぐに戻り、InterruptedExceptionをスローします。

doAcquireNanos(int arg,long nanosTimeout)メソッドは、中断に応じた基盤の上にタイムアウト取得の特性を追加します。タイムアウト取得に関しては、必要な睡眠時間間隔nanosTimeoutを計算する必要があります。早すぎる通知を防ぐために、nanosTimeoutの計算式は：nanosTimeout-=now-lastTimeです。ここでnowは現在の起床時間、lastTimeは前回の起床時間です。nanosTimeoutが0より大きい場合は、タイムアウト時間がまだ到達していないことを示し、nanosTimeoutナノ秒の間、引き続き睡眠する必要があります。逆に、すでにタイムアウトしています・

排他型タイムアウトでの同期状態の取得は、排他型の同期状態の取得プロセスと非常に似ています

主な違いは、同期状態を取得できなかった場合の処理ロジックです。acquire(int args)は、同期状態を取得できなかった場合、現在のスレッドを待機状態に置きますが、doAcquireNanos(int arg,long nanosTimeout)は、現在のスレッドをnanosTimeoutナノ秒待機させます。もし現在のスレッドがnanosTimeoutナノ秒内に同期状態を取得できなければ、待機ロジックから自動的に戻ります。

時間が超時自旋の制限以下であれば、超時待機を行わず、迅速な自旋プロセスに入ります。

三、再入ロック（ReentrantLock）#

synchronized キーワードは暗黙的に再入をサポートします

ReentrantLock は synchronized のように暗黙的にサポートされておらず、lock メソッドを呼び出す際に、すでにロックを取得しているスレッドが再度 lock メソッドを呼び出してもブロックされません。

公平にロックを取得すること、つまり待機時間が最も長いスレッドが最優先でロックを取得すること、またはロックの取得が順序的であると言えます。

実際、公平なロックメカニズムはしばしば非公平なものより効率が高くありませんが、公平なロックの利点は、「飢餓」が発生する確率を減少させることです。待機時間が長いリクエストは優先的に満たされることができます。

1. 再入の実装#

2 つの問題：

再度ロックを取得する

ロックは、ロックを取得しているスレッドが現在のスレッドであるかどうかを識別する必要があります。そうであれば、再度成功裏に取得します。

最終的な解放

ロックは取得に対してカウントを自増させる必要があります。

問題：意味は何か？
循環的にロックを取得することによる性能への影響やデッドロックを防ぐため

再入可能なロック取得メカニズムでは、取得時に初回でない場合、状態を加算し、実際にはCAS操作を行わないため、ロックを解放する際にはstateが0である必要があります。そうでなければ、ロックは完全に解放されません。

2. 公平ロックと非公平ロックの違い：#

もしロックが公平であれば、ロックの取得順序はリクエストの絶対時間順序に従うべきであり、つまり FIFO です。

公平ロック：CASが成功し、かつキューの先頭ノードである（前駆ノードの判断が追加される）
非公平ロック：CASが成功すればよい

再入ロックのデフォルト実装は非公平ロックです。その理由は：飢餓を引き起こす可能性があるが、非公平ロックのオーバーヘッドが少ない（スレッド切り替え回数が少ない）ため、より高いスループットを得ることができるからです。

四、読み書きロック（ReentrantReadWriteLock）#

前述のロックは基本的に排他ロックであり、同時に 1 つのスレッドのみがアクセスを許可されます。

読み書きは同時に複数の読みスレッドのアクセスを許可しますが、書きスレッドがアクセスする際には、すべての読みスレッドと他の書きスレッドがブロックされます。（書き操作の可視性を保証します）

読み書きロックは 1 対のロック、1 つの読みロックと 1 つの書きロックを維持し、読みロックと書きロックを分離することで、一般的な排他ロックに比べて並行性が大幅に向上します。

読み書きロックの実装分析#

1. 読み書き状態の設計#

カスタム同期器に依存し、読み書きロックのカスタム同期器は、同期状態（1 つの int 値）上で複数の読みスレッドと 1 つの書きスレッドの状態を維持する必要があります。高 16 ビットは読みを、低 16 ビットは書きを表します。

ビット演算
現在の同期状態は、あるスレッドが書きロックを取得し、さらに2回再入したことを示します。また、2回連続して読みロックを取得したことも示します。読み書きロックは、読みと書きの状態を迅速に判断する方法は何でしょうか？答えはビット演算です。現在の同期状態値をSとし、書き状態はS&0x0000FFFF（高16ビットをすべて消去）であり、読み状態はS>>>16（符号なしで0を補って右に16ビットシフト）です。書き状態が1増加すると、S+1となり、読み状態が1増加すると、S+(1<<16)、つまりS+0x00010000となります。

2. 書きロックの取得と解放#

書きロックは再入をサポートする排他ロックであり、現在のスレッドが書きロックを取得している場合、書き状態を増加させます。
現在のスレッドが書きロックを取得する際に、読みロックがすでに取得されているか、またはそのスレッドがすでに書きロックを取得しているスレッドでない場合、現在のスレッドは待機状態に入ります。

読みロックが存在する場合、書きロックは取得できない：

読み書きロックは、書きロックの操作が読みロックに可視であることを保証する必要があります。もし読みロックが取得されている状態で書きロックを取得することを許可すると、他の実行中の読みスレッドは現在の書きスレッドの操作を感知できなくなります。したがって、他の読みスレッドがすべて読みロックを解放するのを待たなければ、書きロックは現在のスレッドによって取得されることはできません。書きロックが取得されると、他の読み書きスレッドの後続のアクセスはすべてブロックされます。

3. 読みロックの取得と解放#

他の書きスレッドがアクセスしていない場合、読みロックは常に成功裏に取得されます。書きロックが他のスレッドによって取得されている場合、待機状態に入ります。

読みロックの各解放（スレッドセーフで、複数の読みスレッドが同時に読みロックを解放する可能性があります）は、読み状態を減少させます。減少する値は（1<<16）です。

読み状態のスレッドセーフは CAS によって保証されます

4. ロックのダウングレード（書きロックを読みロックにダウングレード）#

定義：書きロックを保持しながら、読みロックを取得し、その後書きロックを解放するプロセス

writeLock.lock();
readLock.lock();
writeLock.unlock();

ここはあまり理解できません。。。

ロックのダウングレードの前提は、すべてのスレッドがデータの変化に敏感であることを望んでいますが、書きロックは 1 つしかないため、ダウングレードが発生します。もし書きロックを先に解放し、次に読みロックを取得すると、取得する前に他のスレッドが書きロックを取得し、読みロックの取得をブロックする可能性があり、データの変化を感知できなくなります。したがって、まず書きロックを保持し、データの変化がないことを保証し、次に読みロックを取得し、その後書きロックを解放する必要があります。ロックのダウングレードにおける読みロック取得の必要性：

データの可視性を保証するために、現在のスレッドが読みロックを取得せずに書きロックを解放すると、別のスレッドが書きロックを取得してデータを変更した場合、現在のスレッドはデータの更新を感知できなくなります。現在のスレッドが読みロックを取得すれば、別のスレッドはブロックされ、現在のスレッドがデータを使用し、ロックを解放した後にのみ、別のスレッドが書きロックを取得してデータを更新できます。

五、LockSupport ツール#

LockSupport は一連の公共静的メソッドを定義しており、これらのメソッドは最も基本的なスレッドのブロックと起床機能を提供します。LockSupport は同期コンポーネントを構築するための基本ツールともなります。

Java 6 では、LockSupport は park (Object blocker)、parkNanos (Object blocker,long nanos) および parkUntil (Object blocker,long deadline) の 3 つのメソッドを追加し、現在のスレッドをブロックする機能を実現します。ここで、パラメータ blocker は現在のスレッドが待機しているオブジェクトを識別するために使用されます（以下、ブロッキングオブジェクトと呼びます）。このオブジェクトは主に問題のトラブルシューティングとシステム監視に使用されます。

六、Condition インターフェース#

Condition インターフェースも Object の監視器メソッドに似た機能を提供し、Lock と組み合わせることで待機 / 通知パターンを実現できますが、これら二つは使用方法や機能特性において依然として違いがあります。

1.Condition インターフェースと例#

Condition はメソッドを呼び出す前にロックを取得します。

追加および削除メソッドではif判断ではなくwhileループを使用する目的は、早すぎるまたは意図しない通知を防ぐためであり、条件が満たされるまでループを抜けることができません。以前に述べた待機/通知の古典的なパターンを思い出してください。二者は非常に似ています。

2.Condition の実装分析#

ConditionObjectは同期器AbstractQueuedSynchronizerの内部クラスであり、Condition の操作には関連するロックを取得する必要があるため、同期器の内部クラスとしても合理的です。各Conditionオブジェクトは、待機キュー（以下、待機キューと呼びます）を含んでおり、このキューは Condition オブジェクトが待機 / 通知機能を実現するための鍵です。

待機キュー

待機キューは FIFO のキューであり、キュー内の各ノードはスレッド参照を含んでいます。このスレッドは Condition オブジェクト上で待機しているスレッドです。もしスレッドが Condition.await () メソッドを呼び出すと、そのスレッドはロックを解放し、ノードを構築して待機キューに追加し、待機状態に入ります（同期キューと似ています）。

Object の監視器モデルでは、オブジェクトは同期キューと待機キューを持ち、並行パッケージ内の Lock（より正確には同期器）は同期キューと複数の待機キューを持っています。

上記のノード参照の更新プロセスには CAS が保証されていません。理由は、await () メソッドを呼び出すスレッドは必ずロックを取得しているスレッドであるため、つまりこのプロセスはロックによってスレッドセーフが保証されます。

待機

Condition の signal () メソッドを呼び出すと、待機キュー内で最も長く待機しているノード（先頭ノード）が起こされます。ノードを起こす前に、ノードは同期キューに移動されます。

ソースコード略
1. locksupportのpark()メソッドを使用して待機状態に入り、ノードが同期キューにいるかどうかを確認することで、ノードを起こすフラグを判断します。なぜなら、Conditionの通知はノードを起こす前にノードを同期キューに移動させるからです。
起こされた後は、通知または中断の方法を判断することに注意してください。
2. キューの観点から、スレッドがConditionの待機キューに追加されることは、実質的に新しいノードを構築して待機キューに追加することです。