深入解析計算機系統

蘇珊娜·J. 馬修斯，西點軍校計算機科學副教授。

蒂亞·紐霍爾，斯沃斯莫爾學院計算機科學教授。

凱文·C. 韋布，斯沃斯莫爾學院計算機科學副教授。

第 1 章 靠近 C，靠近 C，靠近美麗的 C　　1

1.1 開始使用 C 編程　　2

　1.1.1 編譯和運行 C 程序　　4

　1.1.2 C 類型　　6

1.2 輸入和輸出（函數 printf 和 scanf）　　9

　1.2.1 printf 函數　　9

　1.2.2 scanf 函數　　11

1.3 條件和循環　　13

　1.3.1 C 中的布爾值　　15

　1.3.2 C 中的循環　　16

1.4 函數　　20

1.5 數組和字符串　　25

　1.5.1 數組介紹　　25

　1.5.2 數組訪問方法　　27

　1.5.3 數組和函數　　28

　1.5.4 C 字符串和字符串庫介紹　　30

1.6 結構體　　31

　1.6.1 定義結構體類型　　32

　1.6.2 聲明結構體類型的變量　　32

　1.6.3 訪問字段值　　33

　1.6.4 向函數傳遞結構體　　36

1.7 總結　　39

第 2 章 深入理解 C 語言　　40

2.1 程序內存的組成部分和作用域　　40

2.2 C 指針變量　　43

2.3 指針與函數　　46

2.4 動態內存分配　　48

　2.4.1 堆內存　　48

　2.4.2 函數 malloc 和 free　　49

　2.4.3 動態分配數組和字符串　　50

　2.4.4 指向堆內存和函數的指針　　52

2.5 C 中的數組　　53

　2.5.1 一維數組　　53

　2.5.2 二維數組　　56

2.6 C 字符串和字符串庫　　62

　2.6.1 C 語言對靜態分配字符串（char 數組）的支持　　62

　2.6.2 動態分配字符串　　63

　2.6.3 用於操作 C 字符串和字符的庫　　64

2.7 C 結構體　　71

　2.7.1 復習 C 結構體類型　　71

　2.7.2 指針和結構體　　73

　2.7.3 結構體中的指針字段　　74

　2.7.4 結構體數組　　76

　2.7.5 自引用結構體　　77

2.8 C 中的 I/O（標準 I/O 和文件 I/O）　　79

　2.8.1 標準 I/O　　79

　2.8.2 文件 I/O　　83

　2.8.3 在 C 程序中使用文本文件　　83

　2.8.4 stdio.h 中的標準 I/O 和文件 I/O 函數　　84

2.9 C 語言的一些高級特性　　87

　2.9.1 switch 語句　　87

　2.9.2 命令行參數　　89

　2.9.3 void *類型及類型轉換　　90

　2.9.4 指針運算　　91

　2.9.5 C 庫的使用、編譯和鏈接　　95

　2.9.6 編寫和使用自己的 C 庫　　100

　2.9.7 編譯 C 源文件為匯編代碼，以及編譯並鏈接匯編代碼　　104

2.10 總結　　107

第 3 章 C 調試工具　　108

3.1 使用 GDB 調試程序　　108

　3.1.1 GDB 入門　　109

　3.1.2 GDB 會話示例　　110

3.2 GDB 命令詳情　　118

　3.2.1 GDB 常用快捷鍵　　118

　3.2.2 常用 GDB 命令　　118

3.3 利用 Valgrind 調試內存　　124

　3.3.1 堆內存訪問錯誤示例　　125

　3.3.2 如何使用 Memcheck 調試工具　　127

3.4 GDB 高級功能　　129

　3.4.1 GDB 和 make 命令　　129

　3.4.2 將 GDB 附加到正在運行的進程　　129

　3.4.3 跟蹤分叉進程　　130

　3.4.4 信號控制　　131

　3.4.5 DDD 設置和 bug 修復　　131

3.5 調試匯編代碼　　131

　3.5.1 使用 GDB 檢查二進制代碼　　132

　3.5.2 在匯編代碼級別使用 DDD 進行調試　　133

　3.5.3 GDB 匯編代碼調試命令和示例　　134

　3.5.4 匯編調試常用命令快速摘要　　135

3.6 使用 GDB 調試多線程程序　　135

