排號自旋鎖

排號自旋鎖是計算機科學中的一種多執行緒同步機制。類似於自旋鎖，但每一個申請排隊自旋鎖的執行緒獲得一個排隊號（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 用於排隊自旋鎖的原子操作