本書由G?del獎得主領銜撰寫，主要討論共享存儲通信方式下的多處理器并發程序設計。首先介紹基本原理，分析異步并發環境中的可計算問題，包括相關度量標準和方法。然后開展應用實踐，側重于并發程序的性能分析。每一章討論一種特定的并發數據結構、程序設計模式或算法技巧。第2版對數據并行、事務性編程、存儲管理等內容做了重點更新和擴充，并采用C++語言重構相關示例，更加關注底層機制。本書適合作為高等院校計算機相關專業的課程教材，也適合作為業界技術人員的參考書籍。

莫里斯·赫利希（Maurice Herlihy） 布朗大學計算機科學教授，曾任職于卡內基·梅隆大學和DEC公司劍橋實驗室。他獲得了包括Edsger W. Dijkstra獎（2003，2012）、ACM/EATCS Gödel獎（2004）、IEEE Wallace McDowell獎（2013）和Fulbright杰出講席（2012）在內的眾多榮譽。他是ACM會士，美國國家發明家科學院、美國國家工程院以及美國藝術與科學院院士。他擁有麻省理工學院計算機科學博士學位。

尼爾·沙維特（Nir Shavit） 麻省理工學院計算機科學教授，特拉維夫大學計算機科學教授，曾任職于Sun實驗室和Oracle實驗室。他與Maurice Herlihy分享了Edsger W. Dijkstra獎（2012）和ACM/EATCS Gödel獎（2004）。他擁有希伯來大學計算機科學博士學位。

維克多·盧昌科（Victor Luchangco） Algorand公司高級算法研究員，曾任職于Sun實驗室和Oracle實驗室。他擁有麻省理工學院計算機科學博士學位。

邁克爾·斯皮爾（Michael Spear） 理海大學計算機科學教授。他擁有羅切斯特大學計算機科學博士學位。

