Introduction

介绍了“锯齿螈”操作系统,“始初龙”操作系统和“腔骨龙”操作系统"。

“锯齿螈”初级多道程序操作系统:多道程序的放置和加载

在上一章中,用户程序的镜像被放到了内核 ELF 的 .data 段,并且保存了各镜像的起始地址和结束地址,需要加载程序时将这部分数据复制到 0x8040000 中然后执行。

现在每个程序运行时的位置都不同,也就是链接脚本中的起始地址各不相同,rCore 提供了一个脚本用于生成起始地址不同的链接脚本

# user/build.py
 import os

 base_address = 0x80400000
 step = 0x20000
 linker = 'src/linker.ld'

 app_id = 0
 apps = os.listdir('src/bin')
 apps.sort()
 for app in apps:
     app = app[:app.find('.')]
     lines = []
     lines_before = []
     with open(linker, 'r') as f:
         for line in f.readlines():
             lines_before.append(line)
             line = line.replace(hex(base_address), hex(base_address+step*app_id))
             lines.append(line)
     with open(linker, 'w+') as f:
         f.writelines(lines)
     os.system('cargo build --bin %s --release' % app)
     print('[build.py] application %s start with address %s' %(app, hex(base_address+step*app_id)))
     with open(linker, 'w+') as f:
         f.writelines(lines_before)
     app_id = app_id + 1

这个脚本会替换链接脚本中的 base_address ,然后编译 rust 程序,再恢复原本的 base_address

sodium@nas-MacBook-Air-13 user % python3 build.py
    Finished `release` profile [optimized + debuginfo] target(s) in 0.00s
[build.py] application 00power_3 start with address 0x80400000
    Finished `release` profile [optimized + debuginfo] target(s) in 0.00s
[build.py] application 01power_5 start with address 0x80420000
    Finished `release` profile [optimized + debuginfo] target(s) in 0.00s
[build.py] application 02power_7 start with address 0x80440000
    Finished `release` profile [optimized + debuginfo] target(s) in 0.00s
[build.py] application 03sleep start with address 0x80460000

在运行内核时,再将这些镜像加载到对应的位置上即可

// os/src/loader.rs
pub fn load_apps() {
    unsafe extern "C" {
        safe fn _num_app();         // link_app.S, 存储了程序镜像位置
    }
    let num_app_ptr = linker_symbol_addr!(_num_app) as *const usize;
    let num_app = get_num_app();    // 读取 link_app.S 获得程序数量
    let app_start = unsafe { core::slice::from_raw_parts(num_app_ptr.add(1), num_app + 1) };
    // load apps
    for i in 0..num_app {
        let base_i = get_base_i(i); // 获得第 i 个 APP 的起始地址
        // clear region
        (base_i..base_i + APP_SIZE_LIMIT)
            .for_each(|addr| unsafe { (addr as *mut u8).write_volatile(0) });
        // load app from data section to memory
        let src = unsafe {
            core::slice::from_raw_parts(app_start[i] as *const u8, app_start[i + 1] - app_start[i])
        };
        let dst = unsafe { core::slice::from_raw_parts_mut(base_i as *mut u8, src.len()) };
        dst.copy_from_slice(src);
    }
    unsafe {
        asm!("fence.i");
    }
}

执行应用程序的过程和上一章类似,在执行第一个程序之前,设置好上下文、sepc 等然后调用 sret,进程结束时进入系统调用 exit(),然后执行下一个进程。

这就是“锯齿螈”初级多道程序操作系统。

“始初龙”操作系统

实现任务切换

原本的程序是运行完再自行退出或者出错被迫退出,这给了程序太多权限,而且降低了运行的效率。任务切换需要实现两点:

  1. 程序可以主动让出 CPU
  2. 程序在某些情况下能够被动让出 CPU

