0%

2022开源操作系统夏令营总结-翟启明

2022开源操作系统夏令营总结-翟启明

repo:https://github.com/jackming2271

第一阶段总结

学习过程

学习路线

  • 耗时: 3周+(平均每天3小时左右)
  • 学习路线: 基本按照Schedule的指导
  • 目前进度: 完成全部Lab与Report

首先是学习过程

在学习的过程中, 得益于全面的各种参考资料以及完善的工具链, 我用了3周多的时间, 按照Schedule的指导, 基本顺利完成Lab1~5以及对应的实验报告. 我的主要学习路径就是阅读指导书 以及 更全面的rCore-Tutorial-Book-v3 , 学习过程中整理学习笔记, 对于理解不清晰的模块会仔细梳理代码逻辑直到过程清晰. 在写实验报告的时候再回顾一下整章代码架构, 以及相对于上一章的进化, 这样学习下来对于一章内的知识就有了比较好的把握, 同时也能将内核的演进串联起来

学习氛围

  • 技术氛围浓厚
  • 同学热心互助
  • 目标一致

另外, 各位同学间互相交流的氛围非常好, 大家兴趣驱动&目标一致,个人提出的多个问题问题都得到了积极回复与解决, 也从其他同学提出的问题和相关答复中学到了很多;

个人成长

操作系统

  • 从理论到实践, 从黑盒到白盒
  • 软件开发能力提升
  • 底层思维

接下来是个人成长方面:

在操作系统方面:

  • 浅知理论和(在深入理解的基础上)动手实践是完全不同的感受, 在学习完成内核中一个个功能的具体实现之后, 个人对于操作系统的理解也不断拓展和深入, 之前不理解的一些问题(如实现虚拟内存是如何软硬协作的, 硬盘是如何完成数据存储的等)也都迎刃而解;
  • 在编写各种用户态程序时能从更深的维度思考如何更高效使用CPU/存储, 更清晰的使用多进程/多线程机制实现程序; 在程序异常如core分析/内存泄露等时能从操作系统的角度出发分析问题;

知识领域

  • Rust / Risc-V / 硬件

在知识领域方面:
个人的工作方向主要是后端研发和数据分析, 日常接触到的没有那么底层, 对于通过本次学习学习了一个新的领域, 了解了操作系统开发, 接触很多新技术如RUST语言 / RISC-V汇编 / 硬件机制等, 让自己在编程语言和体系结构等方向的能力也得到了拓展

建议

  • 全流程效能提升
  • 多分享交流

优秀的项目是靠大家一起打磨出来的, 在开发/编译/调试/测试的任何阶段的优化,都会带来全流程的效能提升, 学习或完成实验的过程中如果发现可以优化的地方, 可以多抛出问题多交流, 共同优化提升整体效能

感受

  • 感受到操作系统的深邃
  • 计算机基础 & 编程语言提升, 收获满满
  • 获得成长 & 反馈社区

参与第一阶段的项目让我感受到了操作系统的复杂与优美, 也让我编程语言和计算机基础知识的掌握程度得到了很大提升, 同时加强了自身的软件开发能力, 感谢各位老师助教提供的宝贵机会, 未来将和大家继续努力学习&反馈社区

第一阶段实验报告

本报告为个人在参与 2022年开源操作系统训练营 期间完成, 主要包括 6 个实验报告(对应 指导文档 中ch3~8), 内容涉及了操作系统中的 特权级切换/进程调度/虚拟内存管理/多线程分析等 重点知识.

Lab1-Ch3

功能总结

实现了sys_task_info系统调用,可以获取当前进程的 运行状态/运行时长/每种系统调用的使用次数

  • 运行状态: 由于只能查询当前任务, 所以任务状态只能为 Running
  • 运行时长: 在TaskControlBlock中记录开始运行的时间戳, 查询时使用 (当前时间 - 开始时间) 获取运行时长
  • 系统调用的使用次数: 在中断转发时,转发前一刻将系统调用使用次数+1

    问答题

  1. 正确进入 U 态后,程序的特征还应有:使用 S 态特权指令,访问 S 态寄存器后会报错。 请同学们可以自行测试这些内容 (运行 Rust 三个 bad 测例 (ch2b_bad_*.rs) , 注意在编译时至少需要指定 LOG=ERROR 才能观察到内核的报错信息) , 描述程序出错行为,同时注意注明你使用的 sbi 及其版本。

