【多线程】自旋锁的设计与优化

0xAA55

当你两个线程同时对同一份数据进行读写操作的时候，这份数据的内容就只有鬼才明白是怎么来的了。想象一下两个人同时往一张纸上的同一个位置写字，先不说笔尖打架了，写的字也是互相覆盖的。

于是就有了锁、临界区的概念，它们被用于阻止同一份数据被不同的线程同时读写。而设计这些玩意儿，则需要用到原子操作。

    问：什么是原子操作？

    答：简而言之：它能强制你的CPU真的去读写内存，而不是瞒着你去读写CPU的高速局部缓存。

由于各方面的优化的原因，你写C代码（或者其它任何编译性质的编程语言包括VB6、C++、带JIT的Java或c#、vb.net、

m

asm等）的时候写的那些语句所表达出来的操作，一般都是对CPU的缓存进行读写，而不是内存或者别的线程能访问到的地方。甚至干脆不读写（被当作无用代码优化掉了）。

并且，它有个功能是让你可以先霸占内存（或者缓存），然后完成三个步骤——读取一个值，做一个运算（加、减、与、或、非、交换，或者先判断后再加、减、与、或、非、交换等），再写回内存（或者缓存）。霸占内存的情况下，在三步操作的中途，别的线程和外设等将无法访问内存，它们会等CPU完成这个读写的组合步骤后再访问内存。
典型例子：a = a + 1;，这个过程中a会被读取一次，加上1，再写回去，但如果你不是用的原子操作的话，如果两个线程同时读取了a，加上1，再写回去的话，a的实际值只是加上了1，而不是2。
参考：https://www.0xaa55.com/thread-991-1-1.html

通常原子操作被用于作为多线程协同的“信号”（semaphore），来让其它的线程读取后决定其合作过程。锁，就是原子操作的典型应用。

典型参考Windows的API：InterlockedIncrement();用于实现a = a + 1;的原子操作。
类似的API：https://www.0xaa55.com/thread-1430-1-1.html

典型参考x86汇编指令：LOCK XCHG。注意XCHG指令它其实自带LOCK锁总线功能，所以LOCK前缀是给别的指令用的，比如INC等（注意InterlockedIncrement并非LOCK INC）。相当于Windows的InterlockedExchange();这个API。注意：尽量不要直接用指令，因为那个指令会进行一个全局锁，会锁住整个总线，降低整个系统的性能。

    问：什么是自旋锁？

    答：简而言之它是一个信号用于判断一个数据是否正在被一个线程读写。

这里“锁”表示这个信号的值如果是“正在被一个线程读写”，那么别的线程就不要去读写了（强行去读写的话就失去了加锁的意义了）。否则，想要访问这个数据的线程就可以访问数据了。访问前把它的信号值设为“上锁”就行了。访问后设为“解锁”来让别的线程可以访问。
而“自旋”的意思是：我这个时候必须访问这个数据，如果数据被别的线程独占了，我就不停地循环读取锁的状态。是一种程序的设计逻辑。就像一个特别想上厕所的人看一眼厕所的状态（锁着的）然后转一圈过来再看的这种动作（自个儿打转）。

和多线程开发作为对比，写一个没有BUG的单线程的程序其实是一件非常简单的事情。毕竟单线程程序它十分符合编程语言本身所描述的行为逻辑去运行，而多线程开发则经常让没有经验的开发者感觉很多BUG的发生是十分出人意料的。
更何况，多线程里面对于性能上的BUG更是令人难以察觉——尤其是多个CPU都被占满后，这欣欣向荣的运行效果的掩饰之下，算法的实际效率还不如单线程计算的效果。这通常都是由于线程锁的不当设计而导致的。并且这种BUG不会导致崩溃或者死机，而且它也能生成正确的（或者难以判断正误的）运算结果。

