实验题报告

Lab 1

实验题

简述：在 rust_main 函数中，执行 ebreak 命令后至函数结束前，sp 寄存器的值是怎样变化的？

答：

ebreak 执行后，首先更新 sepc 和 scause ，然后进入到 __interrupt 函数内。

在 __interrupt 函数内，首先先开辟一个 $34\times 8$ 的栈空间，即 sp 的值减去 $34\times 8$ 大小，存放着此时的上下文。

之后，进入 handle_interrupt 函数部分，从这里开始，遵循正常的函数调用和栈使用规则，一直到返回 __restore 函数中。

在 __restore 函数内，函数读取完栈中存放的上下文并还原寄存器后，将栈中的 $34\times 8$ 的空间还原，即 sp 的值加上 $34\times 8$ 大小后，返回 rust_main 函数体内，并执行 ebreak 的下一条指令。
回答：如果去掉 rust_main 后的 panic 会发生什么，为什么？

答：

程序在从 entry.asm 进入 rust_main 的时候，其 ra 寄存器中存放着在 _start 函数中的 jal rust_main 指令的下一条指令的地址。

当去掉 rust_main 后的 panic 时，就会返回到其 ra 寄存器中存放的地址，而在 entry.asm 中可以发现， jal rust_main 后面已经是其他的段，而且段中的内容将会由链接器来决定，所以我们无法预测之后发生的事情。
实验
1. 实验：如果程序访问不存在的地址，会得到 Exception::LoadFault。模仿捕获 ebreak 和时钟中断的方法，捕获 LoadFault（之后 panic 即可）。
  
  思路：即在 interrupt::handler::handle_interrupt 中，增加一个新的分支即可
```
pub fn handle_interrupt(context: &mut Context, scause: Scause, stval: usize) {
    // 返回的 Context 必须位于放在内核栈顶
    match scause.cause() {
        ... ...,
        // read illegal address
        Trap::Exception(Exception::LoadFault) => loadfault(context, stval),
        // 其他情况，终止当前线程
        _ => fault(context, scause, stval),
    };
}
```
2. 实验：在处理异常的过程中，如果程序想要非法访问的地址是 0x0，则打印 SUCCESS!。
  
  思路：在运行时，如果出现 Exception::LoadFault 异常并被捕捉的话，则 stval 寄存器会存放着非法访问的地址。因此只需要改变一下 loadfault 函数体为如下即可：
```
/// 处理时钟中断
fn loadfault(_context: &mut Context, stval: usize) {
    if stval == 0x0 {
        println!("SUCCESS!");
    }
    panic!("An illegal address!");
}
```
3. 实验：添加或修改少量代码，使得运行时触发这个异常，并且打印出 SUCCESS!。
  
  思路：移除 rust_main 中的 panic! 语句，当从 rust_main 返回到汇编代码后，用汇编指令将 pc 的值跳转到 0x0 处。修改 entry.asm 代码如下：
```
... ...
# 目前 _start 的功能：将预留的栈空间写入 $sp，然后跳转至 rust_main
_start:
    la sp, boot_stack_top
    jal rust_main
    li t0, 0	# load an immediate 0
    jr t0		# jump to address 0x0
... ...
```
Lab 2
1. 回答：我们在动态内存分配中实现了一个堆，它允许我们在内核代码中使用动态分配的内存，例如 Vec Box 等。那么，如果我们在实现这个堆的过程中使用 Vec 而不是 [u8]，会出现什么结果？
  
  答：显然这是一个死循环。申请 Vec 的过程中调用分配器，分配器又申请 Vec。
2. 实验
  1. 回答：algorithm/src/allocator 下有一个 Allocator trait，我们之前用它实现了物理页面分配。这个算法的时间和空间复杂度是什么？
    
    答：
    
    观察 AllocatorImpl 代码中的 alloc 和 dealloc 函数体，可以发现其中的操作都是对于 Vec 的 push 和 pop 操作，这两个操作都是 $\mathrm{O}(1)$ 的时间复杂度。
    
    至于空间复杂度，由于每一个物理页，都有可能存在一个对应的 $[PPN, PPN+1)$ 区间，因此其空间复杂度为 $\mathrm{O}(n)$
  2. 实现基于线段树的物理页面分配算法
    
    思路：根据线段树，在已有的接口上进行改进。详情请看同目录下的 segment_tree.md 文件。测试结果如下：
