layout: post
title: "Big Kernel Lock vs FIFO Ticket Spinlock in Linux"
date: 2013-10-30 18:58
comments: true
categories: Linux
tag: [linux, kernel, spinlock, big kernel lock, baidu]
keywords: linux kernel, spinlock kernel lock
description: a item from 2014 baidu interview
這里先寫一篇基礎(chǔ)文章引入一下自旋鎖纹蝴、排隊(duì)自旋鎖和大內(nèi)核鎖扩所。
自旋鎖(Spinlock)是一種 Linux 內(nèi)核中廣泛運(yùn)用的底層同步機(jī)制。自旋鎖是一種工作于多處理器環(huán)境的特殊的鎖刻剥，在單處理環(huán)境中自旋鎖的操作被替換為空操作育灸。當(dāng)某個(gè)處理器上的內(nèi)核執(zhí)行線程申請(qǐng)自旋鎖時(shí)腻窒，如果鎖可用，則獲得鎖磅崭，然后執(zhí)行臨界區(qū)操作儿子，最后釋放鎖；{% img right http://image.zcool.com.cn/cover/20/23/1305391757594.jpg 328 268 %}如果鎖已被占用绽诚，線程并不會(huì)轉(zhuǎn)入睡眠狀態(tài)典徊，而是忙等待該鎖杭煎，一旦鎖被釋放恩够，則第一個(gè)感知此信息的線程將獲得鎖。
linux傳統(tǒng)的自旋鎖
本質(zhì)上用一個(gè)整數(shù)來(lái)表示羡铲，值為1代表鎖未被占用蜂桶。這種無(wú)序競(jìng)爭(zhēng)的本質(zhì)特點(diǎn)導(dǎo)致執(zhí)行線程無(wú)法保證何時(shí)能取到鎖，某些線程可能需要等待很長(zhǎng)時(shí)間也切。隨著計(jì)算機(jī)處理器個(gè)數(shù)的不斷增長(zhǎng)扑媚，這種“不公平”問(wèn)題將會(huì)日益嚴(yán)重。
排隊(duì)自旋鎖(FIFO Ticket Spinlock)是 Linux 內(nèi)核 2.6.25 版本引入的一種新型自旋鎖雷恃，它通過(guò)保存執(zhí)行線程申請(qǐng)鎖的順序信息解決了傳統(tǒng)自旋鎖的“不公平”問(wèn)題疆股。排隊(duì)自旋鎖的代碼由 Linux 內(nèi)核開(kāi)發(fā)者 Nick Piggin 實(shí)現(xiàn)。
傳統(tǒng)的Linux 內(nèi)核自旋鎖的底層數(shù)據(jù)結(jié)構(gòu) raw_spinlock_t 定義如下：
typedef struct {
unsigned int slock;
} raw_spinlock_t;
slock 雖然被定義為無(wú)符號(hào)整數(shù)倒槐，但是實(shí)際上被當(dāng)作有符號(hào)整數(shù)使用旬痹。slock 值為 1 代表鎖未被占用，值為 0 或負(fù)數(shù)代表鎖被占用讨越。初始化時(shí) slock 被置為 1两残。
線程通過(guò)宏 spin_lock 申請(qǐng)自旋鎖。
盡管擁有使用簡(jiǎn)單方便把跨、性能好的優(yōu)點(diǎn)人弓，自旋鎖也存在自身的不足：
- 由于傳統(tǒng)自旋鎖無(wú)序競(jìng)爭(zhēng)的本質(zhì)特點(diǎn)，內(nèi)核執(zhí)行線程無(wú)法保證何時(shí)可以取到鎖着逐，某些執(zhí)行線程可能需要等待很長(zhǎng)時(shí)間崔赌，導(dǎo)致“不公平”問(wèn)題的產(chǎn)生意蛀。這有兩方面的原因：
- 隨著處理器個(gè)數(shù)的不斷增加，自旋鎖的競(jìng)爭(zhēng)也在加劇健芭，自然導(dǎo)致更長(zhǎng)的等待時(shí)間浸间。
- 釋放自旋鎖時(shí)的重置操作將無(wú)效化所有其它正在忙等待的處理器的緩存，那么在處理器拓?fù)浣Y(jié)構(gòu)中臨近自旋鎖擁有者的處理器可能會(huì)更快地刷新緩存吟榴，因而增大獲得自旋鎖的機(jī)率魁蒜。
- 由于每個(gè)申請(qǐng)自旋鎖的處理器均在全局變量 slock 上忙等待，系統(tǒng)總線將因?yàn)樘幚砥鏖g的緩存同步而導(dǎo)致繁重的流量吩翻，從而降低了系統(tǒng)整體的性能兜看。
linux排隊(duì)自旋鎖
傳統(tǒng)自旋鎖的“不公平”問(wèn)題在鎖競(jìng)爭(zhēng)激烈的服務(wù)器系統(tǒng)中尤為嚴(yán)重，因此 Linux 內(nèi)核開(kāi)發(fā)者 Nick Piggin 在 Linux 內(nèi)核 2.6.25 版本中引入了排隊(duì)自旋鎖：通過(guò)保存執(zhí)行線程申請(qǐng)鎖的順序信息來(lái)解決“不公平”問(wèn)題狭瞎。
排隊(duì)自旋鎖仍然使用原有的 raw_spinlock_t 數(shù)據(jù)結(jié)構(gòu)细移，但是賦予 slock 域新的含義。為了保存順序信息熊锭，slock 域被分成兩部分弧轧，分別保存鎖持有者和未來(lái)鎖申請(qǐng)者的票據(jù)序號(hào)(Ticket Number)，如下圖所示:
圖示：next和owner域
如果處理器個(gè)數(shù)不超過(guò) 256碗殷，則 Owner 域?yàn)?slock 的 0-7 位精绎，Next 域?yàn)?slock 的 8-15 位，slock 的高 16 位不使用锌妻；如果處理器個(gè)數(shù)超過(guò) 256代乃，則 Owner 和 Next 域均為 16 位，其中 Owner 域?yàn)?slock 的低 16 位仿粹「橄牛可見(jiàn)排隊(duì)自旋鎖最多支持 216=65536 個(gè)處理器.。
只有 Next 域與 Owner 域相等時(shí)吭历，才表明鎖處于未使用狀態(tài)（此時(shí)也無(wú)人申請(qǐng)?jiān)撴i）堕仔。排隊(duì)自旋鎖初始化時(shí) slock 被置為 0，即 Owner 和 Next 置為 0晌区。內(nèi)核執(zhí)行線程申請(qǐng)自旋鎖時(shí)摩骨，原子地將 Next 域加 1，并將原值返回作為自己的票據(jù)序號(hào)契讲。如果返回的票據(jù)序號(hào)等于申請(qǐng)時(shí)的 Owner 值仿吞，說(shuō)明自旋鎖處于未使用狀態(tài)，則直接獲得鎖捡偏；否則唤冈，該線程忙等待檢查 Owner 域是否等于自己持有的票據(jù)序號(hào)，一旦相等银伟，則表明鎖輪到自己獲取你虹。線程釋放鎖時(shí)绘搞，原子地將 Owner 域加 1 即可，下一個(gè)線程將會(huì)發(fā)現(xiàn)這一變化傅物，從忙等待狀態(tài)中退出夯辖。線程將嚴(yán)格地按照申請(qǐng)順序依次獲取排隊(duì)自旋鎖，從而完全解決了“不公平”問(wèn)題董饰。
linux大內(nèi)核鎖
大內(nèi)核鎖本質(zhì)上也是自旋鎖蒿褂，但是它又不同于自旋鎖，自旋鎖是不可以遞歸獲得鎖的卒暂，因?yàn)槟菢訒?huì)導(dǎo)致死鎖啄栓。但大內(nèi)核鎖可以遞歸獲得鎖。大內(nèi)核鎖用于保護(hù)整個(gè)內(nèi)核也祠，而自旋鎖用于保護(hù)非常特定的某一共享資源昙楚。進(jìn)程保持大內(nèi)核鎖時(shí)可以發(fā)生調(diào)度，具體實(shí)現(xiàn)是：在執(zhí)行schedule時(shí)诈嘿，schedule將檢查進(jìn)程是否擁有大內(nèi)核鎖堪旧，如果有，它將被釋放奖亚，以致于其它的進(jìn)程能夠獲得該鎖淳梦，而當(dāng)輪到該進(jìn)程運(yùn)行時(shí)，再讓它重新獲得大內(nèi)核鎖遂蛀。注意在保持自旋鎖期間是不運(yùn)行發(fā)生調(diào)度的谭跨。
需要特別指出干厚，整個(gè)內(nèi)核只有一個(gè)大內(nèi)核鎖李滴，其實(shí)不難理解，內(nèi)核只有一個(gè)蛮瞄，而大內(nèi)核鎖是保護(hù)整個(gè)內(nèi)核的所坯，當(dāng)然有且只有一個(gè)就足夠了。
還需要特別指出的是挂捅，大內(nèi)核鎖是歷史遺留芹助，內(nèi)核中用的非常少，一般保持該鎖的時(shí)間較長(zhǎng)闲先，因此不提倡使用它状土。從2.6.11內(nèi)核起，大內(nèi)核鎖可以通過(guò)配置內(nèi)核使其變得可搶占（自旋鎖是不可搶占的）伺糠，這時(shí)它實(shí)質(zhì)上是一個(gè)互斥鎖蒙谓，使用信號(hào)量實(shí)現(xiàn)。
大內(nèi)核鎖的API包括：
void lock_kernel(void);
該函數(shù)用于得到大內(nèi)核鎖训桶。它可以遞歸調(diào)用而不會(huì)導(dǎo)致死鎖累驮。
void unlock_kernel(void);
該函數(shù)用于釋放大內(nèi)核鎖酣倾。當(dāng)然必須與lock_kernel配對(duì)使用，調(diào)用了多少次lock_kernel谤专，就需要調(diào)用多少次unlock_kernel躁锡。
大內(nèi)核鎖的API使用非常簡(jiǎn)單，按照以下方式使用就可以了：
lock_kernel();
//對(duì)被保護(hù)的共享資源的訪問(wèn)
…
unlock_kernel()置侍；