　3.6.1 GDB 和線程　　136

　3.6.2 GDB 線程特定命令　　136

　3.6.3 示例　　137

3.7 總結　　139

第 4 章 二進制與數據表示法　　140

4.1 基數和無符號數　　142

　4.1.1 十進制數　　142

　4.1.2 無符號二進制數　　143

　4.1.3 十六進制　　144

　4.1.4 存儲限制　　145

4.2 數制轉換　　146

　4.2.1 二進制和十六進制之間的轉換　　146

　4.2.2 轉換為十進制　　147

　4.2.3 從十進制轉換　　147

4.3 有符號二進制數　　149

　4.3.1 原碼　　149

　4.3.2 補碼　　150

4.4 二進制算術運算　　153

　4.4.1 加法　　153

　4.4.2 減法　　155

　4.4.3 乘法和除法　　155

4.5 溢出　　156

　4.5.1 用裏程表作類比　　156

　4.5.2 二進制溢出　　157

　4.5.3 溢出總結　　160

　4.5.4 溢出後果　　160

4.6 位運算符　　161

　4.6.1 按位與（AND）　　161

　4.6.2 按位或（OR）　　162

　4.6.3 按位異或（XOR）　　163

　4.6.4 按位非（NOT）　　163

　4.6.5 移位　　164

4.7 整數字節序　　165

4.8 二進制中的實數　　167

　4.8.1 定點數表示法　　167

　4.8.2 浮點數表示法　　168

　4.8.3 舍入結果　　169

4.9 總結　　169

第 5 章 馮 諾依曼計算機體系結構　　171

5.1 現代計算機體系結構的起源　　172

　5.1.1 圖靈機　　173

　5.1.2 早期電子計算機　　173

　5.1.3 馮·諾依曼知道些什麼　　175

5.2 馮 諾依曼體系結構　　175

　5.2.1 CPU　　176

　5.2.2 運算器　　176

　5.2.3 控制器　　176

　5.2.4 存儲器　　176

　5.2.5 輸入/輸出（I/O）設備　　177

　5.2.6 馮·諾依曼計算機的運行：執行程序　　177

5.3 邏輯門　　179

　5.3.1 基礎邏輯門　　179

　5.3.2 其他邏輯門　　180

5.4 電路　　181

　5.4.1 算術/邏輯電路　　182

　5.4.2 控制電路　　186

　5.4.3 存儲電路　　190

　5.4.4 RS 鎖存器　　190

5.5 構建處理器：將它們放在一起　　193

　5.5.1 ALU　　193

　5.5.2 寄存器堆　　195

　5.5.3 CPU　　196

5.6 處理器執行程序指令　　197

　5.6.1 時鐘驅動程序指令的執行　　200

　5.6.2 將它們放在一起：完整計算機中的 CPU　　201

5.7 流水線：讓 CPU 更快　　202

5.8 高級流水線指令註意事項　　204

　5.8.1 流水線註意事項：數據冒險　　204

　5.8.2 流水線冒險：控制冒險　　205

5.9 展望未來：現代 CPU 技術　　207

　5.9.1 指令級並行　　207

　5.9.2 多核和硬件多線程　　208

　5.9.3 一些處理器示例　　210

5.10 總結　　210

第 6 章 C 語言底層：深入理解匯編　　212

6.1 學習匯編的好處　　212

6.2 你將在接下來的章節中學到什麼　　214

第 7 章 64 位 x86（x86-64）匯編　　215

7.1 x86-64 匯編基礎知識　　216

　7.1.1 寄存器　　217

　7.1.2 高級寄存器符號　　217

　7.1.3 指令結構　　218

　7.1.4 操作數示例　　219

　7.1.5 指令後綴　　220

7.2 常見指令　　220

7.3 算術指令　　226

　7.3.1 移位指令　　226

　7.3.2 位指令　　227

　7.3.3 加載有效地址指令　　228

7.4 條件和循環　　228

　7.4.1 預備知識　　228

　7.4.2 匯編中的 if 語句　　232

　7.4.3 匯編中的循環語句　　237

7.5 匯編中的函數　　242

　7.5.1 函數參數　　243

　7.5.2 通過示例進行追蹤　　243

　7.5.3 通過 main 函數進行追蹤　　245

7.6 遞歸函數　　257

7.7 數組　　259

