前言

为了最大程度的利用计算机的硬件资源，尽可能的提升应用软件的执行效率，Golang抽象出了协程。实现了GMP线程模型。但是伴随着执行效率的提升的同时，也引来了其他的问题——资源竞争引起的数据原子性问题（这是多CPU核多线程无法回避的并发问题）

Goer有时会碰到线上的偶现性的bug（甚至很难复现），基本上都是因为使用协程引起的并发甚至是并行问题。

简要描述下上述程序的功能：对data进行累加操作，为了加快累加的速度，开了10个协程处理。

我们的期望结果是：1000000，但是实际执行结果总是远小于该数据。是因为在实际的执行过程中，由于并发很多累加结果被吞掉了。

这样的结果肯定是不被接受的，为了解决这个问题，计算机领域的大师们很自然的就提出了并发原语。

何为并发原语？

并发就不多说啦。

原语：所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。在操作系统中，某些被进程调用的操作，如队列操作、对信号量的操作、检查启动外设操作等，一旦开始执行，就不能被中断，否则就会出现操作错误，造成系统混乱。

并发原语就是用于解决并发问题所引起的资源竞争问题的基本程序段，在上层的应用软件如golang|java|python中都会封装出基本的API函数，供开发者直接调用。

能不能讲的通俗点的，不就是加锁嘛???!!!

但这并不完全对。Golang在为了应对各种实际场景分别提出了特色的并发原语。例如：semaphore、singleflight、mutex等。但是所有都是基于mutex。

mutex(锁)

软件层

锁用于对某个数据或某个过程设立保护区。例如对于golang而言，几个协程共同争抢同一把锁，只有抢到锁的协程具有执行权，其他协程必须等待直到当前锁被释放。本质上，就是通过锁实现被保护过程的串行化。

思考：自己怎么实现一个锁？

通过结构体Lock的成员变量locked来标识该锁是否处于锁定状态（true:已锁定; false:未锁定）。如果已处于锁定状态，则一直spin直到其他协程释放该锁。

拿两个协程举例子，期望执行过程如下。当协程1占有锁的过程中，协程2一直等待获取锁，直到协程1释放锁，协程2能向下执行。

看着非常完美，但还是无法实现独占。

存在三问题：

1、多核情况下，存在多个协程同时拿到这把锁，破坏了任何协程都能独占访问的保证

2、编译器优化指令的时候，根据优化策略，可能会生成乱序的机器码，导致执行的时候破坏独占访问。

3、多核CPU实际指令执行的时候，会存在指令的乱序执行。

Emmm.....以上描述有些过于抽象了。除了第二条，问题一、三 其本质都是牵涉到具体的硬件实现。所以为了分析清楚问题，需要剖析下硬件层面的实现。

硬件层面的实现

以下分析的硬件：ARMv8芯片，使用的汇编指令集当然也是ARMv8指令集。

用汇编翻译上述代码：假设内存Lock结构体的基址放在X10寄存器中，且成员变量locked地址位于#1。

给到简化的硬件结构图：

画出了数据存储的主要单元，寄存器(用于直接参与CPU运算的数据存放)、storage cache（数据进入Memory的第一级缓存，数据传输指令牵涉到）、cache（数据进入Memory的第二级缓存，数据传输指令牵涉到）、Memory.

上述问题就是由于多核CPU的缓存一致性的问题引起的，CPU0和CPU1缓存中同一个变量的值并不相同。

为了尽可能解决多级缓存体系缓存一致性的复杂问题，多核CPU缓存现在遵循MESI协议。

单个CPU不会出现并发问题的天然性，在于某个时刻只能执行一条命令（这句话换位置描述）

状态机：

状态描述状态改变条件
M 修改 （Modify）表示该缓存行有效，但是是被更改过的，与内存中的数据并不一致，并且该缓存行只存在于本缓存中（举例：我们有三个CPU，每个CPU都有自己的缓存区域，那么M表示CPU-A从内存中取到了数据，其他CPU并没有取此数据（只存在于本缓存中），CPU-A还把该数据进行了更改，导致与内存中的源数据并不一致）当有其他试图读取该缓存在内存中的源数据时，它们须等待此缓存写回到内存，这时此缓存行的状态为S
E 独占 （Exclusive）表示该缓存行有效，数据和内存中的一致（干净），并且数据只存在于本缓存行中如果有相应的其他读取内存中关于本缓存行的操作时，会将自身的状态更改为S。
S 共享 （Shared）表示该缓存行有效，数据和内存中的一致，并且数据也同时存在于其他缓存中如果其他缓存将该数据在它当前所在的缓存区域内将缓存修改，那么其他没有修改的缓存就需要把S状态修改为I状态
I 无效 （Invalid）该缓存行数据无效

