outline.md

更新记录

2021-01-04更新：

Chaptter4 添加实现的过程描述：改进内存隔离的好处；

2020-12-20更新：

将文件描述符从 Chapter7 移动到 Chapter6。

2020-12-02更新：

根据讨论更新了 Chapter1-Chapter7 到分割线之前的内容作为 Tutorial 的第一部分，即让系统能够将所有的资源都利用起来。第二部分则讨论如何做的更好。在 12 月 26 日之前尽可能按照大纲完成多个不同版本的 demo。

https://shimo.im/sheets/wV3VVxl04EieK3y1/MODOC是目前的系统调用一览表，预计只需要实现 14 个系统调用就能初步满足要求。

2020-11-30更新：

更新了Chapter2。

合并了Chapter3/Chapter4为Chapter3，目前覆盖范围为Chapter1-Chapter5。

lab 设计：2020-11-01

可能的章节与代码风格

• 新 OS 实验的目的是：“强化学生对 OS 的整体观念”。OS的目的是满足应用需求，为此需要一定的硬件支持和自身逐步增强的功能。鼓励学生自己从头写（有参考实现）、强化整体观、step-by-step。
• 整个文档的风格是应用导向的，每个 step 的任务一定不是凭空而来、而是应用的需求。每一章都是为了解决一个应用具体需求而要求OS要完成的功能，这个功能需要一定的硬件支持。
• 每个章节给出完整可运行且带有完整注释（可以通过 rustdoc 工具生成 html 版）的代码。
• 文档中给出重要的代码片段（照顾到纸质版的读者，事实上在网页版给出代码的链接即可）而并不需要完整的代码，但是需要有完整的执行流程叙述，对于边界条件有足够的讨论。在文档中插入的代码不带有注释，而是将解释放到文档的文字部分。
• 类似xv6，每一章的小节描述一项小功能是如何实现的，不同小节之间可能有一定的先后关系，也有可能是并列的。
• 尽可能讲清楚设计背后的思想与优缺点。
• 在讲解OS设计方面，尽量做到与语言无关。在讲解例子的时候，应该有对应的C和rust版本。
• 在某些具体例子中，最好能体现rust比c强
• 2020-10-28：前几章 Chapter1-4 需要等具体实现出来之后再规划章节。

章节大纲

Chapter0 Hello world! 之旅（偏概述）

主要动机：

参考 csapp 第一章，站在一个相对宏观的视角解释一个非常简单的 hello world! 程序是在哪些硬件/软件的支持下得以编译/运行起来的。

helloworld.c 如何被编译器编译成执行程序，且如何被操作系统执行的。

gcc

strace

Chapter1 裸机应用（优先级1）

主要动机

支持应用进行计算与结果输出。

在裸机上输出 Hello world，就像在其他 OS 上一样。

app列表：

• hello_world：输出字符串
• count_sum：累加一维数组的和，并输出结果

备注：不需要输入功能

内核应完成功能

内存地址空间：

知道自己在内存的哪个位置。理解编译器生成的代码。

init：基本初始化

主要是硬件加电后的硬件初始化，以前是OS做，后面给BIOS, bootloader等完成初步初始化。OS需要知道内存大小，IO分布。

write函数：输出字符串

驱动串口的初始化，能够通过串口输出。

exit函数：表明程序结束

其它（不是主要的）：

在 qemu/k210 平台上基于 RustSBI 跳转到内核，打印调试信息，支持内核堆内存分配。

章节分布

基本上和第二版/第三版一致。注意需要考虑上面的应用和功能。

Chapter2批处理系统（优先级1）

主要动机

内核不会被应用程序破坏

用户程序

支持应用进行计算与结果输出。在裸机上输出 Hello world，就像在其他 OS 上一样。但应用程序无法破坏内核，但能得到内核的服务。

app列表：

• hello_world：输出字符串。
• count_sum：累加一维数组的和，并输出结果。

内核应完成功能

设置好内核和用户运行的栈，内核初始化完成后通过 sret 跳转到用户程序进行执行，然后在用户程序系统调用的时候完成特权级切换、上下文保存/恢复及栈的切换

按顺序加载运行多个应用程序。当应用程序出错（非法指令基于 RustSBI 不容易完成，比如访问非法的物理地址）之后直接杀死应用程序并切换到下一个。

新增系统调用

• sys_write：向串口写
• sys_exit： 表明任务结束。

实现备注

将编译之后的用户镜像和内核打包到一起放到内存上

分离用户和内核特权级，保护OS，用户需要请求内核提供的服务

