《深入理解並行編程》筆記

本文是《Is Parallel Programming Hard, And, If So, What Can You Do About It?》的中文翻譯版《深入理解並行編程》的讀書筆記(就是一些摘錄整理,不想按照嚴格的文章進行書寫,所以大佬們各取所需),雖然讀書筆記一般是上傳豆瓣,但是看到知乎上 RCU 內容很少,且自己有時從知乎上獲得一些知識啓發,算是回饋一下社區。由於時間不多,書沒讀完,內容也沒貫通,後續會繼續補更。

原著書作者 Paul E.Mckenney,是 Linux RCU Maintainer,本書很詳細介紹了 linux 內核多核並行編程的乾貨,需要多精讀。

硬件系統

霍金的半導體難題:1. 有限的光速;2. 物質的原子本質。這意味着在摩爾定律受阻,單核 CPU 性能難以提升,多核 CPU 大行其道的時代,多核 CPU 間通信代價高昂,需要注意性能影響。爲了提升性能,硬件做了如下設計:

  1. 由於 CPU 速度遠大於內存系統速度,CPU 硬件中加入了緩存 cache,cache 與內存間數據傳遞是範圍從 16 到 256 字節不等的緩存行 cache-line。緩存缺失原因可能是 startup cache miss(開始數據沒有),capacity miss(容量滿淘汰)以及 communication miss(多個 CPU 間一致性同步使無效)。緩存缺失可能會導致 CPU stall
  2. 由於一個變量可能緩存在多個 CPU 的 cache 中,多個 CPU 的 cache 需要一致性協議 MESI 進行同步。MESI 協議即緩存行中 modified(單 CPU 擁有最新修改的緩存數據),exclusive(單 CPU 獨佔緩存與內存最新數據),shared(數據由多個 CPU 共享),invalid(空數據)四種狀態間進行轉移
  3. CPU 除了 cache,還有存儲緩衝 store buffer。這是爲了提高對於特定緩存行的第一次寫操作的 miss,比如 foo = 1 操作可能因爲 foo 一致性同步而造成 CPU 停頓(等待使無效應答),這樣 CPU 只需將新寫數據保存到 store buffer 就可繼續運行
  4. 由於 store buffer 通常很小,密集讀寫操作會造成大量使無效消息,因此增加使無效隊列 invalidate queue。帶使無效隊列的 CPU 可以迅速應答一個使無效消息,而不必等待相應的行真正變成無效狀態。這意味着在沒有真正將 cache 無效前,就告訴其他 CPU 已經使無效了。這多少有一點欺騙的意思

內存屏障

由於以上硬件設計,CPU 被設計成在從內存中獲取數據的同時可以執行其他指令,這明顯會導致指令和內存引用的亂序執行(執行順序與代碼順序不同),因而編譯器和同步原語有責任通過對內存屏障的使用來保護在並行編程中用戶的直覺。

簡單規則:

  1. 一個特定 CPU 將像 “編程順序” 那樣看到它對內存的訪問操作
  2. 單變量存儲序列一致
  3. 內存屏障將成對操作。不能保證一個 CPU 將看到第二個 CPU 訪問操作的正確順序,即使第二個 CPU 使用一個內存屏障,除非第一個 CPU 也使用一個配對的內存屏障
  4. 互斥鎖原語提供保護。申請,釋放鎖必須以全局順序被看到
  5. 不能保證在內存屏障之前的內存訪問將在內存屏障指令完成時完成
  6. 僅僅在兩個 CPU 之間或者 CPU 與設備之間需要交互時,才需要內存屏障

