[rCore学习笔记 024]多道程序与协作式调度

写在前面

本随笔是非常菜的菜鸡写的。如有问题请及时提出。

可以联系:[email protected]

GitHhub:https://github.com/WindDevil (目前啥也没有

本节重点

主要是对 任务 的概念进行进一步扩展和延伸:形成

  • 任务运行状态:任务从开始到结束执行过程中所处的不同运行状态:未初始化、准备执行、正在执行、已退出
  • 任务控制块:管理程序的执行过程的任务上下文,控制程序的执行与暂停
  • 任务相关系统调用:应用程序和操作系统之间的接口,用于程序主动暂停 sys_yield 和主动退出 sys_exit

这里主要看具体实现,这些概念之前学习RTOS的时候使用是会使用了,但是具体怎么实现还不好说.

多道程序背景与 yield 系统调用

尽管 CPU 可以一直在跑应用了,但是其利用率仍有上升的空间.

随着应用需求的不断复杂,有的时候会在内核的监督下访问一些外设,它们也是计算机系统的另一个非常重要的组成部分,即 输入/输出 (I/O, Input/Output) .

CPU 会把 I/O 请求传递给外设,待外设处理完毕之后,CPU 便可以从外设读到其发出的 I/O 请求的处理结果.

我们暂时考虑 CPU 只能 单向地 通过读取外设提供的寄存器信息来获取外设处理 I/O 的完成状态。

多道程序的思想在于:

  1. 内核同时管理多个应用。如果外设处理 I/O 的时间足够长,那我们可以先进行任务切换去执行其他应用
  2. 在某次切换回来之后,应用再次读取设备寄存器,发现 I/O 请求已经处理完毕了,那么就可以根据返回的 I/O 结果继续向下执行了

这样的话,只要同时存在的 应用足够多 ,就能 一定程度 上隐藏 I/O 外设处理相对于 CPU 的延迟,保证 CPU 不必浪费时间在等待外设上,而是几乎一直在进行计算。

这种任务切换,是让应用 主动 调用 sys_yield 系统调用来实现的,这意味着应用主动交出 CPU 的使用权给其他应用。

这一段的描述相当是一种多任务的轮询,但是在我的脑海中, 外部中断 还是比多任务轮询要好得多的. 但是怎么合理地 利用 外部中断提高实时性,就是一个问题.

至于主动调用sys_yield就是一件很难的事情,也就是为啥叫做 协作式 , 就是系统的性能要依赖程序员在设计APP的时候释放CPU.(我自己都想拉满CPU,谁想管你死活捏)

这里提到了 一种多道程序执行的典型情况 :

这张图很好解释:

  1. 这张图的 横轴 是时间轴
  2. 这张图的 纵轴 是运行实体(任务和IO硬件)
  3. 可以看到是有三个运行实体
    1. I/O Device : 这个是IO硬件
    2. I/O Task : 这个是请求IO硬件的任务
    3. Other Task : 这个是不请求IO硬件的其它任务
  4. 可以看到最开始是 IO Task 在运行.
  5. I/O Start yield 时刻,IO Task 请求了IO硬件,然后释放了CPU.
  6. Other Task 接手CPU,同时 IO Device 继续处理硬件上的问题.
  7. 一直执行到 Not Complete yileld again 时段的开头,Other Task 执行完毕,把CPU释放.
  8. IO Task 接手之后检查IO硬件状态,仍然没有处理完毕.
  9. Not Complete yileld again 时段的结尾, IO Task 释放CPU.
  10. Other Task 再次接手CPU,同时 IO Device 继续处理硬件上的问题.
  11. Other Task 执行期间,发生了 I/O Complete 时刻,但是此时软件感知不到.
  12. Continue 时刻, ,Other Task 执行完毕,把CPU释放.
  13. IO Task 接手之后检查IO硬件状态,处理完毕,因此继续执行.

