公告
页次： 1
#1 2022-10-09 12:32:26
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）这里顺便介绍一下atomic：不用syncronized也能实现变量在多线程之间同步，其底层原理用的还是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的锁标志位来标识当前对象锁状态的：
（4）延展一下，对象实例结构详细说明如下： 
对象头相当于整个对象的“元数据meta data”，是对整个对象的详细说明。我个人觉得最核心的是实例数据instance data，这里包含了所有的类成员变量（类似C语言的struct结构体，人为聚集了所需的所有字段），包括继承了父类的成员变量！从上述分配策略看，相同宽度的字段总是被分配到一起。在满足这个前提条件的情况下，在父类中定义的变量会出现在子类之前；这里啰嗦几句: 类最核心的是成员变量，类中所有的方法都是用来读、写这些成员变量的！
（5）jvm synchronized实现历史：
早期jvm遇到synchronized直接调用操作系统提供的api切换线程。由于产生了线程切换，并且从用户态进入内核态，需要保存上下文context，开销非常高，导致效率低
后期搞了个“偏向锁”：第一个synchronized(obj)的线程会在obj的head记录标记一下，对外官宣这个obj已经被占用了。如果此时有其他线程竞争同一个obj的锁，该线程会开始自旋；如果自旋10次后还没等到obj的锁释放，jvm会再次调用操作系统的接口让该线程进入wait队列等待，避免自旋空转浪费cpu。所以这种方式的本质就是：竞争的线程先自旋CAS等待，如果10次后还是得不到锁，就进入调用os的接口切换线程，进入wait队列放弃cpu，避免浪费cpu时间片！
总结一下：
如果加锁的代码少、执行时间短，并且并发的线程数量少（避免大量线程都在自旋浪费cpu），适合自旋
如果加锁代码多、执行时间长，并且并发线程多，为了避免部分线程被“饿死”，建议直接调用os的接口做线程切换，进入wait队列放弃cpu
参考：
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关键词详解
离线
页次： 1