操作系统原型——xv6分析与实验

操作系统一词的内涵比较丰富。当我们听说某人是操作系统高手时，可能指这个人是操作系统“系统管理”高手。也就是说，这个人可以快速架设Web服务，能把崩溃的文件系统修复，能设置复杂的网络绕过防火墙又不失安全，等等；又或者这个人是一个“系统编程”高手，能够编写复杂而高效的服务器程序，将多进程/多线程并发、通信与同步等各种技艺玩得炉火纯青；还可能这个人是一个“内核编程”的高手，不仅会编写实现不同文件系统的各种内核模块、还精通编写各种硬件的设备驱动程序。
无论上述哪种高手，都离不开对操作系统基本原理的认知，如果对操作系统的核心机制和编码实现有所认知，都将如虎添翼。操作系统的基本原理和算法层面的知识，我们在大学本科操作系统课程已经掌握得很好了，但对于操作系统的核心机制——特别是软硬件结合的机制，则明显不足，更别说编码实现了。因此上面提到的高手，大多是在职业生涯中自我修炼而成的。说是修炼，是因为没有系统的指导，也没有系统的训练教材，甚至没有人指出成长学习的路径和步骤。
系统软件系列丛书，为大家提供了明确的学习成长路径和充分的学习材料，尝试将原来刻苦的摸索和修炼，变成人人可以科学实施自学的系列课程。我们将该课程分解成四个步骤逐级推进，这四个步骤是: 
(1) 打通C语言—可执行文件—进程映像的通路。
(2) 用观测手段将操作系统从黑盒变白盒。
(3) 掌握在“裸硬件”上设计和实现操作系统核心机制的能力。
(4) 钻研真实操作系统代码。《Linux GNU C程序观察》是块基石，将打通从C语言源程序一直到操作系统进程映像的通路。C语言编程和进程的概念，大家都很熟悉，但是如何从C语言到进程，这两者间的环节缺失太多。《Linux GNU C程序观察》自称为C语言的“下半部”基石，澄清了（1）C语言代码如何编译成汇编代码； （2）汇编代码（严格说是二进制机器码）如何通过链接形成可执行文件，链接过程中符号解析和静态/动态重定位过程，以及终的ELF文件格式； （3）ELF格式如何将可执行文件创建进程映像； （4）如何跟踪和分析程序运行的行为。在解决了进程映像怎么来的问题后，就可以进入下一个问题——多个进程在操作系统中如何共存，如何被操作系统管理。
操作系统原型——xv6分析与实验前言《操作系统之编程观察》则是第二块基石，将原来被错作黑盒的操作系统，通过/proc文件系统等手段进行观测、测量，从而建立对操作系统功能和行为的直观认知。该书首先给读者介绍了一款工具——其类似于电路课程中的万用表和示波器。其次是将本科操作系统课程学习过的四大管理，通过系统编程知识逐一编写应用程序，调用或触发操作系统的相关功能，并用/proc及其他内核测量/统计信息，分析多个进程在操作系统发出各种请求时所发生的动作。例如，可观察或定量地给出了进程空间因分配、回收和文件映射等行为引起的堆、栈的动态变化；多进程/多线程的各种资源开销，因调度策略和优先级的差异而竞争CPU使用时间，因负载均衡而在多个CPU间迁移等；文件系统上的元数据格式及其在文件操作过程中呈现的变化等等。此时，可以说读者已经能将本科操作系统课程中的概念，与操作系统的具体行为建立起了全面的对应关系，能获得知识落地的感觉。
第三块基石是《操作系统原型——xv6分析与实验》，为读者提供操作系统编码实现的初步经验。xv6是操作系统实验的典型系统，被大家广泛学习。如果读者只是想零星地体验一下内核设计，比如看看进程管理、进程调度，会发现非常简单，甚至马上就能发现增强或优化的地方。但xv6本身并非只专注于解决四大管理的上层问题，而是更专注于解决如何在“裸硬件”上支撑分页、进程切换（映像切换和执行流切换）、中断与系统调用、系统启动等底层机制上的问题。虽然互联网上有各位高手对不同子系统的详尽分析，但也是上层分析居多，底层细节偏少，而且缺少独立详尽的材料能将所需的知识系统地有逻辑地呈现给读者。因为xv6本身麻雀虽小但面面俱到，所以《操作系统原型——xv6分析与实验》也将源代码的分析做到面面俱到——完整地分析了xv6的所有内容，包括C源文件、汇编S文件、Makefile，以及所需的x86处理器和核外的键盘、显示器和硬盘控制器等硬件知识。特别是关于x86的地址部件和进程执行流切换过程的细节，体现了精巧的设计思路和编程技巧，属于比较烧脑的部分。除此之外，本书还提供了初级、中级和高级三种实验及其示例代码，也设计了一些额外的练习题目，以供读者练手之用。当读者踏上第三块基石之时，已经对操作系统的设计和编码实现了然于胸，大多数人也可止步于此。
《Linux技术内幕》则是本系列的后一块基石，也是系列丛书中繁冗的一部。对于需要在Linux真实系统上进行开发实践的读者，可以将它作为备选材料之一，毕竟Linux内核的几部经典书籍大家都耳熟能详。但本书有自己的特色和优势，主要体现于开篇时给出了操作系统的多角度视图，拓展读者思考分析的视角，避免陷入盲人摸象的困境。读者借助于明确的功能模型、内存模型和时空模型这三个视角，能在阅读源码过程中将知识内化和自洽。其次在一些局部主题上也可能有一些优势，例如进程切换细节、文件系统各部件的联系等。
系统软件系列丛书共4本，其中前三本都是独具特色，各有建树，是系统软件学习环节不可或缺的知识材料，第四本也可圈可点。本系列丛书来源于深圳大学高性能计算所的教研实践，基于龙芯和Open Power8的国产高性能计算机研制，以及华为昆仑小型机、华为泰山/鲲鹏服务器系统软件开发，由积累的本科和研究生教学操作系统的经验汇集而成。
在操作系统的学习过程中，难之处在于将知识内化和自洽。操作系统作为跨越软件和硬件的系统软件，所需背景知识极为庞杂。如果不能有效地从不同来源获取知识，并将这些知识系统性地综合起来，难度极大且效率极低。我们希望本系列丛书所汇聚和组织的知识能成为读者的攀登基石，协助读者一起推动系统软件的发展进步！

