rcore-os Blog

2025开源操作系统训练营总结-刘轶凡

Posted on 2025-05-05 Edited on 2025-06-04

二阶段

我的整理

三阶段

我的整理

<2025春夏季开源操作系统训练营第二阶段总结报告-1430329301Lsj>

Posted on 2025-05-05 Edited on 2025-06-04

rcore第二阶段学习心得

以下是针对 rCore 操作系统各个技术方向的详细扩展叙述：

1. 应用程序与基本执行环境

rCore 的应用程序执行环境构建在硬件抽象层（HAL）之上，其核心依赖 RustSBI 提供的引导和硬件初始化服务。RustSBI 在启动阶段完成以下关键任务：初始化 CPU 核心、配置物理内存保护区域（如设置 PMP 寄存器）、启用时钟中断和外部设备中断（如 UART 串口）。应用程序以 静态链接的 ELF 格式 加载到内存中，内核解析 ELF 文件头获取代码段（.text）、数据段（.data）和未初始化数据段（.bss）的虚拟地址，并为其分配物理页帧，建立虚拟地址到物理地址的映射。

用户程序运行在 RISC-V U 模式（用户态），通过 ecall 指令触发特权级切换到 S 模式（监管态）执行系统调用。内核在初始化用户环境时，需配置用户栈空间（如分配 8KB 栈内存）并设置 Trap 上下文，确保异常处理时能正确保存和恢复寄存器状态。系统调用参数传递遵循 RISC-V ABI 规范：系统调用号存入 a7，参数依次存入 a0-a6，返回值通过 a0 返回。例如，sys_write 调用时，用户程序将文件描述符、缓冲区地址和长度分别存入 a0、a1、a2，内核通过 a0 返回实际写入的字节数。

为确保安全性，内核通过 内存保护机制 阻止用户程序直接访问内核空间。例如，用户程序若尝试访问高于 0x80000000 的内核地址，将触发页错误异常（scause=13），内核根据异常类型终止进程或按需分配物理页。

2. 批处理系统

批处理系统的核心设计是 顺序执行多个用户程序，每个程序独占 CPU 直至完成。内核在编译阶段将多个应用程序的 ELF 文件链接到内核镜像中，并在固定物理地址（如 0x80400000）依次加载。程序加载时，内核执行以下步骤：

内存清零：清除前一程序残留的数据，防止信息泄漏。
页表隔离：为每个程序创建独立的页表，仅映射其代码段、数据段和用户栈，避免越界访问。
上下文初始化：设置程序的入口地址（ELF 的 entry 字段）和初始栈指针（sp 指向用户栈顶部）。

当程序主动调用 sys_exit 或发生致命错误（如非法指令）时，内核通过 TaskManager 切换到下一程序。任务切换的关键在于保存当前程序的 任务上下文（TaskContext），包括 ra（返回地址）、sp（栈指针）和 s0-s11（保留寄存器），并通过汇编函数 __switch 切换到目标程序的上下文。批处理系统需确保 原子性切换，即在切换过程中屏蔽中断（通过 sstatus.SIE 位），防止时钟中断导致状态不一致。

3. 多道程序与分时多任务

分时多任务通过 时间片轮转算法 实现 CPU 资源共享。内核为每个任务维护一个 任务控制块（TaskControlBlock, TCB），包含以下元数据：

任务状态：运行（Running）、就绪（Ready）、阻塞（Blocked）。
时间片计数器：记录剩余时间片长度（如 10ms）。
优先级：用于调度决策（如实时任务优先级高于普通任务）。
上下文信息：包括寄存器快照和页表地址（satp 值）。

时钟中断（通过 sie.STIE 使能）触发调度器执行以下流程：

递减当前任务的时间片计数器，若归零则标记为就绪状态。
从就绪队列中选择下一个任务（如按优先级或轮询策略）。
调用 __switch 切换上下文，并更新 satp 以切换地址空间。

协作式调度 依赖任务主动调用 sys_yield，适用于 I/O 密集型任务减少切换开销；抢占式调度 则通过中断强制切换，适合 CPU 密集型任务提升吞吐量。内核需处理 临界区竞争，例如在修改任务队列时关闭中断，防止并发修改导致数据结构损坏。

4. 地址空间

地址空间通过 Sv39 分页机制 实现虚拟内存管理，支持 512GB 的虚拟地址范围。虚拟地址被划分为三级页表索引（VPN[2]、VPN[1]、VPN[0]），每级页表包含 512 个条目（8 字节/条目）。内核维护 全局页帧分配器，按需分配物理页帧并更新页表条目（PTE）的权限位（如 R/W/X 和 U 位）。

用户程序访问虚拟地址时，若触发缺页异常（scause=12/13/15），内核执行以下处理：

检查访问地址是否合法（如位于用户代码段或堆栈范围内）。
分配物理页帧，建立虚拟地址到物理地址的映射。
刷新 TLB（通过 sfence.vma 指令），确保后续访问使用新页表。

内核自身采用 恒等映射（虚拟地址等于物理地址），简化直接内存访问（如操作外设寄存器）。用户程序通过动态映射访问特定设备（如 MMIO 区域），需在内核中注册设备内存范围并配置页表权限（如设置为不可执行）。

5. 进程与进程管理

进程是资源分配的基本单位，其控制块（PCB）包含以下信息：

进程标识符（PID）：唯一标识进程的整数。
地址空间：指向页表的指针（satp 值）和内存映射信息。
文件描述符表：记录打开的文件、管道或设备。
父子关系：父进程 PID 和子进程链表。

进程创建 通过 fork 系统调用实现，内核复制父进程的地址空间（写时复制优化）和文件描述符表，并为子进程分配新的 PID。exec 系统调用则替换当前进程的地址空间，加载新程序的代码和数据。

进程调度 基于状态机模型：

运行 → 就绪：时间片耗尽或被高优先级任务抢占。
运行 → 阻塞：等待 I/O 完成或信号量资源。
阻塞 → 就绪：资源可用或事件触发。

进程退出时，内核回收其物理内存、关闭打开的文件，并通过 waitpid 通知父进程回收终止状态。若父进程已终止，子进程由 init 进程 接管以避免僵尸进程。

6. 文件系统与重定向

rCore 的虚拟文件系统（VFS）抽象了 文件、目录和设备 的统一接口，支持以下操作：

文件读写：通过 File trait 的 read 和 write 方法实现，具体由设备驱动（如 UART）或块设备（如 virtio-blk）完成。
目录管理：维护目录项（dentry）链表，支持 mkdir 和 readdir 操作。

重定向 通过复制文件描述符实现。例如，执行 echo hello > output.txt 时，shell 进程执行以下步骤：

打开 output.txt 并获取文件描述符 fd。
调用 sys_dup 复制 fd 到标准输出（fd=1）。
子进程继承修改后的文件描述符表，sys_write 输出到文件而非控制台。

文件系统通过 页缓存 优化性能，将频繁访问的数据缓存在内存中，减少磁盘 I/O 操作。索引节点（inode）记录文件的元数据（如大小、权限和物理块地址），并通过 日志机制 确保崩溃一致性。

7. 进程间通信（IPC）

IPC 机制包括以下实现方式：

共享内存：内核分配物理页帧，并映射到多个进程的地址空间。进程通过信号量或自旋锁同步访问。
管道：基于环形缓冲区的 FIFO 队列，内核维护 pipe 结构体记录读写位置和等待队列。sys_pipe 创建管道后返回两个文件描述符（读端和写端），进程通过 read 和 write 系统调用传输数据。
信号：内核为每个进程维护信号处理函数表。当进程收到信号（如 SIGKILL）时，内核修改其 Trap 上下文，强制跳转到注册的处理函数。信号处理完成后，通过 sigreturn 系统调用恢复原执行流程。

消息队列 是另一种 IPC 方式，内核维护消息缓冲区，进程通过 msgsnd 和 msgrcv 发送/接收结构化数据，支持阻塞和非阻塞模式。

8. 并发机制

内核并发通过以下机制管理：

自旋锁（SpinLock）：通过原子指令（如 amoswap）实现忙等待，适用于短期临界区（如修改任务队列）。使用前需关闭中断（sstatus.SIE = 0），防止死锁。
互斥锁（Mutex）：在锁竞争时让出 CPU，将当前任务加入阻塞队列，切换其他任务执行。解锁时唤醒等待任务。
条件变量（Condvar）：与互斥锁配合使用，通过 wait 释放锁并阻塞，notify 唤醒等待任务。适用于生产者-消费者模型。

用户态线程（协程）通过 异步运行时 实现，内核提供轻量级上下文切换（如 swapcontext）和非阻塞 I/O 系统调用（如 read_async）。Rust 的 async/await 语法糖将协程编译为状态机，运行时调度器根据事件（如 I/O 完成）切换协程执行。

内存安全 通过 Rust 的所有权系统和 Send/Sync trait 保障。Send 允许数据跨线程转移所有权，Sync 允许数据被多线程共享引用。编译器静态检查数据竞争，确保并发代码的安全性

rCore学习笔记

