自旋鎖

自旋鎖

自旋鎖是專為防止多處理器併發而引入的一種鎖,它在內核中大量應用於中斷處理等部分(對於單處理器來說,防止中斷處理中的併發可簡單採用關閉中斷的方式,即在標誌寄存器中關閉/打開中斷標誌位,不需要自旋鎖)。

概念


何謂 自旋鎖?它是為實現保護共享資源而提出一種鎖機制。其實,自旋鎖與互斥鎖比較類似,它們都是為了解決對某項資源的互斥使用。無論是 互斥鎖,還是 自旋鎖,在任何時刻,最多只能有一個保持者,也就說,在任何時刻最多只能有一個執行單元獲得鎖。但是兩者在調度機制上略有不同。對於互斥鎖,如果資源已經被佔用,資源申請者只能進入睡眠狀態。但是自旋鎖不會引起調用者睡眠,如果自旋鎖已經被別的執行單元保持,調用者就一直循環在那裡看是否該自旋鎖的保持者已經釋放了鎖,"自旋"一詞就是因此而得名。

原理


跟互斥鎖一樣,一個執行單元要想訪問被自旋鎖保護的 共享資源,必須先得到鎖,在訪問完共享資源后,必須釋放鎖。如果在獲取自旋鎖時,沒有任何執行單元保持該鎖,那麼將立即得到鎖;如果在獲取自旋鎖時鎖已經有保持者,那麼獲取鎖操作將自旋在那裡,直到該自旋鎖的保持者釋放了鎖。由此我們可以看出,自旋鎖是一種比較低級的保護數據結構或代碼片段的原始方式,這種鎖可能存在兩個問題:
死鎖。試圖遞歸地獲得自旋鎖必然會引起死鎖:遞歸程序的持有實例在第二個實例循環,以試圖獲得相同自旋鎖時,不會釋放此自旋鎖。在遞歸程序中使用自旋鎖應遵守下列策略:遞歸程序決不能在持有自旋鎖時調用它自己,也決不能在遞歸調用時試圖獲得相同的自旋鎖。此外如果一個進程已經將資源鎖定,那麼,即使其它申請這個資源的進程不停地瘋狂“自旋”,也無法獲得資源,從而進入死循環。
過多佔用cpu資源。如果不加限制,由於申請者一直在循環等待,因此自旋鎖在鎖定的時候,如果不成功,不會睡眠,會持續的嘗試,單cpu的時候自旋鎖會讓其它process動不了. 因此,一般自旋鎖實現會有一個參數限定最多持續嘗試次數. 超出后, 自旋鎖放棄當前time slice. 等下一次機會。
由此可見,自旋鎖比較適用於鎖使用者保持鎖時間比較短的情況。正是由於自旋鎖使用者一般保持鎖時間非常短,因此選擇自旋而不是睡眠是非常必要的,自旋鎖的效率遠高於互斥鎖。信號量和讀寫信號量適合於保持時間較長的情況,它們會導致調用者睡眠,因此只能在進程上下文使用,而自旋鎖適合於保持時間非常短的情況,它可以在任何上下文使用。如果被保護的共享資源只在進程上下文訪問,使用信號量保護該共享資源非常合適,如果對共享資源的訪問時間非常短,自旋鎖也可以。但是如果被保護的共享資源需要在中斷上下文訪問(包括底半部即中斷處理句柄和頂半部即軟中斷),就必須使用自旋鎖。自旋鎖保持期間是搶佔失效的,而信號量和讀寫信號量保持期間是可以被搶佔的。自旋鎖只有在內核可搶佔或SMP(多處理器)的情況下才真正需要,在單CPU且不可搶佔的內核下,自旋鎖的所有操作都是空操作。
上面簡要介紹了自旋鎖的基本原理,以下將給出具體的例子,進一步闡釋自旋鎖在實際系統中的應用。上面我們已經講過自旋鎖只有在內核可搶佔或SMP(多處理器)的情況下才真正需要,下面我們就以SMP為例,來說明為什麼要使用自旋鎖,以及自旋鎖實現的基本演演算法。

實現


