CAS指令与MESI缓存一致性协议、 “轻量级锁” 与原子操作

“最轻量级的锁”,通常也叫”原子操作”,之所以加引号是因为他们在汇编级别并不是原子操作,是用多条指令完成的,这些操作大多都是利用CPU支持的汇编指令.

CAS（Compare-And-Swap）指令是并行程序设计最基础的基石。

CAS指令，在Intel CPU上称为CMPXCHG。最常见的原子操作有Compare and Exchange,Self Increase/Decrease等等

80486 CPU相关指令：

LOCK:这是一个指令前缀，在所对应的指令操作期间使此指令的目标操作数指定的存储区域锁定，以得到保护。

XADD:先交换两个操作数的值，再进行算术加法操作。多处理器安全，在80486及以上CPU中支持。

CMPXCHG:比较交换指令，第一操作数先和AL/AX/EAX比较，如果相等ZF置1，第二操作数赋给第一操作数，否则ZF清0，第一操作数赋给AL/AX/EAX。多处理器安全，在80486及以上CPU中支持。

XCHG:交换两个操作数,其中至少有一个是寄存器寻址.其他寄存器和标志位不受影响.

80486以上都支持这四个操作,因此当今几乎100%CPU都支持这两个指令

这一系列操作是原子的，不可能被中断。基本上所有的同步机制，与信号量、Java中的synchronized等的实现最终都要用到CAS指令，即使锁无关的数据结构也离不开CAS指令。

CMPXCHG指令详解

cmpxchg是汇编指令  

作用：比较并交换操作数

这条指令将al\ax\eax\rax中的值与首操作数比较:

1.如果相等，第2操作数的直装载到首操作数，zf置1。(相当于相减为0，所以0标志位置位)

2.如果不等， 首操作数的值装载到al\ax\eax\rax，并将zf清0

例如：

CMPXCHG CX,DX


首操作数： CX
第2操作数：DX

(1) 如果指令执行前:

(AX) = 2300H
(CX) = 2300H
(DX) = 2400H

则指令执行后, 因（CX）= (AX), 故
第2操作数(DX)直装载到首操作数(CX)，ZF置1。
(CX)=2400H,ZF=1

(2) 如果指令执行前:

(AX) = 2500H
(CX) = 2300H
(DX) = 2400H

则指令执行后因首操作数（CX）不等于（AX）， 即（CX）!=(AX) 。
寄存器（ al\ax\eax\rax ）中的值与首操作数（CX）不等， 那么首操作数的值 （CX）直接装载到al\ax\eax\rax中，即（AX）= （CX 的值2300H），并将zf清0。

最终得到：

(AX)=2300H，ZF=0

CMPXCHG隐含使用EAX寄存器。象这种隐含使用其他寄存器的指令还有不少。对于哪种操作影响标志位也需要慢慢熟悉。

Compares the value in the AL, AX, or EAX register (depending on the size of the operand) 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, or EAX register.
This instruction can be used with a LOCK prefix to allow the instruction to be executed atomi-cally. 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.)
参考: Intel文档 http://faydoc.tripod.com/cpu/cmpxchg.htm

MESI 缓存一致性协议

关于CAS指令最著名的传闻是CAS需要锁总线，因此CAS指令不但慢而且会严重影响系统并发度，即使没有冲突是也一样。不过在较新的CPU中（对于Intel CPU来说是486之后），事实并非如此。目前的CPU一般都采用了很好的缓存一致性协议，在很多情况下能够防止锁总线的发生，这其中最著名的就是Intel CPU中使用的MESI缓存一致性协议。

先来说说缓存一致性问题。为了提高数据访问效率，每个CPU上都有一个容量很小（现在一般是1M这个数量级），速度很快的缓存，用于缓存最常访问的那些数据。由于操作内存的速度实在太慢，数据被修改时也只更新缓存，并不直接写出到内存中去，这一来就造成了缓存中的数据与内存不一致。如果系统中只有一个CPU，所有线程看到的都是缓存中的最新数据，当然没问题。但如果系统中有多个CPU，同一份内存可能会被缓存到多个CPU中，如果在不同CPU中运行的不同线程看到同一份内存的缓存值不一样就麻烦了，因此有必要维护这多种缓存的一致性。当然要做到这一点只要一有修改操作，就通知所有CPU更新缓存，或者放弃缓存下次访问的时候再重新从内存中读取。但这 Stupid 的实现显然不会有好的性能，为解决这一问题，产生了很多维护缓存一致性的协议，MESI就是其中一种。

