Introduction

这章介绍了“伤齿龙”操作系统,主要包括 rCore 的进程结构、进程管理和调度、进程的创建和回收等内容

进程概念

任务、进程、线程和协程

  • 任务:程序在计算机上的一次执行过程称为一个任务(Task)或一个工作(Job),特点是执行过程不会被切换
  • 进程:CPU 调度和分派的对象,存在分时切换和内存虚拟化机制
  • 线程:进程的一部分,共享进程的地址空间,但是有独立的栈和独立的控制流,是处理器调度和分派的基本单位
    • 绿色线程:用户态线程,操作系统看不到用户态的线程库
  • 协程:一种用户态的轻量级线程,一个线程可以有多个协程,一般是由用户态的协程管理库来进行管理和调度

系统调用

fork 系统调用

每个进程都会有不同的进程标识符(PID),除了用户初始进程通过硬编码形式创建,其他进程全部通过 fork 来创建,它做的事情如下

  1. 创建新进程,用户态代码段、堆栈段以及其他数据段和旧进程完全相同
  2. 但是新进程的 地址空间 和旧进程不同
  3. 通用寄存器几乎完全相同,除了 a0 不同,存放了 fork 的返回值,新进程得到的是 0,父进程得到的值是子进程 PID
/// 功能:当前进程 fork 出来一个子进程。
/// 返回值:对于子进程返回 0,对于当前进程则返回子进程的 PID 。
/// syscall ID:220
pub fn sys_fork() -> isize;

waitpid 系统调用

进程通过 exit 系统调用退出后,部分资源比如内核栈不能立马回收,因此需要有别的方法,通常标记进程为 僵尸进程 之后,由父进程通过 waitpid 的系统调用来获取返回状态并回收剩下的资源。

/// 功能:当前进程等待一个子进程变为僵尸进程,回收其全部资源并收集其返回值。
/// 参数:pid 表示要等待的子进程的进程 ID,如果为 -1 的话表示等待任意一个子进程;
/// exit_code 表示保存子进程返回值的地址,如果这个地址为 0 的话表示不必保存。
/// 返回值:如果要等待的子进程不存在则返回 -1;否则如果要等待的子进程均未结束则返回 -2;
/// 否则返回结束的子进程的进程 ID。
/// syscall ID:260
pub fn sys_waitpid(pid: isize, exit_code: *mut i32) -> isize;

exec 系统调用

exec 系统调用用于执行不同的可执行文件

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

path: &str 包含了起始地址和长度信息,但系统调用需要的只有起始地址(char*),路径字符串的结束通过 \0 标记。

// user/src/exec.rs

pub fn sys_exec(path: &str) -> isize {
    syscall(SYSCALL_EXEC, [path.as_ptr() as usize, 0, 0])
}

rust 系统调用封装

sys_fork 被封装成 fork,sys_exec 被封装成 exec,但是 sys_waitpid 被拆分成两个接口

// user/src/lib.rs

pub fn wait(exit_code: &mut i32) -> isize {
    loop {
        match sys_waitpid(-1, exit_code as *mut _) {
            -2 => { yield_(); }     // 这里 waitpid 是立即返回的,-2 表示有需要等待的线程但是还没退出
            // -1 or a real pid
            exit_pid => return exit_pid,    // 不是 -2 就直接返回
        }
    }
}

pub fn waitpid(pid: usize, exit_code: &mut i32) -> isize {
    loop {
        match sys_waitpid(pid as isize, exit_code as *mut _) {
            -2 => { yield_(); }
            // -1 or a real pid
            exit_pid => return exit_pid,
        }
    }
}

可以对比 xv6: 只有一个接口,并且是阻塞的

// Wait for a child process to exit and return its pid.
// Return -1 if this process has no children.
int wait(int*);

用户程序

初始程序 initproc

用户初始程序一般需要 fork 并 exec shell

// user/src/bin/initproc.rs

#![no_std]
#![no_main]

#[macro_use]
extern crate user_lib;

use user_lib::{
    fork,
    wait,
    exec,
    yield_,
};

#[unsafe(no_mangle)]
fn main() -> i32 {
    if fork() == 0 {
        exec("user_shell\0");
    } else {
        loop {
            let mut exit_code: i32 = 0;
            let pid = wait(&mut exit_code);
            if pid == -1 {
                yield_();
                continue;
            }
            println!(
                "[initproc] Released a zombie process, pid={}, exit_code={}",
                pid,
                exit_code,
            );
        }
    }
    0
}

和 xv6 不同,这里并不会识别 shell 是否退出并重启。

shell

shell 需要读取用户输入并进行解析,因此需要添加读取的系统调用


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

但实际调用是包含了缓冲区长度信息的

// user/src/syscall.rs

pub fn sys_read(fd: usize, buffer: &mut [u8]) -> isize {
    syscall(SYSCALL_READ, [fd, buffer.as_mut_ptr() as usize, buffer.len()])
}

从标准输入封装 getchar()

// user/src/lib.rs

pub fn read(fd: usize, buf: &mut [u8]) -> isize { sys_read(fd, buf) }

// user/src/console.rs
const STDIN: usize = 0;
pub fn getchar() -> u8 {
    let mut c = [0u8; 1];
    read(STDIN, &mut c);
    c[0]
}

shell 程序实现

  1. 先打印提示符 >>
  2. 如果输入了回车换行,尝试执行对应的程序,shell进程保持等待
  3. 如果输入了退格删除,尝试打印 \b 再打印一个空格再打印一个 \b
  4. 正常情况,打印并且添加字符
// user/src/bin/user_shell.rs

#![no_std]
#![no_main]

extern crate alloc;

#[macro_use]
extern crate user_lib;

const LF: u8 = 0x0au8;
const CR: u8 = 0x0du8;
const DL: u8 = 0x7fu8;
const BS: u8 = 0x08u8;