7.8 矩陣　　261

　7.8.1 連續二維數組　　262

　7.8.2 非連續矩陣　　264

7.9 匯編中的結構體　　267

7.10 真實世界：緩存區溢出　　270

　7.10.1 緩存區溢出經典案例　　270

　7.10.2 初步探索：猜謎遊戲　　271

　7.10.3 進一步了解（在C 環境下）　　272

　7.10.4 緩存區溢出：首次嘗試　　275

　7.10.5 更聰明的緩存區溢出：再次嘗試　　276

　7.10.6 緩存區溢出防禦　　278

第 8 章 32 位 x86（IA32）匯編　　281

8.1 IA32 匯編基礎知識　　282

　8.1.1 寄存器　　283

　8.1.2 高級寄存器符號　　283

　8.1.3 指令結構　　284

　8.1.4 操作數示例　　284

　8.1.5 指令後綴　　285

8.2 常見指令　　286

8.3 算術指令　　291

　8.3.1 移位指令　　291

　8.3.2 位指令　　292

　8.3.3 加載有效地址指令　　292

8.4 條件和循環　　293

　8.4.1 預備知識　　293

　8.4.2 匯編中的 if 語句　　296

　8.4.3 匯編中的循環語句　　301

8.5 匯編中的函數　　305

　8.5.1 通過示例進行追蹤　　307

　8.5.2 通過 main 函數進行追蹤　　308

8.6 遞歸函數　　322

8.7 數組　　323

8.8 矩陣　　326

　8.8.1 連續二維數組　　327

　8.8.2 非連續矩陣　　328

8.9 匯編中的結構體　　331

8.10 真實世界：緩存區溢出　　334

　8.10.1 緩存區溢出經典案例　　334

　8.10.2 初步探索：猜謎遊戲　　334

　8.10.3 進一步了解（在C 環境下）　　336

　8.10.4 緩存區溢出：首次嘗試　　338

　8.10.5 更聰明的緩存區溢出：再次嘗試　　340

　8.10.6 緩存區溢出防禦　　341

第 9 章 ARM 匯編　　345

9.1 ARM 匯編基礎知識　　346

　9.1.1 寄存器　　347

　9.1.2 高級寄存器符號　　347

　9.1.3 指令結構　　348

　9.1.4 操作數示例　　348

9.2 常見指令　　349

9.3 算術指令　　354

　9.3.1 移位指令　　355

　9.3.2 位指令　　356

9.4 條件和循環　　356

　9.4.1 預備知識　　356

　9.4.2 匯編中的 if 語句　　360

　9.4.3 匯編中的循環語句　　365

9.5 匯編中的函數　　370

　9.5.1 函數參數　　372

　9.5.2 通過示例進行追蹤　　372

　9.5.3 通過 main 函數進行追蹤　　373

9.6 遞歸函數　　385

9.7 數組　　387

9.8 矩陣　　390

　9.8.1 連續二維數組　　391

　9.8.2 非連續矩陣　　393

9.9 匯編中的結構體　　395

9.10 真實世界：緩存區溢出　　398

　9.10.1 緩存區溢出經典案例　　399

　9.10.2 初步探索：猜謎遊戲　　399

　9.10.3 進一步了解（在C 環境下）　　400

　9.10.4 緩存區溢出：首次嘗試　　403

　9.10.5 更聰明的緩存區溢出：再次嘗試　　404

　9.10.6 緩存區溢出防禦　　406

第 10 章 匯編要點　　409

10.1 共同特點　　409

10.2 進一步閱讀　　410

第 11 章 存儲和內存層次結構　　411

11.1 內存層次結構　　412

11.2 存儲設備　　413

　11.2.1 主存儲設備　　414

　11.2.2 輔助存儲設備　　415

11.3 局部性　　417

　11.3.1 代碼中的局部性示例　　418

　11.3.2 從局部性到緩存　　419

　11.3.3 時間局部性　　420

　11.3.4 空間局部性　　421

11.4 CPU 緩存　　421

　11.4.1 直接映射緩存　　422

　11.4.2 緩存未命中和關聯設計　　429

　11.4.3 集合關聯緩存　　430

11.5 緩存分析和 Valgrind　　434

　11.5.1 理論分析和基準測試　　436

　11.5.2 現實世界中的緩存分析：Cachegrind　　437

