0%

1000oaks的rCore前二阶段小结

写小结一刻, 却不知写些什么.

  • 这已经是我第二次报名了rCore训练营了. 第一次报名于2022年夏季, 然而那个暑假我去研究托福的备考了, 所以第一次报名之后什么也没有做(虽然托福倒是速成成功, 但是这导致我下学期没有修读校内开设的操作系统研讨课). 要不是D同学督促我, 怕不是第二次报名也只停留于一阶段了.

  • 过分杞人忧天, 不如在rCore上静心研究.

Read more »

写在前面

作为上班族,每天下班很晚了,本来没有多余时间,并且之前没有接触过Rust

看到 从零开始用 Rust 语言写一个基于 RISC-V 架构的 类 Unix 内核这样标题

直接打退堂鼓。

转你一想 这就是自己本来期望形式,参与开源方向,操作系统 作为软件工程师 基本功,不管结果如何必须参与。

一阶段总结

  • 选择看什么资料,根据看c++经验,一定选择英文原版 代替看中文翻译,很多翻译遗漏很多信息。我直接选择 rustlings-100exercises README.md

  • 因为时间有限,没有采取全部看完book,然后做题,

    采取看一章节,做题 顺序

    https://github.com/LearningOS/rustlings-100exercises-template/blob/main/exercises/README.md

    rustlings 设计 很合理 提供 README和章节练习。为我节省大量时间

  • 选择在线开发环境

    群里分享了:rustlings流程web版.pdf 然后5分钟搭建好了环境,更适合上班 环境 和家里环境随时切换。

  • 遇到不懂怎么办?

    学习Rust出现新名词 :借用 让你莫不这头脑,我没有从概念理解 这些概念,

    并按照文字提示 翻译

    用c++设计进行类比:常量指针,指针常量, 类 深度拷贝 移动构造 ,move语义

    拷贝构造,还有STL

小结:

为了节省时间,我采用云环境(5分钟搭建完成)

做题顺序按照README.md 推荐方式 README对我帮助很大

二阶段总结

ch1 & ch2

  • 存在问题:

一个hello,world 例子是怎么运行的,代码从编译到产生可执行程序,然后加载到内存,程序入口是哪里 尤其是linker.ld entry.asm这2个文件。

尤其汇报指令。需要加强。之前看程序自我修养,

还有csapp 感觉看懂到,现在看来根本不懂,用了不少时间。

尤其看到别人满分了,担心着急,我还没真正投入开始呢。

  • 解决方式:

为了方便反复运行程序 我搭建vmare+本地环境。

rcore提供框架,让这些知识变成例子,

最后不依赖系统库运行在起来。这个演示例子非常好。

小结 :hello,world 例子

  1. 项目中 每个模块都个mod.rs文件 ,这一般是模块提供对提供功能。

  2. 程序入口地址

chapter3 练习

题目要求:

ch3 中,我们的系统已经能够支持多个任务分时轮流运行,我们希望引入一个新的系统调用 sys_task_info 以获取当前任务的信息,定义如下:

1
fn sys_task_info(ti: *mut TaskInfo) -> isize

思路

  1. 从单元测试 ch3_taskinfo.rs 了解到 ,直接创建了task,该task 可能执行很多系统调用系统调用最终都是通过 sys_call 进行,在该函数增加 add_syscall_count。

  2. 数据结构:TaskManagerInner 记录了正在运行的任务 current_task 和任务列表tasks,全局变量 只有一个。

  3. main.rs 函数启动时候 加载任务 并且运行第一任务

    loader::load_apps();

    task::run_first_task();

小结:系统调用

ch1 和ch2 是ch3 基础,下面这段代码 需要后面花费更多时间学习

1
2
3
4
5
6
7
8
9
10
11
pub fn rust_main() -> ! {
clear_bss();
kernel_log_info();
heap_alloc::init_heap();
trap::init();
loader::load_apps();
trap::enable_timer_interrupt();
timer::set_next_trigger();
task::run_first_task();
panic!("Unreachable in rust_main!");
}

chapter4练习

实验要求

重写 sys_get_time 和 sys_task_info

引入虚存机制后,原来内核的 sys_get_time 和 sys_task_info 函数实现就无效了。请你重写这个函数,恢复其正常功能。

mmap 和 munmap 匿名映射

mmap 在 Linux 中主要用于在内存中映射文件, 本次实验简化它的功能,仅用于申请内存。

请实现 mmap 和 munmap 系统调用,mmap 定义如下:

思路:地址空间

  1. 为什么 重写 sys_get_time 和 sys_task_info ?这从地址空间说起,原文:

    内核如何访问应用的数据?

    应用应该不能直接访问内核的数据,但内核可以访问应用的数据,这是如何做的?由于内核要管理应用,所以它负责构建自身和其他应用的多级页表。如果内核获得了一个应用数据的虚地址,内核就可以通过查询应用的页表来把应用的虚地址转换为物理地址,内核直接访问这个地址

    1
    2
    3
     let info = TaskInfo::new();  //info 这用户空间地址
    assert_eq!(0, task_info(&info));//经过系统调用后,用户空间地址
    //传递到内核空间,用户空间虚拟地址 对内核来说无法直接使用,需要转化
  2. 疑惑地方:我看懂这个数据结构页表项 (PTE, Page Table Entry) 是一个整数)

    里面包含了一个物理页号 + 标志位

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /// 一个物理页号 PhysPageNum 和一个页表项标志位 PTEFlags 生成一个页表项 
    pub fn new(ppn: PhysPageNum, flags: PTEFlags) -> Self {
    PageTableEntry {
    bits: ppn.0 << 10 | flags.bits as usize,
    // 最低的 8 位 [7:0] 则是标志位。
    //其中 [53:10] 这 44 位是物理页号
    // SV39 分页模式下的页表项,其中 这 位是物理页号,最低的 位 则是标志位
    }
    }

虚拟页号 同样也是整数,虚拟页号 和 物理页号对应起来?

经过群里讨论 和看资料,初步理解 虚拟页号当作索引,页表项是数组内容建立关系,这句话初步帮助理解。不代表真实现。

另外一个结构:PageTable

a 通过虚拟页号找到页表项(里面又物理页号)

1
2
3
4
5
6
/// Find PageTableEntry by VirtPageNum
/// 通过虚拟页号找到页表项(里面又物理页号)
fn find_pte(&self, vpn: VirtPageNum) -> Option<&mut PageTableEntry>
let idxs = vpn.indexes();
https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter4/4sv39-implementation-2.html
VirtPageNum 的 indexes 可以取出虚拟页号的三级页索引,并按照从高到低的顺序返回

b 函数:translated_byte_buffer 为参考例子实现了

实现来了 从虚拟地址转化成物理地址

3 map 和 unmap 虚拟地址是一个连续内存,其中一个虚拟地址转化成物理地址,

多个虚拟地址转转化思路很清楚了,具体实现:MemorySet 新增map_range函数

这里对map封装

1
2
3
4
5
pub fn map(&mut self, page_table: &mut PageTable) {
for vpn in self.vpn_range {
self.map_one(page_table, vpn);
}
}

小结

最后通过下面函数封装完成ch4。

  • PageTable find_pte

  • MemorySet map_one unmap_one

    不然无法实现,里面细节不少。

chapter5 练习

实现分支:ch5-lab

实验目录要求不变

通过所有测例

思路

  1. 为什么重新实现 sys_task_info sys_mmap函数?

    • 引入处理器管理结构 Processor 负责从任务管理器 TaskManager 中分出去的维护 CPU 状态的职责

    • 这里注意 语法细节

      1
      2
      3
      4
      5
      6
      7
      8
      ///Get current task in moving semanteme
      pub fn take_current(&mut self) -> Option<Arc<TaskControlBlock>> {
      self.current.take()
      }
      ///Get current task in cloning semanteme
      pub fn current(&self) -> Option<Arc<TaskControlBlock>> {
      self.current.as_ref().map(Arc::clone)
      }
  2. sys_spawn

1
2
3
//功能:新建子进程,使其执行目标程序。
// "ch5b_user_shell\0"
pub fn sys_spawn(_path: *const u8) -> isize
  • 细节:参考 初始进程initproc的创建 【里面有很多知识点】

    1
    2
    TaskControlBlock::new(get_app_data_by_name("initproc").unwrap())
    https://rcore-os.cn/rCore-Tutorial-Book-v3/chapter5/3implement-process-mechanism.html
  • 细节:参考 fn sys_exec(path: *const u8) 对_path处理 需要地址转化。

  • 细节:父子进程关系设定。 parent: Option<Weak>

    weak指针类型

  1. 进程优先级

    每次需要调度时,从当前 runnable 态的进程中选择 stride 最小的进程调度

    改写fetch函数,修改当前任务的stride 使用take 还是as_ref。

小总:进程

  • 这一章节完全是Rust语法细节 引用,借用 ,weak智能指针(避免循环引用)

  • 例如 “ch5b_user_shell\0” 后面执行过程不很清楚,我更加深入学习load实现。

未完待续

感谢老师和主教们提供的精彩课程,让我作为一个已经工作的工程师,在业余时间也能够深刻学习操作系统这门课程。课程内容丰富,技术前沿,把RUSTRISCVOS结合在一起,并且提供了完整的实验。经过学习我对操作系统有了很清楚的认识,虽然目前才做完lab3,但是后续会接着把两个实验也给完成。

Read more »

实验总结

lab1

目的就是实现三个信息的统计

status: TaskStatus

  • 按照提示直接设置为running