所以锁的设计和优化还是很重要的，毕竟CPU它也并不会像一个特别想上厕所的人那样因为在厕所门前等过久而爆发喷屎。在数据被占用的时候，你可以调度CPU去做别的能做的事情，或者用一种更合理的方式来判断应该等待多久等。
用一个锁来决定一块数据是否可以读写，然后循环等待它的占用情况的这种逻辑叫临界区（Critical Section，其实应该被翻译为“关键环节”，大概）。

·最简单的自旋锁的设计是TAS自旋锁。TAS是Test-and-set（判断后设置）的处理逻辑，判断信号是否为“已占用”，如果没占用就占用，如果占用就干等，直到它被设置为“没占用”再去占用它。

1. 初始化：
   
2. // 0表示没有被占用，非零表示被占用。
   
3. volatile int semaphore = 0;
   
4. 
   
5. 进入：
   
6. // 用原子操作交换来实现写入1（实现上锁）的同时，取回旧值看它是否非零。
   
7. // 旧值非零意味着它已经被别的线程占用了，所以此时干等。直到别的线程退出的时候把0写回。
   
8. while(atomic_exchange(&semaphore, 1) != 0);
   
9. 
   
10. 退出：
    
11. // 写入0来解除占用状态。
    
12. atomic_store(&semaphore, 0);

复制代码

单看逻辑的话，它非常简单，想象一下一堆线程要同时访问一个数据，其中一个线程率先使用原子操作把semaphore设为了1，然后发现它之前是0，这意味着它之前没上锁，于是对数据进行操作。别的线程使用原子操作把semaphore设为1后，取得旧值1，知道数据是被占用的，于是不停地循环等待。而之前占用数据的那个线程它完成了对数据的读写后，它把semaphore的值设为0来解开自旋锁。此时别的线程就可以通过相同的方式来独占这个数据了——把semaphore设为1，并且发现semaphore旧值为0，从而判断出自己对数据的独占权。

TAS方式的自旋锁虽然很简单，但它有很多缺点。其中一个明显的缺点就是它无法保证公平。所谓不公平，意思就是当很多线程都要抢着独占数据的时候，有的线程很可能几乎没有机会获得对数据的独占权，而有的线程则可能每次尝试独占都能成功。
其次是它带来的性能损失很严重。因为atomic_exchange总是让semaphore的缓存行被无效化，不管semaphore是否真的被更新了。
当自旋锁被释放后，此时所有的其它线程都会试图去独占这个锁，这会造成一个名为“Thundering Herd”的问题，其它所有试图去独占这个锁的线程的高速缓存行副本都会被无效化，于是去读取释放这个锁的核心的高速缓存行副本。这个过程会造成O(t)内存交互复杂度（此处的t是线程数）。毕竟atomic_exchange不得不进行原子方式的内存写入。
对于这个问题有个解决方式，那就是在atomic_exchange前，用atomic_load来读取semaphore的值，这样可以避免semaphore的缓存行被无效化。这种自旋锁的变体有个新名字——TTAS（Test-and-test-and-set）

·进化的TAS——使用TTAS（Test-and-test-and-set）方式进行优化。

1. 初始化：
   
2. // 无变化
   
3. volatile int semaphore = 0;
   
4. 
   
5. 进入：
   
6. // 在使用atomic_exchange赋值前，先用atomic_load判断原子锁是否被解锁。
   
7. do
   
8. {
   
9.         while(atomic_load(&semaphore) != 0);
   
10.         // 注意，就算atomic_load判断出原子锁已经被解锁了，
    
11.         // 我们依然要在atomic_exchange的时候取回semaphore的旧值，确保占用过程不会被打断。
    
12. }while(atomic_exchange(&semaphore, 1) != 0);
    
13. 
    
14. 退出：
    
15. // 无变化
    
16. atomic_store(&semaphore, 0);

复制代码

TTAS Lock成功减少了尝试获取锁定时发生的缓存行无效的次数。但，一旦锁被释放，所有线程都在尝试更新semaphore的标志。
如果某个线程看到该锁是空闲的，但由于某个别的线程速度较快而无法独占该锁——TAS的不公平问题依然存在。对于高争用状态的锁，它不能保证每个线程都有同等的机会对数据进行读写。
所以在尝试再次进入临界区之前来个很短的时间等待，可以让别的线程更容易取得独占锁的机会。

