rcore-os Blog
0%

Posted on Edited on In

初次接触

作为一个工作党，第一次接触OS训练营课程是通过西安邮电大学的陈丽君教授推荐的，当时看到训练营很兴奋，虽然已经作为工作党已经10多年，那会上大学没有这么好的平台和开源课程，隐约记得06年左右的时候只了解过陈渝教授的网上公开课，但是对实际做的事情并没有深入了解和学习。
这次是通过训练营可以深入学习了。陈老师的课程也越来越丰富，之前的就课程也恶补了一些，这次的训练营是以Rust为主要语言基础，循序渐进一步一部的学习OS的开发过程，主要分成三个阶段，第一阶段以rustling为基础的和第二阶段的Rust语言编程，第二阶段的Rcore的OS实践学习，第三阶段的不通选题的实现，比如ArceOS等。
对于我个人已经参加了三期。之前第一期，仅完成了rustling，第二期，尝试完成了rustling和ucore，因为对rust语言编程还是一头雾水，这次，经过坚持完成到了第二次的rcore，但是还有core 的5个大实验只完成了3个实验，虽然可以过关，还是想冲一波完成实验4，但看了两天文档，仅仅有点思路了，但是没时间完成了，先提交博客过关，只能后面找时间完成了!下面是过程中的一些即简要总结。

第一阶段总结

这个阶段前40题都是一些基本语法，有编程经验的稍微琢磨下都可以完成。等到了泛型，闭包和trait就看似一头雾水了。个人总结做题可以参考官方的手册，但是深入学习语言建议可以参照https://course.rs/basic/base-type/numbers.html，rust语言圣经比较通俗的，比较翻译的和原汁原味的编程书是不一样的，或者直接对照看英文也是可以的。
rustling在做题过程中一定要多看 lint和注释里，因为题目的目的都是里面，同时看来处理对应的参数连接，会快一点。
比如：iterators5.rs实验中，需要多查看手册，我开始移植准备用比较for循环的笨办法去实验，么有理解题目的目标的意思，花费了很多时间，即使完成了实验，但是学迭代的fold用法没有理解和掌握，目前没有达到还是浪费了很多时间，因为rust里面的迭代用的很多，需要慢慢体会，同时还是学会使用手册，只要查看下fold手册，或者浏览下迭代器的用法，就一目了然。
https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.fold
还有就是rust手册还是需要整体先过一遍，再去做题会事半功倍，及时不全完成，但是至少目录要过一遍。

第二阶段总结

第二阶段做的还是比较吃力，一共5个大实验，我仅完成了3个，后面两个只能等后面时间完成。
实验1，整体难度不大，目标是通过syscall实现获取系统时钟和taskinfo的信息，这个时候的rcore还是比较原始，没有MMU，没有进程只有作业的状态，因此实现起来没有内存和进程的限制，只要理解代码和流程和实验的环境就可以完成。
实验2，由于增加了用户空间和内核空间去区分，因此系统之间的调用的数据交换要使用特定的机制完成，这里主要考察了translated_byte_buffer的用法，核心是memoery_set的进制如何使用和对其理解。这里为了代码简洁也查了很多资料，最后使用copy_from_slice，也对切片的使用更深的认识，但是最后看了老师的参考代码，还是有不一样的。
实验3，群里有人说比较难，但个人认为实验难度的不能很难，因为spawn基本上相当于fork+exec，还是考察进程中memory_set,program_brk，task_cx，user_sp，等拷贝和处理
第二阶段如果有一些操作系统的基础会好很多，推荐大家阅读陈海波教授的《现代操作系统：原理与实现》通俗易懂。

总结

通过本课程，除了敲开了对rust编程语言和OS开发的大门，更多的是认识了这么多老师和同学，更加认识了自己。非常感谢清华的老师和同学能提供这样一个开发的平台，晚上各位老师的讲解和答疑，是我们一个指引，也是对我们这些初学者是一个道路的指引，相信这样的训练营将会给我们的国家带来软件的繁荣，再次感谢无私风险的老师和同学们！！！

Posted on Edited on In

背景

我是一名计算机专业的学生，现在进入大三上学期，学校已经安排了操作系统课程，但老师教授的偏理论性缺少实践的过程。我本来已经在学习MIT 6.S081操作系统课程，朋友推荐了rCore，采用Rust语言编写的操作系统课程，觉得非常棒交流环境很好而且是国产然后配套资源也很全，就报名学习了。一起学rCore吧！