use alloc::string::String;
use user_lib::console::getchar;
use user_lib::{exec, fork, waitpid};

#[unsafe(no_mangle)]
pub fn main() -> i32 {
    println!("Rust user shell");
    let mut line: String = String::new();
    print!(">> ");
    loop {
        let c = getchar();
        match c {
            LF | CR => {    // \n (另起一行)或者 \r (回到一行的开头)
                println!("");
                if !line.is_empty() {
                    line.push('\0');    // 路径字符串结束标志
                    let pid = fork();
                    if pid == 0 {
                        // child process
                        if exec(line.as_str()) == -1 {
                            println!("Error when executing!");
                            return -4;
                        }
                        unreachable!();
                    } else {
                        let mut exit_code: i32 = 0;
                        let exit_pid = waitpid(pid as usize, &mut exit_code);
                        assert_eq!(pid, exit_pid);
                        println!(
                            "Shell: Process {} exited with code {}",
                            pid, exit_code
                        );
                    }
                    line.clear();
                }
                print!(">> ");
            }
            BS | DL => {    // \b 退格 或者 DEL 删除
                if !line.is_empty() {
                    print!("{}", BS as char);   // 光标左移
                    print!(" ");                // 用空格覆盖旧的字符
                    print!("{}", BS as char);   // 光标左移
                    line.pop();                 // 从字符串中删掉那个字符
                }
            }
            _ => {
                print!("{}", c as char);
                line.push(c as char);
            }
        }
    }
}

进程管理的数据结构

应用的链接和加载

由于 exec 系统调用需要根据应用的名字而非编号来获取 ELF 数据,因此链接和加载接口需要改变,下面是 rCore 生成链接脚本的程序

// os/build.rs

