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种解决方案:
安装完整的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
上使用正常。 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
编译安装 只需要指定编译安装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
信息。
总体思路
在task.rs
中的TaskControlBlock
结构体增加了sys_call_times
数组, 用于记录当前task
中各个系统调用的次数, 以及sys_call_begin
,记录任务创建的起始时间1 2 3 4 5 6 7 8 pub struct TaskControlBlockInner { ... pub sys_call_times: [u32 ; MAX_SYSCALL_NUM], 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
中新增如下成员: 1 2 3 4 5 6 7 8 pub struct TaskControlBlockInner { ... 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
的流程如下:
查找要指定的目录项, 失败返回, 找到则返回其指向的innode
号
在目录下新创建一个目录项, 指向这个innode
号
将指向的innode
的引用计数自增1
查找要指定的目录项, 失败返回, 找到则返回其指向的innode
号
在目录下删除找到的目录项
将指向的innode
的引用计数自减1
如果指向的innode
的引用计数变成0, 将其以及指向的数据块释放
2.5.2 实现思路 可以看到, 尽管思路清晰, 但实际的视线还是较为繁琐, 主要体现在各个数据块的查找, 判断其有效性等, 以下是具体的视线思路
修改DiskInode
结构体, 添加引用计数成员refcont
1 2 3 4 5 6 pub struct DiskInode { ... pub direct: [u32 ; INODE_DIRECT_COUNT], pub refcont: u32 , ... }
需要注意的是, 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
同步更新
通过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]
1 2 3 4 5 6 7 8 9 pub struct ProcessControlBlockInner { ... pub m_available: Vec <usize >, pub s_available: Vec <usize >, pub use_dead_lock: bool , }
注意这里我使用2个Available[m]
变量s_available
和m_available
, 分别控制信号量和锁
修改TaskControlBlockInner
结构体, 添加Allocation[m]
和Need[m]
1 2 3 4 5 6 7 8 9 10 pub struct TaskControlBlockInner { pub m_allocation: Vec <usize >, pub s_allocation: Vec <usize >, pub m_need: Vec <usize >, 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
!!!