0%

开始

从暑假开始,我就打算重新学习操作系统的相关知识。最开始的打算是学习 Jyy 老师在今年上半年开的操作系统课程。可能是自己太菜了(对 Lab 和 Pa 完全没有思路)于是我转向了学习其前置课程 - 南大开的 ICS 课程。在暑假经过 PA 的一系列训练过后。 我觉得自己可以转向操作系统这座大山了。

此时,我突然看见 Rust 中文语言社区推的一个清华开源操作系统的学习活动。我抱着试一试的态度加入了(这就引出了下面的内容)

过程

第一阶段

老实的说,这一阶段对我而言更像是个“体力活”。在参加之前,我接触过 Rust 这门语言(这是另外一个故事)很巧的是我之前也写过 Rustlings (虽然没写完)

总的来说,这一阶段的训练更像是“康复训练” 唤醒了我对 Rust 的“感情” 🤪

第二阶段

第二阶段的训练相对于第一阶段而言对我更具挑战性,此前我完全没有接触过在线评测的实验这是其一,我从没有认真思考过 System Call 的行为。 我知道在 Linux 上可以通过 strace 来查看命令/程序在运行过程中使用过的 System Call 的行为。但对于具体的 System call 的行为,我并没有试着去思考过。这是我过去在学习过程中,没有考虑到的问题。从此看来,这比我具体学到什么编程方法/技巧,更值得记住。

由于学校课程安排和其他一些事情,让我无法静下心来完成第二阶段的所有训练。但在昨天基本都已经结束了。终于可以将重心放在完成剩下的训练上了!

小结

我认为知识一直存在在某个地方,只要在某一方面不断的探索就会发现的,但在前期的过程是如此的艰难,当我得知这个方面不只我一个人在探索,并时常有好消息传来。这相比起“找到”知识这件事本身更激励我。

可能是操作系统在大众眼中是神秘的、有挑战的让我周边没人敢去了解。但在这个时间的某些地方依旧有一群人在向它发起挑战。这件事对我来说有不一样的意义。

最后,我想向过去两周里默默付出的老师、助教们和群友们。在他们身上我看见了开源的精神和意义。

总体总结

​ 参与本次开源操作系统训练营,我开始学习了rust语言,rust语言的官方文档做得很好,rust语言圣经也很方便学习。不得不说,rust语言的学习十分陡峭,虽然在一阶段写了rustlings,在第二阶段完成了前三个lab,但是我感觉我对rust的语言理解还在比较浅的层次,生命周期和所有权的概念还有待加强,有时候我感觉我写的rust代码并不够rust,还是停留以前其他的编程语言观念,实际写代码的过程都是编译器在教导我如何写代码,通过报错和查看文档来解决问题。然后rcore的文档十分完整,既有操作系统概念上的阐述与总结,又有实践层面上的代码解释。在学习的过程中,我又加深了对操作系统的理解。

二阶段实验总结

​ 能够完成各个LAB的关键,是在于理解本章实现的操作系统的各个模块负责的功能,在通过阅读文档的解释,以及阅读代码进行理解后,才能知道要应该在哪个模块添加代码以实现功能。

LAB 1

​ 本章的操作系统是多道程序与分时操作系统,主要是需要理清多道程序是如何调度的。实验要求我们实验一个sys_taskinfo系统调用,来获取当前任务的任务信息。所以根据以前的操作系统知识,很自然的就能想到应该在进程控制块中加入我们需要收集的信息。我在实现的时候存在数据冗余问题,我先在TaskManagerInner中加入了一个任务信息Taskinfo字段,又加入了一个任务创建时间create_time字段,实际上Taskinfo.status和Taskinfo.time是多存的不必要的信息,因此我在后面的章节之后进行了重构,只加入了create_time和syscall_times两个字段。

LAB 2

​ 在本章节中,内核加入了虚拟空间机制,让进程的实现更加完整。实验要求我们移植get_time和taskinfo系统调用,并增加sys_mmap和sys_munmap系统调用。由于rcore的实现是双页表,内核页表和进程页表是分开的,进行系统调用的时候会切换页表,移植操作就需要进行地址转换拿到进程空间的地址来进行写入。内存映射的系统调用实现根据提示能做出来比较简单的实现便能通过测试,但是实际在取消内存映射的时候,可能需要对内存区域进行分割和合并的操作,例如可能会涉及内存管理算法什么的,似乎题目没做要求,我还没有实现,做完后续实验填坑吧。

LAB 3

​ 在本章节中,内核实现了进程机制,使得能够进程能够创建子进程(fork)、用新的程序覆盖已有程序内容(exec)。实验要求我们移植向前的代码并实现Spawn系统调用(fork+exec),再实现stride调度算法。

  • 在移植的过程中遇到的问题便是前两章记录进程创建时间是用get_time_ms函数,而在本章节中会因为精度不够而无法通过测试,改用get_time_us进行记录,返回任务存活时间时/1000便能得到结果。
  • 实现spwan系统调用,主要就是参考fork和exec的实现,将两者有机的结合起来,不需要复制父进程的内存空间,转而从elf文件中获取。
  • 实现stride调度算法:由于本章将TaskManager进行了拆分,调度实际是再manager中进行,根据提示,将原先的双端队列替换成小顶堆,在任务调出时对stride进行+pass,调度任务的时候每次从小顶堆中弹出stride值最小的进程便能实现。主要难点是BinaryHeap的使用。

Lab 4&5 to be continue.


#关于Rust

之前从未了解过这门语言,想来学习它快有一个月了,感觉和传统的C系语言大不相同,尤其是刚开始学习时,最为痛苦,完全陌生。但随着学习的深入,了解到其相关特性,又不得不承认其设计的巧妙,希望能够在以后的日子,多些相关代码,进一步提升自己的Rust编程水平。

#关于操作系统

之前对于操作系统的了解仅仅停留在书本上面,对于相关代码和具体实现细节,也是知之甚少,所以在第二阶段的时候,感觉进展缓慢,但好在随着学习的深入,总算能解决一些问题,能够有所收获。

#关于未来学习计划

希望在将来,能够在训练营中学到更多有用的东西,感谢训练营的老师们,提供了这么一个好的环境,感谢!

开始阶段

有一年私有云平台开发经验的 Go 开发工程师,有些许的 Rust 基础, 没有 Rust 相关的项目,对操作系统相关的东西一知不解。

在群友的闲聊下发现有 “Linux 源码趣读” 的系列文章,趁空闲的时间过了一遍,对操作系统的整体结构有一定认识,群友说这个讲的蛮浅显的,但是感觉对我这种没有啥操作系统基础的还是有很大的帮助的。

学习感受

一章一章的剥开操作系统的面纱,硬件机制、操作系统理论整体联络起来,渐渐实现一个可用的操作系统。

就目前完成到 ch5 来讲,Guide 的 ch4、ch5 的这部分内容不怎么连贯,基础比较差的我就只能硬读了。听说 rCore-Tutorial V3 的内容更全一点,等后面也对照这学习一下每章节的内容。

学习总结

似乎任何事情都逃不过这句话:“会者不难, 难者不会”,真正的难其实是对未知的恐惧。目前算是完成了这次训练营的基本过线目标:完成前三个作业。现在回头来看,都无非是对操作系统概念的学习和理解,并把这些理解到的概念真正转化成工程代码的一个过程。例如实验中你本就拥有一个完整的模拟环境,运算设备、硬件机制、目前标准的系统调用接口参考、经典理论(SV39 分页机制)等等,需要用自己理解操作系统概念去把这些东西组合在一起,最终提供一个基于底层基础设备提供的机制,为上层用户提供一个可靠的、安全的运行环境。

未知的事物并不可怕,可怕的是你认为它是永远无法被理解的。

ch0

这一部分是构建实验环境:本质上就是安装 Rust 工具链和编译安装 Qemu 模拟器。在尝试使用 classroom 在线环境失败后,决定本地部署环境。据目前所了解到的虚拟环境模拟工具来看(需要一个 Ubuntu 的系统环境),有传统虚拟机软件(Parallel、VMWare 等)、MutilPass(Ubuntu 系统特供)以及更加流行的 Docker 容器模拟,由于对桌面环境不是强需便直接排除了,、MutilPass 和 Docker 自己都比较熟悉,因更倾向于 MutilPass 的使用方式,所以最开始拿 MutilPass 创建的 Ubuntu 虚拟机安装环境,通过 VSCode 的 ssh 插件直接远程虚拟机开始基础环境部署,运行第一个 “Hello World!”。