Posted on 2025-05-04 Edited on 2025-06-04 In 补完计划

rCore学习笔记

根据学习顺序从头梳理一下操作系统的发展历史：

原生之初

CPU做了什么？

CPU-Central Processing Unit，中央处理器，由IFU，EXU，MMU等等等组成，就不赘述了。以RV64IM指令集架构的角度来讲吧：

门电路只能根据输入来生成输出
一个运算模块的输入：ep1，ep2 输出：res 取决于具体的指令
以一个简单的只有加减的ALU为例：MUX(choose, res_add, res_sub)

module ALU (
    input choose,
    input [63:0] ep1,
    input [63:0] ep2,
    output [63:0] res
);
    assign res = choose == 0 ? ep1 + ep2 : ep1 - ep2;
endmodule

电路只管res_add和res_sub的计算，结果是都算出来的，但是最后的res被通过选择器来选择输出res_sub | res_add
CPU就是一个只管埋头干活的驴（有限状态机），而choose是CPU根据PC取值译码后得到的，用来选择哪个输入作为输入以及哪个输出作为输出
所以在CPU看来他只要不停的根据时钟进行不停01摇摆就行，而操作系统关心的就多了，包括“特权级的转换”/“进程调度”/“IO”等等
CPU角度的函数调用：我不知道发生了啥，只知道gpr[rs1] = pc+4, pc = gpr[rs2]，即：用了一下全加器，存了俩reg，调哪个函数全看pc指向内存里面的哪
CPU角度的设备读写：我不知道发生了啥，只知道某总线使用某协议按照某种规律发了一串特定的bit波形
CPU角度的异常处理：我不知道发生了啥，只知道某个被人类称为CSRs的寄存器组里面几个寄存器取了存，存了取
CPU角度的面向对象：我没有这个概念，只知道一个数字存哪取哪全靠选择器最后是否选中MEM，或者选中GPR？CSR？更高层次的汇编里面称这个决定选中哪里的一串01的数字为指针？

所以，CPU压根不知道一些奇奇怪怪的高级概念，更不知道什么奇奇怪怪的转换特权级，只知道，当前状态的输入，以及自己时钟边沿敏感后存下选中的输出。在CPU看来，只是一堆与或门在0101变，有的0101会连接到选择器的与或门上，决定了下一波存的0101而已。

仿佛充电就不停运动的牛马，优雅的被称为“程序是一个状态机”，不停的在状态之间兜兜转转

ISA做了什么？

指令集架构，以上面的ALU为例，规定了choose == 0时选择res_add，否则选择res_sub。在真实的CPU中，ISA规定了每一条指令的格式，数据类型，寄存器，中断/异常，字节次序等等等。比如末尾后7位是opcode，opcode是0110011是基本的运算族指令，比如add，sub等等。简而言之就是上面的规定了choose == 0时选择res_add，还是选择res_sub。

它给人们提供了一套规范，可以有规范可查，遇到情况可以查相关的手册或者文档，有册可查，有规可依。

规定了你看见A就说1，看见B就说0，AABBA就是11001，让CPU的电路运行有据可查

SBI做了什么？

一套二进制接口，封装特定操作的软件程序，刷在PC初始值位置，用于初始化CPU的各项寄存器（广义，包括GPR，CSR，PC等等）中的值，之后提供了一个函数映射表的位置，当某些情况下ecall指令的时候，就把PC设置为这个函数映射表的位置，执行所指向的执行流，之后某个时机再返回到某个特定的位置。

根据规范封装特定的指令，以及初始化指定的寄存器，初始化结束后，PC也被初始化到了OS所在的位置

OS做了什么？

也相当于一套二进制接口，是一个软件程序，用来管理硬件的各项资源，大部分的操作通过调用SBI提供的接口，很少直接操作硬件。决定了某些寄存器的值，以改变PC的指向，从而改变用户眼中的当前执行的程序（执行流）。

因为遇事不决调SBICall，所以可以当是一个封装在特定SBI实现上的一个软件，或者调SBI实现的接口/库的一个程序

Syscall做了什么？

OS提供的一个函数映射表，当某些情况下ecall指令的时候，就把PC指向映射表的位置，映射表会根据参数和栈来决定下一步做什么，之后某个可能的时机再返回原来执行到的地方。

封装了一个函数映射表，可以根据参数的值选择要执行的操作

用户程序做了什么？

依据各基于的标准库，来编写程序或更高层级的库，然后调用现有的依赖编写自己心目中的程序或者功能。游戏，网页，基础设施，编译器等等等，一切他们觉得让生产生活更方便的东西，比如：饥荒营火重生Mod，QQ，雷碧超市小程序……

使用操作系统提供的接口，或者在操作系统之上的虚拟机平台提供的接口，拼接，组装，变成自己需要的程序

所以他们做了什么？

总结来看，仿佛就是一层调用一层的接口，一层接着一层的调包导库，实际上也是，不过是为了学习或使用方便而简化了一些东西而已。这些简化的东西在上层的使用者几乎不用关心，被称为“抽象”

ISA规定了硬件都有哪些寄存器，遇到哪些指令该怎么做，提供了UB以外的确定性硬件操作（不确定的比如/0才是UB吧，所以这句就是废话是吧…）

SBI初始化硬件提供的寄存器，之后跳转到OS所在位置，确保了OS的执行正确，不会遇到get_time的时候，一看，俩寄存器还是未初始化的随机脏值

OS将“资源”具象化，来分配，调度OS所知晓的内存空间，存储空间。同时，也创建了对于用户程序不可见的物理地址之下的虚拟地址，为系统安全提供保障。用户所编写的程序将不需要关心真实的物理地址在哪，程序会被安排到什么地方。OS：“给你这些你就用，其他的别管！”

用户程序，在OS的抽象下，用户以为自己独占了一台物理机，当其需要操作系统的服务，比如获取当前系统时间的时候，调用Syscall

而为了区分不同层级的程序，为了用户越界访问系统的时候，硬件能给点反应，触发中断，切回OS叫醒OS：“你用户越界了！”，部分CSR寄存器的某些位连接了译码器以及MMU的部分部件，为的就是检测到不对就警报进行中断。为了配合这个硬件机制，软件上就得设置这些位是0还是1。比如SBI初始化的mstatus，OS初始化的sstatus等等。这样子在特定位没被设置的时候，某不属于此特权级的指令的执行就会触发中断。但是如果软件不设防，一切运行在裸机（没有SBI，没有OS来管理调度资源的芯片），那么特权级将会失去意义。

这一过程就像你MC（一个游戏）开服务器，你不设防，认为一切道法自然，那么熊孩子炸了你家你也不知道，你也只能接受。但是当你软件开启“游客权限：不准使用TNT”，“好友权限：可申请使用TNT”的时候，你也就划分了特权级的抽象：“USM” - “房主好友游客”。

所以，学的广不能学的深，调库侠不如底层佬什么什么的都是伪命题，都是在认知范围内合理利用工具而已

批处理

当我裸机能运行一个程序的时候，我就想让他运行两个，但是切换好麻烦，能不能一次输入，就能得到所有想要的输出？

好，将两个程序拼接

万一前面的出错怎么办？

将PC指向下一个程序，这程序就算运行结束了

有程序破坏系统篡改数据怎么办？

我得规定程序的权限：不能随意访问空间，不能破坏系统

简而言之，批处理系统是操作系统的雏形，通过简单的程序二进制拼接起来，依次执行，进行了简单的错误处理以及特权级切换

多道分时

提高系统的性能和效率是操作系统的核心目标之一，一个个排着队，不论长短一直等着就不耐烦。为了解决这个问题，不同目的的操作系统有了不同的策略。执行流在被阻塞的状态下让出处理器是通用的。其余的，急者优先，先来先服务等等调度算法应用在了不同领域。但是最常见的还是基于时间平均分配时间片的分时复用算法。底层是每隔一小段时间触发一次时钟中断来切换执行流。

在CPU角度，CPU是一个状态机，下一步的结果只与当前状态有关，所以切换执行流实际上就是保存了CPU当前的状态，即：Context-上下文，之后找个时间再恢复。所以CPU当前的状态是什么？

取指的PC：关系到指令执行到哪了，该执行哪个了

ISA规定的寄存器组：32个寄存器，起码zero恒0，不用保存，sp要手动霍霍调度执行流，不保存

部分执行流相关csr：得按需保存，比如sstatus，sepc，scause等等，按需？比如裸机保存的就是mepc而不是sepc

地址空间

将程序按部就班刷入固定位置，每次有新程序还得重新安排程序所在的位置，且用户程序能直接访问物理地址本来就是不安全的。

所以地址空间思考的就是：如何使用一个抽象，让所有程序不必想自己得被安排到哪，且隔绝不同程序之间的地址空间？

PageTable一个是方便MMU硬件查找虚拟地址对应的物理地址，一个是维护了软件的接口，方便操作系统需要时霍霍。

[MapArea]保存了连续的虚拟地址的映射，以及此段地址的权限，分配和回收直接霍霍PageTable，方便了OS维护PT

