之前的文章

Linux kernel同步機(jī)制

在上一部分，我們討論了最基本常見的幾類同步機(jī)制，這一部分我們將討論相對復(fù)雜的幾種同步機(jī)制，尤其是讀寫信號量和RCU，在操作系統(tǒng)內(nèi)核中有相當(dāng)廣泛的應(yīng)用。

• 讀寫信號量（rw_semaphore）

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

• Rwlock

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

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

一、讀寫信號量（RW_Semaphore）

讀寫信號量與信號量有相似也有不同，它是如下一種同步機(jī)制：讀寫信號量將訪問者分為讀者或者寫者，讀者在持有讀寫信號量期間只能對該信號量保護(hù)的共享資源進(jìn)行讀訪問，而只要一個(gè)任務(wù)需要寫，它就被歸類為寫者，其進(jìn)行訪問之前必先獲得寫者身份，在其不需寫訪問時(shí)可降級為讀者。讀寫信號量可同時(shí)擁有不受限的讀者數(shù)，寫者是排他性的，獨(dú)占性的，而讀者不排他。若讀寫信號量未被寫者持有或者等待，讀者就可以獲得讀寫信號量，否則必須等待直到寫者釋放讀寫信號量為止；若讀寫信號量沒有被讀者或?qū)懻叱钟?#xff0c;也沒用寫者等待，寫者可以獲得該讀寫信號量，否則等待至信號量全部釋放（沒有其他訪問者）為止。

Structure Definition

若從上述結(jié)構(gòu)定義看，最關(guān)鍵的前三個(gè)字段與mutex、信號量十分相似不再贅述，后面的OSQ字段在Mutex中提起過。由于內(nèi)核有關(guān)讀寫信號量的實(shí)現(xiàn)有兩種，取決于CONFIG_RWSEM_GENERIC_SPINLOCK的配置，但是一般默認(rèn)該配置是關(guān)的，因此選用默認(rèn)版本的實(shí)現(xiàn)進(jìn)行解讀。讀寫信號量同mutex一樣，在最近的改進(jìn)中均引入了OSQ lock機(jī)制實(shí)現(xiàn)自旋等待。

讀寫信號量與信號量之間的關(guān)系

讀寫信號量可能會(huì)引起進(jìn)程阻塞,但是它允許N個(gè)讀執(zhí)行單元同時(shí)訪問共享資源,而最多只允許有一個(gè)寫執(zhí)行單元訪問共享資源;因此,讀寫信號量是一種相對放寬條件的、粒度稍大于信號量的互斥機(jī)制。信號量不允許任何操作之間有并發(fā),即:讀操作與讀操作之間、讀操作與寫操作之間、寫操作與寫操作之間,都不允許并發(fā);而讀寫信號量則只允許讀操作與讀操作之間的并發(fā),但不允許讀操作與寫操作之間的并發(fā),也不允許寫操作與寫操作之間的并發(fā)。因此讀寫信號量比較適合讀多寫少的情況，可良好地利用讀者并發(fā)的特性。

Count 字段在讀寫信號量的表示含義

讀寫信號量中的count字段并不如信號量一般表示可用資源數(shù)量，而是標(biāo)記了當(dāng)前的訪問情況，我們?nèi)?2位的情況分析，默認(rèn)是取32位配置。

先觀察如下宏常量：

然后我們再考慮count，我們發(fā)現(xiàn)均是上述宏組合的結(jié)果，可以歸類為以下幾種情況：

所以可見count可以標(biāo)記并區(qū)分許多訪問情況， 尤其是當(dāng)存在寫者或阻塞時(shí)，其對應(yīng)的有符號數(shù)(atomic_long_t)均為負(fù)數(shù)，可以作為判斷的標(biāo)記。