针对问题一：假设l.lock变量在CPU0的local cache中

  • CPU1执行LDUR操作，由于l.lock不在local cache中，CPU0发送一个read message到总线上，看看是否可以从其他CPU的local cache中或者memory中获取数据
  • CPU0收到read message，将最新的l.lock = 0 的值回送到CPU1，同时把存放l.lock数据的cache line在状态设置为sharded
  • CPU1收到来自CPU0的read response消息，将l.lock变量的最新值1写入自己的cachelline，并设置为sharded。
  • CPU0和CPU1同时执行LOOP判断

根本原因：各CPU的本地缓存中，能同时存在lock = 0 也就意味着该锁能被多个线程同时持有，使得程序并行执行。


针对问题三：假设l.lock = 0 变量分别在CPU0和CPU1的local cache中

  • CPU0执行STUR指令，更新local cache中对应的值为1，然后发出read invalidate信号
  • CPU1执行LDUR指令，由于CPU1的local cache中l.lock的值还是旧的值为0，跳出LOOP循环
  • CPU1收到了来自CPU0的read invalidate消息，清空了自己local cache中a的值，但是已经太晚了
  • CPU0收到CPU1的invalidate ack消息后，将l.lock变量标识为E, 并将内存中的值更新为1

根本原因：CPU实际指令执行顺序问题，导致锁同时被多个线程持有


使用golang提供的同步包

CAS(Atomic)

软件层：

分析下Mutex.Lock代码，可以看到有个核心函数：CompareAndSwapInt32（简称CAS）

CAS用于检查指定单元并且返回结果，如果检查结果为假，在返回假之前还要将单元内容设置为真。

可以看到它不是一个单一的指令，而是一组指令对。

但是这样实现还不能保证达到所需要的效果，这里有个至关重要的细节，也是整个系统完成并发控制的核心：CAS操作必须以原子操作的方式执行。也就是，我们必须保证，一旦某线程检查了一个单元内容并发现他是假，该单元的内容就必须设置为真，而且必须在任何其他进程检查这个单元之前完成这一设置。如果没有这种保证，那么这个锁就会失效。在单核处理器上，只需要在检查和设置单元值之间禁止进行时间分片就行。但在多核处理下，就需要由硬件提供原子操作能力。

硬件分析：

在多核处理器中实现同步的关键是需要一组硬件原语，能够对一个存储地址进行原子读和写，读写之间其他任何操作都不得插入和干预。

一种可行的方法是采用指令对，由第二条质量返回一个值，表明这对指令是否按照原子性执行。加入其他处理器的操作都是在这对指令之前或之后执行，那么这对指令就是有效的原子操作。

ARM处理器为例，这对指令包括LDXR和STXR。用这两条指令翻译如下：

任何时候，若有处理器插入并修改了LDXR和STXR两条指令之间存储器的值，STXR指令就返回1（在X9中），导致这段指令重新执行。该指令序列最后，寄存器X23中的内容和X20指向的存储地址（锁）的值实现了原子交换

还是基于上面的硬件结构，STXR指令(相比较STUR指令)还会判断执行该指令的CPU的对应local cache的变量为Exclusive状态，才会返回正常的执行结果。

mutex使用坑

1、特别容易引起死锁问题。

双向依赖造成的死锁

2、mutex的使用颗粒度问题，需要保护的临界区过大，不但会增加程序的复杂度 而且会降低程序的执行效率（可能比起串行化更低）

衍生出其他并发原语

比如Channel，用于协程间进行通信

既然mutex不容易使用，而且在实际的业务场景中 多个协程间进行通信的时候就会导致频繁发生数据竞争。

为了减少mutex的使用负担。golang又做了一层抽象，屏蔽掉了mutex的细节。使用上非常方便。


总结

整篇文章从 软件 -》硬件实现层面对于锁的实现进行了剖析，给出了锁的实现原理。软件层面的CAS操作，需要由硬件提供支持 在保证了缓存一致的基础上，只有独占状态的变量才能抢占到锁。