Chapter3 分时多任务系统之一非抢占式调度（优先级1）

主要动机

提高整个应用的CPU利用率

多任务，因此需要实现任务切换，可采用如下方法：

• 批处理：在内存中放多个程序，执行完一个再执行下一个。当执行IO操作时，采用的是忙等的方式，效率差。
• 非抢占切换：CPU和I/O设备之间速度不匹配矛盾，程序之间的公平性。当一个程序主动要求暂停或退出时，换另外一个程序执行CPU计算。

>> 这时，可能需要引入中断（但中断不是本章主要的内容，如果不引入更好）。

用户程序

两个程序放置在一个不同的固定的物理地址上（这样不需要页表机制等虚存能力），完成的功能为：一个程序完成一些计算&输出，主动暂停，OS切换到另外一个程序执行，交替运行。

• count_multiplication：一维数组的乘法，并输出结果
• count_sum：累加一维数组的和，并输出结果
• [wyf 的具体实现]三个输出小程序，详见here

内核应完成功能

实现通过 sys_yield 交出当前任务的 CPU 所有权，通过 sys_exit 表明任务结束。需要为每个任务分配一个用户栈和内核栈，且需要实现类似 switch 用来任务切换的函数。

• sys_yield：让出CPU
• sys_exit：退出当前任务并让出 CPU

实现备注

重点是实现switch

当所有任务运行结束后退出内核

Chapter3 分时多任务系统之二 抢占式调度（优先级1）

主要动机

进一步提高整个应用的CPU利用率/交互性与任务之间的公平性

因此需要实现强制任务切换，并引入中断，可采用如下方法：

• 时钟中断：基于时间片进行调度
• （不在这里引入）串口中断：在发出输出请求后，不是轮询忙等，而是中断方式响应

用户程序

• [wyf 的具体实现]三个计算质数幂次的小程序，外加一个 sleep 的程序。here

内核应完成功能

实现时钟/串口中断处理，以及基于中断的基本时间片轮转调度

新增系统调用

• sys_get_time：返回当前的 CPU 时钟周期数

Chapter4 内存隔离安全性：地址空间（优先级1）

主要动机

• 更好地支持应用（包括内核）的动态内存需求。首先：在内核态实现动态内存分配（这是物理内存），这样引入了堆的概念
• 更好地支持在内核中对非法地址的访问的检查。在内核态实现页表机制，这样内核访问异常地址也能及时报警。
• 提高应用间的安全性（通过页机制实现隔离）
• 附带好处：应用程序地址空间可以相同，便于应用程序的开发

用户程序

应用程序与上一章基本相同，只不过应用程序的地址空间起始位置应该相同。而且这一章需要将 ELF 链接进内核而不是二进制镜像。

特别的，可以设置访问其他应用程序地址空间或是访问内核地址空间的应用程序，内核会将其杀死。

在用户库使用 sbrk 申请动态分配空间而不是放在数据段中。

内核应完成功能

• 内核动态内存分配器（对于 Rust 而言，对于 C 仍可以考虑静态分配）
• 物理页帧分配器
• 页表机制，特别是用户和内核地址空间的隔离（参考 xv6）
• ELF 解析和加载（在内核初始化的时候完成全部的地址空间创建和加载即可）

新增系统调用

• sys_sbrk：拓展或缩减当前应用程序的堆空间大小

建议实现过程：

1. 在Chapter1的基础上实现基本的物理内存管理机制，即连续内存的动态分配。
2. 在Chapter1的基础上实现基本的页表机制。
3. 然后再合并到Chapter3上。

Chapter5 进程及重要系统调用（优先级1）

主要动机

应用以进程的方式进行运行，简化了应用开发的负担，OS也更好管理

引入重要的进程概念，整合Chapt1~4的内容抽象出进程，实现一系列相关机制及 syscall

用户程序

shell程序 user_shell以及一些相应的测试

内核应完成功能

实现完整的子进程机制，初始化第一个用户进程 initproc。

新增系统调用

• sys_fork
• sys_wait(轮询版)
• sys_exec
• sys_getpid
• sys_yield更新
• sys_exit 更新
• sys_read：终端需要从串口读取命令

Chapter6 文件系统与进程间通信（优先级1）

主要动机

进程之间需要进行一些协作。本章主要是通过管道进行通信。

同时，需要引入文件系统，并通过文件描述符来访问对应类型的 Unix 资源。

用户程序

简单的通过 fork 和子进程共享管道的测试；

【可选】强化shell程序的功能，支持使用 | 进行管道连接。