在低特权级使用更高特权级的指令 / 访问非法地址等都会触发异常,出core
[ERROR] [kernel] PageFault in application, bad addr = 0x0, bad instruction = 0x80400408, core dumped.
[ERROR] [kernel] IllegalInstruction in application, core dumped.
[ERROR] [kernel] IllegalInstruction in application, core dumped.

  1. 深入理解 trap.S 中两个函数 __alltraps 和 __restore 的作用,并回答如下问题:
  • L40:刚进入 __restore 时,a0 代表了什么值。请指出 __restore 的两种使用情景。
    a0 寄存器放置函数返回值, a0中的地址是 trap_handler 的返回值, 指向任务内核栈上的trap_context的地址
    两种使用场景: 完成中断处理后返回用户态继续执行 / 首次被调度为Running时进入用户态

  • L46-L51:这几行汇编代码特殊处理了哪些寄存器?这些寄存器的的值对于进入用户态有何意义?请分别解释。

    1
    2
    3
    4
    5
    6
    ld t0, 32*8(sp)
    ld t1, 33*8(sp)
    ld t2, 2*8(sp)
    csrw sstatus, t0 // 记录中断发生前的许多信息如特权级等
    csrw sepc, t1 // 系统调用返回用户态时从何处开始执行 or 异常代码发生的位置
    csrw sscratch, t2 // 保存内核栈位置
  • L53-L59:为何跳过了 x2 和 x4?
    x2: x2即为sp寄存器, 其实已经保存到sscratch了
    x4: 使用不到,不用保存

    1
    2
    3
    4
    5
    6
    7
    ld x1, 1*8(sp)
    ld x3, 3*8(sp)
    .set n, 5
    .rept 27
    LOAD_GP %n
    .set n, n+1
    .endr
  • L63:该指令( csrrw sp, sscratch, sp )之后,sp 和 sscratch 中的值分别有什么意义?
    sp 和 sscratch 分别指向 内核栈/用户栈 其中的一个和另一个, 执行之后他们的指向发生交换, 此处sp指向用户栈, sscratch指向进程内核栈

  • __restore:中发生状态切换在哪一条指令?为何该指令执行之后会进入用户态?
    sret指令;指令执行后:CPU 会将当前的特权级按照 sstatus 的 SPP 字段设置为 U 或者 S ;CPU 会跳转到 sepc 寄存器指向的那条指令,然后继续执行。

  • L13:该指令( csrrw sp, sscratch, sp )之后,sp 和 sscratch 中的值分别有什么意义?
    sp 和 sscratch 分别指向 内核栈/用户栈 其中的一个和另一个, 执行之后他们的指向发生交换, 此处sscratch指向用户栈, sp指向进程内核栈

  • 从 U 态进入 S 态是哪一条指令发生的?
    ecall

    对本次实验设计及难度/工作量的看法,以及有哪些需要改进的地方

    难度适中,对于起步正好合适

Lab2-Ch4

功能总结

实现了 mmap 和 munmap 系统调用, 提供了在用户态动态申请物理内存的接口

1
2
3
4
/// 申请长度为 len 字节的物理内存(不要求实际物理内存位置,可以随便找一块),将其映射到 start 开始的虚存,内存页属性为 port
fn sys_mmap(start: usize, len: usize, port: usize) -> isize
/// 取消到 [start, start + len) 虚存的映射
fn sys_munmap(start: usize, len: usize) -> isize

mmap实现方法: 通过memory_space的insert_framed_area方法, 每次mmap请求都尝试插入一个area
munmap实现方法: 通过遍历当前memory_space下所有area维护的映射, 如果虚拟页面落在在本次要拆除映射的区间, 则进行拆除操作