后续训练营的群友有推荐使用 Orbstack 这款软件,了解之下发现确实好用,随而更换到这个软件,它的优势:
1、共享宿主机内核:CPU 全部共享到虚拟机、内存几乎接近全部也是给到虚拟机,创建一个 Ubuntu 虚拟机只要十几秒。
2、提供 Docker 命令:可以替换掉 Docker, 又可以少装一个软件了。
3、提供单节点 K8s 集群:像 Docker 一样,更加轻量、启动快。
4、唯一缺点:目前只支持了 MacOS 系统(刚好是 Mac),可能是因为是使用 Swift 开发的,看后续是否会支持 Linux。

ch1

这一部分主要是一步一步的讲解了如何从零开始构建一个可以运行在 Qemu 上的 Rust 操作系统程序:Hello World!,接触到了一些基础概念:系统级标准输出、系统级异常处理、内存基本布局,这些在具体的代码转化后是如何展现的,以及操作系统的入口:entry.asm 文件。

简单来讲,系统加电后会固定去读区特定的位置,也就是操作系统入口文件里的这部分内容,从而就进入了我们编写的 Rust 操作系统程序的 rust_main 入口,当然固定读取的操作是硬件提供的。

ch2

这一部分实现一个最简单的批处理系统。电脑内存本质上就只一个线性的存储结构:这一部分将系统程序需要占用的部分之外的存储结构以固定的布局方式排列在内存上,通过一个程序一个程序的加载执行来达到一次运行可以完成多个任务的系统。这部分也涉及到了 SU 态相关的东西。

ch3

操作系统在一定程度来讲算是一个处于“死循环”的程序,因为各种“中断”操作将读写设备、CPU 计算、任务处理等灵活的控制起来。这部分主要利用了“时钟中断”和任务切换这两部分内容来完成了一个分时多任务系统,通过时钟控制 CPU 不被某个程序长时间占用,这也是最基本的任务调度实现。

这一章的作业是提供一个系统调用来获取当前执行任务的基本信息,不考虑其他影响因素:也就是记录任务的启动时间、各种系统调用的次数和状态,当前已经存在“任务”的存储模型 Task,在其中记录信息并在状态流转处记录即可。

ch4

这一章介绍了 SV39 多级页表机制理论,基于该理论实现了实验里的多级页表,物理地址、虚拟地址的基本定义和对应的基本操作,以及 MMU 机制和 sapt 的理论定义模型,包含了对多级页表的重要解释,同时也通过图介绍了整个内存中操作系统和用户程序的布局。

这一章的作业是在开启多级页表机制下,适配 ch3 的作业实现,并完成 内存分配 mmap、和内存释放 mummap 系统调用: 基本的思路就是如何在多级分页开启的时候从内存获取到对应数据结构的地址并赋值,有物理地址和虚拟地址间的转换、页表的访问权限设置相关的内容。

ch5

这一章基于多级页表机制对任务执行这块进行再次抽象,加入了任务编号、任务队列管理,主要是对任务抽象的部分是需要花些时间需要理解理解。

这一章的作业是老作业迁移适配外,在实现 spawm 和 priority 系统调用接口功能:最主要的还是在对分级页表比较熟悉的情况下,对已经实现的任务管理功能,如 exec、fork 等实现的理解后,spawn 其实就是创建一个新的 TaskControlBlock 并添加到任务队列,并绑定给当前 TaskControlBlock 的 child 下,但同时也别忘记了给这个新的 TaskControlBlock 绑定 parent。另一个 priority 就用户可以设置这个值来简单的控制下程序执行的顺序,来让某些程序优先执行。

后续计划

看时间情况继续学习后续的 ch6、ch7、ch8 的内容,完成整个训练营任务。

前言

不得不承认,自己的代码量在面对这五个实验的时候显得捉襟见肘。由于在此之前我没有进行任何项目的书写,或者说我只写过单独的 code.c 这样的东西,这次实验对我是一个不小的挑战。再加上初次接触 Rust 一些语言特性:闭包、各种集合也让我有点吃力。但万幸最近时间比较充裕,可以花充分的时间来做这件事,整个实验花费了两周的时间,将近五个小时,很少有过的这么快的时间了。

实验总结

由于我对实验的整个框架的了解也不是那么清楚,我只能以写实验时候进行的猜想来对这五个实验进行总结。

lab1

第一个实验让我实现获取进程信息。在基本的操作系统的理解下,我们应该知道进程的信息应该存储在进程控制块(process control block, PCB)中。但 task.rs 并没有向我们暴露什么可以直接访问的接口,而在 mod.rs 中,我们可以发现其实例化了一个 TaskManager,所以我们在这个文件中增加一个函数 get_tcb() 来获取当前进程的进程控制块,然后将信息传递给 TaskInfo 结构体即可。

lab2

第二个实验中向外提供的接口并没有发生变化,仍然是 task/mod.rs 下实例化的 TaskManager。而在进行这个实验之前,我们必须知道我们为什么要重写 sys_get_timesys_task_info。这是因为,我们传给系统调用的指针指向的地址为用户进程的虚拟地址空间中的虚拟地址,这是操作系统无法直接访问的,需要增加一层指针转换的过程。知道了这一点之后,重写的任务就并不困难了。

sys_mmapsys_munmap 的实现,可能开始没有思路,但可以首先把书中所有可能出现的错误排除掉,之后我们进行映射时既可以选择虚拟地址也可以选择虚拟页号,我选择了虚拟地址。而我们进行地址空间的映射,必然需要用到 mm 这个 crate 下的内容。不难想到 mm/memeory_set.rs 是这次实验的重点。在其中我们看到了 MemorySet 这个结构体,而我们如何获得这个结构体呢,我们在 TaskManager 中找到了 TaskControlBlock 并且 TaskControlBlockInner 中有 memory_set 这个成员。然后我们寻找 MemorySet 中有哪些我们可以用到的方法。显然 sys_mmap 可以使用 insert_framed_area() 方法完成,之后我们仿照其实现 remove_framed_area() 方法用以实现 sys_munmap。这里我采用了遍历所有的虚拟地址页并释放页表的方法。而在遍历的过程中有两种选择:

  • 直接使用页表号
  • 使用 VPNRange 结构,进而使用迭代器

其中后者比较复杂,因为 VPNRange 没有直接暴露出来,需要改为 pub 属性并在 mod.rs 中导出,但由于后续实验中不再提供 ViruralPageNumber 的 step() 方法,所以有更好的兼容性。

lab3

实验三相较于前两个实验的变化比较大,首先就是我们不再提供 task/mod.rs 中的 TaskManager 结构体,而是将其放到了 task/manager.rs 中。而从这个实验开始如果我们想获取当前的进程使用 current_task() 这个方法(这里说的并不严谨,在实验五中引入线程之后,task 应该表示线程,但在这里还是进程)。同时一个比较偷懒的地方就是这个实验并不测试 sys_task_info 系统调用,我们可以选择不再实现。

sys_mmapsys_munmap 的实现和实验二是一样的,不多说。

sys_spwan 的实现开始让我有点困扰,因为最开始没有注意到 get_app_data_by_name() 这个方法。知道之后我们可以通过这个方法获取 ELF 文件的数据,再通过 TaskControlBlocknew() 方法新建进程控制块,之后我们需要设置当前进程的子进程和新创建进程的父进程,二者还是有一定不同的。之后将新建的进程加入队列即可。

而关于 stride 调度算法,整个算法没有什么难度,但我最开始没有想清楚这里的调度是指的就绪态的进程的调度,而纠结到底在 task/task.rs、task/processos.rs、task/manager.rs 中哪里实现。在看了 chapter 5 : 进程管理 后发现应在 manager.rs 中实现。这里只需要每次选择 stride 值最小的加入就绪队列即可,这里需要在 TaskControlBlock 中加入相应的内容。

sys_set_priority 比较简单,不多赘述。

lab4

