自研操作系统:DIM-SUM设计与实现

推荐序1

中国必须发展安全、可控的操作系统，不然会被卡脖子。
 操作系统是管理计算机与软件资源的计算机程序，同时也是计算机系统的内核与基石。随着数字经济的发展，随着5G、人工智能、大数据、云计算等新一代信息技术的蓬勃兴起，保障网络安全成为各个国家的重要任务，自主研发操作系统也就成了建设网络强国势在必行的任务。自主可控是实现网络安全的前提和必要条件，面对日益凸显的网络安全挑战，中国在今后一段时期里，必须加快推进国产自主可控替代计划，构建安全可控的信息技术体系，而操作系统正是信息技术体系的核心。 
目前，全世界智能终端操作系统被三家外国跨国公司（苹果、谷歌和微软）所垄断，它们也是世界上的三家IT企业，这并非巧合。在这个领域，我国被人家卡了脖子，只有大力发展自己的操作系统，才能尽快摆脱受制于人的局面。

中国目前还有大量的操作系统人才缺口。
 无论国内国外，厂商开发操作系统都需要投入足够多的人力和巨大的资金，而国内的厂商在资金和人力上都不具备强大的实力，甚至有个别厂商还处于亏损的状态。不妨引用几组数据：Windows XP 有4000万行代码，Windows 7有5000万行代码，3.6版的Linux 内核有1590万行代码，Linux的发行版Debian有着多达6500万行代码。而且，这些代码还都是经过软件厂商反复精简以后的结果。微软开发Windows Vista操作系统时用掉的研发经费在200亿美元以上，开发Windows XP时集中了5000多名的程序员来编写代码。
 实践经验表明，发展操作系统必须有庞大的软件人才队伍的支撑，但国内至今严重缺乏能够开发操作系统的软件人才，特别是一流的人才。事实上，中国有着相当丰富的应用软件开发人才，可以给微软、苹果、谷歌等科技巨头开发出很好的应用软件，可偏偏缺乏了能开发操作系统等基础软件的人才。因此，如何吸引中国广大应用软件人才，迅速提高他们的技能，从开发应用软件转向开发操作系统等基础软件，这对于发展国产操作系统具有重要意义。我们相信，在这方面本书可以发挥很好的作用。
 
操作系统是一个整体概念，一个成型的系统很庞大，初学者一次搞懂很难，从一个简单的系统入手是好的选择。
 与其他软件不同，一个发布版的操作系统非常庞大，仅仅是操作系统的内核就有上千万行代码，随着版本的更新，代码量还在不断增加，从这样的源代码中体会操作系统的整体设计思想无疑是困难的，许多对操作系统有兴趣的学生，面对这个庞大的代码量时退却了。对于初学者而言，从头进行一个小而全的操作系统设计是更好的选择，容易上手，也更容易理解庞杂代码下的设计核心。本书采取了从易到难、从小到大、循序渐进、融会贯通的途径，特别适合操作系统的新手阅读，可以这样说，本书为有志于从事基础软件攻关的读者打开了一扇通向操作系统殿堂的大门。
 
对操作系统发展的期望。
 目前，基于国产操作系统和芯片的自主创新计算机体系已经逐步缩小了与Wintel体系（即Windows操作系统和Intel架构CPU所构成的体系）之间的差距，国产操作系统已经从“不可用”发展到“可用”，并正向“好用”方向发展。在今后一个相当长的时期里，操作系统的国产化替代将成为我国网信领域的新常态。希望有更多的读者对操作系统产生兴趣，加入自主操作系统的研发中去，为祖国的操作系统事业做出贡献！

中国工程院院士 倪光南
推荐序2

