JAva楽観ロックのCAS原理解析
47045 ワード
目次意味 原理分析 CPU原語 CAS欠陥 ABA問題 サイクル時間長オーバーヘッド大 は、単一の共有変数に対してのみ原子的な動作を保証する である.
意味
CAS(CompareAndSwap)は、コンカレントアルゴリズムを実装する際によく用いられる技術である.CAS操作には、メモリ位置、予想値、および新しい値の3つの操作数が含まれます.CAS操作を実行するときは、メモリの位置の値を予想した値と比較し、一致するとプロセッサは自動的にその位置の値を新しい値に更新します.そうしないと、プロセッサは何もしません.
楽観ロックの意味は衝突が発生していないと仮定することであり、私はちょうどある操作を行うことができます.もし衝突が発生したら、私は成功するまで再試行します.楽観ロックで最もよく見られるのはCASです.ReenterLock内部のAQSも,各種Atomicの先頭の原子類も,内部はCASに適用されている.
げんりぶんせき
java.util.concurrent.atomic.***AtomicInteger***を例に分析 Unsafeはsunに位置する.miscパッケージの下のクラスで、UnsafeクラスはJava言語にC言語ポインタのようにメモリ空間を操作する能力を持たせ、プログラムに関連するポインタの問題が発生するリスクも増加したに違いない.プログラムでUnsafeクラスを過度に正しく使用しないと、プログラムエラーの確率が高くなり、Javaという安全な言語が「安全」にならなくなるので、Unsafeの使用には慎重にしなければなりません.
jdk 1で.9では,Usafeを削除したため,Usafeに基づいて開発されたフレームワークは徐々に死んでしまった. valueOffsetはlongタイプであり、ここではオブジェクトメンバー変数valueのオブジェクトメモリアドレスに対するオフセット量 を意味する.
valueOffsetの付与値はstaticコードブロック、すなわちクラスロード初期化時に1回実行され、現在のオブジェクトメモリアドレスに対するvalueメンバー変数のオフセット量が取得される value変数volatile修飾を使用するとメモリの可視性が保証され、後のCASの可能性が提供されます.実際に格納されている値はvalueに格納されている です. incrementAndGetメソッド呼び出しチェーン:incrementAndGet()→unsafe.getAndAddInt(this, valueOffset, 1) + 1 → getAndAddInt(Object var1, long var2, int var4)
var 1:現在のオブジェクトに対応するthis;var 2対応オフセット量valueOffset;var 4は増分1に対応する.上のコードは
上の変数で置き換えるとvar 5しか残っていません.
これはnativeメソッドであり,実際にはvar 1におけるvar 2オフセット量の値を取得する.var 1はAtomicIntegerであり、var 2は前述したvalueOffsetであり、メモリから現在のvalueOffsetの値、すなわち現在のvalueの値を取得します.
getAndAddIntメソッド実行ロジック:は、getIntVolatile(this,valueOffset)によってexpect(所望値)として現在のvalueの値を取得する. compareAndSwapIntメソッドの意味:this内のvalueとexpectが等しい場合、他のスレッドがこの変数を変更したことがないことを証明すると、updateに更新され、このステップのCASが成功しなければ、スピン方式(無限ループ)でCAS動作 を継続する.
CPU原語
CAS、比較して交換します.一見これも2つのステップでしょうが、実はJNIでは1つのCPUコマンド(cmpxchgl)で完了しています.だから原子操作です
CAS欠陥
ABA問題問題説明 CASは、値を操作するときに値が変化しているかどうかをチェックし、変化がなければ更新する必要がありますが、1つの値がAでBになり、Aになった場合、CASを使って検査すると値が変化していないことがわかりますが、実際には変化しています.これがCASのABA問題です.解決策 一般的な解決策は、バージョン番号を使用することです.変数の前にバージョン番号を追加し、変数が更新されるたびにバージョン番号を1つ追加すると、A-B-Aは1 A-2 B-3 Aになります.現在、JDKのatomicパッケージにはABA問題を解決するためのクラスAtomicStampedReferenceが提供されています.このクラスのcompareAndSetメソッドは、まず、現在の参照が所望の参照に等しいかどうかを確認し、現在のフラグが所望のフラグに等しいかどうかを確認し、すべてが等しい場合、その参照とフラグの値を所定の更新値に原子的に設定することです. AtomicStampedReference原理解析 AtomicStampedReferenceは、バージョン番号が付けられたAtomicReferenceです.初期の参照変数initialRefのほかに、参照変数を一意に識別するためにinitialStamp変数があります.initialStampはバージョン番号(またはタイムスタンプ)です.
ソースコードは次のとおりです.例:
サイクル時間が長いとオーバーヘッドが大きい
CASが成功しなければその場でスピンし,長時間スピンするとCPUに非常に大きな実行オーバーヘッドをもたらすと述べた.
単一の共有変数に対してのみ原子的な操作を保証できます.
このときはロックを使うか、複数の共有変数を1つの共有変数に統合して操作する方法があります.例えば、2つの共有変数i=2,j=aがあり、ij=2 aをマージしてCASでijを操作する.Java 1から5からJDKはAtomicReferenceクラスを提供して参照オブジェクト間の原子性を保証し、複数の変数を1つのオブジェクトに配置してCAS操作を行うことができます. AtomicReference原理解析AtomicReferenceは、オブジェクト参照を原子的に更新することです.ソースコードは次の です.
上記のソースコードから、AtomicReferenceは汎用定義を使用していることがわかります.特定の変数(AtomicIntegerなど)ではなく、オブジェクト参照を操作することで、共有変数だけでなく共有リソースオブジェクトを操作できます.(具体的な原理は上のAtomicIntegerの原理解析を参考にすることができ、大同小異で、intタイプのvalueをオブジェクト参照Vに変えただけです)例
意味
CAS(CompareAndSwap)は、コンカレントアルゴリズムを実装する際によく用いられる技術である.CAS操作には、メモリ位置、予想値、および新しい値の3つの操作数が含まれます.CAS操作を実行するときは、メモリの位置の値を予想した値と比較し、一致するとプロセッサは自動的にその位置の値を新しい値に更新します.そうしないと、プロセッサは何もしません.
楽観ロックの意味は衝突が発生していないと仮定することであり、私はちょうどある操作を行うことができます.もし衝突が発生したら、私は成功するまで再試行します.楽観ロックで最もよく見られるのはCASです.ReenterLock内部のAQSも,各種Atomicの先頭の原子類も,内部はCASに適用されている.
げんりぶんせき
java.util.concurrent.atomic.***AtomicInteger***を例に分析
/**
* An {@code int} value that may be updated atomically. See the
* {@link java.util.concurrent.atomic} package specification for
* description of the properties of atomic variables. An
* {@code AtomicInteger} is used in applications such as atomically
* incremented counters, and cannot be used as a replacement for an
* {@link java.lang.Integer}. However, this class does extend
* {@code Number} to allow uniform access by tools and utilities that
* deal with numerically-based classes.
*
* @since 1.5
* @author Doug Lea
*/
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;
/**
* Atomically increments by one the current value.
*
* @return the updated value
*/
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
...
}
jdk 1で.9では,Usafeを削除したため,Usafeに基づいて開発されたフレームワークは徐々に死んでしまった.
valueOffsetの付与値はstaticコードブロック、すなわちクラスロード初期化時に1回実行され、現在のオブジェクトメモリアドレスに対するvalueメンバー変数のオフセット量が取得される
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
var 1:現在のオブジェクトに対応するthis;var 2対応オフセット量valueOffset;var 4は増分1に対応する.上のコードは
public final int getAndAddInt(Object this,long valueOffset,int 1){
int var5;
do {
var5 = this.getIntVolatile(this, valueOffset);
} while(!this.compareAndSwapInt(this, valueOffset, var5, var5 + 1));
return var5;
}
上の変数で置き換えるとvar 5しか残っていません.
var5 = this.getIntVolatile(this, valueOffset);
これはnativeメソッドであり,実際にはvar 1におけるvar 2オフセット量の値を取得する.var 1はAtomicIntegerであり、var 2は前述したvalueOffsetであり、メモリから現在のvalueOffsetの値、すなわち現在のvalueの値を取得します.
public final int getAndAddInt(Object this,long valueOffset,int 1){
int expect;
do {
expect = this.getIntVolatile(this, valueOffset);
} while(!this.compareAndSwapInt(this, valueOffset, expect, update));
return expect;
}
getAndAddIntメソッド実行ロジック:
CPU原語
CAS、比較して交換します.一見これも2つのステップでしょうが、実はJNIでは1つのCPUコマンド(cmpxchgl)で完了しています.だから原子操作です
CAS欠陥
ABA問題
ソースコードは次のとおりです.
/**
* An {@code AtomicStampedReference} maintains an object reference
* along with an integer "stamp", that can be updated atomically.
*
* Implementation note: This implementation maintains stamped
* references by creating internal objects representing "boxed"
* [reference, integer] pairs.
*
* @since 1.5
* @author Doug Lea
* @param The type of object referred to by this reference
*/
public class AtomicStampedReference<V> {
private static class Pair<T> {
final T reference; //
final int stamp; // ，
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
static <T> Pair<T> of(T reference, int stamp) {
return new Pair<T>(reference, stamp);
}
}
private volatile Pair<V> pair;
/**
* Creates a new {@code AtomicStampedReference} with the given
* initial values.
*
* @param initialRef the initial reference
* @param initialStamp the initial stamp
*/
public AtomicStampedReference(V initialRef, int initialStamp) {
pair = Pair.of(initialRef, initialStamp);
}
/**
* Returns the current value of the reference.
*
* @return the current value of the reference
*/
public V getReference() {
return pair.reference;
}
/**
* Returns the current value of the stamp.
*
* @return the current value of the stamp
*/
public int getStamp() {
return pair.stamp;
}
...
/**
* Atomically sets the value of both the reference and stamp
* to the given update values if the
* current reference is {@code ==} to the expected reference
* and the current stamp is equal to the expected stamp.
*
* @param expectedReference the expected value of the reference
* @param newReference the new value for the reference
* @param expectedStamp the expected value of the stamp
* @param newStamp the new value for the stamp
* @return {@code true} if successful
*/
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
...
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
private static final long pairOffset =
objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);
private boolean casPair(Pair<V> cmp, Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}
static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
String field, Class<?> klazz) {
try {
return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
} catch (NoSuchFieldException e) {
// Convert Exception to corresponding Error
NoSuchFieldError error = new NoSuchFieldError(field);
error.initCause(e);
throw error;
}
}
}
AtomicStampedReference atomicStampedReference = new AtomicStampedReference(new Integer(100), 1);
List<Thread> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
Thread thread = new Thread(() -> {
boolean flag = false;
do {
int stamp = atomicStampedReference.getStamp();
flag = atomicStampedReference.compareAndSet((Integer) atomicStampedReference.getReference(), Integer.valueOf((Integer) ((Integer) atomicStampedReference.getReference()).intValue() + 1), stamp, stamp + 1);
} while (!flag);
});
list.add(thread);
thread.start();
}
list.forEach(t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
System.out.println((Integer) atomicStampedReference.getReference()); // 1100
サイクル時間が長いとオーバーヘッドが大きい
CASが成功しなければその場でスピンし,長時間スピンするとCPUに非常に大きな実行オーバーヘッドをもたらすと述べた.
単一の共有変数に対してのみ原子的な操作を保証できます.
このときはロックを使うか、複数の共有変数を1つの共有変数に統合して操作する方法があります.例えば、2つの共有変数i=2,j=aがあり、ij=2 aをマージしてCASでijを操作する.Java 1から5からJDKはAtomicReferenceクラスを提供して参照オブジェクト間の原子性を保証し、複数の変数を1つのオブジェクトに配置してCAS操作を行うことができます.
/**
* An object reference that may be updated atomically. See the {@link
* java.util.concurrent.atomic} package specification for description
* of the properties of atomic variables.
* @since 1.5
* @author Doug Lea
* @param The type of object referred to by this reference
*/
public class AtomicReference<V> implements java.io.Serializable {
private static final long serialVersionUID = -1848883965231344442L;
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicReference.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile V value;
/**
* Creates a new AtomicReference with the given initial value.
*
* @param initialValue the initial value
*/
public AtomicReference(V initialValue) {
value = initialValue;
}
/**
* Creates a new AtomicReference with null initial value.
*/
public AtomicReference() {
}
/**
* Atomically sets the value to the given updated value
* if the current value {@code ==} the expected value.
* @param expect the expected value
* @param update the new value
* @return {@code true} if successful. False return indicates that
* the actual value was not equal to the expected value.
*/
public final boolean compareAndSet(V expect, V update) {
return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
}
/**
* Atomically updates the current value with the results of
* applying the given function, returning the updated value. The
* function should be side-effect-free, since it may be re-applied
* when attempted updates fail due to contention among threads.
*
* @param updateFunction a side-effect-free function
* @return the updated value
* @since 1.8
*/
public final V updateAndGet(UnaryOperator<V> updateFunction) {
V prev, next;
do {
prev = get();
next = updateFunction.apply(prev);
} while (!compareAndSet(prev, next));
return next;
}
...
}
上記のソースコードから、AtomicReferenceは汎用定義を使用していることがわかります.特定の変数(AtomicIntegerなど)ではなく、オブジェクト参照を操作することで、共有変数だけでなく共有リソースオブジェクトを操作できます.(具体的な原理は上のAtomicIntegerの原理解析を参考にすることができ、大同小異で、intタイプのvalueをオブジェクト参照Vに変えただけです)
AtomicReference<Integer> ref = new AtomicReference<>(new Integer(1000));
List<Thread> list = new ArrayList<>();
UnaryOperator<Integer> integerUnaryOperator = x -> x + 1;
for(int i=0;i<1000;i++){
Thread thread = new Thread( ()->{ref.updateAndGet(integerUnaryOperator);});
list.add(thread);
thread.start();
}
list.forEach( t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
System.out.println(ref.get()); // 2000