```
PMP0: 0x0000000080000000-0x000000008001ffff (A)
PMP1: 0x0000000000000000-0xffffffffffffffff (A,R,W,X)
mod interrupt initialized
mod memory initialized
test build box
test drop box
heap test passed
PhysicalAddress(0x80a20000) and PhysicalAddress(0x80a21000)
PhysicalAddress(0x80a20000) and PhysicalAddress(0x80a21000)
src/main.rs:83: 'end of rust_main'
```
    在目录下 make run 得到结果与使用原始的分配器相同。
3. 挑战实验（选做）
  
  目前基于时间无打算，若有可能，以后实现。自己在曾实现过一个简易的动态内存分配器，在 lab2 的文档中有描述。
Lab 3
1. 原理：在 os/src/entry.asm 中，boot_page_table 的意义是什么？当执行 jal rust_main 时，不考虑缓存，硬件通过哪些地址找到了 rust_main 的第一条指令？
  
  答：
  
  由于我们通过链接器，将内核中的代码编译到了高地址处。但是在刚开始执行我们的代码的时候，PC 仍位于低地址处。boot_page_table 就允许系统在启用虚拟内存后，提供一个短暂的大页表映射，使我们无论在低地址处和高地址处都能正常访问到内核空间。
  
  当我们执行 jal rust_main 时，硬件先获取到 rust_main 的地址，此处应该为高地址。然后，通过 satp 寄存器，找寻到现有的页表 boot_page_table ，并定位到页表的 510 项。而由于第 510 项为一个大页，所以直接获得其物理页号，再加上页内偏移，找到 rust_main 的真正物理地址。
2. 分析：为什么 Mapping 中的 page_tables 和 mapped_pairs 都保存了一些 FrameTracker？二者有何不同？
  
  答：page_tables 中存储的是页表，而 mapped_pairs 中保存的是所有的分配的页面。
3. 分析：假设某进程需要虚拟地址 A 到物理地址 B 的映射，这需要操作系统来完成。那么操作系统在建立映射时有没有访问 B？如果有，它是怎么在还没有映射的情况下访问 B 的呢？
  
  答：操作系统建立映射的时候，只需要更改页表即可，不需要访问 B。
4. 实验：了解并实现时钟页面置换算法（或任何你感兴趣的算法），可以自行设计样例来比较性能
  
  答：由于框架准备用时较长，没时间做了，遗憾。
Lab 4
1. 实验：了解并实现 Stride Scheduling 调度算法，为不同线程设置不同优先级，使得其获得与优先级成正比的运行时间。
  
  答：代码位于 os/src/algorithm/src/scheduler/stride_scheduler.rs 。
  
  Stride Scheduling 算法简要概括如下：线程拥有一个 pass 属性和 stride 属性。每当线程被选用，则其 pass 属性就自增 stride 的值。每次选用 pass 值最小的线程。
  
  为了方便起见，优先度的取值范围为 $[0,31]$，优先度与运行时间成正比。
2. 分析：
  - 在 Stride Scheduling 算法下，如果一个线程进入了一段时间的等待（例如等待输入，此时它不会被运行），会发生什么？
    
    答：线程进入休眠状态后，当其他线程运行一段时间后，当切回该线程时，由于此线程的 pass 值相对于其他线程小很多，所以其将长时间抢占执行权。
  - 对于两个优先级分别为 9 和 1 的线程，连续 10 个时间片中，前者的运行次数一定更多吗？
    
    答：不一定。如果低优先级的线程在中途才加入，由于其积累的 pass 值较小，所以也会在一定时间内抢占大部分执行权。
  - 你认为 Stride Scheduling 算法有什么不合理之处？可以怎样改进？
    
    答：针对上面提到的由于 pass 值积累所导致的长时间抢占执行权的问题，可以在线程重新加入（或被唤醒）时，将其 pass 值设定为当前活动线程中最小的 pass 值，以重新公平竞争。

Lab 6

原理：使用条件变量之后，分别从线程和操作系统的角度而言读取字符的系统调用是阻塞的还是非阻塞的？

答：对于线程而言，读取字符是阻塞的过程，线程会等待字符被读取。而对于操作系统而言，等待读取的线程会被置出线程调度队列，转而执行其他的线程，所以是非阻塞的。
设计：如果要让用户线程能够使用 Vec 等，需要做哪些工作？如果要让用户线程能够使用大于其栈大小的动态分配空间，需要做哪些工作？

答：若要使用户现场可使用 Vec 等动态数据结构，需要在 rust 中实现本系统对应的 allocator 接口。若要使用动态分配空间，需要完善动态内存分配的系统调用接口，使程序能向系统请求分配内存页。

