MCSロックの原理と実現
9932 ワード
前情回顧
前の論文では,主にスピンロックの特徴とその適用シーンを議論し,次いで2つのスピンロックの簡単な実装を与えた.
存在する問題
単純な非公平スピンロックでも公平なキューベーススピンロックでも、実行スレッドが同じ共有変数上でスピンするため、ロックの申請と解放時に共有変数を変更する必要があります.これにより、キュースピンロック操作に関与するすべてのプロセッサのキャッシュが無効になります.キュースピンロックの競合が激しい場合、頻繁なキャッシュ同期操作により、システムバスやメモリのトラフィックが重くなり、システム全体のパフォーマンスが大幅に低下します.
したがって、実行スレッドを同じ共有変数上でスピンさせず、高周波数のキャッシュ同期動作を回避する方法が必要である.そこでMCSとCLHロックが誕生した.
この2つのロックの名前は、発明者の名前の頭文字に由来しています.
MCS:John Mellor-Crummey and Michael Scott.
CLH:Craig,Landin and Hagersten.
本論文ではまずMCSロックの原理と対応する実装を紹介する.
MCSロック
MCSスピンロックは、一方向チェーンテーブルに基づく高性能で公平なスピンロックであり、ロックを申請するスレッドはローカル変数上でスピンするだけで、直接前駆者はスピンの終了を通知し、不要なプロセッサキャッシュ同期の回数を大幅に減少させ、総線とメモリのオーバーヘッドを低減する.
まず実装コードを実行し、次に分析のポイントを示します.
ノード定義およびロック所有フィールド
まず、ノードオブジェクトを定義する必要があります.このノードは、ロックを申請するスレッド間の前後関係を表し、ノードはnext属性によって単一のチェーンテーブルのデータ構造を構成する.また、ノードのblockedプロパティは、そのノードがロック待ちの状態であるか否かを示し、デフォルト値はtrueであり、ノードの初期状態が待機中であることを示す.
次に、ロック自体の実装には3つのプロパティがあります.ノードタイプqueue:現在のチェーンテーブルの末尾を表し、新しくキューに追加されたスレッドごとにこの位置 に配置されます. ThreadLocalタイプのcurrentThreadNode:スレッドオブジェクトからノードオブジェクトインスタンスへのマッピング関係 が保存する. queueフィールドに対する原子更新器AtomicReferenceFieldUpdater:queueフィールドに対するAtomicReferenceFieldUpdaterの動作をパッケージ化し、どの操作もqueueに直接適用するのではなく、いくつかのCAS操作を提供して原子性 を保証する
最も重要なのはその中のlockとunlockの方法です.実装方法を簡単に分析します.
ロックメソッド
この方法の操作手順とポイントを簡単に抽出します.現在のスレッドと対応するノードオブジェクト(存在しない場合は初期化) を取得する. queueはgetAndSetという原子操作によって第1ステップで得られたノードオブジェクトにqueueを更新し、前駆が存在する場合はStep 3にジャンプし、存在する可能性のある前駆ノードを返す.Step 4 にジャンプは存在しませんは、前駆ノードによって現在のノードを指す一方向チェーンテーブル関係を確立する.現在のスレッドは、現在のノードオブジェクトのblockedフィールド上でスピン待機(前駆ノードがblockedの状態を変更するのを待つ) を開始する.は、この時点で現在のスレッド以外のスレッドにロックがないことを示す前駆ノードがないため、ノードのblockedをfalseに直接変更することができ、lockメソッドの実行が完了すると、ロックが成功したことを示す を示す.
unlockメソッド
この方法の操作手順とポイントを簡単に抽出します.現在のスレッドと対応するノードオブジェクトを取得する.ノードが存在するか、ノードの状態が待機している場合は、ロックを有するスレッドのみがロックを解除する操作を行う資格があるため、直接戻る. 現在のスレッドに対応するノード情報 をクリアする.現在のノードに後継ノードがあるかどうかを判断し、なければStep 4にジャンプする.なければStep 5 にジャンプ原子更新器のCAS操作を利用してqueueをnullに設定しようとした.設定に成功するとロックの解放に成功し、unlockメソッドの実行が完了して戻ります.設定に失敗するとStep 3とStep 4のCASの操作の間に別のスレッドが絡み合っていることを示し、queueは現在のノードを指しているわけではないので、チェーンテーブルの構造が整っていることを確保するのを待つ必要がある(コード注釈:lock操作のgetAndSet操作とチェーンテーブルの確立は原子的ではない) .現在のノードの後続ノードが準備されているので、後続ノードのblocked状態を変更し、待機しているスレッドがスピンを終了することができる.最後に、現在のノードのnextがnull補助ゴミ回収 を指すことも更新される.
以上のロックとロック解除の各ステップには比較的詳細な注釈があり、よく読むと分かるのは難しいことではないと信じています.
mainメソッド
MCSロックの実装の一例として,10スレッドのロックを奪うシーンをシミュレートした.
まとめ
実装されるコード量は多くないが,lockとunlockの設計思想には微妙な点があり,正確に実現するのは容易ではない.
いくつかのポイントを把握する必要があります. MCSロックのノードオブジェクトには2つの状態が必要であり、nextは一方向チェーンテーブルの構造を維持するために使用され、blockedはノードの状態を表し、trueはスピン中であることを示す.falseはロック成功 を示す MCSロックのノード状態blockedの変更は、その前駆ノードによってトリガ変更された である.ロック時にチェーンテーブルの末尾ノードが更新され、チェーンテーブル構造のメンテナンス が完了する.ロックを解除する際には、チェーンテーブル構造が確立するヒステリシス(getAndSet原子法とチェーンテーブル構築全体として原子性ではない)のため、マルチスレッドの干渉が存在する可能性があり、忙しい待機を使用してチェーンテーブル構造の準備 を保証する必要がある.
なお、MCSロックは再入不可の排他ロックである.
次の記事では、CLHロックというより軽量なソリューションについて説明します.
参考資料 https://coderbee.net/index.php/concurrent/20131115/577 https://en.wikipedia.org/wiki/Spinlock https://www.ibm.com/developerworks/cn/linux/l-cn-mcsspinlock/
前の論文では,主にスピンロックの特徴とその適用シーンを議論し,次いで2つのスピンロックの簡単な実装を与えた.
存在する問題
単純な非公平スピンロックでも公平なキューベーススピンロックでも、実行スレッドが同じ共有変数上でスピンするため、ロックの申請と解放時に共有変数を変更する必要があります.これにより、キュースピンロック操作に関与するすべてのプロセッサのキャッシュが無効になります.キュースピンロックの競合が激しい場合、頻繁なキャッシュ同期操作により、システムバスやメモリのトラフィックが重くなり、システム全体のパフォーマンスが大幅に低下します.
したがって、実行スレッドを同じ共有変数上でスピンさせず、高周波数のキャッシュ同期動作を回避する方法が必要である.そこでMCSとCLHロックが誕生した.
この2つのロックの名前は、発明者の名前の頭文字に由来しています.
MCS:John Mellor-Crummey and Michael Scott.
CLH:Craig,Landin and Hagersten.
本論文ではまずMCSロックの原理と対応する実装を紹介する.
MCSロック
MCSスピンロックは、一方向チェーンテーブルに基づく高性能で公平なスピンロックであり、ロックを申請するスレッドはローカル変数上でスピンするだけで、直接前駆者はスピンの終了を通知し、不要なプロセッサキャッシュ同期の回数を大幅に減少させ、総線とメモリのオーバーヘッドを低減する.
まず実装コードを実行し、次に分析のポイントを示します.
public class MCSLockV2 {
/**
* MCS
*/
public static class MCSNodeV2 {
/**
*
*/
volatile MCSNodeV2 next;
/**
*
*/
volatile boolean blocked = true;
}
/**
*
*/
private ThreadLocal currentThreadNode = new ThreadLocal<>();
/**
* MCSNode
*/
volatile MCSNodeV2 queue;
/**
*
*/
private static final AtomicReferenceFieldUpdater UPDATER = AtomicReferenceFieldUpdater
.newUpdater(
MCSLockV2.class,
MCSLockV2.MCSNodeV2.class,
"queue");
/**
* MCS
*/
public void lock() {
MCSNodeV2 cNode = currentThreadNode.get();
if (cNode == null) {
//
cNode = new MCSNodeV2();
currentThreadNode.set(cNode);
}
// queue
MCSNodeV2 predecessor = (MCSNodeV2) UPDATER.getAndSet(this, cNode); // step 1
if (predecessor != null) {
// ( )
predecessor.next = cNode; // step 2
// (MCSNode blocked true)
// ， blocked false，
while (cNode.blocked) {
}
} else {
// ， ， -
cNode.blocked = false;
}
}
/**
* MCS
*/
public void unlock() {
//
MCSNodeV2 cNode = currentThreadNode.get();
if (cNode == null || cNode.blocked) {
//
//
// - blocked true ， ， ，
return;
}
if (cNode.next == null && !UPDATER.compareAndSet(this, cNode, null)) {
// ， queue
// CAS ， ，
// lock step 1 ，step 2
while (cNode.next == null) {
}
}
if (cNode.next != null) {
//
cNode.next.blocked = false;
// ， GC
cNode.next = null; // for GC
}
//
currentThreadNode.remove();
}
/**
*
*
* @param args
*/
public static void main(String[] args) {
final MCSLockV2 lock = new MCSLockV2();
for (int i = 1; i <= 10; i++) {
new Thread(generateTask(lock, String.valueOf(i))).start();
}
}
private static Runnable generateTask(final MCSLockV2 lock, final String taskId) {
return () -> {
lock.lock();
try {
Thread.sleep(3000);
} catch (Exception e) {
}
System.out.println(String.format("Thread %s Completed", taskId));
lock.unlock();
};
}
} ノード定義およびロック所有フィールド
まず、ノードオブジェクトを定義する必要があります.このノードは、ロックを申請するスレッド間の前後関係を表し、ノードはnext属性によって単一のチェーンテーブルのデータ構造を構成する.また、ノードのblockedプロパティは、そのノードがロック待ちの状態であるか否かを示し、デフォルト値はtrueであり、ノードの初期状態が待機中であることを示す.
次に、ロック自体の実装には3つのプロパティがあります.
最も重要なのはその中のlockとunlockの方法です.実装方法を簡単に分析します.
ロックメソッド
この方法の操作手順とポイントを簡単に抽出します.
unlockメソッド
この方法の操作手順とポイントを簡単に抽出します.
以上のロックとロック解除の各ステップには比較的詳細な注釈があり、よく読むと分かるのは難しいことではないと信じています.
mainメソッド
MCSロックの実装の一例として,10スレッドのロックを奪うシーンをシミュレートした.
まとめ
実装されるコード量は多くないが,lockとunlockの設計思想には微妙な点があり,正確に実現するのは容易ではない.
いくつかのポイントを把握する必要があります.
なお、MCSロックは再入不可の排他ロックである.
次の記事では、CLHロックというより軽量なソリューションについて説明します.
参考資料