linux中大核心鎖（BKL--Big Kernel Lock）和自旋鎖(FIFO Ticket Spinlock) -- 2014百度面試題目

這裡先寫一篇基礎文章引入一下自旋鎖、排隊自旋鎖和大核心鎖。       

自旋鎖(spinlock)是一種 linux 核心中廣泛運用的底層同步機制。自旋鎖是一種工作于多處理器環境的特殊的鎖，在單處理環境中自旋鎖的操作被替換為空操作。當某個處理器上的核心執行線程申請自旋鎖時，如果鎖可用，則獲得鎖，然後執行臨界區操作，最後釋放鎖；如果鎖已被占用，線程并不會轉入睡眠狀态，而是忙等待該鎖，一旦鎖被釋放，則第一個感覺此資訊的線程将獲得鎖

本質上用一個整數來表示，值為1代表鎖未被占用。這種無序競争的本質特點導緻執行線程無法保證何時能取到鎖，某些線程可能需要等待很長時間。随着計算機處理器個數的不斷增長，這種“不公平”問題将會日益嚴重。

排隊自旋鎖(fifo ticket spinlock)是 linux 核心 2.6.25 版本引入的一種新型自旋鎖，它通過儲存執行線程申請鎖的順序資訊解決了傳統自旋鎖的“不公平”問題。排隊自旋鎖的代碼由 linux 核心開發者 nick piggin 實作。

傳統的linux 核心自旋鎖的底層資料結構 raw_spinlock_t 定義如下：

slock 雖然被定義為無符号整數，但是實際上被當作有符号整數使用。slock 值為 1 代表鎖未被占用，值為 0 或負數代表鎖被占用。初始化時 slock 被置為 1。

線程通過宏 spin_lock 申請自旋鎖。

盡管擁有使用簡單友善、性能好的優點，自旋鎖也存在自身的不足：

（1）由于傳統自旋鎖無序競争的本質特點，核心執行線程無法保證何時可以取到鎖，某些執行線程可能需要等待很長時間，導緻“不公平”問題的産生。這有兩方面的原因：

a. 随着處理器個數的不斷增加，自旋鎖的競争也在加劇，自然導緻更長的等待時間。

b. 釋放自旋鎖時的重置操作将無效化所有其它正在忙等待的處理器的緩存，那麼在處理器拓撲結構中臨近自旋鎖擁有者的處理器可能會更快地重新整理緩存，因而增大獲得自旋鎖的機率。

（2）由于每個申請自旋鎖的處理器均在全局變量 slock 上忙等待，系統總線将因為處理器間的緩存同步而導緻繁重的流量，進而降低了系統整體的性能。

傳統自旋鎖的“不公平”問題在鎖競争激烈的伺服器系統中尤為嚴重，是以 linux 核心開發者 nick piggin 在 linux 核心 2.6.25 版本中引入了排隊自旋鎖：通過儲存執行線程申請鎖的順序資訊來解決“不公平”問題。

排隊自旋鎖仍然使用原有的 raw_spinlock_t 資料結構，但是賦予 slock 域新的含義。為了儲存順序資訊，slock 域被分成兩部分，分别儲存鎖持有者和未來鎖申請者的票據序号(ticket number)，如下圖所示：

圖示：next和owner域

如果處理器個數不超過 256，則 owner 域為 slock 的 0-7 位，next 域為 slock 的 8-15 位，slock 的高 16 位不使用；如果處理器個數超過 256，則 owner 和 next 域均為 16 位，其中 owner 域為 slock 的低 16 位。可見排隊自旋鎖最多支援 216=65536 個處理器。

隻有 next 域與 owner 域相等時，才表明鎖處于未使用狀态（此時也無人申請該鎖）。排隊自旋鎖初始化時 slock 被置為 0，即 owner 和 next 置為 0。核心執行線程申請自旋鎖時，原子地将 next 域加 1，并将原值傳回作為自己的票據序号。如果傳回的票據序号等于申請時的 owner 值，說明自旋鎖處于未使用狀态，則直接獲得鎖；否則，該線程忙等待檢查 owner

域是否等于自己持有的票據序号，一旦相等，則表明鎖輪到自己擷取。線程釋放鎖時，原子地将 owner 域加 1 即可，下一個線程将會發現這一變化，從忙等待狀态中退出。線程将嚴格地按照申請順序依次擷取排隊自旋鎖，進而完全解決了“不公平”問題。

大核心鎖本質上也是自旋鎖，但是它又不同于自旋鎖，自旋鎖是不可以遞歸獲得鎖的，因為那樣會導緻死鎖。但大核心鎖可以遞歸獲得鎖。大核心鎖用于保護整個核心，而自旋鎖用于保護非常特定的某一共享資源。程序保持大核心鎖時可以發生排程，具體實作是：在執行schedule時，schedule将檢查程序是否擁有大核心鎖，如果有，它将被釋放，以緻于其它的程序能夠獲得該鎖，而當輪到該程序運作時，再讓它重新獲得大核心鎖。注意在保持自旋鎖期間是不運作發生排程的。

需要特别指出，整個核心隻有一個大核心鎖，其實不難了解，核心隻有一個，而大核心鎖是保護整個核心的，當然有且隻有一個就足夠了。

還需要特别指出的是，大核心鎖是曆史遺留，核心中用的非常少，一般保持該鎖的時間較長，是以不提倡使用它。從2.6.11核心起，大核心鎖可以通過配置核心使其變得可搶占（自旋鎖是不可搶占的），這時它實質上是一個互斥鎖，使用信号量實作。

大核心鎖的api包括：

該函數用于得到大核心鎖。它可以遞歸調用而不會導緻死鎖。

該函數用于釋放大核心鎖。當然必須與lock_kernel配對使用，調用了多少次lock_kernel，就需要調用多少次unlock_kernel。

大核心鎖的api使用非常簡單，按照以下方式使用就可以了：