1014
linux中大內核鎖（BKL--Big Kernel Lock）和自旋鎖(FIFO Ticket Spinlock) -- 2014百度麵試題目
這裏先寫一篇基礎文章引入一下自旋鎖、排隊自旋鎖和大內核鎖。
自旋鎖(Spinlock)是一種 Linux 內核中廣泛運用的底層同步機製。自旋鎖是一種工作於多處理器環境的特殊的鎖，在單處理環境中自旋鎖的操作被替換為空操作。當某個處理器上的內核執行線程申請自旋鎖時，如果鎖可用，則獲得鎖，然後執行臨界區操作，最後釋放鎖；如果鎖已被占用，線程並不會轉入睡眠狀態，而是忙等待該鎖，一旦鎖被釋放，則第一個感知此信息的線程將獲得鎖
linux傳統的自旋鎖
本質上用一個整數來表示，值為1代表鎖未被占用。這種無序競爭的本質特點導致執行線程無法保證何時能取到鎖，某些線程可能需要等待很長時間。隨著計算機處理器個數的不斷增長，這種“不公平”問題將會日益嚴重。
排隊自旋鎖(FIFO Ticket Spinlock)是 Linux 內核 2.6.25 版本引入的一種新型自旋鎖，它通過保存執行線程申請鎖的順序信息解決了傳統自旋鎖的“不公平”問題。排隊自旋鎖的代碼由 Linux 內核開發者 Nick Piggin 實現。
傳統的Linux 內核自旋鎖的底層數據結構 raw_spinlock_t 定義如下：
typedef struct {
unsigned int slock;
} raw_spinlock_t;
slock 雖然被定義為無符號整數，但是實際上被當作有符號整數使用。slock 值為 1 代表鎖未被占用，值為 0 或負數代表鎖被占用。初始化時 slock 被置為 1。
線程通過宏 spin_lock 申請自旋鎖。
盡管擁有使用簡單方便、性能好的優點，自旋鎖也存在自身的不足：
（1）由於傳統自旋鎖無序競爭的本質特點，內核執行線程無法保證何時可以取到鎖，某些執行線程可能需要等待很長時間，導致“不公平”問題的產生。這有兩方麵的原因：
a. 隨著處理器個數的不斷增加，自旋鎖的競爭也在加劇，自然導致更長的等待時間。
b. 釋放自旋鎖時的重置操作將無效化所有其它正在忙等待的處理器的緩存，那麼在處理器拓撲結構中臨近自旋鎖擁有者的處理器可能會更快地刷新緩存，因而增大獲得自旋鎖的機率。
（2）由於每個申請自旋鎖的處理器均在全局變量 slock 上忙等待，係統總線將因為處理器間的緩存同步而導致繁重的流量，從而降低了係統整體的性能。
linux排隊自旋鎖
傳統自旋鎖的“不公平”問題在鎖競爭激烈的服務器係統中尤為嚴重，因此 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 即可，下一個線程將會發現這一變化，從忙等待狀態中退出。線程將嚴格地按照申請順序依次獲取排隊自旋鎖，從而完全解決了“不公平”問題。
linux大內核鎖
大內核鎖本質上也是自旋鎖，但是它又不同於自旋鎖，自旋鎖是不可以遞歸獲得鎖的，因為那樣會導致死鎖。但大內核鎖可以遞歸獲得鎖。大內核鎖用於保護整個內核，而自旋鎖用於保護非常特定的某一共享資源。進程保持大內核鎖時可以發生調度，具體實現是：在執行schedule時，schedule將檢查進程是否擁有大內核鎖，如果有，它將被釋放，以致於其它的進程能夠獲得該鎖，而當輪到該進程運行時，再讓它重新獲得大內核鎖。注意在保持自旋鎖期間是不運行發生調度的。
需要特別指出，整個內核隻有一個大內核鎖，其實不難理解，內核隻有一個，而大內核鎖是保護整個內核的，當然有且隻有一個就足夠了。
還需要特別指出的是，大內核鎖是曆史遺留，內核中用的非常少，一般保持該鎖的時間較長，因此不提倡使用它。從2.6.11內核起，大內核鎖可以通過配置內核使其變得可搶占（自旋鎖是不可搶占的），這時它實質上是一個互斥鎖，使用信號量實現。
大內核鎖的API包括：
void lock_kernel(void);
該函數用於得到大內核鎖。它可以遞歸調用而不會導致死鎖。
void unlock_kernel(void);
該函數用於釋放大內核鎖。當然必須與lock_kernel配對使用，調用了多少次lock_kernel，就需要調用多少次unlock_kernel。
大內核鎖的API使用非常簡單，按照以下方式使用就可以了：
lock_kernel(); //對被保護的共享資源的訪問 … unlock_kernel()；
最後更新：2017-04-03 15:21:51