未来是云的时代，也是大数据和人工智能的时代！
芯片和操作系统共同构成了云时代IT基础设施的基石。从操作系统的角度来说，其重要性在于：
操作系统的稳定性是IT基础设施的生命线。
操作系统可以充分利用硬件的性能，有利于企业在竞争中处于优势地位。
数十年来，Linux操作系统已经在产业界取得了广泛的应用，应用生态也得到了蓬勃发展，目前正处于方兴未艾的阶段。在接下来的10年里，Linux可能仍然会是服务器系统、嵌入式系统，甚至是物联网系统中的主流操作系统。
但是，产业界也存在其他一些与Linux竞争的操作系统。例如苹果的iOS系统、谷歌正在研发的Fuchsia操作系统，以及其他国内厂商研发的操作系统。
这些操作系统可能会对产业界10年之后的竞争态势产生一定的影响，因此引起产业界、学术界越来越多的关注。
操作系统的研发工作是一项复杂的系统工程，这也导致一个结果：很难看到个人在实现操作系统，特别是实现可用于生产系统的、实用的服务器操作系统方面有所作为。我们很难想象哪个人会有胆量去尝试，更难想象哪个人会付诸行动。
当我在OS2ATC 2019大会上，听到本书作者谢宝友演讲“做中国的Linux，做中国的Linus”的时候，感到非常吃惊。竟然真的有人愿意在服务器操作系统方面尝试迈出步！不管结果如何，我们首先应该为本书作者的勇气点赞。当然，我们也期望作者能够知行合一，继续发展DIM-SUM操作系统，并终迈向可用于生产环境的服务器操作系统。
我从书稿看到：虽然DIM-SUM还不是一个真正可用于生产环境的服务器操作系统，而且很多设计思路和代码都源于Linux，但是正因为作者在深刻理解Linux的设计与实现后，才能游刃有余地对其进行重构，并且在重构的过程中糅合自己原创的设计要素。真正在产业界一线的工程师更能清楚地意识到，这是一个很有挑战的工作。
随着本书的出版，作者也会提供可以动手实践的DIM-SUM操作系统源代码，以及实践环境的搭建方法。本书中也对DIM-SUM操作系统源代码进行了逐行注释。这有利于读者亲自动手实践，也有利于业界同仁参与到DIM-SUM操作系统的开发工作中来。
DIM-SUM操作系统已经具备了中断、调度、内存管理、文件系统、I/O、网络等操作系统的基本要素，并且具备与Linux应用生态兼容的能力。因此，它不仅可供读者学习操作系统的设计与实现，也具备发展成为实用服务器操作系统的潜在能力。推荐对操作系统有兴趣的在校学生、一线工程师阅读本书。
“路漫漫其修远兮”，希望10年后，DIM-SUM操作系统能够在生产系统中发挥作用，也希望更多的人加入到DIM-SUM的开发中来。
西安邮电大学 陈莉君

前  言