实验：实现 get_tid 系统调用，使得用户线程可以获取自身的线程 ID。

答：在我使用的 ubuntu 16.04 环境中，经查看 unistd.h 中可知 getpid 系统调用的 id 为 178，于是选择此作为系统调用号。

在 syscall.rs 下增加新的系统调用函数

pub(super) fn sys_get_tid() -> SyscallResult {
    let thread: Arc<Thread> = PROCESSOR.get().current_thread();
    SyscallResult::Proceed(thread.id)
}

同时修改 user crate 中的部分代码，得到实验结果如下：

mod memory initialized
mod interrupt initialized
mod driver initialized
.
..
hello_world
notebook
mod fs initialized
Hello world from user mode program!
Syscall: The thread id of hello-world is 1.
Thread 1 exit with code 0
src/process/processor.rs:101: 'all threads terminated, shutting down'

实验：将你在实验四（上）实现的 clone 改进成为 sys_clone 系统调用，使得该系统调用为父进程返回自身的线程 ID，而为子线程返回 0。

答：在我使用的 ubuntu 16.04 环境中，经查看 unistd.h 中可知 sys_clone 系统调用的 id 为 220，于是选择此作为系统调用号。

在 syscall.rs 下增加新的系统调用函数

pub(super) fn sys_clone(context: Context) -> SyscallResult {
    let current_thread: Arc<Thread> = PROCESSOR.get().current_thread();
    current_thread.clone_with_context(Some(context));
    SyscallResult::Proceed(current_thread.id)
}

同时在 thread.rs 的 clone_with_context 函数中增加一行代码：

    /// clone current thread
pub fn clone_with_context(&self, context: Option<Context>) -> Arc<Thread> {
    ... ...
    // modify the `pc` and `a0`
    let mut context_unwrap: Context = context.expect("fail to load context");
    context_unwrap.set_sp(context_unwrap.sp() - usize::from(self.stack.start) + usize::from(stack.start));
    // return 0 in the sub-thread
    context_unwrap.x[10] = 0;
    ... ...
}

运行测试结果如下：

在用户程序中，我们克隆自身，并打印线程 id ：

mod memory initialized
mod interrupt initialized
mod driver initialized
.
..
hello_world
notebook
mod fs initialized
Hello world from user mode program!
Clone id is 0
Syscall: The thread id of hello-world is 2.
Thread 2 exit with code 0
Clone id is 1
Syscall: The thread id of hello-world is 1.
Thread 1 exit with code 0
src/process/processor.rs:101: 'all threads terminated, shutting down'

可见该线程确实克隆了自身。

实验：将一个文件打包进用户镜像，并让一个用户进程读取它并打印其内容。需要实现 sys_open，将文件描述符加入进程的 descriptors 中，然后通过 sys_read 来读取。

答：选择 sys_open 系统调用的 id 为 1024。实现下面代码：

pub(super) fn sys_open(filename: &str) -> SyscallResult {
    // 从文件系统中找到程序
    let current_thread: Arc<Thread> = PROCESSOR.get().current_thread();
    let inode = ROOT_INODE.find(filename).unwrap();
    let descriptors: &mut Vec<Arc<dyn INode>> = &mut current_thread.inner().descriptors;
    let ret_id = descriptors.len();
    descriptors.push(inode);
    SyscallResult::Proceed(ret_id as isize)
}

在 disk.img 中添加一个 test 文件，其中只含有 123test 这个字符串，则测试结果：

mod memory initialized
mod interrupt initialized
mod driver initialized
.
..
test
hello_world
notebook
mod fs initialized
Hello world from user mode program!
test_fd is 2
[49, 50, 51, 116, 101, 115, 116, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Thread 1 exit with code 0
src/process/processor.rs:101: 'all threads terminated, shutting down'

可见我们成功读取了 test 文件，并读取了其中字符的 Ascii 码。

挑战实验：实现 sys_pipe，返回两个文件描述符，分别为一个管道的读和写端。用户线程调用完 sys_pipe 后调用 sys_fork，父线程写入管道，子线程可以读取。读取时尽量避免忙等待。

**答：**忙于其他事务中。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

实验题汇总.md

实验题汇总.md

实验题报告

Lab 1

实验题

Lab 2

Lab 3

Lab 4

Lab 6

Files

实验题汇总.md

Latest commit

History

实验题汇总.md

File metadata and controls

实验题报告

Lab 1

实验题

Lab 2

Lab 3

Lab 4

Lab 6