问答总结

  1. 请列举 SV39 页表页表项的组成,描述其中的标志位有何作用?

    • V 位决定了该页表项的其余部分是否有效(V = 1 时有效)。若 V = 0,则任何遍历到此页表项的虚址转换操作都会导致页错误。
    • R、W 和 X 位分别表示此页是否可以读取、写入和执行。如果这三个位都是 0,那么这个页表项是指向下一级页表的指针,否则它是页表树的一个叶节点。
    • U 位表示该页是否是用户页面。若 U = 0,则 U 模式不能访问此页面,但 S 模式可以。若 U = 1,则 U 模式下能访问这个页面,而 S 模式不能。
    • G 位表示这个映射是否对所有虚址空间有效,硬件可以用这个信息来提高地址转换的性能。这一位通常只用于属于操作系统的页面。
    • A 位表示自从上次 A 位被清除以来,该页面访问过。
    • D 位表示自从上次清除 D 位以来页面是否被弄脏(例如被写入)。
    • RSW 域留给操作系统使用,它会被硬件忽略。
    • PPN 域包含物理页号,这是物理地址的一部分。若这个页表项是一个叶节点,那么 PPN 是转换后物理地址的一部分。否则 PPN 给出下一节页表的地址。
  2. 缺页

缺页异常是一种正在运行的程序访问当前未由内存管理单元(MMU)映射到虚拟内存的页面时,由计算机硬件引发的异常类型。访问未被映射的页或访问权限不足,都会导致该类异常的发生。处理缺页异常通常是操作系统内核的一部分。当处理缺页异常时,操作系统将尝试使所需页面在物理内存中的位置变得可访问(建立新的映射关系到虚拟内存)。而如果在非法访问内存的情况下,即发现触发Page Fault的虚拟内存地址(Bad Address)不在当前进程 vm_area_struct链表中所定义的允许访问的虚拟内存地址范围内,或访问位置的权限条件不满足时,缺页异常处理将终止该程序的继续运行。

  • 请问哪些异常可能是缺页导致的?
    当系统运行发生异常时,可即时地通过解析csr scause寄存器的值,识别如下三种不同的Page Fault

    Exception Code = 12: page fault caused by an instruction fetch
    Exception Code = 13: page fault caused by a read
    Exception Code = 15: page fault caused by a write

  • 发生缺页时,描述相关重要寄存器的值,上次实验描述过的可以简略.
    八个控制状态寄存器(CSR)是机器模式(M态)下异常处理的必要部分:

    • mtvec(Machine Trap Vector)它保存发生异常时处理器需要跳转到的地址。

    • mepc(Machine Exception PC)它指向发生异常的指令。

    • mcause(Machine Exception Cause)它指示发生异常的种类。

    • mie(Machine Interrupt Enable)它指出处理器目前能处理和必须忽略的中断。

    • mip(Machine Interrupt Pending)它列出目前正准备处理的中断。

    • mtval(Machine Trap Value)它保存了陷入(trap)的附加信息:地址exception中出错的地址、发生非法指令exception的指令本身,对于其他异常,它的值为 0。

    • mscratch(Machine Scratch)它暂时存放一个字大小的数据。

    • mstatus(Machine Status)它保存全局中断使能,以及许多其他的状态

      S 模式有几个异常处理 CSR:sepc、stvec、scause、sscratch、stval 和 sstatus,它们执行与 M 模式 CSR 同的功能。监管者异常返回指令 sret 与 mret 的行为相同,但它作用于 S 模式的异常处理CSR,而不是 M 模式的 CSR。S 模式处理例外的行为已和 M 模式非常相似。如果 hart 接受了异常并且把它委派给了S 模式,则硬件会原子地经历几个类似的状态转换,其中用到了 S 模式而不是 M 模式的CSR:

    • 发生例外的指令的 PC 被存入 sepc,且 PC 被设置为 stvec。

    • scause 根据异常类型设置值,stval 被设置成出错的地址或者其它特定异常的信息字。

    • 把 sstatus CSR 中的 SIE 置零,屏蔽中断,且 SIE 之前的值被保存在 SPIE 中。

    • 发生exception时的权限模式被保存在 sstatus 的 SPP 域,然后设置当前模式为 S 模式。

  • 缺页有两个常见的原因,其一是 Lazy 策略,也就是直到内存页面被访问才实际进行页表操作。 比如,一个程序被执行时,进程的代码段理论上需要从磁盘加载到内存。但是 os 并不会马上这样做, 而是会保存 .text 段在磁盘的位置信息,在这些代码第一次被执行时才完成从磁盘的加载操作。这样做有哪些好处?
    基于此机制, 程序开始运行时并不需要将全部内容加载到内存, 也就是说在 程序运行的机器的实际物理内存 小于 进程运行所需总内存时, 程序依然能够通过页面的换入换出机制运行起来;

