Java CAS(Compare And Swap)

CAS

CAS(Compare And Swap)是一种比较再交换技术。

 

在我们绝大多数CPU处理器中都支持CAS这种技术，不同CPU处理器在实现CAS操作时大同小异，所以在实现时存在不同的变体，但大体类似。

 

在x86等intel处理器中通过CMPXCHG实现CAS操作。如x86，来自https://www.felixcloutier.com/x86/cmpxchg的资料：

https://www.felixcloutier.com/x86/cmpxchg 写道

Description

Compares the value in the AL, AX, EAX, or RAX register with the first operand (destination operand). If the two values are equal, the second operand (source operand) is loaded into the destination operand. Otherwise, the destination operand is loaded into the AL, AX, EAX or RAX register. RAX register is available only in 64-bit mode.

This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically. To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)

In 64-bit mode, the instruction’s default operation size is 32 bits. Use of the REX.R prefix permits access to additional registers (R8-R15). Use of the REX.W prefix promotes operation to 64 bits. See the summary chart at the beginning of this section for encoding data and limits.

还有来自https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b的资料：

https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b 写道

Description

Compares the 64-bit value in EDX:EAX (or 128-bit value in RDX:RAX if operand size is 128 bits) with the operand (destination operand). If the values are equal, the 64-bit value in ECX:EBX (or 128-bit value in RCX:RBX) is stored in the destination operand. Otherwise, the value in the destination operand is loaded into EDX:EAX (or RDX:RAX). The destination operand is an 8-byte memory location (or 16-byte memory location if operand size is 128 bits). For the EDX:EAX and ECX:EBX register pairs, EDX and ECX contain the high-order 32 bits and EAX and EBX contain the low-order 32 bits of a 64-bit value. For the RDX:RAX and RCX:RBX register pairs, RDX and RCX contain the high-order 64 bits and RAX and RBX contain the low-order 64bits of a 128-bit value.

This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically. To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)

In 64-bit mode, default operation size is 64 bits. Use of the REX.W prefix promotes operation to 128 bits. Note that CMPXCHG16B requires that the destination (memory) operand be 16-byte aligned. See the summary chart at the beginning of this section for encoding data and limits. For information on the CPUID flag that indicates CMPXCHG16B, see page 3-212.

 

CMPXCHG — Compare and Exchange

Opcode/Instruction Op/En 64-Bit Mode Compat/Leg Mode Description

0F B0/r CMPXCHG r/m8, r8	MR	Valid	Valid*	Compare AL with r/m8. If equal, ZF is set and r8 is loaded into r/m8. Else, clear ZF and load r/m8 into AL.
REX + 0F B0/r CMPXCHGr/m8**,r8	MR	Valid	N.E.	Compare AL with r/m8. If equal, ZF is set and r8 is loaded into r/m8. Else, clear ZF and load r/m8 into AL.
0F B1/r CMPXCHG r/m16, r16	MR	Valid	Valid*	Compare AX with r/m16. If equal, ZF is set and r16 is loaded into r/m16. Else, clear ZF and load r/m16 into AX.
0F B1/r CMPXCHG r/m32, r32	MR	Valid	Valid*	Compare EAX with r/m32. If equal, ZF is set and r32 is loaded into r/m32. Else, clear ZF and load r/m32 into EAX.
REX.W + 0F B1/r CMPXCHGr/m64, r64	MR	Valid	N.E.	Compare RAX with r/m64. If equal, ZF is set and r64 is loaded into r/m64. Else, clear ZF and load r/m64 into RAX.

采用的Intel汇编语法格式。

 

 

 

 
 

汇编代码：

采用的AT&T汇编语法格式。