上面我们是通过“避免无谓的外设等待来提高 CPU 利用率”这一切入点来引入 sys_yield 。但其实调用 sys_yield 不一定与外设有关 。随着内核功能的逐渐复杂,我们还会遇到 其他需要等待的事件 ,我们都可以立即调用 sys_yield 来避免等待过程造成的浪费。

sys_yield 的缺点

这一部分和我最开始考虑的关于实时性问题的思考是有一定关联的.

当应用调用它主动交出 CPU 使用权之后,它下一次再被允许使用 CPU 的时间点与内核的调度策略与当前的总体应用执行情况有关,很有可能远远迟于该应用等待的事件(如外设处理完请求)达成的时间点。这就会造成该应用的响应延迟不稳定或者很长。比如,设想一下,敲击键盘之后隔了数分钟之后才能在屏幕上看到字符,这已经超出了人类所能忍受的范畴。但也请不要担心,我们后面会有更加优雅的解决方案。

sys_yield 的标准接口

思考我们之前提到的两种syscall.

内核层 实现的:

//os/syscall/mod

const SYSCALL_WRITE: usize = 64;
const SYSCALL_EXIT: usize = 93;

mod fs;
mod process;

use fs::*;
use process::*;

/// handle syscall exception with `syscall_id` and other arguments
pub fn syscall(syscall_id: usize, args: [usize; 3]) -> isize {
    match syscall_id {
        SYSCALL_WRITE => sys_write(args[0], args[1] as *const u8, args[2]),
        SYSCALL_EXIT => sys_exit(args[0] as i32),
        _ => panic!("Unsupported syscall_id: {}", syscall_id),
    }
}

用户层 实现的:

//user/syscall

use core::arch::asm;

const SYSCALL_WRITE: usize = 64;
const SYSCALL_EXIT: usize = 93;

fn syscall(id: usize, args: [usize; 3]) -> isize {
    let mut ret: isize;
    unsafe {
        asm!(
            "ecall",
            inlateout("x10") args[0] => ret,
            in("x11") args[1],
            in("x12") args[2],
            in("x17") id
        );
    }
    ret
}

pub fn sys_write(fd: usize, buffer: &[u8]) -> isize {
    syscall(SYSCALL_WRITE, [fd, buffer.as_ptr() as usize, buffer.len()])
}

pub fn sys_exit(exit_code: i32) -> isize {
    syscall(SYSCALL_EXIT, [exit_code as usize, 0, 0])
}

这里如果能理解到这里的同名的syscall,sys_write,sys_exit不是同一个函数,说明才 理解到位 .

现在要 继续实现 一个 系统调用 sys_yield.

于是要在 用户层 实现接口:

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

SYSCALL_YIELD同样是一个 需要定义 的常量.

这里有个小问题,由于yield是rust的 关键字 ,因此定义函数名字的时候 增加了一个_ .

于是在 内核层syscall里边也需要增加一个判别,现在我只写成伪代码,因为具体我也 不知道 参数怎么填写:

pub fn syscall(syscall_id: usize, args: [usize; 3]) -> isize {
    match syscall_id {
		// 这里是伪代码
	    SYSCALL_YIELD => sys_yield(...)
	    // 这里是伪代码
        SYSCALL_WRITE => sys_write(args[0], args[1] as *const u8, args[2]),
        SYSCALL_EXIT => sys_exit(args[0] as i32),
        _ => panic!("Unsupported syscall_id: {}", syscall_id),
    }
}

任务控制块与任务运行状态

思考上一章实现的AppManager,它包含了三部分:

  1. 应用的 数量 .
  2. 当前 运行应用.
  3. 应用的 入口地址 .

但是考虑当前的任务的状态,可能 不是 简单地如上图两任务的情况一样,而是存在更多的任务和更复杂的情景.

想到我们本节 开头 时候所说,要建立一个 任务运行状态 的概念,把任务归类为如下几种状态:

  1. 未初始化
  2. 准备执行
  3. 正在执行
  4. 已退出

