基础概念

系统调用

  • fork
1
2
3
4
/// 功能：当前进程 fork 出来一个子进程（除返回值外状态机相同）。
/// 返回值：对于子进程返回 0，对于当前进程则返回子进程的 PID 。
/// syscall ID：220
pub fn sys_fork() -> isize;
  • waitpid
1
2
3
4
5
6
7
/// 功能：当前进程等待一个子进程变为僵尸进程，回收其全部资源并收集其返回值。
/// 参数：pid 表示要等待的子进程的进程 ID，如果为 -1 的话表示等待任意一个子进程；
/// exit_code 表示保存子进程返回值的地址，如果这个地址为 0 的话表示不必保存。
/// 返回值：如果要等待的子进程不存在则返回 -1；否则如果要等待的子进程均未结束则返回 -2；
/// 否则返回结束的子进程的进程 ID。
/// syscall ID：260
pub fn sys_waitpid(pid: isize, exit_code: *mut i32) -> isize;

在一个子进程结束后通常由父进程调用 waitpid 回收资源并获取返回值。

若父进程先于子进程结束，则所有子进程的父进程转为用户初始进程（根节点）

  • exec
1
2
3
4
5
/// 功能：将当前进程的地址空间清空并加载一个特定的可执行文件，返回用户态后开始它的执行。
/// 参数：path 给出了要加载的可执行文件的名字；
/// 返回值：如果出错的话（如找不到名字相符的可执行文件）则返回 -1，否则不应该返回。
/// syscall ID：221
pub fn sys_exec(path: &str) -> isize;

实际传入内核的 path 只有起始指针，需要手动在末尾添加 \0

对系统调用的简单封装：

1
2
3
4
5
6
// 目前 sys_waitpid 是立即返回的，所以需要手动实现能够一直等待的调用
// 后续会将 sys_waitpid 改为阻塞式

// 等待任意或指定线程直到结束
pub fn wait(exit_code: &mut i32) -> isize;
pub fn waitpid(pid: usize, exit_code: &mut i32) -> isize;

读取文件的系统调用：sys_read：

1
2
3
4
5
6
7
8
/// 功能：从文件中读取一段内容到缓冲区。
/// 参数：fd 是待读取文件的文件描述符，切片 buffer 则给出缓冲区。
/// 返回值：如果出现了错误则返回 -1，否则返回实际读到的字节数。
/// syscall ID：63
pub fn sys_read(fd: usize, buffer: &mut [u8]) -> isize;

pub fn read(fd: usize, buf: &mut [u8]) -> isize;
pub fn getchar() -> u8; // stdin

用户初始程序：initproc shell 程序：user_shell

核心数据结构

  • Rust 编译&链接辅助程序 os/build.rs：在 link_app.S 中生成 _num_app、_app_names、app_*_start 等内容

  • 应用加载器 loader.rs：

1
2
3
4
5
6
7
8
// 全局保存所有应用名字
static ref APP_NAMES: Vec<&'static str>;

// 读取指定应用 ELF
pub fn get_app_data_by_name(name: &str) -> Option<&'static [u8]>;

// 打印所有应用名字
pub fn list_apps();
  • 进程标识符（PID）

使用 RAII 方法包装，支持自动回收

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub struct PidHandle(pub usize);    // impl Trait Drop

// 类似 FrameAllocator，可以查询未被使用的 PID
struct PidAllocator {
    current: usize,
    recycled: Vec<usize>,
}

impl PidAllocator {
    pub fn new() -> Self;
    pub fn alloc(&mut self) -> PidHandle;
    pub fn dealloc(&mut self, pid: usize);
}

// 全局 PID 管理器
static ref PID_ALLOCATOR : UPSafeCell<PidAllocator>;

// API
pub fn pid_alloc() -> PidHandle;
  • 内核栈 KernelStack

在 Lab2 中按照应用编号排布，在 Lab3 中改为以 PID 标识与排布

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 同时也实现了 Drop Trait
pub struct KernelStack {
    pid: usize,
}

// 根据 PID 计算地址
pub fn kernel_stack_position(app_id: usize) -> (usize, usize);

impl KernelStack {
    // 根据 PID 生成内核栈
    pub fn new(pid_handle: &PidHandle) -> Self;

