操作系统导论

第1章 关于本书的对话 1

第2章 操作系统介绍 3

2.1 虚拟化CPU 4

2.2 虚拟化内存 6

2.3 并发 7

2.4 持久性 9

2.5 设计目标 11

2.6 简单历史 12

2.7 小结 15

参考资料 15

第1部分 虚拟化

第3章 关于虚拟化的对话 18

第4章 抽象：进程 19

4.1 抽象：进程 20

4.2 进程API 20

4.3 进程创建：更多细节 21

4.4 进程状态 22

4.5 数据结构 24

4.6 小结 25

参考资料 25

作业 26

问题 26

第5章 插叙：进程API 28

5.1 fork()系统调用 28

5.2 wait()系统调用 29

5.3 最后是exec()系统调用 30

5.4 为什么这样设计API 32

5.5 其他API 34

5.6 小结 34

参考资料 34

作业（编码） 35

问题 35

第6章 机制：受限直接执行 37

6.1 基本技巧：受限直接执行 37

6.2 问题1：受限制的操作 38

6.3 问题2：在进程之间切换 40

6.4 担心并发吗 44

6.5 小结 45

参考资料 45

作业（测量） 47

第7章 进程调度：介绍 48

7.1 工作负载假设 48

7.2 调度指标 49

7.3 先进先出（FIFO） 49

7.4 最短任务优先（SJF） 50

7.5 最短完成时间优先（STCF） 51

7.6 新度量指标：响应时间 52

7.7 轮转 52

7.8 结合I/O 54

7.9 无法预知 54

7.10 小结 55

参考资料 55

作业 56

问题 56

第8章 调度：多级反馈队列 57

8.1 MLFQ：基本规则 57

8.2 尝试 #1：如何改变优先级 58

8.3 尝试 #2：提升优先级 60

8.4 尝试 #3：更好的计时方式 61

8.5 MLFQ调优及其他问题 61

8.6 MLFQ：小结 62

参考资料 63

作业 64

问题 64

第9章 调度：比例份额 65

9.1 基本概念：彩票数表示份额 65

9.2 彩票机制 66

9.3 实现 67

9.4 一个例子 68

9.5 如何分配彩票 68

9.6 为什么不是确定的 69

9.7 小结 70

参考资料 70

作业 71

问题 71

第10章 多处理器调度（高级） 73

10.1 背景：多处理器架构 73

10.2 别忘了同步 75

10.3 最后一个问题：缓存亲和度 76

10.4 单队列调度 76

10.5 多队列调度 77

10.6 Linux 多处理器调度 79

10.7 小结 79

参考资料 79

第11章 关于CPU虚拟化的总结对话 81

第12章 关于内存虚拟化的对话 83

第13章 抽象：地址空间 85

13.1 早期系统 85

13.2 多道程序和时分共享 85

13.3 地址空间 86

13.4 目标 87

13.5 小结 89

参考资料 89

第14章 插叙：内存操作API 91

14.1 内存类型 91

14.2 malloc()调用 92

14.3 free()调用 93

14.4 常见错误 93

14.5 底层操作系统支持 96

14.6 其他调用 97

14.7 小结 97

参考资料 97

作业（编码） 98

问题 98

第15章 机制：地址转换 100

15.1 假设 101

15.2 一个例子 101

15.3 动态（基于硬件）重定位 103

15.4 硬件支持：总结 105

15.5 操作系统的问题 105

15.6 小结 108

参考资料 109

作业 110

问题 110

第16章 分段 111

16.1 分段：泛化的基址/界限 111

16.2 我们引用哪个段 113

16.3 栈怎么办 114

16.4 支持共享 114

16.5 细粒度与粗粒度的分段 115

16.6 操作系统支持 115

16.7 小结 117

参考资料 117

作业 118

问题 119

第17章 空闲空间管理 120

17.1 假设 120

17.2 底层机制 121

17.3 基本策略 126

17.4 其他方式 128

17.5 小结 130

参考资料 130

作业 131

问题 131

第18章 分页：介绍 132

18.1 一个简单例子 132

18.2 页表存在哪里 134

18.3 列表中究竟有什么 135

18.4 分页：也很慢 136

18.5 内存追踪 137

18.6 小结 139

参考资料 139

作业 140

问题 140

第19章 分页：快速地址转换（TLB） 142

19.1 TLB的基本算法 142

19.2 示例：访问数组 143

19.3 谁来处理TLB未命中 145

19.4 TLB的内容 146

19.5 上下文切换时对TLB的处理 147

19.6 TLB替换策略 149

19.7 实际系统的TLB表项 149

19.8 小结 150

参考资料 151

作业（测量） 152

问题 153

第20章 分页：较小的表 154

20.1 简单的解决方案：更大的页 154