因此可以使用rust构建这样一个结构体:

// os/src/task/task.rs

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

#[derive]这个注解有点类似于 Kotlin ,可以让 编译器自动 帮你实现一些方法:

  • 实现了 Clone Trait 之后就可以调用 clone 函数完成拷贝;
  • 实现了 PartialEq Trait 之后就可以使用 == 运算符比较该类型的两个实例,从逻辑上说只有 两个相等的应用执行状态才会被判为相等,而事实上也确实如此。
  • Copy 是一个标记 Trait,决定该类型在按值传参/赋值的时候采用移动语义还是复制语义。

回想起上一节提到的TaskContext,我们的 任务控制块 中需要保存的两部分也就知道了:

  1. TaskContext保存任务上下文
  2. TaskStatus保存任务状态

因此用rust构建这样一个结构体:

// os/src/task/task.rs

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

任务管理器

那么有了TaskControlBlock,就可以实现一个任务管理器.

任务管理器需要管理多个任务,于是就需要知道:

  1. app 总数
  2. 当前 的任务
  3. 每个任务的 控制块
    1. 任务 状态
    2. 任务 上下文

这里使用了 常量和变量分离的方法 来实现它.

// os/src/task/mod.rs

pub struct TaskManager {
    num_app: usize,
    inner: UPSafeCell<TaskManagerInner>,
}

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

这是因为num_app是常量不需要变化,而inner是变量,需要用UPSafeCell,保证其 内部可变性单核时 安全的借用能力.

这里在官方文档里提到了:

  1. 在第二章的AppManager是可以通过current_app推测上/下任务 的.
  2. 但是在TaskManger里的TaskManagerInnercurrent_task只能 感知当前任务.

TaskManager创建全局实例TASK_MANAGER,仍然使用 懒初始化 的方法:

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

这个初始化顺序是:

  1. 使用 上一节实现get_num_app来获取任务数量
  2. 创建一个TaskControlBlock数组 ,大小为 设定好的 MAX_APP_NUM.
  3. 然后通过 上一节实现的 init_app_cx 来获取每个 已经加载到内存 的任务上下文.
  4. 把所有的任务都 初始化Ready 状态.
  5. 然后用 匿名函数 的方式得到的 task 和初始化为0的current_task创建一个匿名 TaskManagerInner,随后包裹在 UPSafeCell 之中,和num_app一起创建一个TaskManager,传给TASK_MANAGER.

实现 sys_yield 和 sys_exit 系统调用

类似于上一章实现的 内核层syscall函数中会根据 函数代码 调用函数.

我们需要理解到的一点就是:

  1. 应用层syscall 函数只是使用 ecall 触发Trap.
  2. 内核层syscall函数才是真的具体实现.

我们现在讲的是 内核层具体实现 调用的函数,其作用是在syscall中作为一个 分支 :

// os/src/syscall/process.rs

use crate::task::suspend_current_and_run_next;

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

这个是sys_yield,用于暂停当前的应用并切换到下个应用.

看它的具体实现实际上是 抽象化suspend_current_and_run_next接口,使得接口名称 一致 .

这时候要考虑我们上一章实现的sys_exit:

//! App management syscalls
use crate::loader::run_next_app;
use crate::println;

/// task exits and submit an exit code
pub fn sys_exit(exit_code: i32) -> ! {
    println!("[kernel] Application exited with code {}", exit_code);
    run_next_app()
}

打印了LOG之后,使用run_next_app切换到下一个APP.

那么考虑到现在run_next_app已经不适合于当前的有 任务调度 的系统,所以也要对sys_exit的具体实现进行修改.

// os/src/syscall/process.rs

use crate::task::exit_current_and_run_next;

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_and_run_next接口,使得接口名称 一致 .

接下来我们只需要 具体实现 ,刚刚提到的两个接口就行了:

// os/src/task/mod.rs

pub fn suspend_current_and_run_next() {
    mark_current_suspended();
    run_next_task();
}

