2020-05-19计算机基础9 分钟读完 (大约 1343 个字)

深挖CAS的底层实现

前言

代码层面，所有的锁在cpu层面都是一条条的指令，所有最终所有的锁，都要考底层指令的支持，CAS是代码层面比较常用的一种“无锁”,实际对应于cpu里面的几条指令，当然一个cpu有多个核下是如何解决锁的。在单核的时候，还可以通过关闭中断，来阻止操作系统调度。但是在多核的情况下，各个cpu是并行执行的，因此这个时候，就会出现，同时获取到锁的状态，而这个时候，通过禁止中断，是没有效果的，就需要引入一种机制实现多核本地缓存失效和内存全局的锁，涉及多级缓存的失效与同步，其实在计算机组成原理与操作系统里面有学的。

X86平台

基于JVM unsafe.compareAndSwapInt

可以看到jdk里面的都是native实现

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

    public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

可以在openjdk的源码src/share/vm/prims/unsafe.cpp里找到对应的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

我们可以通过c++的atmoic库进行调试，发现汇编层面

untitled1`atomic_worker:
->  0x10ce7fbed <+157>: lock   
    0x10ce7fbee <+158>: cmpxchgb %cl, (%rdx)
    0x10ce7fbf1 <+161>: sete   %cl
    0x10ce7fbf4 <+164>: testb  $0x1, %cl
    0x10ce7fbf7 <+167>: movb   %cl, -0x65(%rbp)
    0x10ce7fbfa <+170>: movb   %al, -0x66(%rbp)
    0x10ce7fbfd <+173>: jne    0x10ce7fc8f               ; <+319> [inlined] std::__1::__atomic_base<bool, false>::compare_exchange_strong(bool&, bool, std::__1::memory_order) + 249 at main.cpp:30
    0x10ce7fc03 <+179>: jmp    0x10ce7fc86               ; <+310> [inlined] std::__1::__atomic_base<bool, false>::compare_exchange_strong(bool&, bool, std::__1::memory_order) + 240 at main.cpp:30

lock与cmpxchgb

lock 并不是单独的一条可执行指令，你debug 使用next i 会发现是2条一起走了
LOCK前缀可确保CPU在操作期间对适当的高速缓存行具有排他性所有权，并提供某些其他排序保证。这可以通过声明总线锁定来实现，但是CPU会尽可能避免这种情况。如果总线被锁定，则仅在锁定指令期间。
cmpxchgb 系列就是真正的底层CAS的支持

ARM平台
基于android art

CompareAndSetWeakAcquire

// Atomically replace the value with desired_value if it matches the expected_value. Prior writes
 // made to other memory locations by the thread that did the release become visible in this
 // thread.
 bool CompareAndSetWeakAcquire(T expected_value, T desired_value) {
   return this->compare_exchange_weak(expected_value, desired_value, std::memory_order_acquire);
 }

通过ASdebug 得到native汇编

->  0x7ea6aa6964 <+220>: ldaxr  w10, [x22]
    //比较
    0x7ea6aa6968 <+224>: cmp    w10, w9
    //bne: 数据跳转指令，道标志寄存器中Z标志位不等于零时, 跳转到BNE后标签处
    0x7ea6aa696c <+228>: b.ne   0x7ea6aa693c              ; <+180> [inlined] std::__1::__atomic_base<int, false>::compare_exchange_weak(int&, int, std::__1::memory_order) at atomic.h:159
    0x7ea6aa6970 <+232>: stxr   w9, w8, [x22]

ldaxr stxr

Load-acquire exclusive register

ARMV8下的CAS并不是一条指令OK
Load-Acquire Exclusive Register derives an address from a base register value, loads a 32-bit word or 64-bit doubleword from memory, and writes it to a register. The memory access is atomic. The PE marks the physical address being accessed as an exclusive access. This exclusive access mark is checked by Store Exclusive instructions. See Synchronization and semaphores. The instruction also has memory ordering semantics as described in Load-Acquire, Store-Release. For information about memory accesses see Load/Store addressing modes.
内存访问是原子的。PE将要访问的物理地址标记为互斥访问
LDXR指令，将状态从open状态切换到exclusive状态，STXR指令，将状态从exclusive状态切换到open状态，这个就表示store exclusive操作成功。
为了解决多核情况下的锁竞争问题，arm引入了exclusive操作，并添加了相应的指令
exclusive的操作的核心，就是会将锁，用一个状态机进行维护，该状态机有2种状态，open状态和exclusive状态。要想成功的对锁进行上锁，状态必须要从exclusive状态切换到open状态，其他状态，都是失败的。
要达到目的，显然exclusive是对每个CPU核都是有效的

通过ldaxr/stxr指令实现在SMP系统中多核共享内存的互斥访问，也就是说原子操作是由独占访问指令”Load-Exclusive and Store-Exclusive”来实现的，其中最核心的地方在于系统通过exclusive monitor(一种简单的状态机)来监控独占访问。ldaxr/stxr可以保证任何情况下（包括被中断）的访问原子性。
STXR指令和普通的STR指令，不同的是，该指令有返回值，表示store exclusive是否成功。如果成功，ws为0，不成功，ws为1

参考

#Java

深挖CAS的底层实现

前言

X86平台

lock与cmpxchgb

ARM平台

CompareAndSetWeakAcquire

ldaxr stxr

参考

分类

最新文章

标签

目录