这个实验不再检查 sys_task_info 和 调度算法,可以不用实现。

sys_mampsys_munmap 是一样的,不再赘述。

sys_spwan 变得不太一样了,因为我们有文件系统的出现,所以此时如果想要获取 ELF 的所有数据则要先获得其 inode,之后再进行,而我们调用 open_file() 函数来完成这件事情。

这个实验卡了我很长时间,主要是向外提供的 DiskInodeInodeOSInode虽然比较清楚,但还是很难确定什么时候用哪个,而且有些时候需要和 block_id 以及 block_offset 打交道还是比较麻烦的。然后有一点就是实例化了一个 ROOT_INODE 来惯例所有的内容,这里我开始很不理解为什么其他的文件需要用根目录的 inode 来进行管理,后来才发现需要在这里完成 DirEntry 的更新。我们首先根据 inode 获得文件的 block_id 和 block_offset,然后获取缓存并加锁,然后更新链接数目,之后再更新 DirEntry

sys_unlinkat 我的实现并不完整,但通过了测试。因为考虑到可能删除最后一个链接之后,我们需要清空 DirEntry,我选择了遍历现在的目录项,并将所有我们不 unlink 的目录项放到一个向量中,之后释放所有的目录项,将向量中的内容写入到目录项。而我所说的不完整,则是我没有实现如果 unlink 之后链接数不为零,需要将其写回目录项,我没有想太清楚如何实现这个事情。

lab5

首先我的实现稍显臃肿,因为 mutex 的思索检测可以不使用银行家算法来完成。而在这里我的整体思路则是通过修改 sync/mutex.rs 和 sync/semaphore.rs 中的结构体的内容,获得可以银行家算法中的三个向量。而在 mutex_lockdown 中更新三个向量,之后的思路如下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
let mut if_finish = vec![false; task_count];

loop {
let mut task_id: isize = -1;

for i in 0..task_count {
let mut task_id_can_run = true;

for j in 0..mutex_count {
if if_finish[i] || need[i][j] > available[j] {
task_id_can_run = false;
break;
}
}

if task_id_can_run {
task_id = i as isize;
break;
}
}

if task_id == -1 as isize {
break;
}

// 释放可以运行的线程的资源
for i in 0..mutex_count {
available[i] += allocated[task_id as usize][i];
if_finish[task_id as usize] = true;
}
}

for i in 0..task_count {
if !if_finish[i] {
return -0xdead;
}
}

如果找到不能运行的线程则发生死锁。

后记

这次的实验过程还是比较艰难的,而且最开始得知只有两周的时间,加之自己 Rust 基础并不好,所以最开始写的很是急躁,但后来平复一下,开始慢慢自己猜整体框架的思路,以及找一些自己可以用到 API,有点没想到自己可以完成这五个实验。在这个过程中参考了:

非常感谢大家讲解自己的思路,也感谢上课的老师以及群友。

前言

rCore实验参考文档: rCore-Tutorial-Guide-2023A 文档

几年前便久闻Rust大名, 想入门但不得其法.

去年初学操作系统, 阅读的uCore文档, 但因自身水平过低, 看了几章就败下阵来, 抄抄答案草草收场. 当时也听说还有个rCore版本, 但囿于各种事务缠身, 最后不了了之.

今年兜兜转转, 还是捧起操作系统, 参加了老师推荐的训练营, 没想到是rCore, 令人感叹. 时间有限, 未能观看网课, 颇为遗憾. 所幸文档内容足够丰富, 获益匪浅.

CRust, 从X86RV64, 系统的实现方法大相径庭, 但终归也有不变之处, 或许能看清这部分, 才能明晰操作系统吧. 去年对操作系统一无所知的我没能看清, 今年的我, 但愿能略窥一二.

以下为这两个阶段所遇到的一些问题和记录

Rust

啃书. 阶段一的题目倒也亲民.

ch0 配置环境

按部就班, 参照文档.

工作环境为WSL2-Ubuntu_18.

编译 qemu 的时候出错, 提示can't find ninja

ch1: 应用程序与基本执行环境

rust-analyzer 报错

使用#![no_std]时候, rust-analyzer提示错误, 但是可以编译, 无伤大雅

echo 的用法

打印上一条指令返回给系统的退出信号

1
qemu-riscv64 target/riscv64gc-unknown-none-elf/debug/os; echo $?

QEMU 的使用

两种运行模式

  • User mode: 即用户态模拟,如qemu-riscv64, 能够模拟不同处理器的用户态指令的执行, 可以直接解析ELF文件
  • System mode: 即系统态模式, 如qemu-system-riscv64程序, 模拟一个完整的硬件系统, 包括处理器、内存及其他外部设备

参数

1
2
3
4
5
qemu-system-riscv64 \
-machine virt \
-nographic \
-bios $(BOOTLOADER) \
-device loader,file=$(KERNEL_BIN),addr=$(KERNEL_ENTRY_PA)
  • -machine virt: 预设模拟的机器
  • bios $(BOOTLOADER): 指定BootLoader程序文件路径
  • device loader,file=$(KERNEL_BIN),addr=$(KERNEL_ENTRY_PA): 将file指定路径的文件, 加载到模拟的内存中的addr位置

执行上述命令, 将会执行:

  • 机器加电, 此时通用寄存器清零, PC指向0x1000, 即ROM引导代码
  • 很快跳转到0x80000000, 即bootloader处, 完成初始化, 接着跳转到内核位置, rustSBI默认内核在0x80200000处.
  • 跳转到$(KERNEL_BIN), 执行操作系统的第一条指令。

链接器脚本

链接脚本 (Linker Script): 使得最终生成的可执行文件的内存布局符合我们的预期

cargo设置

  • -Clink-arg=-Tsrc/linker.ld: 设置链接器脚本linker.ld路径
  • -Cforce-frame-pointers=yes: 强制编译器生成带有帧指针(frame pointer)的代码, 以便进行调试和异常处理等操作

rCORElinker.ld

  • 架构OUTPUT_ARCH(riscv)
  • 入口ENTRY(_start)
  • 定义全局变量BASE_ADDRESS = 0x80200000;, 这是RustSBI 期望的内核起始地址
  • 定义全局变量skernel = .;ekernel = .;, 意思是kernel段的起始和结束地址
    • 可以在rust里用extern "C" {skernel();}拿到skernel的地址
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      OUTPUT_ARCH(riscv)
      ENTRY(_start)
      BASE_ADDRESS = 0x80200000;

      SECTIONS
      {
      . = BASE_ADDRESS;
      skernel = .;
      // ...
      }

ch2: Trap

用户库

用户库里实现_start:

  • 和大多数libc一样, 提供了csu, 完成在用户main()之前的环境设置, 以及main()之后的收尾工作.
  • #[link_section = ".text.entry"], 在linker.ld里, 将这个段放在了.text的最开始, 即入口
    1
    2
    3
    4
    5
    6
    7
    #[no_mangle]
    #[link_section = ".text.entry"]
    pub extern "C" fn _start(argc: usize, argv: usize) -> ! {
    clear_bss();
    // ...
    exit(main(argc, v.as_slice()));
    }

用户库里实现 main:

  • #[linkage = "weak"]弱链接, 即c里的weak_alias
  • 如果用户没有提供main(), 将会链接这个进去, 这样就不会在链接阶段报错, 而是会在运行时报错(额, 行吧)
    1
    2
    3
    4
    5
    #[no_mangle]
    #[linkage = "weak"]
    fn main(_argc: usize, _argv: &[&str]) -> i32 {
    panic!("Cannot find main!");
    }

链接脚本

我们使用链接脚本 user/src/linker.ld 规定用户程序的内存布局:

  • 将程序的起始物理地址调整为 0x80400000 ,三个应用程序都会被加载到这个物理地址上运行;
  • 将 _start 所在的 .text.entry 放在整个程序的开头 0x80400000; 批处理系统在加载应用后,跳转到 0x80400000,就进入了用户库的 _start 函数;
  • 提供了最终生成可执行文件的 .bss 段的起始和终止地址,方便 clear_bss 函数使用。

问题: user/src/linker.ld 实际上不是 0x80400000 而是 0x0?

  • 解决: 文档里说是用了 linker.ld, 实际上根本没用, 用的是 build.py

