排号自旋锁
排号自旋锁是计算机科学中的一种多线程同步机制。类似于自旋锁，但每一个申请排队自旋锁的线程获得一个排队号（ticket）。至多一个线程拥有自旋锁，当它释放锁时，把自身的ticket加1作为下一个可获得锁的ticket，持有该ticket的线程在自旋检查时就可发现已经获得了自旋锁。这种机制类似于一些提供社会服务的场所（如银行）：进门的顾客从排号机获取一个等待号，然后不断检查当前可服务的号，直至轮到其手持的号。
这是一种先进先出(FIFO)的公平性机制。[1][2][3]
锁的比较
Linux内核实现的排号自旋锁，比更简单的基于test-and-set或exchange的自旋锁，有更低时耗。下表比较了各种自旋锁：[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 用于排队自旋锁的原子操作
参考文献
- ^ Sottile, Matthew J.; Mattson, Timothy G.; Rasmussen, Craig E. Introduction to Concurrency in Programming Languages. Boca Raton, FL, USA: CRC Press. Sep 28, 2009: 56. ISBN 978-1-4200-7214-3.
- ^ 2.0 2.1 2.2 Solihin, Yan. Fundamentals of parallel computer architecture : multichip and multicore systems. Solihin Pub. 2009: 262–269. ISBN 978-0-9841630-0-7.
- ^ 3.0 3.1 John M. Mellor-Crummey and Michael L. Scott; et al. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM TOCS. February 1991. （原始内容存档于2021-02-02）.
- ^ 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 （页面存档备份，存于互联网档案馆）
- ^ Jonathan Corbet, Ticket spinlocks （页面存档备份，存于互联网档案馆）, Linux Weekly News, February 6, 2008. Retrieved 23. July, 2010.
- ^ Jeremy Fitzhardinge, paravirt: introduce a "lock-byte" spinlock implementation Archive.is的存档，存档日期2012-07-08, Linux kernel, July 7, 2008
- ^ Revert "Merge branch 'xen/pvticketlock' into xen/next". [2021-12-19]. （原始内容存档于2012-07-12）.
- ^ Ticket Spinlocks. [2017-11-27]. （原始内容存档于2016-11-18）.
- ^ 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.