演讲嘉宾简介：陶云峰,阿里云高级技术专家，上海交通大学理论计算机科学博士，专注数据存储、分布式系统与计算等领域，写了20多年程序。2000年参加ACM/ICPC大赛，实现亚洲队伍进World Final前十的突破。
本次分享主要包括以下内容：
1.
原子变量
2.
内存模型
3.
spin lock
一、 原子变量
Atomic，即原子变量，是可以跨线程共享的变量。在下面这个例子中，有一个全局变量sExit，线程1中进行循环，只要sExit为true则退出。线程2对是sExit进行操作，用于控制线程1的退出。在这个例子中，可能发生一种情形，虽然线程2执行了，但线程1仍然有可能不退出。对线程1来说，sExit看起来访问的是一个变量，但对CPU和编译器来说，可能会把它放到cache甚至寄存器中。因此，当线程2写内存时，线程1中仍不会发生改变。另一方面，也有可能线程2在写sExit，写到了寄存器或者cache中时，线程1也会无法退出。
如果sExit加上关键字volatile，则线程1能退出，但理论上这段代码是有问题的。volatile的本意是用来访问外部设备，而非用于线程同步。以前的计算机中，一般访问外部设备的接口会全部映射到一块内存地址中，访问这块地址时就相当于访问外部设备。现在的驱动程序还是可以这样做。而一般应用层的程序是不可以这样操作的。对于线程同步问题来说，volatile能保证访存，因此这个程序能正常运行。但volatile不保证原子性，也不对指令乱序加以限制。由于bool型只有一个字节，没有比其更细的粒度，因此在这个场景下原子性不会有问题。而指令乱序问题，由于案例代码不完整，所以无法得知。
那么，在什么情况下会出现问题呢？如下面这个例子。由于不知道线程1和线程2哪个会先运行，所以线程1的x有多种可能的值。{1,2}或{3,4}是比较好理解的。但也有可能出现{3,2}，由于线程2在赋值时，实际的赋值指令为两条，当线程2中的a完成赋值后，先执行了线程1。同时，{1,4}也是一种可能的情况。这是由于，线程2运行时，两条赋值指令操作的内存单元是不一样的，是允许乱序执行的，即先执行b的赋值操作。那么就会出现{1,4}这样的结果。
如果将volatile改为atomic，就只会出现{1,2}或{3,4}这样的结果。
前文中讲解过mutex和各类锁操作，那么如果这里利用mutex进行互斥，在临界区中进行赋值和读值，是否就可以不用atomic了呢？从程序的逻辑上看，是对的。通过这两种方式都可以使程序达到相同的执行流。但这两种方法存在区别，使用mutex可能会陷入操作系统内核，将当前的线程挂入操作系统内核中的调度器的working队列中，而atomic是纯粹用CPU提供的硬件指令完成的，与操作系统无关。现代的mutex，比如高版本gcc提供的mutex，已经高度优化了，在无竞争的情况下，性能和atomic一样，事实上它也是利用atomic实现的。但在有激烈竞争的情况下，mutex会陷入内核，一次内核调用大约在百纳秒的量级上。而使用atomic利用CPU硬件指令只需几纳秒。但atomic会霸占CPU，如果需要霸占CPU的线程很多，就会导致程序整体性能的下降。
二、 内存模型
内存模型是和原子变量搭配使用的。这里介绍三种内存模型。
1、 最终一致性
第一种是最终一致性。如下面这个例子。
定义了一个int型的原子变量cnt，线程不断进行加法操作。当所有线程结束时打印cnt的值。在这个例子中，只要保证最终的加法结果正确即可，可以不关心执行顺序。因此就可以使用“最终一致性“内存模型——relaxed。这里，relaxed保证了原子变量的一致性，也保证了任何一个线程对原子变量的改变最终一定会被其他线程看到。但它有两点无法保证 ：第一，不保证一个线程对原子变量的改变，会以相同的顺序被其他线程看到。（比如，先改a，再改b，其他线程看到的顺序可能是先b后a。）第二，不保证一个线程对原子变量的改变，和其他访存操作，会以相同的顺序被其他线程看到。最终一致性是最弱的一种一致性条件。
2、 顺序一致性
下面介绍一种最强的一致性条件，顺序一致性。在下面这个例子中，使用任何更弱一些的一致性模型都是无法得到正确结果的。
在这个例子中，定义了三个原子变量。其中x, y是初值为false的布尔型变量。线程1，2将这两个变量置成true。线程3，4是对偶的。线程3，如果x为true则退出循环，此时，如果y是true，就进行++z。线程4，如果y为true则退出循环，此时，如果x是true，就进行++z。在顺序一致性模型中，可以保证最终z是大于0的。这是由于，线程1和线程2的访存一定是有先后的。假设线程1先做，线程2后做，那么在线程4中，当y为true时，x一定是true，一定会执行++z。反之，线程3一定会执行++z.。顺序一致性还保证了一个线程内有一个顺序一致性的原子变量访存，就能保证其他非原子的访存操作，既不能乱序到原子变量前，也不能把前面的指令跨过原子变量往后重排。顺序一致性是锁内存总线的，并且强制各个CPU同步cache。它的性能较差，但安全性比较有保障。
3、 release-acquire
第三种内存模型release-acquire。以下面这段代码为例。
有原子变量ptr，有普通变量data。线程1中有局部变量指针p，保存到ptr中，在此之前将data赋值为42。线程2中，不断从ptr中加载指针，一旦指针不是NULL，那么一定能看到data==42。这是因为如果能读到同一个原子变量的写存，也一定能读到在其之前的访存，包括之前的原子访存和普通访存。这就是release-acquire模型。线程3是使用了relaxed内存模型的情况。最终输出的data可能不为42。
release-acquire这个名称怎么来的呢？没错，互斥锁。acquire代表获得锁，release代表释放锁。下面展示了一种互斥锁的实现。
定义了一个原子变量mtx。抢锁时将true原子地赋给mtx。exchange函数会在把变量当前的值返回的同时，将 新设的值写入变量。如果返回的值是false则说明当前无人持有锁。如果是true就说明当前有人持有锁 ，无法进临界区，此时需要进行循环等待。出临界区的时候只需要将mtx赋为false。
下面简单介绍一下现代CPU的架构（如下图），以便让大家更好的理解release-require为何是一个高效的内存模型。
大家知道CPU的运算速度很快，而相对而言访问一次内存的速度要差一个数量级。因此，CPU一般不直接向内存要计算数，而是向L1 cache要。同时，CPU通常是多核的，这也就意味着，当计算单元完成运算写入L1 cache时，L1 cache 需要将结果通知给其他内核，并写入内存。因此，CPU写入cache时也比较慢，因此会先写入store buffer中，然后从store buffer写入L1 cache，再由L1 cache通知其他内核。这一过程也相对较慢，所以内核也并不马上做，而是把其他内核发送过来的更新通知放进一个队列里，即invalidate queue。当store buffer为空时表示其他内核都已经知道了自己写入的内容。这一过程就是release，即等待其他CPU都知道当前内核写的内容。而acquire就是等待invalidate queue队列为空的过程，意味着当前CPU知道了其他CPU的所有写操作。release-acquire是一个与当前CPU设计非常相符的，因此，它非常高效。
三、 spin lock
最后，介绍spin lock案例。
1、 TAS
第一个实现是Test-and-Set，即TAS。通过原子地对变量赋值，并返回老值进行上锁。通过将false写入，进行放锁。逻辑上看，这段代码没有问题，但实际上它是不可用的，一旦出现争抢会使程序运行非常缓慢，并且CPU负载很高。
2、TTAS
下面对TAS进行了改进，Test-Test-and-Set，即TTAS。
在上锁时，先通过relaxed读mtx的值。一旦mtx为false，就用acquire的方式对mtx进行exchange，以保证正确性。由于relaxed是不需要清store buffer和invalidate queue的，因此它的效率相对较高。Relaxed读到的其实是一个脏值。绝大多数情况下，invalidate queue是不空的，但queue中的值不是由于mtx写造成的。因此，清理queue的过程会使得性能下降。此时，通过脏值来判断mtx是否值得去抢锁。换句话说，通过relaxed方式，减少了对mtx的争抢。因此，TTAS的性能会优于TAS。通常情况下，TTAS是可以实际使用的，但当竞争更激烈的时候，它的性能还是不够好。
3、backoff
下面介绍backoff退避锁。使用前面的方法，通过relaxed判断是否值得抢，可以一定程度上提高性能。但在这种情况下，一旦放锁发生了，其他人几乎会在同一时间进行争抢，性能还是会很差。这时，就有这样一种设想，能否将争抢的过程打散。在放锁的时候，只安排少数人去抢锁，这就是退避 。退避的原理是，如果抢不到锁，就等待一会儿。如下面这段代码所示。
一旦尝试抢锁没有成功，就进行退避，将原limit翻倍，并在旧limit和新limit之间取一个随机数，等待随机数对应的时间，然后通过调用sleep_for，进行等待。
下面我们对退避的性能做一个估算。
假设初始limit为10ms，临界区耗时1ms，有100个线程抢锁。
正确的做法：每次limit翻倍，实际退避时间在limit/2到limit之间随机。
1.第一轮只有一个线程抢到锁，其余线程退避；
2.第二轮有5个线程抢到锁；
3.第三轮有10个线程抢到锁；
4. ……
5.最多需要6轮，最多耗时310ms
错误的做法：在limit之内取随机，然后每次对这个随机数翻倍。
1.第一轮只有一个线程抢到锁，其余线程退避；
2.第二轮有10个线程抢到锁；
3.第三轮有10个线程抢到锁；
4. ……
5.最多需要10轮，最多耗时10s+
退避锁是一中实现简单，实用的锁。在多线程和分布式系统中都有非常广泛的应用。在分布式系统中，可以认为锁的临界区就是web服务器的busy状态，例如web服务器一秒钟可以handle一万个请求，当有一万零一个请求时，就返回busy状态，可以使用退避的方式解决，让web服务器以最大的吞吐量来处理所有的请求。但在单个进程内，退避锁并不是最好的解决方案。‘
4、CLH
下面介绍CLH。它的实现稍复杂些，mtx是一个原子变量的原子变量。代码不再详细介绍了。
下面通过几张图片介绍一下CLH的原理。
首先，mtx指针指向另一个布尔型的原子变量，初值为false。
这时，线程1要抢锁，它先new一个布尔型的原子变量，值为true。
然后将两个指针交换，线程1发现mtx原来的指针指向的是false，就抢到了锁。
这时，出现了线程2要抢锁。它先new一个布尔型的原子变量，值为true。
然后和mtx交换指针，线程2发现mtx原来的指针指向的是true，说明有线程占着锁。
线程1完成工作，放锁，直接将蓝色的原子变量改为false。 为什么线程1可以直接修改蓝色的原子变量呢？因为这个变量原本就是他分配出来的，它知道地址。这时，线程2看到了false，即抢到了锁。
CLH锁本质上是一个队列。让同时抢锁的线程排队，并由前一个通知后一个，减少了争抢，同时避免了sleep造成的无效的等待。
最后，总结一下本次分享的主要内容。
本文由云栖志愿小组马JY整理，编辑百见