11.6 展望未來：多核處理器上的緩存　　439

　11.6.1 緩存一致性　　441

　11.6.2 MSI 協議　　441

　11.6.3 實現緩存一致性協議　　443

　11.6.4 有關多核緩存的更多信息　　443

11.7 總結　　444

第 12 章 代碼優化　　445

12.1 優化之前：了解編譯器　　445

　12.1.1 編譯器已經做了什麼　　445

　12.1.2 編譯器無法始終完成的任務：學習代碼優化的好處　　447

　12.1.3 與編譯器合作：一個示例程序　　450

12.2 代碼優化第 一步：代碼分析　　451

　12.2.1 使用Callgrind 進行性能分析　　453

　12.2.2 循環不變代碼移動　　455

12.3 其他編譯器優化技術：循環展開和函數內聯　　457

　12.3.1 函數內聯　　457

　12.3.2 循環展開　　458

12.4 內存註意事項　　460

　12.4.1 循環交換　　460

　12.4.2 用於改進局部性的其他一些編譯器優化技術：循環裂變和融合　　461

　12.4.3 使用 Massif 進行內存分析　　463

12.5 總結　　465

第 13 章 操作系統　　467

13.1 操作系統的工作原理及運行方式　　468

　13.1.1 操作系統的引導過程　　469

　13.1.2 讓操作系統執行任務：中斷和陷阱　　469

13.2 進程　　472

　13.2.1 多道程序設計和上下文切換　　472

　13.2.2 進程狀態　　473

　13.2.3 創建（和銷毀）進程　　475

　13.2.4 退出和等待　　480

13.3 虛擬內存　　482

　13.3.1 內存地址　　484

　13.3.2 虛擬地址到物理地址的轉換　　485

　13.3.3 分頁　　486

　13.3.4 內存效率　　492

13.4 進程間通信　　494

　13.4.1 信號　　495

　13.4.2 消息傳遞　　499

　13.4.3 共享內存　　500

13.5 總結　　501

第 14 章 在多核時代利用共享內存　　503

14.1 編程多核系統　　505

　14.1.1 多核系統對進程執行的影響　　505

　14.1.2 使用線程加速進程執行　　506

14.2 編寫你的第 一個多線程程序　　508

　14.2.1 創建和加入線程　　509

　14.2.2 線程函數　　511

　14.2.3 運行代碼　　511

　14.2.4 重新審視標量乘法　　512

　14.2.5 改進標量乘法：傳遞多個參數　　514

14.3 線程同步　　515

　14.3.1 互斥　　521

　14.3.2 信號量　　528

　14.3.3 其他同步機制　　529

14.4 並行程序的性能測量　　534

　14.4.1 並行程序性能測量基礎　　534

　14.4.2 並行程序性能測量進階　　537

14.5 緩存一致性和虛假共享　　538

　14.5.1 多核系統中的緩存　　539

　14.5.2 虛假共享　　540

　14.5.3 解決虛假共享　　542

14.6 線程安全　　543

14.7 OpenMP 中的隱式線程　　547

　14.7.1 常用編譯指示　　548

　14.7.2 為 OpenMP 增添趣味　　548

　14.7.3 一個更復雜的示例：OpenMP 中的 CountSort 算法　　550

　14.7.4 了解更多關於 OpenMP 的知識　　552

14.8 總結　　552

第 15 章 展望：其他並行系統和並行編程模型　　554

15.1 異構計算：硬件加速器、GPGPU 計算和 CUDA　　555

　15.1.1 硬件加速器　　555

　15.1.2 GPU 體系結構簡介　　556

　15.1.3 GPGPU 計算　　557

　15.1.4 CUDA　　557

　15.1.5 其他 GPGPU 編程語言　　561

15.2 分布式內存系統、消息傳遞和MPI　　561

　15.2.1 並行和分布式處理模型　　563

　15.2.2 通信協議　　563

　15.2.3 消息傳遞接口　　564

　15.2.4 MPI Hello World　　564

　15.2.5 MPI 標量乘法　　566

　15.2.6 分布式內存系統面臨的挑戰　　572

15.3 邁向百億億次計算：雲計算、大數據和計算科學的未來　　572

　15.3.1 雲計算　　574

　15.3.2 MapReduce　　575

　15.3.3 展望未來：機遇與挑戰　　579