linux源码解读（十一）：多进程/线程的互斥和同步&JVM同步原理

　　为了提高cpu的使用率，硬件层面的cpu和软件层面的操作系统都支持多进程/多线程同时运行，这就必然涉及到同一个资源的互斥/有序访问，保证结果在逻辑上正确；由此诞生了原子变量、自旋锁、读写锁、顺序锁、互斥体、信号量等互斥和同步的手段！这么多的方式、手段，很容易混淆，所以这里做了这6种互斥/同步方式要点的总结和对比，如下：

　　详细的代码解读可以参考末尾的链接，都比较详细，这里不再赘述！从这些结构体的定义可以看出，在C语言层面并没有太大的区别，都是靠着某个变量（再直白一点就是某个内存）的取值来决定是否继续进入临界区执行；如果当前无法进入临界区，要么一直霸占着cpu自旋空转，要么主动sleep把cpu让出给其他进程，然后加入等待队列待唤醒；这里最基本的两种数据结构就是原子变量和自旋锁了，C层面的结构体如上图所示。然而所有的代码都会经过编译器变成汇编代码，不同硬件平台在汇编层面又是怎么实现这些基本的功能了？

　1、先看看windows+x86平台是怎么实现自旋锁的，最精妙的就是红框框这句了：lock bts dword ptr [ecx],0; 这句代码加了lock前缀，保证了当前cpu对[ecx]这块内存的独占；在这行代码没执行完前，其他cpu是无法读写[ecx]这块内存的，这很关键，保证了代码执行的原子性（能完整执行而不被打断）！正式分析前，先解释一下bts dword ptr [ecx],0的功能:

　　把[ecx]的第0位赋给标志位寄存器的CF位
把[ecx]的第0位设置置1

由于加了lock前缀，上述两个功能在cpu硬件层面会保证100%执行完成！在执行bts代码时：

（1）如果[ecx]是0，说明锁还没被进程/线程获取，还是空闲状态，当前进程/线程是可以获取锁，然后继续进入临界区执行的。那么获取锁和继续进入临界区着两个功能该怎么用代码实现了？

获取锁：锁的本质就是一段内存，这里是[ecx]，所以需要把[ecx]置1，这个功能bts指令执行完后就能实现
继续进入临界区：此时CF=0，会导致下面的jb语句不执行，而后就是retn 4返回了，标明获取锁的方法已经执行完毕，调用该方法的进程/线程可以继续往下执行了，这里取名A；

（2）如果A还在临界区执行，此时B也调用这个获取锁的方法，B该怎么执行了？因为A还在临界区，所以此时[ecx]还是1，锁还在A手上；B执行bts语句的结果：

把[ecx]的第0位赋值给CF；由于此时[ecx]=1，所以CF=1
把[ecx]置1，这里没变

bts执行完毕后继续下一条jb代码：由于CF=1，jb跳转的条件满足，立即跳转到0x469a12处执行；

test和jz代码检查[ecx]的值，如果还是1，也就是锁还被占用，就不执行jz跳转，继续往下执行pause和jmp 0x469a12，周而复始地检查[ecx]的值，也就是锁是否被释放了；自旋锁的阻塞和空转就是这样实现的！
如果A执行完毕退出临界区，也释放了锁，让[ecx]=1；B执行tes时发现了[ecx]=1，会通过jz跳回0x469a08处获取执行bts语句获取锁，然后退出该函数进入临界区
从上述流程可以看出：spinlock没有队列机制，等待锁的进程不一定是先到先得；如果有多个进程都在等锁，就看谁运气好，先执行jz 0x469a08者就能先跳回去执行bts得到锁！

（3）上述spinlock是windows的实现，linux在x86平台是怎么实现的了？如下：核心还是使用lock前缀让decb执行时其他cpu不能访问lock->slock这块内存，保证decb执行的原子性！这里的空转和阻塞是通过rep；nop来实现的，据说效率比pause要高！

typedef struct {
                unsigned int slock;
        } raw_spinlock_t;