內存屏障分類:

  1. 寫內存屏障:CPU 可以被視爲按時間順序提交一系列存儲操作,所有在寫屏障之前的存儲操作將發生在所有屏障之後的存儲操作之前。寫屏障僅僅對寫操作進行排序,對加載沒有任何效果。注意寫屏障通常應當與讀或者數據依賴屏障配對使用
  2. 數據依賴屏障:弱的讀屏障。當兩個裝載操作中,第二個依賴於第一個的結果時 (如第一個裝載得到第二個裝載的地址),需要一個數據依賴屏障,以確保第二個裝載的目標將在第一個地址裝載之後被更新。數據依賴屏障僅僅對相互依賴的加載進行排序。它對任何存儲沒有效果,對相互獨立的加載或者重疊加載也沒有效果。注意第一個裝載實際上需要一個數據依賴而不是控制依賴。如果第二個裝載的地址依賴於第一個裝載,但是依賴的是一個條件而不是實際裝載地址本身(if-else 選擇), 那麼它就是一個控制依賴,這需要一個完整的讀屏障
  3. 讀內存屏障:所有在屏障之前的加載操作將在屏障之後的加載操作之前發生。讀屏障僅僅對加載進行排序,它對存儲沒有任何效果。讀內存屏障隱含數據依賴屏障,因此可以替代它。
  4. 通用內存屏障:通用內存屏障保證屏障之前的加載、存儲操作都將在屏障之後的加載、存儲操作之前被系統中的其他組件看到。通用內存屏障同時對加載和存儲操作進行排序。通用內存屏障隱含讀和寫內存屏障,因此也可以替換它們中的任何一個
  5. 鎖原語隱含內存屏障:LOCK 操作確保所有 LOCK 操作後面的內存操作看起來發生在鎖操作之後,LOCK 鎖操作之前的內存操作可能發生在它完成之後。UNLOCK 操作確保在 UNLOCK 操作之前的所有內存操作看起來發生在鎖操作之前,UNLOCK 操作之後的內存操作看起來可能發生在它完成之前。LOCK 後面跟隨 UNLOCK 不能設定爲全內存屏障,因爲 LOCK 之前的操作可能發生在 LOCK 之後,並且 UNLOCK 之後的訪問可能發生在 UNLOCK 之前,因此這兩個訪問可能相互交叉

SMP 屏障對:

一個寫屏障應當總是與數據依賴屏障或者讀屏障配對,雖然通用屏障也是可以的。類似的一個讀屏障或者數據依賴屏障總是應當與至少一個寫屏障配對使用,雖然通用屏障也是可以的。

寫屏障圖解:

數據依賴屏障圖解:

讀內存屏障圖解:

多 CPU 使用同一個鎖的順序:

c++11 內存模型:

RCU

並行編程要注意性能與安全性。可以使用鎖之類的同步原語,簡單可靠,但是多核 CPU 同步造成擴展時性能降低。或者使用內存屏障與原子指令,但是編程複雜,很容易就犯難以察覺的錯誤。過於輕率地使用大鎖或者原子變量,由於 CPU 緩存一致性同步造成可擴展性不夠。這時有種策略就是延遲處理,通用的並行編程延後技術包括排隊、引用計數和 RCU。

引用計數跟蹤一個對象被引用的次數,防止對象過早的被釋放。Linux 內核中 kref:

1 struct kref {
2   atomic_t refcount;
3 };
4
5 void kref_init(struct kref *kref)
6 {
7   atomic_set(&kref->refcount,1);
8 }
9
10 void kref_get(struct kref *kref)
11 {
12   WARN_ON(!atomic_read(&kref->refcount));
13   atomic_inc(&kref->refcount);
14 }
15
16 int kref_put(struct kref *kref,
17 void (*release)(struct kref *kref))
18 {
19   WARN_ON(release == NULL);
20   WARN_ON(release == (void (*)(struct kref *))kfree);
21
22   if ((atomic_read(&kref->refcount) == 1) ||
23     (atomic_dec_and_test(&kref->refcount))) {
24     release(kref);
25     return 1;
26   }
27   return 0;
28 }

