Compare and Swap - 版本历史

2024年1月18日 (四) 09:02 Riguz

2024-01-18T09:02:36Z

←上一版本		2024年1月18日 (四) 09:02的版本
第1行：		第1行：

	CAS：Compare and Swap，即比较再交换。jdk5增加了并发包<span class="article-label">java.util.concurrent.*</span>,其下面的类使用CAS算法实现了区别于<span class="article-label">synchronized</span>同步锁的一种乐观锁。		CAS：Compare and Swap，即比较再交换。jdk5增加了并发包<span class="article-label">java.util.concurrent.*</span>,其下面的类使用CAS算法实现了区别于<span class="article-label">synchronized</span>同步锁的一种乐观锁。

			要实现无锁（lock-free）的非阻塞算法有多种实现方法，其中 CAS（比较与交换，Compare and swap）是一种有名的无锁算法。CAS, CPU指令，在大多数处理器架构，包括IA32、Space中采用的都是CAS指令，CAS的语义是“我认为V的值应该为A，如果是，那么将V的值更新为B，否则不修改并告诉V的值实际为多少”，CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。CAS无锁算法的C实现如下：
			<source lang="c">
			int compare_and_swap (int* reg, int oldval, int newval)
			{
			ATOMIC();
			int old_reg_val = *reg;
			if (old_reg_val == oldval)
			*reg = newval;
			END_ATOMIC();
			return old_reg_val;
			}
			</source>
			在JDK1.5之前，如果不编写明确的代码就无法执行CAS操作，在JDK1.5中引入了底层的支持，在int、long和对象的引用等类型上都公开了CAS的操作，并且JVM把它们编译为底层硬件提供的最有效的方法，在运行CAS的平台上，运行时把它们编译为相应的机器指令，如果处理器/CPU不支持CAS指令，那么JVM将使用自旋锁。因此，值得注意的是， CAS解决方案与平台/编译器紧密相关（比如x86架构下其对应的汇编指令是lock cmpxchg，如果想要64Bit的交换，则应使用lock cmpxchg8b。在.NET中我们可以使用Interlocked.CompareExchange函数）。

			在原子类变量中，如java.util.concurrent.atomic中的AtomicXXX，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些原子变量类。
			*refer:http://www.tuicool.com/articles/zuui6z

	= 实现机制=		= 实现机制=

Riguz：Riguz移动页面CAS至Compare and Swap，不留重定向

2024-01-18T09:02:05Z

Riguz移动页面CAS至Compare and Swap，不留重定向

←上一版本	2024年1月18日 (四) 09:02的版本
（没有差异）

Riguz：Riguz移动页面Blog:理解Java并发(3)：CAS至CAS，不留重定向

2023-12-19T06:49:07Z

Riguz移动页面Blog:理解Java并发(3)：CAS至CAS，不留重定向

←上一版本	2023年12月19日 (二) 06:49的版本
（没有差异）

2021年4月28日 (三) 13:29 Riguz

2021-04-28T13:29:57Z

