专栏首页一个会写诗的程序员的博客CAS指令与MESI缓存一致性协议、 “轻量级锁” 与原子操作CAS指令与MESI缓存一致性协议、 “轻量级锁” 与原子操作

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

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;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java 反射工具类 ReflectionUtil

    一个会写诗的程序员
  • 缓存雪崩 & 缓存穿透

    一个会写诗的程序员
  • Redis 设计与实现: redisObject 数据结构,以及 Redis 的数据类型

    redisObject 是 Redis 类型系统的核心, 数据库中的每个键、值,以及 Redis 本身处理的参数, 都表示为这种数据类型。

    一个会写诗的程序员
  • JAVA线程-CPU缓存和内存屏障(四)

    1.修改态(Modified),此cache行已被修改过(脏行),内容已不同于主存,为此cache专有。 2.专有态(Exclusive),此cache行内容同...

    IT故事会
  • 视频直播与虚拟现实的渲染 - OpenGL ES

    这是一篇OpenGL ES的学习笔记,介绍图像绘制里面用到的概念,学习OpenGL ES的基础知识备忘录。 教程 OpenGLES入门教程1-Tutorial0...

    落影
  • 原来 CPU 为程序性能优化做了这么多

    本文主要来学习内存屏障和 CPU 缓存知识,以便于我们去了解 CPU 对程序性能优化做了哪些努力。

    武培轩
  • 失联的架构师,只留下一段脚本

    我对Linux非常的精通,尤其是脚本语言比如sed、awk、python等,用起来更是炉火纯青。我把它作为自己一个非常特立独行的技能,一个和其他普通程序员区别开...

    xjjdog
  • LeetCode 543. 二叉树的直径(DFS)

    给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

    Michael阿明
  • Spring Cloud学习教程1【面试+工作】

    Java帮帮
  • FasterXML jackson-databind远程代码执行漏洞

    FasterXMLjackson-databind是一个简单基于Java应用库,Jackson可以轻松的将Java对象转换成json对象和xml文档,同样也可以...

    FB客服

扫码关注云+社区

领取腾讯云代金券