risc-v 通用寄存器, CSR, ABI

参考知乎

RISC-V 寄存器编号从 031 ,表示为 x0x31 , 对应 abi 如下

  • x0: 零寄存器
  • x1: ra
  • x2: sp
  • x3: gp(通用指针)
  • x4: tp(线程指针)
  • x5: t0(临时寄存器或备用链接寄存器)
  • x6x7: t1t2(临时寄存器)
  • x8: s0/fp(帧指针)
  • x9: s1(需要保存的寄存器)
  • x10x11: a0a1(参数/返回值)
  • x12x17: a2a7(参数)
  • x18x27: s2s11(需要保存的寄存器)
  • x28x31: t3t6(临时)

对于 syscall:

  • a0~a6 参数
  • a0 返回值
  • a7 用来传递 syscall ID。

仅考虑U特权级触发Trap, 并切换到S特权级, 相关CSR如下

  • sstatus: 用SPP等字段给出Trap处在哪个特权级
  • sepc: 记录触发Trap的指令地址
  • scause: Trap原因
  • stval: Trap附加信息
  • stvec: Trap处理代码的入口地址

发生Trap时, 硬件会自动完成如下这些事情

  • 修改sstatusSPP字段
  • 修改sepc, scause, stval,
  • 跳转到stvec指定的地址, 并修改特权级为S

stvec相关细节

  • MODE 位于 [1:0], 若为00, 则意味着Direct模式, 无论Trap原因如何, 处理入口都是BASE<<2
  • BASE 位于 [63:2], 表示处理入口

Trap返回, 使用S特权级的特权指令: sret, 硬件会完成以下功能:

  • 将当前的特权级设置为 sstatus 的 SPP 字段
  • 跳转到 sepc 寄存器指向的指令

lazy_static

外部库lazy_static提供的宏lazy_static!: 全局变量运行时初始化

  • 默认下, 全局变量必须在编译期设置初始值, 但有些全局变量需要运行时数据才能初始化
  • lazy_static!声明的全局实例, 只有第一次被使用到的时候才会初始化

riscv 汇编

fence.i: 清理i-cache:

  • 切换应用会修改会被CPU取指的内存区域, 使得i-cache和内存不一致
  • 使用指令手动清空, 让里面所有的内容全部失效

.align 2: 4 字节对齐, 这是 RISC-V 特权级规范的要求

csrrw rd, csr, rs: 将csr写入rd, 再将rs写入csr

宏:

  • 启用宏功能.altmacro
  • 宏开始.macro NAME ARG
  • 宏结束.endm

循环伪指令.rept, 循环结束.endr

如何启动第一个应用

操作系统初始化完成之后, 处于S特权级, 通过sret, 可以切换到U特权级运行应用, 而之前要完成如下这些工作:

  • 跳转到应用程序入口点, 假设是0x80400000
  • 切换到用户栈
  • __alltraps时我们要求sscratch指向内核栈, 在这里完成
  • 切换特权级

通过复用__restore的代码来实现上述工作

  • 在内核栈上压入一个伪造的Trap上下文
  • 调用__restore函数, 让这些寄存器到达启动应用程序所需要的上下文状态

ch3: 分时任务管理

任务切换的流程

流程

  • 初始是操作系统在运行
  • os 把所有任务导入内存, 并为他们初始化了 task 结构(tcb): s0~11, ra, sp, 状态(ready)
    • ra 指向 __restore
    • sp 指向 任务上下文: 即这个任务的所有寄存器内容, 一般在下处理机之前保存, 但是因为是初次运行, 所以初始由 os 虚构.
  • os 启动第一个任务 task0: 将其设置为 running, 调用 __switch(_unused, task0)
  • __switch 把当前的 s0~11, ra, sp 保存到 _unused 指向的 task 结构里, 再把 task0 指向的 task 结构里的内容恢复到对应寄存器, ret
  • 此时会返回到 ra 指向的, 也就是 __restore 里, 她根据 sp 指向的上下文, 把里面的东西恢复到寄存器里
    • 先恢复 sstatus, sepc, sscratch ; 再到通用寄存器x0~x31(x0(零), x2(sp), x4(tp)不需要恢复) ; 最后 sp ; sret
  • sret 发生降级, 根据 ra(x1) 返回执行, 而这个 ra 由 os 虚构, 指向 task 的第一行代码
  • 此时运行 task0 …
  • 该是任务切换的时候了! 下面是理由, 无论是哪个理由, 都会进入系统调用.
    • 理由1: 时钟中断, 发现时片用尽, 直接帮你切换
    • 理由2: 该任务主动放弃, sys_yield
  • 进入内核态, 开始系统调用, 第一件事就是保存当前上下文, 即 __restore 的反操作, 把所有关键寄存器入栈, 然后将 sp 设置为内核栈
  • 此时看看系统调用想干嘛: 原来是切换任务, 于是开始切换任务
  • 首先遍历任务数组, 找到一个 ready, 比如 task1, 设为 running, 再把当前任务设置为 ready, 然后进入 __switch(task0, task1)
  • __switch 一样的操作: 把 task0 的东西保存, 把 task1 的东西写入寄存器, 然后 ret
  • ret 又回到了 os 事先设计好的 __restore, 然后重复, task1 正式开始运行
  • 该是任务切换的时候了! 首先进入系统调用
  • 首先给 task1 保存当前上下文, 然后进入内核栈, 开始切换任务
  • 遍历任务数组, 找到一个 ready, 假设是 task0 吧, 设为 running, 把 task1 改为 ready, 然后 __switch(task1, task0)
  • __switch 把 task1 的东西保存, 把 task0 的东西写入寄存器: s0~s11, ra, sp, 然后 ret.
  • 有意思的来了: 这时候的 s0~11, ra, sp 是什么呢?
    • 回忆下 task0 当时在干嘛: 首先是 task0 进入内核态保存了用户态的上下文, 然后把 ready 和 running 互换, 然后 __switch
    • 所以 ra 应该是 __switch 的下一行, 因为调用完了要返回嘛, sp 就是此时的内核栈, s0~11 就是正在用的寄存器, 因为是被调用者保存的, 所以 __switch 得帮你保持原样.
  • 总之, __switch ret 了, 根据 ra, 回到 task0 在内核态里调用 __switch 的下一行, 回忆一下, 为什么进入内核态了?
    • 因为时钟中断/sys_yield
  • 所以 __switch 的下一行应该是系统调用返回, 怎么返回来着? 回一下系统调用的过程:
    • 首先是程序调用相关函数, 发生了 Trap
    • Trap 的入口是 all_trap
    • all_trap 进行用户态寄存器的保存, 然后修改 sp 指向内核栈, 然后调用 trap_handler, 参数是上下文
    • trap_handler 读取 scause, 发现是系统调用, 先修改上下文里的 pc(sepc)(让他+4), 然后根据系统调用号进行调用, 返回值存在上下文的 x10 里, 返回
    • all_trap 继续, 进行 __restore
  • 所以 __switch 的下一行应该是 __restore: 这不是完美对上了吗!
    • __restore 先恢复 sstatus, sepc, sscratch ; 再到通用寄存器x0~x31(x0(零), x2(sp), x4(tp)不需要恢复) ; 最后 sp ; sret
  • 这回回到了 task0 的上次停住的地方了, 一样的寄存器, 一点没变, 对于 task0 来说, 毫无感知
  • 继续运行!

为什么要 drop(inner):

  • 因为调用 __switch 之后这个 task 的状态就停滞在那里了, 转而运行别的 task 了
  • 但是任务切换本质只是 pc 和上下文改变, 所以这个 inner 实际上还处于被借用状态, 得等到 task0 恢复了, 并且从该函数返回了, 才能 drop, 在这之前没人可以再次借用

RISC-V 架构中的嵌套中断: 不会发生

默认情况下,当 Trap 进入某个特权级之后,在 Trap 处理的过程中同特权级的中断都会被屏蔽。

  • 当 Trap 发生时,sstatus.sie 会被保存在 sstatus.spie 字段中,同时 sstatus.sie 置零, 这也就在 Trap 处理的过程中屏蔽了所有 S 特权级的中断;
  • 当 Trap 处理完毕 sret 的时候, sstatus.sie 会恢复到 sstatus.spie 内的值。
  • 也就是说,如果不去手动设置 sstatus CSR ,在只考虑 S 特权级中断的情况下,是不会出现 嵌套中断 (Nested Interrupt) 的。