其实,我们的 mmap 也可以采取 Lazy 策略,比如:一个用户进程先后申请了 10G 的内存空间, 然后用了其中 1M 就直接退出了。按照现在的做法,我们显然亏大了,进行了很多没有意义的页表操作。

  • 处理 10G 连续的内存页面,对应的 SV39 页表大致占用多少内存 (估算数量级即可)?
    10G / 512

  • 请简单思考如何才能实现 Lazy 策略,缺页时又如何处理?描述合理即可,不需要考虑实现。
    不考虑局部性的情况下, 使用lazy策略时, 根据发生缺页异常的类型, 去memory_set的各个段寻找 [缺页的虚拟地址在当前逻辑段 && 逻辑段权限达到缺页的要求], 如果寻找成功, 则将页面加载到物理内存并映射;

  • 缺页的另一个常见原因是 swap 策略,也就是内存页面可能被换到磁盘上了,导致对应页面失效。此时页面失效如何表现在页表项(PTE)上?
    V权限位为0
    双页表与单页表

  1. 为了防范侧信道攻击,我们的 os 使用了双页表。但是传统的设计一直是单页表的,也就是说, 用户线程和对应的内核线程共用同一张页表,只不过内核对应的地址只允许在内核态访问。 (备注:这里的单/双的说法仅为自创的通俗说法,并无这个名词概念,详情见 KPTI )
  • 在单页表情况下,如何更换页表?
    切换任务后, 返回用户态时重写sntp

  • 单页表情况下,如何控制用户态无法访问内核页面?(tips:看看上一题最后一问)
    内核对应的地址只允许在内核态访问, PTE 的 U = 0

  • 单页表有何优势?(回答合理即可)
    用户态和内核态切换时不用更换页表

  • 双页表实现下,何时需要更换页表?假设你写一个单页表操作系统,你会选择何时更换页表(回答合理即可)?
    用户态和内核态切换时; 在返回用户态时 or 任务切换时, 因为内核部分都是一样的;

对本次实验设计及难度/工作量的看法,以及有哪些需要改进的地方

难点在于理解虚拟内存, 实验代码基于现有框架难度不大. 希望能有Lazy策略 和 Swap策略的实现学习 orz

Lab3-Ch5

功能总结

spwan系统调用
新建子进程,使其执行目标程序 (从结果来看是等于Fork + Exec, 但是过程是不同的)
实现思路: 整体过程基本与task::new()的过程相同

stride 优先级调度算法

基于优先级的进程调度算法, 每个进程有一个优先级, 优先级越高执行频率越高
实现思路: 在TASK_MANAGER中每次选择stride最小的进程, 按照调度算法计算出步长(MAX_STRIDE / Priority), 然后进程stride加上这个值; 关于原理可以参看: 关于stride schedule很好的一个解释

问答总结

stride 算法深入

stride 算法原理非常简单,但是有一个比较大的问题。例如两个 stride = 10 的进程,使用 8bit 无符号整形储存 pass, p1.pass = 255, p2.pass = 250,在 p2 执行一个时间片后,理论上下一次应该 p1 执行。

  • 实际情况是轮到 p1 执行吗?为什么?
    不是, 250 + 10 = 260 , 无符号整数溢出后回转变为 4 (260 % 256) , 4 < 255 , 所以 p2 继续执行

我们之前要求进程优先级 >= 2 其实就是为了解决这个问题。可以证明, 在不考虑溢出的情况下 , 在进程优先级全部 >= 2 的情况下,如果严格按照算法执行,那么 PASS_MAX – PASS_MIN <= BigStride / 2

  • 为什么?尝试简单说明(不要求严格证明)。
    每次增大的都是最小的, 每次增大的步幅小的进程调度的次数多, 每次增大的步幅大的进程调度的次数少 {% asset_img stride.png stride调度进程PASS值变化 %}

已知以上结论,考虑溢出的情况下,可以为 pass 设计特别的比较器,让 BinaryHeap 的 pop 方法能返回真正最小的 Pass。补全下列代码中的 partial_cmp 函数,假设两个 Pass 永远不会相等。
TIPS: 使用 8 bits 存储 pass, BigStride = 255, 则: (125 < 255) == false, (129 < 255) == true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
use core::cmp::Ordering;

