现代操作系统：原理与实现

　　本书以三个“面向”为导向，即面向经典基础理论与方法，面向国际前沿研究，面向工业界实践，深入浅出地介绍操作系统的理论、架构、设计方法与具体实现。本书是首本以ARM64为主体介绍操作系统的教材，将学术前沿与工业实践充分结合，不仅介绍了现有的Linux宏内核操作系统架构，而且介绍了微内核、外核等操作系统架构。 本书共分为三个部分，其中第一部分（操作系统基础）以纸质版的形式出版，第二部分（操作系统进阶）和第三部分（ChCore课程实验）则以电子版的形式在本书网站发布。第一部分共分为11章，内容包括：操作系统概述、硬件结构、操作系统结构、内存管理、进程与线程、操作系统调度、进程间通信、同步原语、文件系统与存储、设备管理和系统虚拟化。 本书包含大量插图、示例和练习，并融入了典型的操作系统相关的技术问题，既可以作为高等院校计算机专业本科生和研究生的操作系统课程教材，也可以作为工业界从事操作系统相关领域研发工作的专业人员的参考书。

　　陈海波 上海交通大学特聘教授、博导，并行与分布式系统研究所所长，领域操作系统教育部工程研究中心主任，国家杰出青年基金获得者，ACM杰出科学家，CCF杰出会员与杰出演讲者。主要研究领域为操作系统和系统安全。曾获教育部技术发明一等奖（第一完成人）、全国优秀博士学位论文奖、CCF青年科学家奖。目前担任ACM SIGOPS ChinaSys主席、CCF系统软件专委会副主任、ACM旗舰杂志Communications of the ACM中国首位编委与Special Sections领域共同主席、ACM Transactions on Storage编委。曾任ACM SOSP 2017年大会共同主席、ACM CCS 2018系统安全领域主席、ACM SIGSAC奖励委员会委员。研究工作还获得了华为最*个人贡献奖、金牌团队奖。按照csrankings.org的统计，其近5年（2015～2019）在操作系统领域高水平会议（SOSP/OSDI、EuroSys、USENIX ATC和FAST）上发表的论文数居世界第一。 夏虞斌 上海交通大学副教授、博导，CCF高级会员。主要研究领域为操作系统、体系结构和系统安全，曾任OSDI、EuroSys等多个国际会议的程序委员会委员。领导团队研发的安全操作系统T6获得2015年“挑战杯”全国大学生课外学术科技作品竞赛和中国大学生创业计划竞赛特等奖、2019年中国“互联网+”大学生创新创业大赛全国银奖，并已实现产业化，实际部署设备数量过亿；基于RISC-V平台研发的可信执行环境软硬件系统“蓬莱”现已开源。

