浅谈spinlock的实现

本文主要汇总spinlock的相关知识点。

如果不了解spinlock，建议先阅读该文：Operating Systems: Three Easy Pieces。

本文不会介绍spinlock的实现细节，详情请参考：

本文的部分内容也是源于上述文章。

cas实现

int CompareAndSwap(int *ptr, int expected, int new) {
	int actual = *ptr;
	if (actual == expected)
		*ptr = new;
	return actual;
}

compare-and-swap指令的功能如上所示。

spinlock的实现代码如下：

typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *lock) {
	// 0 indicates that lock is available, 1 that it is held
	lock->flag = 0;
}

void lock(lock_t *lock) {
	while (CompareAndSwap(&lock->flag, 0, 1) == 1)
		; // spin-wait (do nothing)
}

void unlock(lock_t *lock) {
	lock->flag = 0;
}

基于CAS的实现速度很快，尤其是在没有真正竞态的情况下（事实上大部分时候就是这种情况），但这种方法存在一个缺点：它是不公平的。一旦spinlock被释放，第一个能够成功执行CAS操作的CPU将成为新的owner，没有办法确保在该spinlock上等待时间最长的那个CPU优先获得锁，这将带来延迟不能确定的问题。

为了解决这种无序竞争带来的不公平问题，spinlock的另一种实现方法是采用排队形式的”ticket spinlock”。

Ticket Spinlock

每当一个spinlock的值出现变化时，所有试图获取这个spinlock的CPU都需要读取内存，刷新自己对应的cache line，而最终只有一个CPU可以获得锁，也只有它的刷新才是有意义的。锁的争抢越激烈（试图获取锁的CPU数目越多），无谓的开销也就越大。

MCS Lock

如果在ticket spinlock的基础上进行一定的修改，让多个CPU不再等待同一个spinlock变量，而是基于各自不同的per-CPU的变量进行等待，那么每个CPU平时只需要查询自己对应的这个变量所在的本地cache line，仅在这个变量发生变化的时候，才需要读取内存和刷新这条cache line，这样就可以解决上述问题。

要实现类似这样的spinlock的分身，其中的一种方法就是使用MCS lock。试图获取一个spinlock的每个CPU，都有一份自己的MCS lock。

qspinlock

相比起Linux中只占4个字节的ticket spinlock，MCS lock多了一个指针，要多占4（或者8）个字节，消耗的存储空间是原来的2-3倍。

qspinlock，其首要目标就是改进原生的MCS lock结构体，尽量将原生MCS lock要包含的内容塞进4字节的空间里。

如果只有1个或2个CPU试图获取锁，那么只需要一个4字节的qspinlock就可以了，其所占内存的大小和ticket spinlock一样。当有3个以上的CPU试图获取锁，需要一个qspinlock加上(N-2)个MCS node。

对于设计合理的spinlock，在大多数情况下，锁的争抢都不应该太激烈，最大概率是只有1个CPU试图获得锁，其次是2个，并依次递减。

这也是qspinlock中加入”pending”位域的意义，如果是两个CPU试图获取锁，那么第二个CPU只需要简单地设置”pending”为1，而不用另起炉灶创建一个MCS node。

试图加锁的CPU数目超过3个是小概率事件，但一旦发生，使用ticket spinlock机制就会造成多个CPU的cache line无谓刷新的问题，而qspinlock可以利用MCS node队列来解决这个问题。

可见，使用qspinlock机制来实现spinlock，具有很好的可扩展性，也就是无论当前锁的争抢程度如何，性能都可以得到保证。

参考资料：

文章目录

cas实现

Ticket Spinlock

MCS Lock

qspinlock