Read-copy-update(RCU)是一種同步機制,於 2002 年 10 月引入 Linux 內核。RCU 允許讀操作可以與更新操作併發執行,這一點提升了程序的可擴展性。RCU 定義並使用了高效並且易於擴展的機制,用來發布和讀取對象的新版本,還用於延後舊版本對象的垃圾收集工作。這些機制恰當地在讀端和更新端工作,讓讀端非常快速。在某些場合下(比如非搶佔式內核裏),RCU 讀端的函數完全是零開銷。

  1. RCU 保護的是指針
  2. 發佈 - 訂閱機制:RCU 通過一種發佈 - 訂閱機制達成了併發的數據插入。可以安全的讀取數據,即使數據此時正被修改。linux 中使用 rcu_assign_pointer() 原語來發布新數據,其將指針 p 用內存屏障封裝起來,強制讓編譯器和 CPU 在爲 p 的各字段賦值後再發布。使用 rcu_dereference() 原語依靠各種內存屏障指令和編譯器指令來訂閱指針的值
  3. 等待已有的 RCU 讀者執行完畢:RCU 就是一種等待事物結束的方式。RCU 的最偉大之處在於它可以等待多種不同的事物,而無需顯式地去跟蹤它們中的每一個,也無需去擔心對性能的影響,對擴展性的限制,複雜的死鎖場景,還有內存泄漏帶來的危害等等使用顯式跟蹤手段會出現的問題。被等待的事物稱爲 “RCU 讀端臨界區”。RCU 讀端臨界區從 rcu_read_lock() 原語開始,到對應的 rcu_read_unlock()原語結束。RCU 讀端臨界區可以嵌套,也可以包含一大塊代碼,只要這其中的代碼不會阻塞或者睡眠(先不考慮可睡眠 RCU)。如果你遵守這些約定,就可以使用 RCU 去等待任何代碼的完成。RCU 是一種等待已有的 RCU 讀端臨界區執行完畢(比如使用 synchronize_rcu()原語)的方法,這裏的執行完畢也包括在臨界區裏執行的內存操作,請注意在某個寬限期開始後才啓動的 RCU 讀端臨界區會擴展到該寬限期的結尾處。算法是:改變原數據,比如替換鏈表中的一個元素;等待所有已有的 RCU 讀端臨界區執行完畢,即優雅寬限期(grace peroid)結束;再清理,比如釋放剛纔被替換的元素
  4. 維護最近被更新對象的多個版本:允許在不影響或者延遲其他併發 RCU 讀者的前提下改變數據。這意味着 RCU 保護的是內存不一致的數據結構,即存在多個版本,更新數據時,舊版本數據與新版本數據可能被不同讀者讀到

RCU 使用:

RCU 優點:

  1. RCU 是讀寫鎖的替代者。也許在 Linux 內核中 RCU 最常見的用途就是在讀佔大多數時間的情況下替換讀寫鎖了。RCU 的優點在於性能,讀端不會死鎖,以及良好的實時延遲。當然 RCU 也有一點缺點,比如讀者與更新者併發執行,低優先級 RCU 讀者也可以阻塞正等待優雅週期 (Grace Period) 結束的高優先級線程,優雅週期的延遲可能達到好幾毫秒。RCU 這種免於死鎖的能力來源於 RCU 的讀端原語不阻塞、不自旋,甚至不會向後跳轉,所以 RCU 讀端原語的執行時間是確定的,這使得 RCU 讀端原語不可能組成死鎖循環,也保證實時延遲。RCU 讀端免於死鎖的能力帶來了一個有趣的後果,RCU 讀者可以無條件地升級爲 RCU 更新者,在讀寫鎖中嘗試這種升級則會造成死鎖。RCU 免於死鎖的特性帶來的另一個有趣後果是 RCU 不會受很多優先級反轉問題影響。比如低優先級的 RCU 讀者無法阻止高優先級的 RCU 更新者獲取更新端鎖。類似地,低優先級的更新者也無法阻止高優先級的 RCU 讀者進入 RCU 讀端臨界區。RCU 讀者與更新者併發執行,但讀寫鎖和 RCU 提供了不同的保證。在讀寫鎖中,任何在寫者之後開始的讀者都 “保證” 能看到新值,而在寫者正在自旋時開始的讀者有可能看見新值,也有可能看見舊值,這取決於讀寫鎖實現中的讀者 / 寫者哪一個先獲得鎖。與之相反,在 RCU 中,在更新者完成後纔開始的讀者都 “保證” 能看見新值,在更新者開始後才完成的讀者有可能看見新值,也有可能看見舊值,這取決於具體的時機。
  2. RCU 是一種受限制的引用計數機制:rcu_read_lock() 原語可以看作是獲取對 p 的引用,因爲相應的優雅週期無法在配對的 rcu_read_unlock() 之前結束。這種引用計數機制是受限制的,因爲我們不允許在 RCU 讀端臨界區中阻塞,也不允許將一個任務的 RCU 讀端臨界區傳遞給另一個任務。和讀寫鎖一樣,RCU 的性能優勢主要來源於較短的臨界區
  3. RCU 是一種 bulk 引用計數機制:傳統的引用計數通常與某種或者一組數據結構有聯繫,然而維護一組數據結構的全局引用計數,通常會導致包含引用計數的緩存行來回 “乒乓”,這種緩存行“乒乓” 會嚴重影響系統性能。相反,RCU 的輕量級讀端原語允許讀端極其頻繁地調用,卻只帶來微不足道的性能影響,這使得 RCU 可以作爲一種幾乎沒有性能損失的“批量引用計數機制”
  4. RCU 是窮人版的垃圾回收器:RCU 類似自動決定回收時機的 GC,但是 RCU 與 GC 有幾點不同:程序員必須手動指示何時可以回收指定數據結構,且程序員必須手動標出可以合法持有引用的 RCU 讀端臨界區
  5. RCU 是一種提供存在擔保的方法:與鎖類似,如果任何受 RCU 保護的數據元素在 RCU 讀端臨界區中被訪問,那麼數據元素在 RCU 讀端臨界區持續期間保證存在
  6. RCU 是一種提供類型安全內存的方法:很多無鎖算法並不需要數據元素在被 RCU 讀端臨界區引用時保持完全一致,只要數據元素的類型不變就可以了。換句話說只要數據結構類型不變,無鎖算法可以允許某個數據元素在被其他對象引用時被釋放並重新分配,但是決不允許類型上的改變,這種 “保證” 在學術文獻中被稱爲“類型安全的內存”
  7. RCU 是一種等待事物結束的方式

