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	$ 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

克隆riscv-gnu-toolchain

1	$ git clone --recursive https://github.com/riscv/riscv-gnu-toolchain

编译安装

1
2
3

$ cd riscv-gnu-toolchain
$ ./configure --prefix=/usr/local
$ sudo make

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

安装依赖

1	$ sudo apt-get install libncurses5-dev python2 python2-dev texinfo libreadline-dev

下载gdb源码
此处我选择gdb-13.1, 该版本在wsl2 Ubuntu22.04上使用正常。

# 推荐清华源下载
wget https://mirrors.tuna.tsinghua.edu.cn/gnu/gdb/gdb-13.1.tar.xz
# 解压
tar -xvf gdb-13.1.tar.x

编译安装
只需要指定编译安装riscv64-unknown-elf并配置相关参数。

$ 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信息。

总体思路

在task.rs中的TaskControlBlock结构体增加了sys_call_times数组, 用于记录当前task中各个系统调用的次数, 以及sys_call_begin,记录任务创建的起始时间

pub struct TaskControlBlockInner {
    ...
    /// syscall time count
    pub sys_call_times: [u32; MAX_SYSCALL_NUM],
    /// begen time
    pub sys_call_begin: usize,
    ...
}

每次执行系统调用时, 将全局变量TASK_MANAGER中当前任务current_task对应的TaskControlBlock结构体的系统调用记录自增
如果调度任务时发现sys_call_begin = 0, 说明这个task是第一次被调用, 需要将sys_call_begin设置为当前时间
为TaskManager实现get_sys_call_times方法, 获取当前任务current_task对应的TaskControlBlock结构体的系统调用数组的拷贝
完成process.rs的sys_task_info, 调用get_sys_call_times和get_time_ms获取TaskInfo结构体的syscall_times和time部分, status部分设为Running

2.3 ch4-lab2

2.3.1 重新实现 `sys_get_time` 和 `sys_task_info`

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

思路

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

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

2.3.2 `mmap` 和 `munmap` 匿名映射

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

`mmap` 实现思路：

选择一个地址空间进行映射, 由前文介绍可知, 需要映射到当前task的内存地址空间
可以用TaskManagerInner的current_task找到当前的task序号, 再在tasks中找到对应的memory_set
在找到的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类似

调用page_table的unmap方法删除映射
调用map_tree的remove方法移除FrameTracker使其能被FRAME_ALLOCATOR回收

易错点

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

2.4 ch5-lab3

2.4.1 实现`sys_spawn`系统调用

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

和exec一样, 将地址通过task处获取的页表进行转化得到有效的字符串
调用get_app_data_by_name直接获取文件的u8数组表示的elf数据
将得到的elf数据传入TaskControlBlock::new获取一个新的任务控制块
设置新的任务控制块和当前任务控制块的父子关系
将心的task加入任务列表
2.4.2 实现stride 调度算法
stride本质上就是综合了任务优先级程序后的任务运行时间的反映, 每次选择stride值最低的任务运行,一定程度上实现了公平的调度。
实现思路
在config.rs中添加常量BigStride

在TaskControlBlockInner中新增如下成员:

pub struct TaskControlBlockInner {
    ...
    /// 当前 stride
    pub cur_stride: usize,
    /// 优先级等级
    pub pro_lev: usize,
    ...
}

每次切换任务时, 选择stride值最低的任务运行
阅读代码可知, run_tasks方法每次都是调用TaskManager::fetch方法来获取下一个运行任务, 因此只需要修改fetch方法来实现我们的调度算法。
由于TaskManager使用ready_queue: VecDeque<Arc<TaskControlBlock>>来存放TaskControlBlock, 每次调用fetch时，对ready_queue按照stride进行排序, 然后pop_front即可
更新锁选择任务的其stride
使其cur_stride变量自增BIG_STRIDE / var.pro_lev即可

2.5 ch6-lab4

2.5.1 硬链接简介

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

linkat

查找要指定的目录项, 失败返回, 找到则返回其指向的innode号
在目录下新创建一个目录项, 指向这个innode号
将指向的innode的引用计数自增1

unlinkat