#define __RAW_SPIN_LOCK_UNLOCKED { 1 }
static inline void __raw_spin_lock(raw_spinlock_t *lock)
       {
                asm volatile("\n1:\t"
                        LOCK_PREFIX " ; decb %0\n\t"
                // lock->slock减1
                        "jns 3f\n"
                //如果不为负.跳转到3f.3f后面没有任何指令，即为退出
                        "2:\t"
                        "rep;nop\n\t"
                //重复执行nop.nop是x86的小延迟函数
                        "cmpb $0,%0\n\t"
                        "jle 2b\n\t"
                //如果lock->slock不大于0，跳转到标号2，即继续重复执行nop
                        "jmp 1b\n"
                //如果lock->slock大于0，跳转到标号1，重新判断锁的slock成员
                        "3:\n\t"
                        : "+m" (lock->slock) : : "memory");
      }

　　相比之下，解锁就简单多了：直接把lock->slock置1，这里也不需要lock指令了；知道原因么？ 解锁指令是临界区的最后一行代码，说明同一时间只能有一个进程/线程执行该代码，这种情况还有必要加lock么？这点也引申出了spinlock的另一个特性：

　　A进程加锁，也只能由A进程解锁；如果A进程在执行临界区时意外退出，这锁就解不了了！

static inline void __raw_spin_unlock(raw_spinlock_t *lock)
        {
                asm volatile("movb $1,%0" : "+m" (lock->slock) :: "memory");
        }

　　2、再来看看arm v6及以上硬件平台是怎么实现spinlock的，如下：

#if __LINUX_ARM_ARCH__ < 6
        #error SMP not supported on pre-ARMv6 CPUs //ARMv6后，才有多核ARM处理器
        #endif
        ……
        static inline void __raw_spin_lock(raw_spinlock_t *lock)
        {
                unsigned long tmp;
                __asm__ __volatile__(
        "1: ldrex        %0, [%1]\n"
        //取lock->lock放在 tmp里，并且设置&lock->lock这个内存地址为独占访问
        "        teq %0, #0\n"
        //测试lock_lock是否为0，影响标志位z
        #ifdef CONFIG_CPU_32v6K
        "        wfene\n"
        #endif
        "        strexeq %0, %2, [%1]\n"
        //如果lock_lock是0，并且是独占访问这个内存，就向lock->lock里写入1，并向tmp返回0，同时清除独占标记
        "        teqeq %0, #0\n"
        //如果lock_lock是0，并且strexeq返回了0，表示加锁成功，返回
        " bne 1b"
        //如果上面的条件(1：lock->lock里不为0，2：strexeq失败)有一个符合，就在原地打转
                : "=&r" (tmp) //%0：输出放在tmp里，可以是任意寄存器
                : "r" (&lock->lock), "r" (1)
        //%1：取&lock->lock放在任意寄存器，%2：任意寄存器放入1
                : "cc"); //状态寄存器可能会改变
                smp_mb();
        }

　　核心的指令就是ldrex和strexeq了；ldr和str指令很常见，就是从内存加载数据到寄存器，然后从寄存器输出到内存；两条指令分别加ex（就是exclusive独占），可以让总线监控LDREX和STREX指令之间有无其它CPU和DMA来存取过这个地址，若有的话STREX指令的第一个寄存器里设置为1（动作失败）; 若没有，指令的第一个寄存器里设置为0（动作成功）；个人觉得和x86的lock指令没有本质区别，都是通过独占某块内存然后设置为1达到加锁的目的！

　　解锁的原理和x86一样，直接用str设置为1就行了，都不需要再独占了，代码如下：

static inline void __raw_spin_unlock(raw_spinlock_t *lock)
        {
                smp_mb();
                __asm__ __volatile__(
        "         str %1, [%0]\n" // 向lock->lock里写0，解锁
        #ifdef CONFIG_CPU_32v6K
        "         mcr p15, 0, %1, c7, c10, 4\n"
        "         sev"
        #endif
                :
                : "r" (&lock->lock), "r" (0) //%0取&lock->lock放在任意寄存器，%1：任意寄存器放入0
                : "cc");
        }

　　 atomic的实现方式类似，这里不再赘述！最后总结如下：

不管是锁、互斥体还是信号量，都是通过独占某块内存、然后置1的方式加锁的
如果加锁成功，进入临界区执行
如果加锁失败，要么sleep让出cpu，自己加入wait队列，直到被唤醒；要么自旋原地等待，同时继续尝试加锁，直到成功加锁为止；
临界区执行完毕后在不独占内存的情况下解锁