实验任务: 获取任务信息

任务介绍

引入一个新的系统调用 sys_task_info 以获取当前任务的信息,定义如下:

1
2
3
4
5
6
7
8
9
10
fn sys_task_info(ti: *mut TaskInfo) -> isize {  // ti: 待查询任务信息
// syscall ID: 410
// 返回值:执行成功返回 0,错误返回 -1
}

struct TaskInfo {
status: TaskStatus, // 任务控制块相关信息(任务状态), 一定是 Running
syscall_times: [u32; MAX_SYSCALL_NUM], // 任务使用的系统调用及调用次数, MAX_SYSCALL_NUM=500 。调用 `sys_task_info` 也会对本次调用计数。
time: usize // 系统调用时刻距离任务第一次被调度时刻的时长(单位ms)
}

实现思路

sys_task_info

  • 这也是个系统调用, 调用号为 410, 所以应该修改 syscall/mod.rs的…已经帮我改好了那没事了

status

  • task/mod.rs 里暴露一个接口 get_current_status()
  • 当然返回值肯定是 running

syscall_times

  • 存在哪里: 这是个程序本身强相关的数组, 所以要放入 tcb 里, 并且一开始就初始化
  • 如何记录: 每次 syscall 的时候, 进入 trap_handler, 如果是系统调用, 就拿到系统调用号index
    • task/mod.rs 里暴露一个接口 set_current_syscall_times(index), 修改数组里对应的地方 + 1
  • task/mod.rs 里暴露一个接口 get_current_syscall_times(), 返回这个数组

time

  • 存在哪里: 和程序本身强相关, 在 tcb 里记录第一次启动的时间first_start_time, 并且一开始就初始化
  • 如何记录: 当这个程序第一次被调用的时候, 修改first_start_time为当前时间.
    • 选择在task/mod.rsrun_next_task()里, 新增: 如果nextfirst_start_time为0, 就设置为当前时间
  • task/mod.rs 里暴露一个接口 get_current_first_start_time()

思考题: 虽然系统调用接口采用桶计数,但是内核采用相同的方法进行维护会遇到什么问题?是不是可以用其他结构计数?

  • 内核统计本身系统调用次数? 内核本身还需要系统调用?

ch4: 分页

后期补充: 本章内容繁多信息量大, 开头埋下的跳板伏笔迟迟不能回收, 增加了理解和记忆压力, 导致当时阅读得颇为吃力, 辛辛苦苦看了大半只觉头昏脑胀不知所云. 快结束时, 终有一段注解点明要义

目前我们的设计是有一个唯一的内核地址空间存放内核的代码、数据,同时对于每个应用维护一个它们自己的地址空间,因此在 Trap 的时候就需要进行地址空间切换,而在任务切换的时候无需进行(因为这个过程全程在内核内完成)。而教程前两版以及 ucore 中的设计是每个应用都有一个地址空间,可以将其中的逻辑段分为内核和用户两部分,分别映射到内核和 用户的数据和代码,且分别在 CPU 处于 S/U 特权级时访问。此设计中并不存在一个单独的内核地址空间。

颇有推理小说的风味, 开头倒叙留下悬念, 结尾反转推翻读者前面的一切推理, 不禁令人拍案叫绝.

  • 此前只见过 ucore 的实现, 即内核和用户空间不隔离, 这次也先入为主了, 只能感叹所学甚微.

遂将内容倒着梳理一遍.

跳板

ucore 里, 每个用户内存空间里的高 1G 都是内核代码

  • 用户态无法读写高1G的空间
  • 如果Trap, 进入内核态, 就可以跳转到高1G的空间里执行内核代码

rcore, 内核空间和用户空间是隔离的, 也就是说

  • 用户哪怕Trap进入内核态, 也需要切换页表才能访问内核空间
  • 众所周知, Trap后, 会进入内核态, 并跳转到 __alltraps, 这期间是没机会切换页表的
  • 所以__alltraps需要在用户空间里的某个地方, 而且在所有用户空间里都要有相同的虚拟地址
  • __alltraps执行过程中, 需要执行切换页表的指令
  • 执行之后PC + 1, 指向了: 内核空间里的一块地方! 这下尴尬了
  • 显然, __alltraps也要在内核空间里也有一份, 而且虚拟地址必须和用户空间里一样.

这就是跳板: 内核和用户空间里, 相同的虚拟地址, 都有__alltraps__restore这两个函数.

  • rcore里, 让这个虚拟地址为, 虚拟空间最高的一页.
  • 本质上, 这个和ucore里高1G都映射到内核空间是一样的, 只不过映射得更少, 仅两个函数, 这样更安全(也更麻烦).

考虑一次简单的Trap:

  • 用户进入内核态, 调用__alltraps, 切换页表, 保存上下文, 执行处理例程 … 且慢! 切换页表何时发生为好?
    • 首先执行处理例程肯定要在最后, 那么先切换页表还是先保存上下文?
    • 如果先切换页表
      • 此时进入内核空间里, 将上下文保存到内核栈里, 一切照旧
      • 执行__restore, 将上下文弹出, 再切换页表, 再sret, 完美 … 吗?
      • 很遗憾: 修改页表寄存器的指令, 需要另一个寄存器, 但是, 将上下文弹出之后, 所有通用寄存器都无法使用了, 根本不能切换页表
      • 你或许会说: 有没有另一个寄存器, 如同修改spsscratch一样 – 答案就是, 还真没
  • 因此只能先保存上下文, 再切换页表
    • 上下文存在哪里?
      • 为了不影响到用户, 选择在跳板的下方, 虚拟空间的次高页, 申请一页, 写入上下文
      • 这样需要多申请一页, 而不能优雅的写到内核栈里, 很遗憾, 但是没办法, 谁让RV不给多一个寄存器呢
    • 上下文保存了什么? – 之前的上下文是所有通用寄存器, 以及几个关键 CSR, 现在只存这些, 够了吗?
      • 每个进程都有自己的内核栈, 都有自己的页表, 都需要找个地方存起来
      • rcore: 就和上下文保存在一起了(反正那一页很空)
  • 继续: 执行处理例程trap_handler … 且慢! 怎么执行? 还是call trap_handler?
    • RV小知识: call其实是伪指令, call trap_handler会被编译成相对跳转, 即linker.ld里, 这条call指令, 到trap_handler的距离
    • 然而, 在我们特意设计之下, __alltraps执行的时候, pc并不在.text里, 而是在次高页里, 使用call会跳到错误的地方
  • 因此我们只能手动跳转到trap_handler – 额, 先思考, 跳转地址从哪里来?
    • 显然, 我们需要定一个地方, 提前保存好trap_handler的地址, 可以存在哪里呢?
    • rcore: 就和上下文保存在一起了(反正那一页很空)
  • 处理例程执行结束之后, 调用一个新函数, trap_return, 其负责手动跳转到__restore, 并提供两个参数, 页表和上下文的地址
    • 此处如何手动跳转: 因为这是Rust函数, 只要获得提前标记好跳板的地址, 就能跳过去了.
  • 终于到了__restore
    • 因为把上下文保存到用户空间了, 所以这里要先切换页表, 所以需要一个参数, 页表
    • 因为上下文不再保存到栈里, 所以需要一个参数, 上下文
    • 然后把上下文弹出, 用sscratch切换sp, sret, 完美!

考虑第一次执行用户程序, 也就是直接__restore的情况:

  • 首先, 在__restore之前, 内核要为这个进程申请几页, 作为内核栈
  • 接着, 内核还得先为这个进程, 生成用户空间:
    • 首先为用户生成一个页表
    • 然后申请很多页, 把用户程序的各个段读入内存里
    • 还要申请几页, 作为用户栈
    • 还要申请一页, 映射到跳板
    • 最后申请一页, 构造一个上下文存进去
  • 别忘了, 内核还要生成一个TCB, 上面这些信息, 就一起存到TCB里吧!
    • 还记得构造的TCB里, 还有什么吗? 没错就是任务上下文s0~11, ra, sp, 以及状态(ready)
  • 准备完全, 运行应用: 将s0~11, ra, sp恢复, ret, 跳转到ra, 也就是上文提到的新函数trap_return
    • trap_return负责给__restore送参数: 这就是为什么需要新函数, 因为有足足两个地方都要用到!
    • sp就是这个进程的内核栈, 毕竟恢复任务上下文之后, 就算是正式恢复到这个进程了, 接下来的操作应该用该进程的内核栈来操作.
  • trap_return之后, 终于跳转到__restore了, 看看__restore做了什么, 实际上和从Trap返回是一样的
    • 先切换页表到用户空间
    • 然后把上下文倒腾出来, 切换spsscratch, sret