RCU 實現:

僅討論 userspace rcu,具體論文參考 User-Level Implementations of Read-Copy Update。書中詳細討論了設計演進的過程,漸漸完善 RCU 原語使其符合原來定義。

是一種基於單個全局 free-running 計數器的 RCU 實現,但是允許 RCU 讀端臨界區的嵌套。嵌套通過全局變量 rcu_gp_ctr 實現,RCU_GP_CTR_NEST_MASK 宏則是 rcu_gp_ctr 中所有用於記錄嵌套的位掩碼。

rcu_read_lock() 的實現中,第 6 行指向本線程 rcu_reader_gp 實例的指針放入局部變量 rrgp 中,將代價昂貴的訪問每線程變量函數的數目降到最低。第 8 行檢查低位字節是否爲 0,表明當前的 rcu_read_lock() 是最外層的。如果是,第 9 行將全局變量 rcu_gp_ctr 的值存入 tmp,因爲第 7 行之前存入的值可能已經過期了,如果不是,第 10 行增加嵌套深度。第 11 行將更新後的計數器值重新放入當前線程的 rcu_reader_gp 實例中,最後第 12 行執行一個內存屏障,防止 RCU 讀端臨界區泄漏到 rcu_read_lock() 之前的代碼裏。除非當前調用的 rcu_read_lock() 是嵌套在 RCU 讀端臨界區中,否則本節實現的 rcu_read_lock() 原語會獲取全局變量 rcu_gp_ctr 的一個副本,而在嵌套環境中,rcu_read_lock() 則去獲取 rcu_reader_gp 在當前線程中的實例。在兩種情況下,rcu_read_lock() 都會增加獲取到的值,表明嵌套深度又增加了一層,然後將結果儲存到當前線程的 rcu_reader_gp 實例中。

rcu_read_unlock() 的實現。第 19 行執行一個內存屏障,防止 RCU 讀端臨界區泄漏到 rcu_read_unlock() 之後的代碼中去,然後第 20 行減少當前線程的 rcu_reader_gp 實例,這將減少 rcu_reader_gp 低幾位包含的嵌套深度。

synchronize_rcu()的實現,只需要等待 “在調用 synchronize_rcu() 之前就已存在的”RCU 讀端臨界區。第 24 行執行一個內存屏障,防止之前操縱的受 RCU 保護的數據結構被亂序(由編譯器或者是 CPU)放到第 24 行之後執行。爲了防止多個 synchronize_rcu()實例併發執行,第 25 行獲取 rcu_gp_lock 鎖(第 29 釋放鎖)。然後第 13 行給全局變量 rcu_gp_ctr 異或,使得 synchronize_rcu()之後就存在的 RCU 讀端臨界區的 rcu_reader_gp 位最高端爲 0。然後 16 行掃描所有線程檢查 RCU_GP_CTR_BOTTOM_BIT 指示的位是否爲 0 及是否是之前的 rcu_gp_ctr,爲 0 則表示已經不在臨界區,爲 1 表示是 synchronize_rcu()之前就已存在的 RCU 讀端臨界區。flip_counter_and_wait 執行兩次恢復 rcu_gp_ctr 的最高位爲 1。最後第 30 行的內存屏障保證所有後續的銷燬工作不會被亂序到循環之前進行.

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://zhuanlan.zhihu.com/p/56873613