for i in 0..apps.len() {
    writeln!(f, r#"    .quad app_{}_start"#, i)?;   // r#"..."# 表示按字面内容处理,不需要考虑转义
}
writeln!(f, r#"    .quad app_{}_end"#, apps.len() - 1)?;

writeln!(f, r#"
.global _app_names
_app_names:"#)?;
for app in apps.iter() {
    writeln!(f, r#"    .string "{}""#, app)?;
}

for (idx, app) in apps.iter().enumerate() {
    ...
}

生成出来的链接文件如下,可以看到它可以分为三个部分,_num_app 保存了各个镜像的地址, _app_names 保存了字符串,app_xxx_start...app_xxx_end 保存了ELF 数据

# os/src/link_app.S

    .align 3
    .section .data
    .global _num_app
_num_app:
    .quad 17
    .quad app_0_start
    .quad app_1_start
...
    .quad app_15_start
    .quad app_16_start
    .quad app_16_end

    .global _app_names
_app_names:
    .string "exit"
    .string "fantastic_text"
    ...
    .string "usertests-simple"
    .string "yield"

    .section .data
    .global app_0_start
    .global app_0_end
    .align 3
app_0_start:
    .incbin "../user/target/riscv64gc-unknown-none-elf/release/exit"
app_0_end:

    .section .data
    .global app_1_start
    .global app_1_end
    .align 3
app_1_start:
    .incbin "../user/target/riscv64gc-unknown-none-elf/release/fantastic_text"
app_1_end:

    .section .data
    .global app_2_start
    .global app_2_end
    .align 3
app_2_start:
    .incbin "../user/target/riscv64gc-unknown-none-elf/release/forkexec"
app_2_end:

...
...

    .section .data
    .global app_16_start
    .global app_16_end
    .align 3
app_16_start:
    .incbin "../user/target/riscv64gc-unknown-none-elf/release/yield"
app_16_end:

加载器也需要修改,从 _app_names 处读取程序名

lazy_static! {
    ///All of app's name
    static ref APP_NAMES: Vec<&'static str> = {
        let num_app = get_num_app();
        unsafe extern "C" {
            safe fn _app_names();
        }
        let mut start = linker_symbol_addr!(_app_names) as *const u8;
        let mut v = Vec::new();
        unsafe {
            for _ in 0..num_app {
                let mut end = start;
                while end.read_volatile() != b'\0' {
                    end = end.add(1);
                }
                let slice = core::slice::from_raw_parts(start, end as usize - start as usize);
                let str = core::str::from_utf8(slice).unwrap();
                v.push(str);
                start = end.add(1);
            }
        }
        v
    };
}

接下来需要能够按照程序名找到对应的 ELF 数据

#[allow(unused)]
///get app data from name
pub fn get_app_data_by_name(name: &str) -> Option<&'static [u8]> {
    let num_app = get_num_app();
    (0..num_app)                            // Range<usize> 类型
        .find(|&i| APP_NAMES[i] == name)    // 找到符合要求的,返回 Option<usize>
        .map(get_app_data)                  // Some(value) => Some(f(value))
}
///list all apps
pub fn list_apps() {
    println!("/**** APPS ****");
    for app in APP_NAMES.iter() {
        println!("{}", app);
    }
    println!("**************/");
}

进程标识符

每一个进程都要对应一个 PID,因此生命周期也是绑定的,使用 RAII 思想,当进程被回收时,PID 也会被回收

// os/src/task/pid.rs
pub struct PidHandle(pub usize);    // 元组结构体

impl Drop for PidHandle {
    fn drop(&mut self) {
        //println!("drop pid {}", self.0);
        PID_ALLOCATOR.exclusive_access().dealloc(self.0);
    }
}

仿照 FrameAllocator 实现 PidAllocator,其中 current 是当前未分配的 pid 的起点,而 recycled 则存放了回收的 pid

pub struct PidAllocator {
    current: usize,
    recycled: Vec<usize>,
}

impl PidAllocator {
    ///Create an empty `PidAllocator`
    pub fn new() -> Self {
        PidAllocator {
            current: 1,
            recycled: Vec::new(),
        }
    }
    ///Allocate a pid
    pub fn alloc(&mut self) -> PidHandle {
        if let Some(pid) = self.recycled.pop() {
            PidHandle(pid)
        } else {
            self.current += 1;
            PidHandle(self.current - 1)
        }
    }
    ///Recycle a pid
    pub fn dealloc(&mut self, pid: usize) {
        assert!(pid < self.current);
        assert!(
            !self.recycled.iter().any(|ppid| *ppid == pid),
            "pid {} has been deallocated!",
            pid
        );
        self.recycled.push(pid);
    }
}

注意到 PID 分配从 1 开始,这和 Linux 的约定是一样的:Linux 中保留 PID 0 并让用户态 init 进程使用 PID 1。

///Allocate a pid from PID_ALLOCATOR
pub fn pid_alloc() -> PidHandle {
    PID_ALLOCATOR.exclusive_access().alloc()
}

为其他子模块提供接口,分配 PidHandle

内核栈

内核栈的代码如下,注意到内核栈是根据 PID 创建的,但是内核栈自身并不保存栈顶栈底位置,而是插入到了 KERNEL_SPACE 中,需要时根据 PID 计算栈的位置。

///Kernelstack for app
pub struct KernelStack {
    pid: usize,
}

impl KernelStack {
    ///Create a kernelstack from pid
    pub fn new(pid_handle: &PidHandle) -> Self {
        let pid = pid_handle.0;
        let (kernel_stack_bottom, kernel_stack_top) = kernel_stack_position(pid);
        KERNEL_SPACE.exclusive_access().insert_framed_area(
            kernel_stack_bottom.into(),
            kernel_stack_top.into(),
            MapPermission::R | MapPermission::W,
        );
        KernelStack { pid: pid_handle.0 }
    }
    #[allow(unused)]
    ///Push a value on top of kernelstack
    pub fn push_on_top<T>(&self, value: T) -> *mut T
    where
        T: Sized,
    {
        let kernel_stack_top = self.get_top();
        let ptr_mut = (kernel_stack_top - core::mem::size_of::<T>()) as *mut T;
        unsafe {
            *ptr_mut = value;
        }
        ptr_mut
    }
    ///Get the value on the top of kernelstack
    pub fn get_top(&self) -> usize {
        let (_, kernel_stack_top) = kernel_stack_position(self.pid);
        kernel_stack_top
    }
}

impl Drop for KernelStack { // RAII:回收 KernelStack时,物理帧也会跟着回收
    fn drop(&mut self) {
        let (kernel_stack_bottom, _) = kernel_stack_position(self.pid);
        let kernel_stack_bottom_va: VirtAddr = kernel_stack_bottom.into();
        KERNEL_SPACE
            .exclusive_access()
            .remove_area_with_start_vpn(kernel_stack_bottom_va.into()); // 找到一块起始地址为栈底的连续物理内存区域并释放
    }
}

对于栈位置的获取,没有太大变化,可以和 xv6 进行对比

pub fn kernel_stack_position(app_id: usize) -> (usize, usize) {
    let top = TRAMPOLINE - app_id * (KERNEL_STACK_SIZE + PAGE_SIZE);
    let bottom = top - KERNEL_STACK_SIZE;
    (bottom, top)
}

xv6 的内核栈是每个进程位置提前预留好的,与 PID 无关,进入 trap 时通过 struct proc 中的 kstack 切换栈指针。

#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)

进程控制块 PCB

对 TaskControlBlock 修改,使其满足进程控制块的功能

pub struct TaskControlBlock {
    // immutable
    pub pid: PidHandle,
    pub kernel_stack: KernelStack,
    // mutable
    inner: UPSafeCell<TaskControlBlockInner>,
}

pub struct TaskControlBlockInner {
    pub trap_cx_ppn: PhysPageNum,   // trap 上下文物理页号
    #[allow(unused)]
    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,             // 退出状态
}

注意到 TCB 可以分成两部分,pid 和 kernel_stack 是在初始化之后不可修改的,而 inner 则可以修改,通过 UPSafeCell

为了避免循环引用造成内存泄漏,parent 使用了 Weak<T> 智能指针,只会增加弱引用次数而不增加强引用计数,父进程只要不被任何强引用持有时就会销毁。

因为弱引用不保证对象一定存在,所以需要先调用 weak.upgrade() 得到 Option<Arc<T>>

// 示例
use std::sync::Arc;

let strong = Arc::new(42);
let weak = Arc::downgrade(&strong);

// 对象仍然存在
assert_eq!(*weak.upgrade().unwrap(), 42);

// 释放最后一个强引用
drop(strong);

// 对象已经销毁
assert!(weak.upgrade().is_none());

需要获取父进程时

if let Some(parent_weak) = &task.inner_exclusive_access().parent {
    if let Some(parent) = parent_weak.upgrade() {
        // 这里可以访问父进程的 TaskControlBlock
        println!("Parent PID: {}", parent.pid.0);
    }
}

TaskControlBlock 和 TaskControBlockInner 各自实现了以下方法

  • TaskControlBlockInner
    1. get_trap_cx 返回 trap 上下文静态引用
    2. get_user_token 返回地址空间的 satp
    3. get_status 返回任务状态
    4. is_zombie 确认任务状态是否为 TaskStatus::Zombie
  • TaskControlBlock
    1. inner_exclusive_access 返回 inner 的可变引用
    2. new 给定 ELF 数据新建对象,任务上下文是返回 trap return 的,trap 上下文和内核栈有关
    3. exec 内容大致和 new 接近,但是少了 pid、kernel stack、parent、childrenen、exit code等部分
    4. fork 复制地址空间、新分配 pid、kernel stack、parent、children 等部分
    5. getpid 返回 pid

任务管理器

任务管理器仅负责管理任务(进程),获得任务并执行则交给了 Processor 结构体,这种做法和 xv6 固定数组的方式截然不同,使得更多的任务可以参与到调度中。

// os/src/task/manager.rs

///A array of `TaskControlBlock` that is thread-safe
pub struct TaskManager {
    ready_queue: VecDeque<Arc<TaskControlBlock>>,
}

/// A simple FIFO scheduler.
impl TaskManager {
    ///Creat an empty TaskManager
    pub fn new() -> Self {
        Self {
            ready_queue: VecDeque::new(),
        }
    }
    ///Add a task to `TaskManager`
    pub fn add(&mut self, task: Arc<TaskControlBlock>) {
        self.ready_queue.push_back(task);
    }
    ///Remove the first task and return it,or `None` if `TaskManager` is empty
    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        self.ready_queue.pop_front()
    }
}

lazy_static! {
    pub static ref TASK_MANAGER: UPSafeCell<TaskManager> =
        unsafe { UPSafeCell::new(TaskManager::new()) };
}
///Interface offered to add task
pub fn add_task(task: Arc<TaskControlBlock>) {
    TASK_MANAGER.exclusive_access().add(task);
}
///Interface offered to pop the first task
pub fn fetch_task() -> Option<Arc<TaskControlBlock>> {
    TASK_MANAGER.exclusive_access().fetch()
}

全局的 TASK_MANAGER 依旧使用 UPSafeCell 进行包装,提供两个接口 add_task 和 fetch_task,分别对应了队列的 PUSH 和 POP 操作。进程控制块被放在了内存堆上,而任务管理器只以队列的方式保存了引用计数智能指针,这样可以减少数据移动开销

处理器管理结构

// os/src/task/processor.rs

pub struct Processor {
    current: Option<Arc<TaskControlBlock>>, // 当前处理器上正在执行的任务
    idle_task_cx: TaskContext,              // 当前处理器上的 idle 控制流的任务上下文。
}

impl Processor {
    pub fn new() -> Self {
        Self {
            current: None,
            idle_task_cx: TaskContext::zero_init(),
        }
    }
    fn get_idle_task_cx_ptr(&mut self) -> *mut TaskContext {
        &mut self.idle_task_cx as *mut _    // 转换引用为裸指针,相当于 as *mut TaskContext
    }
    pub fn take_current(&mut self) -> Option<Arc<TaskControlBlock>> {
        self.current.take()
    }
    pub fn current(&self) -> Option<Arc<TaskControlBlock>> {
        self.current.as_ref().map(Arc::clone)
    }
}

Processor 用于描述处理器的执行状态,单个 CPU 情况下只需要一个全局实例

// os/src/task/processor.rs

lazy_static! {
    pub static ref PROCESSOR: UPSafeCell<Processor> = unsafe {
        UPSafeCell::new(Processor::new())
    };
}

读取修改当前正在运行的任务的相关信息

// os/src/task/processor.rs

impl Processor {
    pub fn take_current(&mut self) -> Option<Arc<TaskControlBlock>> {
        self.current.take()     // 取走当前任务,原来的位置会变成 None
    }
    pub fn current(&self) -> Option<Arc<TaskControlBlock>> {    // as_ref() 得到 Option<&Arc<TaskControlBlock>>
        self.current.as_ref().map(|task| Arc::clone(task))      // map() 将传入的 Option<&T> 交给 Arc::clone 变成 Option<T> 返回
    }
}

pub fn take_current_task() -> Option<Arc<TaskControlBlock>> {
    PROCESSOR.exclusive_access().take_current()
}

pub fn current_task() -> Option<Arc<TaskControlBlock>> {
    PROCESSOR.exclusive_access().current()
}

pub fn current_user_token() -> usize {
    let task = current_task().unwrap();
    let token = task.inner_exclusive_access().get_user_token();
    token
}

pub fn current_trap_cx() -> &'static mut TrapContext {
    current_task().unwrap().inner_exclusive_access().get_trap_cx()
}