应用程序的一次执行过程(也是一段控制流)称为一个 任务 ,应用执行过程中的一个时间片段上的执行片段或空闲片段称为 “ 计算任务片 ” 或“ 空闲任务片 ”

在任务切换的过程中,必须保存一些资源,用于恢复执行,需要保存与恢复的资源被称为 任务上下文 (Task Context)。

两种上下文:

  1. 函数调用上下文:由编译器完成,分为调用者保存寄存器和被调用者保存寄存器,栈始终固定,只需要提前设置好,不涉及特权级切换。
  2. 系统调用上下文:需要使用特权级切换,必须保存几乎所有寄存器,栈地址使用不同的栈。

这里的任务切换和 xv6 的 switch.S 是一样的,由于函数调用的过程中编译器会自己把调用者寄存器保存到自己的栈中,因此 switch.S 只需要保存被调用者寄存器s0,..,s11、返回地址 ra 和栈指针 sp 以及切换栈即可

  1. 与 Trap 切换不同,它不涉及特权级切换
  2. 与 Trap 切换不同,它的一部分是由编译器帮忙完成的
  3. 与 Trap 切换相同,它对应用是透明的
# os/src/task/switch.S

.altmacro
.macro SAVE_SN n
    sd s\n, (\n+2)*8(a0)
.endm
.macro LOAD_SN n
    ld s\n, (\n+2)*8(a1)
.endm
    .section .text
    .globl __switch
__switch:
    # 阶段 [1]
    # __switch(
    #     current_task_cx_ptr: *mut TaskContext,
    #     next_task_cx_ptr: *const TaskContext
    # )
    # 阶段 [2]
    # save kernel stack of current task
    sd sp, 8(a0)
    # save ra & s0~s11 of current execution
    sd ra, 0(a0)
    .set n, 0
    .rept 12
        SAVE_SN %n
        .set n, n + 1
    .endr
    # 阶段 [3]
    # restore ra & s0~s11 of next execution
    ld ra, 0(a1)
    .set n, 0
    .rept 12
        LOAD_SN %n
        .set n, n + 1
    .endr
    # restore kernel stack of next task
    ld sp, 8(a1)
    # 阶段 [4]
    ret

根据 C ABI,a0 是 current_task_cx_ptr,而 a1 是 next_task_cx_ptr。这里做的事情只有保存 ra, sp, s0~s11 寄存器

pub struct TaskContext {
    ra: usize,
    sp: usize,
    /// callee saved registers:  s 0..11
    s: [usize; 12],
}

任务管理器

协作式调度在这里指的是一个应用会持续运行下去,直到它主动调用 sys_yield 系统调用来交出 CPU 使用权,这要求程序必须遵守规则来提高利用率。

/// 功能:应用主动交出 CPU 所有权并切换到其他应用。
/// 返回值:总是返回 0。
/// syscall ID:124
fn sys_yield() -> isize;
// user/src/syscall.rs

pub fn sys_yield() -> isize {
    syscall(SYSCALL_YIELD, [0, 0, 0])
}

// user/src/lib.rs

pub fn yield_() -> isize { sys_yield() }    // yield 是 Rust 的关键字

应用让出 CPU 所有权之后,怎么知道下一个应用应该选择哪个?这需要引入应用的运行状态。

// os/src/task/task.rs

#[derive(Copy, Clone, PartialEq)]
pub enum TaskStatus {
    UnInit, // 未初始化
    Ready, // 准备运行
    Running, // 正在运行
    Exited, // 已退出
}

Ready 的应用可以随时运行,除此之外,加上上下文信息可以构成一个任务控制块

// os/src/task/task.rs

#[derive(Copy, Clone)]
pub struct TaskControlBlock {
    pub task_status: TaskStatus,
    pub task_cx: TaskContext,
}

再加上一个任务管理器管理这些控制块

// os/src/task/mod.rs
pub struct TaskManager {
    num_app: usize,                         // 常量
    inner: UPSafeCell<TaskManagerInner>,    // 变量
}