#define cmpxchg(ptr, _old, _new) {                       \
  volatile uint32_t *__ptr = (volatile uint32_t *)(ptr);   \
  uint32_t __ret;                                          \
  uint32_t __eax = 0;                                      \
                                                           \
  printf("__ret=%ld\n", __ret);                            \
                                                           \
  /* 这里__ret返回的就是寄存器eax的值 */                   \
  /* 这里__eax返回的就是寄存器eax的值，也就等于__ret */    \
  asm volatile( "lock; cmpxchgl %2,%1"           \
    : "=a" (__ret), "+m" (*__ptr)                \
    : "r" (_new), "0" (_old)                     \
    : "memory");				                 \
                                                 \
  asm("mov %%eax, %0"                            \
    : "=d" (__eax));                             \
                                                 \
  printf("__eax=%ld\n", __eax);                  \
  printf("__ret=%ld\n", __ret);                  \
  __ret;                                  \
}

上面代码还可以写成这样：

asm volatile( "lock cmpxchgl %2,%1"  
    : "=a" (__ret), "+m" (*__ptr)          
    : "r" (_new), "0" (_old)                 
    : "memory");				

 

 

int __cmpxchg(int *ptr, int expect, int value) cmpxchg(ptr, expect, value)
int compare_and_swapi(int *ptr, int expect, int value) 
{
  return __cmpxchg(ptr, expect, value) == expect;
}

 

int i= 1000;
int ret = compare_and_swapi(&i, i, 1234);
printf("ret=%ld\n", ret);

核心汇编代码