20.2 混合方法：分页和分段 155

20.3 多级页表 157

20.4 反向页表 162

20.5 将页表交换到磁盘 163

20.6 小结 163

参考资料 163

作业 164

问题 164

第21章 超越物理内存：机制 165

21.1 交换空间 165

21.2 存在位 166

21.3 页错误 167

21.4 内存满了怎么办 168

21.5 页错误处理流程 168

21.6 交换何时真正发生 169

21.7 小结 170

参考资料 171

第22章 超越物理内存：策略 172

22.1 缓存管理 172

22.2 最优替换策略 173

22.3 简单策略：FIFO 175

22.4 另一简单策略：随机 176

22.5 利用历史数据：LRU 177

22.6 工作负载示例 178

22.7 实现基于历史信息的算法 180

22.8 近似LRU 181

22.9 考虑脏页 182

22.10 其他虚拟内存策略 182

22.11 抖动 183

22.12 小结 183

参考资料 183

作业 185

问题 185

第23章 VAX/VMS虚拟内存系统 186

23.1 背景 186

23.2 内存管理硬件 186

23.3 一个真实的地址空间 187

23.4 页替换 189

23.5 其他漂亮的虚拟内存技巧 190

23.6 小结 191

参考资料 191

第24章 内存虚拟化总结对话 193

第2部分 并发

第25章 关于并发的对话 196

第26章 并发：介绍 198

26.1 实例：线程创建 199

26.2 为什么更糟糕：共享数据 201

26.3 核心问题：不可控的调度 203

26.4 原子性愿望 205

26.5 还有一个问题：等待另一个

线程 206

26.6 小结：为什么操作系统课要研究

并发 207

参考资料 207

作业 208

问题 208

第27章 插叙：线程API 210

27.1 线程创建 210

27.2 线程完成 211

27.3 锁 214

27.4 条件变量 215

27.5 编译和运行 217

27.6 小结 217

参考资料 218

第28章 锁 219

28.1 锁的基本思想 219

28.2 Pthread锁 220

28.3 实现一个锁 220

28.4 评价锁 220

28.5 控制中断 221

28.6 测试并设置指令（原子交换） 222

28.7 实现可用的自旋锁 223

28.8 评价自旋锁 225

28.9 比较并交换 225

28.10 链接的加载和条件式存储指令 226

28.11 获取并增加 228

28.12 自旋过多：怎么办 229

28.13 简单方法：让出来吧，宝贝 229

28.14 使用队列：休眠替代自旋 230

28.15 不同操作系统，不同实现 232

28.16 两阶段锁 233

28.17 小结 233

参考资料 233

作业 235

问题 235

第29章 基于锁的并发数据结构 237

29.1 并发计数器 237

29.2 并发链表 241

29.3 并发队列 244

29.4 并发散列表 245

29.5 小结 246

参考资料 247

第30章 条件变量 249

30.1 定义和程序 250

30.2 生产者/消费者（有界缓冲区）

问题 252

30.3 覆盖条件 260

30.4 小结 261

参考资料 261

第31章 信号量 263

31.1 信号量的定义 263

31.2 二值信号量（锁） 264

31.3 信号量用作条件变量 266

31.4 生产者/消费者（有界缓冲区）

问题 268

31.5 读者—写者锁 271

31.6 哲学家就餐问题 273

31.7 如何实现信号量 275

31.8 小结 276

参考资料 276

第32章 常见并发问题 279

32.1 有哪些类型的缺陷 279

32.2 非死锁缺陷 280

32.3 死锁缺陷 282

32.4 小结 288

参考资料 289

第33章 基于事件的并发（进阶） 291

33.1 基本想法：事件循环 291

33.2 重要API：select()（或poll()） 292

33.3 使用select() 293

33.4 为何更简单？无须锁 294

33.5 一个问题：阻塞系统调用 294

33.6 解决方案：异步I/O 294

33.7 另一个问题：状态管理 296

33.8 什么事情仍然很难 297

33.9 小结 298

参考资料 298

第34章 并发的总结对话 300

第3部分 持久性

第35章 关于持久性的对话 302

第36章 I/O设备 303

36.1 系统架构 303

36.2 标准设备 304

36.3 标准协议 304

36.4 利用中断减少CPU开销 305

36.5 利用DMA进行更高效的数据

传送 306

36.6 设备交互的方法 307

36.7 纳入操作系统：设备驱动程序 307

36.8 案例研究：简单的IDE磁盘驱动

程序 309

36.9 历史记录 311

36.10 小结 311

参考资料 312

第37章 磁盘驱动器 314

37.1 接口 314

37.2 基本几何形状 314

37.3 简单的磁盘驱动器 315

37.4 I/O时间：用数学 318

37.5 磁盘调度 320

37.6 小结 323

参考资料 323