run_tasks 会通过 fetch_task 获取任务,然后从 idle 上下文中切换过去

// os/src/task/processor.rs

pub fn run_tasks() {
    loop {
        let mut processor = PROCESSOR.exclusive_access();
        if let Some(task) = fetch_task() {
            let idle_task_cx_ptr = processor.get_idle_task_cx_ptr();
            // access coming task TCB exclusively
            let mut task_inner = task.inner_exclusive_access();
            let next_task_cx_ptr = &task_inner.task_cx as *const TaskContext;
            task_inner.task_status = TaskStatus::Running;
            // stop exclusively accessing coming task TCB manually
            drop(task_inner);
            processor.current = Some(task);
            // stop exclusively accessing processor manually
            drop(processor);
            unsafe {
                __switch(
                    idle_task_cx_ptr,
                    next_task_cx_ptr,
                );
            }
        }
    }
}

impl Processor {
    fn get_idle_task_cx_ptr(&mut self) -> *mut TaskContext {
        &mut self.idle_task_cx as *mut _
    }
}

这里手动释放引用/指针是因为进入 __switch 之后上下文就会切换,没有回收,进入 __switch 时,idle 上下文就会保存当前 run_tasks 的上下文。

而当进程用完时间片之后,控制流会切换回 idle

///Return to idle control flow for new scheduling
pub fn schedule(switched_task_cx_ptr: *mut TaskContext) {
    let mut processor = PROCESSOR.exclusive_access();
    let idle_task_cx_ptr = processor.get_idle_task_cx_ptr();
    drop(processor);
    unsafe {
        __switch(switched_task_cx_ptr, idle_task_cx_ptr);
    }
}

这里 run_tasks 有些类似于 xv6 的 scheduler ,而 schedule 有些类似于 sched

进程管理机制

初始进程的创建

使用 add_task 将第一个进程添加到任务队列中,INITPROC 通过 lazy_static! 进行初始化

// os/src/task/mod.rs

use crate::loader::get_app_data_by_name;
use manager::add_task;

lazy_static! {
    pub static ref INITPROC: Arc<TaskControlBlock> = Arc::new(
        TaskControlBlock::new(get_app_data_by_name("initproc").unwrap())
    );
}

