Linux kernel 同步機制（下篇）

之前的文章

Linux kernel同步機制

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

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

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

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

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

先觀察如下宏常量：

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

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

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

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

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

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

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

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

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

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

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

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

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

對應read_lock，read_unlock僅僅需要將lock -1 更新至lock。

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

Write_unlock只需將lock置零即可。

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

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

順序鎖有一個限制，它必須要求被保護的共享資源不含有指針，因為寫者可能使得指針失效，但讀者如果正要訪問該指針，將導致OOPs。如果讀者在讀操作期間，寫者已經(jīng)發(fā)生了寫操作，那么，讀者必須重新讀取數(shù)據(jù)，以便確保得到的數(shù)據(jù)是完整的。順序鎖適用于讀多寫少的情況。

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

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

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

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

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

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

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

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

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

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

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

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

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

Rcp主要用于全局控制，而rcu的回調(diào)函數(shù)以鏈式組織，next用于遍歷鏈。

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

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

相對麻煩的是回收階段，RCU通過一個垃圾收集器檢查需要回收的舊數(shù)據(jù)并調(diào)用回調(diào)函數(shù)釋放，準確的說調(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ù)呢？時鐘系統(tǒng)，每當時間片消耗完或者出現(xiàn)時鐘中斷，時鐘系統(tǒng)都將調(diào)用rcu_check_callbacks進行及時檢查處理，避免過量的舊數(shù)據(jù)垃圾造成內(nèi)存浪費。

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

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

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

我們主要分析以下兩種：

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

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

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

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

如下圖：

Input.c 中的使用為例。

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

Input_pass_value處理所有的輸入事件，首先我們read_lock標記進入臨界區(qū)不可搶占，讀出dev->grab并以處理輸入事件，最后read_unlock退出臨界區(qū)。

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