　　3、上述都是C语言和汇编层面实现的互斥和同步，那么cpu硬件层面的lock或ldrex+strex又是怎么实现的了？

早期的cpu直接锁总线，也就是cpu1独占某块内存的时候其他cpu是没法继续使用总线的，这么一来其他cpu都只能等了，效率很低
近些年cpu采用了缓存一致性协议在多个cpu之间同步内存的数据，最出名的应该是intel的MESI协议了！

　　4、这里扩展一下，介绍另一个大家耳熟能详的软件产品：JVM；JVM里面有两个关键词：synchronized和volatile，著名的DCL代码如下：

public class Singleton {
    private volatile static Singleton uniqueSingleton;

    private Singleton() {
    }

    public Singleton getInstance() {
        if (null == uniqueSingleton) {
            synchronized (Singleton.class) {
                if (null == uniqueSingleton) {
                    uniqueSingleton = new Singleton();
                }
            }
        }
        return uniqueSingleton;
    }
}

　　这两者在底层cpu汇编层面又是怎么实现的了？以x86架构的cpu为例：

　　（1）先来看看volatile：底层用的还是lock实现的！

JVM底层汇编代码如下：

inline jint     Atomic::add    (jint     add_value, volatile jint*     dest) {
  jint addend = add_value;
  int mp = os::is_MP();
  __asm__ volatile (  LOCK_IF_MP(%3) "xaddl %0,(%2)"
                    : "=r" (addend)
                    : "0" (addend), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return addend + add_value;
}

（2）synchronized类似，用的还是lock关键字，不过由于涉及到临界区，还用了cmpxchg，连起来就是lock cmpxchg，在https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/os_cpu/linux_x86/vm/atomic_linux_x86.inline.hpp 这里有完整的实现代码，如下:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

　　上面两段C代码在内联汇编前面都加上了volatile，并且还特意用不同的颜色标记了，说明还是个关键词，难道java层的volatile是依赖C语言层的volatile实现的？注意：volatile关键词的作用很多，比如：

　编译器层面
- 　　不要自作聪明优化指令，比如合并、甚至删除某些代码或指令，典型的如嵌入式的存储器映射的硬件寄存器；
- 不要打乱原作者代码的顺序
操作系统层面：需要共享的变量加上前缀
- 　　中断handler中修改的供其它程序检测的变量；
- 多线程执行时，强制某些共享的变量需要从内存读取数据，而不是用cpu自己的缓存，避免读到脏数据；
cpu层面
- 　　汇编指令加lock锁定内存区域；
- 通过缓存一致性协议在不同的cpu核之间同步内存的值，典型的如intel的mesi协议;

（3）大家有没有注意到上面的synchronized (Singleton.class)，用的是一个class；既然所有互斥/同步都是通过读写某个特定的内存达到目的的，这里又是通过怎么读写class对象的内存达到目的的了？

　　java和c++的类对象实例在内存的布局有些许不同：c++类实例有虚函数表指针，而java对象的实例是没有的，取而代之的是markword和类型执行；markword有64bit，类型指针可能是32bit，也能是64bit，布局如下：

同步方便最核心的字段就是markword了，其包含如下：利用的就是最低2bit的锁标志位来标识当前对象锁状态的：

参考：

1、https://blog.51cto.com/u_15127625/2731250 linux竞争并发

2、https://blog.csdn.net/u012603457/article/details/52895537 linux源码自旋锁的实现

3、https://zhuanlan.zhihu.com/p/364044713 linux读写锁

4、https://zhuanlan.zhihu.com/p/364044850 linux顺序锁

5、https://blog.csdn.net/zhoutaopower/article/details/86611798 linux内核同步-顺序锁

6、https://zhuanlan.zhihu.com/p/363982620 linux原子操作

7、https://zhuanlan.zhihu.com/p/364130923 linux 互斥体

8、https://www.cnblogs.com/crybaby/p/13061627.html linux同步原语-信号量

9、https://codeantenna.com/a/F2a5C0tK3a Linux中Spinlock在ARM及X86平台上的实现

10、https://www.cnblogs.com/yc_sunniwell/archive/2010/07/14/1777432.html c/c++中volatile关键词详解