虚拟内存管理

所谓虚拟内存管理, 实际上就是实现两个东西

  • 物理页管理器
  • 虚拟映射物理地址的方法
    什么? 虚拟内存管理器? 完全不需要!
  • 能用的虚拟地址, 都存在页表里了
  • 虚拟地址告诉进程了, 他应该自己保存好

物理页管理器

实际上就是有一个数据结构, 他负责

  • 管理空闲物理页
  • 有人来要一页, 怎么分配
  • 有人来还一页, 怎么回收
    只要实现一页一页的就行了, 很多页的分配和回收, 循环调用就好了
  • 因为物理页不会有连续一块的借用的说法, 那是虚拟页的说法.

rcore的极简栈式的物理页管理器

  • 有两个数组, 记录没分配过的物理页号, 和已回收的物理页号
  • 总共可用的物理页: 从ekernel(内核数据的结束)开始, 到0x80800000(硬编码)结束

仅暴露接口frame_alloc

  • 返回一个FrameTracker, 内容其实就是物理页号
  • 为什么没有回收接口? – RAII思想
    • FrameTracker实现了Drop Trait: 将该物理页号push到数组里
    • 也就是说, 等到这个程序自然消亡之后, FrameTracker也会自动Drop, 即自动回收内存

注意, 现在还没有实现动态内存分配

注意, 现在还没有实现动态内存分配

注意, 现在还没有实现动态内存分配

硬件MMU, 清空快表的指令

rv64 的分页机制, 通过修改satp来开启

  • satp: 一个CSR, 指示了页表位置和分页模式
    • mode: 4位, 分页模式, bare(0000), sv39(1000)
    • ASID: 16
    • PPN: 44位, 一级页表的物理页号

sv39只使用虚拟地址的低39位, 转换为56位的物理地址

  • 其他位必须和有效地址的最高位一致, 即虚拟地址只有高256G和低256G是有效的
  • 为什么是39:
    • 一页4KB, 一个页表项64位, 一页可以存512个页表项, 也就是9位索引
    • sv39使用三级页表, 总共需要27位索引, 再加上页偏移12位, 所以只需要39位有效

页表项

  • 保留: 10
  • PPN: 44位, 物理页号
  • RSW: 2位(9:8)
  • 标志位: 8 位(7:0), DAGUXWRV – dirty, access, G(粒度?), user(用户可访问), XWR(执行,写,读), V(有效)
    • RWX若不全为0, 则意味着这是最后一级页表.

sfence.vma清空快表

内核和应用的内存视图

rcore 采用了 ucore 设计的改进版, 即

内核空间不再是用户空间的高 1G, 而是独立出来, 和用户空间隔离

当然, 没法做到完全隔离, 内核和用户的高一页, 还是得映射到一起, 充当 ‘跳板’

内核的内存视图

  • 此处是虚拟内存最高处, 往下256GB是有效地址
  • 跳板
  • 各个进程的内核栈从此处分配, 注意各个栈之间要有保护页
    • 保护页: 这一页直接被跳过, 也就是说, 其虚拟地址永远不会写入页表里, 对其访问会直接异常, 这样可以防止栈溢出, 覆盖其他数据
  • 此处是虚拟内存0x80800000(硬编码), 即可用物理页的结束
  • 可用的物理页框
  • .bss
  • .data
  • .rodata
  • .text
  • 此处是虚拟内存0x80200000(硬编码), 即内核数据的起始处
    注意到内核数据, 虚拟地址和物理地址一样, 都是0x80200000开始, 这是故意的
  • 在内核的页表里, 将内核数据的虚拟地址和物理地址, 进行了恒等映射
  • 这样做, 方便内核直接用物理地址访问内存.
    • 注意, 虽然这是内核虚拟空间视图, 但是物理空间里, 可以使用的物理空间是真真切切的0x80200000~0x80800000
    • 使用恒等映射, 内核访问用户空间就可以少走一步
      • 内核得到一个用户地址 va, 如何访问
      • 先获取当前进程的页表, 查表得到 pa
      • 这时候, 内核需要通过 pa 反推出内核空间的 va
      • 恒等映射: va 就是 pa!

有点抽象, 虽然这里是内核虚拟空间, 但是其中有一部分是物理空间. 既是虚幻也是现实.

不如说用户空间也是? 凡是保存了数据的, 实际上都是物理空间.

应用的内存视图

  • 此处是虚拟内存最高处, 往下256GB是有效地址
  • 跳板
  • 上下文页: 越想越气, 每个进程要多申请一页, 浪费
  • 申请X页作为用户栈
  • 保护页
  • .bss
  • .data
  • .rodata
  • .text
  • 此处是虚拟内存最低处(0), 往上256GB是有效地址

虚拟地址到物理地址的映射

再次声明: 此时并没有实现动态内存分配, 记录内存使用情况仅仅是加载程序的时候记录分配的页

rcore采用段页式设计, 但是分段仅仅为了区分不同的访问权限rwxu

rcore给每个进程生成一个MemorySet, 记录内存使用情况, 保存在TCB

RAII: MemorySet保存了所有这个程序申请的FrameTracker, 程序消失的时候, 系统会释放TCB, 从而自动回收所有页框

MemorySet有两个成员: 页表和段数组(vec[MemoryArea])

  • 页表很简单: 维护了一级页表的物理页号, 以及为了新建二三级页表, 所申请的FrameTracker
  • 段数组:
    • 为每个段生成一个MemoryArea, 根据视图决定虚拟地址
    • 每个MemoryArea生成的时候, 都会判断要不要为了这个段, 申请页框
      • 比如内核数据就不需要申请
      • 如果申请了页框, 就要把这段映射关系先记录下来, 尤其是FrameTracker得存下来
    • 随后就要把MemoryArea插入段数组里, 插入的时候, 就把其记录的映射关系给写到页表里.
  • MemorySet还负责设置跳板: 其实就是给页表写入, 把高一页映射到那两个函数所在的, 物理页

重写 sys_get_time 和 sys_task_info

参数是一个指针, 需要往里面填数据.

  • 指针的值是个地址, 是个虚拟地址, 是个用户给的虚拟地址, 所以当然是用户的页表上的虚拟地址
  • 内核使用的是自己的页表, 所以无法直接使用这个指针写数据, 因为自己的页表映射的物理地址和用户页表映射的物理地址不一样.
  • 但是内核可以查用户的页表, 得到这个指针实际的物理地址, 内核需要向这个物理地址里写数据, 此时有两种实现
    • 实现1: 因为内核使用恒等映射, 所以把这个物理地址当成虚拟地址访问, 就等于访问这个物理地址.
    • 实现2: 朝内核的页表里, 随便用一个虚拟地址映射这个物理地址, 访问完毕后将这个页表项改回原样.
      • 我使用了0x0, 因为内核起点是0x800000, 代码里也没用到, 所以用完后直接清零这个页表项即可.

实现简易的动态分配内存: mmap 和 munmap

此处正式开始涉及到动态分配

rCore本身已经给出了极其丰富的 api, 直接调用即可.

mmap: 将 _start 开始的虚拟地址, _len 个字节, 映射到某个物理内存, 内存属性为 _port.

  • 找到用户的 mem_set, 插入一个 map_area, 这将会自动申请物理页框, 自动修改页表.

munmap: 将 _start 开始的虚拟地址, _len 个字节, 解除映射

  • 找到用户的 mem_set, 找到 _start 开头的 map_area, 将 _start + _len 作为新的开头, 对之前的部分调用 unmap
    • 这将会自动释放物理页框, 自动修改页表.

