本書以霍金提出的兩個理論物理限制為引子，解釋了多核并行計算興起的原因。并從硬件的角度闡述并行編程的難題。然后，本書以常見的計數器為例，探討其不同的實現方法及適用場景。在這些實現方法中，除了介紹常見的鎖以外，本書還重點介紹了RCU的使用及其原理，以及實現RCU的基礎：內存屏障。最后，本書還介紹了并行軟件的驗證，以及并行實時計算等內容。
譯者序1
希望這本著作能夠成為經典！
20年前，當我正式成為一名軟件工程師的時候，就有一個夢想：開發一款操作系統。那時候，雖然知道Linux的存在，但是實在找不到一臺可以正常安裝使用Linux的PC。因此只能閱讀相關的源碼分析書籍而不能動手實踐。
我至今仍然清楚記得：大約10年前，中興通訊操作系統團隊的鐘衛東部長，可能被我對操作系統的熱情所感動，不顧我沒有上過大學的事實，冒著風險將我招聘到中興通訊成都研究所。面對100多種型號的單板，我既興奮又惶恐。這些單板涉及ARM、X86、PowerPC、MIPS、SH、Sparc等不同的CPU架構。從此，我開始了激動人心而有趣的內核之旅。
在之后的6年中，我對照Linux內核源碼，根據《深入理解Linux內核》、《深入理解Linux網絡內幕》、《深入理解Linux虛擬內存管理》，以及其他一些Linux內核文件系統、網絡協議棧方面的書籍，做了2200頁、87萬字的內核學習筆記，同時將相應的源碼注釋公布到網絡中供自由下載。
然而，這6年在看Linux內核代碼的過程中，以及在工程實踐中，總有一個幽靈般的陰影出現在我的腦海中：什么是內存屏障？2011年，我看過內核源碼目錄中的文檔以后，終于解決了標準內核和工具鏈一個關于內存屏障的故障。要復現這個故障，項目同事需要在整整一個房間里面擺滿單板和服務器，才能搭建一套復現環境，并且需要用多套這樣的環境，花費2個月時間才能復現一次相關故障。即使在解決了相關故障以后，我仍然覺得自己對內存屏障理解得不深刻。因為內核源碼目錄下的文檔，對內存屏障描述得仍然語焉不詳。那個幽靈仍然在腦海中盤旋：到底什么才是內存屏障？
直到有一天，我在辦公室晃悠的時候，突然在魯陽的辦公桌上發現一本特別的書——《IsParallelProgrammingHard,And,IfSo,WhatCanYouDoAboutIt?》。說它特別，是因為它是打印出來的。當我翻看了目錄看到里面包含內存屏障和RCU的時候，立即明白這就是我幾年來苦苦追尋而未得的書！并且，這本書里面花了濃重的筆墨來講述這兩個主題。還有比這更令人高興的事情嗎？
聰明的讀者一定知道接下來發生了什么事情。你猜得沒錯，我鼓動魯陽一起翻譯這本書，當時的目的純粹是為了學習，并且分享到網絡中。在此，我不得不向魯陽道歉：為了讓你堅持下去，我說過一些不留情面的話。這些話不過是云門禪宗棒喝之法而已。如果你早就忘記這些話，那就謝天謝地了！
為了翻譯好這本書，我特意去補了一下英語方面的課。最終，這本書能夠與讀者見面，大概有以下幾個原因。
1．魯陽和我都有一點Linux內核和并行編程基礎。
2．我們的熱情和有點自大的自信。
3．英語不算太難學。
4．家人的容忍。也許是我常常念叨：翻譯好這本書，工資可能漲一大截。
5．有一些值得感恩的網友，他們督促我們做好翻譯工作。
在終于完整地翻譯完本書之際，我整理出幾條理由，這些理由使得本書有成為經典的潛質。
1．深刻是本書的特點。本書從霍金提出的兩個理論物理限制為起點，站在硬件而不是軟件的角度，闡述并行編程的難題。讓人有一種“知其然并且知其所以然”的感覺。書中不少觀點，如內存屏障的傳遞性，是資深工程師也不容易理解的。但是，看過本書以后，讀者會有一種豁然開朗的感覺。
2．在并行編程方面，本書比較全面，并且包含豐富的示例。包括但不僅僅限于硬件基礎、緩存、并行設計、鎖、RCU、內存屏障、驗證及形式驗證、實時并行計算。
3．原著作者Paul是真正的大師。看過作者簡介，并且真正知道RCU在Linux內核中份量的朋友，不知道你們是否會在心里嘀咕：在Linux開源社區，有沒有人愿意試著去挖Paul的墻角，代替Paul把RCU維護起來？
4．Paul在40年的職業生涯中，大部分時間都在編寫并行編程的代碼。當他扛著與奔馳車價值相當的雙核計算機往實驗室走的時候，我這個有20年編程經驗的程序員，還沒有上小學。
5．國內對并行計算和Linux內核的研究逐步深入，讀者期待一本深入講解并行編程的書籍。本書有并行編程的入門知識，更有值得細細回味、反復琢磨的金玉良言。
6．譯者多次核對校正，盡量做到符合原著本意，兩位譯者有多年Linux內核經驗，盡量做到不錯譯。
當然，由于譯者水平的原因，書中錯漏之處在所難免，熱忱歡迎讀者提出批評建議。
最后，譯者誠心感謝原著作者Paul給大家奉獻了一本好書；也感謝電子工業出版社符隆美編輯的辛勤工作；以及資深互聯網軟件工程師劉海平，感謝你熱心地向出版社推薦這本書；最真心的感謝留給同桌夫人巫緒萍及我們的兒子謝文韜，犧牲了大量陪伴你們的時間，謝謝你們的寬容！
謝寶友
2017年4月20日
于深圳
譯者序2
大概在6年前，那時我在中興通訊的操作系統部門工作。當時中興通訊希望加入Linux基金會，由于英語還不算差，操作系統部的鐘衛東部長讓我負責一些部門與開源社區的合作推進工作，所以除了編程工作以外，我時常密切關注Linux開源社區的最新動態。有一天我在LWN.net上瀏覽新聞，一條消息突然跳入了我的視線：PaulMcKenney出了一本關于并行編程的書（原文鏈接在此，https://lwn.net/Articles/421425）。那時候我還不知道Paul是誰，但是書的內容很吸引人，于是我開始把書介紹給周圍的同事。過了一陣子，謝寶友找到我，問我有沒有興趣一起把這本書翻譯成中文，我們倆一拍即合，開始利用業余時間合力翻譯這本大部頭。
雖然當時本書的內容尚未完成，有一些章節只列了提綱，但是關于并行程序的設計思想、相關基礎知識、RCU和內存屏障方面的內容已經非常豐富，對于從事內核開發工作的我們來說，簡直就是寶庫，我們認為即使只翻譯這些內容，對其他中國讀者來說也很有幫助。
翻譯的過程遠遠比最初想象得困難，原著作者Paul是一位有近40年從業經驗的資深大牛，在書中大量使用了Linux內核的術語、并行編程的研究文獻，以及對復雜算法和示例代碼的解釋，在翻譯過程中需要字斟句酌，力求準確地傳達作者的原意，所以進度很慢。不過當時我還未婚，尚算自由，下班以后的空余時間幾乎全部用來做這件事，大概花了4個月的時間完成了第一個中文版本。
我們把中文版發布到了網上，也開始和Paul聯系，請他幫我們宣傳，希望能讓更多的中國開發者知道這件事。同年在南京舉行的CLK2011（中國Linux內核開發者大會）上，我和寶友見到了Paul本人。這里有一個有趣的小插曲，由于會后找Paul提問和咨詢的人太多，Paul干脆在會場外席地而坐，逐一侃侃而談。不擺架子的大牛，是Paul給我留下的最深刻印象。
后來因為家庭的原因，我去了美國。生活充滿了新的挑戰，繼續更新內容的事情因此擱置。期間，寶友繼續翻譯了答案部分的內容，也有出版社聯系過我們，想出版本書的中文版，但因為種種原因，后來無疾而終。直到去年夏天，電子工業出版社正式從原著作者處獲得版權授權，邀請我和寶友將本書最新版翻譯成中文。于是我們再度合作，花了大半年時間，重新審閱翻譯稿，將內容更新到最新版本，完整地翻譯了所有附錄和小問題答案，同時修訂了很多錯誤。相較之前的翻譯稿，作者對這一版的內容有大幅改變：
第6章新增了對迷宮問題并行化解法的討論，
完全重寫了第7章鎖和第8章數據所有權的內容。
第9章新增了關于危險指針和順序鎖，更新了一些例子。
新增了第10章，如何將哈希表并行化。
新增了第11章，如何驗證并行算法的正確性。
新增了第13章綜合應用。
新增了第15章并行實時計算。
從這個列表可以看出，原著作者Paul對并行編程技術的思考一直沒有停止，還在不停地將這個經典領域的新問題和新進展加入到本書中。比如一些學者對常見數據結構哈希表的最新研究，使得本書不僅成為一部案頭必備的工具書，還是一個開拓新知識的出發點。
作者在書中數次強調設計的重要性。工作以來，我曾參與的項目有操作系統內核、瀏覽器內核，目前開發的是內存數據庫，都屬于系統軟件的范疇。這些項目都大量使用了多線程來充分利用硬件。在這些實踐中，我有一點體會，關于分割數據、分割時間、減少跨線程訪問、并行快速路徑、鎖的使用紀律這些設計思想，一旦應用到項目中，代碼就變得清晰易懂，很少有BUG。一旦違反，就帶來難以維護的代碼，隨之而來的是層出不窮的BUG。
書中還散落著許多寶貴的經驗法則，比如10.6.3節中如何通過重新排列數據結構順序來避免緩存行“顛簸”。這些前輩摸索出來的經驗能讓新一代的開發者少走很多彎路。
作者的行文十分幽默，我在翻譯過程中，經常忍俊不禁。希望能在中文版中，盡量將作者的幽默感保留下來。
去年我的兒子小魚兒降生，作為一個新爸爸，白天工作，晚上在照顧孩子之余還要加班翻譯文稿，真是分秒必爭。最后借這個機會，將最真心的感謝留給我的夫人盧靜，感謝你對家庭的付出，沒有你的幫助和理解，就沒有本書中文版的面世。
魯陽
2017年6月16日于Woburn，Massachusetts
第1章 如何使用本書1
1.1 路線圖1
1.2 小問題2
1.3除本書之外的選擇3
1.4 示例源代碼4
1.5 這本書屬于誰4
第2章 簡介6
2.1 導致并行編程困難的歷史原因6
2.2 并行編程的目標7
2.2.1 性能8
2.2.2 生產率9
2.2.3 通用性9
2.3 并行編程的替代方案11
2.3.1 串行應用的多個實例11
2.3.2 使用現有的并行軟件11
2.3.3 性能優化12
2.4 是什么使并行編程變得復雜12
2.4.1 分割任務13
2.4.2 并行訪問控制13
2.4.3 資源分割和復制14
2.4.4 與硬件的交互14
2.4.5 組合使用14
2.4.6 語言和環境如何支持這些任務14
2.5 本章的討論15
第3章 硬件和它的習慣16
3.1 概述16
3.1.1 流水線CPU16
3.1.2 內存引用17
3.1.3 原子操作18
3.1.4 內存屏障19
3.1.5 高速緩存未命中19
3.1.6 I/O操作19
3.2 開銷20
3.2.1 硬件體系結構20
3.2.2 操作的開銷21
3.3 硬件的免費午餐23
3.3.1 3D集成23
3.3.2 新材料和新工藝24
3.3.3 是光，不是電子24
3.3.4 專用加速器24
3.3.5 現有的并行軟件25
3.4 對軟件設計的啟示25
第4章 辦事的家伙27
4.1 腳本語言27
4.2 POSIX多進程28
4.2.1 POSIX進程創建和銷毀28
4.2.2 POSIX線程創建和銷毀30
4.2.3 POSIX鎖31
4.2.4 POSIX讀/寫鎖34
4.3 原子操作37
4.4 Linux內核中類似POSIX的操作38
4.5 如何選擇趁手的工具39
第5章 計數40
5.1 為什么并發計數不可小看41
5.2 統計計數器42
5.2.1 設計43
5.2.2 基于數組的實現43
5.2.3 最終結果一致的實現44
5.2.4 基于每線程變量的實現46
5.2.5 本節討論48
5.3 近似上限計數器48
5.3.1 設計48
5.3.2 簡單的上限計數實現50
5.3.3 關于簡單上限計數的討論55
5.3.4 近似上限計數器的實現55
5.3.5 關于近似上限計數器的討論55
5.4 精確上限計數56
5.4.1 原子上限計數的實現56
5.4.2 關于原子上限計數的討論62
5.4.3 Signal-Theft上限計數的設計62
5.4.4 Signal-Theft上限計數的實現63
5.4.5 關于Signal-Theft上限計數的討論68
5.5 特殊場合的并行計數68
5.6 關于并行計數的討論69
5.6.1 并行計數的性能70
5.6.2 并行計數的專門化71
5.6.3 從并行計數中學到什么71
第6章 對分割和同步的設計73
6.1 分割練習73
6.1.1 哲學家就餐問題73
6.1.2 雙端隊列75
6.1.3 關于分割問題示例的討論81
6.2 設計準則82
6.3 同步粒度83
6.3.1 串行程序84
6.3.2 代碼鎖85
6.3.3 數據鎖86
6.3.4 數據所有權88
6.3.5 鎖粒度與性能88
6.4 并行快速路徑90
6.4.1 讀/寫鎖91
6.4.2 層次鎖91
6.4.3 資源分配器緩存92
6.5 分割之外97
6.5.1 使用工作隊列的迷宮問題并行解法97
6.5.2 另一種迷宮問題的并行解法100
6.5.3 性能比較I102
6.5.4 另一種迷宮問題的串行解法104
6.5.5 性能比較II104
6.5.6 未來展望與本節總結105
6.6 分割、并行化與優化106
第7章 鎖107
7.1 努力活著108
7.1.1 死鎖108
7.1.2 活鎖與饑餓114
7.1.3 不公平的鎖116
7.1.4 低效率的鎖117
7.2 鎖的類型117
7.2.1 互斥鎖117
7.2.2 讀/寫鎖118
7.2.3 讀/寫鎖之外118
7.2.4 范圍鎖119
7.3 鎖在實現中的問題121
7.3.1 基于原子交換的互斥鎖實現示例121
7.3.2 互斥鎖的其他實現122
7.4 基于鎖的存在保證124
7.5 鎖：是英雄還是惡棍125
7.5.1 應用程序中的鎖：英雄125
7.5.2 并行庫中的鎖：只是一個工具126
7.5.3 并行化串行庫時的鎖：惡棍128
7.6 總結130
第8章 數據所有權131
8.1 多進程131
8.2 部分數據所有權和pthread線程庫132
8.3 函數輸送132
8.4 指派線程132
8.5 私有化133
8.6 數據所有權的其他用途133
第9章 延后處理134
9.1 引用計數134
9.1.1 各種引用計數的實現135
9.1.2 危險指針140
9.1.3 支持引用計數的Linux原語141
9.1.4 計數優化142
9.2 順序鎖142
9.3 讀-復制-修改（RCU）145
9.3.1 RCU介紹145
9.3.2 RCU基礎147
9.3.3 RCU用法155
9.3.4 Linux內核中的RCU API166
9.3.5 “玩具式”的RCU實現171
9.3.6 RCU練習188
9.4 如何選擇？188
9.5 更新端怎么辦190
第10章 數據結構191
10.1 從例子入手191
10.2 可分割的數據結構192
10.2.1 哈希表的設計192
10.2.2 哈希表的實現192
10.2.3 哈希表的性能195
10.3 讀側重的數據結構197
10.3.1 受RCU保護的哈希表的實現197
10.3.2 受RCU保護的哈希表的性能199
10.3.3 對受RCU保護的哈希表的討論201
10.4 不可分割的數據結構201
10.4.1 可擴展哈希表的設計202
10.4.2 可擴展哈希表的實現203
10.4.3 可擴展哈希表的討論210
10.4.4 其他可擴展的哈希表211
10.5 其他數據結構214
10.6 微優化214
10.6.1 實例化215
10.6.2 比特與字節215
10.6.3 硬件層面的考慮216
10.7 總結217
第11章 驗證218
11.1 簡介218
11.1.1 BUG來自于何處218
11.1.2 所需的心態220
11.1.3 應該何時開始驗證221
11.1.4 開源之路221
11.2 跟蹤222
11.3 斷言223
11.4 靜態分析224
11.5 代碼走查224
11.5.1 審查224
11.5.2 走查225
11.5.3 自查225
11.6 幾率及海森堡BUG227
11.6.1 離散測試統計228
11.6.2 濫用離散測試統計229
11.6.3 持續測試統計229
11.6.4 定位海森堡BUG232
11.7 性能評估235
11.7.1 性能基準236
11.7.2 剖析236
11.7.3 差分分析237
11.7.4 微基準237
11.7.5 隔離237
11.7.6 檢測干擾238
11.8 總結242
第12章 形式驗證244
12.1 通用目的的狀態空間搜索244
12.1.1 Promela和Spin244
12.1.2 如何使用 Promela249
12.1.3 Promela 示例: 鎖251
12.1.4 Promela 示例: QRCU254
12.1.5 Promela初試牛刀：dynticks和可搶占RCU260
12.1.6 驗證可搶占RCU和dynticks264
12.2 特定目的的狀態空間搜索288
12.2.1 解析Litmus測試289
12.2.2 Litmus測試意味著什么290
12.2.3 運行Litmus測試291
12.2.4 PPCMEM討論292
12.3 公理方法293
12.4 SAT求解器294
12.5 總結295
第13章 綜合應用296
13.1 計數難題296
13.1.1 對更新進行計數296
13.1.2 對查找進行計數296
13.2 使用RCU拯救并行軟件性能297
13.2.1 RCU和基于每CPU變量的統計計數297
13.2.2 RCU及可插拔I/O設備的計數器300
13.2.3 數組及長度300
13.2.4 相關聯的字段301
13.3 散列難題302
13.3.1 相關聯的數據元素302
13.3.2 更新友好的哈希表遍歷303
第14章 高級同步304
14.1 避免鎖304
14.2 內存屏障304
14.2.1 內存序及內存屏障305
14.2.2 如果B在A后面，并且C在B后面，為什么C不在A后面306
14.2.3 變量可以擁有多個值307
14.2.4 能信任什么東西308
14.2.5 鎖實現回顧312
14.2.6 一些簡單的規則313
14.2.7 抽象內存訪問模型314
14.2.8 設備操作315
14.2.9 保證315
14.2.10 什么是內存屏障316
14.2.11 鎖約束325
14.2.12 內存屏障示例326
14.2.13 CPU緩存的影響328
14.2.14 哪里需要內存屏障329
14.3 非阻塞同步329
14.3.1 簡單NBS330
14.3.2 NBS討論331
第15章 并行實時計算332
15.1 什么是實時計算332
15.1.1 軟實時332
15.1.2 硬實時333
15.1.3 現實世界的實時334
15.2 誰需要實時計算336
15.3 誰需要并行實時計算337
15.4 實現并行實時系統337
15.4.1 實現并行實時操作系統339
15.4.2 實現并行實時應用349
15.5 實時VS.快速：如何選擇351
第16章 易于使用353
16.1 簡單是什么353
16.2 API設計的Rusty準則353
16.3 修整Mandelbrot集合354
第17章 未來的沖突357
17.1 曾經的CPU技術不代表未來357
17.1.1 單處理器Uber Alles358
17.1.2 多線程Mania359
17.1.3 更多類似的場景359
17.1.4 撞上內存墻359
17.2 事務內存360
17.2.1 外部世界361
17.2.2 進程修改364
17.2.3 同步367
17.2.4 討論370
17.3 硬件事務內存371
17.3.1 HTM與鎖相比的優勢372
17.3.2 HTM與鎖相比的劣勢373
17.3.3 HTM與增強后的鎖機制相比的劣勢379
17.3.4 HTM最適合的場合380
17.3.5 潛在的攪局者380
17.3.6 結論382
17.4 并行函數式編程383
附錄A 重要問題385
A.1 “After”的含義是什么385
A.2 “并發”和“并行”之間的差異是什么388
A.3 現在是什么時間389
附錄B 同步原語391
B.1 組織和初始化391
B.1.1 smp_init()391
B.2 線程創建、銷毀及控制392
B.2.1 create_thread()392
B.2.2 smp_thread_id()392
B.2.3 for_each_thread()392
B.2.4 for_each_running_thread()392
B.2.5 wait_thread()393
B.2.6 wait_all_threads()393
B.2.7 用法示例393
B.3 鎖394
B.3.1 spin_lock_init()394
B.3.2 spin_lock()394
B.3.3 spin_trylock()394
B.3.4 spin_unlock()394
B.3.5 用法示例395
B.4 每線程變量395
B.4.1 DEFINE_PER_THREAD()395
B.4.2 DECLARE_PER_THREAD()395
B.4.3 per_thread()395
B.4.4 __get_thread_var()396
B.4.5 init_per_thread()396
B.4.6 用法示例396
B.5 性能396
附錄C 為什么需要內存屏障397
C.1 緩存結構397
C.2 緩存一致性協議399
C.2.1 MESI狀態399
C.2.2 MESI協議消息400
C.2.3 MESI狀態圖400
C.2.4 MESI協議示例401
C.3 存儲導致不必要的停頓402
C.3.1 存儲緩沖403
C.3.2 存儲轉發403
C.3.3 存儲緩沖區及內存屏障404
C.4 存儲序列導致不必要的停頓406
C.4.1 使無效隊列406
C.4.2 使無效隊列及使無效應答407
C.4.3 使無效隊列及內存屏障407
C.5 讀和寫內存屏障409
C.6 內存屏障示例410
C.6.1 亂序體系結構410
C.6.2 示例1411
C.6.3 示例2412
C.6.4 示例3412
C.7 特定的內存屏障指令413
C.7.1 Alpha414
C.7.2 AMD64417
C.7.3 ARMv7-A/R417
C.7.4 IA64418
C.7.5 PA-RISC418
C.7.6 POWER / Power PC418
C.7.7 SPARC RMO、PSO及TSO419
C.7.8 x86420
C.7.9 zSeries421
C.8 內存屏障是永恒的嗎421
C.9 對硬件設計者的建議422
附錄D 問題答案423
D.1 如何使用本書423
D.2 簡介424
D.3 硬件和它的習慣427
D.4 辦事的家伙429
D.5 計數433
D.6 對分割和同步的設計445
D.7 鎖449
D.8 數據所有權455
D.9 延遲處理456
D.10 數據結構471
D.11 驗證473
D.12 形式驗證478
D.13 綜合應用481
D.14 高級同步483
D.15 并行實時計算486
D.16 易于使用487
D.17 未來的沖突487
D.18 重要問題490
D.19 同步原語491
D.20 為什么需要內存屏障491
附錄E 術語495
附錄F 感謝502
F.1 評審者502
F.2 硬件提供者502
F.3 原始出處503
F.4 圖表作者503
F.5 其他幫助505
作者序
我希望能夠說本書的誕生源于甜蜜和光明，但這無疑是個謊言。和許多需要長年堅持努力的事情一樣，本書經過了大量挫折才得以誕生。
你看，大約10年前，在并發領域的一個行業專家小組研討會上，我很榮幸得以提問最后一個問題。一些參會的專家長篇大論地討論了并行編程的高難度，所以我問為什么并行編程不會在10或20年內成為司空見慣的事情。大多數小組成員一點都不喜歡這個問題。事實上，第一個小組成員試圖用一個簡短的回答敷衍了事，但我很容易地做了簡短的反駁。無奈，他嘗試給出了第二個簡短回答，我也繼續反駁。幾輪之后，他大聲喊叫：“像你這樣的人應該用錘子敲敲頭！”我不甘示弱地回答道：“那你可要排隊才能敲得到。”
我不認為這種交流是特別有啟發性的，相反這展示了一個毫無疑問的事實：這位“業內”專家對于并行編程一無所知。不過在場的其他聽眾卻認為這場對話非常有啟發性，尤其是那一位感謝我提出這個問題的聽眾，他的眼里甚至含著淚水。他像學徒一樣在Sequent計算機系統公司學到了并行編程的訣竅，正如我曾經所做的那樣。后來他跳槽去了另一家公司，他的新雇主開始涉足并行編程。出乎他意料之外，事情發展得并非一帆風順。正如他所說，“我已經足足跟他們說了兩年，只要你用正確的辦法，這并不是很難，但他們完全不聽我的話！”
現在，我們很容易將這個悲傷故事里面的團隊作為反面教材。但是在他們的看法中，并行編程等于用你自己的智力傷害自己。除非你了解實現并行性的正確方法，否則在意識到遇到麻煩之前，你越聰明，挖的坑就越深。因此，你越聰明，并行編程看起來就越難。不僅如此，在這件事發生時，極少有人知道如何進行并行編程，這意味著大多數人剛剛開始了解到他們為自己挖的并行編程坑的深度。
即使如此，當這個人用哽咽的聲音講述他的故事，眼淚滑過他的臉龐時，我意識到我不得不做一些事。那就是寫眼前這本書，這里面不僅僅濃縮我自己四分之一個世紀的經歷，還有其他人加起來數不清幾個世紀的經歷。
我的母語是英語，英語是我唯一可以聲稱掌握了的語言。但幸運的是，感謝魯陽和謝寶友所付出的巨大努力，現在中文版翻譯即將面世。我希望這本書不僅可以幫助你學習我所知道的知識，從而不再需要擔心并行編程，還能使你能夠創建屬于自己的并行編程新發現！
PaulE.McKenney
推薦序
讀著《深入理解并行編程》的樣章，我的腦海里不斷地浮現出9年前的一幕幕。我在網上尋找操作系統的志同道合者，看到一個稅收專業中專畢業者的自薦信，其時他已具有10年的IT行業工作經驗，從事過大量手機、通信行業軟件研發工作，擔任過項目總監研發管理工作，在電信應用開發方面已經做得比較成功。但他對操作系統有濃厚的興趣、執著的追求，放棄了在高層應用軟件方面的既有優勢，專注于操作系統的研究。離職在家，利用半年時間開發出一個嵌入式操作系統模型，計劃兩年內研發一款自研操作系統。有感于他的執著和熱愛，我向公司爭取破格錄取他。我認為做一個操作系統不難，但做生態難，做商業成功難，建議他深入學習開源Linux的技術，站到巨人肩膀上，再結合操作系統團隊的商業模式探索，爭取把操作系統做成功。于是，他如癡如醉地研究Linux內核，在一年時間里，每天晚上堅持花三個小時以上的時間鉆研《深入理解Linux內核》這本書，還將自己的讀書心得筆記共享到團隊論壇上，并對開源內核進行注解，分享到開源論壇上。
2008年正是多核架構快速發展之時，操作系統的支持參差不齊，驅動、應用開發模式不成熟，既有單態單核單進程的業務應用如何進行重構和演進，方案設計、開發聯調、故障排查、系統調優又會遇到很多復雜和棘手的問題，中興通訊操作系統團隊需要支撐公司所有產品、各種CPU架構、各種復雜業務場景，團隊面臨著前所未有的技術和進度壓力。團隊成員除了在研發一線通過不斷實踐進行被動積累和提升外，也加強了主動的理論知識提升，閱讀《深入理解并行編程》就是其中之一。令我印象非常深刻的是，多核故障往往比較隨機和復雜，難以復現和理解，但以謝寶友為代表的團隊成員往往可以通過閱讀業務、驅動、內核代碼就定位到故障根源，整理出故障邏輯，我認為這與他們的系統理論水平提升是分不開的。非常欣慰的是，我們成功地解決了這個過渡時期涌現的諸如多核內存序相關故障，利用無鎖并行編程優化了系統性能。時至今日，我們團隊已經從30人發展到數百人，嵌入式操作系統已全面應用于公司所有產品，在全球穩定商用，并且擴展應用到電力、鐵路、汽車等領域，2016年獲得了第四屆中國工業大獎。
另一方面，站在技術的角度來看，在計算機領域，并行編程的困難是眾所周知的。
有4、5年編程經驗的讀者，可能或多或少遇到過并行編程的問題，最著名的問題可能就是死鎖。讀者需要掌握調試死鎖問題的技巧，以及避免死鎖問題的編程技術。
喜歡深入思考的讀者，在理解并解決死鎖問題之后，可能還會閱讀并行編程方面的書籍，進一步接觸到活鎖、饑餓等更有趣的并行編程問題。中興通訊操作系統團隊的同事，就曾經在開源虛擬化軟件中遇到過類似的問題：虛擬機容器在互斥鎖的保護下，輪詢系統狀態并等待狀態變化。這樣的輪詢操作造成了進程調度不及時，系統狀態遲遲不能變化。這是一個典型的活鎖問題。在多核系統越來越普及的今天，類似的活鎖問題更容易出現。解決這類問題，需要經驗豐富的工程師，借助多種調試工具，花費不少的時間。
但是，并行編程僅僅與鎖相關嗎？
在摩爾定律尚未失效時，并行編程確實主要與鎖緊密相關。但是，我們看看霍金向IT工程師所提出的兩個難題：
1．有限的光速；
2．物質的原子特性。
這兩個難題最終會將CPU頻率的理論上限限制在10GHz以內，不可避免地使摩爾定律失效。要繼續提升硬件性能，需要借助于多核擴展。
要充分發揮多核系統的性能，必須提升并行軟件的擴展性。也就是說，并行軟件需要盡量減少鎖沖突，避免由于鎖競爭而引起性能急劇下降。這不是一件簡單的事情！我們知道，Linux操作系統在接近20年的時候內，一直受到大內核鎖的困擾。為了徹底拋棄大內核鎖，開源社區近幾年內做出了艱辛的努力，才實現了這個目標。即使如此，Linux內核仍然大量使用不同種類的鎖，并且不可能完全放棄鎖的使用。
也許你會說，在多核系統中，有一種簡單的避免鎖的方法，就是原子變量。在某些架構中，原子變量是由單條指令實現的，性能“想必”不差，使用方法也簡單。曾經有一位具有十多年編程經驗的工程師也表達過類似的觀點。在此，有兩個問題需要回答。
1．這樣的原子操作指令，其性能真的不差？它的執行周期是否可能達到上千個時鐘周期？
2．對于多個相互之間有邏輯關聯的變量，原子操作是否滿足要求？
實際上，多核系統中的并行軟件，除了常見的鎖之外，還需要使用冒險指針、RCU、內存屏障這樣的重量級并行編程工具。這些編程工具都屬于“無鎖編程”的范疇。
即使在Linux內核開源社區工作10年以上的資深工程師，也不一定能真正靈活自如地使用RCU、內存屏障來進行并行編程。因此，真正了解并行編程的讀者，難免在面對并行編程難題時，有一種“撫襟長嘆息”的感覺。
然而，我們知道，有很多重要的應用依賴于并行——圖形渲染、密碼破解、圖像掃描、物理與生物過程模擬等。有一個極端的例子，在證券交易所，為了避免長距離傳輸引起的通信延遲（理論上，光束繞地球一周需要大概130ms），需要將分析證券交易的計算機放到更接近證券交易的地方，并且壓榨出計算機的所有性能。這樣，才能保證達成有利的證券交易。可以毫不夸張地說，對軟件性能有苛刻需求的軟件工程師和大型軟件開發企業，都需要真正掌握并行編程的藝術，特別是“無鎖編程”的藝術。一旦真正掌握了，它就會為你帶來意想不到的性能提升。曾經有一位著名企業的高級專家，在應用了本書所述的RCU后，軟件性能提升了大約10倍。
本書正是這樣一本深入講解多核并行編程，特別是無鎖編程的好書。
首先，本書作者Paul具有40年軟件編程職業生涯，他大部分的工作都與并行編程相關。即使在領導IBMLinux中心時，他仍然堅持每天編程，是一名真正的“工匠”。同時，作者也是Linux開源社區RCU模塊的領導者和維護者。認真閱讀本書后，不得不欽佩于作者在并行編程方面的真知灼見和實踐能力。例如作者親自編寫了一個軟件用例，來考察CPU核之間原子操作和鎖的性能，得出一個結論，原子操作和鎖可能消耗超過1000個CPU時鐘周期；作者也編寫過另外一個關于全局變量的用例，其中一個CPU核遞增操作一個全局變量，同時在不同的CPU核上觀察所讀到的全局變量值。這個用例向讀者展示了多核系統令人驚奇的、反直覺的效果；作者對內存屏障的講解，特別是內存屏障傳遞性的講解，十分深入。這些深入的內容，難得一見，非大師不能為。
其次，這本書也得到Linux內核社區和應用軟件專家的一致推薦。這些推薦者既包括Linux社區大名鼎鼎的IngoMolnar、RustyRussel、GregKroah-Hartman、MagedM.Micheal，也包括國內活躍于社區的龐訓磊、ShawnGuo等開源貢獻者，還包括Linaro開源組織的領導和資深工程師，以及在BAT工作多年的高級應用軟件專家。
第三，這本書的內容比較全面。除了介紹常見的鎖以外，還重點介紹了RCU的使用及其原理，以及實現RCU的基礎：內存屏障。本書最后還介紹了并行軟件的驗證，以及并行實時計算等內容。實際上，其中每一部分都是并行編程的寶藏。由于篇幅和難度的原因，作者在當前版本中，將RCU部分作了大幅壓縮。對RCU感興趣的讀者可以閱讀早期原版著作。即使如此，本書對RCU的講解也非常深入。對于并行軟件的驗證，作者提出了不少獨特的觀點，這些觀點和作者多年的編程經驗息息相關，與常見的理論著作相比，有一定的新意。形式驗證部分，作者以實際的例子，一步一步講述驗證過程，很明顯，作者親自動手做過這種驗證。并行實時計算部分，是作者新增的內容，別具一格，值得讀者細讀。內存屏障部分，是本書一個難點，借助于作者在這方面的功力，需要讀者反復閱讀，才能真正理解。
第四，這本書講解得很深入。有些語句，需要讀者反復琢磨、推敲，甚至需要多次通讀本書才能領會作者的意思。也許，經典書籍的閱讀方法均是如此。剛剛開始接觸Linux內核的讀者，不太會喜歡閱讀《深入理解Linux內核》一書，覺得這本書不易理解。但是，如果你愿意花一年時間，將這本書反復閱讀三遍，則會有一種別樣的心情。本書也是如此，建議讀者在初次閱讀時，不要輕易放棄。本書實為并行編程方面不可多得的好書。舉兩個例子：第一，5.2.2節中有一句原文是“Onewaytoprovideper-threadvariablesistoallocateanarraywithoneelementperthread(presumablycachealignedandpaddedtoavoidfalsesharing).”。譯者將其翻譯為“一種實現每線程變量的方法是分配一個數組，數組每個元素對應一個線程（假設已經對齊并且填充過了，這樣可以防止共享出現“假共享”）”。第一次閱讀本書，可能會不理解括號中那句話，有一種云里霧里的感覺。要真正理解這句話，需要讀者仔細閱讀本書后面關于MESI消息協議部分，參閱更多參考資料。要理解本句中“對齊”和“填充”兩個詞，也需要深厚的內核功底。第二，14.2.10.2節，“一個LOCK操作充當了一個單方面屏障的角色。它確保：對于系統中其他組件的角度來說，所有鎖操作后面的內存操作看起來發生在鎖操作之后。LOCK操作之前的內存操作可能發生在它完成之后。”這句話讀起來也比較繞，難于理解，似乎也相互矛盾。實際上，讀者需要琢磨“看起來”這個詞，它表示其他核看到內存操作的順序，并不代表內存操作的完成時機。
總之，如果你對并行編程或者操作系統內核有興趣，或者需要對項目進行深度性能優化，我強烈推薦這本并行編程的經典好書！
中興通訊操作系統產品部鐘衛東
新書資訊