作业 324

问题 324

第38章 廉价冗余磁盘阵列（RAID） 326

38.1 接口和RAID内部 327

38.2 故障模型 327

38.3 如何评估RAID 328

38.4 RAID 0级：条带化 328

38.5 RAID 1级：镜像 331

38.6 RAID 4级：通过奇偶校验节省

空间 333

38.7 RAID 5级：旋转奇偶校验 336

38.8 RAID比较：总结 337

38.9 其他有趣的RAID问题 338

38.10 小结 338

参考资料 339

作业 340

问题 340

第39章 插叙：文件和目录 342

39.1 文件和目录 342

39.2 文件系统接口 343

39.3 创建文件 343

39.4 读写文件 344

39.5 读取和写入，但不按顺序 346

39.6 用fsync()立即写入 346

39.7 文件重命名 347

39.8 获取文件信息 348

39.9 删除文件 349

39.10 创建目录 349

39.11 读取目录 350

39.12 删除目录 351

39.13 硬链接 351

39.14 符号链接 353

39.15 创建并挂载文件系统 354

39.16 总结 355

参考资料 355

作业 356

问题 356

第40章 文件系统实现 357

40.1 思考方式 357

40.2 整体组织 358

40.3 文件组织：inode 359

40.4 目录组织 363

40.5 空闲空间管理 364

40.6 访问路径：读取和写入 364

40.7 缓存和缓冲 367

40.8 小结 369

参考资料 369

作业 370

问题 371

第41章 局部性和快速文件系统 372

41.1 问题：性能不佳 372

41.2 FFS：磁盘意识是解决方案 373

41.3 组织结构：柱面组 373

41.4 策略：如何分配文件和目录 374

41.5 测量文件的局部性 375

41.6 大文件例外 376

41.7 关于FFS的其他几件事 377

41.8 小结 378

参考资料 378

第42章 崩溃一致性：FSCK和日志 380

42.1 一个详细的例子 380

42.2 解决方案＃1：文件系统检查

程序 383

42.3 解决方案＃2：日志

（或预写日志） 384

42.4 解决方案＃3：其他方法 392

42.5 小结 393

参考资料 393

第43章 日志结构文件系统 395

43.1 按顺序写入磁盘 396

43.2 顺序而高效地写入 396

43.3 要缓冲多少 397

43.4 问题：查找inode 398

43.5 通过间接解决方案：inode映射 398

43.6 检查点区域 399

43.7 从磁盘读取文件：回顾 400

43.8 目录如何 400

43.9 一个新问题：垃圾收集 401

43.10 确定块的死活 402

43.11 策略问题：要清理哪些块，

何时清理 403

43.12 崩溃恢复和日志 403

43.13 小结 404

参考资料 404

第44章 数据完整性和保护 407

44.1 磁盘故障模式 407

44.2 处理潜在的扇区错误 409

44.3 检测讹误：校验和 409

44.4 使用校验和 412

44.5 一个新问题：错误的写入 412

44.6 最后一个问题：丢失的写入 413

44.7 擦净 413

44.8 校验和的开销 414

44.9 小结 414

参考资料 414

第45章 关于持久的总结对话 417

第46章 关于分布式的对话 418

第47章 分布式系统 419

47.1 通信基础 420

47.2 不可靠的通信层 420

47.3 可靠的通信层 422

47.4 通信抽象 424

47.5 远程过程调用（RPC） 425

47.6 小结 428

参考资料 429

第48章 Sun的网络文件系统（NFS） 430

48.1 基本分布式文件系统 430

48.2 交出NFS 431

48.3 关注点：简单快速的服务器崩溃

恢复 431

48.4 快速崩溃恢复的关键：无状态 432

48.5 NFSv2协议 433

48.6 从协议到分布式文件系统 434

48.7 利用幂等操作处理服务器故障 435

48.8 提高性能：客户端缓存 437

48.9 缓存一致性问题 437

48.10 评估NFS的缓存一致性 439

48.11 服务器端写缓冲的隐含意义 439

48.12 小结 440

参考资料 440

第49章 Andrew文件系统（AFS） 442

49.1 AFS版本1 442

49.2 版本1的问题 443

49.3 改进协议 444

49.4 AFS版本2 444

49.5 缓存一致性 446

49.6 崩溃恢复 447

49.7 AFSv2的扩展性和性能 448

49.8 AFS：其他改进 450

49.9 小结 450

参考资料 451

作业 452

问题 452

第50章 关于分布式的总结对话 453

附录A 关于虚拟机监视器的对话 454

附录B 虚拟机监视器 455

附录C 关于监视器的对话 466

附录D 关于实验室的对话 467

附录E 实验室：指南 468

附录F 实验室：系统项目 478

附录G 实验室：xv6项目 480

......(更多)