    // 栈顶位置
    pub fn get_top(&self) -> usize;

    // 在栈顶压入值
    pub fn push_on_top<T>(&self, value: T) -> *mut T where T: Sized;
}
  • 进程控制块 TaskControlBlock

管理一个进程的所有内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 不可变的内容直接放在 TaskControlBlock 中，可变的再用一个 UPSafeCell（RefCell） 包裹起来，因为通常 TaskControlBlock 的实例为不可变引用
pub struct TaskControlBlock {
    // immutable
    pub pid: PidHandle,
    pub kernel_stack: KernelStack,
    // mutable
    inner: UPSafeCell<TaskControlBlockInner>,
}

pub struct TaskControlBlockInner {
    pub trap_cx_ppn: PhysPageNum,
    pub base_size: usize,   // 应用数据仅出现在应用地址空间低于 base_size 字节的区域
    pub task_cx: TaskContext,
    pub task_status: TaskStatus,
    pub memory_set: MemorySet,
    pub parent: Option<Weak<TaskControlBlock>>,
    pub children: Vec<Arc<TaskControlBlock>>,
    pub exit_code: i32,
}

impl TaskControlBlockInner {    // 一些字面意思的 API
    pub fn get_trap_cx(&self) -> &'static mut TrapContext;
    pub fn get_user_token(&self) -> usize;
    fn get_status(&self) -> TaskStatus;
    pub fn is_zombie(&self) -> bool;
}

impl TaskControlBlock {
    pub fn inner_exclusive_access(&self) -> RefMut<'_, TaskControlBlockInner>;
    pub fn getpid(&self) -> usize;
    pub fn new(elf_data: &[u8]) -> Self;    // 根据 ELF Data 生成进程（目前用于生成 initproc）
    pub fn exec(&self, elf_data: &[u8]) {...}
    pub fn fork(self: &Arc<TaskControlBlock>) -> Arc<TaskControlBlock> {...}
}
  • 任务管理器 TaskManager

为后续的扩展方便，将目前任务管理器对 CPU 的监控功能解耦，分到后面即将新增的结构 Processor 中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub struct TaskManager {
    ready_queue: VecDeque<Arc<TaskControlBlock>>,
}

/// A simple FIFO scheduler.
impl TaskManager {
    pub fn new() -> Self;
    pub fn add(&mut self, task: Arc<TaskControlBlock>;
    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>>;
}

pub static ref TASK_MANAGER: UPSafeCell<TaskManager>;

// API
pub fn add_task(task: Arc<TaskControlBlock>);
pub fn fetch_task() -> Option<Arc<TaskControlBlock>>;
  • 处理器管理结构 Processor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub struct Processor {
    current: Option<Arc<TaskControlBlock>>,
    idle_task_cx: TaskContext,  // 当前处理器上的 idle 控制流的任务上下文
}

// 单核条件下直接创建一个全局 Processor
pub static ref PROCESSOR: UPSafeCell<Processor>;

impl Processor {
    pub fn new() -> Self;
    fn get_idle_task_cx_ptr(&mut self) -> *mut TaskContext;
    // 取出或拷贝任务
    pub fn take_current(&mut self) -> Option<Arc<TaskControlBlock>>;
    pub fn current(&self) -> Option<Arc<TaskControlBlock>>;
}

pub fn take_current_task() -> Option<Arc<TaskControlBlock>>;
pub fn current_task() -> Option<Arc<TaskControlBlock>>;
pub fn current_user_token() -> usize;
pub fn current_trap_cx() -> &'static mut TrapContext;

Processor 有一个单独的 idle 控制流，用于在空闲时从任务管理器获取进程

而当应用交出 CPU 使用权后，内核调用 schedule 切换回 idle 控制流：

1
2
pub fn run_tasks();
pub fn schedule(switched_task_cx_ptr: *mut TaskContext);

管理机制实现

