操作系统设计：Xinu方法（原书第2版）

本书以Xinu（一个小型简洁的操作系统）为例，全面介绍操作系统设计方面的知识。本书着重讨论用于嵌入式设备的微内核操作系统，采用的方法是在现有的操作系统课程中纳入更多的嵌入式处理内容，而非引入一门教读者如何在嵌入式系统上编程的新课程。
本书从底层机器开始，一步步地设计和实现一个小型但优雅的操作系统Xinu，指导读者通过实用、简单的原语来构造传统的基于进程的操作系统。本书回顾了主要的系统组件，并利用分层设计范式，以一种有序、易于理解的方式组织内容。
作者的网站www.xinu.cs.purdue.edu提供了便于学生搭建实验环境的软件和资料。

出版者的话
译者序
前言
关于作者
第1章　引言和概述1
1.1　操作系统1
1.2　本书的研究方法2
1.3　分层设计2
1.4　Xinu操作系统4
1.5　操作系统的界定4
1.6　从外部看操作系统5
1.7　其他章节概要6
1.8　观点6
1.9　总结7
练习7
第2章　并发执行与操作系统服务8
2.1　引言8
2.2　多活动的编程模型8
2.3　操作系统服务9
2.4　并发处理的概念和术语9
2.5　串行程序和并发程序的区别11
2.6　多个进程共享同一段代码12
2.7　进程退出与进程终止14
2.8　共享内存、竞争条件和同步14
2.9　信号量与互斥18
2.10　Xinu中的类型命名方法19
2.11　使用kputc和kprintf进行操作系统的调试20
2.12　观点20
2.13　总结21
练习21
第3章　硬件与运行时环境概述22
3.1　引言22
3.2　开发平台的物理和逻辑架构22
3.3　指令集23
3.4　通用寄存器23
3.5　I/O总线和存-取范例24
3.6　DMA机制25
3.7　总线地址空间25
3.8　总线启动和配置26
3.9　函数调用约定和运行时栈26
3.10　中断和中断处理28
3.11　中断向量29
3.12　异常向量和异常处理29
3.13　时钟硬件29
3.14　串行通信30
3.15　轮询与中断驱动I/O30
3.16　存储布局30
3.17　内存保护31
3.18　硬件细节和片上系统体系结构31
3.19　观点31
3.20　硬件参考资料32
练习32
第4章　链表与队列操作33
4.1　引言33
4.2　进程链表的统一数据结构33
4.3　简洁的链表数据结构34
4.4　队列数据结构的实现35
4.5　内联队列操作函数36
4.6　获取链表中进程的基础函数37
4.7　FIFO队列操作38
4.8　优先级队列的操作40
4.9　链表初始化42
4.10　观点43
4.11　总结43
练习43
第5章　调度和上下文切换45
5.1　引言45
5.2　进程表45
5.3　进程状态47
5.4　就绪和当前状态48
5.5　调度策略48
5.6　调度的实现49
5.7　推迟重新调度52
5.8　上下文切换的实现52
5.9　内存中保存的状态52
5.10　上下文切换操作53
5.11　重新启动进程执行的地址56
5.12　并发执行和空进程57
5.13　使进程就绪和调度常量57
5.14　其他进程调度算法58
5.15　观点58
5.16　总结59
练习59
第6章　更多进程管理60
6.1　引言60
6.2　进程挂起和恢复60
6.3　自我挂起和信息隐藏60
6.4　系统调用61
6.5　禁止和恢复中断62
6.6　系统调用模板63
6.7　系统调用返回值SYSERR和OK63
6.8　挂起的实现64
6.9　挂起当前进程65
6.10　suspend函数的返回值65
6.11　进程终止和进程退出66
6.12　进程创建68
6.13　其他进程管理函数72
6.14　总结74
练习74
第7章　协调并发进程76
7.1　引言76
7.2　进程同步的必要性76
7.3　计数信号量的概念77
7.4　避免忙等待77
7.5　信号量策略和进程选择77
7.6　等待状态78
7.7　信号量数据结构79
7.8　系统调用wait79
7.9　系统调用signal80
7.10　静态和动态信号量分配81
7.11　动态信号量的实现示例82
7.12　信号量删除83
7.13　信号量重置84
7.14　并行处理器（多核）之间的协调85
7.15　观点86
7.16　总结86
练习87
第8章　消息传递88
8.1　引言88
8.2　两种类型的消息传递服务88
8.3　消息使用资源的限制89
8.4　消息传递函数和状态转换89
8.5　send的实现90
8.6　receive的实现91
8.7　非阻塞消息接收的实现92
8.8　观点92
8.9　总结92
练习93
第9章　基本内存管理94
9.1　引言94
9.2　内存的类型94
9.3　重量级进程的定义95
9.4　示例系统的内存管理95
9.5　程序段和内存区域95
9.6　动态内存分配96
9.7　底层内存管理器的设计97
9.8　分配策略和内存持久性97
9.9　追踪空闲内存98
9.10　底层内存管理的实现98
9.11　使用空闲内存的数据结构定义99
9.12　分配堆存储100
9.13　分配栈存储102
9.14　堆和栈存储的释放103
9.15　观点105
9.16　总结106
练习106
第10章　高级内存管理和虚拟内存107
10.1　引言107
10.2　分区空间分配107
10.3　缓冲池108
10.4　分配缓冲区108
10.5　将缓冲区返还给缓冲池110
10.6　创建缓冲池111
10.7　初始化缓冲池表112
10.8　虚拟内存和内存复用113
10.9　实地址空间和虚地址空间113
10.10　支持按需分页的硬件114
10.11　使用页表的地址转换114
10.12　页表项中的元数据115
10.13　按需分页以及设计上的问题116
10.14　页面替换和全局时钟算法116
10.15　观点117
10.16　总结117
练习118
第11章　高层消息传递119
11.1　引言119
11.2　进程间通信端口119
11.3　端口实现119
11.4　端口表初始化120
11.5　端口创建121
11.6　向端口发送消息122
11.7　从端口接收消息124
11.8　端口的删除和重置125
11.9　观点128
11.10　总结128
练习128
第12章　中断处理130
12.1　引言130
12.2　中断的优点130
12.3　中断处理130
12.4　中断向量131
12.5　中断和异常集成131
12.6　使用代码的ARM异常向量132
12.7　设备中断向量号的分配135
12.8　中断分派136
12.9　中断的软件结构137
12.10　禁止中断139
12.11　中断代码调用函数的限制140
12.12　中断过程中重新调度的必要性140
12.13　中断过程中的重新调度140
12.14　观点141
12.15　总结142
练习142
第13章　实时时钟管理143
13.1　引言143
13.2　定时事件143
13.3　实时时钟和计时器硬件143
13.4　实时时钟中断处理144
13.5　延时与抢占145
13.6　抢占的实现145
13.7　使用增量链表对延迟进行有效管理146
13.8　增量链表的实现147
13.9　将进程转入睡眠148
13.10　定时消息接收150
13.11　唤醒睡眠进程154
13.12　时钟中断处理154
13.13　时钟初始化156
13.14　观点159
13.15　总结159
练习159
第14章　设备无关的I/O161
14.1　引言161
14.2　I/O和设备驱动的概念结构161
14.3　接口抽象和驱动抽象162
14.4　I/O接口示例163
14.5　打开-读-写-关闭范例163
14.6　绑定I/O操作和设备名164
14.7　Xinu中的设备名164
14.8　设备转换表概念165
14.9　设备的多个副本和共享驱动166
14.10　高层I/O操作的实现168
14.11　其他高层I/O函数169
14.12　打开、关闭和引用计数172
14.13　devtab中的空条目和错误条目174
14.14　I/O系统的初始化174
14.15　观点178
14.16　总结179
练习179
第15章　设备驱动示例180
15.1　引言180
15.2　使用UART硬件进行串行通信180
15.3　tty抽象180
15.4　tty设备驱动的组织结构181
15.5　请求队列和缓冲区182
15.6　上半部和下半部的同步183
15.7　UART硬件FIFO与驱动设计184
15.8　控制块的概念184
15.9　tty控制块和数据声明184
15.10　次设备号186
15.11　上半部tty字符输入（ttygetc）187
15.12　上半部tty读取函数（ttyread）188
15.13　上半部tty字符输出（ttyputc）189
15.14　开始输出（ttykickout）190
15.15　上半部tty多字符输出（ttywrite）191
15.16　下半部tty驱动函数（ttyhandler）192
15.17　输出中断处理（ttyhandle_out）194
15.18　tty输入处理（ttyhandle_in）196
15.19　tty控制块初始化（ttyinit）202
15.20　设备驱动控制（ttycontrol）204
15.21　观点205
15.22　总结205
练习206
第16章　DMA设备和驱动（以太网）207
16.1　引言207
16.2　直接内存访问和缓冲区207
16.3　多个缓冲区和缓冲区环207
16.4　使用DMA的以太网驱动示例208
16.5　设备的硬件定义和常量209
16.6　环和内存缓冲区211
16.7　以太网控制块的定义213
16.8　设备和驱动初始化215
16.9　从以太网设备读取数据包221
16.10　向以太网设备写入数据包223
16.11　以太网设备的中断处理225
16.12　以太网控制函数228
16.13　观点229
16.14　总结229
练习229
第17章　最小互联网协议栈230
17.1　引言230
17.2　所需的功能230
17.3　同步会话、超时和网络处理进程231
17.4　设计的影响232
17.5　ARP函数232
17.6　网络数据包的定义241
17.7　网络输入进程242
17.8　IP的相关定义245
17.9　IP函数246
17.10　UDP表的定义255
17.11　UDP函数256
17.12　互联网控制报文协议267
17.13　动态主机配置协议268
17.14　观点275
17.15　总结275
练习275
第18章　远程磁盘驱动277
18.1　引言277
18.2　磁盘抽象277
18.3　磁盘驱动支持的操作277
18.4　块传输和高层I/O函数277
18.5　远程磁盘范例278
18.6　高速缓存的重要概念278
18.7　磁盘操作的语义279
18.8　驱动数据结构的定义280
18.9　驱动初始化（rdsinit）284
18.10　上半部打开函数（rdsopen）287
18.11　远程通信函数（rdscomm）289
18.12　上半部写函数（rdswrite）291
18.13　上半部读函数（rdsread）293
18.14　刷新挂起的请求296
18.15　上半部控制函数（rdscontrol）297
18.16　分配磁盘缓冲区（rdsbufalloc）299
18.17　上半部关闭函数（rdsclose）300
18.18　下半部通信进程（rdsprocess）302
18.19　观点306
18.20　总结306
练习306
第19章　文件系统308
19.1　什么是文件系统308
19.2　文件操作的示例集308
19.3　本地文件系统的设计309
19.4　Xinu文件系统的数据结构309
19.5　索引管理器的实现310
19.6　清空索引块（lfibclear）314
19.7　获取索引块（lfibget）315
19.8　存储索引块（lfibput）315
19.9　从空闲链表中分配索引块（lfiballoc）316
19.10　从空闲链表中分配数据块（lfdballoc）317
19.11　使用设备无关的I/O函数进行文件操作319
19.12　文件系统的设备配置和函数名称320
19.13　本地文件系统打开函数（lfsopen）320
19.14　关闭文件伪设备（lflclose）326
19.15　刷新磁盘中的数据（lfflush）328
19.16　文件的批量传输函数（lflwrite、lflread）328
19.17　在文件中查找新位置（lflseek）330
19.18　从文件中提取一字节（lflgetc）331
19.19　改变文件中的一字节（lflputc）332
19.20　载入索引块和数据块（lfsetup）334
19.21　主文件系统设备的初始化（lfsinit）337
19.22　伪设备的初始化（lflinit）338
19.23　文件截断（lftruncate）339
19.24　初始文件系统的创建（lfscreate）341
19.25　观点343
19.26　总结343
练习343
第20章　远程文件机制345
20.1　引言345
20.2　远程文件访问345
20.3　远程文件语义345
20.4　远程文件设计和消息346
20.5　远程文件服务器通信（rfscomm）352
20.6　发送基本消息（rfsndmsg）354
20.7　网络字节序355
20.8　使用设备范例的远程文件系统355
20.9　打开远程文件（rfsopen）356
20.10　检查文件模式（rfsgetmode）359
20.11　关闭远程文件（rflclose）360
20.12　读远程文件（rflread）361
20.13　写远程文件（rflwrite）363
20.14　远程文件的定位（rflseek）365
20.15　远程文件单字符I/O（rflgetc、rflputc）366
20.16　远程文件系统控制函数（rfscontrol）367
20.17　初始化远程文件系统（rfsinit、rflinit）370
20.18　观点372
20.19　总结372
练习372
第21章　句法名字空间374
21.1　引言374
21.2　透明与名字空间抽象374
21.3　多种命名方案375
21.4　命名系统设计的其他方案376
21.5　基于句法的名字空间376
21.6　模式和替换376
21.7　前缀模式377
21.8　名字空间的实现377
21.9　名字空间的数据结构和常量377
21.10　增加名字空间前缀表的映射378
21.11　使用前缀表进行名字映射379
21.12　打开命名文件383
21.13　名字空间初始化383
21.14　对前缀表中的项进行排序386
21.15　选择逻辑名字空间386
21.16　默认层次和空前缀387
21.17　额外的对象操作函数387
21.18　名字空间方法的优点和限制388
21.19　广义模式388
21.20　观点389
21.21　总结389
练习390
第22章　系统初始化391
22.1　引言391
22.2　引导程序：从零开始391
22.3　一个通过网络启动的例子392
22.4　操作系统初始化392
22.5　Xinu初始化393
22.6　Xinu系统启动395
22.7　从程序转化为进程399
22.8　观点399
22.9　总结399
练习400
第23章　子系统初始化和内存标记401
23.1　引言401
23.2　自初始化模块401
23.3　并发系统中的自初始化模块402
23.4　重新启动后的自初始化403
23.5　使用登录号初始化404
23.6　广义内存标记方案405
23.7　内存标记系统的数据声明406
23.8　标记的实现407
23.9　观点408
23.10　总结408
练习408
第24章　异常处理409
24.1　引言409
24.2　术语：故障、检测、陷阱和异常409
24.3　向量异常和可屏蔽中断 409
24.4　异常的类型410
24.5　处理异常410
24.6　异常向量初始化411
24.7　面对灾难时的panic411
24.8　panic函数的实现411
24.9　观点412
24.10　总结412
练习412
第25章　系统配置413
25.1　引言413
25.2　多重配置的需求413
25.3　Xinu系统配置414
25.4　Xinu配置文件的内容414
25.5　计算次设备号416
25.6　配置Xinu系统的步骤417
25.7　观点417
25.8　总结417
练习417
第26章　一个用户接口例子：Xinu shell419
26.1　引言419
26.2　什么是用户接口419
26.3　命令和设计原则419
26.4　一个简化shell的设计决策420
26.5　shell的组织和操作420
26.6　词法符号的定义421
26.7　命令行语法的定义421
26.8　Xinu shell的实现422
26.9　符号的存储424
26.10　词法分析器代码424
26.11　命令解释器的核心428
26.12　命令名查询和内部处理434
26.13　传递给命令的参数435
26.14　向外部命令传递参数435
26.15　I/O重定向438
26.16　命令函数（sleep）的例子439
26.17　观点440
26.18　总结441
练习441
附录1　操作系统移植443
附录2　Xinu设计注解450
索引454