[syscall_times: [u32; MAX_SYSCALL_NUM]

  • 第一次尝试直接在sys_task_info来加载,发现好像不行,因为不知道传入的ti: *mut TaskInfo,这个参数到底在哪里被初始化的,而且每个任务都需要有一个syscall_times数组
  • 由此我在TaskControBlock中维护一个pub task_syscall_times: [u32; MAX_SYSCALL_NUM]数组,这样通过全局遍历TASK_MANAGER可以很好的在每次系统调用时更新
  • 更新位置在trap_handler进入syscall之前,读取x17寄存器为syscall id

time: usize

  • 需要得到的是从第一次运行到现在的时间,现在的时间可以通过get_time_ms直接获得

  • 第一次运行开始的时间,需要在应用第一次变成Running态的时候记载,因此我们为每个

    1
    TaskControBlock

    中维护

    • pub task_start: usize, 记录任务第一次开始的时间
    • pub task_flag: bool, 标志是否为第一次,如果是就是false,然后我们更新task_start,并且将该变量置为false,保证只记录一次start time

lab2

直接<<12直接这样会报错overflow,但是那个函数确实就是干了这个事情,只是我帮他弄了一把,很奇怪,还是最后用函数了

taskInfo报错,按照群里大佬这样修改,但不知道为什么这样修改

1
2
3
4
5
6
7
8
//原
pub fn get_time_us() -> usize {
time::read() / (CLOCK_FREQ / MICRO_PER_SEC)
}
//修改为
pub fn get_time_us() -> usize {
time::read() * MICRO_PER_SEC / CLOCK_FREQ
}

疑问

  1. vpn_end计算有问题,len需要/8吗:不需要,因为VA就是取最低39位,不会左移右移啥的
  2. 上取整,如果已经对齐的情况下还会上取整吗:回答,不会的

bug与问题

  1. 对于判断是否mapped过,只考虑了find_pte不能为None,没有考虑find_pte存在,但是pte.is_valid()不合法这件事,卡了很久,也不好调试
  2. MapPermission不好进行零初始化,那么就用match,但是match要解决穷尽匹配,我们先把不合法的删去,然后最后一个_只代表6的情况
  3. 对题意理解有问题,在mmap中,我以为如果start和end之间有已经被映射的页,我们还是需要分配len这么长,也就是不error,映射一段不连续的虚拟内存,写了比较复杂,后面才知道直接error
  4. 这章很难debug,看样子甚至是多线程跑测试,所以花费很多时间

lab3

继承上一章修改

今天上下午一直在移植代码,尝试了git cherry-pick试了很久,重置过去重置过来,问了gpt,看了b站,csdn都无果,就是没有合并,只显示reports文件夹有冲突,主要的os没有,遂还是采用git diff打patch的笨方法,冲突太多了,合并了小一个小时。

修理waitpid

移植好之后,make run确实能跑了,但是随便输一个就报错,说waitpid清除僵尸进程的引用计数有错,本来应该是1,结果是2,多了一个,debug找不出来,println也没看出来在哪里。仔细想想,找了跟Arc有关的所有代码,可以肯定一件事,模板代码一定没问题,那问题就出在我自己移植过来的代码,最后一个个注释排除法,找到了原来是我自己用了一个Arc没有drop,我以为drop了inner的RefMut就可以了,没想到这个也要drop。为啥这个不会自动drop呢?

目前还有usertest卡住的问题,再看看。

spawn

通过注释发现卡住的原因是spawn的实现有问题,重点在维护父子关系,注意drop的位置

  • spawn就是新建一个进程而已,不要想着用fork+exec,之前直接调用fork()和exec()会出问题,也不好调试,于是自己仿照fork内容与exec自己实现

stride

stride感觉倒是很简单,根据提示BIG_STRIDE需要大一点,于是把BIG_STRIDE设置为了0x100000,然后每次调度的时候,都要fetch_task,于是在这里找出最小的stride返回,pass的维护在set_piro里面实现,因为prio只会在这里修改

lab4

这章我真的心累了,调试了两天,目前还是有一个神奇的bug,我觉得不是我代码的问题

ch6_file2里面:我做了如下修改,//后的就是新加入的

1
2
3
4
5
6
7
8
9
10
11
12
13
   let test_str = "Hello, world!";
let fname = "fname2\0";
let (lname0, lname1, lname2) = ("linkname0\0", "linkname1\0", "linkname2\0");
let fd = open(fname, OpenFlags::CREATE | OpenFlags::WRONLY) as usize;
//
let fd1 = open(lname0, OpenFlags::CREATE | OpenFlags::WRONLY) as usize;
//
println!("ok1");
//此处传入的lname0是0x0,为什么
link(fname, lname0);
//
println!("ok2");
...

发现在 link(fname, lname0); //此处传入的lname0是0x0,为什么,看运行结果(在open系统调用和link加入了println!打印传入str的地址),部分结果如下

1
2
3
4
5
6
7
open:path  is 0x42cd
open:path is 0x42d4
ok1
link:old name addr is 0x42cd
link:new name addr is0x0
old_name is6 ,new_name is45
[kernel] Panicked at /root/2023a-rcore-Ywinh/easy-fs/src/layout.rs:419 range end index 45 out of range for slice of length 28

可以看到lname对应的new name在open里面的地址是0x42d4,但是在link里面是0x0,就是这个bug让我以为我的link出错了,改了一整天,后面copy别人的代码也不行,真的心累了。。请教了群里的一位大佬,还没回我,希望能解决…

自己对于rust的理解还是不够,还是要在实践中多用,但很感谢能通过这个机会锻炼自己~~

1 整体总结

在完成Rustlings后,终于能亲自上手把玩操作系统了。rCore的每一个branch实际上可以看做是对一个初具框架项目的不断更新和迭代。ch1是在裸机上部署一个hello world, ch2是引入了特权级, ch3实现分时多任务系统, ch4引入了虚拟内存和页表, ch5引入了进程的概念并提供了相关系统调用和调度算法支持, ch6添加了简易文件系统, ch7添加了管道这一古老的ipc方法, ch8引入了线程的概念并加入了与线程同步相关的资源:锁, 信号量和条件变量。

这样的渐进式布置, 有助于理解操作系统设计的思路,对于我个人而言, 前2章将用户程序链接到内核反而是最困难的,也是平时学习中不容易注意到的知识点。

lab的难度整体上不算太高, 但需要注意细节, 另外兼容前一个章节的代码确实会带来一些压力, 比如lab5时, 我卡住了很久, 最后才发现需要重新实现sys_get_time, 希望老师们能在以后的课程中考虑到这个问题

2 lab 通关记录

2.1 ch0-环境配置

按照指导书进行环境配置对于基础的代码运行是没有问题,但我发现自己按照指导书操作后无法进行gdb调试, 经过总结后在此处给出我的2种解决方案:

方案1: 安装完整的 riscv-gnu-toolchain

安装完整的riscv-gnu-toolchain流程如下, 次方法费时较长, 且占据空间较大, 更推荐第二种方法。

  1. 安装依赖
    1
    $ sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev libexpat-dev
  2. 克隆riscv-gnu-toolchain
    1
    $ git clone --recursive https://github.com/riscv/riscv-gnu-toolchain
  3. 编译安装
    1
    2
    3
    $ cd riscv-gnu-toolchain
    $ ./configure --prefix=/usr/local
    $ sudo make

    方案2: 编译安装 riscv64-unknown-elf-gdb

  4. 安装依赖
    1
    $ sudo apt-get install libncurses5-dev python2 python2-dev texinfo libreadline-dev
  5. 下载gdb源码
    此处我选择gdb-13.1, 该版本在wsl2 Ubuntu22.04上使用正常。
    1
    2
    3
    4
    # 推荐清华源下载
    wget https://mirrors.tuna.tsinghua.edu.cn/gnu/gdb/gdb-13.1.tar.xz
    # 解压
    tar -xvf gdb-13.1.tar.x
  6. 编译安装
    只需要指定编译安装riscv64-unknown-elf并配置相关参数。
    1
    2
    3
    4
    5
    $ cd gdb-13.1
    $ mkdir build && cd build
    $ ../configure --prefix=/your_path --target=riscv64-unknown-elf --enable-tui=yes
    $ make -j$(nproc)
    $ sudo make install

2.2 ch3-lab1

本次作业需要实现sys_task_info这一系统调用以统计task信息。

总体思路

  1. task.rs中的TaskControlBlock结构体增加了sys_call_times数组, 用于记录当前task中各个系统调用的次数, 以及sys_call_begin,记录任务创建的起始时间
    1
    2
    3
    4
    5
    6
    7
    8
    pub struct TaskControlBlockInner {
    ...
    /// syscall time count
    pub sys_call_times: [u32; MAX_SYSCALL_NUM],
    /// begen time
    pub sys_call_begin: usize,
    ...
    }
  2. 每次执行系统调用时, 将全局变量TASK_MANAGER中当前任务current_task对应的TaskControlBlock结构体的系统调用记录自增
  3. 如果调度任务时发现sys_call_begin = 0, 说明这个task是第一次被调用, 需要将sys_call_begin设置为当前时间
  4. TaskManager实现get_sys_call_times方法, 获取当前任务current_task对应的TaskControlBlock结构体的系统调用数组的拷贝
  5. 完成process.rssys_task_info, 调用get_sys_call_timesget_time_ms获取TaskInfo结构体的syscall_timestime部分, status部分设为Running

2.3 ch4-lab2

2.3.1 重新实现 sys_get_timesys_task_info

相比于之前的实现, 唯一的变化就是系统调用函数中传递的指针不能直接使用, 因为内核页表与用户页表是不同的。

思路

通过软件的实现来转换地址

> 参考`translated_byte_buffer`实现`translated_struct_ptr`
`translated_byte_buffer`将一个指向`u8`数组的指针按照指定的页表获取其物理地址, 我们不需要获取数组的长度, 只需要通过指定的泛型告知`PhysAddr`的`get_mut`方法需要转化的类型即可。

2.3.2 mmapmunmap 匿名映射

本项目中, 这两个系统调用仅用于申请内存。在实际上, mmap 系统调用是用来将一个文件或者其他对象映射进调用进程的地址空间的。它通常映射到进程的用户空间,使得进程能够像访问普通内存一样访问文件的内容, 减少IO次数。

mmap 实现思路:

  1. 选择一个地址空间进行映射, 由前文介绍可知, 需要映射到当前task的内存地址空间
    可以用TaskManagerInnercurrent_task找到当前的task序号, 再在tasks中找到对应的memory_set
  2. 在找到的memory_set上申请内存
    需要注意的是, 分配内存页需要调用frame_alloc, 为了内存页的自动回收, 还需要将其加入一个集合类型中, 这里我为MemorySet新增了成员map_tree: BTreeMap<VirtPageNum, FrameTracker>用以接受mmap新分配的FrameTracker:
    1
    2
    3
    4
    5
    pub struct MemorySet {
    page_table: PageTable,
    areas: Vec<MapArea>,
    map_tree: BTreeMap<VirtPageNum, FrameTracker>,
    }

munmap 实现思路

思路和mmap类似

  1. 调用page_tableunmap方法删除映射
  2. 调用map_treeremove方法移除FrameTracker使其能被FRAME_ALLOCATOR回收

易错点

  1. 需要通过PageTableEntryis_valid方法判断转换后页表项的有效性
  2. mmap使要判断地址是否对齐
  3. 判断权限

2.4 ch5-lab3

2.4.1 实现sys_spawn系统调用

sys_spawn系统调用从效果上就是fork+exec, 区别在于既然马上要exec, 就没有必要负责父进程的地址空间了, 毕竟马上就要被覆盖掉, 因此, 思路如下:

  1. exec一样, 将地址通过task处获取的页表进行转化得到有效的字符串
  2. 调用get_app_data_by_name直接获取文件的u8数组表示的elf数据
  3. 将得到的elf数据传入TaskControlBlock::new获取一个新的任务控制块
  4. 设置新的任务控制块和当前任务控制块的父子关系
  5. 将心的task加入任务列表

    2.4.2 实现stride 调度算法

    stride本质上就是综合了任务优先级程序后的任务运行时间的反映, 每次选择stride值最低的任务运行,一定程度上实现了公平的调度。

    实现思路

  6. config.rs中添加常量BigStride
  7. TaskControlBlockInner中新增如下成员:
    1
    2
    3
    4
    5
    6
    7
    8
    pub struct TaskControlBlockInner {
    ...
    /// 当前 stride
    pub cur_stride: usize,
    /// 优先级等级
    pub pro_lev: usize,
    ...
    }
  8. 每次切换任务时, 选择stride值最低的任务运行
    阅读代码可知, run_tasks方法每次都是调用TaskManager::fetch方法来获取下一个运行任务, 因此只需要修改fetch方法来实现我们的调度算法。
    由于TaskManager使用ready_queue: VecDeque<Arc<TaskControlBlock>>来存放TaskControlBlock, 每次调用fetch时,对ready_queue按照stride进行排序, 然后pop_front即可
  9. 更新锁选择任务的其stride
    使其cur_stride变量自增BIG_STRIDE / var.pro_lev即可

2.5 ch6-lab4

2.5.1 硬链接简介

实现硬链接的系统调用: linkatunlinkat
硬链接: 本质上就是不同的目录项指向了同一个innode, 因此实现linkatunlinkat的流程如下:

  • linkat
  1. 查找要指定的目录项, 失败返回, 找到则返回其指向的innode
  2. 在目录下新创建一个目录项, 指向这个innode
  3. 将指向的innode的引用计数自增1
  • unlinkat
  1. 查找要指定的目录项, 失败返回, 找到则返回其指向的innode
  2. 在目录下删除找到的目录项
  3. 将指向的innode的引用计数自减1
  4. 如果指向的innode的引用计数变成0, 将其以及指向的数据块释放

2.5.2 实现思路

可以看到, 尽管思路清晰, 但实际的视线还是较为繁琐, 主要体现在各个数据块的查找, 判断其有效性等, 以下是具体的视线思路

  • linkat
  1. 修改DiskInode结构体, 添加引用计数成员refcont
    1
    2
    3
    4
    5
    6
    pub struct DiskInode {
    ...
    pub direct: [u32; INODE_DIRECT_COUNT],
    pub refcont: u32, // 新增这个变量后需要将 INODE_DIRECT_COUNT - 1
    ...
    }
    需要注意的是, DiskInode需要匹配其在block中的大小, 因此我们添加了一个变量refcont, 需要将将 INODE_DIRECT_COUNT - 1以保证其在block中的大小不变
  2. 通过translated_str获取实际的_old_name_new_name
  3. ROOT_INODE中调用read_disk_inode查询old_name的inode序号inode_id
  4. 调用在ROOT_INODE中调用modify_disk_inode写入新的目录项
    需要注意计算新的size并调用increase_size分盘空间
  5. 通过inode_id调用get_disk_inode_pos得到具体的inode位置, 将其引用计数自增
  6. 调用block_cache_sync_all同步更新
  • unlinkat
  1. 通过translated_str获取实际的_name
  2. ROOT_INODE中调用read_disk_inode查询_name的inode序号inode_id, 注意需要判断其是否存在
  3. 调用在ROOT_INODE中调用modify_disk_inode删除找到的目录项
    注意此处的删除, 我的实现思路是
    • 找到改目录项在根目录中的序号
    • 如果这个序号是最后一位, 只需要将size自减
    • 否则需要将最后一个目录项移动到这个位置进行覆盖, 然后再将size自减
  4. 通过inode_id调用get_disk_inode_pos得到具体的inode位置, 将其引用计数自减
  5. 如果硬链接对应的innode引用计数达到了0, 需要释放其空间
    调用clear_size获取其的每一个数据block, 并调用EasyFileSystem::dealloc_data进行清理

2.6 ch8-lab5

2.6.1 死锁检测算法进一步介绍

此处对任务书中的算法进行进一步补充

  • Available[m]: 其下标对应的资源是最具体的资源, 比如具体是哪一把锁, 哪一个信号量
    可知, 进程是最基础的资源管理单位, 因此这一统计资源应该放在ProcessControlBlockInner
  • Allocation[n][m]: 每个具体资源已分配给每个线程的资源数, 具体而言就是lock了但还没unlock时需要记录资源的使用数量
    这个资源仍然可通过ProcessControlBlockInner来管理, 但是这样的话每个线程创建和操作相应资源时, 还需要在访问一次进程控制块, 因此可以将其托管给线程控制块TaskControlBlockInner
  • Need[n][m]: 表示每个线程还需要的各类资源数量, 具体而言, 在lock前需要先登记需求, 将对应的资源自增, 在lock后则需要撤销这次登记
    Allocation[n][m]类似, 托管给线程控制块TaskControlBlockInner管理是更容易的实现

    2.6.2 实现思路

  1. 修改ProcessControlBlockInner结构体, 添加Available[m]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    pub struct ProcessControlBlockInner {
    ...
    /// mutex的Available[m]
    pub m_available: Vec<usize>,
    /// 信号量的Available[m]
    pub s_available: Vec<usize>,
    /// 是否使用死锁检测
    pub use_dead_lock: bool,
    }
    注意这里我使用2个Available[m]变量s_availablem_available, 分别控制信号量和锁
  2. 修改TaskControlBlockInner结构体, 添加Allocation[m]Need[m]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    pub struct TaskControlBlockInner {
    /// mutex的Allocation[m]
    pub m_allocation: Vec<usize>,
    /// 信号量的Allocation[m]
    pub s_allocation: Vec<usize>,
    /// mutex的Need[m]
    pub m_need: Vec<usize>,
    /// 信号量的Need[m]
    pub s_need: Vec<usize>,
    }
    由于是将其托管到TaskControlBlockInner管理, 因此Allocation[m]Need[m]退化为了一维数组, 同时将信号量和锁分开管理
  3. 修改创建sys_mutex_createsys_semaphore_create
    拿到对应资源的序号id后, 需要更新m_availables_available, 注意的是m_available只需要自增1, 而s_available需要自增信号量分配的具体值
  4. 修改sys_mutex_locksys_semaphore_down
    • 这2个方法是申请对资源的使用, 因此在使用前需要进行登记: 将s_needm_need进行自增
    • 按照任务书中的算法进行死锁检测, 此处不详细说明代码实现
    • 死锁检测通过后, 将s_needm_need进行自减以撤销登记, 同时将m_availables_available自减以标识资源被占用, 将m_allocations_allocation自增以标识自身对资源的占用
  5. 修改sys_mutex_unlocksys_semaphore_up
    • 这2个方法是归还资源, 相对简单, 只需要s_availablem_available自增以归还资源, 将m_allocations_allocation自减以标识自身对资源的释放

2.6.3 易错点

  1. 每次对m_available统计资源进行访问时, 要同步更新所有TaskControlBlockInner中的m_allocationm_need的数组长度以防止后续数组访问越界, 访问s_available时同理
  2. 通过inner_exclusive_access方法获取process_innertask_inner时, 要注意此前是否已经获取过相应资源, 尤其是在多层函数调用时, 需要手动drop掉以上变量
  3. 测试依赖sys_get_time,一定要实现sys_get_time!!!

学习报告

经历了一个月的学习,2023开源操作系统训练营的一二阶段算是接近尾声。对于进度,十分惭愧只完全完成了一阶段100道rustlings习题,以及二阶段的前五章,对应前三个实验。这已经是我第三次接触这一开源项目。第一次接触此项目是在2022年秋,当时我正好学习操作系统及其研讨课的课内内容。当时并没有报名该项目,而是作为课内的补充学习。不过由于该学期的事情太多,所以并没有深入探究。第二次接触该项目就是2023年夏,这个夏天我正好参加另一个开源项目,该项目使用rust编程语言进行编写,并且我报名参加了我们学校操作系统助教,为了加深对于操作系统概念的理解,并且学习rust,当时只是简单看了该项目,并没有深入理解。十分幸运的是,今年秋,此项目再次启动,因此我决定将此项目完成。并且本人对于虚拟化比较感兴趣,十分想参加后续的项目实习。

Read more »

2023rCore 训练营第二阶段总结

参加本次rcore训练营的原因是希望找人和我一起写课程来督促我成长,因为本人做事很容易烂尾。

之前做过类似的操作系统lab,并且也用过rust,所以前三个实验还是比较顺利完成了,这次报名也是希望能进一步参与后面的项目。

下面简单总结一下在第二阶段我完成的各个实验情况。

ch3

rcore 的前几个实验难度不是很大,读懂代码结构,按照需求去实现就行了。

本次实验在要实现一个当前任务信息查询调用。

而这个系统调用sys_task_info调用的实现建立在对TaskManager的修改的基础上。

我们只需要在TaskManagerInner中的TaskControlBlock里添加syscall_times来统计该任务的各个系统调用次数的统计,并在系统调用时,以及任务切换时进行相应数据的修改就行了。

ch4

本次实验是在有了分页机制的前提下,重写了ch3中的sys_write和sys_task_info。

由于我们引入了虚拟存储机制,所以要把数据写到任务地址空间需要根据我们的页表得到其实际物理地址再写入。mmp与munmap都已在memroy_set中帮我们实现,我们只需要简单封装一下即可,同时我们要注意访问权限的管理。

ch5

本次实验任务简单,spawn一个新任务就是创建一个空白子进程然后加载对应程序即可,

总结

通过这个阶段的学习,我巩固和掌握了很多操作系统的知识,并且在实践中得到了很大的收益。

实验的逐步进行让我能够在已经写好的代码基础上增加对系统的理解并进行修改,从而使我的思维得到不断蜕变。此外,采用增加功能的实验方式让我感觉像在编写自己的操作系统,因此更加认真地学习,从中获取更多知识,并得到积极的反馈。

此外,第二阶段的实践使我的 Rust 编程技能得到了进一步提升。

前二阶段学习感受

Rust

Rust吸引我的地方在:于相较于C语言,Rust提供了高级别的抽象和语法糖并且不会带来额外的性能开销;相较于C++虽然上手难度较高,但是C++更难熟练掌握和精通。此外Rust的官方教程非常不错,使用Cargo方便地发布和管理包使得Rust相比C++更加“现代化”。Rust的学习曲线比较陡峭,以至于需要把整本《Rust 程序设计语言》看完后才能正确地写出规模比较大的程序。所有权机制像是默认实现的C++的移动语义,这一点和我之前接触过的大部分语言都不一样。引用和生命周期有时相当折磨,比如最开始写程序的时候容易犯的一个错误是在函数内部创建一个变量然后返回它的引用,不过这种方式本来也十分危险,因为,假如使用C++,如果不设计好析构函数就非常容易引发内存泄漏,而在Rust中这中问题在编译器就解决了。虽然Rust一开始写比较痛苦,但编译器更像是以为老师去纠正错误。

Rcore

作为一个使用Rust写的OS内核,通过阅读Rcore代码能很好的锻炼我的rust功底,rcore-tutorial-book给出了非常详细的讲解,不得不令人称赞。

这是我第二次做lab,但是第一次正式参加训练营。从现在来看Rcore的编程题其实整体的难度不大,每个lab需要修改的代码整体不超过400行,不过想要快速地完成lab还是需要对代码比较熟悉,结合自己的经历,我认为0基础能一个月之内完成5个lab算是比较快了。因为前置的一些技能也需要花一些时间,我一开始学习时rcore在正式开始看代码之前还花了一周左右的时间学习Makefile、GUN Linker、Risc v规范,如果有相关的基础会快很多。

对于前3个lab,本次训练营花费了10天完成。其中个人认为难度比较大一点的时munmap系统调用的实现。这里我在第一次做lab的时候想用区间树实现快捷的区间查询操作,我参考了《算法导论》手写了红黑树并期望在此基础上实现最终的区间树,但是除了一些bug就被鸽了。不过这次我使用了crates.io上的一个包iset,很方便地实现了区间查找,同时从iset的源码中一窥优秀的rust代码是怎么写的。

截至11.3,成功上传了前3个lab的代码并获得了300分,剩下的两个lab还需继续完成。

前言

在朋友推荐下报名了这个训练营,现在过了差不多一个月感觉收获颇丰。虽然我本科专业是电子信息的,但我一直对计算机方面还有操作系统的知识很感兴趣,所以就开始了这段学习之旅。以下就是我这两个阶段以来的一些总结及感悟。

第一阶段

一开始先是rust的语法学习,以前并没有接触过rust,很多github和linux上的操作也不太懂,导致浪费了很多时间。 之后听完直播课老师的讲解,听完后再就开始看Rust语言圣经和相关资料开始学习rust的语法。在一开始,就是先看一段然后在rustlings上做相关类型的题,到了中间题变难了一些,有几道题看半天代码和圣经也找不到头绪,只能hint。在之后就发现我的策略上一个大的问题,因为我看书是按书本身的顺序看的,所以当时做到rustlings里面的那些不按顺序的题我都看了半天,比如error那些专题的题目我在上面翻了半天也找不到相关内容,然后又是通过hint和rust官方的库来了解相关做法,所以又浪费了很多时间。分析之后为找到了正确的决策:按照rustlings的专题来看知识点,做完一个专题后就先去了解下一个专题的知识点,看到自己大概有信心能写的时候再开始做题,一步一个脚印稳扎稳打的前进。最后也是用这样的方法成功地做完了所有的题目。

第二阶段

零基础的话做这个阶段的实验是真的折磨,刚开始配环境就折腾了很久但也还好,之后开始看书,很多的知识点都是没接触过的,从批处理的操作和特权级的切换到分时多任务系统的构建,然后动态内存与页表的定义,最后再到进程的管理。最开始的路最为难走,第3章是最开始的实验,同样也包含了前三章的知识,我花了很长时间才弄清除整体代码的运行流程,实现的功能确实也不难,前提是搞懂整体框架。然后第四章最基本的要求虚实地址转换我就理解了很久很久,因为对语法的不够熟悉,我对数组及内部地址的操作都写了很久都没有成功。第四章最后花了5,6天才解决,反而是第5章一下就做好了。

总结

通过这次训练营,我学到了很多的操作系统的知识,也培养了各种能力。虽然实验现在我只做好了前面三个,但我感觉已经有了对整体的基本认知,我会在之后的时间把实验补完并认真完成实习的内容。

Stage 1 (Rustling)

I tried to learn Rust programming language many times, but it was from start to give up every time. Mostly because I never used it in my real job or other personal works. The recent one was trying to implement a vulkan game engine with Rust, but I do have other stuff to do, so that was never finished.

I spent about 3 nights to finish the rustling problem set, it was fun. For the first half, it was a refresh to my already rusty Rust memory. I did learn something different during the second part. It was indeed engaging. The compiler message is a very powerful tool in general, Many times I just need to follow what the compiler said to answer the question. I did have to Google a lot and consult The Book and the official Rust lang document.

With these practices, I started to get used to Rust, I wouldn’t say I am fully equipped comparing with my C++ and Java skill, but I think it is a good start.

Stage 2 (Lab)

Lab 1

After setting up the environment, I realized that I had read the tutorial book before, but just brief. It was probably because I followed an OS course from Nanjing University taught by Yanyan Jiang on Bilibili. I even have a qemu installed in my WSL2. In general, the guide book is very readable. I followed the book to understand the code structure and WeChat group helped some of the common questions on newer version of qemu, which saved my a lot of time.

However, 2 weeks are super short, I can’t finish reading the first two chapters to understand all the details and I have to start chapter 3 right away to meet the deadline. Fortunately the actual lab isn’t very hard. The first lab is just to implement sys_task_info, there is a big hint that the TaskControlBlock has a TaskStatus field, we also have that in TaskInfo struct, I immediately realized that we just need replace that field with the TaskInfo struct type. The rest of the work is fairly straightfoward.

Lab 2

This lab is indeed harder than the previous one, again I didn’t have time to read the book in a great detail, so I had to make a guess sometimes. But fortunately the code itself is very readable as well, I can find all the info I need in the code. The first hint I get is the translated_byte_buffer() function, which reminds me memcpy in C/C++, if I can write a function to convert everything to a byte array, I then can use translated_byte_buffer() with that to easily copy data from kernel space to user space. That’s exactly what I did in my code to solve this.

The second part is mmap and munmap, there are many restrictions on the params, which simplied the whole story. I am happy to see this so I can pass the test cases, but wondering how a real world OS implements them.

Lab 3

I spent more time than before to read chapter 5, which didn’ help me a ton in the lab, but I still think that is worth because it provides me some details about how this particular OS is designed.

I was planning to rewrite all of lab 2 and lab 1 requirements again, but I don’t have that time, so I spent about 1 hour to do cherry-pick from ch4. The spawn part was easy if we understood how fork and exec work.

The stride part is also not too hard since the problem statement is clear about what I need to do. I did have some bugs (and I probably still have some bugs even I passed the test cases), it was not too hard to debug them. I ended with using a binary heap to implement the algorithm.

Summary

That’s all I did so far, I wish I can finish the rest two labs soon, 2 weeks are super tight, not sure why this was arranged in this way, the curves in stage 1 and stage 2 are completely different. But maybe that was on purpose, so everyboday has to find their way out, I did have fun and finally had time to get my hands on code.

Big thanks to all the hosts and staff!