我也认为在本科阶段，就需要认真学习理解计算机核心课程包括操作系统，应该学习计算机底层知识去了解探索计算机科学领域的魅力和故事，打下扎实基础，毕竟是计算机专业的本科生，大学毕业后可能没有足够的时间与精力去做这些事情。

Read more »

Posted on Edited on

2023开源操作系统训练营第二阶段总结报告

学习动机与兴趣

使用rust已经很久了， 但是一直没有机会可以深入学习Rust编程和操作系统原理。对于Rust，它的内存安全性、”零开销抽象”和Cargo包管理工具等特性吸引了我（ps: cpp的包管理差的有点子多)。在训练营里面, 我可以深入了解了RISC-V架构。虽然之前可能只是听说过，但在训练营中，我学习了SBI和RISC-V指令集的使用。相对于传统的x86架构，RISC-V的指令集更为简洁，文档也相对清晰，这为理解底层原理提供了很好的机会。

实验内容与技术挑战

训练营的实验内容广泛，涵盖了操作系统的核心概念，包括多道程序的放置与加载、虚拟内存管理、进程管理、文件系统、管道和线程支持等。但是目前 文件系统和异步这方面的内容还没有看太明白。

在实验中，我遇到了不少技术挑战。例如，在虚拟内存管理实验中，我们需要处理虚拟地址到物理地址的映射，而在进程管理实验中，我们必须正确处理任务切换和多任务调度。这些挑战锻炼了问题解决能力和编程技巧。

同时 UPSafeCell的使用，也给我的工作中有一定启发。 我通过使用sdk中UnsafeCell结构体, 结合atomic变量来完成ReadGuard。 成功去除了锁依赖， 使用无锁编程的方式解决并发效率问题。 这种学习并能实践的感觉，让我觉得不虚此行。

学习总结

整个训练营让我更深入地理解了操作系统的原理和底层机制。通过实际的内核开发和编程实践，积累了宝贵的经验，不仅掌握了Rust编程，还深刻理解了操作系统的内部工作原理。我对于Rust的掌握也有了显著提高。

Posted on Edited on In

开始

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

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

过程

第一阶段

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

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

第二阶段

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

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

小结

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

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

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

Posted on Edited on

总体总结

​ 参与本次开源操作系统训练营，我开始学习了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.

Posted on Edited on

#关于Rust

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

#关于操作系统

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

#关于未来学习计划

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

Posted on Edited on In

开始阶段

有一年私有云平台开发经验的 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 的内容，完成整个训练营任务。

Posted on Edited on

前言

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

实验总结

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

lab1

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

lab2

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

而 sys_mmap 和 sys_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_mmap 和 sys_munmap 的实现和实验二是一样的，不多说。

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

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

sys_set_priority 比较简单，不多赘述。

lab4

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

sys_mamp 和 sys_munmap 是一样的，不再赘述。

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

这个实验卡了我很长时间，主要是向外提供的 DiskInode、Inode、OSInode虽然比较清楚，但还是很难确定什么时候用哪个，而且有些时候需要和 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_lock 和 down 中更新三个向量，之后的思路如下面的代码：

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，有点没想到自己可以完成这五个实验。在这个过程中参考了：

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

Posted on Edited on In

前言

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

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

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

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

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

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

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）的代码, 以便进行调试和异常处理等操作

rCORE的linker.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时, 硬件会自动完成如下这些事情

  • 修改sstatus的SPP字段
  • 修改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.rs的run_next_task()里, 新增: 如果next的first_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, 完美 … 吗?
      • 很遗憾: 修改页表寄存器的指令, 需要另一个寄存器, 但是, 将上下文弹出之后, 所有通用寄存器都无法使用了, 根本不能切换页表
      • 你或许会说: 有没有另一个寄存器, 如同修改sp的sscratch一样 – 答案就是, 还真没
  • 因此只能先保存上下文, 再切换页表
    • 上下文存在哪里?
      • 为了不影响到用户, 选择在跳板的下方, 虚拟空间的次高页, 申请一页, 写入上下文
      • 这样需要多申请一页, 而不能优雅的写到内核栈里, 很遗憾, 但是没办法, 谁让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返回是一样的
    • 先切换页表到用户空间
    • 然后把上下文倒腾出来, 切换sp和sscratch, 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
  • 修改新的tcb的trap上下文:
    • 入口点
    • 用户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

Posted on Edited on In

整体收获

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

学习过程的资料那里来？

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

如何阅读实验代码

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

如何实现 lab

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