建立计算机操作系统就像编织锦缎，这两种工作的最终成品都是一个和谐一致、大型、复杂的人造系统。且在以上两种工作中，最后的人造成品都是经由细微、精巧的步骤所构造的。在编织锦缎时，细节至关重要，因为一点点不协调的瑕疵都很容易被观察到。就像锦缎里的缎面一样，加入操作系统里的每个新组件都需要与整体设计相协调。因此，将不同组件组装起来的机械加工只是整个建造过程中的一小部分，一个大师级产品必须以某个模式为蓝本，所有参与系统设计的工作人员都必须遵循这个模式。
具有讽刺意味的是，现有的操作系统教材或课程很少对底层的模式和原理进行解释，而这些模式和原理正是操作系统构造的基础。在学生看来，操作系统似乎是一个暗箱，而现有的教材则加深了这种误解，因为这些教材所解释的不过是操作系统的特性，其关注的也只是操作系统各种功能的使用。更为重要的是，学生在学习操作系统时采取的是从操作系统外面来查看的方式，从而常常导致这样一种感觉：操作系统由一组接口函数组成，这些接口下的功能由一大堆晦涩神秘的代码连接在一起，而这些神秘的代码本身还包含着许多与机器硬件直接相关的、无规律可循的奇技巧术。
令人惊奇的是，学生一旦从大学毕业，就马上觉得与操作系统有关的研究工作已经结束，自己不再需要理解或学习操作系统了，因为由商业公司和开源社区所构造的现有操作系统足以应付各种需要—没有什么比这种想法离真理更远了。与之相反，尽管为个人计算机设计传统操作系统的公司数量比以前更少了，但社会和行业对操作系统专门技术的需求却在增长，许多公司雇佣学生来从事操作系统方面的工作。这些需求增长主要源于更便宜的微处理器，而这些便宜的微处理器被广泛嵌入在智能手机、视频游戏产品、无线传感器、线缆和机顶盒以及打印机等设备中。
在与嵌入式系统打交道时，有关原理和结构的知识非常关键，因为程序员可能需要在现有的操作系统内部构造某种新的机制，或者对现有操作系统进行修改以便可以在新的硬件平台上运行。此外,为嵌入式设备编写应用程序需要理解底层操作系统。如果不理解操作系统设计的各种细微之处，则不可能充分开发小型嵌入式处理器的功能。
本书的目的是揭开操作系统设计的神秘面纱，将方方面面的材料整合为一个系统化的整体。本书对操作系统的主要系统组件进行了详细阐述，并以一种层次架构的设计范例来组织这些组件，从而以一种有序、可理解的方式来展开内容。与其他尽可能多地提供不同方案的评述性书籍不同的是，本书引导读者使用实用的、直截了当的原语来构造一个传统的基于进程的操作系统，从裸机开始，一步一步地设计和实现一个小型但优雅的操作系统。这个名为Xinu的操作系统将成为系统设计的一个样板和模式。
虽然Xinu操作系统的规模较小，可以完全容纳在本书中，但是该系统包含了构成一个普通操作系统的全部组件：内存管理、进程管理、进程协调和同步、进程间通信、实时时钟管理、设备无关的I/O、设备驱动、网络协议和文件系统。本书将这些组件组织成一个多层次架构，这使得它们之间的相互连接清晰可见、设计过程浅显易懂。尽管规模小，Xinu却拥有大型系统的大部分功能。此外，Xinu并不是一个“玩具”系统，它在很多商业产品中得到了应用。使用该系统的厂商包括Mitsubishi、Lexmark、HP、IBM、Woodward（woodward.com）、Barnard Software和Mantissa公司。读者通过本书可以学到的重要一课是：不管是小型嵌入式系统还是大型系统，好的系统设计都一样重要，而好的设计是通过选择好的抽象方法来实现的。
本书所覆盖的议题都以一种特定的次序排列，这种次序就是设计人员在构建操作系统时所遵守的工作次序。本书的每一章描述了设计架构里的一个组件，并提供示例软件来演示该层架构所提供的功能。使用这种方式具有如下优点：第一，每一章所解释的操作系统的功能子集均比上一章所讨论的功能子集更大，这种安排使得我们在考虑一层特定架构的设计和实现时不用关心后续层的实现。第二， 一个特定章节的细节描述在第一次阅读时可以跳过去，读者只需要理解该层所提供的服务即可，而不是这些服务是如何实现的。第三，如果按次序阅读本书，读者可以先理解某个功能，然后再应用该功能。第四，有智力挑战的议题（如对并发的支持）出现在书的较前面，高层次的操作系统服务则在后面展示。在本书中，读者将看到大多数核心功能仅仅用几行代码就可以完成，这样我们就可以将大体量的代码（网络和文件系统）放到书的较后面，在读者已经做好充分的思想准备后再进行讲解。
如前所述，与许多其他关于操作系统的书籍不同，本书并不试图对每个系统组件的每种实现方案进行评估，也不对现有的商业系统进行综述，而是对一组使用广泛的操作系统原语的实现细节进行阐述。例如，在讨论进程协调的一章，我们解释的是信号量（使用最广泛的进程协调原语），而将其他原语（如监视器）的讨论放至练习中。我们的目的是展示如何在传统硬件上实现原语，消除其神秘感。学生一旦理解了一组特定原语的魔力，其他原语的实现也就容易掌握了。
本书展示的Xinu代码可以运行在多种硬件平台上。我