淺談Linux內(nèi)核的同步機(jī)制

在現(xiàn)代操作系統(tǒng)里，同一時間可能有多個內(nèi)核執(zhí)行流在執(zhí)行，因此內(nèi)核其實(shí)像多進(jìn)程多線程編程一樣也需要一些同步機(jī)制來同步各執(zhí)行單元對共享數(shù)據(jù)的訪問，尤其是在多處理器系統(tǒng)上，更需要一些同步機(jī)制來同步不同處理器上的執(zhí)行單元對共享的數(shù)據(jù)的訪問。

在主流的Linux內(nèi)核中包含了如下這些同步機(jī)制包括：

原子操作

信號量(semaphore)

讀寫信號量(rw_semaphore)

Spinlock

Mutex

BKL(Big Kernel Lock，只包含在2.4內(nèi)核中，不講)

Rwlock

brlock(只包含在2.4內(nèi)核中，不講)

RCU(只包含在2.6內(nèi)核及以后的版本中)

seqlock(只包含在2.6內(nèi)核及以后的版本中)

本文章分為兩部分，這一章我們主要討論原子操作，自旋鎖，信號量和互斥鎖。

一、原子操作

原子操作的概念來源于物理概念中的原子定義，指執(zhí)行結(jié)束前不可分割(即不可打斷)的操作，是最小的執(zhí)行單位。

原子操作與硬件架構(gòu)強(qiáng)相關(guān)，其API具體的定義均位于對應(yīng)arch目錄下的include/asm/atomic.h文件中，通過匯編語言實(shí)現(xiàn)，內(nèi)核源碼根目錄下的include/asm-generic/atomic.h則抽象封裝了API，該API最后分派的實(shí)現(xiàn)來自于arch目錄下對應(yīng)的代碼。

Structure Definition

typedefstruct{intcounter;}atomic_t;

原子操作主要用于實(shí)現(xiàn)資源計數(shù)， 許多引用計數(shù)(refcnt)就是通過原子操作實(shí)現(xiàn)，例如TCP/IP協(xié)議棧的IP碎片中，struct ipq中的refcnt字段，類型即為atomic_t。

atomic_add

原子操作的實(shí)現(xiàn)比較簡單，以下為例。

原子操作的原子性依賴于ldrex與strex實(shí)現(xiàn)，ldrex讀取數(shù)據(jù)時會進(jìn)行獨(dú)占標(biāo)記，防止其他內(nèi)核路徑訪問，直至調(diào)用strex完成寫入后清除標(biāo)記。自然strex也不能寫入被別的內(nèi)核路徑獨(dú)占的內(nèi)存，若是寫入失敗則循環(huán)至成功寫入。

API

原子操作的API包括如下, 以arm平臺為例：

二 、自旋鎖(spinlock)

自旋鎖是這樣一種同步機(jī)制：若自旋鎖已被別的執(zhí)行者保持，調(diào)用者就會原地循環(huán)等待并檢查該鎖的持有者是否已經(jīng)釋放鎖(即進(jìn)入自旋狀態(tài))，若釋放則調(diào)用者開始持有該鎖。自旋鎖持有期間不可被搶占。

Structure Definition

從定義出發(fā)， spinlock根本的實(shí)現(xiàn)依賴于具體架構(gòu)實(shí)現(xiàn)中slock這個變量，由于spin_lock是大多l(xiāng)ocking機(jī)制的基礎(chǔ)，我們看一看它的實(shí)現(xiàn)。

Lock & Unlock

核心unlock函數(shù)，使owner自增，保持?jǐn)?shù)據(jù)同步。

核心lock函數(shù)，使slock +2^16, 當(dāng)next==owner時，釋放鎖，否則進(jìn)入循環(huán)等待。Prefetchw用于cache預(yù)加載數(shù)據(jù)。

由于slock與tickets共享同一塊內(nèi)存(union)，slock 占32位4字節(jié)，tickets內(nèi)部變量next與owner各16位2字節(jié)。以大端序?yàn)槔?，slock 高2字節(jié)與next共享，低2字節(jié)與owner共享，因此arch_spin_lock實(shí)際上是將tickets.next+1。假設(shè)初始時next與owner皆為0，此時next與owner不等，通過wfe指令進(jìn)入一小段時間等待狀態(tài)，而后讀取新的owner值檢查與next是否相等，不等則繼續(xù)等待，相等則結(jié)束等待。

而owner的值由arch_spin_unlock控制，即unlock控制何時結(jié)束等待。

Spin_lock basic API

Spin_lock API & irq

性能上，spin_lock > spin_lock_bh > spin_lock_irq > spin_lock_irqsave。