如果说DIM-SUM操作系统是一个完美的操作系统，那无疑是一个谎言。如果说DIM-SUM操作系统只是大家茶余饭后的谈资，那无疑是另一个谎言。
30年前，计算机逐渐进入公众的视野。笔者在使用DOS操作系统命令的时候，就对操作系统非常好奇，想搞清楚系统如何启动并响应输入的命令。于是在同学的帮助下，笔者将部分DOS操作系统文件进行了反汇编，通过阅读汇编代码的方式了解到一些操作系统的知识。
那时很难找到硬件相关的资料，也没有合适的操作系统设计方面的书。因此，笔者对操作系统的探索只能浅尝辄止。
但是，这并没有引起笔者对国内操作系统现状的担忧，因为笔者曾看到一则报道，从20世纪80年代中期开始，国内就有专家团队在系统性地研发国产操作系统、编译器这样的基础软件。我们只不过是落后一些时日，迟早会有自研操作系统问世的。
在20世纪90年代，Linux和BSD操作系统慢慢发展成为可用于生产的稳定操作系统。由于这些操作系统是开源的，所以在全球范围内得到了极大的普及，这也间接压缩了自研操作系统的生存空间。
另外，从20世纪80年代开始，自研的国产操作系统终都失败了，国内工程技术人员和研究者纷纷开始基于Linux开展他们的工作。
进入21世纪以后，Linux在国内发展得如火如荼。虽然“核高基”项目仍然坚持在操作系统领域投入数十亿元人民币，但是从笔者亲身参与的操作系统项目来看，这些项目均以Linux为基础，严格来说，并不是从头开始自研的操作系统。
笔者对这样的现状深感忧心，在2010年就预测Android系统可能会走向封闭，或者限制国内厂商的使用。可惜业界同人对此不以为然，认为国内可以基于Android系统持续使用。
从目前的现状来看，谷歌公司已经开始限制国内厂商使用Android系统了。这进一步加深了笔者的担忧：如果某一天，我们不能免费使用基于Linux的这些开源操作系统，我们是否有替代操作系统可用？
正是这样的忧患意识，促使笔者潜心研究Linux开源操作系统。从2008年进入中兴通讯操作系统团队开始，在随后的6年时间内，笔者利用业余时间认真阅读了《深入理解Linux内核》、《深入理解Linux网络内幕》、《深入理解Linux虚拟内存管理》，以及其他一些与存储、网络相关的内核图书，并做了2200页、88万字的学习笔记，同时翻译并出版了《深入理解并行编程》一书。
在潜心研究Linux之时，笔者也尝试编写自研操作系统DIM-SUM，并在2018年完成了个版本：HOT-POT操作系统。业界同人亲切地将这个系统称为火锅操作系统。笔者是四川人，在成都生活了将近30年，对火锅有一种亲切感，因此将个版本命名为HOT-POT。
实际上，DIM-SUM仅仅是一个快速原型操作系统，它可以运行在ARM 64 的QEMU模拟器中。读者可以随便找一台机器，通过QEMU模拟器将它运行起来。在这个原型操作系统中，实现了同步与互斥、调度、内存、中断、定时器、块设备、文件系统模块，并且有一个简单的命令行控制台。虽然它的很多思想是借鉴Linux的，你甚至可以毫不留情地批评这个操作系统大量抄袭了Linux，但是笔者可以自豪地声称：DIM-SUM操作系统进行了重大的代码重构，同时也有不少原创的元素包含在里面。在一线工作的工匠程序员们应该会满含热泪地认同这项工作的艰辛。
本书详细阐述了自研操作系统DIM-SUM的设计与实现，提供了在ARM 64虚拟机中动手实践DIM-SUM及参与DIM-SUM开发的方法。本书也针对DIM-SUM操作系统的各个模块进行了详细的分析，包括这些模块的设计思路、数据结构定义、关键API说明。本书的特点是对各个模块的主要函数进行了逐行解释，这样有助于读者深刻理解如何实现一款实用的操作系统。
后，本书还展望了接下来

本书详细阐述了自研操作系统DIM-SUM的设计与实现，提供了在ARM 64虚拟机中动手实践DIM-SUM及参与DIM-SUM开发的方法。针对DIM-SUM操作系统的同步与互斥、调度、内存、中断与定时器、块设备、文件系统模块进行了详细的分析，包括这些模块的设计思路、数据结构定义、关键API说明。*重要的是，本书对各个模块的主要函数进行了逐行解释，有助于读者深刻理解如何实现一款实用的操作系统。*后，本书还展望了接下来10年DIM-SUM操作系统的发展目标，希望*终其能发展为可以在服务器系统、桌面系统中实用的自研操作系统。

谢宝友，曾任中兴嵌入式实时操作系统技术总工，该系统获第四届中国工业大奖；中兴通讯2010年度金银奖获得者；阿里集团2019年度安全生产之星金奖获得者；2018年和2019年阿里集团“双11”卓越贡献奖获得者；《深入理解并行编程》译者；Linux ZTE架构维护者；DIM-SUM自研操作系统发起者和创始人。

第 1章 准备工作 1 
1.1 DIM-SUM简介 1 
1.2 DIM-SUM是什么 1 
1.2.1 DIM-SUM的个版本为什么是HOT-POT 1 
1.2.2 DIM-SUM欢迎什么 2 
1.2.3 DIM-SUM不欢迎什么 3 
1.3 获得源代码 3 
1.3.1 通过网页下载源代码 3 
1.3.2 通过Git获取源代码 3 
1.4 搭建调试开发环境 4 
1.4.1 安装ubuntu 16.04 4 
1.4.2 ubuntu 16.04环境配置 5 
1.4.3 搭建编译环境 6 
1.4.4 编译HOT-POT 7 
1.4.5 运行HOT-POT 8 
1.4.6 开始调试 10 
1.5 向DIM-SUM操作系统提交补丁 11 
1.5.1 心态 11 
1.5.2 准备工作 11 
1.5.3 制作补丁 13 
1.5.4 制作正确的补丁 14 
1.5.5 发送补丁 16 
1.6 获得帮助 17 
1.7 提醒 17 
第 2章 算法基础 18 
2.1 链表 18 
2.2 散列表 19 
2.3 红黑树 20 
2.4 基树 22 