ch5: 进程管理

和 ch3 所设计的分时管理系统类似, 只是更为细致, 更多数据结构.

阅读即可, 思考部分不多, 难点都已经帮忙实现好了.

实现: spawn

TaskControlBlock::new(elf_data)

  • 根据 elf_data 建立 mem_set
    • 新建一个空白 mem_set
    • 设置跳板
    • 解析elf_data
    • 遍历所有Load类型的段, 新建对应mem_area
    • mem_area推入mem_set, 此时会申请对应页框, 并写入数据
    • 为用户栈新建一个mem_area, 推入mem_set
    • 在用户栈上方, 新建一个mem_area, 大小为0, (用于sbrk? 啥)
    • trap上下文, 新建一个mem_area, 占地一页
    • 返回mem_set, 用户栈顶, 入口点
  • 拿到 trap 上下文的物理页号
  • 申请一个pid, 和一个内核栈
  • 新建一个tcb
    • 填入刚刚申请的pid和内核栈
    • 填入trap上下文物理页号
    • 基础大小: 用户栈顶
    • 任务上下文: goto_trap_return: ra(trap_return), sp(内核栈), s0~11
    • 状态: ready
    • mem_set
    • 父亲: none
    • 孩子: vec::new
    • 退出码: 0
    • 堆底: 用户栈顶
    • brk: 用户栈顶
    • sys_call_times, first_run_time
  • 修改新的tcbtrap上下文:
    • 入口点
    • 用户sp
    • 内核页表token
    • 内核栈顶
    • trap_handler
  • 返回tcb

如果不用fork, exec来新建进程:

  • 建立tcb: TaskControlBlock::new(elf_data), 这将会自动建立用户空间
  • 还需要对tcb修改
    • 设置其父亲为当前进程(也要修改当前进程的孩子数组)
  • 加入准备队列: add_task

实现: stride 调度

算法描述如下:

  • 为每个进程设置一个当前 stride, 表示已经运行的“长度”, 以及对应的pass值, 表示调度后 stride 需要进行的累加值
  • 每次调度时, 选择 stride 最小的调度, 将对应的 stride 加上其对应的步长 pass
  • 一个时间片后,回到上一步骤

可以证明:

  • 如果令 P.pass = BigStride / P.priority, 则该调度方案为每个进程分配的时间将与其优先级成正比
  • 其中 P.priority 表示进程的优先权(大于1),而 BigStride 表示一个预先定义的大常数,

其他实验细节:

  • stride 调度要求进程优先级 >= 2, 所以设定进程优先级 <= 1 会导致错误
  • 进程初始 stride 设置为 0 即可
  • 进程初始优先级设置为 16

实现 tips:

  • 为了实现该调度算法,内核还要增加 set_prio 系统调用
  • 你可以在 TCB 加入新的字段来支持优先级等。
  • 为了减少整数除的误差 BIG_STRIDE 一般需要很大, 但可能溢出, 或许选择一个适中的数即可, 当然能进行溢出处理就更好了
  • 如何找到 stride 最小的进程: 优先级队列是不错的办法, 但是我们的实验测例很简单, 很推荐使用暴力
  • 注意设置进程的初始优先级。

stride溢出

  • 考虑进程A和B, 优先级为9和90, BIG_STRIDE = 900, 所以步长为100和10, 假设数字范围0~999.
  • A运行1次, B运行10次
  • 某次调度: 当A和B都是900时, A先运行, A变成 900+100 = 0
  • 下次调度: 0 < 900, 所以仍是 A 运行, 不合理

解决思路

  • 已知: 最大的和最小的stride之差, 不会大于最大的pass, 证明如下
    • 初始所有stride均为零, 假设最大pass先行动, 此时之差恰为最大的pass, 符合
    • 接下来她永远无法行动, 直到成为最小的stride, 情况还不如初始情况, 初始好歹是同一起跑线, 证毕
  • 而因为prio >= 2, 且pass = BIG_STRIDE / prio, 所以最大的和最小的stride之差, 不会大于BIG_STRIDE / 2
  • 因此哪怕溢出也能比较大小
    • 考虑: 数字范围 0~999, 那我们令BIG_STRIDE = 900, 那么A和B, 优先级为9和90, 步长为100和10
    • 同样运行到900, A先动, A变成0
    • 此时, B - A = 900 > 最大的pass, -> 发生溢出, 实际上是 A > B
    • B会连续运行, 直到B=990, 再次运行, 变成0, 之后回到最开始

考虑真实情况

  • 进程A,B, 优先级为 100 和 16, BIG_STRIDE = 65535, 所以步长为655和4095
  • A运行 100 次到 65500, B运行 16 次到 65520.
  • 此时到B, B变成 4079
  • 进行 A - B = 61471 > 最大步长 4095, 说明溢出, 所以 A < B
  • B - A = 4065 <= 最大步长 4095, 说明没问题, 所以 B > A
  • 无论如何都是 A 运行, A变成 669, 显然 A < B, 而且不需要思考溢出问题, ok

解决算法

  • 已知: 最大的和最小的stride之差, 不会大于最大的pass
  • 所以进行判断, 对于 A - B, 如果结果
    • 大于max_pass: A < B
    • 其他: A >= B

多进程情况

  • 数组V, stride 各不相同
  • 遍历 V, 得到最大步长 P
  • 假设 min_stride = V[0] , for i in V:
    • 若 i.stride - min_stride <= 最大步长: i 大, 不操作
    • 若 i.stride == min_stride: 步长一样, 判断优先级高者(数值大), 成为新的 min_stride
    • 其他情况: i 小, i 成为新的 min

整体收获

  • 学下到 软件是如何与硬件进行交互的
  • 学习到 RISC-V 的基础知识, 包括特权等级、汇编指令、特殊寄存器等
  • 了解了操作系统对内存地址空间的管理方式
  • 能够自己实现简单的进程调度算法,并真正的进行进程调度
  • 回顾了操作系统对磁盘等块设备的交互方式,并基本掌握了 easy-fs 的实现思路
  • 能够更加熟练的使用 rust 进行编程

学习过程的资料那里来?

实验指导书是最好的学习资料,其次就是 RISC 的官方网站提供的文档资料

如何阅读实验代码

根据实验指导书,向自己画出整个操作系统的结构图,各个模块的组合结构,和交互流程,结合实验指导书,
实验代码中的代码命名和注释, 来整体向理解代码结构与组合逻辑。 遇到不明白的方法或代码块,可以先跳过,
阅读此段代码的程序上下文,来大胆假设代码块的作用,如还是猜测不到其作用, 找到这段代码在整体架构中的位置,
根据逻辑推理,进行猜测,还可以打印日志,追踪程序执行过程等方式来验证;

如何实现 lab

  • 一定现先认真读懂题目要求,理清需求,再动手实现
  • 根据题目定位自己的实现在整个操作系统的结构图的位置,属于哪个模块, 然后推测自己的实现可能需要与其他那些模块交互
  • 大胆为已经存在的 struct、trait 的新建方法与变量
  • “大方”的打印日志(不用白不用),使用日志可以很好的辅助自己进行问题的调试与解决

1000oaks的rCore前二阶段小结

写小结一刻, 却不知写些什么.

  • 这已经是我第二次报名了rCore训练营了. 第一次报名于2022年夏季, 然而那个暑假我去研究托福的备考了, 所以第一次报名之后什么也没有做(虽然托福倒是速成成功, 但是这导致我下学期没有修读校内开设的操作系统研讨课). 要不是D同学督促我, 怕不是第二次报名也只停留于一阶段了.

  • 过分杞人忧天, 不如在rCore上静心研究.

Read more »

写在前面

作为上班族,每天下班很晚了,本来没有多余时间,并且之前没有接触过Rust

看到 从零开始用 Rust 语言写一个基于 RISC-V 架构的 类 Unix 内核这样标题

直接打退堂鼓。

转你一想 这就是自己本来期望形式,参与开源方向,操作系统 作为软件工程师 基本功,不管结果如何必须参与。

