多處理器編程的藝術(shù)（修訂版）

出版者的話
譯者序
前言
教學(xué)建議
第1章 引言
1.1 共享對(duì)象和同步
1.2 生活實(shí)例
1.2.1 互斥特性
1.2.2 道德
1.3 生產(chǎn)者-消費(fèi)者問(wèn)題
1.4 讀者-寫者問(wèn)題
1.5 并行的困境
1.6 并行程序設(shè)計(jì)
1.7 本章注釋
1.8 習(xí)題
第一部分 原理
第2章 互斥
2.1 時(shí)間
2.2 臨界區(qū)
2.3 雙線程解決方案
2.3.1 LockOne類
2.3.2 LockTwo類
2.3.3 Peterson鎖
2.4 過(guò)濾鎖
2.5 公平性
2.6 Bakery算法
2.7 有界時(shí)間戳
2.8 存儲(chǔ)單元數(shù)量的下界
2.9 本章注釋
2.10 習(xí)題
第3章 并發(fā)對(duì)象
3.1 并發(fā)性與正確性
3.2 順序?qū)ο?br />3.3 靜態(tài)一致性
3.4 順序一致性
3.5 可線性化性
3.5.1 可線性化點(diǎn)
3.5.2 評(píng)析
3.6 形式化定義
3.6.1 可線性化性
3.6.2 可線性化性的復(fù)合性
3.6.3 非阻塞特性
3.7 演進(jìn)條件
3.8 Java存儲(chǔ)器模型
3.8.1 鎖和同步塊
3.8.2 volatile域
3.8.3 final域
3.9 評(píng)析
3.10 本章注釋
3.11 習(xí)題
第4章 共享存儲(chǔ)器基礎(chǔ)
4.1 寄存器空間
4.2 寄存器構(gòu)造
4.2.1 MRSW安全寄存器
4.2.2 MRSW規(guī)則布爾寄存器
4.2.3 M-值MRSW規(guī)則寄存器
4.2.4 SRSW原子寄存器
4.2.5 MRSW原子寄存器
4.2.6 MRMW原子寄存器
4.3 原子快照
4.3.1 無(wú)障礙快照
4.3.2 無(wú)等待快照
4.3.3 正確性證明
4.4 本章注釋
4.5 習(xí)題
第5章 同步原子操作的相對(duì)能力
5.1 一致數(shù)
5.2 原子寄存器
5.3 一致性協(xié)議
5.4 FIFO隊(duì)列
5.5 多重賦值對(duì)象
5.6 讀-改-寫操作
5.7 Common2RMW操作
5.8 compareAndSet（）操作
5.9 本章注釋
5.10 題
第6章 一致性的通用性
6.1 引言
6.2 通用性
6.3 一種通用的無(wú)鎖構(gòu)造
6.4 一種通用的無(wú)等待構(gòu)造
6.5 本章注釋
6.6 習(xí)題
第二部分 實(shí)踐
第7章 自旋鎖與爭(zhēng)用
7.1 實(shí)際問(wèn)題
7.2 測(cè)試-設(shè)置鎖
7.3 再論基于TAS的自旋鎖
7.4 指數(shù)后退
7.5 隊(duì)列鎖
7.5.1 基于數(shù)組的鎖
7.5.2 CLH隊(duì)列鎖
7.5.3 MCS隊(duì)列鎖
7.6 時(shí)限隊(duì)列鎖
7.7 復(fù)合鎖
7.8 層次鎖
7.8.1 層次后退鎖
7.8.2 層次CLH隊(duì)列鎖
7.9 由一個(gè)鎖管理所有的鎖
7.10 本章注釋
7.11 習(xí)題
第8章 管程和阻塞同步
8.1 引言
8.2 管程鎖和條件
8.2.1 條件
8.2.2 喚醒丟失問(wèn)題
8.3 讀者-寫者鎖
8.3.1 簡(jiǎn)單的讀者-寫者鎖
8.3.2 公平的讀者-寫者鎖
8.4 我們的可重入鎖
8.5 信號(hào)量
8.6 本章注釋
8.7 習(xí)題
第9章 鏈表：鎖的作用
9.1 引言
9.2 基于鏈表的集合
9.3 并發(fā)推理
9.4 粗粒度同步
9.5 細(xì)粒度同步
9.6 樂(lè)觀同步
9.7 惰性同步
9.8 非阻塞同步
9.9 討論
9.10 本章注釋
9.11 習(xí)題
第10章 并行隊(duì)列和ABA問(wèn)題
10.1 引言
10.2 隊(duì)列
10.3 部分有界隊(duì)列
10.4 完全無(wú)界隊(duì)列
10.5 無(wú)鎖的無(wú)界隊(duì)列
10.6 內(nèi)存回收和ABA問(wèn)題
10.7 雙重?cái)?shù)據(jù)結(jié)構(gòu)
10.8 本章注釋
10.9 習(xí)題
第11章 并發(fā)棧和消除
11.1 引言
11.2 無(wú)鎖的無(wú)界棧
11.3 消除
11.4 后退消除棧
11.4.1 無(wú)鎖交換機(jī)
11.4.2 消除數(shù)組
11.5 本章注釋
11.6 習(xí)題
第12章 計(jì)數(shù)、排序和分布式協(xié)作
12.1 引言
12.2 共享計(jì)數(shù)
12.3 軟件組合
12.3.1 概述
12.3.2 一個(gè)擴(kuò)展實(shí)例
12.3.3 性能和健壯性
12.4 靜態(tài)一致池和計(jì)數(shù)器
12.5 計(jì)數(shù)網(wǎng)
12.5.1 可計(jì)數(shù)網(wǎng)
12.5.2 雙調(diào)計(jì)數(shù)網(wǎng)
12.5.3 性能和流水線
12.6 衍射樹
12.7 并行排序
12.8 排序網(wǎng)
12.9 樣本排序
12.10 分布式協(xié)作
12.11 本章注釋
12.12 習(xí)題
第13章 并發(fā)哈希和固有并行
13.1 引言
13.2 封閉地址哈希集
13.2.1 粗粒度哈希集
13.2.2 空間分帶哈希集
13.2.3 細(xì)粒度哈希集
13.3 無(wú)鎖哈希集
13.3.1 遞歸有序劃分
13.3.2 BucketList類
13.3.3 LockFreeHashSet類
13.4 開放地址哈希集
13.4.1 Cuckoo哈希
13.4.2 并發(fā)Cuckoo哈希
13.4.3 空間分帶的并發(fā)Cuckoo哈希
13.4.4 細(xì)粒度的并發(fā)Cuckoo哈希集
13.5 本章注釋
13.6 習(xí)題
第14章 跳表和平衡查找
14.1 引言
14.2 順序跳表
14.3 基于鎖的并發(fā)跳表
14.3.1 簡(jiǎn)介
14.3.2 算法
14.4 無(wú)鎖并發(fā)跳表
14.4.1 簡(jiǎn)介
14.4.2 算法細(xì)節(jié)
14.5 并發(fā)跳表
14.6 本章注釋
14.7 習(xí)題
第15章 優(yōu)先級(jí)隊(duì)列
15.1 引言
15.2 基于數(shù)組的有界優(yōu)先級(jí)隊(duì)列
15.3 基于樹的有界優(yōu)先級(jí)隊(duì)列
15.4 基于堆的無(wú)界優(yōu)先級(jí)隊(duì)列
15.4.1 順序堆
15.4.2 并發(fā)堆
15.5 基于跳表的無(wú)界優(yōu)先級(jí)隊(duì)列
15.6 本章注釋
15.7 習(xí)題
第16章 異步執(zhí)行、調(diào)度和工作分配
16.1 引言
16.2 并行分析
16.3 多處理器的實(shí)際調(diào)度
16.4 工作分配
16.4.1 工作竊取
16.4.2 屈從和多道程序設(shè)計(jì)
16.5 工作竊取雙端隊(duì)列
16.5.1 有界工作竊取雙端隊(duì)列
16.5.2 無(wú)界工作竊取雙端隊(duì)列
16.5.3 工作平衡
16.6 本章注釋
16.7 習(xí)題
第17章 障礙
17.1 引言
17.2 障礙實(shí)現(xiàn)
17.3 語(yǔ)義換向障礙
17.4 組合樹障礙
17.5 靜態(tài)樹障礙
17.6 終止檢測(cè)障礙
17.7 本章注釋
17.8 習(xí)題
第18章 事務(wù)內(nèi)存
18.1 引言
18.1.1 關(guān)于鎖的問(wèn)題
18.1.2 關(guān)于compareAndSet（）的問(wèn)題
18.1.3 關(guān)于復(fù)合性的問(wèn)題
18.1.4 我們能做什么
18.2 事務(wù)和原子性
18.3 軟事務(wù)內(nèi)存
18.3.1 事務(wù)和事務(wù)線程
18.3.2 僵尸事務(wù)和一致性
18.3.3 原子對(duì)象
18.3.4 如何演進(jìn)
18.3.5 爭(zhēng)用管理器
18.3.6 原子對(duì)象的實(shí)現(xiàn)
18.3.7 無(wú)干擾原子對(duì)象
18.3.8 基于鎖的原子對(duì)象
18.4 硬事務(wù)內(nèi)存
18.4.1 緩存一致性
18.4.2 事務(wù)緩存一致性
18.4.3 改進(jìn)
18.5 本章注釋
18.6 習(xí)題
第三部分 附錄
附錄A 軟件基礎(chǔ)
附錄B 硬件基礎(chǔ)
參考文獻(xiàn)
索引