pub fn add_initproc() {
    add_task(INITPROC.clone());     // clone 提供一个新的Arc对象,指向 initproc 的 TCB
}

进程调度

yield 系统调用需要让 CPU 放弃当前进程然后执行下一个任务,而时间片用完(也就是计时器中断发生)时,也要放弃当前进程并执行下一个进程

// os/src/syscall/process.rs

pub fn sys_yield() -> isize {
    suspend_current_and_run_next();
    0
}

// os/src/trap/mod.rs

#[unsafe(no_mangle)]
pub fn trap_handler() -> ! {
    set_kernel_trap_entry();
    let scause = scause::read();
    let stval = stval::read();
    let trap: Trap<Interrupt, Exception> = match scause.cause().try_into() {
        Ok(trap) => trap,
        Err(_) => panic!(
            "Unsupported trap {:?}, stval = {:#x}!",
            scause.cause(),
            stval
        ),
    };
    match trap {
        Trap::Interrupt(Interrupt::SupervisorTimer) => {
            set_next_trigger();
            suspend_current_and_run_next();
        }
        ...
    }
    trap_return();
}

这两种情况都走 suspend_current_and_run_next(),取得当前的 TCB 引用,将状态改成 Ready 后将任务插入到队列中,然后调用 schedule 切换到 idle 控制流,那么 idle 控制流就会回到 run_tasks 中

/// Suspend the current 'Running' task and run the next task in task list.
pub fn suspend_current_and_run_next() {
    // There must be an application running.
    let task = take_current_task().unwrap();

    // ---- access current TCB exclusively
    let mut task_inner = task.inner_exclusive_access();
    let task_cx_ptr = &mut task_inner.task_cx as *mut TaskContext;
    // Change status to Ready
    task_inner.task_status = TaskStatus::Ready;
    drop(task_inner);
    // ---- release current PCB

    // push back to ready queue.
    add_task(task);
    // jump to scheduling cycle
    schedule(task_cx_ptr);
}

如果只有一个任务,那么后面 schedule 和 run_tasks 还是会选中这个任务并且执行下去

进程的生成

fork

fork 需要为子进程创建一个和父进程几乎完全相同的地址空间,所以需要对原来的 mm 模块进行一些扩展,能够进行“复制”操作

// os/src/mm/memory_set.rs

impl MapArea {
    pub fn from_another(another: &MapArea) -> Self {
        Self {
            vpn_range: VPNRange::new(
                another.vpn_range.get_start(),
                another.vpn_range.get_end()
            ),
            data_frames: BTreeMap::new(),   // 物理页帧还没映射
            map_type: another.map_type,
            map_perm: another.map_perm,
        }
    }
}

impl MemorySet {
    pub fn from_existed_user(user_space: &MemorySet) -> MemorySet {
        let mut memory_set = Self::new_bare();
        // map trampoline
        memory_set.map_trampoline();    // trampoline 映射
        // copy data sections/trap_context/user_stack
        for area in user_space.areas.iter() {
            let new_area = MapArea::from_another(area);
            memory_set.push(new_area, None);    // 只建立映射,不复制数据
            // copy data from another space
            for vpn in area.vpn_range {         // 在这里进行复制
                let src_ppn = user_space.translate(vpn).unwrap().ppn();
                let dst_ppn = memory_set.translate(vpn).unwrap().ppn();
                dst_ppn.get_bytes_array().copy_from_slice(src_ppn.get_bytes_array());
            }
        }
        memory_set
    }
}

TCB 中的 fork 方法前面已经有介绍,需要复制地址空间、新分配/初始化 pid、kernel stack、parent、children 等部分

// os/src/task/task.rs

impl TaskControlBlock {
    pub fn fork(self: &Arc<TaskControlBlock>) -> Arc<TaskControlBlock> {
        // ---- access parent PCB exclusively
        let mut parent_inner = self.inner_exclusive_access();
        // copy user space(include trap context)
        let memory_set = MemorySet::from_existed_user(
            &parent_inner.memory_set
        );
        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 pid_handle = pid_alloc();
        let kernel_stack = KernelStack::new(&pid_handle);
        let kernel_stack_top = kernel_stack.get_top();
        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,
            })},
        });
        // add child
        parent_inner.children.push(task_control_block.clone());
        // modify kernel_sp in trap_cx
        // **** access children PCB exclusively
        let trap_cx = task_control_block.inner_exclusive_access().get_trap_cx();
        trap_cx.kernel_sp = kernel_stack_top;
        // return
        task_control_block
        // ---- stop exclusively accessing parent/children PCB automatically
    }
}

sys_fork 除了调用 fork 添加新进程到队列中以外,还需要处理子进程的返回值 a0 为 0

// os/src/syscall/process.rs

pub fn sys_fork() -> isize {
    let current_task = current_task().unwrap();
    let new_task = current_task.fork();
    let new_pid = new_task.pid.0;
    // modify trap context of new_task, because it returns immediately after switching
    let trap_cx = new_task.inner_exclusive_access().get_trap_cx();
    // we do not have to move to next instruction since we have done it before
    // for child process, fork returns 0
    trap_cx.x[10] = 0;  //x[10] is a0 reg
    // add new task to scheduler
    add_task(new_task);
    new_pid as isize
}

不仅如此,当前进程返回时需要从下一条指令开始执行,并且 a0 要填上子进程 pid

// os/src/trap/mod.rs