深圳大学计算机与软件学院高性能计算所系统技术组罗秋明2021年6月

本书作为系统软件系列丛书的第四本，与已出版的《Linux GNU C程序观察》《操作系统之编程观察》《Linux技术内幕》共同组成系统软件学习的递进学习材料。 本书共12章，全面分析了xv6的实现并提供了丰富的实验及其示例代码。在分析方面不仅包含了几乎完整的C代码解读，还包括编译、链接和程序装入细节，并给出了QEMU仿真、GDB调试和底层系统硬件架构相关的必要知识。实验方面安排了入门、中级和高级三个层次的内容: 入门实验指导读者自行增加一个系统调用并通过应用程序验证其功能，开启修改操作系统步；中级实验全面体验了调度机制和算法，以及进程间通信中的信号量、共享内存和消息队列的实现，还有内存管理中的离散内存管理和代码数据隔离实验；高级实验综合多方面的知识，实现线程机制、文件功能扩展、虚拟内存实验以及多终端实验。 本书可作为计算机相关专业本科高年级学生和研究生的操作系统实验课程教学用书，也可作为相关专业人员深入了解操作系统的实践用书。

深圳大学计算机与软件学院副教授，广东省国产高性能计算系统工程技术研究中心副主任、深圳市服务计算与应用重点实验室常务副主任，长期从事高性能计算研究。

第1章xv6安装使用1
1.1运行于QEMU的xv61
1.1.1CentOS 7 QEMU xv61
1.1.2Ubuntu 18 QEMU xv62
1.2调试观察4
1.2.1xv6 shell命令4
1.2.2QEMU gdb调试6
1.2.3多核调试10
1.3本章小结12
练习13

第2章入门实验14
2.1新增可执行程序15
2.1.1磁盘映像的生成15
2.1.2添加简单程序16
2.2新增系统调用18
2.2.1系统调用示例19
2.2.2添加系统调用20
2.2.3验证新系统调用22
2.3观察调度过程23
2.4本章小结25
练习25

第3章xv6概述26
3.1xv6代码总览26
3.2xv6二进制代码与镜像27
3.2.1启动扇区27
3.2.2内核代码31
3.2.3磁盘镜像40
3.2.4xv6的Makefile43
3.3xv6内核简介51
3.3.1进程管理52
3.3.2内存管理56
3.3.3文件系统57
3.3.4设备59
3.4本章小结59
练习59
操作系统原型——xv6分析与实验目录
第4章系统启动60
4.1全局性信息60
4.1.1xv6系统常数（param.h）60
4.1.2x86.h硬件相关代码61
4.2bootblock70
4.2.116位/32位模式71
4.2.2bootasm.S72
4.2.3bootmain.c83
4.2.4ELF文件格式87
4.3kernel启动89
4.3.1启动分页90
4.3.2main()95
4.4多核启动100
4.4.1检测多核信息100
4.4.2激活其他处理器107
4.5通用代码111
4.6QEMU仿真命令114
4.7本章小结115
练习116

