操作系统概念（原书第10版）

前言
Operating System Concepts,Tenth Edition

操作系统是计算机系统的重要组成部分。同样，操作系统课程也是计算机科学教育的基本组成部分。这个领域正在快速发展，因为计算机已逐渐渗透到日常生活的方方面面——从汽车的嵌入式设备到政府和跨国公司的先进规划工具。然而，其中的基本概念仍然比较清晰，本书也是基于这些概念展开讨论的。
本书是面向操作系统导论课程的教科书，适用于大三、大四学生和一年级研究生，同时也可供工程技术人员参考。本书清晰地描述了操作系统的概念。作为先决条件，我们假设读者熟悉基本数据结构、计算机组成和一种高级语言（如C或Java）。本书第1章包括学习操作系统所需的硬件知识，同时还包括大多数操作系统普遍使用的基础数据结构知识。代码示例主要使用C和Java，不过，即使读者不具有这些语言的全部知识，也能理解这些算法。
本书不仅直观描述了概念，而且包括重要的理论结果，但是省略了大部分的形式化证明。每章结尾的推荐读物给出了相关研究论文，其中有的首次提出或证明了这些理论结果，有的提供深入阅读的新材料。本书通过图形和举例来说明为什么有关结果是真实有效的。
本书描述的基本概念和算法通常用于商用和开源的操作系统。我们的目标是，按照通用的（而非特定的）操作系统来描述这些概念和算法。另外，我们提供了受欢迎和具创新的操作系统的大量示例，包括Linux、Microsoft Windows、Apple macOS（原名为OS X，在2016年改为macOS，以与其他Apple产品的命名方案相匹配）和Solaris。我们还给出了两个主要移动操作系统（Android和iOS）的示例。
本书的编写融合了我们从事操作系统教学的多年经验。另外，还考虑了多位审稿人员提供的反馈意见，以及之前版本的读者和用书师生的许多意见和建议。第10版还反映了2013年计算机科学课程中操作系统领域的大部分课程指南，该指南由IEEE计算机协会（IEEE Computing Society）和ACM（Association for Computing Machinery，计算机学会）共同出版。
本书资源
本书共有21章。有些章包含以下配套资源：
一套练习。
一套常规习题。
一组编程题。
一组编程项目。
推荐读物。
重要术语（黑体）的定义。
本书内容
本书包括九个主要部分：
概论。第1章和第2章解释了操作系统是什么，它们能做什么，以及它们是如何设计与构造的。这一部分讨论了操作系统的常见功能是什么，以及操作系统能为用户提供什么。我们不仅讨论PC和服务器的传统操作系统，而且讨论移动设备的操作系统。描述主要以启发和解释为主。这一部分避免讨论内部实现细节。因此，这部分适合低年级学生或类似读者，以便了解操作系统是什么而无须关注内部算法细节。
进程管理。第3~5章描述了进程概念和并发，这是现代操作系统的核心。进程是系统内的工作单元。这种系统包括一组并发执行进程，其中一些是操作系统进程（执行系统代码的进程），其余的是用户进程（执行用户代码的进程）。这一部分包括进程调度、进程间通信方法，还包括线程分析以及多核系统和并行编程的有关分析。
进程同步。第6~8章包括进程同步和死锁的处理方法。由于加强了进程同步的讨论，所以我们将上一版的第5章（进程同步）分为两个独立章节：同步工具（第6章）和同步案例（第7章）。
内存管理。第9章和第10章讨论进程执行期间的内存管理。为了改进CPU的利用率及其对用户的响应速度，计算机必须同时在内存中保存多个进程。内存管理有很多不同方案，反映了内存管理的各种方法；而特定算法的有效性取决于具体的应用场景。
存储管理。第11章和第12章描述了现代计算机系统如何处理大容量存储和I／O。由于连到计算机的I／O设备种类繁多，操作系统需要为应用程序提供大量的功能来控制这些设备。这一部分深入讨论了系统I／O，包括I／O系统设计、接口及系统内部的结构和功能。在许多方面，I／O设备是计算机中慢的主要组件。因为设备通常会是性能瓶颈，所以这一部分也讨论了I／O设备的性能问题。
文件系统。第13~15章讨论了现代计算机系统如何处理文件系统。文件系统提供了在线存储和访问数据、程序的机制。我们描述了存储管理的经典内部算法和结构，并对所使用的算法进行了深入讨论，包括它们的属性和优缺点。
安全与保护。第16章和第17章讨论了计算机系统安全和保护所需的机制。操作系统的进程活动必须互相保护，我们必须确保只有获得操作系统适当授权的进程才能使用系统的文件、内存、CPU和其他资源。保护是一种机制，用于控制程序、进程和用户对计算机系统资源的访问，这种机制必须提供指定控制和实施控制的手段。安全保护系统的存储信息（数据和代码）和计算机物理资源的完整性，从而避免未经授权的访问、恶意破坏或修改，以及意外引入不一致。
高级主题。第18章和第19章讨论虚拟机和网络与分布式系统。第18章概述了虚拟机及其与现代操作系统的关系，也讨论了使虚拟化成为可能的硬件和软件技术。第19章概述了计算机网络与分布式系统，以Internet和TCP／IP为主。
案例研究。第20章和第21章详细研究了两个真实操作系统：Linux和Wind