struct TaskManagerInner {
    tasks: [TaskControlBlock; MAX_APP_NUM],
    current_task: usize,
}

类似于之前的 AppManager 实例化的方式

// os/src/task/mod.rs
lazy_static! {
    pub static ref TASK_MANAGER: TaskManager = {
        let num_app = get_num_app();
        let mut tasks = [
            TaskControlBlock {
                task_cx: TaskContext::zero_init(),
                task_status: TaskStatus::UnInit
            };
            MAX_APP_NUM
        ];
        for i in 0..num_app {
            tasks[i].task_cx = TaskContext::goto_restore(init_app_cx(i));
            tasks[i].task_status = TaskStatus::Ready;
        }
        TaskManager {
            num_app,
            inner: unsafe { UPSafeCell::new(TaskManagerInner {
                tasks,
                current_task: 0,
            })},
        }
    };
}

sys_yield 和 sys_exit

yield 会放弃 CPU,进入 ready 状态

// os/src/syscall/process.rs
use crate::task::suspend_current_and_run_next;
pub fn sys_yield() -> isize {
    suspend_current_and_run_next();
    0
}
// os/src/task/mod.rs
/// suspend current task, then run next task
pub fn suspend_current_and_run_next() {
    mark_current_suspended();
    run_next_task();
}

/// suspend current task
fn mark_current_suspended() {
    TASK_MANAGER.mark_current_suspended();
}

/// rust next task
fn run_next_task() {
    TASK_MANAGER.run_next_task();
}
// os/src/task/mod.rs
impl TaskManager {
    fn find_next_task(&self) -> Option<usize> {
        let inner = self.inner.exclusive_access();
        let current = inner.current_task;
        (current + 1..current + self.num_app + 1)
            .map(|id| id % self.num_app)
            .find(|id| inner.tasks[*id].task_status == TaskStatus::Ready)
    }
    ...
    /// Change the status of current `Running` task into `Ready`.
    fn mark_current_suspended(&self) {
        let mut inner = self.inner.exclusive_access();
        let current = inner.current_task;
        inner.tasks[current].task_status = TaskStatus::Ready;
    }
    ...
    fn run_next_task(&self) {
        if let Some(next) = self.find_next_task() {
            let mut inner = self.inner.exclusive_access();
            let current = inner.current_task;
            inner.tasks[next].task_status = TaskStatus::Running;
            inner.current_task = next;
            let current_task_cx_ptr = &mut inner.tasks[current].task_cx as *mut TaskContext;
            let next_task_cx_ptr = &inner.tasks[next].task_cx as *const TaskContext;
            drop(inner);
            // before this, we should drop local variables that must be dropped manually
            unsafe {
                __switch(current_task_cx_ptr, next_task_cx_ptr);
            }
            // go back to user mode
        } else {
            println!("All applications completed!");
            shutdown(false);
        }
    }
}

这里调用 __switch 之后,如果下一个任务是第一次执行,那么返回的地址是初始化时设定的 __restore ,然后回到用户程序;或者下一个任务是之前放弃过 CPU 的,那么返回的地址应该是调用 run_next_task 的地方,也就是最终会从 sys_yield, trap_handler 最终经过 __restore 返用户程序,这一点和 xv6 是类似的。

这里的 run_next_task 和 find_next_task() 类似于 xv6 的 scheduler(),都是从列表中找到下一个可运行的任务。

类似的 exit 只是将原本的 Ready 变成了 Exited

pub fn sys_exit(exit_code: i32) -> ! {
    println!("[kernel] Application exited with code {}", exit_code);
    exit_current_and_run_next();
    panic!("Unreachable in sys_exit!");
}
/// exit current task,  then run next task
pub fn exit_current_and_run_next() {
    mark_current_exited();
    run_next_task();
}
/// exit current task
fn mark_current_exited() {
    TASK_MANAGER.mark_current_exited();
}
// os/src/task/mod.rs
impl TaskManager {
    ...
    /// Change the status of current `Running` task into `Exited`.
    fn mark_current_exited(&self) {
        let mut inner = self.inner.exclusive_access();
        let current = inner.current_task;
        inner.tasks[current].task_status = TaskStatus::Exited;
    }
    ...
}