此时程序看到的地址都是OS提供的抽象幻象，隔绝了程序的同时，用户编写程序也不用思考程序将会被放在哪了！

进程管理

之前的程序都是确定要运行的，被刷入的程序只能决定会被运行，不能决定自己什么时候不运行，什么时候去运行。人机交互差。所以一开始只执行一个负责和用户交互的程序，后续由用户选择执行特定的程序。提高了用户的自由度和体验。

现在的程序可以被用户选择是否要运行，以及什么时候开始运行。比起之前开机只是为了关机的死程序疙瘩多了人性化。

比死程序疙瘩多的操作也就是：如何将创建一个执行流的上下文，将上下文加入调度队列，以及获取上下文返回的信息

由于地址空间的支持，所有程序的起始地址都可以相同，应该说，都是相同的，所以每次创建执行流的时候，虚拟起始地址每个程序都一样，不一样的只是被映射到的物理地址。

文件系统

一次性刷好所有的程序，有新的程序还得重新刷，关机内存的数据就没了，所以需要一种持久化存储数据/程序的方式。然后管理这种持久化存储的程序的系统就是文件系统，这种持久化的程序或者数据的抽象就是“文件”。但是文件平铺对于习惯分门别类的人来说阅读性太差，就有了“目录”。归结到底“目录”也是一种特殊的文件，其中存的内容是规则的目录项罢了。

所以，目录就是一个目录项的容器，目录项就是描述一个目录或者文件的指针和属性的集合。而一切的起源就是根目录，就是目录树的根节点。通过一层层指针，就能找到最终指向的文件区域。

有了文件系统，可以很方便的持久化程序和数据。程序又何不是一种数据？

之后想运行程序的时候就可以在持久化的数据中寻找对应的文件，读入内存，后创建PCB，加入调度

管道通信

不同进程之间的通信，可以通过父进程的文件描述符来进行读写buffer。

并发和锁

当进程变为线程的管理容器的时候，线程共享着进程的资源。由于线程异步执行的不确定性，一个内存区域（资源）被不同线程访问修改后不能保证原执行流的原子性。很有可能一个数据，比如一个u128的变量，在sd低64位的时候被调度了，导致写线程还没把高64位写进去，读线程读的时候会发现数据错误。所以就需要一种机制来保证这种边沿区域的读写原子性。没写完就读的，让读的先缓缓，切回写的，写完再把要读的放出来读就不会出错了。

但是往往一个线程有时候并不只需要一个资源，有时候需要N个不同的资源。这时假设A线程拿到了资源1，B线程拿到了资源2，但是B要访问资源1，A要访问资源2，但A拿着资源1睡去了，B就只能干耗着，形成死锁。死锁的解锁方式很多，比如卡足够时间就释放，过段随机时间再请求等等。但是如果可以预防死锁，在可能发生死锁的时候拒绝分配，让可以安全执行完成的执行流先完成，那么就不会形成死锁。所以在ch8完成了银行家算法的化简版。

2025s-os-camp-note-welkin-y

Posted on 2025-05-03 Edited on 2025-06-04

Rust warm-up

April 4th to April 6th
Pattern match 和 Functional programming 好文明, 梦回 compiler。
Result<T,E> 很好封装
~~后面忘了~~

rCore-OS

April 13th to April 20th

按说明实现scheduling即可

Lab 2 virtual memory

核心在于VA, VPN, PA, PPN之间转换，不要混淆

Lab 3 process

结合exec和fork实现spawn

Lab 4 file system

OSInode, Inode, DiskInode三层封装
实现 fstat和 hardlink补充完成对应调用即可

Lab 5 thread

死锁检测，按要求实现 Banker’s algorithm

ArceOS

April 22nd to April 29th

Lab 1 color print

DIY过bashrc的懂得都懂
pseudocode:

print_with_color(str):
  if print with color:
    print('\x1b[31m'+ str + '\x1b[0m')
  else
    print(str)

也可以换用别的颜色

Lab 2 hashmap

照葫芦画瓢std::collections::HashMap

Lab 3 bump allocator

~~没印象了~~

Lab 4 file rename

更改parent dir中的name, 且本题只有一个rootdir

Lab 5 mmap

因为测例也没有多次分配所以直接没写找freed memory的步骤，总体和rCore的sys_mmap思路一致，需要注意转换VA.

Lab 6 hypervisor

改asm, 但我真不会汇编

2025开源操作系统训练营总结-王扬

Posted on 2025-05-03 Edited on 2025-06-04

rcore 总结

Lab1

最终设计思路

在每个task下用syscall_count:[u8;MAX_SYSCALL_ID]存下调用次数，
在mod.rs中为TaskManager实现incerment和get方法
踩坑记录
以为不同task在一起统计，后来询问群友得知分开统计。（感觉文档里最好应该说清楚）
一开始想用hashmap存，后面发现在no std下使用要用hashbrown库，但没有实现Clone，就不能用
在task中用一个数组存syscall的count，数组如果用usize不知道为什么write A B C的时候会卡住(可能太大了==???==)，尝试用u8就成功了

lab2

最终设计思路

sys_mmap:遍历vpns，使用translate建立vpn和ppn映射
sys_unmmap：遍历vpns，使用memory_set.page_table.unmap(...)取消映射
sys_get_timer:获取当前时间的微秒值并转换为 TimeVal 结构体获取其字节数组time_val_bytes，然后将其拷贝到用户空间的目标地址对应字节数组位置dst:Vec<& mut[u8]>。
sys_trace: 根据id得vpn+offset，使用translate获取其物理地址进行读写

踩坑记录

首先尝试实现sys_mmap，一开始想impl TaskManager中实现get_memoryset方法，尝试后发现返回&会有生命周期问题，试了很久后放弃了。直接在mod.rs实现一个map_vpns_to_ppns
sys_get_time一开始没用translated_byte_buffer，用完后简化很多。然后遇到：
1. 如何把time_val转为字节数组time_val_bytes。：core::slice::from_raw_parts
2. 如何把time_val_bytes复制到dst:Vec<& mut[u8]>。 : core::ptr::copy_nonoverlapping
不小心直接把id转为ppn
没有设置用户空间地址上限

lab3

实现过程

spawn 系统调用结合 fork 和 exec将两部分结合即可，试一次就成功了，没遇到什么问题
stride 调度算法：主要需要在task里新加一个prio属性，然后修改fetch方法，一个坑是修改highest_tcb.stride是生命周期有问题要用一个{}块去限制

lab4

实现过程

主要是需要在inode里实现link unlink仿照clear方法，先定义op找到old_name节点，接着调用modify_disk_inode方法，在最后添加一项设置对应inode_id与old的相同即可。要记得block_cache_sync_all()确保数据刷回磁盘
踩坑：一开始没有仔细看文档，easy-fs的文件全部挂在根目录下啊

lab5

算法记录

定义如下三个数据结构：
可利用资源向量 Available ：含有 m 个元素的一维数组，每个元素代表可利用的某一类资源的数目，其初值是该类资源的全部可用数目，其值随该类资源的分配和回收而动态地改变。 Available[j] = k，表示第 j 类资源的可用数量为 k。
分配矩阵 Allocation：n * m 矩阵，表示每类资源已分配给每个线程的资源数。 Allocation[i,j] = g，则表示线程 i 当前己分得第 j 类资源的数量为 g。
需求矩阵 Need：n * m 的矩阵，表示每个线程还需要的各类资源数量。 Need[i,j] = d，则表示线程 i 还需要第 j 类资源的数量为 d 。
算法运行过程如下：
设置两个向量: 工作向量 Work，表示操作系统可提供给线程继续运行所需的各类资源数目，它含有 m 个元素。初始时，Work = Available ；结束向量 Finish，表示系统是否有足够的资源分配给线程，使之运行完成。初始时 Finish[0..n-1] = false，表示所有线程都没结束；当有足够资源分配给线程时，设置 Finish[i] = true。
从线程集合中找到一个能满足下述条件的线程
1Finish[i] == false;
2Need[i,j] <= Work[j];
若找到，执行步骤 3，否则执行步骤 4。
当线程 thr[i] 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
1Work[j] = Work[j] + Allocation[i, j];
2Finish[i] = true;
跳转回步骤2
如果 Finish[0..n-1] 都为 true，则表示系统处于安全状态；否则表示系统处于不安全状态，即出现死锁。

实验过程

enable_deadlock_detect只负责检查是否enable,具体实现在check_dead_mutex和check_dead_sem还有banker
按照上面算法写即可

arceos 总结

1 基础调用流程

调用组件的流程 :app–>ulib:axstd–>arceos_api–>axhal–>axruntime–>app
axhal组件：_start()(初始化页表)–>rust_entry()–>
axruntime组件: rust_main()(打印logo+基本信息，初始化日志，显示kernel各各段范围，初始化内存分配器，platform初始化，初始化thread调度器，初始化设备和驱动，初始化文件系统网络系统，初始化中断，等待所有cpu启动)–>
apphello_world组件:main()–>
axstd组件: println(macros.rs)–>print_impl–>stdout::Write(io.rs)–>
arceos_api组件:ax_console_write_bytes–>
axhal组件：console write_bytes–>riscv64 put_char–>
sbi: putchar

