java cas

 

CPU原语-比较并交换(CompareAndSet),实现非阻塞算法

什么是CAS?
cas是现代CPU提供给并发程序使用的原语操作. 不同的CPU有不同的使用规范.

在 Intel 处理器中，比较并交换通过指令的 cmpxchg 系列实现。
PowerPC 处理器有一对名为“加载并保留”和“条件存储”的指令，它们实现相同的目地；
MIPS 与 PowerPC 处理器相似，除了第一个指令称为“加载链接”。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)

什么是非阻塞算法?
一个线程的失败或挂起不应该影响其他线程的失败或挂起.这类算法称之为非阻塞(nonblocking)算法

对比阻塞算法:
如果有一类并发操作, 其中一个线程优先得到对象监视器的锁, 当其他线程到达同步边界时, 就会被阻塞.
直到前一个线程释放掉锁后, 才可以继续竞争对象锁.(当然,这里的竞争也可是公平的, 按先来后到的次序)

CAS 原理:

我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可

 

CAS使用示例(jdk 1.5 并发包 AtomicInteger类分析:)

    /**
     * Atomically sets to the given value and returns the old value.
     *
     * @param newValue the new value
     * @return the previous value
     */
    public final int getAndSet(int newValue) {
        for (;;) {
            int current = get();
            if (compareAndSet(current, newValue))
                return current;
        }
    }

    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

这个方法是, AtomicInteger类的常用方法, 作用是, 将变量设置为指定值, 并返回设置前的值.
它利用了cpu原语compareAndSet来保障值的唯一性.

 

直接调用的是UnSafe这个类的compareAndSwapInt方法

 

 public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);

 

跟踪OpenJDK的源代码在hotspot\src\share\vm\prims\目录下可以找到unsafe.cpp

 

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

 

   Atomic类的cmpxchg方法

     hotspot\src\os_cpu\windows_x86\vm\目录的atomic_windows_x86.inline.hpp文件里

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}