Linux kernel同步機(jī)制及原子操作，自旋鎖，信號(hào)量和互斥鎖

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

原子操作

信號(hào)量（semaphore）

讀寫(xiě)信號(hào)量（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)核及以后的版本中）

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

一、原子操作

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

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

Structure Definition

typedefstruct{intcounter;}atomic_t;

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

atomic_add

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

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

API

原子操作的API包括如下, 以arm平臺(tái)為例：

二 、自旋鎖（spinlock)

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

Structure Definition

從定義出發(fā)， spinlock根本的實(shí)現(xiàn)依賴于具體架構(gòu)實(shí)現(xiàn)中slock這個(gè)變量，由于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時(shí)，釋放鎖，否則進(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è)初始時(shí)next與owner皆為0，此時(shí)next與owner不等，通過(guò)wfe指令進(jìn)入一小段時(shí)間等待狀態(tài)，而后讀取新的owner值檢查與next是否相等，不等則繼續(xù)等待，相等則結(jié)束等待。

而owner的值由arch_spin_unlock控制，即unlock控制何時(shí)結(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í)行單元對(duì)共享資源的同時(shí)訪問(wèn)以及不同進(jìn)程上下文互相搶占導(dǎo)致的對(duì)共享資源的非同步訪問(wèn)，而中斷失效（spin_lock_irq）和軟中斷失效(spin_lock_bh)卻是為了阻止在同一CPU上軟中斷或中斷對(duì)共享資源的非同步訪問(wèn)。

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

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

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

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

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

三、信號(hào)量（Semaphore）

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

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

Structure Definition

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

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

down & up

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

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

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

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

Semaphore API

四、互斥鎖（Mutex）

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

Structure Definition

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

mutex_lock & mutex_unlock

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

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

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

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

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

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

Mutex 的改進(jìn)

最初的互斥鎖僅支持睡眠等待，然而經(jīng)過(guò)漫長(zhǎng)時(shí)間的改進(jìn)，如今的互斥鎖已經(jīng)可以支持自旋等待，通過(guò)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í)行并且沒(méi)有其他優(yōu)先級(jí)高的進(jìn)程要被調(diào)度（need_resched）時(shí)，那么mutex當(dāng)前所在進(jìn)程認(rèn)為該持有者很快會(huì)離開(kāi)臨界區(qū)并釋放鎖，此時(shí)mutex選擇自旋等待，短時(shí)間的自旋等待顯然比睡眠-喚醒開(kāi)銷小一些。

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

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

Mutex 的使用條件

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

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

只有鎖持有者可以解鎖

不允許遞歸加鎖解鎖

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

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

Mutex API