使用features可以自由选择组件

print_with_color实验
直接在字符串两端加入颜色字符即可

2 动态内存分配支持

使用rust trait #[global_allocator]支持rust library中内存分配
支持hashmap思路：使用vec实现，根据key的hash值%hashmap容量作为位置存下value即可
bump_allocator实现思路：[ bytes-used | avail-area | pages-used ] 比较简单记录下三个区域分开的位置即可
3 ReadPFlash 引入页表
PFlash的作用：Qemu的PFlash模拟闪存磁盘，启动时自动从文件加载内容到固定的MMIO区域，而且对读操作不需要驱动，可以直接访问。
为何不指定”paging”时导致读PFlash失败？ArceOS Unikernel包括两阶段地址空间映射，Boot阶段默认开启1G空间的恒等映射；如果需要支持设备MMIO区间，通过指定一个feature - “paging”来实现重映射。
axhal提供体系结构无关的接口方法set_kernel_page_table写入根页表地址并启用分页

4 启动子任务

接口公开的是runqueue的对应方法

spawn&spawn_raw：产生一个新任务，加入runqueue，处于Ready
yield_now (协作式调度的关键)主动让出CPU执行权
sleep&sleep_until睡眠固定的时间后醒来在timers定时器列表中注册，等待唤醒
exit当前任务退出，标记状态，等待GC回收

5 协作式调度算法

context_switch
协作式调度：任务之间通过“友好”协作方式分享CPU资源。具体的，当前任务是否让出和何时让出CPU控制权完全由当前任务自己决定。

6 抢占式调度

只有内外条件都满足时，才发生抢占；内部条件举例任务时间片耗尽，外部条件类似定义某种临界区，控制什么时候不能抢占，本质上它基于当前任务的preempt_disable_count。
只在禁用->启用切换的下边沿触发；下边沿通常在自旋锁解锁时产生，此时是切换时机。
推动内部条件变化(例: 任务时间片消耗)和边沿触发产生(例: 自旋锁加解锁)的根本源是时钟中断。
CFS算法
1. vruntime最小的任务就是优先权最高任务，即当前任务。计算公式：vruntime = init_vruntime + (delta / weight(nice))系统初始化时，init_vruntime, delta, nice三者都是0
2. 新增任务：新任务的init_vruntime等于min_vruntime即默认情况下新任务能够尽快投入运行
3. 设置优先级set_priority：只有CFS支持设置优先级，即nice值，会影响init_vruntime以及运行中vruntime值，该任务会比默认情况获得更多或更少的运行机会。
4. 任务队列基于BtreeMap，即有序队列，排序基于vruntime

7 ReadBlock

virtio设备的probe过程
virtio驱动和virtio设备交互的两条路：
1. 主要基于vring环形队列:本质上是连续的Page页面，在Guest和Host都可见可写
2. 中断响应的通道主要对等待读取大块数据时是有用。
块设备驱动Trait - BlockDriverOps

8 加入文件系统

文件系统节点的操作流程：第一步：获得Root 目录节点第二步：解析路径，逐级通过lookup方法找到对应节点，直至目标节点第三步：对目标节点执行操作
rename_ramfs实验
1. 实验踩坑1：没有添加patch的部分axfs_ramfs={path="axfs_ramfs"}
2. 实验踩坑2： axfs中rename函数有问题，没有考虑dst的挂载

9 引入特权级

分析从Unikernel基础到目标最小化宏内核需要完成的增量工作：
1. 用户地址空间的创建和区域映射
2. 在异常中断响应的基础上增加系统调用
3. 复用Unikernel原来的调度机制，针对宏内核扩展Task属性
4. 在内核与用户两个特权级之间的切换机制
实例
1. 为应用创建独立的用户地址空间涉及组件：axmm
2. 加载应用程序代码到地址空间涉及组件：axfs，axmm
3. . 初始化用户栈涉及组件：axmm
4. 创建用户任务涉及组件：axtask (with taskext)
5. 让出CPU，使得用户任务运行涉及组件：axtask，axhal
切使用系统调用时使用异常

10 缺页异常与内存映射

地址空间区域映射后端Backend，负责针对空间中特定区域的具体的映射操作， Backend从实现角度是一个Trait
如何让Linux的原始应用（二进制）直接在我们的宏内核上直接运行？
在应用和内核交互界面上实现兼容。兼容界面包含三类：
1. syscall
2. procfs & sysfs等伪文件系统
3. 应用、编译器和libc对地址空间的假定，涉及某些参数定义或某些特殊地址的引用
elf格式加载
1. 需要注意文件内偏移和预定的虚拟内存空间内偏移可能不一致，特别是数据段部分
初始化应用的栈
系统调用层次结构
sys_mmap实现：先读到buf，在用户态页表找一片物理地址，转换为内核态地址，然后把buf里的东西复制过去。
11 Hypervisor
I型：直接在硬件平台上运行 II型：在宿主OS上运行
Hypervisor支撑的资源对象层次：
1. VM：管理地址空间；同一整合下级各类资源
2. vCPU：计算资源虚拟化，VM中执行流
3. vMem：内存虚拟化，按照VM的物理空间布局
4. vDevice：设备虚拟化：包括直接映射和模拟
5. vUtilities：中断虚拟化、总线发现设备等
最简Hypervisor执行流程：
1. 加载Guest OS内核Image到新建地址空间。
2. 准备虚拟机环境，设置特殊上下文。
3. 结合特殊上下文和指令sret切换到V模式，即VM-ENTRY。
4. OS内核只有一条指令，调用sbi-call的关机操作。
5. 在虚拟机中，sbi-call超出V模式权限，导致VM-EXIT退出虚拟机，切换回Hypervisor。
6. Hypervisor响应VM-EXIT的函数检查退出原因和参数，进行处理，由于是请求关机，清理虚拟机后，退出。
Riscv64:M/HS/U形成Host域，用来运行I型Hypervisor或者II型的HostOS，三个特权级的作用不变。VS/VU形成Guest域，用来运行GuestOS，这两个特权级分别对应内核态和用户态。HS是关键，作为联通真实世界和虚拟世界的通道。体系结构设计了双向变迁机制。
H扩展后，S模式发送明显变化：原有s[xxx]寄存器组作用不变，新增hs[xxx]和vs[xxx]
hs[xxx]寄存器组的作用：面向Guest进行路径控制，例如异常/中断委托等
vs[xxx]寄存器组的作用：直接操纵Guest域中的VS，为其准备或设置状态
为进入虚拟化模式准备的条件
1. ISA寄存器misa第7位代表Hypervisor扩展的启用/禁止。对这一位写入0，可以禁止H扩展
2. 进入V模式路径的控制：hstatus第7位SPV记录上一次进入HS特权级前的模式，1代表来自虚拟化模式。执行sret时，根据SPV决定是返回用户态，还是返回虚拟化模式。
3. Hypervisor首次启动Guest的内核之前，伪造上下文作准备：设置Guest的sstatus，让其初始特权级为Supervisor；设置Guest的sepc为OS启动入口地址VM_ENTRY，VM_ENTRY值就是内核启动的入口地址，对于Riscv64，其地址是0x8020_0000。
从Host到Guest的切换run_guest每个vCPU维护一组上下文状态，分别对应Host和Guest。从Hypervisor切断到虚拟机时，暂存Host中部分可能被破坏的状态；加载Guest状态；然后执行sret完成切换。封装该过程的专门函数run_guest。
VM-Exit原因
1. 执行特权操作
2. Guest环境的物理地址区间尚未映射，导致二次缺页，切换进入Host环境
simple_hv实验：只需改变sepc寄存器，并将对应值存进对应寄存器

12 Hypervisor 两阶段地址映射

有两种处理方式：
1. 模拟模式 - 为虚拟机模拟一个pflash，以file1为后备文件。当Guest读该设备时，提供file1文件的内容。
2. 透传模式 - 直接把宿主物理机(即qemu)的pflash透传给虚拟机。
  优劣势：模拟模式可为不同虚拟机提供不同的pflash内容，但效率低；透传模式效率高，但是捆绑了设备。
Hypervisor负责基于HPA面向Guest映射GPA，基本寄存器是hgatp；Guest认为看到的GPA是“实际”的物理空间，它基于satp映射内部的GVA虚拟空间。 GVA–> (vsatp)->GPA–> (hgatp) ->HPA
Hypervisor的主逻辑包含三个部分：
1. 准备VM的资源：VM地址空间和单个vCPU
2. 切换进入Guest的代码
3. 响应VMExit各种原因的代码
相比于宏内核多了vm-entry和vm-exit

13 虚拟时钟中断支持；虚拟机外设的支持