第 3章 计数与互斥同步 23 
3.1 计数 23 
3.1.1 计数的难题 24 
3.1.2 精确计数器 24 
3.1.3 近似计数器 27 
3.1.4 引用计数 31 
3.2 内核互斥原语 32 
3.2.1 每CPU变量 32 
3.2.2 自旋锁 38 
3.2.3 自旋位锁 42 
3.2.4 自旋顺序锁 44 
3.2.5 自旋读/写锁 47 
3.2.6 读/写信号量 50 
3.2.7 互斥锁 56 
3.3 内核同步原语 60 
3.3.1 信号量的设计原理 60 
3.3.2 信号量的数据结构 61 
3.3. 3 信号量API 61 
3.3.4 信号量的实现 62 
第 4章 调度 65 
4.1 基本概念 65 
4.1.1 进程和线程 65 
4.1.2 任务 66 
4.1.3 任务抢占 66 
4.1.4 idle线程 66 
4.2 SMP CPU初始化 66 
4.3 数据结构 71 
4.3.1 线程 71 
4.3.2 调度队列 76 
4.3.3 杂项 77 
4.4 调度子系统初始化 77 
4.4.1 init_sched_early函数 78 
4.4.2 init_idle_process函数 78 
4.4.3 init_sched函数 79 
4.5 线程调度 79 
4.5.1 上下文切换 79 
4.5.2 唤醒线程 82 
4.6 高级调度API 85 
4.6.1 等待队列 85 
4.6.2 位等待队列 89 
4.6.3 线程睡眠 93 
4.6.4 消息队列 96 
第 5章 中断及定时器 108 
5.1 中断控制器初始化 108 
5.1.1 主CPU中断控制器初始化 109 
5.1.2 从CPU中断控制器初始化 110 
5.2 中断控制器维护 110 
5.2.1 中断号映射 110 
5.2.2 逻辑中断的控制 113 
5.2.3 设备中断处理函数 116 
5.3 中断处理 119 
5.3.1 序言 119 
5.3.2 中断处理通用流程 120 
5.3.3 处理外部设备中断 122 
5.3.4 处理核间中断 126 
5.3.5 软中断 126 
5.3.6 尾声 126 
5.4 工作队列 128 
5.4.1 工作队列的数据结构 128 
5.4.2 工作队列的全局变量 130 
5.4.3 工作队列的API 130 
5.4.4 工作队列的实现 131 
5.5 定时器与时间管理 139 
5.5.1 初始化 139 
5.5.2 定时器的数据结构 139 
5.5.3 定时器的全局变量 141 
5.5.4 定时器的API 141 
5.5.5 定时器的实现 141 
5.5.6 定时器中断处理 144 
5.5.7 时间管理 148 
第 6章 内存管理 151 
6.1 内存初始化 151 
6.1.1 艰难地准备C运行环境 151 
6.1.2 准备BOOT内存空间 152 
6.1.3 物理内存块管理 152 
6.1.4 早期设备内存映射 153 
6.1.5 初始化每CPU变量 157 
6.1.6 初始化线性映射 157 
6.1.7 其他内存初始化工作 160 
6.2 BOOT内存分配器 160 
6.2.1 BOOT内存分配API 161 
6.2.2 BOOT内存分配器的实现 161 
6.2.3 BOOT内存分配器的销毁 163 
6.3 页面编号 163 
6.3.1 页面编号的数据结构 164 
6.3.2 页面编号的全局变量 165 
6.3.3 页面编号的API 165 
6.3.4 页面编号的实现 165 
6.4 页面分配器 168 
6.4.1 页面分配器的设计原理 168 
6.4.2 页面分配器的数据结构 169 
6.4.3 页面分配器的全局变量 174 
6.4.4 页面分配器的API 175 
6.4.5 页面分配器的实现 176 
6.4.6 页面分配器的初始化 192 
6.5 Beehive内存分配器 193 
6.5.1 Beehive内存分配器的设计原理 193 
6.5.2 Beehive内存分配器的数据结构 195 
6.5.3 Beehive内存分配器的全局变量 197 
6.5.4 Beehive内存分配器的API 199 
6.5.5 Beehive内存分配器的实现 199 
6.5.6 Beehive内存分配器的初始化 214 
6.6 I/O内存映射 216 
第 7章 块设备 219 
7.1 磁盘及其分区 220 
7.1.1 磁盘及其分区的数据结构 220 
7.1.2 磁盘及其分区的全局变量 222 
7.1.3 磁盘及其分区的API 222 
7.1.4 磁盘及其分区的实现 222 
7.2 块设备维护 228 
7.2.1 块设备的数据结构 228 
7.2.2 块设备的全局变量 230 
7.2.3 块设备的API 231 
7.2.4 块设备的实现 231 
7.3 I/O请求 242 
7.3.1 I/O请求的数据结构 243 
7.3.2 I/O请求的全局变量 250 
7.3.3 I/O请求的API 250 
7.3.4 I/O请求的实现 251 
7.4 I/O调度 265 
7.4.1 I/O调度的数据结构 265 
7.4.2 I/O调度的全局变量 267 
7.4.3 I/O调度的API 267 
7.4.4 I/O调度的实现 268 
第 8章 虚拟文件系统 271 
8.1 挂载、卸载文件系统 271 
8.1.1 挂载、卸载文件系统的数据结构 272 
8.1.2 挂载、卸载文件系统的全局变量 277 
8.1.3 挂载、卸载文件系统的API 278 
8.1.4 挂载、卸载文件系统的实现 278 
8.2 文件节点缓存 285 
8.2.1 文件节点缓存的数据结构 286 
8.2.2 文件节点缓存的全局变量 288 
8.2.3 文件节点缓存的API 289 
8.2.4 文件节点缓存的实现 290 
8.3 打开、关闭文件 304 
8.3.1 打开、关闭文件的数据结构 305 
8.3.2 打开、关闭文件的全局变量 308 
8.3.3 打开、关闭文件的API 309 
8.3.4 打开、关闭文件的实现 309 
8.4 读/写文件 319 
8.4.1 读/写文件的数据结构 320 
8.4.2 读/写文件的全局变量 323 
8.4.3 读/写文件的API 323 
8.4.4 读/写文件的实现 323 
8.5 其他功能 337 
第 9章 杂项文件系统 338 
9.1 文件系统的挂载 338 
9.1.1 次加载根文件系统 338 
9.1.2 第二次加载根文件系统 340 
9.2 内存文件系统 340 
9.2.1 内存文件系统的数据结构 340 
9.2.2 内存文件系统的全局变量 340 
9.2.3 内存文件系统的API 341 
9.2.4 内存文件系统的实现 341 
9.3 设备文件系统 349 
9.3.1 设备文件系统的数据结构 349 
9.3.2 设备文件系统的全局变量 350 
9.3.3 设备文件系统的API 351 
9.3.4 设备文件系统的实现 351 
第 10章 LEXT3文件系统 358 
10.1 简介 358 
10.1.1 超级块 359 
10.1.2 块组描述符 359 
10.1.3 块位图 360 
10.1.4 文件节点位图 360 
10.1.5 文件节点表 360 
10.1.6 文件节点 360 
10.1.7 文件日志 362 
10.2 LEXT3 363 
10.2.1 LEXT3的数据结构 363 
10.2.2 LEXT3的全局变量 371 
10.2.3 LEXT3的API 372 
10.2.4 LEXT3的实现 373 
10.3 文件系统日志 397 
10.3.1 日志的数据结构 397 
10.3.2 日志的全局变量 405 
10.3.3 日志的API 405 
10.3.4 日志的实现 406 
第 11章 杂项 438 
11.1 klibc 438 
11.2 网络子系统 440 
11.3 SIMPLE-KSHELL 440