MESI协议的名称由来是指这一协议为缓存的每个数据单位（称为cache line，在Intel CPU上一般是64字节）维护两个状态位，使得每个数据单位可能处于M、E、S或I这四种状态之一。各种状态含义如下：

• M: 被修改的。处于这一状态的数据只在本CPU中有缓存，且其数据已被修改，没有更新到内存中

• E: 独占的。处于这一状态的数据只在本CPU中有缓存，且其数据没有被修改，与内存一致

• S: 共享的。处于这一状态的数据在多个CPU中有缓存

• I: 无效的。本CPU中的这份缓存已经无效了。

当CPU要读取数据时，只要缓存的状态不是I都可以从缓存中读，否则就要从主存中读。这一读操作可能会被某个处于M或E状态的CPU截获，该CPU将修改的数据写出到内存，并将自己设为S状态后这一读操作才继续进行。只有缓存状态是E或M时，CPU才可以修改其中的数据，修改后缓存即处于M状态。如果CPU要修改数据时发现其缓存不处于E或M状态，则需要发出特殊的RFO指令（Read For Ownership），将其它CPU的缓存设为I状态。

因此，如果一个变量在某段时间内只被一个线程频繁修改，则对应的缓存早就处于M状态，这时CAS操作就不会涉及到总线操作。所以频繁的加锁并不一定会影响系统并发度，关键是看锁冲突的情况严重不严重，如果经常出现冲突，即缓存一会被这个CPU独占，一会被那个CPU独占，这时才会不断产生RFO，影响到并发性能。

compareAndSwapInt 源码实现分析

在Java中的JamVM natives.c 的源码如下：

// compareAndSwapInt(this, offset, var5, var5 + 1)

//JamVM natives.c

uintptr_t *compareAndSwapInt(Class *class, MethodBlock *mb, uintptr_t *ostack) {

    long long offset = *((long long *)&ostack[2]);

    unsigned int *addr = (unsigned int*)((char *)ostack[1] + offset);

    unsigned int expect = ostack[4];

    unsigned int update = ostack[5];

    int result;

    //调用平台CPU特定的汇编代码实现

    result = COMPARE_AND_SWAP_32(addr, expect, update);

    *ostack++ = result;

    return ostack;

}

x86-64 的汇编实现宏

#define COMPARE_AND_SWAP_32(addr, old_val, new_val)        \

({                                                         \

    char result;                                           \

    __asm__ __volatile__ ("                                \

        lock;                                              \

        cmpxchgl %4, %1;                                   \

        sete %0"                                           \

    : "=q" (result), "=m" (*addr)/*out*/                   \

    : "m" (*addr), "a" (old_val), "r" (new_val) /*in*/     \

    : "memory");     /*Clobbers, reload from memory*/      \

    result;                                                \

})

COMPARE_AND_SWAP_32的伪代码如下

//下文的 <- 指赋值的意思，Intel文档也是这样写的

--INPUT:

rcx <- memory <- addr

al <- old_val

esi <- new_val

--OUTPUT:

rax <- result

rcx <-memory <- addr

--PROCEDURE:

//cmpxchg dword [ds:rcx], esi

IF al == rcx

THEN

  ZF <- 1;

  rcx <- esi;

ELSE

  ZF <- 0;

  al <- rcx;

FI;

//sete       al

IF ZF == 1

THEN

  al <- 0;

ELSE

  al <- 1;

FI;

//movsx      rax, al

rax <- al

return rax

用C语言简化是这样的

if(old_val == *addr){ // 这里的相等，判断的是什么？ EAX 寄存器中的值与当前操作数的值比较？

  *addr = new_val;  // 把新的值赋给 *addr

  return true;

} else{

  old_val = *addr;

  return false;

}