安全上，spin_lock_irqsave > spin_lock_irq > spin_lock_bh >spin_lock。

Spin_lock 不同版本的使用

spin_lock用于阻止在不同CPU上的執(zhí)行單元對共享資源的同時訪問以及不同進(jìn)程上下文互相搶占導(dǎo)致的對共享資源的非同步訪問，而中斷失效(spin_lock_irq)和軟中斷失效(spin_lock_bh)卻是為了阻止在同一CPU上軟中斷或中斷對共享資源的非同步訪問。

如果被保護(hù)的共享資源只在進(jìn)程上下文訪問和軟中斷上下文訪問，那么當(dāng)在進(jìn)程上下文訪問共享資源時，可能被軟中斷打斷，從而可能進(jìn)入軟中斷上下文來對被保護(hù)的共享資源訪問，因此對于這種情況，對共享資源的訪問最好使用spin_lock_bh和spin_unlock_bh來保護(hù)。

如果被保護(hù)的共享資源只在進(jìn)程上下文和tasklet或timer上下文訪問，那么應(yīng)該使用與上面情況相同，因?yàn)閠asklet和timer是用軟中斷實(shí)現(xiàn)的。

如果被保護(hù)的共享資源只在兩個或多個tasklet或timer上下文訪問，那么對共享資源的訪問僅需要用spin_lock和spin_unlock來保護(hù)，不必使用_bh版本，因?yàn)楫?dāng)tasklet或timer運(yùn)行時，不可能有其他tasklet或timer在當(dāng)前CPU上運(yùn)行。 如果被保護(hù)的共享資源只在一個軟中斷(tasklet和timer除外)上下文訪問，那么這個共享資源需要用spin_lock和spin_unlock來保護(hù)，因?yàn)橥瑯拥能浿袛嗫梢酝瑫r在不同的CPU上運(yùn)行。

如果被保護(hù)的共享資源在軟中斷(包括tasklet和timer)或進(jìn)程上下文和硬中斷上下文訪問，那么在軟中斷或進(jìn)程上下文訪問期間，可能被硬中斷打斷，從而進(jìn)入硬中斷上下文對共享資源進(jìn)行訪問，因此，在進(jìn)程或軟中斷上下文需要使用spin_lock_irq和spin_unlock_irq來保護(hù)對共享資源的訪問。

在使用spin_lock_irq和spin_unlock_irq的情況下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代，那具體應(yīng)該使用哪一個也需要依情況而定，如果可以確信在對共享資源訪問前中斷是使能的，那么使用spin_lock_irq更好一些，因?yàn)樗萻pin_lock_irqsave要快一些。

三、信號量(Semaphore)

Linux內(nèi)核的信號量在概念和原理上與用戶態(tài)的System V的IPC機(jī)制信號量是一樣的，但是它不可能在內(nèi)核之外使用，因此它與System V的IPC機(jī)制信號量完全不同。

信號量是這樣一種同步機(jī)制：信號量在創(chuàng)建時設(shè)置一個初始值count，用于表示當(dāng)前可用的資源數(shù)。一個任務(wù)要想訪問共享資源，首先必須得到信號量，獲取信號量的操作為count-1，若當(dāng)前count為負(fù)數(shù)，表明無法獲得信號量，該任務(wù)必須掛起在該信號量的等待隊列等待;若當(dāng)前count為非負(fù)數(shù)，表示可獲得信號量，因而可立刻訪問被該信號量保護(hù)的共享資源。當(dāng)任務(wù)訪問完被信號量保護(hù)的共享資源后，必須釋放信號量，釋放信號量通過把count+1實(shí)現(xiàn)，如果count為非正數(shù)，表明有任務(wù)等待，它也喚醒所有等待該信號量的任務(wù)。

Structure Definition

可以發(fā)現(xiàn)，信號量是基于spinlock實(shí)現(xiàn)的，對其封裝以滿足高級的功能，例如全局共享資源的配置，并通過等待隊列較為靈活的調(diào)度。信號量與接下來要講的mutex都建立在自旋鎖實(shí)現(xiàn)的執(zhí)行同步上。

了解了信號量的結(jié)構(gòu)與定義，我們來看看最核心的兩個實(shí)現(xiàn)down ，up。

down & up

down用于調(diào)用者獲得信號量，若count大于0，說明資源可用，將其減一即可。

若count<0,將task加入等待隊列，并進(jìn)入等待隊列，并進(jìn)入調(diào)度循環(huán)等待，直至其被__up喚醒，或者因超時以被移除等待隊列。

