System|并发|Rethinking Lock

朝闻君

发布于 2021-11-22 10:50:45

3250

发布于 2021-11-22 10:50:45

文章被收录于专栏：用户9199536的专栏

并发控制是多核系统中最重要的问题，人们常常使用锁进行实现，然而，在保证正确性的同时，人们发现随着核数的上升，锁的性能可拓展性断崖却制约了并发的上限。因此，多核架构下很多创新的并发控制算法应运而生。

本文将从悲观锁、乐观锁等两方面介绍它们所使用的并发控制算法实现

悲观锁

自旋锁

自旋锁是最简单的实现，仰仗于硬件提供的原子性操作CAS(compare and swap)。

Intel中通过锁总线保证，相当于硬件版的悲观锁
ARM中则通过Load-linked & Store-conditional(LL/SC)保证，相当于硬件版的乐观锁

void lock(int *lock) {
while(atomic_CAS(lock, 0, 1)!= 0)
/* Busy-looping */ ;
}
void unlock(int *lock) {
*lock = 0;
}

然而，自旋锁的问题在于，所有的竞争者都是一视同仁的，运气差的竞争者可能一辈子获取不到锁导致饥饿，从而破坏了互斥访问/有限等待/空闲让进中的有限等待。

排号锁

排号锁的思想类似于我们餐厅排队，叫号时进行消费，采取FIFO的方式，仰仗于硬件提供的原子性操作FAA(fetch and add)。由于FIFO，因此解决了有限等待的问题。

void lock(int *lock) {
volatile unsigned my_ticket =
atomic_FAA(&lock->next, 1);
while(lock->owner != my_ticket)
/* busy waiting */;
}
void unlock(int *lock) {
lock->owner ++;
}

读写锁

互斥锁的条件太过于苛刻，我们希望临界区的读者之间并行，读者与写者之间互斥，从而提高读的性能。

偏向写者: 有写者等待读者时，读者不能进入临界区(更公平)
偏向读者: 有写者等待读者时，读者可以进入临界区(更并行)

偏向读者

Read Copy Update(RCU)

读写锁只能保证读并行，但是如果写者进入临界区便无法读取。RCU解决了这个问题

当写操作时，对副本进行修改(写互斥)，写操作完成后，原子性地将指针指向修改的副本
当读操作进入临界区时引用计数++，离开临界区时引用计数--,引用计数为0后回收旧拷贝

MVCC-2PL

MVCC指的是通过为每个数据单元赋予版本号的方式，使得版本号更大的数据对于版本号更小的事务不可见。这个隔离级别名为快照隔离，避免了读写冲突。与此同时，面对写写冲突，采用传统的2PL方式避免,2PL指的是第一阶段只获得锁，第二阶段只释放锁，而不交错。

mysql中，MVCC的实现通过为每个tuple赋予版本号以及其上个版本地址

InnoDB

CLH锁

让我们回到自旋锁,可拓展性断崖出现了!最重要的问题在于，所有的核都想要对于lock进行修改，对单一缓存行的竞争导致严重的性能开销。

while(atomic_CAS(lock, 0, 1)!= 0);

因为在缓存一致性的MSI协议中，我们需要存储缓存行对每个核的状态，而状态通过bit存储在全局目录项中。而当多核同时竞争这个目录项时性能会剧烈下降。

综上，在单一的数据结构上进行加锁是不具备可拓展性的，我们必须为每个竞争者维护其本地的状态，从而减少单一缓存行的竞争，这便成了队列锁

CLH锁基于链表，申请线程不断轮询前驱的状态(volatile)，如果发现前驱释放了锁就结束自旋。当然，自旋是个傻事，所以在Java的实现中采用park和unpark避免其占用CPU。

当然，CLH锁也会导致所有的申请线程对于队尾竞争，但是因为入队的开销远远小于轮询的开销，并非关键路径，因此在关键路径上避免对单一缓存行的高度竞争

public abstract class AbstractQueuedSynchronizer{
static final class Node {
    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter; 
}
private transient volatile Node head;
private transient volatile Node tail;
private volatile int state;
}

MCS锁

CLH锁的问题在于，其对前驱自旋，而非本地变量，因此在NUMA架构下由于访问非本地的内存而更慢。MCS锁选择对于本地状态自旋。

Queue Spinlock

Reference: https://lwn.net/Articles/561775/ 兰新宇：Linux中的spinlock机制[三] - qspinlock

Qspinlock的思想在于，竞争者仅有两个的时候，状态保存在qspinlock上，而多于两者时，转化为MCS锁。从而保证了高竞争和低竞争情况下分别具有高性能。

Cohort锁

然而MCS并不能真正解决NUMA的问题，尽管锁能控制自己所访问的状态是本地的，但是却无法控制临界区访问的数据也是本地的。

Lock Cohorting的思路在于: 在一定时间内将访存局限在本地。

分为两种锁，分别是本地锁和全局锁。

申请时先获得本地锁，再获得全局锁。
当全局锁释放时，传给本地等待队列的下一位。
直到一个NUMA节点全部结束后才能由其他节点获取锁。

Lock Cohorting: A General Technique for Designing NUMA Locks

乐观锁

CAS

JAVA中所有锁的底层本质上都是CAS，也就是上文提到的硬件原子性支持。

在执行修改前获取对象的值作为预期，然后在修改时进行验证，如果此时对象的值不符合预期，说明存在写写冲突不能修改；否则正常修改对象。

在Java中var1代表对象地址,var2表示字段偏移量,var4表示预期值,var5表示修改值。

字段偏移量通过Object.class.getDeclaredField("fieldname"))获得

    public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
    public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

有个ABA现象，就是如果只看预期值的话，万一预期A但是途中被修改成了B最终又被改成A，就会误判没有发生修改。方法就是加个版本号，改一次++，或者用标记表示是否被修改。

OCC

OCC假设并发的写数目较少，而并发读较多，这玩意儿其实就是大号CAS。