一阶段总结

  • 选择看什么资料,根据看c++经验,一定选择英文原版 代替看中文翻译,很多翻译遗漏很多信息。我直接选择 rustlings-100exercises README.md

  • 因为时间有限,没有采取全部看完book,然后做题,

    采取看一章节,做题 顺序

    https://github.com/LearningOS/rustlings-100exercises-template/blob/main/exercises/README.md

    rustlings 设计 很合理 提供 README和章节练习。为我节省大量时间

  • 选择在线开发环境

    群里分享了:rustlings流程web版.pdf 然后5分钟搭建好了环境,更适合上班 环境 和家里环境随时切换。

  • 遇到不懂怎么办?

    学习Rust出现新名词 :借用 让你莫不这头脑,我没有从概念理解 这些概念,

    并按照文字提示 翻译

    用c++设计进行类比:常量指针,指针常量, 类 深度拷贝 移动构造 ,move语义

    拷贝构造,还有STL

小结:

为了节省时间,我采用云环境(5分钟搭建完成)

做题顺序按照README.md 推荐方式 README对我帮助很大

二阶段总结

ch1 & ch2

  • 存在问题:

一个hello,world 例子是怎么运行的,代码从编译到产生可执行程序,然后加载到内存,程序入口是哪里 尤其是linker.ld entry.asm这2个文件。

尤其汇报指令。需要加强。之前看程序自我修养,

还有csapp 感觉看懂到,现在看来根本不懂,用了不少时间。

尤其看到别人满分了,担心着急,我还没真正投入开始呢。

  • 解决方式:

为了方便反复运行程序 我搭建vmare+本地环境。

rcore提供框架,让这些知识变成例子,

最后不依赖系统库运行在起来。这个演示例子非常好。

小结 :hello,world 例子

  1. 项目中 每个模块都个mod.rs文件 ,这一般是模块提供对提供功能。

  2. 程序入口地址

chapter3 练习

题目要求:

ch3 中,我们的系统已经能够支持多个任务分时轮流运行,我们希望引入一个新的系统调用 sys_task_info 以获取当前任务的信息,定义如下:

1
fn sys_task_info(ti: *mut TaskInfo) -> isize

思路

  1. 从单元测试 ch3_taskinfo.rs 了解到 ,直接创建了task,该task 可能执行很多系统调用系统调用最终都是通过 sys_call 进行,在该函数增加 add_syscall_count。

  2. 数据结构:TaskManagerInner 记录了正在运行的任务 current_task 和任务列表tasks,全局变量 只有一个。

  3. main.rs 函数启动时候 加载任务 并且运行第一任务

    loader::load_apps();

    task::run_first_task();

小结:系统调用

ch1 和ch2 是ch3 基础,下面这段代码 需要后面花费更多时间学习

1
2
3
4
5
6
7
8
9
10
11
pub fn rust_main() -> ! {
clear_bss();
kernel_log_info();
heap_alloc::init_heap();
trap::init();
loader::load_apps();
trap::enable_timer_interrupt();
timer::set_next_trigger();
task::run_first_task();
panic!("Unreachable in rust_main!");
}

chapter4练习

实验要求

重写 sys_get_time 和 sys_task_info

引入虚存机制后,原来内核的 sys_get_time 和 sys_task_info 函数实现就无效了。请你重写这个函数,恢复其正常功能。

mmap 和 munmap 匿名映射

mmap 在 Linux 中主要用于在内存中映射文件, 本次实验简化它的功能,仅用于申请内存。

请实现 mmap 和 munmap 系统调用,mmap 定义如下:

思路:地址空间

  1. 为什么 重写 sys_get_time 和 sys_task_info ?这从地址空间说起,原文:

    内核如何访问应用的数据?

    应用应该不能直接访问内核的数据,但内核可以访问应用的数据,这是如何做的?由于内核要管理应用,所以它负责构建自身和其他应用的多级页表。如果内核获得了一个应用数据的虚地址,内核就可以通过查询应用的页表来把应用的虚地址转换为物理地址,内核直接访问这个地址

    1
    2
    3
     let info = TaskInfo::new();  //info 这用户空间地址
    assert_eq!(0, task_info(&info));//经过系统调用后,用户空间地址
    //传递到内核空间,用户空间虚拟地址 对内核来说无法直接使用,需要转化
  2. 疑惑地方:我看懂这个数据结构页表项 (PTE, Page Table Entry) 是一个整数)

    里面包含了一个物理页号 + 标志位

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /// 一个物理页号 PhysPageNum 和一个页表项标志位 PTEFlags 生成一个页表项 
    pub fn new(ppn: PhysPageNum, flags: PTEFlags) -> Self {
    PageTableEntry {
    bits: ppn.0 << 10 | flags.bits as usize,
    // 最低的 8 位 [7:0] 则是标志位。
    //其中 [53:10] 这 44 位是物理页号
    // SV39 分页模式下的页表项,其中 这 位是物理页号,最低的 位 则是标志位
    }
    }

虚拟页号 同样也是整数,虚拟页号 和 物理页号对应起来?

经过群里讨论 和看资料,初步理解 虚拟页号当作索引,页表项是数组内容建立关系,这句话初步帮助理解。不代表真实现。

另外一个结构:PageTable

a 通过虚拟页号找到页表项(里面又物理页号)

1
2
3
4
5
6
/// Find PageTableEntry by VirtPageNum
/// 通过虚拟页号找到页表项(里面又物理页号)
fn find_pte(&self, vpn: VirtPageNum) -> Option<&mut PageTableEntry>
let idxs = vpn.indexes();
https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter4/4sv39-implementation-2.html
VirtPageNum 的 indexes 可以取出虚拟页号的三级页索引,并按照从高到低的顺序返回

b 函数:translated_byte_buffer 为参考例子实现了

实现来了 从虚拟地址转化成物理地址

3 map 和 unmap 虚拟地址是一个连续内存,其中一个虚拟地址转化成物理地址,

多个虚拟地址转转化思路很清楚了,具体实现:MemorySet 新增map_range函数

这里对map封装

1
2
3
4
5
pub fn map(&mut self, page_table: &mut PageTable) {
for vpn in self.vpn_range {
self.map_one(page_table, vpn);
}
}

小结

最后通过下面函数封装完成ch4。

  • PageTable find_pte

  • MemorySet map_one unmap_one

    不然无法实现,里面细节不少。

chapter5 练习

实现分支:ch5-lab

实验目录要求不变

通过所有测例

思路

  1. 为什么重新实现 sys_task_info sys_mmap函数?

    • 引入处理器管理结构 Processor 负责从任务管理器 TaskManager 中分出去的维护 CPU 状态的职责

    • 这里注意 语法细节

      1
      2
      3
      4
      5
      6
      7
      8
      ///Get current task in moving semanteme
      pub fn take_current(&mut self) -> Option<Arc<TaskControlBlock>> {
      self.current.take()
      }
      ///Get current task in cloning semanteme
      pub fn current(&self) -> Option<Arc<TaskControlBlock>> {
      self.current.as_ref().map(Arc::clone)
      }
  2. sys_spawn

1
2
3
//功能:新建子进程,使其执行目标程序。
// "ch5b_user_shell\0"
pub fn sys_spawn(_path: *const u8) -> isize
  • 细节:参考 初始进程initproc的创建 【里面有很多知识点】

    1
    2
    TaskControlBlock::new(get_app_data_by_name("initproc").unwrap())
    https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter5/3implement-process-mechanism.html
  • 细节:参考 fn sys_exec(path: *const u8) 对_path处理 需要地址转化。

  • 细节:父子进程关系设定。 parent: Option<Weak>

    weak指针类型

  1. 进程优先级

    每次需要调度时,从当前 runnable 态的进程中选择 stride 最小的进程调度

    改写fetch函数,修改当前任务的stride 使用take 还是as_ref。

小总:进程

  • 这一章节完全是Rust语法细节 引用,借用 ,weak智能指针(避免循环引用)

  • 例如 “ch5b_user_shell\0” 后面执行过程不很清楚,我更加深入学习load实现。

未完待续

感谢老师和主教们提供的精彩课程,让我作为一个已经工作的工程师,在业余时间也能够深刻学习操作系统这门课程。课程内容丰富,技术前沿,把RUSTRISCVOS结合在一起,并且提供了完整的实验。经过学习我对操作系统有了很清楚的认识,虽然目前才做完lab3,但是后续会接着把两个实验也给完成。

Read more »