本书是面向操作系统导论课程的经典书籍，从第1版至今被国内外众多高校选作教材。全书共九个部分，相较于上一版增加了三个部分，并且优化了各章的编排顺序。本书不仅详细讲解进程管理、内存管理、存储管理、保护与安全等概念，而且涵盖重要的理论结果和案例研究，并且给出了供读者深入学习的推荐读物。这一版在移动操作系统、多核系统、虚拟化和NVM外存等方面做了大幅更新，每一章都融入了新的技术进展，并且更新了习题和编程项目。本书既适合高等院校计算机相关专业的学生学习，也是专业技术人员的有益参考。

目录
Operating System Concepts,Tenth Edition
译者序
前言
第一部分概论
第1章导论2
1.1操作系统的功能2
1.1.1用户视角2
1.1.2系统视角3
1.1.3操作系统的定义3
1.2计算机系统的组成4
1.2.1中断5
1.2.2存储结构7
1.2.3I／O结构9
1.3计算机系统的体系结构9
1.3.1单处理器系统9
1.3.2多处理器系统10
1.3.3集群系统11
1.4操作系统的执行13
1.4.1多道程序与多任务14
1.4.2双模式与多模式操作15
1.4.3定时器16
1.5资源管理16
1.5.1进程管理16
1.5.2内存管理17
1.5.3文件系统管理17
1.5.4大容量存储管理18
1.5.5高速缓存管理18
1.5.6I／O系统管理20
1.6安全与保护20
1.7虚拟化21
1.8分布式系统22
1.9内核数据结构22
1.9.1列表、堆栈与队列22
1.9.2树23
1.9.3哈希函数与哈希表24
1.9.4位图24
1.10计算环境25
1.10.1传统计算25
1.10.2移动计算25
1.10.3客户机-服务器计算26
1.10.4对等计算26
1.10.5云计算27
1.10.6实时嵌入式系统27
1.11免费与开源操作系统28
1.11.1开源操作系统的历史29
1.11.2自由操作系统29
1.11.3GNU／Linux29
1.11.4BSD UNIX30
1.11.5Solaris30
1.11.6用作学习的开源操作
系统31
1.12本章小结31
1.13推荐读物32
1.14参考文献32
1.15练习33
1.16习题33
第2章操作系统结构35
2.1操作系统的服务35
2.2用户与操作系统的界面36
2.2.1命令解释器37
2.2.2图形用户界面37
2.2.3触摸屏界面38
2.2.4界面的选择38
2.3系统调用39
2.3.1系统调用示例39
2.3.2应用编程接口39
2.3.3系统调用的类型41
2.4系统服务46
2.5链接器与加载器46
2.6应用程序特定于操作系统的
原因48
2.7操作系统的设计与实现49
2.7.1设计目标49
2.7.2机制与策略49
2.7.3实现50
2.8操作系统的结构50
2.8.1简单结构51
2.8.2分层法51
2.8.3微内核52
2.8.4模块53
2.8.5混合系统53
2.9操作系统的构建与引导56
2.9.1操作系统的生成56
2.9.2操作系统的引导57
2.10操作系统的调试58
2.10.1故障分析59
2.10.2性能优化59
2.10.3跟踪60
2.10.4BCC60
2.11本章小结61
2.12推荐读物62
2.13参考文献62
2.14练习63
2.15习题63
2.16编程题63
2.17编程项目64
第二部分进程管理
第3章进程70
3.1进程的概念70
3.1.1进程概述70
3.1.2进程状态71
3.1.3进程控制块72
3.1.4线程73
3.2进程调度73
3.2.1调度队列74
3.2.2CPU调度74
3.2.3上下文切换75
3.3进程操作76
3.3.1进程创建76
3.3.2进程终止79
3.4进程间通信81
3.5共享内存系统的IPC82
3.6消息传递系统的IPC83
3.6.1命名84
3.6.2同步85
3.6.3缓冲85
3.7IPC系统示例86
3.7.1POSIX共享内存86
3.7.2Mach消息传递88
3.7.3Windows90
3.7.4管道91
3.8客户机-服务器系统中的通信
95
3.8.1套接字95
3.8.2远程过程调用97
3.9本章小结99
3.10推荐读物100
3.11参考文献100
3.12练习100
3.13习题101
3.14编程题104
3.15编程项目106
第4章线程与并发113
4.1概述113
4.1.1动机113
4.1.2优点114
4.2多核编程115
4.2.1编程挑战115
4.2.2并行的类型116
4.3多线程模型117
4.3.1多对一模型117
4.3.2一对一模型117
4.3.3多对多模型117
4.4线程库118
4.4.1Pthreads119
4.4.2Windows线程120
4.4.3Java线程121
4.5隐式线程124
4.5.1线程池124
4.5.2复刻加入126
4.5.3OpenMP128
4.5.4大中央调度129
4.5.5Intel线程构建模块130
4.6多线程问题131
4.6.1系统调用fork()和
exec()131
4.6.2信号处理131
4.6.3线程撤销132
4.6.4线程本地存储133
4.6.5调度程序激活134
4.7操作系统示例135
4.7.1Windows线程135
4.7.2Linux线程135
4.8本章小结136
4.9推荐读物137
4.10参考文献137
4.11练习137
4.12习题137
4.13编程题139
4.14编程项目141
第5章CPU调度143
5.1基本概念143
5.1.1CPU-I/O突发周期143
5.1.2CPU调度程序144
5.1.3抢占式和非抢占式调度144
5.1.4分派程序145
5.2调度准则146
5.3调度算法146
5.3.1先到先服务调度146
5.3.2短作业优先调度147
5.3.3轮转调度149
5.3.4优先级调度150
5.3.5多级队列调度151
5.3.6多级反馈队列调度152
5.4线程调度153
5.4.1竞争范围153
5.4.2Pthreads调度153
5.5多处理器调度155
5.5.1多处理器调度的方法155
5.5.2多核处理器156
5.5.3负载平衡158
5.5.4处理器亲和性158
5.5.5异构多处理159
5.6实时CPU调度159
5.6.1小化延迟159
5.6.2基于优先级的调度160
5.6.3单调速率调度161
5.6.4早截止期限优先调度162
5.6.5比例分享调度163
5.6.6POSIX实时调度163
5.7操作系统示例165
5.7.1示例：Linux调度165
5.7.2示例：Windows调度167
5.7.3示例：Solaris调度169
5.8算法评估170
5.8.1确定性模型171
5.8.2排队模型171
5.8.3仿真172
5.8.4实现172
5.9本章小结173
5.10推荐读物174
5.11参考文献174
5.12练习175
5.13习题176
5.14编程项目178
第三部分进程同步
第6章同步工具182
6.1背景182
6.2临界区问题183
6.3Peterson解决方案185
6.4硬件同步支持186
6.4.1内存屏障186
6.4.2硬件指令187
6.4.3原子变量189
6.5互斥锁189
6.6信号量191
6.6.1信号量的使用191
6.6.2信号量的实现191
6.7管程193
6.7.1管程的使用194
6.7.2采用信号量的管程实现195
6.7.3管程内的进程重启196
6.8活性196
6.8.1死锁197
6.8.2优先级反转197
6.9评估198
6.10本章小结199
6.11推荐读物199
6.12参考文献200
6.13练习200
6.14习题200
6.15编程题205
第7章同步案例207
7.1经典同步问题207
7.1.1有界缓冲区问题207
7.1.2读者-作者问题207
7.1.3哲学家就餐问题209
7.2内核的同步211
7.2.1Windows的同步211
7.2.2Linux的同步212
7.3POSIX的同步213
7.3.1POSIX 互斥锁213
7.3.2POSIX信号量213
7.3.3POSIX条件变量214
7.4Java的同步215
7.4.1Java管程215
7.4.2重入锁218
7.4.3信号量218
7.4.4条件变量219
7.5其他方法220
7.5.1事务内存220
7.5.2OpenMP221
7.5.3函数式编程语言222
7.6本章小结222
7.7推荐读物222
7.8参考文献222
7.9练习223
7.10习题223
7.11编程题223
7.12编程项目224
第8章死锁230
8.1系统模型230
8.2多线程应用程序的死锁231
8.3死锁特点233
8.3.1必要条件233
8.3.2资源分配图233
8.4死锁处理方法235
8.5死锁预防235
8.5.1互斥235
8.5.2占有并等待236
8.5.3非抢占236
8.5.4 循环等待236
8.6死锁避免238
8.6.1 安全状态238
8.6.2资源分配图算法239
8.6.3银行家算法239
8.7死锁检测241
8.7.1每种资源类型只有单个
实例241
8.7.2每种资源类型可有多个
实例242
8.7.3检测算法的使用243
8.8死锁恢复244
8.8.1进程与线程的中止244
8.8.2资源抢占244
8.9本章小结245
8.10推荐读物245
8.11参考文献245
8.12练习245
8.13习题247
8.14编程题249
8.15编程项目249
第四部分内存管理
第9章内存252
9.1背景252
9.1.1基本硬件252
9.1.2地址绑定253
9.1.3逻辑地址空间与物理地址
空间254
9.1.4动态加载255
9.1.5动态链接与共享库255
9.2连续内存分配256
9.2.1内存保护256
9.2.2内存分配257
9.2.3碎片257
9.3分页258
9.3.1基本方法258
9.3.2硬件支持261
9.3.3保护263
9.3.4共享页263
9.4页表结构264
9.4.1分层分页264
9.4.2哈希页表265
9.4.3倒置页表266
9.4.4Oracle SPARC Solaris267
9.5交换267
9.5.1标准交换267
9.5.2采用分页的交换267
9.5.3移动系统的交换268
9.6示例：Intel 32位与64位体系
结构268
9.6.1IA-32架构269
9.6.2x86-64270
9.7示例：ARMv8架构271
9.8本章小结272
9.9推荐读物272
9.10参考文献273
9.11练习273
9.12习题274
9.13编程题275
9.14编程项目275
第10章虚拟内存277
10.1背景277
10.2请求调页279
10.2.1基本概念279
10.2.2空闲帧列表281
10.2.3请求调页的性能282
10.3写时复制283
10.4页面置换284
10.4.1基本页面置换285
10.4.2FIFO页面置换287
10.4.3优页面置换288
10.4.4LRU页面置换288
10.4.5近似LRU页面置换290
10.4.6基于计数的页面置换291
10.4.7页面缓冲算法292
10.4.8应用程序与页面置换292
10.5帧分配292
10.5.1帧的小数293
10.5.2分配算法293
10.5.3全局分配与局部分配294
10.5.4非均匀内存访问295
10.6抖动296
10.6.1抖动的原因296
10.6.2工作集模型297
10.6.3缺页错误频率299
10.6.4当前做法300
10.7内存压缩300
10.8分配内核内存301
10.8.1伙伴系统301
10.8.2slab分配302
10.9其他考虑因素303
10.9.1预调页面303
10.9.2页面大小304
10.9.3TLB范围304
10.9.4倒置页表305
10.9.5程序结构305
10.9.6I/O联锁与页面锁定306
10.10操作系统示例307
10.10.1Linux307
10.10.2Windows308
10.10.3Solaris308
10.11本章小结309
10.12推荐读物310
10.13参考文献310
10.14练习310
10.15习题312
10.16编程题316
10.17编程项目316
第五部分存储管理
第11章大容量存储320
11.1大容量存储结构概述320
11.1.1硬盘驱动器320
11.1.2非易失性存储设备321
11.1.3易失性存储器323
11.1.4二级存储连接方法324
11.1.5地址映射324
11.2HDD调度325
11.2.1FCFS调度325
11.2.2SCAN调度326
11.2.3C-SCAN调度326
11.2.4磁盘调度算法的选择326
11.3NVM调度327
11.4错误检测和纠正328
11.5存储设备管理328
11.5