自旋锁在用户态下的应用——谈folly库的MicroSpinLock

自旋锁（如pthreads中的pthread_spin_lock）特点是线程一直占用cpu，直到其他线程退出临界区、设置锁释放标志。相比基于OS休眠和唤醒机制的互斥锁（如pthreads中的mutex），自旋锁更适用于临界区短、对cpu延时要求比较高的情况。

而当临界区持续时间较长时，传统的自旋锁会有高cpu占用率的缺点；用户态下的进程又有可能被更高优先级的进程或内核线程抢占的可能，因而不能很准确地计算用户态程序临界区持续时间。

那么有没有什么方法，既能在临界区短时，自旋锁像传统意义那样工作，在临界区持续时间较长时，让出cpu，降低cpu资源消耗呢？

Fackbook folly库的MicroSpinLock就是根据以上需求改进而来的spin lock，下面我们看其具体实现。

MicroSpinLock实现spin lock的核心是cas原语，cas过程是原子的，其依赖于硬件实现，x86上对应cmpxchg指令。cas原语的逻辑如下：

以上addr是lock（可以是一个unsinged char变量）的起始地址，expected是当前进程认为lock起始地址头字节应该等于的值，newValue是当前进程将要赋给lock起始地址头字节的值。

利用cas原语，我们可以设计实现spin lock的方法为：

1. 设定锁的两种状态enum{ FREE=0, LOCKED=1 }
2. 当前进程调用cas(&lock, FREE, LOCKED)进行加锁（实际就是尝试改变lock头字节为1）
3. 若lock头字节不为本进程预期的值0，表示有其他进程已占用锁，cas返回false
4. 当前进程反复以上过程，直到case返回true，此时本进程加锁成功

由以上逻辑，有以下代码实现：

有了基于cas原语实现的spin lock，我们可以进一步考虑如何在临界区持续时间较长的情况下，如何让spin lock让出cpu。简单地，我们引入一个计数器spinCount，每次尝试加锁时spinCount加1，当spinCount达到一定次数时调用sleep，让进程休眠以让出cpu，如是有以下代码实现：

基于我们临界区短时使用spin lock的假设，多数是不会出现锁竞争情况的，因而很少会调用sleep进行休眠。我们通过添加一条语句，减少不必要的执行路径：

又因为在锁竞争情况出现时，锁未释放的情况下没必要再进行一次加锁操作，因而代码可以修改为：

以上方法属于锁的double check优化，在lock == FREE条件不达成的情况下，避免不必要的加锁开销。

folly MicroSpinLock源码地址：
https://github.com/facebook/folly/blob/master/folly/SmallLocks.h

Have fun!