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

第一阶段总结

学习过程

学习路线

耗时: 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
问答题

正确进入 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.

深入理解 trap.S 中两个函数 __alltraps 和 __restore 的作用，并回答如下问题:

L40：刚进入 __restore 时，a0 代表了什么值。请指出 __restore 的两种使用情景。
a0 寄存器放置函数返回值, a0中的地址是 trap_handler 的返回值, 指向任务内核栈上的trap_context的地址
两种使用场景: 完成中断处理后返回用户态继续执行 / 首次被调度为Running时进入用户态

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

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 系统调用, 提供了在用户态动态申请物理内存的接口

/// 申请长度为 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维护的映射, 如果虚拟页面落在在本次要拆除映射的区间, 则进行拆除操作

问答总结

请列举 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 给出下一节页表的地址。
缺页

缺页异常是一种正在运行的程序访问当前未由内存管理单元（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
双页表与单页表

为了防范侧信道攻击，我们的 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.

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: 获取文件的各种信息如硬链接数量等

问答总结

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

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

Ch7

功能总结

本章无编程内容

问答总结

举出使用 pipe 的一个实际应用的例子
netstat -nap | grep 80
如果需要在多个进程间互相通信，则需要为每一对进程建立一个管道，非常繁琐，请设计一个更易用的多进程通信机制
消息队列, 共享内存等

Lab5-Ch8

功能总结

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

问答总结

在我们的多线程实现中，当主线程 (即 0 号线程) 退出时，视为整个进程退出，此时需要结束该进程管理的所有线程并回收其资源。
- 需要回收的资源有哪些？
  回收TaskUserRes相关(提前回收, 不然会释放两次, 因为drop在函数周期结束后才调用, 晚于memory_set.recycle_data_pages调用), 回收fd_table, 回收children
- 其他线程的 TaskControlBlock 可能在哪些位置被引用，分别是否需要回收，为什么？
  可能在锁或者信号量等的数据结构上, 但是不用回收, 地址空间已回收, 子线程运行时会自动失败

对比以下两种 Mutex.unlock 的实现，二者有什么区别？这些区别可能会导致什么问题?
如下第二种实现, 虽然将等待锁的线程重新开始调度, 但是锁并未释放, 会导致死锁

 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 }

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

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

第一阶段总结

学习过程

学习路线

学习氛围

个人成长

操作系统

知识领域

建议

感受

第一阶段实验报告

Lab1-Ch3

功能总结

问答题

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

Lab2-Ch4

功能总结

问答总结

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

Lab3-Ch5

功能总结

问答总结

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

Lab4-Ch6

功能总结

问答总结

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

Ch7

功能总结

问答总结

Lab5-Ch8

功能总结

问答总结

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