排號自旋鎖
排號自旋鎖是計算機科學中的一種多線程同步機制。類似於自旋鎖,但每一個申請排隊自旋鎖的線程獲得一個排隊號(ticket)。至多一個線程擁有自旋鎖,當它釋放鎖時,把自身的ticket加1作為下一個可獲得鎖的ticket,持有該ticket的線程在自旋檢查時就可發現已經獲得了自旋鎖。這種機制類似於一些提供社會服務的場所(如銀行):進門的顧客從排號機獲取一個等待號,然後不斷檢查當前可服務的號,直至輪到其手持的號。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/8/84/Take_a_ticket.jpg/220px-Take_a_ticket.jpg)
這是一種先進先出(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.