___cmpxchg:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%esi
	pushl	%ebx
	subl	$32, %esp
	movl	8(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	$0, -16(%ebp)
	movl	$0, -20(%ebp)
	movl	-24(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$LC4, (%esp)
	call	_printf
	movl	-12(%ebp), %esi
	movl	16(%ebp), %edx
	movl	12(%ebp), %eax
	movl	-12(%ebp), %ecx
	movl	%eax, %ebx
	movl	%ebx, %eax
/APP
 # 119 "compareAndSwapTest.c" 1
	lock; cmpxchgl %edx,(%esi)
 # 0 "" 2
/NO_APP
	movl	%eax, %ebx
	movl	%ebx, -24(%ebp)
/APP
 # 119 "compareAndSwapTest.c" 1
	mov %eax, %edx
 # 0 "" 2
/NO_APP
	movl	%edx, %ebx
	movl	%ebx, -16(%ebp)
	movl	-20(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$LC5, (%esp)
	call	_printf
	movl	-16(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$LC6, (%esp)
	call	_printf
	movl	-24(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$LC4, (%esp)
	call	_printf
	movl	-24(%ebp), %eax
	addl	$32, %esp
	popl	%ebx
	popl	%esi
	popl	%ebp
	ret

 

有关CAS可参考另一篇文章：https://lobin.iteye.com/blog/2327437

 

Java也支持CAS操作，Java Unsafe提供了硬件级别的CAS操作。Java作为一种高级语言不能直接操作硬件，在实现CAS操作时并不是在Java层面做的，而是通过本机接口来实现，实现原理也用到CPU处理器对CAS的硬件支持。

 

受限于底层硬件的支持，如是否支持cmpxchg8，如果CPU不支持，Java本机实现时也会采用软件实现CAS操作。

 

在JAVA中，Unsafe类针对CAS操作提供了3个方法：compareAndSwapInt、compareAndSwapLong、compareAndSwapObject。

 

CAS操作是原子操作吗？

上面提到，CAS是一种比较再交换技术，也就是它包括两个操作：先执行比较操作，还进行更新操作（即交换）。

这样来看，CAS就不是原子操作。但我们这里说的CAS指的是cmpxchg指令操作，或者说cmpxchg指令操作本身不是原子操作。

 

我们常说CAS原子操作, 比如在Java中，CAS操作是原子操作，在反编译出汇编代码后，cmpxchg指令前面有个LOCK前缀的，真正保证CAS操作是原子操作的其实是这个LOCK前缀。

 

如上面汇编代码lock; cmpxchgl %edx,(%esi)这一行。

 

Java中CAS的应用

Java中用到CAS的地方很多，基本上用到sun.misc.Unsafe这个类的地方都应用了CAS。该类在jdk\src\share\classes\sun\misc目录下。

 

Java原子变量(java.util.concurrent.atomic)，以Atomic*前缀，如java.util.concurrent.atomic.AtomicInteger，java.util.concurrent.atomic.AtomicLong，java.util.concurrent.atomic.AtomicReference都用到CAS，以实现变量的原子操作。

 

还有AQS，java.util.concurrent.locks.AbstractQueuedSynchronizer，java.util.concurrent.locks.AbstractQueuedLongSynchronizer

比如java.util.concurrent.CountDownLatch.Sync，java.util.concurrent.FutureTask.Sync，java.util.concurrent.locks.ReentrantLock，java.util.concurrent.locks.ReentrantLock.FairSync，java.util.concurrent.locks.ReentrantLock.NonfairSync，java.util.concurrent.locks.ReentrantReadWriteLock.Sync，java.util.concurrent.locks.ReentrantReadWriteLock.FairSync，java.util.concurrent.locks.ReentrantReadWriteLock.NonfairSync，java.util.concurrent.Semaphore.Sync，java.util.concurrent.Semaphore.FairSync，java.util.concurrent.Semaphore.NonfairSync等。

 

 

 

在解释CAS的时候，存在这样一个问题：假设一个线程在对某个变量执行CAS操作时，变量的初始值为A（实际值），线程将变量更新为B，在这个过程中，线程读取变量值A（期望值），在更新变量值为B的时候，先比较变量的实际值和期望值，即判断变量的值是否为A，如果实际值和期望值一致，则更新变量的值为B，但在线程比较变量的实际值和期望值是否一致之前，另一个线程同时也对该变量执行CAS操作，它先将变量更新为B，之后再将变量更新为A，如果这个时候在切换到第一个线程，线程比较变量的实际值和期望值时，发现发现实际值和期望值一致，则将变量的值更新为B。在这个过程中，第一个线程在将变量的值由A更新为B的时候，另一个线程已经将变量的值由A更新为B再更新为A，所以实际上变量的值已经更新了，只是它重新将变量的值更新回B了，但第一个线程没有感知到这个变化，认为变量的值没有变化。

 

这就是我们所说的ABA问题。

 

大多数CPU处理器在支持CAS这种操作时都没有考虑这种ABA问题。所以针对这种情况，我们需要自己解决这种问题。

 

为了解决ABA问题，我们在对变量（数据）执行CAS操作时，给变量（数据）携带一个状态，这样原来对变量（数据）执行CAS操作变成对(变量/数据，状态)执行CAS操作， 即(变量/数据，状态)作为一个整体就是CAS操作的变量（数据），每次CAS操作时同时比较变量/数据，状态，在更新变量（数据）同时更新它的状态。

 

Java在实现原子变量的时候，绝大多数，以Atomic-为前缀的都没有考虑ABA问题。

 

但AtomicStampedReference，以AtomicStamped-为前缀，解决了ABA问题。AtomicStampedReference在解决ABA问题问题时和上面的思路差不多，AtomicStampedReference给要更新的变量/数据打了个标记，这类似上面的状态。但AtomicStampedReference在执行CAS操作时要指定期望的变量/数据，标记，这个其实可以不需要。另外在更新时还需要指定新的标记。

 

这里有个疑问，既然我们说CAS操作是原子操作的话，为什么会产生ABA问题呢？这里要说处理器支持的cmpxchg指令操作（CAS操作）不是原子操作，那会产生ABA问题，这个还要理解。但是如果我们从Java的CAS操作来看，它是原子操作的，反编译出的汇编指令包含LOCK前缀，那么怎么还会有ABA问题呢？

 

Java对CAS操作支持的内部实现，参考另一篇文章：https://lobin.iteye.com/blog/2311755