运行第一个用户程序

内核启动时,需要运行第一个用户程序,调用过程如下

#[unsafe(no_mangle)]
pub fn rust_main() -> ! {
    clear_bss();
    logging::init();
    info!("[kernel] Hello, world!");
    trap::init();
    loader::load_apps();
    task::run_first_task();
    panic!("Unreachable in rust_main!");
}
/// run first task
pub fn run_first_task() {
    TASK_MANAGER.run_first_task();
}

impl TaskManager {
    /// Run the first task in task list.
    ///
    /// Generally, the first task in task list is an idle task (we call it zero process later).
    /// But in ch3, we load apps statically, so the first task is a real app.
    fn run_first_task(&self) -> ! {
        let mut inner = self.inner.exclusive_access();
        let task0 = &mut inner.tasks[0];
        task0.task_status = TaskStatus::Running;
        let next_task_cx_ptr = &task0.task_cx as *const TaskContext;
        drop(inner);
        let mut _unused = TaskContext::zero_init();
        // before this, we should drop local variables that must be dropped manually
        unsafe {
            __switch(&mut _unused as *mut TaskContext, next_task_cx_ptr);
        }
        panic!("unreachable in run_first_task!");
    }
    ...
}

这里的 _unused 是一个全为 0 的上下文。但是这个上下文没有什么用,只是为了避免覆盖有用的数据。

“腔骨龙”抢占式操作系统

在“始初龙”操作系统中,需要靠程序自觉让出资源才能实现高效调度切换,现在需要让程序强制放弃 CPU, 完成:

  1. 分时多任务:操作系统管理每个应用程序,以时间片为单位来分时占用处理器运行应用。
  2. 时间片轮转调度:操作系统在一个程序用完其时间片后,就抢占当前程序并调用下一个程序执行,周而复始,形成对应用程序在任务级别上的时间片轮转调度。

RISCV 计时器中断

隔一段时间,计时器就会发生中断,此时就可以进行任务的切换

InterruptException CodeDescription
11Supervisor software interrupt
13Machine software interrupt
15Supervisor timer interrupt
17Machine timer interrupt
19Supervisor external interrupt
111Machine external interrupt

RISC-V 的中断可以分成三类:

  • 软件中断 (Software Interrupt):由软件控制发出的中断
  • 时钟中断 (Timer Interrupt):由时钟电路发出的中断
  • 外部中断 (External Interrupt):由外设发出的中断

在判断中断是否会被屏蔽的时候,有以下规则:

  1. 如果中断的特权级低于 CPU 当前的特权级,则该中断会被屏蔽,不会被处理;
  2. 如果中断的特权级高于与 CPU 当前的特权级或相同,则需要通过相应的 CSR 判断该中断是否会被屏蔽。

S 特权级相关的 CSR 有

  1. sstatus,其中如果 sstatus.sie 置0,那么所有的 S 特权级中断都会关闭
  2. sie,三个字段 ssie/stie/seie 分别控制 S 特权级的软件中断、时钟中断和外部中断的中断使能,在 sstatus.sie 为 1 时有效。
  3. 只有 CPU 特权级不高于 S 特权级并且 sie 中相关字段为 1 , 中断才不会被屏蔽。

默认情况下,所有的中断都需要到 M 特权级处理。而通过软件设置这些中断代理 CSR 之后,就可以到低特权级处理,但是 Trap 到的特权级不能低于中断的特权级