第5章内存管理118
5.1物理内存初始化（PI）119
5.1.1早期布局119
5.1.2物理页帧的初始化120
5.1.3kalloc.c和mmu.h122
5.2页帧的分配与回收（PR）126
5.3内核空间126
5.3.1内核页表（KI）127
5.3.2内核页表切换（KR）129
5.3.3vm.c131
5.4进程用户空间149
5.4.1用户空间映像（UI）150
5.4.2分配与回收（UR）152
5.4.3用户进程空间切换153
5.4.4内核空间与用户空间交换数据153
5.5本章小结154
练习155

第6章进程管理与同步156
6.1进程管理156
6.1.1调度状态与执行现场156
6.1.2进程控制175
6.1.3执行流的切换184
6.2内核同步——自旋锁190
6.2.1spinlock.h190
6.2.2spinlock.c191
6.3用户应用程序195
6.3.1运行程序195
6.3.2个用户进程init200
6.3.3sh.c203
6.3.4xv6测试（usertests.c）218
6.3.5用户进程的ELF220
6.3.6ULIB库221
6.4本章小结230
练习231

第7章中断/异常/系统调用232
7.1中断及其处理233
7.1.1中断整体描述233
7.2系统调用245
7.2.1系统调用框架246
7.2.2数据传递254
7.2.3用户态接口255
7.3本章小结259
练习260

第8章中级实验261
8.1调度实验261
8.1.1调整时间片长度261
8.1.2优先级调度264
8.2实现信号量273
8.2.1共享变量及其访问273
8.2.2信号量数据结构275
8.2.3信号量操作的系统调用276
8.2.4用户测试代码280
8.3实现进程间通信的实验282
8.3.1共享内存的实现282
8.3.2消息队列的实现299
8.4内存管理实验317
8.4.1实现myfree()和myalloc()系统调用317
8.4.2代码与数据隔离324
8.5本章小结331
练习331

第9章xv6fs文件管理333
9.1xv6fs文件系统333
9.1.1xv6fs概述334
9.2文件系统操作344
9.2.1盘块操作345
9.2.2索引节点操作356
9.2.3目录操作372
9.2.4文件378
9.2.5系统调用386
9.3非核心功能401
9.3.1日志层401
9.3.2特殊文件411
9.4本章小结415
练习416

第10章设备管理417
10.1终端设备417
10.1.1console/tty/terminal/shell417
10.1.2终端及CGA显示器418
10.1.3键盘430
10.1.4串口439
10.2其他硬件442
10.2.1定时器442
10.2.2IDE磁盘/块设备443
10.3中断控制器449
10.3.1APIC450
10.3.2IOAPIC451
10.3.3LAPIC457
10.4本章小结468
练习468

第11章高级实验469
11.1实现xv6内核线程469
11.1.1修改PCB469
11.1.2sys_clone和sys_join系统调用470
11.1.3线程库的实现474
11.1.4测试样例476
11.2文件系统实验478
11.2.1文件权限478
11.2.2恢复被删除的文件484
11.2.3磁盘裸设备的读写488
11.3虚拟内存494
11.3.1虚存交换机制495
11.3.2缺页异常498
11.3.3功能验证501
11.4用户终端实验504
11.4.1设计思路505
11.4.2代码实现506
11.4.3功能验证518
11.5本章小结523
练习523

第12章x86架构概述524
12.1x86的ISA架构524
12.1.1寄存器524
12.1.2内存组织530
12.2x86 MMU地址部件531
12.2.1模式及地址空间531
12.2.2实地址模式533
12.2.3保护模式535
12.2.4分页机制543
12.3中断/异常/系统调用547
12.3.1中断机制548
12.3.2中断描述符表IDT548
12.3.3TSS和内核栈554
12.4本章小结560

本书作为系统软件系列丛书的第四本，与已出版的《Linux GNU C程序观察》《操作系统之编程观察》《Linux技术内幕》共同组成系统软件学习的递进学习材料。 本书共12章，全面分析了xv6的实现并提供了丰富的实验及其示例代码。在分析方面不仅包含了几乎完整的C代码解读，还包括编译、链接和程序装入细节，并给出了QEMU仿真、GDB调试和底层系统硬件架构相关的必要知识。实验方面安排了入门、中级和高级三个层次的内容: 入门实验指导读者自行增加一个系统调用并通过应用程序验证其功能，开启修改操作系统步；中级实验全面体验了调度机制和算法，以及进程间通信中的信号量、共享内存和消息队列的实现，还有内存管理中的离散内存管理和代码数据隔离实验；高级实验综合多方面的知识，实现线程机制、文件功能扩展、虚拟内存实验以及多终端实验。 本书可作为计算机相关专业本科高年级学生和研究生的操作系统实验课程教学用书，也可作为相关专业人员深入了解操作系统的实践用书。

深圳大学计算机与软件学院副教授，广东省国产高性能计算系统工程技术研究中心副主任、深圳市服务计算与应用重点实验室常务副主任，长期从事高性能计算研究。