up用于調(diào)用者釋放信號量，若waitlist為空，說明無等待任務(wù)，count+1，該信號量可用。

若waitlist非空，將task從等待隊列移除，并喚醒該task,對應(yīng)__down條件。

Semaphore API

四、互斥鎖(Mutex)

Linux 內(nèi)核互斥鎖是非常常用的同步機(jī)制，互斥鎖是這樣一種同步機(jī)制：在互斥鎖中同時只能有一個任務(wù)可以訪問該鎖保護(hù)的共享資源，且釋放鎖和獲得鎖的調(diào)用方必須一致。因此在互斥鎖中，除了對鎖本身進(jìn)行同步，對調(diào)用方(或稱持有者)必須也進(jìn)行同步。當(dāng)互斥鎖無法獲得時，task會加入等待隊列，直至可獲得鎖為止。

Structure Definition

互斥鎖從結(jié)構(gòu)上看與信號量十分類似，但將原本的int類型的count計數(shù)，改成了atomic_long_t的owner以便同步，保證釋放者與持有者一致。

mutex_lock & mutex_unlock

上圖簡單的表現(xiàn)了mutex_lock與mutex_unlock實(shí)現(xiàn)的對稱性，___mutex_trylock_fast用于owner為0的特殊狀態(tài)，用于快速加鎖，實(shí)現(xiàn)核心在slowpath版本上。

*might_sleep指在之后的代碼執(zhí)行中可能會sleep。

由于mutex實(shí)現(xiàn)的具體步驟相當(dāng)復(fù)雜，這里選講比較核心簡單的兩塊。Mutex有關(guān)等待隊列的處理比較復(fù)雜，有興趣閱讀相關(guān)內(nèi)核書籍。

當(dāng)且僅當(dāng)lock當(dāng)前的owner沒有變化時(沒有其他mutex搶先擁有該鎖)，此時獲得鎖，返回NULL, owner 為 curr | flags,owner本身對應(yīng)task指針。若該鎖已被占用，owner和當(dāng)前task不匹配，返回owner對應(yīng)指針。

當(dāng)unlock時，不考慮等待隊列的影響，則與上述類似，當(dāng)且僅當(dāng)之前持有鎖的owner可以解鎖，解鎖時本來應(yīng)將lock的owner置為初始0，但是這里保留了mutex的flag以便后續(xù)操作。

*這里的owner實(shí)際上是task_struct的指針，也就是地址，由于task_struct的地址是L1_cache對齊的，因此實(shí)際上指針地址后三位為0，因此linux內(nèi)核利用這三個比特位用于設(shè)置mutex的標(biāo)志位，不影響指針地址的表示也更高效利用了冗余的比特位。

Mutex 的改進(jìn)

最初的互斥鎖僅支持睡眠等待，然而經(jīng)過漫長時間的改進(jìn)，如今的互斥鎖已經(jīng)可以支持自旋等待，通過MCS鎖機(jī)制實(shí)現(xiàn)。在內(nèi)核中可以選擇配置以支持，CONFIG_MUTEX_SPIN_ON_OWNER。

如上是4.9內(nèi)核中mutex中常用有效的字段，目前最常用的算法是OSQ算法。自旋等待機(jī)制的核心原理是當(dāng)發(fā)現(xiàn)持有者正在臨界區(qū)執(zhí)行并且沒有其他優(yōu)先級高的進(jìn)程要被調(diào)度(need_resched)時，那么mutex當(dāng)前所在進(jìn)程認(rèn)為該持有者很快會離開臨界區(qū)并釋放鎖，此時mutex選擇自旋等待，短時間的自旋等待顯然比睡眠-喚醒開銷小一些。

在實(shí)現(xiàn)上MCS保證了同一時間只有一個進(jìn)程自旋等待持有者釋放鎖。MCS 的實(shí)現(xiàn)較為復(fù)雜，具體可參考一些內(nèi)核書籍。MCS保證了不會存在多個cpu爭用鎖的情況，從而避免了多個CPU的cacheline顛簸從而降低系統(tǒng)性能的問題。

經(jīng)過改進(jìn)后，mutex的性能有了相當(dāng)大的提高，相對信號量的實(shí)現(xiàn)要高效得多。因此我們盡量選用mutex。

Mutex 的使用條件

Mutex雖然高效，靈活，但存在若干限制條件，需要牢記:

同一時刻只有一條內(nèi)核路徑可以持有鎖

只有鎖持有者可以解鎖

不允許遞歸加鎖解鎖

進(jìn)程持有mutex時不可退出

Mutex 可能導(dǎo)致睡眠阻塞，不可用于中斷處理與下半部使用

Mutex API