所以我们应该怎么优(ji)化(ya gao)呢？根据《牙膏厂架构优化参考手册》（Toothpaste Architectures Optimization Reference Manual）里面提到：向所有自旋循环体添加PAUSE指令可提高奔腾4及更高版本的性能。PAUSE指令向CPU提示正在执行的代码是自旋等待循环。它向后兼容，并且在旧的CPU上相当于NOP指令。它有以下三个好处：
1、它避免了内存顺序违规导致的昂贵的管道刷新成本，因为CPU不需要继续用推测性的方式去加载后续的指令来填充管道了。
2、它给自旋循环体增加了一点延迟，使其与系统的内存总线频率同步。该频率通常远低于CPU的频率，从而达到省一下电的效果。
3、它对牙膏厂超线程CPU核心的另一个同步线程提供了余裕。
此外还有另一种优化，那就是停止自旋，让线程进入休眠状态并重新安排。重点是不要去yield（比如Linux的sched_yield()，Windows的SwitchToThread()，或者C艹11的std::this_thread::yield()），而是去Sleep(一段很短的时间);。这样做的好处是，如果你没有别的线程任务可以安排的话，它会真的进入睡眠状态，这对于超线程的牙膏厂CPU而言可以把更多的运算单元让出来，让有事可做的线程能更快一些。而yield()失败，也就是没有可以安排的别的线程任务的话，它会立即回到之前的自旋循环里面去，等同于跑了个“非PAUSE”的更忙碌的自旋。

·让线程在“干等”的时候没那么“无聊”，至少有点事儿可做（比如省一下电等）——使用PAUSE指令进行优化。

1. 初始化：
   
2. // 无变化
   
3. volatile int semaphore = 0;
   
4. 
   
5. 进入：
   
6. do
   
7. {
   
8.         while(atomic_load(&semaphore) != 0) // 在这个循环里，加入我们之前说的“省一下电”的动作
   
9.                 cpu_relax();
   
10. }while(atomic_exchange(&semaphore, 1) != 0);
    
11. 
    
12. 退出：
    
13. // 无变化
    
14. atomic_store(&semaphore, 0);
    
15. 
    
16. 杂项：
    
17. // “省一下电”的实现过程
    
18. void cpu_relax()
    
19. {
    
20.         // 总之用的就是CPU的pause指令
    
21. #if (OS == WIN)
    
22.     _mm_pause(); // 要包含#include<Windows.h>
    
23. #elif (OS == UNIX)
    
24.     asm("pause");
    
25. #endif
    
26. }

复制代码

但其实对于等待的时间也是讲究的。pause指令可以让CPU以内存频率的速度运行，并且能省电，便于下一次的原子操作。但看起来一个pause似乎并不足以解决公平性的问题。事实上，这个等待的时间长短它也是很讲究的。想象一下你有个线程它独占了数据了后需要花500ms甚至更长的时间进行等待，此时还这么省着电干等下去效率就很低了，甚至不如用usleep()等方式来等。

实验证明，用指数方式进行退避（看到厕所被人占用后，说一句“打扰了”然后暂时不去抢那个厕所，多等一会儿，等的时间以指数方式递增，等得足够久就usleep(

233

)）是一个比较可靠的策略，类似于以太网协议中使用的拥塞避免机制。

·等待合适的时间，并伺机使用usleep()、Sleep()——使用带退避的宽松式TTAS方式进行优化。

1. 初始化：
   
2. // 无变化
   
3. volatile int semaphore = 0;
   
4. 
   
5. 进入：
   
6. cur_max_iters = MIN_BACKOFF_ITERS;
   
7. while(1)
   
8. {
   
9.         // 等待直到锁解开
   
10.         wait_until_lock_is_free(); // 它的具体实现，请看杂项部分。
    
11.         if(atomic_exchange(&semaphore, 1) != 0)
    
12.                 back_off_exp(&cur_max_iters); // 退避——“打扰了。”
    
13.         else
    
14.                 break; // 独占！
    
15. }
    
16. 
    
17. 退出：
    
18. // 无变化
    
19. atomic_store(&semaphore, 0);
    
20. 
    
21. 杂项：
    
22. // 各种常量
    
23. const unsigned MAX_WAIT_ITERS = 0x10000; // 虽然是钦定数值，但可以根据情况来调整
    
24. const unsigned MIN_BACKOFF_ITERS = 32;
    
25. const unsigned MAX_BACKOFF_ITERS = ???;
    
26. 
    
27. // “省一下电”的实现过程
    
28. void cpu_relax()
    
29. {
    
30.         // 无变化
    
31. #if (OS == WIN)
    
32.     _mm_pause();
    
33. #elif (OS == UNIX)
    
34.     asm("pause");
    
35. #endif
    
36. }
    
37. 
    
38. // 睡眠的实现过程
    
39. void yield_sleep()
    
40. {
    
41. #if (OS == WIN)
    
42.         Sleep(1); // 换成NtDelayExecution()可以提高精度
    
43.         // 文档：https://undocumented.ntinternals.net/index.html?page=UserMode%2FUndocumented%20Functions%2FNT%20Objects%2FThread%2FNtDelayExecution.html
    
44. #elif (OS == UNIX)
    
45.         usleep(500);
    
46. #endif
    
47. }
    
48. 
    
49. // 等待直到锁解开
    
50. void wait_until_lock_is_free()
    
51. {
    
52.         volatile size_t iters = 0; // 不要让它被优化掉
    
53.         while(atomic_load(&semaphore) != 0)
    
54.         {
    
55.                 if(iters < MAX_WAIT_ITERS)
    
56.                 {
    
57.                         // 如果需要等待的时间不是很长，跑指令循环等待
    
58.                         iters ++;
    
59.                         cpu_relax();
    
60.                 }
    
61.                 else
    
62.                 {
    
63.                         // 如果需要等待的时间过长，干脆进入睡眠状态
    
64.                         yield_sleep();
    
65.                 }
    
66.         }
    
67. }
    
68. 
    
69. // 指数方式的“打扰了”
    
70. void back_off_exp(size_t *p_cur_max_iters)
    
71. {
    
72.         // 退避的步数在0到最大步数之间随机取值
    
73.         size_t spin_iters = rand() % *p_cur_max_iters;
    
74.        
    
75.         volatile size_t i; // 不要让它被优化掉
    
76.        
    
77.         // 最大步数翻倍。此所谓“指数方式”
    
78.         *p_cur_max_iters = min(*p_cur_max_iters * 2, MAX_BACKOFF_ITERS);
    
79.        
    
80.         // 循环等待
    
81.         for(i = 0; i < spin_iters; i++)
    
82.                 cpu_relax();
    
83. }

复制代码

请看实际效果跑分。
跑分环境：牛马架构双牙膏厂Xeon E5-2630 v2频率2.60 GHz。这款牙膏厂CPU支持超线程，每颗CPU有6个物理核心，也就是12个逻辑核心。
这个NUMA双CPU插槽的机器总共有12个物理核心、24个逻辑核心。

纵轴：花的时间
横轴：线程数量
可以看出，TAS方式（最简单的那个）获取锁的过程花费的时间随线程数量的增长而呈指数方式增长——想象一下你有个64核心的CPU，但你的多线程的程序为了这个独占锁而花费了64倍于单线程的时间。这是十分尴尬的。
所有的TTAS方式的分数都显著比TAS的分数好。刷新缓存的过程确实对性能很伤。
动态退避方式确实也是性能最好的。
并且加入PAUSE指令确实可以把TTAS方式变得更优化一些。

另外，之前的文章内容一直都是在用atomic_exchange来进行实际的锁状态的设置和判断，但其实使用atomic_compare_exchange（对应Windows的API是InterlockedCompareExchange，并且在stdatomic.h有atomic_compare_exchange_weak和atomic_compare_exchange_strong）比单纯使用atomic_exchange效率更高。而且它们基本就是为了此种应用场合而生的。

