ConcurrentHashMapはjdk/java 1.8/8種類のUnsafeとCASで操作します
3730 ワード
ガイド:JDK 8での実装
ConcurrentHashMapはJDK 8で大きな変更が行われており,Doug Leaの実現方法をソースコードで再学習する必要がある.
Segment(セグメントロック)の概念を捨て、CASアルゴリズムを利用した新しい方法で実装を開始した.同時期のHashMapバージョンの考え方に沿っており、下層は依然として「配列」+チェーンテーブル+赤黒樹の方式思想(JDK 7とJDK 8におけるHashMapの実装)によって行われているが、同時化を図るためにTreeBinのような補助的なクラスが多く追加されている.Traverserなどのオブジェクトの内部クラス.
UnsafeとCAS
ConcurrentHashMapでは、Uが随所に見られ、U.compareAndSwapXXXの方法が大量に使用されている.この方法はCASアルゴリズムを利用して無ロック化された修正値の操作を実現し、ロックエージェントの性能消費を大幅に低減することができる.このアルゴリズムの基本的な考え方は、現在のメモリの変数値が指定した変数値と等しいかどうかを絶えず比較し、等しい場合は指定した変更値を受け入れ、そうでなければ操作を拒否することです.現在のスレッドの値は最新の値ではないため、他のスレッドの変更結果を上書きする可能性があります.この点は楽観的ロック,SVNの考えと比較的に似ている.
1 unsafe静的ブロック
unsafeコードブロックは、最も一般的なSIZECTLのようないくつかの属性の修正作業を制御する.このバージョンのconcurrentHashMapでは、多くのCASメソッドが変数、属性の変更を行います.CASによる無ロック操作により、性能を大幅に向上させることができます.
2 3つのコアメソッド
ConcurrentHashMapは、指定された位置のノードを操作するための3つの原子操作を定義します.これらの原子操作こそConcurrentHashMapのスレッドの安全を保証している.
3.
JDK 8の実装もロック分離の考え方であり,JDK 7のSegmentではなくノードをロックするだけであり,ノードをロックする前の動作はロックされずスレッドも安全であり,前に述べた3つの原子操作に基づいていることが分かった.
4.まとめ
jdk 7のConcurrentHashmapでは,長さが長すぎると衝突が頻繁になり,チェーンテーブルの増改削除操作に時間がかかり,性能に影響するため,jdk 8ではconcurrentHashmapを完全に書き換え,コード量が従来の1000行以上から6000行以上になり,実現上も従来のセグメント式記憶と大きく異なる.
主な設計上の変化は以下の点である.
segmentではなくnodeを採用し,nodeをロックしてロック粒度の低減を実現した.
MOVED状態を設計し、resizeの途中でスレッド2がputデータにある場合、スレッド2はresizeを助ける.
3つのCAS操作を用いてnodeのいくつかの操作の原子性を確保し,この方式はロックの代わりになった.
sizeCtlの異なる値は異なる意味を表し,制御の役割を果たす.
なぜJDK 8でReentrantLockではなくsynchronizedが使われているのかというと、JDK 8ではsynchronizedに十分な最適化がなされているからだと思います.
ConcurrentHashMapはJDK 8で大きな変更が行われており,Doug Leaの実現方法をソースコードで再学習する必要がある.
Segment(セグメントロック)の概念を捨て、CASアルゴリズムを利用した新しい方法で実装を開始した.同時期のHashMapバージョンの考え方に沿っており、下層は依然として「配列」+チェーンテーブル+赤黒樹の方式思想(JDK 7とJDK 8におけるHashMapの実装)によって行われているが、同時化を図るためにTreeBinのような補助的なクラスが多く追加されている.Traverserなどのオブジェクトの内部クラス.
UnsafeとCAS
ConcurrentHashMapでは、Uが随所に見られ、U.compareAndSwapXXXの方法が大量に使用されている.この方法はCASアルゴリズムを利用して無ロック化された修正値の操作を実現し、ロックエージェントの性能消費を大幅に低減することができる.このアルゴリズムの基本的な考え方は、現在のメモリの変数値が指定した変数値と等しいかどうかを絶えず比較し、等しい場合は指定した変更値を受け入れ、そうでなければ操作を拒否することです.現在のスレッドの値は最新の値ではないため、他のスレッドの変更結果を上書きする可能性があります.この点は楽観的ロック,SVNの考えと比較的に似ている.
1 unsafe静的ブロック
unsafeコードブロックは、最も一般的なSIZECTLのようないくつかの属性の修正作業を制御する.このバージョンのconcurrentHashMapでは、多くのCASメソッドが変数、属性の変更を行います.CASによる無ロック操作により、性能を大幅に向上させることができます.
private static final sun.misc.Unsafe U;
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;
private static final long CELLSBUSY;
private static final long CELLVALUE;
private static final long ABASE;
private static final int ASHIFT;
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class> k = ConcurrentHashMap.class;
SIZECTL = U.objectFieldOffset
(k.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(k.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(k.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(k.getDeclaredField("cellsBusy"));
Class> ck = CounterCell.class;
CELLVALUE = U.objectFieldOffset
(ck.getDeclaredField("value"));
Class> ak = Node[].class;
ABASE = U.arrayBaseOffset(ak);
int scale = U.arrayIndexScale(ak);
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
}catch (Exception e) {
throw new Error(e);
}
}
2 3つのコアメソッド
ConcurrentHashMapは、指定された位置のノードを操作するための3つの原子操作を定義します.これらの原子操作こそConcurrentHashMapのスレッドの安全を保証している.
// i Node
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
// CAS i Node 。
// CAS , , ,
// , SVN
static final boolean casTabAt(Node[] tab, int i,
Node c, Node v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
// volatile
static final void setTabAt(Node[] tab, int i, Node v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
3.
JDK 8の実装もロック分離の考え方であり,JDK 7のSegmentではなくノードをロックするだけであり,ノードをロックする前の動作はロックされずスレッドも安全であり,前に述べた3つの原子操作に基づいていることが分かった.
4.まとめ
jdk 7のConcurrentHashmapでは,長さが長すぎると衝突が頻繁になり,チェーンテーブルの増改削除操作に時間がかかり,性能に影響するため,jdk 8ではconcurrentHashmapを完全に書き換え,コード量が従来の1000行以上から6000行以上になり,実現上も従来のセグメント式記憶と大きく異なる.
主な設計上の変化は以下の点である.
segmentではなくnodeを採用し,nodeをロックしてロック粒度の低減を実現した.
MOVED状態を設計し、resizeの途中でスレッド2がputデータにある場合、スレッド2はresizeを助ける.
3つのCAS操作を用いてnodeのいくつかの操作の原子性を確保し,この方式はロックの代わりになった.
sizeCtlの異なる値は異なる意味を表し,制御の役割を果たす.
なぜJDK 8でReentrantLockではなくsynchronizedが使われているのかというと、JDK 8ではsynchronizedに十分な最適化がなされているからだと思います.