struct Pass(u64);

impl PartialOrd for Pass {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {

let cmp: i64 = (self.0 - other.0) as i64;
if cmp < 0 {
Some(Ordering::Less)
} else if cmp == 0 {
Some(Ordering::Equal)
} else {
Some(Ordering::Greater)
}
}
}

impl PartialEq for Pass {
fn eq(&self, other: &Self) -> bool {
false
}
}

对本次实验设计及难度/工作量的看法,以及有哪些需要改进的地方

可以在练习部分多给出一些相关参考资料

Lab4-Ch6

功能总结

实现三个系统调用 sys_linkat、sys_unlinkat、sys_stat

  • sys_linkat: 为现有的文件创建一个硬连接; 通过在FileSystem中添加一个name不同但是inode相同的目录项实现;
  • sys_unlinkat: 取消硬连接; 删除目录项; 如果删除后硬链接数量 = 0, 回收文件占用的资源;
  • sys_stat: 获取文件的各种信息如硬链接数量等

问答总结

  1. 在我们的easy-fs中,root inode起着什么作用?如果root inode中的内容损坏了,会发生什么?
    root inode是根目录索引的inode, root inode 对应的数据区维护了所有的目录项;
    如果损坏目录项会丢失, 导致无法根据name对文件进行操作

你对本次实验设计及难度/工作量的看法,以及有哪些需要改进的地方,欢迎畅所欲言

Ch7

功能总结

本章无编程内容

问答总结

  1. 举出使用 pipe 的一个实际应用的例子
    netstat -nap | grep 80

  2. 如果需要在多个进程间互相通信,则需要为每一对进程建立一个管道,非常繁琐,请设计一个更易用的多进程通信机制
    消息队列, 共享内存等

Lab5-Ch8

功能总结

实现死锁检测功能. 目前的 mutex 和 semaphore 相关的系统调用不会分析资源的依赖情况,用户程序可能出现死锁。 我们希望在系统中加入死锁检测机制,当发现可能发生死锁时拒绝对应的资源获取请求.
注意此处的死锁检测和银行家算法(死锁避免算法)是不同的, 死锁检测是针对当前状态, 判断当前资源分配情况是否能让所有线程都继续运行(而不是每个都运行结束). 所以只基于每个线程对资源的请求(即 锁Lock or 信号量down), 来构造需求矩阵need / 维护alloc / 维护available , 就能完成判断了

问答总结

  1. 在我们的多线程实现中,当主线程 (即 0 号线程) 退出时,视为整个进程退出, 此时需要结束该进程管理的所有线程并回收其资源。
    • 需要回收的资源有哪些?
      回收TaskUserRes相关(提前回收, 不然会释放两次, 因为drop在函数周期结束后才调用, 晚于memory_set.recycle_data_pages调用), 回收fd_table, 回收children
    • 其他线程的 TaskControlBlock 可能在哪些位置被引用,分别是否需要回收,为什么?
      可能在锁或者信号量等的数据结构上, 但是不用回收, 地址空间已回收, 子线程运行时会自动失败
  1. 对比以下两种 Mutex.unlock 的实现,二者有什么区别?这些区别可能会导致什么问题?
    如下第二种实现, 虽然将等待锁的线程重新开始调度, 但是锁并未释放, 会导致死锁
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     1 impl Mutex for Mutex1 {  
    2 fn unlock(&self) {
    3 let mut mutex_inner = self.inner.exclusive_access();
    4 assert!(mutex_inner.locked);
    5 mutex_inner.locked = false;
    6 if let Some(waking_task) = mutex_inner.wait_queue.pop_front() {
    7 add_task(waking_task);
    8 }
    9 }
    10 }
    11
    12 impl Mutex for Mutex2 {
    13 fn unlock(&self) {
    14 let mut mutex_inner = self.inner.exclusive_access();
    15 assert!(mutex_inner.locked);
    16 if let Some(waking_task) = mutex_inner.wait_queue.pop_front() {
    17 add_task(waking_task);
    18 } else {
    19 mutex_inner.locked = false;
    20 }
    21 }
    22 }

你对本次实验设计及难度/工作量的看法,以及有哪些需要改进的地方,欢迎畅所欲言

可以同时讲一下死锁避免和死锁检测