在單處理機環境中可以使用特定的原子級彙編指令swap和test_and_set實現進程互斥,(Swap指令:交換兩個內存單元的內容;test_and_set指令取出內存某一單元(位)的值,然後再給該單元(位)賦一個新值,關於為何這兩條指令能實現互斥我們不在贅述,讀者可以了解其演演算法)這些指令涉及對同一存儲單元的兩次或兩次以上操作,這些操作將在幾個指令周期內完成,但由於中斷只能發生在兩條機器指令之間,而同一指令內的多個指令周期不可中斷,從而保證swap指令或test_and_set指令的執行不會交叉進行.
但在多處理機環境中情況有所不同,例如test_and_set指令包括“取”、“送”兩個指令周期,兩個CPU執行test_and_set(lock)可能發生指令周期上的交叉,假如lock初始為0, CPU1和CPU2可能分別執行完前一個指令周期並通過檢測(均為0),然後分別執行后一個指令周期將lock設置為1,結果都取回0作為判斷臨界區空閑的依據,從而不能實現互斥. 如圖4-3所示.
為在多CPU環境中利用test_and_set指令實現進程互斥,硬體需要提供進一步的支持,以保證test_and_set指令執行的原子性. 這種支持目前多以“鎖匯流排”(bus locking)的形式提供的,由於test_and_set指令對內存的兩次操作都需要經過匯流排,在執行test_and_set指令之前鎖住匯流排,在執行test_and_set指令后開放匯流排,即可保證test_and_set指令執行的原子性,用法如下:
演演算法4-6:多處理機互斥演演算法(自旋鎖演演算法)
do{
b=1;
while(b){
lock(bus);
b = test_and_set(&lock);
unlock(bus);
}
臨界區
lock = 0;
其餘部分
}while(1)
總之,自旋鎖是一種對多處理器相當有效的機制,而在單處理器非搶佔式的系統中基本上沒有作用。自旋鎖在SMP系統中應用得相當普遍。在許多SMP系統中,允許多個處理機同時執行目態程序,而一次只允許一個處理機執行操作系統代碼,利用一個自旋鎖可以很容易實現這種控制.一次只允許一個CPU執行核心代碼併發性不夠高,若期望核心程序在多CPU之間的并行執行,將核心分為若干相對獨立的部分,不同的CPU可以同時進入和執行核心中的不同部分,實現時可以為每個相對獨立的區域設置一個自旋鎖.

初衷


事實上,自旋鎖的初衷就是:在短期間內進行輕量級的鎖定。一個被爭用的自旋鎖使得請求它的線程在等待鎖重新可用的期間進行自旋(特別浪費處理器時間),所以自旋鎖不應該被持有時間過長。如果需要長時間鎖定的話, 最好使用信號量。
1自旋鎖實際上是忙等鎖
徠當鎖不可用時,CPU一直循環執行“測試並設置”該鎖直到可用而取得該鎖,CPU在等待自旋鎖時不做任何有用的工作,僅僅是等待。因此,只有在佔用鎖的時間極短的情況下,使用自旋鎖才是合理的。當臨界區很大或有共享設備的時候,需要較長時間佔用鎖,使用自旋鎖會降低系統的性能。
自旋鎖可能導致系統死鎖
引發這個問題最常見的情況是遞歸使用一個自旋鎖,即如果一個已經擁有某個自旋鎖的CPU 想第二次獲得這個自旋鎖,則該CPU 將死鎖。此外,如果進程獲得自旋鎖之後再阻塞,也有可能導致死鎖的發生。copy_from_user()、copy_to_user()和kmalloc()等函數都有可能引起阻塞,因此在自旋鎖的佔用期間不能調用這些函數。代碼清單7.2 給出了自旋鎖的使用實例,它被用於實現使得設備只能被最多一個進程打開。

基本形式


自旋鎖的基本形式如下:
spin_lock(&mr_lock);
//臨界區
spin_unlock(&mr_lock);
因為自旋鎖在同一時刻只能被最多一個內核任務持有,所以一個時刻只有一個線程允許存在於臨界區中。這點很好地滿足了對稱多處理機器需要的鎖定服務。在單處理器上,自旋鎖僅僅當作一個設置內核搶佔的開關。如果內核搶佔也不存在,那麼自旋鎖會在編譯時被完全剔除出內核。
簡單的說,自旋鎖在內核中主要用來防止多處理器中併發訪問臨界區,防止內核搶佔造成的競爭。另外自旋鎖不允許任務睡眠(持有自旋鎖的任務睡眠會造成自死鎖——因為睡眠有可能造成持有鎖的內核任務被重新調度,而再次申請自己已持有的鎖),它能夠在中斷上下文中使用。
死鎖:假設有一個或多個內核任務和一個或多個資源,每個內核都在等待其中的一個資源,但所有的資源都已經被佔用了。這便會發生所有內核任務都在相互等待,但它們永遠不會釋放已經佔有的資源,於是任何內核任務都無法獲得所需要的資源,無法繼續運行,這便意味著死鎖發生了。自死瑣是說自己佔有了某個資源,然後自己又申請自己已佔有的資源,顯然不可能再獲得該資源,因此就自縛手腳了。