中断产生后,硬件会完成如下事务:

  1. 当中断发生时,sstatus.sie 字段会被保存在 sstatus.spie 字段中,同时把 sstatus.sie 字段置零,这样软件在进行后续的中断处理过程中,所有 S 特权级的中断都会被屏蔽;
  2. 当软件执行中断处理完毕后,会执行 sret 指令返回到被中断打断的地方继续执行,硬件会把 sstatus.sie 字段恢复为 sstatus.spie 字段内的值。
  3. 也就是说,如果不去手动设置 sstatus CSR ,在只考虑 S 特权级中断的情况下,是不会出现 嵌套中断 (Nested Interrupt) 的。

但是如果发生更高级别的中断,嵌套中断会不可避免地发生。

通过 riscv 库,rCore 可以直接调用接口访问计数器的值

// os/src/timer.rs
use riscv::register::time;
pub fn get_time() -> usize {
    time::read()
}

每次计时器中断发生时,内核需要设置下一次中断发生的时间

// os/src/sbi.rs
const SBI_SET_TIMER: usize = 0;
pub fn set_timer(timer: usize) {
    sbi_call(SBI_SET_TIMER, timer, 0, 0);
}

// os/src/timer.rs
use crate::config::CLOCK_FREQ;
const TICKS_PER_SEC: usize = 100;
pub fn set_next_trigger() {
    set_timer(get_time() + CLOCK_FREQ / TICKS_PER_SEC);
}

除此之外,应用可能有计时需求,所以再封装一个函数

// os/src/timer.rs
const MICRO_PER_SEC: usize = 1_000_000;
pub fn get_time_us() -> usize {
    time::read() / (CLOCK_FREQ / MICRO_PER_SEC)
}

并且新增一个系统调用

/// 功能:获取当前的时间,保存在 TimeVal 结构体 ts 中,_tz 在我们的实现中忽略
/// 返回值:返回是否执行成功,成功则返回 0
/// syscall ID:169
fn sys_get_time(ts: *mut TimeVal, _tz: usize) -> isize;
#[repr(C)]
pub struct TimeVal {
    pub sec: usize,
    pub usec: usize,
}

抢占式调度

有了计时器中断,只需要在 trap_handler 中识别出这个中断然后进行相应操作即可

// os/src/trap/mod.rs

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();
    }
}

计时器同样需要初始化

// os/src/main.rs

#[unsafe(no_mangle)]
pub fn rust_main() -> ! {
    clear_bss();
    println!("[kernel] Hello, world!");
    trap::init();
    loader::load_apps();
    trap::enable_timer_interrupt(); // 设置了 sie.stie 使得 S 特权级时钟中断不会被屏蔽
    timer::set_next_trigger();      // 设置第一个 10ms 的计时器
    task::run_first_task();
    panic!("Unreachable in rust_main!");
}

// os/src/trap/mod.rs

use riscv::register::sie;

pub fn enable_timer_interrupt() {
    unsafe { sie::set_stimer(); }
}

虽然返回用户态时,spie 并没有手动恢复,但是因为 U-Mode 级别低于 S-Mode,CPU 在 U 态接收到一个 S 态时钟中断时会被抢占,这时无论 SIE 位是否被设置都会进入 Trap 处理流程。

和 xv6 进行对比的话,xv6 在 M 态的时候就对计时器进行了初始化,设置对应的 mtvec 入口,每当计时器中断发生时,进入 timervec 设置下一次计时器中断,然后通过软件中断的方式进入到 S-Mode 的 usertrap 中,通过 devintr 函数识别出来。这部分在 HITSZ 的 OS Lab4 中有进行一些分析:

CLINT

下面是一个使用 yield_ 替代原本轮询的用户程序。

// user/src/bin/03sleep.rs

#[unsafe(no_mangle)]
fn main() -> i32 {
    let current_timer = get_time();
    let wait_for = current_timer + 3000;
    while get_time() < wait_for {
        yield_();
    }
    println!("Test sleep OK!");
    0
}