rcore-os Blog
0%

2023开源操作系统训练营一二阶段总结-TheSayOL

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