物理环境或者qemu模拟器中，时钟中断触发时，能够正常通过stvec寄存器找到异常中断向量表，然后进入事先注册的响应函数。但是在虚拟机环境下，宿主环境下的原始路径失效了。有两种解决方案：
1. 启用Riscv AIA机制，把特定的中断委托到虚拟机Guest环境下。要求平台支持，且比较复杂。
2. 通过中断注入的方式来实现。即本实验采取的方式。注入机制的关键是寄存器hvip，指示在Guest环境中，哪些中断处于Pending状态。
支持虚拟机时钟中断需要实现两部分的内容：
1. 响应虚拟机发出的SBI-Call功能调用SetTimer
2. 响应宿主机时钟中断导致的VM退出，注入到虚拟机内部
具体实现modules/riscv_vcpu/src/vcpu.rs
管理上的层次结构：虚拟机（VM），设备组VmDevGroup以及设备VmDev。Riscv架构下，虚拟机包含的各种外设通常是通过MMIO方式访问，因此主要用地址范围标记它们的资源。

2025春夏季OS训练营学习笔记

Posted on 2025-05-02 Edited on 2025-06-04

终于完成了前三个阶段的练习。我这个系统方向的博士生，读了很多操作系统方面的论文，但是直到今天终于是脱离了书籍上的一知半解，可以称得上是“了解”操作系统的基本原理了。作为一个转专业学生，我从统计学起步，跨专业申请到了计算机方向的硕士，到现在在异国他乡博士在读。也算是凭着对计算机的热爱走到了现在。只是要在这个领域做出好的问题和好的研究，还是一件很困难的事情。写完最后一个hypervisor实验的感慨倒是适合放在此处： “仔细想想，实际上type-II hypervisor也几乎可以通过类似的机制实现。这一套并不局限于直接运行在硬件上的Type-I Hypervisor，只要硬件提供特权级的隔离的功能可以轻易实现。硬件支持真是个好东西。想到了当时读Xen的论文，通过Para Virtualization重量级实现hypervisor那种巨大的工程量，再到现在各个处理器指令集都支持虚拟化扩展，可以通过几百行代码实现一个简单虚拟机。也算是软件系统的需求促进的硬件发展的一个样例了。
时过境迁，前两年Timothy在OSDI疾呼研究者应该回归OS的本质做hardware-software co-design。现在新硬件层出不穷，硬件加速器，智能网卡，TEE，还有RDMA，CXL一堆新名词。好像“攻守之势异也”，变成了硬件推动OS进步了。面对着越来越多的外设和越来越专业化的使用场景，操作系统研究者的未来又在何方呢？”

祝自己将来能成为一名好的system researcher

rcore部分

Chapter 1 应用程序与基本执行环境

Ref: https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter1/index.html
作为rCore教程的第一章，这章其实并未涉及到太多OS的概念。而是主要介绍了OS作为一个系统软件和应用层软件的区别：执行环境。并通过代码介绍了编写在OS执行环境中可以执行的代码。
我们在之前的学习中编写的用户态代码在执行时依赖于语言提供的运行时+标准库。运行时是一些预编译好的代码，会在编译时与我们自己编写的代码编译在一起，来实现一些诸如数组越界检查等功能。而标准库包含了对于很多系统调用的封装，比如说在使用print时，这个标准库函数在底层调用了操作系统提供的系统调用write 来把希望打印的内容输出到屏幕上。在运行时，操作系统也会帮我们完成准备和收尾工作，比如开辟虚拟内存，将程序代码载入到内存中，并在程序退出后执行清理工作等等等等等等。但是对于OS来说，它直接运行在硬件上，并没有封装好的系统调用，也没有其它软件为他进行准备工作了。因此一切都需要我们使用代码完成。

编译选项

首先就是在编译层面我们需要设置特别的编译选项。默认情况下Rust的编译选项默认标准库和对应的操作系统存在，因此生成代码时会用到其中的功能，这显然是不能接收的。因此我们需要把编译选项中只指定硬件架构RISCV 和基本的二进制文件格式elf 。

设置内存布局

由于没有fork 等系统调用，我们必须自己处理程序启动时的准备工作才能让程序运行起来。好在我们还可以使用rust_sbi 以及系统架构和上面的固件。RISCV固件在加电启动时会默认从内存0x1000 开始运行代码，并帮助我们跳转到rust_sbi 的启动流程中去。rust_sbi 规定系统软件的代码需要被放置在0x800002000 以保证正常执行。因此我们只需要在启动时把编译好的二进制文件load到0x80002000 中去即可。另一点需要注意的是rust的链接器（最终决定二进制内存布局）的默认设置并不符合QEMU中RISCV的要求。因此我们需要手动设置链接器的脚本以确保各个段被放置在合适的位置。从而保证load后能顺利运行

编写代码

由于这一章中仅仅是使用rust_sbi 完成输出Hello World，所以大部分内容属于调用SBI的细节无需赘述。需要注意的有几点，第一是在没有标准库后，代码默认的panic和exit都需要我们进行退出处理（甚至没有标准库的情况下它甚至无法指定默认入口为main 函数，我们需要给代码标注上![no_main] 宏然后在汇编中call main函数，并在链接脚本中指定开始执行的指令）。因此我们需要在代码中编写panic handler函数以处理出现panic的情况。另外就是作为系统软件，我们需要手动编写代码在启动时将.bss(全局变量)所在的内存段清零，防止后面出现奇怪的错误。当然，我们还需要在汇编代码中分配好栈的大小（由于现在并没有虚拟内存的支持因此只能分配固定大小的栈，我们没有很好的办法防止栈溢出，在完成虚拟内存章节后我们就完全避免这个问题了。）
当然我们还需要用宏将我们预编写的汇编语言包含在源代码中这样也生成的二进制中就也会包含我们写的汇编啦(汇编中包含函数入口，分配栈等内容)

ASM和链接器解析

下面是注释后的entry.asm和链接器脚本。asm生成了一些符号然后链接器会把他们按照链接脚本的方式计算出实际地址并翻译为二进制代码。

一个注释后的entry.asm

.section .text.entry       # 定义代码段，.text.entry是一个特殊的段名
.globl _start              # 声明_start符号为全局可见
_start:                    # _start标签，程序入口点
    la sp, boot_stack_top  # 将boot_stack_top的地址加载到栈指针(sp)
    call rust_main         # 调用rust_main函数
    
.section .bss.stack        # 定义未初始化数据段，用于栈
.globl boot_stack_lower_bound  # 声明栈底界限为全局可见
boot_stack_lower_bound:    # 栈底界限标签
    .space 4096 * 16       # 分配16页内存(每页4KB)作为栈空间
.globl boot_stack_top      # 声明栈顶为全局可见
boot_stack_top:            # 栈顶标签

boot_stack_lower_bound: 定义了栈底部的标签（地址）
.space 4096 * 16 在这个标签之后预留了 64KB 的内存空间
boot_stack_top: 定义了栈顶部的标签（地址）
boot_stack_top 后面什么都没有是因为它标记的是栈空间的结束位置。由于栈是向下增长的，实际的内存布局是这样的：
1
2
3
4
5
高地址 --> boot_stack_top (栈指针初始位置)
|
| 64KB 的栈空间
|
低地址 --> boot_stack_lower_bound (栈底限制)

一个注释后的链接器脚本

OUTPUT_ARCH(riscv)         // 指定输出架构为RISC-V
ENTRY(_start)              // 指定程序入口点为_start符号
BASE_ADDRESS = 0x80200000; // 定义基地址常量，这是RISC-V SBI通常加载内核的地址

SECTIONS
{
    . = BASE_ADDRESS;      // 将当前位置计数器设为基地址
    skernel = .;           // 定义skernel符号，表示内核起始地址

    stext = .;             // 定义stext符号，表示代码段起始地址
    .text : {              // 定义.text段（代码段）
        *(.text.entry)     // 首先放入所有.text.entry段（启动代码）
        *(.text .text.*)   // 然后放入所有其他.text段（普通代码）
    }

    . = ALIGN(4K);         // 将当前位置按4KB对齐
    etext = .;             // 定义etext符号，表示代码段结束地址
    srodata = .;           // 定义srodata符号，表示只读数据段起始地址
    .rodata : {            // 定义.rodata段（只读数据段）
        *(.rodata .rodata.*) // 放入所有.rodata段（常量等）
        *(.srodata .srodata.*) // 放入所有.srodata段（小型只读数据）
    }

    . = ALIGN(4K);         // 将当前位置按4KB对齐
    erodata = .;           // 定义erodata符号，表示只读数据段结束地址
    sdata = .;             // 定义sdata符号，表示数据段起始地址
    .data : {              // 定义.data段（已初始化数据段）
        *(.data .data.*)   // 放入所有.data段（初始化的变量）
        *(.sdata .sdata.*) // 放入所有.sdata段（小型数据）
    }

    . = ALIGN(4K);         // 将当前位置按4KB对齐
    edata = .;             // 定义edata符号，表示数据段结束地址
    .bss : {               // 定义.bss段（未初始化数据段）
        *(.bss.stack)      // 首先放入.bss.stack段（栈空间）
        sbss = .;          // 定义sbss符号，表示bss段主体起始地址
        *(.bss .bss.*)     // 放入所有.bss段（未初始化变量）
        *(.sbss .sbss.*)   // 放入所有.sbss段（小型bss数据）
    }

    . = ALIGN(4K);         // 将当前位置按4KB对齐
    ebss = .;              // 定义ebss符号，表示bss段结束地址
    ekernel = .;           // 定义ekernel符号，表示整个内核结束地址

    /DISCARD/ : {          // 定义丢弃段，这些段不会出现在最终二进制文件中
        *(.eh_frame)       // 丢弃所有.eh_frame段（异常处理框架，通常不需要）
    }
}