#[unsafe(no_mangle)]
pub fn trap_handler() -> ! {
    set_kernel_trap_entry();
    let scause = scause::read();
    let stval = stval::read();
    let trap: Trap<Interrupt, Exception> = match scause.cause().try_into() {
        Ok(trap) => trap,
        Err(_) => panic!(
            "Unsupported trap {:?}, stval = {:#x}!",
            scause.cause(),
            stval
        ),
    };
    match trap {
        Trap::Exception(Exception::UserEnvCall) => {
            // jump to next instruction anyway
            let mut cx = current_trap_cx();
            cx.sepc += 4;
            // get system call return value
            let result = syscall(cx.x[17], [cx.x[10], cx.x[11], cx.x[12]]);
            // cx is changed during sys_exec, so we have to call it again
            cx = current_trap_cx();
            cx.x[10] = result as usize;
        }
    ...
}

exec

exec 前面也有介绍,从 ELF 中建立地址空间,设置 trap 上下文,旧的地址空间会被自动释放掉

// os/src/task/task.rs

impl TaskControlBlock {
    pub fn exec(&self, elf_data: &[u8]) {
        // memory_set with elf program headers/trampoline/trap context/user stack
        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();

        // **** access inner exclusively
        let mut inner = self.inner_exclusive_access();
        // substitute memory_set
        inner.memory_set = memory_set;
        // update trap_cx ppn
        inner.trap_cx_ppn = trap_cx_ppn;
        // initialize trap_cx
        let trap_cx = inner.get_trap_cx();
        *trap_cx = TrapContext::app_init_context(
            entry_point,
            user_sp,
            KERNEL_SPACE.exclusive_access().token(),
            self.kernel_stack.get_top(),
            linker_symbol_addr!(trap_handler),
        );
        // **** stop exclusively accessing inner automatically
    }
}

不需要处理任务上下文,因为返回时会从 trap 上下文中恢复,而旧的任务上下文已经不需要了。然后就可以实现 sys_exec

// os/src/mm/page_table.rs

pub fn translated_str(token: usize, ptr: *const u8) -> String {
    let page_table = PageTable::from_token(token);
    let mut string = String::new();
    let mut va = ptr as usize;
    loop {
        let ch: u8 = *(page_table.translate_va(VirtAddr::from(va)).unwrap().get_mut());
        if ch == 0 {
            break;
        } else {
            string.push(ch as char);
            va += 1;
        }
    }
    string
}

// os/src/syscall/process.rs

pub fn sys_exec(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();
        task.exec(data);
        0
    } else {
        -1
    }
}

因为 sys_exec 涉及到用户态的字符串数据,所以 rCore 添加了一个辅助函数,将用户态的字符串复制过来。这里的返回值中,0 其实没有太大意义,因为 Trap 上下文已经变了。

Trap 上下文获取

因为执行 exec 之后,trap_cx_ppn 已经发生了改变,因此需要在返回前重新获取一次 cx

// os/src/trap/mod.rs

#[unsafe(no_mangle)]
pub fn trap_handler() -> ! {
    set_kernel_trap_entry();
    let scause = scause::read();
    let stval = stval::read();
    let trap: Trap<Interrupt, Exception> = match scause.cause().try_into() {
        Ok(trap) => trap,
        Err(_) => panic!(
            "Unsupported trap {:?}, stval = {:#x}!",
            scause.cause(),
            stval
        ),
    };
    match trap {
        Trap::Exception(Exception::UserEnvCall) => {
            // jump to next instruction anyway
            let mut cx = current_trap_cx();
            cx.sepc += 4;
            // get system call return value
            let result = syscall(cx.x[17], [cx.x[10], cx.x[11], cx.x[12]]);
            // cx is changed during sys_exec, so we have to call it again
            cx = current_trap_cx();
            cx.x[10] = result as usize;
        }
        ...
    }
    trap_return();
}

sys_read

前面提到了 shell 的实现需要 getchar,而 getchar 是通过标准输入和 read 系统调用实现的,这里 console_getchar 则是 rustsbi 的接口

// os/src/syscall/fs.rs

use crate::sbi::console_getchar;

const FD_STDIN: usize = 0;

pub fn sys_read(fd: usize, buf: *const u8, len: usize) -> isize {
    match fd {
        FD_STDIN => {
            assert_eq!(len, 1, "Only support len = 1 in sys_read!");
            let mut c: usize;
            loop {
                c = console_getchar();
                if c == 0 {     // 返回 0 表示没输入
                    suspend_current_and_run_next();
                    continue;
                } else {
                    break;
                }
            }
            let ch = c as u8;
            let mut buffers = translated_byte_buffer(current_user_token(), buf, len);
            unsafe { buffers[0].as_mut_ptr().write_volatile(ch); }
            1
        }
        _ => {
            panic!("Unsupported fd in sys_read!");
        }
    }
}

对比:xv6 如何获取控制台输入?

在 xv6 中,因为没有 sbi,所以最后是通过读地址来完成的,标准输入的 sys_read 会一步步进入 fileread, consoleread

uint64
sys_read(void)
{
  struct file *f;
  int n;
  uint64 p;

  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argaddr(1, &p) < 0)
    return -1;
  return fileread(f, p, n);     // <==
}
// Read from file f.
// addr is a user virtual address.
int
fileread(struct file *f, uint64 addr, int n)
{
  int r = 0;

  if(f->readable == 0)
    return -1;

  if(f->type == FD_PIPE){
    r = piperead(f->pipe, addr, n);
  } else if(f->type == FD_DEVICE){
    if(f->major < 0 || f->major >= NDEV || !devsw[f->major].read)
      return -1;
    r = devsw[f->major].read(1, addr, n);   // <==
  } else if(f->type == FD_INODE){
    ilock(f->ip);
    if((r = readi(f->ip, 1, addr, f->off, n)) > 0)
      f->off += r;
    iunlock(f->ip);
  } else {
    panic("fileread");
  }

  return r;
}
struct {
  struct spinlock lock;
  
  // input
#define INPUT_BUF 128
  char buf[INPUT_BUF];
  uint r;  // Read index
  uint w;  // Write index
  uint e;  // Edit index
} cons;