目　　录
序言一
序言二
前言
第一部分　操作系统基础
第1章　操作系统概述 2
1.1　简约但不简单：从Hello World说起 2
1.2　什么是操作系统 3
1.3　操作系统简史 6
1.3.1　GM-NAA I/O：第一个（批处理）操作系统 6
1.3.2　OS/360：从专用走向通用 6
1.3.3　Multics/UNIX/Linux：分时与多任务 7
1.3.4　macOS/Windows：以人为本的人机交互 8
1.4　操作系统接口 9
1.5　ChCore：一个简单的实验操作系统 11
参考文献 12
第2章　硬件结构 13
2.1　CPU与指令集架构 14
2.1.1　指令集 14
2.1.2　特权级 15
2.1.3　寄存器 17
2.2　物理内存与CPU缓存 17
2.2.1　缓存结构 18
2.2.2　缓存寻址 19
2.3　设备与中断 20
2.3.1　内存映射输入输出 20
2.3.2　轮询与中断 21
2.4　思考题 22
参考文献 22
第3章　操作系统结构 23
3.1　操作系统的机制与策略 24
3.2　操作系统复杂度管理方法 25
3.3　操作系统内核架构 27
3.3.1　简要结构 27
3.3.2　宏内核架构 28
3.3.3　微内核架构 30
3.3.4　外核架构 32
3.3.5　其他操作系统内核架构 34
3.4　操作系统框架结构 35
3.4.1　Android系统框架 35
3.4.2　ROS系统框架 37
3.5　思考题 39
参考文献 40
第4章　内存管理 42
4.1　虚拟地址与物理地址 43
4.1.1　初识物理地址与虚拟地址 43
4.1.2　使用虚拟地址访问物理内存 44
4.1.3　分段与分页机制 44
4.2　基于分页的虚拟内存 46
4.2.1　AArch64架构下的4级页表 47
4.2.2　加速地址翻译的重要硬件：TLB 49
4.2.3　换页与缺页异常 52
4.2.4　页替换策略 54
4.2.5　工作集模型 57
4.3　虚拟内存功能 58
4.3.1　共享内存 58
4.3.2　写时拷贝 58
4.3.3　内存去重 60
4.3.4　内存压缩 60
4.3.5　大页 61
4.4　物理内存分配与管理 62
4.4.1　目标与评价维度 62
4.4.2　伙伴系统 63
4.4.3　SLAB分配器 65
4.4.4　常用的空闲链表 66
4.4.5　物理内存与CPU缓存 68
4.5　案例分析：ChCore内存管理机制 70
4.6　思考题 73
参考文献 74
第5章　进程与线程 76
5.1　进程 76
5.1.1　进程的状态 76
5.1.2　进程的内存空间布局 78
5.1.3　进程控制块和上下文切换 79
5.2　案例分析：Linux的进程操作 80
5.2.1　进程的创建：fork 80
5.2.2　进程的执行：exec 84
5.2.3　进程管理 85
5.2.4　讨论：fork过时了吗 89
5.3　线程 92
5.3.1　多线程的地址空间布局 93
5.3.2　用户态线程与内核态线程 93
5.3.3　线程控制块与线程本地存储 94
5.3.4　线程的基本接口：以POSIX线程库为例 95
5.4　案例分析：ChCore的线程上下文 99
5.4.1　线程的上下文和TCB 99
5.4.2　ChCore中上下文切换的实现 100
5.5　纤程 102
5.5.1　对纤程的需求：一个简单的例子 103
5.5.2　POSIX的纤程支持：ucontext 103
5.5.3　纤程的上下文切换 105
5.6　思考题 106
参考文献 107
第6章　操作系统调度 108
6.1　计算机调度简介 108
6.1.1　操作系统调度 110
6.1.2　调度指标 111
6.2　调度机制 113
6.2.1　长期、中期与短期调度 114
6.2.2　任务调度总览 116
6.3　单核调度策略 117
6.3.1　经典调度 118
6.3.2　优先级调度 122
6.3.3　公平共享调度 127
6.3.4　实时调度 133
6.3.5　其他调度 138
6.4　多核调度策略 141
6.4.1　负载分担 141
6.4.2　协同调度 142
6.4.3　两级调度 144
6.4.4　负载追踪与负载均衡 145
6.4.5　能耗感知调度 148
6.5　调度进阶机制 151
6.5.1　处理器亲和性 152
6.5.2　调度策略设置 153
6.6　案例分析：现代调度器 155
6.6.1　Linux调度器 155
6.6.2　macOS/iOS调度器 160
6.7　思考题 162
参考文献 163
第7章　进程间通信 165
7.1　进程间通信基础 165
7.1.1　一个简单的进程间通信设计 166
7.1.2　数据传递 167
7.1.3　控制流转移 169
7.1.4　单向和双向 170
7.1.5　同步和异步 170
7.1.6　超时机制 171
7.1.7　通信连接管理 172
7.1.8　权限检查 173
7.1.9　命名服务 174
7.2　宏内核进程间通信 175
7.2.1　管道进程间通信 175
7.2.2　System V消息队列 178
7.2.3　System V信号量 179
7.2.4　System V共享内存 180
7.2.5　信号进程间通信 181
7.2.6　套接字进程间通信 185
7.3　微内核进程间通信 186
7.3.1　Mach：早期的微内核进程间通信设计 186
7.3.2　L4：围绕进程间通信优化而设计的微内核系统 188
7.3.3　LRPC：迁移线程模型 193
7.4　案例分析：Android Binder 195
7.4.1　背景 195
7.4.2　Binder IPC总览 196
7.4.3　Binder IPC内核设计 196
7.4.4　匿名共享内存 199
7.5　案例分析：ChCore 进程间通信机制 201
7.6　思考题 203
参考文献 203
第8章　同步原语 206
8.1　互斥锁 209
8.1.1　临界区问题 209
8.1.2　硬件实现：关闭中断 211
8.1.3　软件实现：皮特森算法 211
8.1.4　软硬件协同：使用原子操作实现互斥锁 213
8.2　条件变量 219
8.2.1　条件变量的使用 219
8.2.2　条件变量的实现 222
8.3　信号量 223
8.3.1　信号量的使用 224
8.3.2　信号量的实现 225
8.4　读写锁 229
8.4.1　读写锁的使用 229
8.4.2　读写锁的实现 230
8.5　RCU 233
8.5.1　订阅/发布机制 234
8.5.2　宽限期 236
8.6　管程 237
8.7　同步带来的问题 239
8.7.1　死锁 239
8.7.2　活锁 245
8.7.3　优先级反转 246
8.8　案例分析：Linux中的futex 249
8.9　案例分析：ChCore中的同步原语 251
8.10　思考题 252
参考文献 254
第9章　文件系统 256
9.1　基于inode的文件系统 257
9.1.1　inode与文件 258
9.1.2　文件名与目录 260
9.1.3　硬链接与符号链接 263
9.1.4　存储布局 264
9.2　虚拟文件系统 266
9.2.1　面向文件系统的接口 266
9.2.2　面向应用程序的接口 270
9.2.3　页缓存、直接I/O与内存映射 277
9.2.4　多种文件系统的组织和管理 280
9.2.5　伪文件系统 282
9.3　其他文件系统 284
9.3.1　FAT文件系统 284
9.3.2　NTFS 288
9.3.3　FUSE与用户态文件系统 292
9.4　案例分析：ChCore文件系统 294
9.4.1　ChCore的文件系统架构 294
9.4.2　内存文件系统 295
9.5　思考题 296
参考文献 297
第10章　设备管理 299
10.1　计算机设备的连接和通信 300
10.1.1　设备的连接：总线 300
10.1.2　可编程I/O 301
10.1.3　高效数据传输：DMA 301
10.1.4　设备地址翻译：IOMMU 302
10.2　设备的识别 303
10.2.1　设备树 303
10.2.2　ACPI 304
10.3　设备的中断处理 305
10.3.1　中断控制器 305
10.3.2　中断的基本概念 306
10.3.3　中断处理：以Linux上下半部的机制为例 308
10.4　设备驱动与设备驱动模型 313
10.4.1　设备驱动 313
10.4.2　设备驱动模型 315
10.5　案例分析：Linux设备驱动模型 315
10.5.1　Linux的设备抽象 315
10.5.2　Linux的设备驱动模型 318
10.5.3　Linux驱动的动态管理 319
10.5.4　Linux的sysfs文件系统 321
10.6　案例分析：L4设备驱动模型 322
10.7　案例分析：Linux的用户态驱动框架 323
10.8　思考题 327
参考文献 327
第11章　系统虚拟化 329
11.1　系统虚拟化技术概述 330
11.1.1　系统虚拟化及其组成部分 330
11.1.2　虚拟机监控器的类型 331
11.2　CPU虚拟化 332
11.2.1　下陷和模拟 333
11.2.2　可虚拟化架构与不可虚拟化架构 333
11.2.3　解释执行 334
11.2.4　动态二进制翻译 335
11.2.5　扫描和翻译 336
11.2.6　半虚拟化技术 337
11.2.7　硬件虚拟化技术 338
11.2.8　小结 340
11.3　内存虚拟化 341
11.3.1　影子页表机制 343
11.3.2　影子页表的缺页异常处理流程 345
11.3.3　直接页表映射机制 345
11.3.4　两阶段地址翻译机制 346
11.3.5　换页和内存气球机制 349
11.3.6　小结 351
11.4　I/O虚拟化 351
11.4.1　软件模拟方法 352
11.4.2　半虚拟化方法 354
11.4.3　设备直通：IOMMU和SR-IOV 356
11.4.4　小结 359
11.5　中断虚拟化 360
11.6　案例分析：QEMU/KVM 361
11.6.1　KVM API和一个简单的虚拟机监控器 362
11.6.2　KVM与QEMU 364
11.6.3　KVM内部实现简介 366
11.7　思考题 367
参考文献 367
缩略语 369
在线章节一
第二部分　操作系统进阶
第12章　多核与多处理器
第13章　文件系统崩溃一致性
第14章　网络协议栈与系统
第15章　轻量级虚拟化
第16章　操作系统安全
第17章　操作系统调测
第18章　形式化证明
第三部分　ChCore课程实验
第19章　实验1：机器启动
第20章　实验2：内存管理
第21章　实验3：用户进程与异常处理
第22章　实验4：多核处理
第23章　实验5：文件系统与Shell
第24章　实验6：进阶实践