查找要指定的目录项, 失败返回, 找到则返回其指向的innode号
在目录下删除找到的目录项
将指向的innode的引用计数自减1
如果指向的innode的引用计数变成0, 将其以及指向的数据块释放

2.5.2 实现思路

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

linkat

修改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中的大小不变
通过translated_str获取实际的_old_name和_new_name
在ROOT_INODE中调用read_disk_inode查询old_name的inode序号inode_id
调用在ROOT_INODE中调用modify_disk_inode写入新的目录项
需要注意计算新的size并调用increase_size分盘空间
通过inode_id调用get_disk_inode_pos得到具体的inode位置, 将其引用计数自增
调用block_cache_sync_all同步更新

unlinkat

通过translated_str获取实际的_name和
在ROOT_INODE中调用read_disk_inode查询_name的inode序号inode_id, 注意需要判断其是否存在
调用在ROOT_INODE中调用modify_disk_inode删除找到的目录项
注意此处的删除, 我的实现思路是
- 找到改目录项在根目录中的序号
- 如果这个序号是最后一位, 只需要将size自减
- 否则需要将最后一个目录项移动到这个位置进行覆盖, 然后再将size自减
通过inode_id调用get_disk_inode_pos得到具体的inode位置, 将其引用计数自减
如果硬链接对应的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 实现思路

修改ProcessControlBlockInner结构体, 添加Available[m]

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_available和m_available, 分别控制信号量和锁

修改TaskControlBlockInner结构体, 添加Allocation[m]和Need[m]

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]退化为了一维数组, 同时将信号量和锁分开管理

修改创建sys_mutex_create和sys_semaphore_create
拿到对应资源的序号id后, 需要更新m_available和s_available, 注意的是m_available只需要自增1, 而s_available需要自增信号量分配的具体值
修改sys_mutex_lock和sys_semaphore_down
- 这2个方法是申请对资源的使用, 因此在使用前需要进行登记: 将s_need或m_need进行自增
- 按照任务书中的算法进行死锁检测, 此处不详细说明代码实现
- 死锁检测通过后, 将s_need或m_need进行自减以撤销登记, 同时将m_available或s_available自减以标识资源被占用, 将m_allocation或s_allocation自增以标识自身对资源的占用
修改sys_mutex_unlock和sys_semaphore_up
- 这2个方法是归还资源, 相对简单, 只需要s_available或m_available自增以归还资源, 将m_allocation或s_allocation自减以标识自身对资源的释放

2.6.3 易错点

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

rcore-os Blog

2023开源操作系统训练营第二阶段总结报告-ToniXWD

1 整体总结

2 lab 通关记录

2.1 ch0-环境配置

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

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

2.2 ch3-lab1

总体思路

2.3 ch4-lab2

2.3.1 重新实现 `sys_get_time` 和 `sys_task_info`

思路

2.3.2 `mmap` 和 `munmap` 匿名映射

`mmap` 实现思路：

`munmap` 实现思路

易错点

2.4 ch5-lab3

2.4.1 实现`sys_spawn`系统调用

2.4.2 实现`stride` 调度算法

实现思路

2.5 ch6-lab4

2.5.1 硬链接简介

2.5.2 实现思路

2.6 ch8-lab5

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

2.6.2 实现思路

2.6.3 易错点

1 整体总结

2 lab 通关记录

2.1 ch0-环境配置

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

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

2.2 ch3-lab1

总体思路

2.3 ch4-lab2

2.3.1 重新实现 sys_get_time 和 sys_task_info

思路

2.3.2 mmap 和 munmap 匿名映射

mmap 实现思路：

munmap 实现思路

易错点

2.4 ch5-lab3

2.4.1 实现sys_spawn系统调用

2.4.2 实现stride 调度算法

实现思路

2.5 ch6-lab4

2.5.1 硬链接简介

2.5.2 实现思路

2.6 ch8-lab5

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

2.6.2 实现思路

2.6.3 易错点

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

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

2.3.1 重新实现 `sys_get_time` 和 `sys_task_info`

2.3.2 `mmap` 和 `munmap` 匿名映射

`mmap` 实现思路：

`munmap` 实现思路

2.4.1 实现`sys_spawn`系统调用

2.4.2 实现`stride` 调度算法