在傳統(tǒng)的讀寫信號量中，會(huì)直接進(jìn)阻塞，因此只有等待隊(duì)列非空還是為空的問題，但是在最近的改進(jìn)中存在自旋等待的問題，因此使得在鎖的獲取中可能出現(xiàn)自旋狀態(tài)的寫者偷出鎖的情況。

__down_read & __up_read

根據(jù)count字段的含義，count + 1小于0說明原本存在寫者或者等待隊(duì)列非空，因此不能獲得鎖，rwsem_down_read_failed調(diào)用

一個(gè)讀者釋放后count - 1小于-1說明等待隊(duì)列非空，因此還需喚醒等待的寫者

Rwsem_down_read不能直接獲取時(shí)調(diào)用，首先判斷等待隊(duì)列是否為空，為空則字段置為非空，并將count回退之前讀的嘗試，將當(dāng)前task壓入等待隊(duì)列，如果當(dāng)前沒有人持有或正在獲取鎖鎖,則喚醒等待隊(duì)列的前面的進(jìn)程，同時(shí)將喚醒進(jìn)程的waiter.task置NULL，在調(diào)度中若發(fā)現(xiàn)自己的waiter.task為NULL，說明輪到本進(jìn)程運(yùn)行，置為TASK_RUNNING

down_write & up_write

一個(gè)寫者獲取鎖后，如果返回的count不是0xffff0001，那么寫者獲取信號量失敗

Rwsem_down_write_failed的基本邏輯與read相似，回退先前count的變化，對waitlist的處理，等待獲取鎖，有興趣可以自己閱讀源碼。

一個(gè)寫者釋放鎖后，如果count返回小于0，說明等待非空，將其喚醒。

RW_Semaphore ?API

二、讀寫鎖（rw_lock）

讀寫鎖實(shí)際是一種特殊的自旋鎖，它把對共享資源的訪問者劃分成讀者和寫者，讀者只對共享資源進(jìn)行讀訪問，寫者則需要對共享資源進(jìn)行寫操作。這種鎖相對于自旋鎖而言，能提高并發(fā)性，因?yàn)樵诙嗵幚砥飨到y(tǒng)中，它允許同時(shí)有多個(gè)讀者來訪問共享資源，最大可能的讀者數(shù)為實(shí)際的邏輯CPU數(shù)。寫者是排他性的，一個(gè)讀寫鎖同時(shí)只能有一個(gè)寫者或多個(gè)讀者（與CPU數(shù)相關(guān)），但不能同時(shí)既有讀者又有寫者。

在讀寫鎖保持期間也是搶占失效的。如果讀寫鎖當(dāng)前沒有讀者，也沒有寫者，那么寫者可以立刻獲得讀寫鎖，否則它必須自旋在那里，直到?jīng)]有任何寫者或讀者。如果讀寫鎖沒有寫者，那么讀者可以立即獲得該讀寫鎖，否則讀者必須自旋在那里，直到寫者釋放該讀寫鎖。

Structure Definition

從結(jié)構(gòu)上看，讀寫鎖與自旋鎖基本相似，實(shí)際上二者的實(shí)現(xiàn)也十分相似，二者的關(guān)系可以類比讀寫信號量與信號量的關(guān)系。

arch_read_lock & arch_read_unlock

Read_lock實(shí)現(xiàn)上判斷l(xiāng)ock+1是否為負(fù)，為負(fù)說明有寫者持有鎖（0x80000000)，此時(shí)調(diào)用wfe進(jìn)入一小段自旋狀態(tài)后再度執(zhí)行；若非負(fù)，則將lock+1更新至lock中。

對應(yīng)read_lock，read_unlock僅僅需要將lock -1 更新至lock。

arch_write_lock & arch_write_unlock

write_lock 在嘗試獲得鎖時(shí)，檢查lock是否為0，不為0則說明有讀者或者寫者持有鎖，此時(shí)wfe進(jìn)入一小段等待直到lock為0，若lock為0則賦值lock獲得鎖。

Write_unlock只需將lock置零即可。