关于你提到的 "xx = ." 和 ". = xx" 语法：

xx = .

这种形式是在当前位置定义一个符号。
例如 stext = . 表示定义符号 stext 指向当前位置计数器的值。
这些符号通常用于在程序中获取段的边界地址。


. = xx

这种形式是将当前位置计数器设置为某个值。
例如 . = BASE_ADDRESS 将位置计数器设为基地址。
. = ALIGN(4K) 将位置计数器向上对齐到4KB的整数倍。



链接器脚本的工作方式是按顺序处理各个段，并且使用一个"位置计数器"（用 . 表示）来跟踪当前的地址。每定义一个段，这个计数器就会增加该段的大小。
通过这种方式，链接器能够：

计算每个段和符号的最终内存地址
调整代码中的引用，使它们指向正确的地址
生成一个内存布局明确的最终二进制文件

Chapter 2 批处理系统

Ref: https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter2/index.html
rCore的第二章主要内容是如何实现系统调用。这一章涉及的具体“知识”非常少，大部分是工程细节。系统调用和函数调用非常相似，为了防止寄存器被嵌套函数执行时修改，都需要在调用前保存好上下文并在返回时恢复。与编译原理中哪些prolog和epilog完全一致。
唯二的区别在于，首先。操作系统需要保存所有的通用寄存器（因为不再有convention保护），以及重要的CSR（控制寄存器）。CSR是用户态程序无需关心的。这些寄存器包括保存了CPU当前特权级的sstatus ，trap返回后继续执行的地址sepc trap的原因以及附加信息scause/stval 等等。其次，处于安全考虑，操作系统需要维护自己的栈，而不能和用户态程序一样单纯继续向下开辟栈。因此我们可以利用RISCV中提供的额外寄存器sscratch 来保存内核栈的地址。这样当trap发生时，我们就可以从sscratch 中找到内核栈的地址并开始处理了。
需要注意的是，由于目前为止所有操作都是在物理地址上发生的。所以实际上应用程序有能力访问所有内存的并找到操作系统的内核栈，目前我们的操作系统并没有实现任何内核态和用户态的隔离。这一点可以通过x86架构提供的段实现，RISCV有没有类似功能尚不清楚。当然，这个问题会在我们实现虚拟内存后完全解决。
祝自己明天开始写第一个lab顺利！

Chapter 3 多道程序与分时多任务

Ref:https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter3/index.html
rCore的第三章将操作系统的调度能力进一步拓展，在chapter 2中，我们的操作系统只能按照设定好的顺序逐个运行程序。而Chapter 3加入了抢占机制，使操作系统能够交替运行不同程序。极大的改善了程序的交互体验。
实现分时共享系统的核心是timer的加入。timer是一个来自硬件的中断发生器，会不断的向操作系统发出中断。每当中断来临时，操作系统就会接管节点，并决定是否要切换到另一个应用程序执行。切换的步骤与第二章中的系统调用是非常相似的。因为都是“打断”当前应用程序的执行并在稍后回复。因此需要保存应用运行的上下文。
在这一章中，应用程序有了task的抽象。并通过task数据结构被操作系统调度(突然理解了为什么linux中的进程管理块名叫task哈哈哈)
这一章的作业实现trace系统调用，还是比较简单的，希望之后一切顺利。容易错的点是题目实际要求的是分别统计每个应用的系统调用次数。因此需要简历一个二维数组。另外如果试图将数组放到更内层的TaskControlBlock 而不是TaskManager 会出现奇怪的内核崩溃bug。怀疑是因为TaskControlBlock 在内存中位置和长度都固定锁导致的.所以最终还是把二维数组放到了TaskManager 中

Chapter 4 地址空间

Ref:https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter4/index.html
这一章中终于实现了虚拟内存。我们的程序可以拥有单独的地址空间而不是时刻在意自己具体的内存位置了。虚拟内存的实现是通过名为MemorySet 和MemoryMap 的数据结构实现的，这点和Linux中的虚拟内存管理非常一致。
虚拟内存管理通过硬件上的MMU自动实现虚拟地址到物理地址的翻译。只需要将页表的root page放置在特定的寄存器中就可以让硬件实现正确寻址。
加入虚拟内存让内核迎来了一次比较大的重构。因为我们之前最重要的管理机制：系统调用和程序切换锁保存的上下文会发生不同。这里涉及到很多tricky的问题，比如说开启虚拟内存后，在我进入内核的地址空间后，需要通过应用态的页表手动找到需要保存的上下文。还有由于地址空间不同，在陷入内核态之前需要通过一个特定的相同的跳板页来实现丝滑switch。这些设计上的细节是之前理论上学习操作系统时根本没有想过的。
关于这一节的实验没想到最困难的并不是mmap和unmap，而是port sys_trace函数。再试图往对应地址写入是，我把PPN转usize再加上offset结果发现一直不对。然后发现PPN居然并不是Physical Address但是后面用0 padding，它就单纯的是个物理页号。需要先左移PAGE_SIZE再加offset才是对应的physical address。

Chapter 5 进程

Ref: https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter5/5exercise.html
这一节终于引入了进程的概念。它其实只是之前四章内容的更上一层抽象。进程的抽象让操作系统可以实现更加丰富的语义。比如更只能的进程调度，通过fork(), exec()运行新的程序。以及在这一章，我们终于有了shell！操作系统更像一个真正的操作系统了。
这一章具体的内容不多，大部分为有机的组合前四章的内容实现进程的概念。以及增加了进程管理的相关细节。比如如何启动第一个进程，进程退出后如何回收等等。
本章的实验倒是十分简单， spawn系统调用就是fork+exec拼一拼，只不过把复制memoryset的部分去掉。而stride调度器也只是在manager结构中统计一下步长和priority并根据它们调度。只要找到了对应的数据结构实现起来非常简单。

Chapter 6 文件系统

Ref: https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter6/index.html
文件系统！终于可以把程序存在块设备上而不是呆在内存里了！因为在ECE566课上已经学过一遍了所以基本没有什么新知识。但是能看到具体的实现还是学到了很多细节。比如说具体如何和驱动程序沟通。但是由于disk的驱动程序已经做好了抽象所以实际上我们只需要实现对应的接口就可以了。
我在实验的第一版实现中犯了蠢在实现hardLink的时候给每个hardlink都创建了一个新的inode并且给inode增加一个新的type hardlink，然后修改read和write的逻辑。加一层indirection找到linkto的inode执行实际的读写
后面发现根本没必要啊！只需要在文件夹中的directory entry中将文件名link到对应的inode即可。另外一个奇怪的bug是如果在DiskNode加入太多的字段会触发奇怪的虚拟内存相关报错LoadPageError。而这个behavior在不同机器上跑的出现还不一样，非常随机。不知道为什么会这样，怀疑是加入太多字段会影响数据结构在内存中的排布？由于实在是太难debug了所以最终并没有发现根因、这个bug是所有rcore实验中困扰我最多的实验，干了一整个通宵，十分痛苦。
另一点是因为引入了stdout和stdin，在spawn创建新的进程的时候需要记得初始化stdout，否则会出现测试程序打印不出来内容的窘境。

Chapter 7 进程间通信

Ref: https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter7/index.html
之前一直觉得linux语法很难理解，，总觉得程序是一步一步执行的。比如a|b 就是先运行a再把输出传给b 但看到有一些命令就晕了比如为什么有的命令可以cmd xx > yy << zz 难道先执行xx和yy？看这一章惊觉shell命令是一起被处理而不是一步一步执行的，恍然大悟！
具体内容倒没有很多，我们只需要给不同的东西实现file trait就可以在进程中使用文件描述符等来管理它，再在运行时动态分配到stdout 特有的write函数中去打印到屏幕上。
io重定向也是类似的原理，通过一些操作读取第一个程序的stdout然后作为输入交给第二个程序，也就实现了重定向了。
进程间通信同理，我们给进程间通信的ringbuffer也实现read write等方法，在调用时实际写入一个ringbuffer而非实际文件即可。

Chapter 8 并发

这一节大部分内容真是学了无数遍了，OSTEP学了一遍，ECE650学了一遍，这次又学了一遍。锁，信号量，条件变量着实是滚瓜烂熟了。倒是线程管理的部分非常有趣。这一章把rcore变成了类似linux的方式，线程是基本的调度单位，进程仅仅维护fd_table, memoryset等进程共享资源。为了添加线程的支持，进程需要维护好每个线程的上下文和运行栈，线程的栈因为共享地址空间所以会被放置在特定的内存位置统一管理。在切换的时候与进程调度基本一致。
如果需要跨进程切换线程switch函数会负责切换地址空间，来保证线程的顺利运行。
这一章的lab是实现银行家算法。算是个蛮有意思的题目。但是感觉实现本身和OS的线程调度机制没有太大的关系，而且由于类似算法的时间复杂度实际操作系统中应该不会包含类似的算法。如果题目可以和OS本身更加相关就好了

