Compare and Swap:修订间差异

来自WHY42
Riguz留言 | 贡献
无编辑摘要
Riguz留言 | 贡献
无编辑摘要
 
(未显示同一用户的3个中间版本)
第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


= 实现机制=
= 实现机制=
第89行: 第106行:
* [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]]

2024年1月18日 (四) 09:02的最新版本

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

要实现无锁(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实现如下:

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;
}

在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中的大多数类在实现时都直接或间接的使用了这些原子变量类。

实现机制

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

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);
    }
    // ...
}

这里的操作调用了Unsafe类来实现,而这个Unsafe类里面的实代码是这样的:

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;
}

而最终是用到了native的方法compareAndSwapInt,这部分的源码可以在OpenJDK源码中找到,而最终是会调用到CMPXCHG这样到CPU指令来完成CAS。

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

其中,源码位于:

ABA问题

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

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

 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)));
 }

References: