no-scalable lock及其解决方案

请设置文章作者

发布于：Apr 25, 2022

次浏览

Summary

• 有共享就得考虑哪里有瓶颈
• no-scalable问题的本质就是”即共享又私下算账, 最后还要那私账说事”

Abstract

所谓no-scalable lock就是，并发程序为了实现一致性，需要使用锁对共享资源进行互斥访问。如果使用的是一个no-scalable的锁，那么就会观察到随着cpu核心数量的上升，并发程序的性能并不能得到有效的提高，甚至会有所下降。

要理解这个问题的根源需要我们深入了解CPU内部缓存一致性的细节。这就是为什么高性能计算需要对硬件熟悉，而不仅仅是进程数的堆砌。

本文将会介绍no scalable产生的原因，并介绍一种Mscalable的锁MCS LOCK(MCS是三个发明者的首字母)

no scalable lock

如何判断一个锁是不是no scalable的锁，其中一个简单是办法是：如果这个锁是通过访问同一资源来实现互斥的，或者说是single cache line，那么该锁就是no scalable的。这个结论的原理是CPU的缓存一致性协议。

缓存一致性协议带来的问题简单来说就是：CPU间为了达成缓存一致性，需要引入额外的”通信复杂度”，从而每条指令的执行周期(cycle)就增加了。并且随着CPU(core)的增加，这个通信的开销也会增加，那么并发程序带来的优势就没有了。

可扩展性断崖

对应这个问题的一个直观理解是：核越多，需要的交互越多，对single cache line的竞争就越激烈

下面通过阿姆达尔定律(Amdahl’s law)分析这点

$$S = \frac{1}{(1-p) + \frac{p}{n}} $$

• S表示加速比
• p表示提升的部分所占的比例
• n表示提升的倍数

对应到我们这里的情况，p就表示可并行的比例，n表示核心数。因为缓存一致性协议的存在，CPU间需要大量的通信来保证一致性，如果单CPU的周期的1个cycle，那么64核就可能变为了120个cycle

那么CPU在临界区中的时间就变多了，可并行的比例就下降了。即p减小，p减小S相应的减小导致可扩展性断崖问题。

Scalable lock: MCS lock

好的，我们已经识别到了导致可扩展性断崖问题的原因是因为频繁的竞争single cache line，不单自己无法获取，还污染别人的cache。那么一个直观的解法就是: 等待时间长一点呗。这就是back-off策略，但是显然，这治标不治本。

对于这个问题一个经典的解法就是：MCS lock。MCS锁是一个FIFO的lock，其核心思路就是：每个节点单独缓存行，避免单一缓存行竞争

就好比排队，排队的时候你只需要盯着你前面的那个人看就行了。

1
2
3
4
5
6
7
8

                            tail
                             │
  lock                       ▼
┌──────┐     ┌──────┐     ┌──────┐
│      │     │      │     │      │
│ grant├────►│ wait ├────►│ wait │
│      │     │      │     │      │
└──────┘     └──────┘     └──────┘

MCS是一个FIFO锁

• 前一个节点指向下一个节点，每个节点只需要等待自己的状态变为granted(即拿到锁)
• 那到锁的节点就是队首
• 拿锁的时候如何队列为空，那就获得锁，成为队首
• 如果拿锁的时候队列不为空，那就是锁已被占用，插入队尾
• 释放锁的时候传给下一个节点(如果存在的话)
  • “有点协作式的意思”
• 需要注意的是
  • 插入时使用原子操作，将队尾指针指向自己(因为可能并行抢锁吗)
  • 放锁时的一个难点: 放锁的节点是最后一个节点

放锁时的一个难点: 放锁的节点是最后一个节点，释放锁和插入队列就可能导致tail指针的竞争。解决就是使用原子操作完成

假设这么一个情景：最后一个节点释放锁的同时，一个节点插入队列。会出现两种情况：

1. 原子操作的释放成功：tail指向null，那么插入的节点看到的就是队列空，获得锁
2. tricky 原子操作的插入成功：tail指向新节点，那么做释放操作的节点应该能感知到(如tail不指向自己)，然后释放失败并 重试