從這里可以看出，讀寫鎖的實(shí)現(xiàn)上以及功能上，相當(dāng)于針對自旋鎖對于讀多寫少的場景提高并發(fā)度，設(shè)計(jì)原理與讀寫信號量十分類似。

RW_Lock API

三、順序鎖（seqlock）

順序鎖是對讀寫鎖的一種優(yōu)化:讀者絕不會(huì)被寫者阻塞，也就說，讀者可以在寫者對被順序鎖保護(hù)的共享資源進(jìn)行寫操作時(shí)仍然可以繼續(xù)讀，不必等待寫者完成寫操作，寫者也不需要等待所有讀者完成讀操作才去進(jìn)行寫操作。但是，寫者與寫者之間仍然是互斥的。寫操作的優(yōu)先級大于讀操作。

順序鎖有一個(gè)限制，它必須要求被保護(hù)的共享資源不含有指針，因?yàn)閷懻呖赡苁沟弥羔樖?#xff0c;但讀者如果正要訪問該指針，將導(dǎo)致OOPs。如果讀者在讀操作期間，寫者已經(jīng)發(fā)生了寫操作，那么，讀者必須重新讀取數(shù)據(jù)，以便確保得到的數(shù)據(jù)是完整的。順序鎖適用于讀多寫少的情況。

這種鎖對于讀寫同時(shí)進(jìn)行的概率比較小的情況，性能是非常好的，而且它允許讀寫同時(shí)進(jìn)行，更大地提高了并發(fā)性。順序鎖的一個(gè)典型的應(yīng)用在于時(shí)鐘系統(tǒng)。

Structure Definition

從結(jié)構(gòu)上看，也是依賴于自旋鎖的，seqcount用于同步寫者訪問的順序以更新讀者訪問,自旋鎖的作用在于實(shí)現(xiàn)寫操作之間的互斥，讀者訪問不受限制。

write_seqlock & write_sequnlock

順序鎖對寫操作之間必須互斥，實(shí)現(xiàn)上調(diào)用spin_lock進(jìn)行互斥，另外對seqcount操作以同步讀者的訪問。

seqcount的計(jì)數(shù)符合以下規(guī)則：進(jìn)入臨界區(qū)時(shí)加一，離開臨界區(qū)時(shí)也加一

read_seqretry & read_seqbegin

read_seqcount_begin返回當(dāng)前seqlock的seqcount, 在讀完后，需調(diào)用read_seqretry查看讀者讀完后的seqcount是否與讀之前一致，一致則結(jié)束，不一致則說明有寫操作正在或已經(jīng)執(zhí)行，需要重新讀一次以更新數(shù)據(jù)。另外read_seqbegin返回的是lock.seqcount/2,實(shí)際上是寫操作發(fā)生的次數(shù)。

seqlock API

其他_irqsave,_irq,_bh版本均是與其他鎖類似的。

四、RCU（Read-Copy Update）

RCU是讀寫鎖的高性能版本，既允許多個(gè)讀者同時(shí)訪問被保護(hù)的數(shù)據(jù)，又允許多個(gè)讀者和多個(gè)寫者同時(shí)訪問被保護(hù)的數(shù)據(jù)（注意：是否可以有多個(gè)寫者并行訪問取決于寫者之間使用的同步機(jī)制），讀者沒有任何同步開銷，而寫者的同步開銷則取決于使用的寫者間同步機(jī)制。

對于被RCU保護(hù)的共享數(shù)據(jù)結(jié)構(gòu)，讀者不需要獲得任何鎖就可以訪問它，但寫者在訪問它時(shí)首先拷貝一個(gè)副本，然后對副本進(jìn)行修改，最后使用一個(gè)回調(diào)（callback）機(jī)制在適當(dāng)?shù)臅r(shí)機(jī)(所有引用該數(shù)據(jù)的CPU都退出對共享數(shù)據(jù)的操作時(shí))把指向原來數(shù)據(jù)的指針重新指向新的被修改的數(shù)據(jù)。有一個(gè)專門的垃圾收集器探測讀者的信號，一旦所有讀者都已發(fā)送信號告知它們不在使用被RCU保護(hù)的數(shù)據(jù)結(jié)構(gòu)，垃圾收集器就調(diào)用回調(diào)函數(shù)完成最后的數(shù)據(jù)釋放或修改操作。

