操作系统导论

这是一本关于现代操作系统的书。全书围绕虚拟化、并发和持久性这3个主要概念展开，介绍了所有现代系统的主要组件（包括调度、虚拟内存管理、磁盘和I/O子系统、文件系统 ）。
本书共50章，分为3个部分，分别讲述虚拟化、并发和持久性的相关内容。本书大部分章节均先提出特定的问题，然后通过书中介绍的技术、算法和思想来解决这些问题。笔者以对话形式引入所介绍的主题概念，行文诙谐幽默却又鞭辟入里，力求帮助读者理解操作系统中虚拟化、并发和持久性的原理。
本书内容全面，并给出了真实可运行的代码（而非伪代码），还提供了相应的练习，适合高等院校相关专业教师教学和高校学生自学。

雷姆兹·H.阿帕希杜塞尔（Remzi H.Arpaci-Dusseau）和安德莉亚·C.阿帕希杜塞尔
（Andrea C.Arpaci-Dusseau）夫妇是美国威斯康星大学计算机科学教授。二人都从事计算机操作系统方面的教学和研究。

本书围绕虚拟化、并发和持久性这三个主要概念展开，介绍了所有现代系统的主要组件（包括调度、虚拟内存管理、磁盘和I/O子系统、文件系统）。全书共50章，分为3个部分，分别讲述虚拟化、并发和持久性的相关内容。作者以对话形式引入所介绍的主题概念，行文诙谐幽默却又鞭辟入里，力求帮助读者理解操作系统中虚拟化、并发和持久性的原理。
本书内容全面，并给出了真实可运行的代码（而非伪代码），还提供了相应的练习，很适合高等院校相关专业的教师开展教学和高校学生进行自学。

本书具有以下特色：
● 主题突出，紧紧围绕操作系统的三大主题元素——虚拟化、并发和持久性。
● 以对话的方式引入背景，提出问题，进而阐释原理，启发动手实践。
● 包含众多“补充”和“提示”，拓展读者知识面，增加趣味性。
● 使用真实代码而不是伪代码，让读者更加深入透彻地了解操作系统。
● 提供作业、模拟和项目等众多学习方式，鼓励读者动手实践。
● 为教师提供教学辅助资源。

本书为教师提供如下教学辅助资源：
● 教学PPT和听课笔记。
● 考试题和参考答案。
● 讨论题和作业。
● 项目说明和指导。

如果您是教师，希望获得教学配套资源，请发邮件到[email protected]申请。

第 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