pub fn exit_current_and_run_next() {
    mark_current_exited();
    run_next_task();
}

这里摘抄出具体实现,但是具体实现中还是有三个函数 有待实现 :

  1. mark_current_suspended
  2. mark_current_exited
  3. run_next_task

他们的具体实现要和上一章和上一节的实现对比:

  1. 上一章: 加载应用 然后 修改程序指针 直接开始运行 .
  2. 上一节:直接 修改程序指针 直接开始运行.

这一章的实现是不同的,是通过 修改用户的状态 ,解决.

// os/src/task/mod.rs

fn mark_current_suspended() {
    TASK_MANAGER.mark_current_suspended();
}

fn mark_current_exited() {
    TASK_MANAGER.mark_current_exited();
}

impl TaskManager {
    fn mark_current_suspended(&self) {
        let mut inner = self.inner.borrow_mut();
        let current = inner.current_task;
        inner.tasks[current].task_status = TaskStatus::Ready;
    }

    fn mark_current_exited(&self) {
        let mut inner = self.inner.borrow_mut();
        let current = inner.current_task;
        inner.tasks[current].task_status = TaskStatus::Exited;
    }
}

然后再通过run_next_task来(根据状态) 决定(可以叫调度吗?对的...不对...对的对的...不对) 下一步要运行哪个Task.

// os/src/task/mod.rs

fn run_next_task() {
    TASK_MANAGER.run_next_task();
}

impl TaskManager {
    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 {
            panic!("All applications completed!");
        }
    }
}

这里也是分为两部分:

  1. run_next_task是对TASK_MANAGER.run_next_task();的封装.
  2. TaskManager结构体的run_next_task方法的实现.
    1. 首先就是if let这种模式匹配写法,最开始没有掌握rust的开发技术,因此不懂.
      1. 这时候查阅Rust圣经.关于if let的部分.
        1. 当只需要进行一次匹配的时候就可以使用这个方法.
        2. 使用匹配是为了解决用简单的 == 不能解决 复杂类型 匹配的情况.
        3. 使用if let而不是match是为了解决只有None和非None两种情况的简单写法.
      2. 查阅Rust圣经.关于Some的部分.
        1. Option枚举有两种可能
          1. Some代表有值,Some包裹的内容就是它的值
            1. 一个在 定义 枚举类型的时候是 Some(T),T代表的是类型.Some(i32)就代表可以存储i32类型的值.
            2. 在实例的时候Some(T)可以被实例化Some(3),就代表这个值存在且值为3.
          2. None代表没值
      3. 因此这一段的结果意思是:
        1. 如果self.find_next_task()的结果不是None,那么对应的返回值应该是Some(next).
        2. 下面的逻辑里的next就是返回的Some()里包裹的next.代表 下一个任务的任务号 .
    2. 随后获取TaskManager.inner的单线程可变借用.
    3. 从上一步的结果中获取 当前任务.
    4. 下一个任务 的状态改为 运行中 .
    5. 把当前任务号改为 刚刚获取到的下一个任务号 .
    6. 分别获取 当前和下一个 任务上下文.
    7. 主动释放获取到的TaskManager.inner.
      1. 因为如果不去主动释放要等函数运行结束才能继续访问这个TaskManager.inner里的内容.
      2. __switch需要操作TaskManager.inner里的task.task_cx的内容.
    8. 使用 上一节实现的 __switch 完成任务栈切换,如果已经忘了可以回去看看.

可以看到find_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
            })
    }
}

它在获取TaskManager.inner的单线程可变借用之后对current_task为开头( 不包含它本身 )把整个数组看成一个 环形队列 然后逐个去 查询状态 , 直到找到 第一个 状态为准备的任务.

这里关于Rust语言,每次我们遇到不会了的,不是光把它搞懂,还要把它上一层的偏概念性的东西搞懂.

