排号自旋锁

排号自旋锁是计算机科学中的一种多线程同步机制。类似于自旋锁，但每一个申请排队自旋锁的线程获得一个排队号（ticket）。至多一个线程拥有自旋锁，当它释放锁时，把自身的ticket加1作为下一个可获得锁的ticket，持有该ticket的线程在自旋检查时就可发现已经获得了自旋锁。这种机制类似于一些提供社会服务的场所（如银行）：进门的顾客从排号机获取一个等待号，然后不断检查当前可服务的号，直至轮到其手持的号。

排号队列管理机制的一个ticket与"Now Serving"符号

这是一种先进先出(FIFO)的公平性机制。^[1][2][3]

锁的比较

Linux内核实现的排号自旋锁，比更简单的基于test-and-set或exchange的自旋锁，有更低时耗。下表比较了各种自旋锁：^[2]

Comparing Performance of Different Locking Mechanisms^[2]

标准	test-and-set	Test and Test-and-set	Load-link/store-conditional	Ticket	ABQL
Uncontended latency	Lowest	Lower	Lower	Higher	Higher
1 Release max traffic	Ө(p)	Ө(p)	Ө(p)	Ө(p)	Ө(1)
Wait traffic	High	-	-	-	-
Storage	Ө(1)	Ө(1)	Ө(1)	Ө(1)	Ө(p)
Fairness guarantee	No	No	No	Yes	Yes

排号自旋锁的一个缺点是随着CPU核数增加，性能指数下降。^[4]

历史

1991年Mellor-Crummey与Scott引入概念。^[3]2008年被Linux内核使用。^{[5] [6]} 2010年7月，解决了半虚拟化问题。^[7]2015年3月，Red Hat Enterprise Linux使用了这种锁。^[8]

相关工作

• Lamport面包店算法
• 基于队列的自旋锁^[9]

参见

• fetch-and-add 用于排队自旋锁的原子操作