arceos部分

Lab1 Print

第一个lab非常简单，只需要在println宏中加入riscv对应颜色的转义字符即可。注意要在打印后使用reset转义字符，不然后面所有的输出就都变颜色了。
下面是一些常用的转义字符

const ANSI_CODES: &[(&str, &str)] = &[
    // 基本颜色
    ("BLACK", "\x1b[30m"),
    ("RED", "\x1b[31m"),
    ("GREEN", "\x1b[32m"),
    ("YELLOW", "\x1b[33m"),
    ("BLUE", "\x1b[34m"),
    ("MAGENTA", "\x1b[35m"),
    ("CYAN", "\x1b[36m"),
    ("WHITE", "\x1b[37m"),
    
    // 粗体颜色
    ("BRIGHT_BLACK", "\x1b[90m"),
    ("BRIGHT_RED", "\x1b[91m"),
    ("BRIGHT_GREEN", "\x1b[92m"),
    ("BRIGHT_YELLOW", "\x1b[93m"),
    ("BRIGHT_BLUE", "\x1b[94m"),
    ("BRIGHT_MAGENTA", "\x1b[95m"),
    ("BRIGHT_CYAN", "\x1b[96m"),
    ("BRIGHT_WHITE", "\x1b[97m"),
    
    // 背景色
    ("BG_BLACK", "\x1b[40m"),
    ("BG_RED", "\x1b[41m"),
    // ... 其他背景色
    
    // 样式
    ("BOLD", "\x1b[1m"),
    ("UNDERLINE", "\x1b[4m"),
    ("REVERSED", "\x1b[7m"),
    
    // 控制
    ("RESET", "\x1b[0m"),
];

Lab 2 Hashmap

由于测例非常简单，所以偷了一下懒，用嵌套vector实现的hashmap，甚至没有实现resize(非常懒了！)
这一个lab的难度也不在写代码上，重点在于理解ArceOS的代码结构，然后把HashMap的代码糊上即可。
实验中遇到了两个小坑，

因为在std的lib.rs 中已经引用了alloc中的collections，因此我们的hashmap不能在collections里面，必须命名成别的，我命名成了axcollections。exercise中的用户态程序也要同步更改。
我的hashmap实现中用到了vector，因此需要用到globalallocator调用alloc动态分配内存。但是在第一个测试print_with_color编译选项中没有编译allocator。因此需要在axstd中我们的collections前面加上编译选项的宏，这样就编译第一个测试才不会报错。
1
2
3

#[cfg(feature = "alloc")]
pub mod axcollections;
目前对ArceOS有了一个比较初步的理解
axlibc和axstd对应linux中的glibc和std。是用户态程序，会通过系统api(位于arceos/api )和os通信（而不是syscall？）
OS的核心代码在modules中，包括了硬件抽象层HAL，内存管理MM，网络，进程管理等等都以模块化管理。这次作业比较相关的动态内存分配GlobalAllocator实现在了在axalloc中
还有一个意外得到知识是哈希函数本身
这次第一次用到Rust的Hash trait。这个trait提供hash函数，接收一个实现了Hasher trait的state
为什么需要一个带state的Hasher而不能直接Hash返回一组字节呢？
因为希望灵活的处理哈希算法，并且比如你有多个字段或者字段内部有嵌套的字段它们都需要被被哈希，这个时候hash(hasher)可以帮助你抽象掉冗杂的细节，实现增量哈希。
ps: 在哈希或密码学最忌讳灵机一动,我一开始想着把多个字段的哈希值直接异或也可以得到一个值呀，但这样的算法会面临严重的碰撞问题，比如(a,b,c)和(c,b,a)会得到相同的哈希值，会对哈希表的性能产生很大的影响。

Lab 3 Bump Allocator

这次的实验是实现一个Global Allocator。这是我一直非常好奇的一个部分。在rcore实验，rcore已经提供了一个实现好的buddy allocator。这次终于有机会自己实现了。
研读代码后发现，Global Allocator虽然名义上管理memory的allocation，但它实际上并不操作任何memory。它只是个“数字管理器”，记录哪些块被分出去，哪些块没有。实际上也没有任何措施来保证未分配的块不能被访问——这个功能是由Page Table通过页表项中合理的bit设定通过硬件保证的。
我在这里意外的发现Slab Allocator的实现和之前在CSAPP学习到的malloc实现惊人的相似。都是通过二的幂次管理多重链表来平衡分配内存的时间复杂度和额外空间占用。仔细想来也非常合理。global allocator和malloc实际上不涉及任何用户态和内核态的内容。它们本质上都是管理一段连续的数组，然后通过一定的算法尽量保证这个数组被高效利用。那么最终收敛到相似的设计就完全可以理解了。
本身的代码非常简单，略过不提。

Lab 4 File Rename

这次的实验是实现file rename操作。我照着ppt里的要求实现了结果发现ppt的作业和实际跑的test并不一样（尴尬。
由于myfilesystem的大部分实现是调用的现有库，无法更改。我的move实现本质上并没有操作文件系统，而是单纯的调用操作系统的API把一个文件内容读出来，然后创建并写入新文件。算是取巧过去了。
如果需要在文件系统层级实现rename，无需如此笨拙，只需更改directory node中对应的name，将name复制到new path 的directory node中即可。根本无需访问inode进行整个文件的读写

Lab 5 sys_mmap

这次实验是给教学用的arceos添加mmap操作。之前并没怎么使用过linux的mmap映射文件的功能。恰好借助这个机会补充一下。map文件到内存听上去很高大上，其实仔细想来只需要做三件事。

根据用户的参数申请一段连续内存
将文件内容读入内存并写到对应的内存上
当对应内存写入时，标记脏页并由内核线程写回磁盘(类似于文件写)
在这次lab中，由于测例比较简单并没有实现3.
1和2的实现方法需要找到陷入当前trap的进程的currentTask控制块，然后在它的地址空间中预定一块内存。然后调用fs的api读取文件，再将文件写入对应的内存中。更理想的实现可能为修改fs的接口，让文件读取可以直接读取到一段指定内存，这可以减少一次内存的复制操作。
实现3的方法应该是借助MemoryArea的分类进行。比如文件申请的内存为FileBlockMemoryArea，有一个异步线程会定期被唤醒去把脏页写回block。所以对应到mmap当mmap需求的是map文件时，在map.alloc这个调用中需要指定类型为FileBlock。对于普通的操作则申请匿名内存，不需要异步线程进行检查

Lab6 simple_hv

这一个lab给我们展示了一个“最小hypervisor”的实现。类似于rcore Lab中的syscall实验。在rcore和arceos阶段研读过操作系统的代码后，实际上Hypervisor的运行方式并不难以想象。操作系统的目的是，安全，高效的同时运行多个程序。为了达成这个目的主要实现了抢占式调度，地址空间，以及特权级机制。Hypervisor同理，它要安全，高效的运行多个操作系统。因此也可以通过类似的方法，比如抢占式调度（或者干脆利用多核实现真并行调度，如教学代码所示），对于操作系统来说也需要“虚拟物理地址”，相当于一个vm级别的地址空间。另外，OS不再直接管理外设，也不能直接控制硬件，所以对于一些可能影响硬件的”危险操作“我们再进行一次特权级的隔离。让os通过与syscall类似的hypercall把这些操作的权利交给hypervisor定夺。
仔细想想，实际上type-II hypervisor也几乎可以通过类似的机制实现。这一套并不局限于直接运行在硬件上的Type-I Hypervisor，只要硬件提供特权级的隔离这一套可以轻易实现。硬件支持真是个好东西。想到了当时读Xen的论文，通过Para Virtualization重量级实现hypervisor那种巨大的工程量，再到现在各个处理器指令集都支持虚拟化扩展，可以通过几百行代码实现一个简单虚拟机。也算是软件系统的需求促进的硬件发展的一个样例了。
时过境迁，前两年Timothy在OSDI疾呼研究者应该回归OS的本质做hardware-software co-design。现在新硬件层出不穷，硬件加速器，智能网卡，TEE，还有RDMA，CXL一堆新名词。好像“攻守之势异也”，变成了硬件推动OS进步了。面对着越来越多的外设和越来越专业化的使用场景，操作系统研究者的未来又在何方呢？

2025春操作系统训练营游记（一二阶段）

Posted on 2025-05-02 Edited on 2025-06-04

Caiwen 的 2025 年春季操作系统训练营一二阶段的学习笔记

2025春夏操作系统训练营第二阶段总结-heirish

Posted on 2025-05-01 Edited on 2025-06-04

总结