RCU不能替代讀寫鎖，當(dāng)寫比較多時(shí)，對讀者的性能提高不能彌補(bǔ)寫者導(dǎo)致的損失，但是大多數(shù)情況下RCU的表現(xiàn)高于讀寫鎖。

RCU Basic API

RCU 臨界區(qū)管理

之前的同步機(jī)制中，均是利用鎖或原子操作實(shí)現(xiàn)的，一個(gè)鎖管理一個(gè)臨界區(qū)，并通過加鎖解鎖控制進(jìn)程進(jìn)入或者離開臨界區(qū)。一個(gè)程序中可以存在若干的臨界區(qū)，因此可以對應(yīng)存在若干把鎖分別管理，這是之前所有鎖機(jī)制的基礎(chǔ)。

然而RCU并不基于鎖機(jī)制實(shí)現(xiàn)，RCU字段是耦合在進(jìn)程描述符和CPU變量中的，是一種與系統(tǒng)強(qiáng)耦合的同步機(jī)制，RCU負(fù)責(zé)管理進(jìn)程內(nèi)所有的臨界區(qū)，進(jìn)程通過調(diào)用rcu_read_lock與rcu_read_unlock標(biāo)記讀者臨界區(qū)，通過rcu_assign_pointer、list_add_rcu將數(shù)據(jù)納入保護(hù)區(qū)，當(dāng)寫者copy出新數(shù)據(jù)時(shí)在讀者全部退出臨界區(qū)后，將新數(shù)據(jù)指針更新，舊數(shù)據(jù)將在垃圾收集器的檢查中被釋放，但存在延遲。

RCU 限制條件

• RCU只保護(hù)動(dòng)態(tài)分配并通過指針引用的數(shù)據(jù)結(jié)構(gòu)

• 在被RCU保護(hù)的臨界區(qū)中，任何內(nèi)核路徑都不能睡眠（經(jīng)典實(shí)現(xiàn)中）

RCU callback的實(shí)現(xiàn)

rcu_head 是RCU回調(diào)函數(shù)的關(guān)鍵結(jié)構(gòu)。此外，回調(diào)機(jī)制主要涉及兩個(gè)基本函數(shù)__call_rcu(用于注冊), __rcu_reclaim（用于調(diào)用）。

__call_rcu僅僅將func注冊進(jìn)rcu_head, 便立刻返回。該func一般用于回收釋放copy后遺留的舊數(shù)據(jù)垃圾，但是RCU采用了延時(shí)執(zhí)行防止讀者還在讀舊數(shù)據(jù)時(shí)回收數(shù)據(jù)造成崩潰。

Rcp主要用于全局控制，而rcu的回調(diào)函數(shù)以鏈?zhǔn)浇M織，next用于遍歷鏈。

__rcu_reclaim用于回收rcu先前分配的舊數(shù)據(jù)，回調(diào)函數(shù)也是回收操作的一種。

實(shí)際上，synchronize_rcu在等待讀者全數(shù)退出臨界區(qū)時(shí)，也通過call_rcu注冊了回調(diào)函數(shù)。

相對麻煩的是回收階段，RCU通過一個(gè)垃圾收集器檢查需要回收的舊數(shù)據(jù)并調(diào)用回調(diào)函數(shù)釋放，準(zhǔn)確的說調(diào)用rcu_check_callbacks檢查是否有需要執(zhí)行的回調(diào)函數(shù)，而后調(diào)用rcu_process_callbacks執(zhí)行必要的rcu 回調(diào)函數(shù)。

