Java CAS 原理分析,分享两道阿里P7究极难度算法题

前面说了 CAS 操作的流程,并不是很难。但仅有上面的说明还不够,接下来我将会再介绍一点其他的背景知识。有这些背景知识,才能更好的理解后续的内容。

2.背景介绍


我们都知道,CPU 是通过总线和内存进行数据传输的。在多核心时代下,多个核心通过同一条总线和内存以及其他硬件进行通信。如下图:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TSXZnVe1-1631373698813)(https://blog.csdn.net/)]

图片出处:《深入理解计算机系统》

上图是一个较为简单的计算机结构图,虽然简单,但足以说明问题。在上图中,CPU 通过两个蓝色箭头标注的总线与内存进行通信。大家考虑一个问题,CPU 的多个核心同时对同一片内存进行操作,若不加以控制,会导致什么样的错误?这里简单说明一下,假设核心1经32位带宽的总线向内存写入64位的数据,核心1要进行两次写入才能完成整个操作。若在核心1第一次写入32位的数据后,核心2从核心1写入的内存位置读取了64位数据。由于核心1还未完全将64位的数据全部写入内存中,核心2就开始从该内存位置读取数据,那么读取出来的数据必定是混乱的。

不过对于这个问题,实际上不用担心。通过 Intel 开发人员手册,我们可以了解到自奔腾处理器开始,Intel 处理器会保证以原子的方式读写按64位边界对齐的四字(quadword)。

根据上面的说明,我们可总结出,Intel 处理器可以保证单次访问内存对齐的指令以原子的方式执行。但如果是两次访存的指令呢?答案是无法保证。比如递增指令inc dword ptr [...],等价于DEST = DEST + 1。该指令包含三个操作读->改->写,涉及两次访存。考虑这样一种情况,在内存指定位置处,存放了一个为1的数值。现在 CPU 两个核心同时执行该条指令。两个核心交替执行的流程如下:

  1. 核心1 从内存指定位置出读取数值1,并加载到寄存器中

  2. 核心2 从内存指定位置出读取数值1,并加载到寄存器中

  3. 核心1 将寄存器中值递减1

  4. 核心2 将寄存器中值递减1

  5. 核心1 将修改后的值写回内存

  6. 核心2 将修改后的值写回内存

经过执行上述流程,内存中的最终值时2,而我们期待的是3,这就出问题了。要处理这个问题,就要避免两个或多个核心同时操作同一片内存区域。那么怎样避免呢?这就要引入本文的主角 - lock 前缀。关于该指令的详细描述,可以参考 Intel 开发人员手册 Volume 2 Instruction Set Reference,Chapter 3 Instruction Set Reference A-L。我这里引用其中的一段,如下:

LOCK—Assert LOCK# Signal Prefix

Causes the processor’s LOCK# signal to be asserted during execution of the accompanying instruction (turns the instruction into an atomic instruction). In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted.

上面描述的重点已经用黑体标出了,在多处理器环境下,LOCK# 信号可以确保处理器独占使用某些共享内存。lock 可以被添加在下面的指令前:

ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG.

通过在 inc 指令前添加 lock 前缀,即可让该指令具备原子性。多个核心同时执行同一条 inc 指令时,会以串行的方式进行,也就避免了上面所说的那种情况。那么这里还有一个问题,lock 前缀是怎样保证核心独占某片内存区域的呢?答案如下:

在 Intel 处理器中,有两种方式保证处理器的某个核心独占某片内存区域。第一种方式是通过锁定总线,让某个核心独占使用总线,但这样代价太大。总线被锁定后,其他核心就不能访问内存了,可能会导致其他核心短时内停止工作。第二种方式是锁定缓存,若某处内存数据被缓存在处理器缓存中。处理器发出的 LOCK# 信号不会锁定总线,而是锁定缓存行对应的内存区域。其他处理器在这片内存区域锁定期间,无法对这片内存区域进行相关操作。相对于锁定总线,锁定缓存的代价明显比较小。关于总线锁和缓存锁,更详细的描述请参考 Intel 开发人员手册 Volume 3 Software Developer’s Manual,Chapter 8 Multiple-Processor Management。

3.源码分析


有了上面的背景知识,现在我们就可以从容不迫的阅读 CAS 的源码了。本章的内容将对 java.util.concurrent.atomic 包下的原子类 AtomicInteger 中的 compareAndSet 方法进行分析,相关分析如下:


`public class AtomicInteger extends Number implements java.io.Serializable {



    // setup to use Unsafe.compareAndSwapInt for updates

    private static final Unsafe unsafe = Unsafe.getUnsafe();

    private static final long valueOffset;



    static {

        try {

            // 计算变量 value 在类对象中的偏移

            valueOffset = unsafe.objectFieldOffset

                (AtomicInteger.class.getDeclaredField("value"));

        } catch (Exception ex) { throw new Error(ex); }

    }



    private volatile int value;

    

    public final boolean compareAndSet(int expect, int update) {

        /*  * compareAndSet 实际上只是一个壳子,主要的逻辑封装在 Unsafe 的  * compareAndSwapInt 方法中  */

        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);

    }

    

    // ......

}



public final class Unsafe {

    // compareAndSwapInt 是 native 类型的方法,继续往下看

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

    // ......

}`


`// unsafe.cpp

/*  * 这个看起来好像不像一个函数,不过不用担心,不是重点。UNSAFE_ENTRY 和 UNSAFE_END 都是宏,  * 在预编译期间会被替换成真正的代码。下面的 jboolean、jlong 和 jint 等一些类型也都是宏:  *  * jni.h  *     typedef unsigned char   jboolean;  *     typedef unsigned short  jchar;  *     typedef short           jshort;  *     typedef float           jfloat;  *     typedef double          jdouble;  *  * jni_md.h  *     typedef int jint;  *     #ifdef _LP64 /* 64-bit */

 *     typedef long jlong;

 *     #else

 *     typedef long long jlong;

 *     #endif

 *     typedef signed char jbyte;

 */

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

  // 根据偏移量,计算 value 的地址。这里的 offset 就是 AtomaicInteger 中的 valueOffset

  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);

  // 调用 Atomic 中的函数 cmpxchg,该函数声明于 Atomic.hpp 中

  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;

UNSAFE_END



// atomic.cpp

unsigned Atomic::cmpxchg(unsigned int exchange_value,

                         volatile unsigned int* dest, unsigned int compare_value) {

  assert(sizeof(unsigned int) == sizeof(jint), "more work to do");

  /*  * 根据操作系统类型调用不同平台下的重载函数,这个在预编译期间编译器会决定调用哪个平台下的重载  * 函数。相关的预编译逻辑如下:  *  * atomic.inline.hpp:  *    #include "runtime/atomic.hpp"  *  *    // Linux  *    #ifdef TARGET_OS_ARCH_linux_x86  *    # include "atomic_linux_x86.inline.hpp"  *    #endif  *  *    // 省略部分代码  *  *    // Windows  *    #ifdef TARGET_OS_ARCH_windows_x86  *    # include "atomic_windows_x86.inline.hpp"  *    #endif  *  *    // BSD  *    #ifdef TARGET_OS_ARCH_bsd_x86  *    # include "atomic_bsd_x86.inline.hpp"  *    #endif  *  * 接下来分析 atomic_windows_x86.inline.hpp 中的 cmpxchg 函数实现  */

  return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest,

                                       (jint)compare_value);


> **Java网盘:pan.baidu.com/s/1MtPP4d9Xy3qb7zrF4N8Qpg
> 提取码:2p8n**



**面试资料整理汇总**

![成功从小公司跳槽进蚂蚁定级P7,只因刷了七遍这些面试真题](https://www.icode9.com/i/ll/?i=img_convert/1c39c35125624e522e26a6c6c65814da.png)

![成功从小公司跳槽进蚂蚁定级P7,只因刷了七遍这些面试真题](https://www.icode9.com/i/ll/?i=img_convert/0c374614d957b6855b65eff536cb01f4.png)

这些面试题是我朋友进阿里前狂刷七遍以上的面试资料,由于面试文档很多,内容更多,没有办法一一为大家展示出来,所以只好为大家节选出来了一部分供大家参考。

**[CodeChina开源项目:【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](

)**

面试的本质不是考试,而是告诉面试官你会做什么,所以,这些面试资料中提到的技术也是要学会的,不然稍微改动一下你就凉凉了

mL-1631373698815)]

这些面试题是我朋友进阿里前狂刷七遍以上的面试资料,由于面试文档很多,内容更多,没有办法一一为大家展示出来,所以只好为大家节选出来了一部分供大家参考。

**[CodeChina开源项目:【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](

)**

面试的本质不是考试,而是告诉面试官你会做什么,所以,这些面试资料中提到的技术也是要学会的,不然稍微改动一下你就凉凉了

**在这里祝大家能够拿到心仪的offer!**
上一篇:什么让python-pandas与excel彻底拉开了距离


下一篇:3d Slicer开发者入门