void
consoleinit(void)
{
  initlock(&cons.lock, "cons");

  uartinit();

  // connect read and write system calls
  // to consoleread and consolewrite.
  devsw[CONSOLE].read = consoleread;    // <==
  devsw[CONSOLE].write = consolewrite;
}
#define C(x)  ((x)-'@')  // Control-x

//
// user read()s from the console go here.
// copy (up to) a whole input line to dst.
// user_dist indicates whether dst is a user
// or kernel address.
//
int
consoleread(int user_dst, uint64 dst, int n)
{
  uint target;
  int c;
  char cbuf;

  target = n;
  acquire(&cons.lock);
  while(n > 0){
    // wait until interrupt handler has put some
    // input into cons.buffer.
    while(cons.r == cons.w){
      if(myproc()->killed){
        release(&cons.lock);
        return -1;
      }
      sleep(&cons.r, &cons.lock);
    }

    c = cons.buf[cons.r++ % INPUT_BUF];

    if(c == C('D')){  // end-of-file
      if(n < target){
        // Save ^D for next time, to make sure
        // caller gets a 0-byte result.
        cons.r--;
      }
      break;
    }

    // copy the input byte to the user-space buffer.
    cbuf = c;
    if(either_copyout(user_dst, dst, &cbuf, 1) == -1)
      break;

    dst++;
    --n;

    if(c == '\n'){
      // a whole line has arrived, return to
      // the user-level read().
      break;
    }
  }
  release(&cons.lock);

  return target - n;
}

而 consoleread 从控制台缓冲区 cons.buf 中读取数据,再拷贝到用户空间中,如果缓冲区为空,那么就会等待中断,如果发生 UART 中断,那么usertrap 会判断为设备终端并调用 devintr,进一步识别出 UART 中断

int
devintr()
{
  uint64 scause = r_scause();

  if((scause & 0x8000000000000000L) &&
     (scause & 0xff) == 9){
    // this is a supervisor external interrupt, via PLIC.

    // irq indicates which device interrupted.
    int irq = plic_claim();

    if(irq == UART0_IRQ){
      uartintr();
    } else if(irq == VIRTIO0_IRQ){
      virtio_disk_intr();
    } else if(irq){
      printf("unexpected interrupt irq=%d\n", irq);
    }

    // the PLIC allows each device to raise at most one
    // interrupt at a time; tell the PLIC the device is
    // now allowed to interrupt again.
    if(irq)
      plic_complete(irq);

    return 1;
  } else if(scause == 0x8000000000000001L){
    // software interrupt from a machine-mode timer interrupt,
    // forwarded by timervec in kernelvec.S.

    if(cpuid() == 0){
      clockintr();
    }
    
    // acknowledge the software interrupt by clearing
    // the SSIP bit in sip.
    w_sip(r_sip() & ~2);

    return 2;
  } else {
    return 0;
  }
}

在 uartintr 中,会调用 uartgetc 读取字符

// handle a uart interrupt, raised because input has
// arrived, or the uart is ready for more output, or
// both. called from trap.c.
void
uartintr(void)
{
  // read and process incoming characters.
  while(1){
    int c = uartgetc();
    if(c == -1)
      break;
    consoleintr(c);
  }

  // send buffered characters.
  acquire(&uart_tx_lock);
  uartstart();
  release(&uart_tx_lock);
}
#define Reg(reg) ((volatile unsigned char *)(UART0 + reg))
#define LSR 5                 // line status register
#define RHR 0                 // receive holding register (for input bytes)
#define ReadReg(reg) (*(Reg(reg)))

// read one input character from the UART.
// return -1 if none is waiting.
int
uartgetc(void)
{
  if(ReadReg(LSR) & 0x01){
    // input data is ready.
    return ReadReg(RHR);
  } else {
    return -1;
  }
}

每读取一个字符,就会复制到缓冲区中

//
// the console input interrupt handler.
// uartintr() calls this for input character.
// do erase/kill processing, append to cons.buf,
// wake up consoleread() if a whole line has arrived.
//
void
consoleintr(int c)
{
  acquire(&cons.lock);

  switch(c){
  case C('P'):  // Print process list.
    procdump();
    break;
  case C('U'):  // Kill line.
    while(cons.e != cons.w &&
          cons.buf[(cons.e-1) % INPUT_BUF] != '\n'){
      cons.e--;
      consputc(BACKSPACE);
    }
    break;
  case C('H'): // Backspace
  case '\x7f':
    if(cons.e != cons.w){
      cons.e--;
      consputc(BACKSPACE);
    }
    break;
  default:
    if(c != 0 && cons.e-cons.r < INPUT_BUF){
      c = (c == '\r') ? '\n' : c;

      // echo back to the user.
      consputc(c);

      // store for consumption by consoleread().
      cons.buf[cons.e++ % INPUT_BUF] = c;

      if(c == '\n' || c == C('D') || cons.e == cons.r+INPUT_BUF){
        // wake up consoleread() if a whole line (or end-of-file)
        // has arrived.
        cons.w = cons.e;
        wakeup(&cons.r);
      }
    }
    break;
  }
  
  release(&cons.lock);
}

如果没有收到新的字符了,那么调用 uartstart 将 UART 缓冲区 uart_tx_buf 的字符发送回去,如有需要,唤醒对应的进程

// if the UART is idle, and a character is waiting
// in the transmit buffer, send it.
// caller must hold uart_tx_lock.
// called from both the top- and bottom-half.
void
uartstart()
{
  while(1){
    if(uart_tx_w == uart_tx_r){
      // transmit buffer is empty.
      return;
    }
    
    if((ReadReg(LSR) & LSR_TX_IDLE) == 0){
      // the UART transmit holding register is full,
      // so we cannot give it another byte.
      // it will interrupt when it's ready for a new byte.
      return;
    }
    
    int c = uart_tx_buf[uart_tx_r];
    uart_tx_r = (uart_tx_r + 1) % UART_TX_BUF_SIZE;
    
    // maybe uartputc() is waiting for space in the buffer.
    wakeup(&uart_tx_r);
    
    WriteReg(THR, c);
  }
}

