排号自旋锁

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

这是一种先进先出(FIFO)的公平性机制。 

锁的比较
Linux内核实现的排号自旋锁，比更简单的基于test-and-set或exchange的自旋锁，有更低时耗。下表比较了各种自旋锁：
+Comparing Performance of Different Locking Mechanisms 标准   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 NoNoNoYesYes 

排号自旋锁的一个缺点是随着CPU核数增加，性能指数下降。Boyd-Wickizer, Silas, et al. "Non-scalable locks are dangerous." Proceedings of the Linux Symposium. 2012. http://pdos.csail.mit.edu/papers/linux:lock.pdf  

历史
1991年Mellor-Crummey与Scott引入概念。2008年被Linux内核使用。Jonathan Corbet, Ticket spinlocks , Linux Weekly News, February 6, 2008. Retrieved 23. July, 2010. Jeremy Fitzhardinge, paravirt: introduce a "lock-byte" spinlock implementation , Linux kernel, July 7, 2008 2010年7月，解决了半虚拟化问题。2015年3月，Red Hat Enterprise Linux使用了这种锁。

相关工作
 Lamport面包店算法 
 基于队列的自旋锁Michael L. Scott and William N. Scherer III. Scalable Queue-Based Spin Locks with Timeout .
Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, pp. 44-52, 2001.

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

参考文献

Category:并发控制