多道程序与分时多任务--rCore[3]

原 作者 高鹏 | 发表于 | 分类于 2021级

概念

  • 协作式操作系统

计算机硬件在快速发展，内存容量在逐渐增大，处理器的速度也在增加，外设 I/O 性能方面的进展不大。于是就想到，让应用在执行 I/O 操作或空闲时，可以主动 释放处理器 ，让其他应用继续执行。

  • 抢占式操作系统

在应用程序员的脑海里，整个计算机就应该是为他们自己的应用准备的，不用考虑其他程序的运行。这导致应用程序员在编写程序时，无法做到在程序的合适位置放置 放弃处理器的系统调用请求 ，这样系统的整体利用率还是无法提高。
所以，站在系统的层面，还是需要有一种办法能强制打断应用程序的执行。

把一个程序的一次完整执行过程称为一次 任务 (Task)，把一个程序在一个时间片（Time Slice）上占用处理器执行的过程称为一个 任务片 (Task Slice)。操作系统对不同程序的执行过程中的 任务片 进行调度和管理，即通过平衡各个程序在整个时间段上的任务片数量，就能达到一定程度的系统公平和高效的系统效率。

总体结构

多道程序操作系统 - Multiprog OS的总体结构：
1

通过上图，大致可以看出Qemu把包含多个app的列表和MultiprogOS的image镜像加载到内存中，RustSBI（bootloader）完成基本的硬件初始化后，跳转到MultiprogOS起始位置，MultiprogOS首先进行正常运行前的初始化工作，即建立栈空间和清零bss段，然后通过改进的 AppManager 内核模块从app列表中把所有app都加载到内存中，并按指定顺序让app在用户态一个接一个地执行。app在执行过程中，会通过系统调用的方式得到MultiprogOS提供的OS服务，如输出字符串等。

协作式多道程序操作系统 – CoopOS的总体结构：
2

CoopOS进一步改进了 AppManager 内核模块，把它拆分为负责加载应用的 Loader 内核模块和管理应用运行过程的 TaskManager 内核模块。
TaskManager 通过 task 任务控制块来管理应用程序的执行过程，支持应用程序主动放弃 CPU 并切换到另一个应用继续执行，从而提高系统整体执行效率。应用程序在运行时有自己所在的内存空间和栈，确保被切换时相关信息不会被其他应用破坏。如果当前应用程序正在运行，则该应用对应的任务处于运行（Running）状态；如果该应用主动放弃处理器，则该应用对应的任务处于就绪（Ready）状态。操作系统进行任务切换时，需要把要暂停任务的上下文（即任务用到的通用寄存器）保存起来，把要继续执行的任务的上下文恢复为暂停前的内容，这样就能让不同的应用协同使用处理器了。

分时多任务操作系统 – TimesharingOS的总体结构：
3

TimesharingOS最大的变化是改进了 Trap_handler 内核模块，支持时钟中断，从而可以抢占应用的执行。并通过进一步改进 TaskManager 内核模块，提供任务调度功能，这样可以在收到时钟中断后统计任务的使用时间片，如果任务的时间片用完后，则切换任务。从而可以公平和高效地分时执行多个应用，提高系统的整体效率。

多道程序放置与加载

  • 多道程序放置
    多个应用同时放在内存中，所以他们的起始地址是不同的，且地址范围不能重叠
    由于每个应用被加载到的位置都不同，也就导致它们的链接脚本 linker.ld 中的 BASE_ADDRESS 都是不同的。不用直接 cargo build 构建应用的链接脚本，而是写一个脚本定制工具 build.py ，为每个应用定制了各自的链接脚本。
  • 多道程序加载
    所有的应用在内核初始化的时候就一并被加载到内存中。为了避免覆盖，它们自然需要被加载到不同的物理地址。这是通过调用 loader 子模块的 load_apps 函数实现的

任务切换

为了提高效率，我们需要引入新的操作系统概念 任务 、 任务切换 、任务上下文 。
任务切换支持的场景是：一个应用在运行途中便会主动或被动交出 CPU 的使用权，此时它只能暂停执行，等到内核重新给它分配处理器资源之后才能恢复并继续执行

  • __switch 函数
    调用 __switch 之后直到它返回前的这段时间，原 Trap 控制流 A 会先被暂停并被切换出去， CPU 转而运行另一个应用在内核中的 Trap 控制流 B 。然后在某个合适的时机，原 Trap 控制流 A 才会从某一条 Trap 控制流 C 切换回来继续执行并最终返回。
    _switch 函数和一个普通的函数之间的核心差别仅仅是它会 换栈

(当前正在执行的任务的 Trap 控制流，我们用一个名为 current_task_cx_ptr 的变量来保存放置当前任务上下文的地址；而用 next_task_cx_ptr 的变量来保存放置下一个要执行任务的上下文的地址。)
4

多道程序与协作式调度

任务运行状态：任务从开始到结束执行过程中所处的不同运行状态：未初始化、准备执行、正在执行、已退出

任务控制块：管理程序的执行过程的任务上下文，控制程序的执行与暂停

任务相关系统调用：应用程序和操作系统直接的接口，用于程序主动暂停 sys_yield 和主动退出 sys_exit。
sys_yield 表示应用自己暂时放弃对CPU的当前使用权，进入 Ready 状态。
sys_exit 表示应用退出执行。

  • 任务运行状态、任务控制块
    在一段时间内，内核需要管理多个未完成的应用，而且我们不能对应用完成的顺序做任何假定，并不是先加入的应用就一定会先完成。必须在内核中对每个应用分别维护它的运行状态。
    任务控制块非常重要，它是内核管理应用的核心数据结构。
// os/src/task/task.rs

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

// 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,
}

运行状态变化图：
5

分时多任务系统与抢占式调度

  • 分时多任务：操作系统管理每个应用程序，以时间片为单位来分时占用处理器运行应用。
  • 时间片轮转调度：操作系统在一个程序用完其时间片后，就抢占当前程序并调用下一个程序执行，周而复始，形成对应用程序在任务级别上的时间片轮转调度。维护一个任务队列，每次从队头取出一个应用执行一个时间片，然后把它丢到队尾，再继续从队头取出一个应用，以此类推直到所有的应用执行完毕。
  • 时钟中断与计时器
    操作系统的计时功能是依靠硬件提供的时钟中断来实现的。
    在 RISC-V 64 架构上，该计数器保存在一个 64 位的 CSR mtime 中，我们无需担心它的溢出问题，在内核运行全程可以认为它是一直递增的。
    一旦计数器 mtime 的值超过了 mtimecmp，就会触发一次时钟中断。

计时器的控制：

// os/src/timer.rs

use riscv::register::time;

pub fn get_time() -> usize {
   
    time::read()
}
  • 抢占式调度
// os/src/trap/mod.rs

match scause.cause() {
   
    Trap::Interrupt(Interrupt::SupervisorTimer) => {
   
        set_next_trigger();
        suspend_current_and_run_next();
    }
}

trap_handler 函数下新增一个条件分支跳转，当发现触发了一个 S 特权级时钟中断的时候，首先重新设置一个 10ms 的计时器，然后调用上一小节提到的 suspend_current_and_run_next 函数暂停当前应用并切换到下一个。

参考：rCore-Tutorial文档