←上一版本		2021年4月28日 (三) 13:29的版本
第89行：		第89行：
	* [https://blogs.oracle.com/dave/biased-locking-in-hotspot Biased Locking in HotSpot]		* [https://blogs.oracle.com/dave/biased-locking-in-hotspot Biased Locking in HotSpot]
	* http://gee.cs.oswego.edu/dl/jmm/cookbook.html		* http://gee.cs.oswego.edu/dl/jmm/cookbook.html

			[[Category:Concurrency]]

2021年4月28日 (三) 13:29 Riguz

2021-04-28T13:29:32Z

←上一版本		2021年4月28日 (三) 13:29的版本
第1行：		第1行：

	CAS：Compare and ~~Swap，即比较再交换。jdk5增加了并发包java~~.util.concurrent.*,~~其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。~~		CAS：Compare and Swap，即比较再交换。jdk5增加了并发包<span class="article-label">java.util.concurrent.*</span>,其下面的类使用CAS算法实现了区别于<span class="article-label">synchronized</span>同步锁的一种乐观锁。

	= 实现机制=		= 实现机制=

	~~在Java中很多原子操作是通过CAS实现的，是一种无锁的方式，比如AtomicIntger的自增操作：~~		在Java中很多原子操作是通过CAS实现的，是一种无锁的方式，比如<syntaxhighlight lang="java" inline>AtomicIntger</syntaxhighlight>的自增操作：

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
第30行：		第30行：

	</syntaxhighlight>		</syntaxhighlight>
	~~这里的操作调用了Unsafe类来实现，而这个Unsafe类里面的实代码是这样的：~~		这里的操作调用了<syntaxhighlight lang="java" inline>Unsafe</syntaxhighlight>类来实现，而这个<syntaxhighlight lang="java" inline>Unsafe</syntaxhighlight>类里面的实代码是这样的：

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
第43行：		第43行：
	</syntaxhighlight>		</syntaxhighlight>

	~~而最终是用到了native的方法compareAndSwapInt，这部分的源码可以在OpenJDK源码中找到，而最终是会调用到~~[https://www.felixcloutier.com/x86/cmpxchg CMPXCHG]这样到CPU指令来完成CAS。		而最终是用到了native的方法<syntaxhighlight lang="java" inline>compareAndSwapInt</syntaxhighlight>，这部分的源码可以在OpenJDK源码中找到，而最终是会调用到[https://www.felixcloutier.com/x86/cmpxchg CMPXCHG]这样到CPU指令来完成CAS。

	<syntaxhighlight lang="c++">		<syntaxhighlight lang="c++">
第63行：		第63行：
	使用CAS一个问题就是可能出现A-B-A问题，因为CAS到逻辑就是，假设更新到时候判断出值跟期望的一致那么就会进行更改；但实际值跟期望的一致并不能代表值没有发生过变化。可能的场景就是，值被改成别的然后又改回来了，就是从A-B，然后又变成A。		使用CAS一个问题就是可能出现A-B-A问题，因为CAS到逻辑就是，假设更新到时候判断出值跟期望的一致那么就会进行更改；但实际值跟期望的一致并不能代表值没有发生过变化。可能的场景就是，值被改成别的然后又改回来了，就是从A-B，然后又变成A。

	~~解决这个问题的思路在于，想办法标记出变化。通常的做法是利用版本号（而不是值），保证版本号每次都会变化。JDK中提供了AtomicStampedReference来解决A~~-B-A问题，实现如下：		解决这个问题的思路在于，想办法标记出变化。通常的做法是利用版本号（而不是值），保证版本号每次都会变化。JDK中提供了<syntaxhighlight lang="java" inline>AtomicStampedReference</syntaxhighlight>来解决A-B-A问题，实现如下：

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">

imported>Riguz：CAS：Compare and Swap，即比较再交换。jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。

2020-05-20T00:00:00Z

CAS：Compare and Swap，即比较再交换。jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。

新页面

CAS：Compare and Swap，即比较再交换。jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。

= 实现机制=

在Java中很多原子操作是通过CAS实现的，是一种无锁的方式，比如AtomicIntger的自增操作：

<syntaxhighlight lang="java">
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;
// ...
public final int getAndIncrement() {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
// ...
}

</syntaxhighlight>
这里的操作调用了Unsafe类来实现，而这个Unsafe类里面的实代码是这样的：

<syntaxhighlight lang="java">
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
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;
}
</syntaxhighlight>

而最终是用到了native的方法compareAndSwapInt，这部分的源码可以在OpenJDK源码中找到，而最终是会调用到[https://www.felixcloutier.com/x86/cmpxchg CMPXCHG]这样到CPU指令来完成CAS。

<syntaxhighlight lang="c++">
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
UnsafeWrapper("Unsafe_CompareAndSwapInt");
oop p = JNIHandles::resolve(obj);
jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
</syntaxhighlight>

其中，源码位于：

* [http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/tip/src/share/vm/prims/unsafe.cpp openjdk8/unsafe.cpp]
* [http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/tip/src/share/vm/runtime/atomic.cpp openjdk8/atomic.cpp]

= ABA问题=

使用CAS一个问题就是可能出现A-B-A问题，因为CAS到逻辑就是，假设更新到时候判断出值跟期望的一致那么就会进行更改；但实际值跟期望的一致并不能代表值没有发生过变化。可能的场景就是，值被改成别的然后又改回来了，就是从A-B，然后又变成A。

解决这个问题的思路在于，想办法标记出变化。通常的做法是利用版本号（而不是值），保证版本号每次都会变化。JDK中提供了AtomicStampedReference来解决A-B-A问题，实现如下：

<syntaxhighlight lang="java">
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)));
}
</syntaxhighlight>

References:

* https://docs.huihoo.com/javaone/2006/java_se/JAVA%20SE/TS-3412.pdf
* https://fliphtml5.com/tzor/bqxz/basic
* https://www.artima.com/insidejvm/ed2/index.html
* [https://wiki.openjdk.java.net/display/HotSpot/Synchronization OpenJDK Wiki - Synchronization]
* https://www.zhihu.com/question/53826114
* [https://blogs.oracle.com/dave/biased-locking-in-hotspot Biased Locking in HotSpot]
* http://gee.cs.oswego.edu/dl/jmm/cookbook.html

Compare and Swap - 版本历史

2024年1月18日 (四) 09:02 Riguz

Riguz：​Riguz移动页面CAS至Compare and Swap，不留重定向

Riguz：​Riguz移动页面Blog:理解Java并发(3)：CAS至CAS，不留重定向

2021年4月28日 (三) 13:29 Riguz

2021年4月28日 (三) 13:29 Riguz

imported>Riguz：​CAS：Compare and Swap，即比较再交换。jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。

Riguz：Riguz移动页面CAS至Compare and Swap，不留重定向

Riguz：Riguz移动页面Blog:理解Java并发(3)：CAS至CAS，不留重定向

imported>Riguz：CAS：Compare and Swap，即比较再交换。jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。