内核应完成功能

实现管道。

将字符设备（标准输入/输出）和管道封装为通过文件描述符访问的文件。

新增系统调用

• sys_pipe：目前对于管道的 read/write 只需实现轮询版本。
• sys_close：作用是关闭管道

Chapter7 数据持久化（优先级1）

主要动机

实现数据持久化存储。

用户程序

多种不同大小的文件读写。

内核应完成功能

实现另一种在块设备上持久化存储的文件。

文件系统不需要实现目录。

新增系统调用

• sys_open：创建或打开一个文件

----------------------------分割线-------------------------------------------------

Chapter6 单核同步互斥（优先级1，需要划分为单核/多核两部分）

主要动机：

应用之间需要在操作系统的帮助下有序共享资源（如串口，内存等）。

解释内核中已有的同步互斥问题，并实现阻塞机制。

内核应完成功能：

实现死锁检测机制，并基于阻塞机制实现 sys_sleep 和 sys_wait 以及 sys_kill

新增系统调用：

sys_sleep 以及 sys_wait/sys_kill 的更新

章节分布：

基于原子指令实现自旋锁

• 讨论并发冲突的来源（单核/多核）
• 关中断/自旋/自旋关中断锁各自什么情况下能起作用，在课上还讲到一种获取锁失败直接 yield 的锁
• 原子指令与内存一致性模型简介
• 具体实现
• 需要说明的是，课上的锁是针对于同一时刻只能有一个进程处于临界区之内。但是 Rust 风格的锁，也就是 Mutex 更加类似于一个管程（尽管 Rust 语言并没有这个概念），它用来保护一个数据结构，保证同一时间只有一个进程对于这个数据结构进行操作，自然保证了一致性。而 xv6 里面的锁只能保护临界区，相对而言对于数据结构一致性的保护就需要更加复杂的讨论。

死锁检测

阻塞的同步原语：条件变量

简单讨论一下其他的同步原语。

• 课上提到的信号量和互斥量（后者是前者的特例）保护的都是某一个临界区

基于条件变量实现 sys_sleep

基于条件变量重新实现 sys_wait

更新 sys_kill 使得支持 kill 掉正在阻塞的进程

ChapterX IPC（优先级1）

主要动机：

应用之间需要交换信息

内核应完成功能：

• pipe
• shared mem

新增系统调用：

Chapter8 设备驱动（优先级2）

主要动机：

应用可以把I/O 设备用起来。

内核应完成功能：

实现块设备驱动和串口驱动，理解同步/异步两种驱动实现方式

背景知识：设备驱动、设备寄存器、轮询、中断

设备树（可选）

实现 virtio_disk 块设备的块读写（同步+轮询风格）

实现 virtio_disk 块设备的块读写（异步+中断风格）

实现串口设备的异步输入和同步输出

• 参考 xv6，可以在内核里面维护一个 FIFO，这样即使串口本身没有 FIFO 也可以

Chapter9 Unix 资源：文件（优先级1）

主要动机：

应用可以通过单一接口（文件）访问磁盘来保存信息和访问其他外设

Unix 万物皆文件，将文件作为进程可以访问的内核资源单位

内核应完成功能：

支持三种不同的 Unix 资源：字符设备（串口）、块设备（文件系统）、管道

新增系统调用：

sys_open/sys_close

背景知识：Unix 万物皆文件/进程对于文件的访问方式

file 抽象接口

• 支持 read/write 两种操作，表示 file 到地址空间中一块缓冲区的读写操作

字符设备路线

• 直接将串口设备驱动封装一下即可。

文件系统路线

• 分成多个子章节，等实现出来之后才知道怎么写

管道路线

• 一个非常经典的读者/写者问题。

ChapterX 虚存管理（优先级2）

主要动机：

提高应用执行的效率（侧重内存）

• 支持物理内存不够的情况

• copy on write

内核应完成功能：

新增系统调用：

Chapter10 多核（可选）

主要动机：

提高应用执行的并行执行效率（侧重多处理器）

内核应完成功能：

新增系统调用：

多核启动与 IPI

多核调度

Chapter11多核下的同步互斥（可选）

主要动机：

提高应用并行执行下的正确性（侧重多处理器）

内核应完成功能：

新增系统调用：

多核启动与 IPI

多核调度

Appendix A Rust 语言快速入门与练习题

Appendix B 常见构建工具的使用方法

比如 Makefile\ld 等。

Appendix C RustSBI 与 Kendryte K210 兼容性设计

其他附录…