并发与锁

JUC AQS

AQS整体结构

锁的获取过程

• CAS rote 回转数的问题

获取失败挂起的过程

释放锁唤醒等待的过程

• 如何防止丢失唤醒

  入队时不能“贪睡”，找可靠等待者并让他叫醒自己，不在进而就获取锁，其他所有情况都告诉标记前驱别忘了叫醒自己

  这就够了吗，显然还不行；满足自己去“睡”的条件的check和“睡”显然不是一个原子操作。在check后和“睡着”前如果条件变了就没人叫醒

  unpark和park早就预防相关问题，猜想内部是有变量记忆了上次的操作后状态，同时基于操作系统提供的锁保证了原子性

• 如何防止惊群问题

  锁的唤醒通常是有唤醒一个等待线程和唤醒全部等待线程的；通常在编程条件下如果想减少全部唤醒的引发不必要的竞争时，还要注意虚假

  唤醒问题，被唤醒的线程如果条件不满足条件释放锁后造成唤醒链脱节的问题。而这种情况又不能简单在自己释放锁前去唤醒其他等待者。

  所以比如在leader-follower模式中，如果leader线程只在原leader线程离任时唤醒任意一个等待线程时，则当线程都在follower模式

  时因为没有唤醒者陷入停机状态，所以在每次完成工作时还要尝试自荐为leader。如果leader在离任时唤起其他所有线程显然时惊群的。

AQS小结

• 双检锁的简单优化

• 流言：cas+clh队列语义上等价于锁

  线程阻塞于唤醒的闭合性无法满足，需要借助cpu指令中的屏蔽中断与禁止抢占保证调度切换的原子性

从CAS到内存屏障再到缓存一致性协议

• volatile happens-before

  如果a线程先写入新值，b线程紧接着（赋值后隔一个时钟周期，这样可以使得无论是lock前缀的指令排空store buffer

  并且失效其他处理器的对于缓存得以执行完，或者时钟中断引发store buffer排空进而触发缓存一致性同步）去读就能

  最新值，不过由于需要间隔一个时钟周期，看似违反happens-before；不过由于紧接着是lock的情况在紧接着的时钟

  周期里由于lock触发缓存一致性同步会失效该数据项的旧值所以不会有问题，时钟中断的间接触发缓存同步也类似。

• unsafe 源码

https://github.com/dmlloyd/openjdk/blob/jdk/jdk/src/hotspot/share/prims/unsafe.cpp

• CAS 指令与总线锁 CMPXCHG16B

• 内存屏障与缓存一致性协议

• 编译器优化、cpu乱序执行【关于体系结构只针对X86-64其他乱序自由度更大的暂不考虑，料想其原理是类似的】

冒险：

数据冒险
结构冒险
控制冒险（分支冒险）
MESI、MOSI、MESIF

一图胜过千言（待添加），

硬件结构： 写缓存的读取优先与L1cache，写合并WC优化；写回缓存WB，写穿透缓存WT，

写失效WI，经验表明写失效，更节约带宽

写更新WU，看起来快，有时候是不必要的如果更新每个缓存比起一条失效指令代价大许多；

更新可能是断续多次而失效只要一次，而且缓存行内容的大小比缓存地址大位宽大不少

X86-64一致性高，LoadLoad Memory Barrier是因为读屏障会强制等待Invalidate Queue清空才继续执行，

这样可以消除其引发的读乱序问题

• 缓存一致性协议提供了缓存一致性的必要的手段和机制，内存屏障是通过简单的抑制乱序以及对这些手段和机制的利用

  进而达到缓存一致的对外表现。这里提现硬件的对外复杂度的隔离封装，对外暴露了简单的接口，内部实现像水面下的

  冰山。

缓存一致性协议显然在硬件上有锁的语义的

loadload

loadstore

storeload （x86 TSO 唯一乱序的地方）

storestore

Synchronized

• 对象头

• 锁升级

• 安全点及延申

  精确式GC、安全点调度以及协程调度java与golang

Futex

Futex是一种用户态和内核态混合的同步机制。首先，同步的进程间通过mmap共享一段内存，futex变量就位于这段共享 的内存中且操作是原子的，当进程尝试进入互斥区或者退出互斥区的时候，先去查看共享内存中的futex变量，如果没有竞争发生，则只修改futex,而不 用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生，则还是得执行系统调用去完成相应的处理(wait 或者 wake up)。简单的说，futex就是通过在用户态的检查，（motivation）如果了解到没有竞争就不用陷入内核了，大大提高了low-contention时候的效率。 Linux从2.5.7开始支持Futex。

• 自旋锁

  内核的基本锁之一

• 自旋优化（jdk9与自旋提示）

自旋是在循环中不断重试检测条件变量的值，这样为了保证可见性，就需要不断的同步缓存，造成很多不必要的开销。

• RCU锁

  包含的数据通常都是指针类型的，每个核上都发生过调度就说明如果其他核在该rcu锁的读临界区，完成一轮调度后（读临界区不可抢占）

  如果再有新的线程可见的数据是新的老版本的可以释放了。如果是可抢占的RCU就需要在锁定开头和释放的结尾维护一个计数器。

• 屏蔽中断与禁止抢占

锁的构成要素

>cas
>等待队列
>屏蔽中断禁止抢占的原子调度上下文的切换

理解与体会

• 不总结不准备就会拔剑四顾心茫然

• 读写时序

• 控制流与数据流的等价性

• 几种并发模型 actor、CSP、CPS/CallCC

• 锁的本质问题是时序问题，调度可以解决时序问题，调度问题从cpu角度看又是执行权的问题，锁是保护了数据，锁是通过限制代码的执行来保护数据的。

mesi为什么可以保证一致性对分布式环境缓存一致性有什么启示

首先总线的作用是巨大的，他保证了多核乃至多路cpu间的缓存一致性

分布式环境下由于没有统一的总线，缺少收敛的协调控制。