排號自旋鎖

排號自旋鎖是計算機科學中的一種多線程同步機制。類似於自旋鎖，但每一個申請排隊自旋鎖的線程獲得一個排隊號（ticket）。至多一個線程擁有自旋鎖，當它釋放鎖時，把自身的ticket加1作為下一個可獲得鎖的ticket，持有該ticket的線程在自旋檢查時就可發現已經獲得了自旋鎖。這種機制類似於一些提供社會服務的場所（如銀行）：進門的顧客從排號機獲取一個等待號，然後不斷檢查當前可服務的號，直至輪到其手持的號。

這是一種先進先出(FIFO)的公平性機制。^[1]^[2]^[3]

Linux內核實現的排號自旋鎖，比更簡單的基於test-and-set或exchange的自旋鎖，有更低時耗。下表比較了各種自旋鎖：^[2]

More information 標準, test-and-set ...

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

Close

排號自旋鎖的一個缺點是隨着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 用於排隊自旋鎖的原子操作

[1]
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]
Solihin, Yan. Fundamentals of parallel computer architecture : multichip and multicore systems. Solihin Pub. 2009: 262–269. ISBN 978-0-9841630-0-7.
[3]
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）.
[4]
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 （頁面存檔備份，存於互聯網檔案館）
[5]
Jonathan Corbet, Ticket spinlocks （頁面存檔備份，存於互聯網檔案館）, Linux Weekly News, February 6, 2008. Retrieved 23. July, 2010.
[6]
Jeremy Fitzhardinge, paravirt: introduce a "lock-byte" spinlock implementation Archive.is的存檔，存檔日期2012-07-08, Linux kernel, July 7, 2008
[7]
Revert "Merge branch 'xen/pvticketlock' into xen/next". [2021-12-19]. （原始內容存檔於2012-07-12）.
[8]
Ticket Spinlocks. [2017-11-27]. （原始內容存檔於2016-11-18）.
[9]
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.

[Sottile-1] [1]
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.

[:0-2] [2]
Solihin, Yan. Fundamentals of parallel computer architecture : multichip and multicore systems. Solihin Pub. 2009: 262–269. ISBN 978-0-9841630-0-7.

[:1-3] [3]
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）.

[4] [4]
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 （頁面存檔備份，存於互聯網檔案館）

[5] [5]
Jonathan Corbet, Ticket spinlocks （頁面存檔備份，存於互聯網檔案館）, Linux Weekly News, February 6, 2008. Retrieved 23. July, 2010.

[6] [6]
Jeremy Fitzhardinge, paravirt: introduce a "lock-byte" spinlock implementation Archive.is的存檔，存檔日期2012-07-08, Linux kernel, July 7, 2008

[7] [7]
Revert "Merge branch 'xen/pvticketlock' into xen/next". [2021-12-19]. （原始內容存檔於2012-07-12）.

[8] [8]
Ticket Spinlocks. [2017-11-27]. （原始內容存檔於2016-11-18）.

[9] [9]
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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Wikiwand in your browser!

排號自旋鎖

Wikiwand in your browser!

鎖的比較

歷史

相關工作

參見

參考文獻