进程资源回收

进程退出与 sys_exit

调用 sys_exit 之后,内核会调用 exit_current_and_run_next() 或者进程访问不合法被杀死也会调用

// os/src/syscall/process.rs

pub fn sys_exit(exit_code: i32) -> ! {
    exit_current_and_run_next(exit_code);
    panic!("Unreachable in sys_exit!");
}
// os/src/trap/mod.rs

#[unsafe(no_mangle)]
pub fn trap_handler() -> ! {
    set_kernel_trap_entry();
    let scause = scause::read();
    let stval = stval::read();
    let trap: Trap<Interrupt, Exception> = match scause.cause().try_into() {
        Ok(trap) => trap,
        Err(_) => panic!(
            "Unsupported trap {:?}, stval = {:#x}!",
            scause.cause(),
            stval
        ),
    };
    match trap {
        Trap::Exception(Exception::StoreFault) |
        Trap::Exception(Exception::StorePageFault) |
        Trap::Exception(Exception::InstructionFault) |
        Trap::Exception(Exception::InstructionPageFault) |
        Trap::Exception(Exception::LoadFault) |
        Trap::Exception(Exception::LoadPageFault) => {
            println!(
                "[kernel] {:?} in application, bad addr = {:#x}, bad instruction = {:#x}, kernel killed it.",
                scause.cause(),
                stval,
                current_trap_cx().sepc,
            );
            // page fault exit code
            exit_current_and_run_next(-2);
        }
        Trap::Exception(Exception::IllegalInstruction) => {
            println!("[kernel] IllegalInstruction in application, kernel killed it.");
            // illegal instruction exit code
            exit_current_and_run_next(-3);
        }
        ...
    }
    trap_return();
}

退出时,对于一般进程,会设置状态为 Zombie,然后将子进程挂载到 initproc 下,最后清理掉当前进程的内存资源并释放相关引用(但是页表的资源和内核栈还没有回收,得等 TCB 被回收)进行下一次调度。

impl MemorySet {
    pub fn recycle_data_pages(&mut self) {
        self.areas.clear();
    }
}

/// Exit the current 'Running' task and run the next task in task list.
pub fn exit_current_and_run_next(exit_code: i32) {
    // take from Processor
    let task = take_current_task().unwrap();

    let pid = task.getpid();
    if pid == IDLE_PID {
        println!(
            "[kernel] Idle process exit with exit_code {} ...",
            exit_code
        );
        if exit_code != 0 {
            //crate::sbi::shutdown(255); //255 == -1 for err hint
            shutdown(true)
        } else {
            //crate::sbi::shutdown(0); //0 for success hint
            shutdown(false)
        }
    }

    // **** access current TCB exclusively
    let mut inner = task.inner_exclusive_access();
    // Change status to Zombie
    inner.task_status = TaskStatus::Zombie;
    // Record exit code
    inner.exit_code = exit_code;
    // do not move to its parent but under initproc

    // ++++++ access initproc TCB exclusively
    {
        let mut initproc_inner = INITPROC.inner_exclusive_access();
        for child in inner.children.iter() {
            child.inner_exclusive_access().parent = Some(Arc::downgrade(&INITPROC));
            initproc_inner.children.push(child.clone());
        }
    }
    // ++++++ release parent PCB

    inner.children.clear();
    // deallocate user space
    inner.memory_set.recycle_data_pages();
    drop(inner);
    // **** release current PCB
    // drop task manually to maintain rc correctly
    drop(task);
    // we do not have to save task context
    let mut _unused = TaskContext::zero_init();
    schedule(&mut _unused as *mut _);
}

父进程回收与 sys_waitpid

子进程没释放的资源将在这里进行释放,移除子进程时,会确保这是最后一个强引用,离开作用域之后子进程剩下没释放的 TCB 资源(包括PID、页表、内核栈等)就会自动释放

// os/src/syscall/process.rs

/// If there is not a child process whose pid is same as given, return -1.
/// Else if there is a child process but it is still running, return -2.
pub fn sys_waitpid(pid: isize, exit_code_ptr: *mut i32) -> isize {
    let task = current_task().unwrap();
    // find a child process

    // ---- access current TCB exclusively
    let mut inner = task.inner_exclusive_access();
    if inner.children
        .iter()
        .find(|p| {pid == -1 || pid as usize == p.getpid()})    // 确认子进程中确实有这个 PID
        .is_none() {
        return -1;  // 没找到子进程
        // ---- stop exclusively accessing current PCB
    }
    let pair = inner.children
        .iter()
        .enumerate()
        .find(|(_, p)| {
            // ++++ temporarily access child PCB exclusively
            p.inner_exclusive_access().is_zombie() && (pid == -1 || pid as usize == p.getpid()) // 确认这个子进程是僵尸
            // ++++ stop exclusively accessing child PCB
        });
    if let Some((idx, _)) = pair {
        let child = inner.children.remove(idx);
        // confirm that child will be deallocated after removing from children list
        assert_eq!(Arc::strong_count(&child), 1);   // 确认强引用计数只有目前这一个
        let found_pid = child.getpid();
        // ++++ temporarily access child TCB exclusively
        let exit_code = child.inner_exclusive_access().exit_code;
        // ++++ stop exclusively accessing child PCB
        *translated_refmut(inner.memory_set.token(), exit_code_ptr) = exit_code;    // 填入退出状态
        found_pid as isize  // 返回找到的这个 PID
    } else {
        -2  // 要找的不是僵尸
    }
    // ---- stop exclusively accessing current PCB automatically
}

// user/src/lib.rs

pub fn wait(exit_code: &mut i32) -> isize {
    loop {
        match sys_waitpid(-1, exit_code as *mut _) {
            -2 => { yield_(); }
            // -1 or a real pid
            exit_pid => return exit_pid,
        }
    }
}