这里用到的就是 闭包迭代器 的知识:

  1. 迭代器跟 for 循环颇为相似,都是去遍历一个集合,但是实际上它们存在不小的差别,其中最主要的差别就是:是否通过索引来访问集合
    1. Iterator Trait 的 map 方法: Rust中的迭代器(Iterator)有一个map方法,它接收一个闭包(closure),并将迭代器中的每个元素传递给这个闭包。map方法会生成一个新的迭代器,其中的元素是闭包返回的结果。
    2. 迭代器有一个find方法,它接收一个闭包作为参数。该闭包定义了要查找的条件,当迭代器中的元素满足这个条件时,find方法就会返回一个Option类型的结果,其中包含找到的第一个匹配项或者None如果没有任何元素满足条件。
  2. 闭包一种匿名函数,它可以赋值给变量也可以作为参数传递给其它函数,不同于函数的是,它允许捕获调用者作用域中的值.
    1. 有点像是某种C里的 函数宏 ,用 do...while封装起来的这种.因此可以偷取别的作用域的变量来用.

这张图太好了:

第一次进入用户态

回想上一章,我们使用run_next_app调用了__restore调用sret回到用户态.

目前我们要第一次进入用户态应该也需要sret才可以.

但是思考一下上一章我们学到的__switch的实现,显然它是 不改变 特权级的.

因此第一次进入用户态还是要依赖__restore.

为了使用__restore则需要构建Trap上下文,把 上一节 实现的init_app_cx,移动到loader.rs:

// os/src/loader.rs

pub fn init_app_cx(app_id: usize) -> usize {
    KERNEL_STACK[app_id].push_context(
        TrapContext::app_init_context(get_base_i(app_id), USER_STACK[app_id].get_sp()),
    )
}

再给TaskContext构造一个 构建第一次执行任务的上下文 的方法:

// os/src/task/context.rs

impl TaskContext {
    pub fn goto_restore(kstack_ptr: usize) -> Self {
        extern "C" { fn __restore(); }
        Self {
            ra: __restore as usize,
            sp: kstack_ptr,
            s: [0; 12],
        }
    }
}

在这个操作之中,

  1. 传入了一个 内核栈指针 .
  2. 使用如下内容构建一个 TaskContext.
    1. 内核栈指针作为 任务上下文的栈指针 .
    2. __restore的函数地址作为 函数调用完毕返回地址 .也就是说 __switchret执行完毕之后执行__restore.
    3. 空的s0~s12.

需要注意的是, __restore 的实现需要做出变化:它 不再需要 在开头 mv sp, a0 了。因为在 __switch 之后,sp 就已经正确指向了我们需要的 Trap 上下文地址。

然后在创建 TaskManager 的全局实例 TASK_MANAGER 的时候为 每个任务上下文 , 初始化为由如下内容组成的TaskContext:

  1. 链接进去 的任务内存位置决定的 每个任务的内核栈指针 作为栈指针.
  2. __restore作为 函数调用完毕返回地址 .
  3. 空的s0~s12.

TaskContext构建一个 执行第一个任务 的方法:

impl TaskManager {
    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!");
    }

这段代码可以这样理解:

  1. 获取 单线程的借用 .
  2. 获取第一个 任务块的指针 .
  3. 随后把这个任务设置为 运行状态 .
  4. 获取这个任务的 上下文 .
  5. 由于后续要使用__switch因此需要 主动释放 这个借用.
  6. 使用__switch调用
    1. zero_init构建的一个 全空 的上下文.
    2. 第一个任务 的上下文.

这时候这个执行顺序有点乱了,我尝试画一个流程图.

首先是这章实现的结构体TaskManager的结构:

初始化 的流程为:

初始化后的TASK_MANAGER:

调用run_fist_app之后发生了什么:

这时候考虑APP发生挂起的时候会发生什么:

热门相关:闪婚总裁很惧内   全民女神之重生腹黑千金   一级BOSS:你结婚,我劫婚   恶魔总裁霸道宠:老婆,太惹火   99次出墙:老公,情难自禁