那么問題來了，誰去調(diào)用rcu_check_callbacks函數(shù)呢？時(shí)鐘系統(tǒng)，每當(dāng)時(shí)間片消耗完或者出現(xiàn)時(shí)鐘中斷，時(shí)鐘系統(tǒng)都將調(diào)用rcu_check_callbacks進(jìn)行及時(shí)檢查處理，避免過量的舊數(shù)據(jù)垃圾造成內(nèi)存浪費(fèi)。

RCU read

rcu_read_lock與rcu_read_unlock的經(jīng)典實(shí)現(xiàn)是不可搶占的，從代碼看，這兩個(gè)函數(shù)僅僅用于開關(guān)搶占。

RCU read之所以禁止搶占，主要是由于寫者必須等待讀者完全執(zhí)行完退出臨界區(qū)方能修改數(shù)據(jù)指針。一旦讀者被搶占，那么其退出臨界區(qū)的過程將會(huì)阻塞，進(jìn)而阻塞寫者，這對性能是一種不小的開銷。但是現(xiàn)在的linux 內(nèi)核版本中提供了可搶占的版本，只是對搶占深度做了把控。

RCU Synchronize

可是RCU是如何獲知所有讀者已經(jīng)離開臨界區(qū)？RCU read實(shí)現(xiàn)中并沒有設(shè)置字段標(biāo)記進(jìn)出臨界區(qū)，RCU是通過什么判斷的呢？既然RCU read過程不可搶占，那么換言之，若所有 CPU 都已經(jīng)過一次上下文切換，則所有前置 reader 的臨界區(qū)必定全部退出。

我們主要分析以下兩種：

• rcu_check_callbacks

• synchronize_rcu

user其實(shí)在調(diào)用中真實(shí)的傳入是user_tick,值為1指用戶時(shí)間，0指系統(tǒng)時(shí)間，由于RCU必須在內(nèi)核態(tài)執(zhí)行，因此user為1說明必然不處于lock~unlock的時(shí)段，很有可能已經(jīng)發(fā)生過rcu_read,因此發(fā)送一個(gè)RCU_SOFTIRQ軟中斷，調(diào)用rcu_process_callbacks。

synchronize_rcu的核心是wait_rcu_gp函數(shù)。

該函數(shù)通過注冊一個(gè)func為wakeme_after_rcu的rcu_head并等待該rcu_head完成回調(diào)來判斷之前的rcu讀者已經(jīng)全部退出。

由于該rcu_head注冊較晚，當(dāng)且僅當(dāng)當(dāng)前的讀者都已退出臨界區(qū)，該rcu_head的回調(diào)才可能執(zhí)行，因此當(dāng)該func回調(diào)完成，就必然已經(jīng)滿足同步條件。最后銷毀該多余的head內(nèi)存。

如下圖：

RCU Example

Input.c 中的使用為例。

Grab_device即掛載設(shè)備，注意這里的rcu_assign_pointer用于將dev->grab加入rcu保護(hù)的共享區(qū)，handle（處理函數(shù)）是其值。在這里完成了向rcu注冊數(shù)據(jù)的過程。

Input_pass_value處理所有的輸入事件，首先我們r(jià)ead_lock標(biāo)記進(jìn)入臨界區(qū)不可搶占，讀出dev->grab并以處理輸入事件，最后read_unlock退出臨界區(qū)。

Release device與掛載相對，釋放過程即將原本的handler變?yōu)镹ULL, 最后調(diào)用synchronize_rcu通知所有輸入事件handler移除

五、同步機(jī)制之間的比較

? ? 推薦閱讀：

? ??專輯|Linux文章匯總

? ??專輯|程序人生

? ??專輯|C語言

嵌入式Linux

微信掃描二維碼，關(guān)注我的公眾號?

總結(jié)

以上是生活随笔為你收集整理的Linux kernel 同步机制（下篇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。