  • fork 系统调用实现

对所有内存信息进行复制，注意过程中细节，如父子关系维护

1
2
3
4
5
6
7
8
9
10
11
12
13
impl MapArea {
    pub fn from_another(another: &MapArea) -> Self;
}

impl MemorySet {
    pub fn from_existed_user(user_space: &MemorySet) -> Self;
}

impl TaskControlBlock {
    pub fn fork(self: &Arc<TaskControlBlock>) -> Arc<TaskControlBlock>;
}

pub fn sys_fork() -> isize;
  • exec 系统调用实现
1
2
3
4
5
6
impl TaskControlBlock {
    pub fn exec(&self, elf_data: &[u8]);
}

pub fn translated_str(token: usize, ptr: *const u8) -> String;
pub fn sys_exec(path: *const u8) -> isize;

编程作业

实现 sys_spawn

其实就是把 fork 和 exec 缝在一起，实际实现的时候可以直接在 TaskControlBlock::new 的基础上稍稍修改（就是把父进程设为当前进程）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// os/src/syscall/process.rs

pub fn sys_spawn(path: *const u8) -> isize {
    let token = current_user_token();
    let path = translated_str(token, path);
    if let Some(data) = get_app_data_by_name(path.as_str()) {
        let task = current_task().unwrap().spawn(data);
        let pid = task.pid.0 as isize;
        add_task(task);
        pid
    } else {
        -1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// os/src/task/task.rs

impl TaskControlBlock {
    pub fn spawn(self: &Arc<TaskControlBlock>, elf_data: &[u8]) -> Arc<TaskControlBlock> {
        let (memory_set, user_sp, entry_point) = MemorySet::from_elf(elf_data);
        let trap_cx_ppn = memory_set
            .translate(VirtAddr::from(TRAP_CONTEXT).into())
            .unwrap()
            .ppn();
        // alloc a pid and a kernel stack in kernel space
        let mut parent_inner = self.inner_exclusive_access();
        let pid_handle = pid_alloc();
        let kernel_stack = KernelStack::new(&pid_handle);
        let kernel_stack_top = kernel_stack.get_top();
        // push a task context which goes to trap_return to the top of kernel stack
        let task_control_block = Arc::new(TaskControlBlock {
            pid: pid_handle,
            kernel_stack,
            inner: unsafe {
                UPSafeCell::new(TaskControlBlockInner {
                    trap_cx_ppn,
                    base_size: parent_inner.base_size,
                    task_cx: TaskContext::goto_trap_return(kernel_stack_top),
                    task_status: TaskStatus::Ready,
                    memory_set,
                    parent: Some(Arc::downgrade(self)),
                    children: Vec::new(),
                    exit_code: 0,
                })
            },
        });
        parent_inner.children.push(task_control_block.clone());
        // prepare TrapContext in user space
        let trap_cx = task_control_block.inner_exclusive_access().get_trap_cx();
        *trap_cx = TrapContext::app_init_context(
            entry_point,
            user_sp,
            KERNEL_SPACE.exclusive_access().token(),
            kernel_stack_top,
            trap_handler as usize,
        );
        task_control_block
    }
}

stride 调度算法

在 TaskControlBlock 中加上 pass 和 priority 值，然后模拟就行，取任务的时候直接遍历一遍

fork exec spwan 对应的 pass priority 值也要分别修改

为了防止溢出，我将 BIG_STRIDE 改为了 usize::MAX / 1048576

1
2
3
4
5
6
7
8
9
// os/src/syscall/process.rs

pub fn sys_set_priority(prio: isize) -> isize {
    if prio < 2 {
        return -1;
    }
    current_task().unwrap().inner_exclusive_access().priority = prio as usize;
    prio
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// os/src/task/manager.rs

impl TaskManager {
    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        //self.ready_queue.pop_front()
        if self.ready_queue.is_empty() {
            return None;
        }
        let mut task_pos: usize = 0;
        for (idx, task) in self.ready_queue.iter().enumerate().skip(1) {
            if self.ready_queue[task_pos].inner_exclusive_access().pass > task.inner_exclusive_access().pass {
                task_pos = idx;
            }
        }
        let task = self.ready_queue.remove(task_pos).unwrap();
        let mut inner = task.inner_exclusive_access();
        inner.pass += BIG_STRIDE / inner.priority;
        drop(inner);
        Some(task)
    }
}

前向兼容

基本就是把之前的代码照搬过来，然后对着修改适应现在的框架，如 mmap 之前在 TaskManager 中，现在改到 Processor 中，在 run_tasks() 中维护运行时间。

Github Repository