第二阶段的强度慢慢上来了，由于平时要上班和前期收不到短信验证码的问题,不能跟上每周的直播课，主要通过学习tutorial文档和课后看录频和课件的方式学习。本阶段对内存管理，进程管理和文件系统, 线程进行了系统的学习。特别是内存映射和文件系统章节，学习到很多。同时，随着代码量增大，学习的同时画UML图对理解代码和整个框架也很有帮助。

Rust补完计划

Posted on 2025-05-01 Edited on 2025-06-04 In 补完计划

Rust补完计划

src：rust官网，rust官文，rust官仓，crates.io，rust-wiki，卡狗圣经

Rust可看作一个在语法层面（编译时）具有严格检查和限制的C语言上位。且扩展了面向对象的便捷方法绑定。编译和运行方式类似于C/C++，可以rustc xxx.rs编译，./xxx运行。有约定的项目目录格式，可使用Cargo配置toml进行包管理、编译、运行、测试等等。包资源网站为CratesIO，见src↑。不支持运算符重载，支持多态。其中语句为：表达式+;，语句的值是()。

为了安全，几乎所有的方法/变量/属性都是私有的，除非使用pub进行显式公用声明。

说到底，编程语言就是人类用来快速生成机器码以便于执行的模板引擎，有的语法层面(编译时/解释时)有强约束，有的仅仅是把特定字符串替换成另外的字符串或二进制，属于弱约束或者无约束。所有你在编程语言所看到的抽象，在机器码的层面本来就是一场幻月楼阁。比如你在编程语言层面，继承多态面向对象权限生命周期搞的花里胡哨的，但是在机器码看来，就仅仅是把PC变一下，或者某数据/指针变一下而已，你所关心的语法层面，语义特性，都是高层编译时/解释时的语法约束。这些约束让你写正确的高级语法的同时，最重要的是保证执行的结果符合预期。所以学底层的，一定要层层解耦，梳理层层抽象！

快速开始

安装：

1	curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs \| sh

推荐开发环境：

VSCode + rust-analyzer，VIM，RustRover

见面礼：

1 2	// main.rs fn main() { println!("hello world!") }

1	rustc main.rs -o main && ./main

使用包管理器：

cargo new my_project_name	# 生成项目目录结构，包括`toml`、`lock`、`src`、`test`等等
cargo build					# 编译后生成文件在`target/debug/项目名`下生成可执行文件，可选--release生成优化版本
cargo run					# 仅run也会build
cargo clean					# 清除target下编译后的文件
cargo check					# 仅检查语法是否出错
# 安装新的包，在Cargo.toml的依赖下配置：`包名=版本`即可

包管理器代理：vim ~/.cargo/config.toml

[source.crates-io]
replace-with = 'ustc'

[source.ustc]
registry = "sparse+https://mirrors.ustc.edu.cn/crates.io-index/"

初次接触

语法语义一览表：

标识符：^[a-Z0-9_][a-Z0-9_$]* 其中，命名习惯为：CONST_VAL，StructName，ImplName，method_name，val_name

注释符：// 单行注释，/* 多行注释 */，/// 文档注释，支持MD语法以及文档测试以及自动生成文档

运算符：+ - * / % += -= *= /= %= ! ~|& ^ [] ; , >> << == != < <= > >= && ||

变量声明：const CONST_VAL: i32 = 123; static STATIC_VAL: u32 = 321; let emm = 233; let mut var = 0;

类型别名：type word = u64

类型转换：var as type_name type_name::from(var)

分支：if 条件必须是布尔值 { ... } else { ... } match obj { case xx => { ... }, _ => { ... } }

循环：loop { ... } for i in 0..10 while n < 233，break continue

支持循环标签来跳出指定的循环：tag1: loop { tag2: while true { break: tag1 } }

函数格式：fn add(a: i32, b: i32) -> i32 { a + b } 默认返回值是最后一条表达式的值，等同于：return a+b;

匿名函数：|a: i32, b: i32| -> i32 { a + b } 如果只有一条执行语句，可以省略大括号

类和对象：采用结构体struct(存数据)和特质trait(类似于抽象interface存方法)抽象，数据方法分离的思想

方法多态：方法和数据的关系是多对多，支持采用数据/特质签名来访问匿去的数据/方法：TraitA::fun1(&obj)

基本类型：i8 u8 i16 u16 … 有无符号+位数，str，bool，f64 … 同整型

类型变体：&i32 - 不可变引用，&mut - 可变引用，*const - 不可变裸指针，*mut - 可变裸指针

容器类型：[1, 2, 3] - Array - 定长同类型，(1, "heke", 1228) - Tuple - 定长不可变

数据容器：struct Person { age: u8; name: &str; } struct Bag (i32, i32, u8)

枚举类型：enum State { StateA, StateB, State233=233, ,PA(ch) ... } 详见特殊部分与模式匹配 ↓

其他容器：Vec，Deque，Queue，BTreeSet，BTreeMap …

导入管理：mod package_emm; mod mode_name { fn emm() { ... } } use mode_name::emm;

异步支持：async，await，std::thread，以及异步的通道和异步智能指针

快速迁移（将采用Py作为对比语言）：

1 2	def emm(a: int, b: int) -> float: return float(a) + b

pub fn emm(a: i32, b: i32) -> f64 {
    // 运算块的值是最后一句表达式的值，所以不显示写return也可以，语句的值是()表示空！
    a as f64 + b    // 或写为：`return a as f64 + b` 或 `return f64::from(a) + b;`
}

1
2
3

def emm(op) -> (int, str, int):
    op
    return 1, "heke", 1228

pub fn emm(op) -> (i32, &str, i32) {  // op会在编译时自动根据所调用时的类型生成对应类型标签的多态方法
    op;
    1, "heke".as_str(), 1228
}

class A:
    def __init__(self, a: int, b: int, c: int):
        self.a = a
        self.b = b
        self.c = c
    
    def method233(self):
        self.a += self.b
        return None

if __name__ == '__main__':
	obj = A(1,2,3)
    obj.method233()
    print(f"a: {obj.a}, b: {obj.b}")
    print("c: ", obj.c)

struct A {
    pub a: i32,
    pub b: i32,
    pub c: i32,
}
impl A {
    pub fn method233(&self) {
        self.a += self.b;
        return None;
    }
}
fn main() {
    let mut obj = A {a: 1, b: 2, c: 3};
    obj.method233();
    println!("{}", format!("a: {}, b: {}", obj.a, obj.b));
    println!("c: {}", obj.c);
}

1
2
3

# method.py
def func():
    pass

# __init__.py
from method import *		# '0

from method import func		# 语法多余，但是为了对比语法'1
from .method import func	# 语法多余，但是为了对比语法'2
__all__ = ['func']			# 'export

func()
method.func()

// method.rs
pub fn func() {
    ;
}

// lib.rs / mod.rs
mod method;						// '0
use method::*;					// '0

pub use method::func;			// pub use使得导入此包的也可以被别的包从此包导入'1 'export
pub use crate::method::func;	// crate表示从包的根目录进行相对路径索引'2 'export

// 如果有main，则在main内：
func();
method::func();
crate::method::func();

rcore-camp-2025S-stage1&2-颜熙炆.md

Posted on 2025-04-30 Edited on 2025-06-04

前导

本博客作为开源操作系统训练营2025S的1、2阶段学习记录，简单总结了在这两个阶段的学习和coding。留作纪念，也希望能够帮助到大家。

二阶段

三阶段

rcore第二阶段学习心得

1. 应用程序与基本执行环境

2. 批处理系统

3. 多道程序与分时多任务

4. 地址空间

5. 进程与进程管理

6. 文件系统与重定向

7. 进程间通信（IPC）

8. 并发机制

rCore学习笔记

原生之初

CPU做了什么？

ISA做了什么？

SBI做了什么？

OS做了什么？

Syscall做了什么？

用户程序做了什么？

所以他们做了什么？

批处理

多道分时

地址空间

进程管理

文件系统

管道通信

并发和锁

Rust warm-up

rCore-OS

Lab 1 Time sharing multitasking

Lab 2 virtual memory

Lab 3 process

Lab 4 file system

Lab 5 thread

ArceOS

Lab 1 color print

Lab 2 hashmap

Lab 3 bump allocator

Lab 4 file rename

Lab 5 mmap

Lab 6 hypervisor

rcore 总结

Lab1

最终设计思路

踩坑记录

lab2

最终设计思路

踩坑记录

lab3

实现过程

lab4

实现过程

lab5

算法记录

实验过程

arceos 总结

1 基础调用流程

2 动态内存分配支持

3 ReadPFlash 引入页表

4 启动子任务

5 协作式调度算法

6 抢占式调度

7 ReadBlock

8 加入文件系统

9 引入特权级

10 缺页异常与内存映射

11 Hypervisor

12 Hypervisor 两阶段地址映射

13 虚拟时钟中断支持；虚拟机外设的支持

rcore部分

Chapter 1 应用程序与基本执行环境

Chapter 2 批处理系统

Chapter 3 多道程序与分时多任务

Chapter 4 地址空间

Chapter 5 进程

Chapter 6 文件系统

Chapter 7 进程间通信

Chapter 8 并发

arceos部分

Lab1 Print