譯者序<br/>前言<br/>第1章　導論1<br/>1.1　共享對象和同步2<br/>1.2　一則寓言故事4<br/>1.2.1　互斥協議的特性6<br/>1.2.2　故事的寓意7<br/>1.3　生產者-消費者問題7<br/>1.4　讀者-寫者問題9<br/>1.5　并行化的嚴酷現實10<br/>1.6　并行程序設計11<br/>1.7　章節注釋12<br/>1.8　練習題12<br/>第一部分　基本原理<br/>第2章　互斥16<br/>2.1　時間和事件16<br/>2.2　臨界區16<br/>2.3　雙線程解決方案19<br/>2.3.1　LockOne類19<br/>2.3.2　LockTwo類20<br/>2.3.3　彼得森鎖21<br/>2.4　關于死鎖的說明22<br/>2.5　過濾鎖23<br/>2.6　公平性25<br/>2.7　蘭波特的面包房鎖算法25<br/>2.8　有界時間戳27<br/>2.9　存儲單元數量的下界29<br/>2.10　章節注釋32<br/>2.11　練習題32<br/>第3章　并發對象36<br/>3.1　并發性和正確性36<br/>3.2　串行對象38<br/>3.3　順序一致性39<br/>3.3.1　順序一致性與實時次序41<br/>3.3.2　順序一致性是非阻塞的41<br/>3.3.3　可組合性42<br/>3.4　線性一致性43<br/>3.4.1　可線性化點43<br/>3.4.2　線性一致性和順序一致性43<br/>3.5　靜態一致性44<br/>3.5.1　靜態一致性的特性44<br/>3.6　形式化定義44<br/>3.6.1　歷史記錄45<br/>3.6.2　線性一致性46<br/>3.6.3　線性一致性滿足可組合性47<br/>3.6.4　線性一致性是非阻塞的47<br/>3.7　內存一致性模型47<br/>3.8　演進條件48<br/>3.8.1　無等待性48<br/>3.8.2　無鎖性49<br/>3.8.3　無阻塞性49<br/>3.8.4　阻塞演進條件50<br/>3.8.5　演進條件的特征描述50<br/>3.9　評析51<br/>3.10　章節注釋52<br/>3.11　練習題52<br/>第4章　共享存儲器基礎57<br/>4.1　寄存器空間58<br/>4.2　寄存器構造62<br/>4.2.1　MRSW安全寄存器63<br/>4.2.2　MRSW常規布爾寄存器63<br/>4.2.3　MRSW常規M-值寄存器64<br/>4.2.4　SRSW原子寄存器65<br/>4.2.5　MRSW原子寄存器67<br/>4.2.6　MRMW原子寄存器69<br/>4.3　原子快照71<br/>4.3.1　無阻塞快照71<br/>4.3.2　無等待快照73<br/>4.3.3　正確性證明75<br/>4.4　章節注釋76<br/>4.5　練習題77<br/>第5章　同步操作原語的相對能力80<br/>5.1　共識數80<br/>5.1.1　狀態和價81<br/>5.2　原子寄存器82<br/>5.3　共識性協議84<br/>5.4　FIFO隊列85<br/>5.5　多重賦值對象87<br/>5.6　讀取-修改-寫入操作90<br/>5.7　Common2 RMW操作91<br/>5.8　compareAndSet操作92<br/>5.9　章節注釋93<br/>5.10　練習題94<br/>第6章　共識性的通用性99<br/>6.1　引言99<br/>6.2　通用性99<br/>6.3　無鎖的通用構造100<br/>6.4　無等待的通用構造103<br/>6.5　章節注釋107<br/>6.6　練習題108<br/>第二部分　應用實踐<br/>第7章　自旋鎖和爭用112<br/>7.1　實際問題的研究112<br/>7.2　易失性字段和原子對象114<br/>7.3　測試-設置鎖115<br/>7.4　指數退避算法117<br/>7.5　隊列鎖119<br/>7.5.1　基于數組的鎖119<br/>7.5.2　CLH隊列鎖121<br/>7.5.3　MCS隊列鎖123<br/>7.6　時限隊列鎖125<br/>7.7　層級鎖127<br/>7.7.1　層級退避鎖128<br/>7.7.2　同類群組鎖129<br/>7.7.3　同類群組鎖的實現130<br/>7.8　復合鎖132<br/>7.9　線程單獨運行的快速路徑137<br/>7.10　鎖的選擇說明138<br/>7.11　章節注釋138<br/>7.12　練習題139<br/>第8章　管程和阻塞同步141<br/>8.1　引言141<br/>8.2　管程鎖和條件141<br/>8.2.1　條件142<br/>8.2.2　喚醒丟失的問題145<br/>8.3　讀取-寫入鎖146<br/>8.3.1　簡單的讀取-寫入鎖146<br/>8.3.2　公平的讀取-寫入鎖148<br/>8.4　可重入鎖150<br/>8.5　信號量151<br/>8.6　章節注釋151<br/>8.7　練習題152<br/>第9章　鏈表：鎖的作用155<br/>9.1　引言155<br/>9.2　基于鏈表的集合156<br/>9.3　并發推理157<br/>9.4　粗粒度同步159<br/>9.5　細粒度同步160<br/>9.6　樂觀同步163<br/>9.7　惰性同步167<br/>9.8　非阻塞同步170<br/>9.9　討論175<br/>9.10　章節注釋176<br/>9.11　練習題176<br/>第10章　隊列、內存管理和ABA問題178<br/>10.1　引言178<br/>10.2　隊列179<br/>10.3　有界部分隊列179<br/>10.4　無界完全隊列183<br/>10.5　無鎖的無界隊列184<br/>10.6　內存回收和ABA問題187<br/>10.6.1　簡單的同步隊列190<br/>10.7　雙重數據結構192<br/>10.8　章節注釋194<br/>10.9　練習題194<br/>第11章　棧和消除196<br/>11.1　引言196<br/>11.2　無鎖的無界棧196<br/>11.3　消除198<br/>11.4　消除退避棧199<br/>11.4.1　無鎖交換機199<br/>11.4.2　消除數組201<br/>11.5　章節注釋204<br/>11.6　練習題204<br/>第12章　計數、排序和分布式協作208<br/>12.1　引言208<br/>12.2　共享計數208<br/>12.3　軟件組合209<br/>12.3.1　概述209<br/>12.3.2　一個擴展的實例215<br/>12.3.3　性能和健壯性216<br/>12.4　靜態一致池和計數器217<br/>12.5　計數網絡217<br/>12.5.1　可計數網絡218<br/>12.5.2　雙調計數網絡219<br/>12.5.3　性能和流水線227<br/>12.6　衍射樹228<br/>12.7　并行排序231<br/>12.8　排序網絡231<br/>12.8.1　設計一個排序網絡232<br/>12.9　樣本排序234<br/>12.10　分布式協作235<br/>12.11　章節注釋236<br/>12.12　練習題237<br/>第13章　并發哈希和固有并行240<br/>13.1　引言240<br/>13.2　封閉地址哈希集241<br/>13.2.1　粗粒度哈希集243<br/>13.2.2　帶狀哈希集244<br/>13.2.3　可細化的哈希集246<br/>13.3　無鎖的哈希集249<br/>13.3.1　遞歸有序拆分249<br/>13.3.2　BucketList類252<br/>13.3.3　LockFreeHashSet<T>類253<br/>13.4　開放地址哈希集255<br/>13.4.1　布谷鳥哈希算法255<br/>13.4.2　并發布谷鳥算法257<br/>13.4.3　帶狀并發布谷鳥哈希算法261<br/>13.4.4　可細化的并發布谷鳥哈希算法262<br/>13.5　章節注釋265<br/>13.6　練習題265<br/>第14章　跳躍鏈表和平衡查找266<br/>14.1　引言266<br/>14.2　順序跳躍鏈表266<br/>14.3　基于鎖的并發跳躍鏈表268<br/>14.3.1　概述268<br/>14.3.2　算法269<br/>14.4　無鎖的并發跳躍鏈表275<br/>14.4.1　概述275<br/>14.4.2　算法277<br/>14.5　并發跳躍鏈表283<br/>14.6　章節注釋284<br/>14.7　練習題284<br/>第15章　優先級隊列286<br/>15.1　引言286<br/>15.1.1　并發優先級隊列286<br/>15.2　基于數組的有界優先級隊列286<br/>15.3　基于樹的有界優先級隊列287<br/>15.4　基于堆的無界優先級隊列290<br/>15.4.1　順序堆290<br/>15.4.2　并發堆292<br/>15.5　基于跳躍鏈表的無界優先級隊列297<br/>15.6　章節注釋299<br/>15.7　練習題300<br/>第16章　調度和工作分配302<br/>16.1　引言302<br/>16.2　并行化分析308<br/>16.3　多處理器的實際調度311<br/>16.4　工作分配312<br/>16.4.1　工作竊取312<br/>16.4.2　讓步和多道程序設計313<br/>16.5　工作竊取雙端隊列314<br/>16.5.1　有界工作竊取雙端隊列314<br/>16.5.2　無界工作竊取雙端隊列318<br/>16.5.3　工作交易321<br/>16.6　章節注釋322<br/>16.7　練習題323<br/>第17章　數據并行326<br/>17.1　MapReduce328<br/>17.1.1　MapReduce框架328<br/>17.1.2　基于MapReduce的Word-Count應用程序330<br/>17.1.3　基于MapReduce的KMeans應用程序331<br/>17.1.4　MapReduce的實現332<br/>17.2　流計算334<br/>17.2.1　基于流的WordCount應用程序335<br/>17.2.2　基于流的KMeans應用程序336<br/>17.2.3　實現聚合運算的并行化338<br/>17.3　章節注釋340<br/>17.4　練習題341<br/>第18章　屏障347<br/>18.1　引言347<br/>18.2　屏障的實現348<br/>18.3　語義反向屏障348<br/>18.4　組合樹屏障349<br/>18.5　靜態樹屏障352<br/>18.6　終止檢測屏障353<br/>18.7　章節注釋356<br/>18.8　練習題357<br/>第19章　樂觀主義和手動內存管理363<br/>19.1　從Java過渡到C++363<br/>19.2　樂觀主義和顯式回收364<br/>19.3　保護掛起的操作365<br/>19.4　用于管理內存的對象366<br/>19.5　遍歷鏈表367<br/>19.6　風險指針369<br/>19.7　基于周期的內存回收372<br/>19.8　章節注釋374<br/>19.9　練習題375<br/>第20章　事務性編程376<br/>20.1　并發程序設計面臨的挑戰376<br/>20.1.1　鎖的問題376<br/>20.1.2　明確預測的問題377<br/>20.1.3　非阻塞算法的問題378<br/>20.1.4　可組合性問題379<br/>20.1.5　總結380<br/>20.2　事務性編程380<br/>20.2.1　事務性編程示例381<br/>20.3　事務性編程的硬件支持382<br/>20.3.1　硬件預測382<br/>20.3.2　基本緩存一致性382<br/>20.3.3　事務緩存一致性383<br/>20.3.4　硬件支持的局限性384<br/>20.4　事務性鎖消除384<br/>20.4.1　討論386<br/>20.5　事務性內存387<br/>20.5.1　運行時調度388<br/>20.5.2　顯式自我中止388<br/>20.6　軟件事務389<br/>20.6.1　使用所有權記錄的事務390<br/>20.6.2　基于值驗證的事務394<br/>20.7　硬件事務和軟件事務的有機結合396<br/>20.8　事務數據結構設計397<br/>20.9　章節注釋397<br/>20.10　練習題398<br/>附錄A　軟件基礎399<br/>附錄B　硬件基礎417<br/>參考文獻428