参考资料：
Test-and-set spinlocks
https://geidav.wordpress.com/2016/03/23/test-and-set-spinlocks/

sml2

不知道NET的SyncLock(System.Threading.Monitor)是怎么实现的  但愿不要是全局总线锁 而是Net自己实现的一个框架级的锁  不至于拖慢系统 233333

Ayala

临界区的锁还分执行锁、读锁、写锁，获取锁的公平性可以用线程的局部储存来调整线程获取到锁定优先级或者干脆排序取锁（很麻烦！）

勇芳软件

已阅，写的不错，年轻人，继续加油，每天写出精彩文章。
请问大家：你看明白吗？

0xAA55

Ayala 发表于 2018-9-29 19:04
临界区的锁还分执行锁、读锁、写锁，获取锁的公平性可以用线程的局部储存来调整线程获取到锁定优先级或者干 ...

目前文章讲的是独占锁，对于读写锁，我正准备写一篇新的文章。

对于锁的公平性，我曾经用过钦定的方式来实现其公平性（钦点线程）。不过对于当时的应用场合，我还是让多个线程通过查询自身的原子自增变量来判断自己该干啥。所以最后我弄了个自获取任务的线程池出来。

此外，我还把“写入后的数据必须被读一次”和“只需要读取到正确的数据即可”的两种情况区分开设计了不同的读写锁方式。我发现其实很多时候多线程的程序都不是同步运行，而是当特定CPU路过的时候，别的CPU都在执行其它进程的任务。

watermelon

学习一下Orz

唐凌

随口扯一句pause指令。
在使用硬件虚拟化的虚拟机里pause指令会引起VM-Exit（虚拟机退出执行，由虚拟机软件接管执行），不会省电。主要看虚拟机软件里的设置是PE（Pause Exit）还是PLE（Pause-Loop Exit）。
如果是PE，则任何pause指令都立即VM-Exit。
如果是PLE，则当CPU认为这个pause指令被循环执行的时候发起VM-Exit。
在AMD处理器上虚拟机软件可以在VMCB里设置Pause Filter Threshold来调整CPU对pause是否被循环执行的判定。
在Intel处理器上虚拟机软件可以在VMCS里设置PLE Gap和PLE Window来调整CPU对pause是否被循环执行的判定。
这么设计应该是为了让虚拟机软件把等待自旋锁的vCPU给直接调度出去。

0xAA55

tangptr@126.com 发表于 2019-6-17 16:25
随口扯一句pause指令。
在使用硬件虚拟化的虚拟机里pause指令会引起VM-Exit（虚拟机退出执行，由虚拟机软件 ...

这相当于如果虚拟机内的软件pause了，它其实相当于去执行主机上的任务了，相当于某种yield。
这不禁令人思考：这岂不就是轻重不分、遇到锁就yield嘛？

这个细节大概对虚拟机的设计者而言非常值得在意——如果虚拟机退出了，那么它应该退出多久合适，以及能否管理它退出的时长？就像对于操作系统而言，应用程序在SwitchToThread()或sched_yield()后，操作系统应该让它咕多久。

唐凌

0xAA55 发表于 2019-6-17 16:45
这相当于如果虚拟机内的软件pause了，它其实相当于去执行主机上的任务了，相当于某种yield。
这不禁令人 ...

嗯，另外也有虚拟机软件在设置PLE门槛时发挥的智慧了，设置不好PLE的门槛，PLE和PE就没啥区别了。比如在Intel处理器上PLE Window（含pause循环的tick数上界）应该设置为一个很大的数，PLE Gap（两次pause指令之间tick数上界）应该设置为一个很小的数。
目测好的虚拟机软件不会闲着蛋疼用PE的方式，Xen就会使用PLE方式。
虚拟机软件也可以选择不拦截pause，于是pause指令在虚拟机里运行时可以省电了。（在VMCB/VMCS的控制区里设置好就行了）。