[rCore学习笔记 025]分时多任务系统与抢占式调度
写在前面
本随笔是非常菜的菜鸡写的。如有问题请及时提出。
可以联系：1160712160@qq.com
GitHhub：
https://github.com/WindDevil
（目前啥也没有
本节重点
本章最开始的时候讲解了有类似于多道程序与协作式调度的区别.
回想上一节,我们提到的,如果我们仍然是不使用上一节实现的
yeild
,仍然和上上节(多道程序加载)的实现效果是一样的.
因为如果我们不主动释放CPU,任务仍然是顺序执行的.
那么并不是所有的程序员都会在写程序的时候考虑到别人.比如写单片机的代码,我使用
IIC
通信,我就嗯等
ACK
信号,我宁愿
while()
也不愿意放弃CPU给你.
这时候使用抢占式调度就非常有必要了.
官方文档
有云:我们需要对
任务
的概念进行进一步扩展和延伸,
- 分时多任务：操作系统管理每个应用程序，以时间片为单位来分时占用处理器运行应用。
- 时间片轮转调度：操作系统在一个程序用完其时间片后，就抢占当前程序并调用下一个程序执行，周而复始，形成对应用程序在任务级别上的时间片轮转调度。
文档中还有一些概念:
- 而随着技术的发展，涌现了越来越多的
交互式应用
(Interactive Application) ，它们要达成的一个重要目标就是提高用户（应用的使用者和开发者）操作的响应速度，减少
延迟
（Latency），这样才能优化应用的使用体验和开发体验。对于这些应用而言，即使需要等待外设或某些事件，它们也不会倾向于主动 yield 交出 CPU 使用权，因为这样可能会带来无法接受的延迟。 - 抢占式调度
(Preemptive Scheduling) 则是应用
随时
都有被内核切换出去的可能。
现代的任务调度算法基本都是抢占式的，它要求每个应用只能连续执行一段时间，然后内核就会将它强制性切换出去。一般将
时间片
(Time Slice) 作为应用连续执行时长的度量单位，每个时间片可能在毫秒量级。
调度算法需要考虑：每次在换出之前给一个应用多少时间片去执行，以及要换入哪个应用。可以从性能（主要是吞吐量和延迟两个指标）和
公平性
(Fairness) 两个维度来评价调度算法，后者要求多个应用分到的时间片占比不应差距过大。
这里插一句,这时候往往就想到写
RT-Thread
的时候给每个应用添加一个
500ms
时的纠结.(当然现在想到
RT-Thread
似乎应该有更先进的调度算法,我心里悬着的石头就放下了).
这时候就提到
调度算法
的重要性了(怪不得这个专门有一个岗位).
时间片轮转调度
在这个项目中,使用的调度算法就是
时间片轮转算法
(RR, Round-Robin) .
本章中我们仅需要最原始的 RR 算法，用文字描述的话就是维护一个任务队列，每次从队头取出一个应用执行一个时间片，然后把它丢到队尾，再继续从队头取出一个应用，以此类推直到所有的应用执行完毕。
时间片的实现
时间片我们在本章开始的时候猜想它是用定时器加中断实现的,目前看来也确实如此.
risc-v的中断
官方文档
对中断的解析是这样的,很深刻,尤其是提到了同步和异步的概念:
在 RISC-V 架构语境下，
中断
(Interrupt) 和我们第二章中介绍的异常（包括程序错误导致或执行 Trap 类指令如用于系统调用的
ecall
）一样都是一种 Trap ，但是它们被触发的原因却是不同的。对于某个处理器核而言， 异常与当前 CPU 的指令执行是
同步
(Synchronous) 的，异常被触发的原因一定能够追溯到某条指令的执行；而中断则
异步
(Asynchronous) 于当前正在进行的指令，也就是说中断来自于哪个外设以及中断如何触发完全与处理器正在执行的当前指令无关。
关于中断,这里提到一个关键点,
检查中断是在每次处理器执行完指令之后
的:
对于中断，可以理解为发起中断的是一套与处理器执行指令无关的电路（从时钟中断来看就是简单的计数和比较器），这套电路仅通过一根导线接入处理器。当外设想要触发中断的时候则输入一个高电平或正边沿，处理器会在每执行完一条指令之后检查一下这根线，看情况决定是继续执行接下来的指令还是进入中断处理流程。也就是说，大多数情况下，指令执行的相关硬件单元和可能发起中断的电路是完全独立
并行
(Parallel) 运行的，它们中间只有一根导线相连。
有关于RISC-V的中断类型和优先级规则,还是要仔细阅读
官方文档
.
这里只提出其中比较重点的一个规则,就是进入中断之后,会
屏蔽低于和等于该优先级的其他中断
.
时钟中断
这里提到了
RISC-V架构
的计时机制,要求它一定要有一个内置时钟.
这里就让我们想起了之前学到过的
Cortex-M3
内置的
systick
.还有很少人注意到的内置在
Cortex-M3
中的
DWT
模块.
(这里也可以去做
第一章作业
里
第三题
那个延时程序了,有没有记得我们之前去访问
sepc
寄存器的时候使用的
riscv::register
,现在我们可以直接调用它来实现了)
在
RISC-V 64
架构中,这个计时器的具体实现是
mtime
寄存器.
这个寄存器的不能在
S
特权级直接访问,回想我们之前学过的
OS
架构层次:
创建
os/src/timer.rs
文件.
只需要在
M
特权级的上层(
SBI
)构建一个接口就行了.
RustSBI
恰恰帮我们实现了这样的一个接口,因此我们可以这样实现:
// os/src/timer.rs
use riscv::register::time;
pub fn get_time() -> usize {
time::read()
}
为了实现
定时一段时间
强行切换应用的效果,我们需要实现一个
定时中断
的特性.
RustSBI
可以实现这个功能,在
os/src/sbi.rs
里使用
sbi_call
实现这个功能,即设置一个计时器,实际原理是设置
mtimecmp
模块的值,等待
mtime
计时达到之后
触发中断
:
// os/src/sbi.rs
pub fn set_timer(time: usize)
{
sbi_rt::set_timer(time as _);
}
这里
注意
,
手册中写的代码
是
旧版
,在按照第0章配置的基础上
sbi-rt
的版本是
0.02
.应该使用
如上
代码.
这时候在
os/src/timer.rs
里进行封装.计算计时器在
10ms
内的增量,然后把当前
mtime
的值和增量加起来设置到
mtimecmp
中:
// 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);
}
这里注意
CLOCK_FREQ
是写在
os/src/config.rs
里的常量,这里直接参考
源码
即可,这里可以看到
K210
的时钟频率和
QEMU
默认的时钟频率:
/*
#[cfg(feature = "board_k210")]
pub const CLOCK_FREQ: usize = 403000000 / 62;
#[cfg(feature = "board_qemu")]
pub const CLOCK_FREQ: usize = 12500000;
*/
pub use crate::board::CLOCK_FREQ;
这个
board
模块需要在
src/board/qemu.rs
里实现.
//! Constants used in rCore for qemu
pub const CLOCK_FREQ: usize = 12500000;
最后
board
模块和
timer
模块也需在
os/src/main.rs
里声明.
...
mod timer;
#[path = "boards/qemu.rs"]
mod board;
...
#[path = "boards/qemu.rs"]
是一个属性宏 (
attribute macro
),用来告诉 Rust 编译器该模块的实际源文件位置是在
boards/qemu.rs
这个文件中.
还需要实现一个
获取当前定时器时间
的函数.可以
用来
统计应用运行时长.
// 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)
}
这里官方文档说要实现一个
系统调用
,用于应用获取当前时间.那么我们已经有了
get_time_us
函数了.
根据上一节的经验,我们只需要分别在
用户层
和
内核层
写实现即可.
首先是在用户层实现:
// user/src/syscall.rs
const SYSCALL_GET_TIME: usize = 169;
pub fn sys_get_time() -> isize {
syscall(SYSCALL_GET_TIME, [0, 0, 0])
}
进一步封装:
// user/src/lib.rs
pub fn get_time() -> isize {
sys_get_time()
}
然后需要在内核层实现,这里是回调:
// os/src/syscall/mod.rs
...
const SYSCALL_GET_TIME: usize = 169;
/// 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),
SYSCALL_YIELD => sys_yield(),
SYSCALL_GET_TIME => sys_get_time(),
_ => panic!("Unsupported syscall_id: {}", syscall_id),
}
}
...
这里还需要具体实现
sys_get_time
:
// os/src/syscall/process.rs
use crate::timer::get_time_us;
pub fn sys_get_time() -> isize {
get_time_us() as isize
}
那么我们也不能直接返回当前
mtime
的值,而是需要更换单位,因此
get_time_us
的实现也显而易见,根据
系统时钟频率
计算出当前的
微秒级
时间:
// 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)
}
抢占式调度
这里要回忆起
中断也是一种
trap
.
那么要实现抢占式调度就很简单了.只需要在发生
定时器中断
之后
继续设置一个定时器
,然后执行
suspend_current_and_run_next
,
挂起当前应用并且执行下一个应用
.
那么只需要修改
trap_handler
函数,加入相应的处理逻辑.
// os/src/trap/mod.rs
match scause.cause() {
Trap::Interrupt(Interrupt::SupervisorTimer) => {
set_next_trigger();
suspend_current_and_run_next();
}
}
那么第一个时间片是哪里来的呢,答案是我们
自己设置一个定时器
timer::set_next_trigger();
.为了避免
S
特权级时钟中断被屏蔽,我们需要
启动时钟中断的陷入
trap::enable_timer_interrupt();
.
// os/src/main.rs
#[no_mangle]
pub fn rust_main() -> ! {
clear_bss();
println!("[kernel] Hello, world!");
trap::init();
loader::load_apps();
trap::enable_timer_interrupt();
timer::set_next_trigger()
task::run_first_task();
panic!("Unreachable in rust_main!");
}
trap::enable_timer_interrupt();
实际是设置了
sie
寄存器的
stie
位,使得
S
特权级时钟中断不会被屏蔽.
// os/src/trap/mod.rs
/// timer interrupt enabled
pub fn enable_timer_interrupt() {
unsafe {
sie::set_stimer();
}
}
这里这个特殊的处理机制也需要关注,虽然以我的水平暂时发现不了这么高深的玩意:
有同学可能会注意到，我们并没有将应用初始 Trap 上下文中的
sstatus
中的
SPIE
位置为 1 。这将意味着 CPU 在用户态执行应用的时候
sstatus
的
SIE
为 0 ，根据定义来说，此时的 CPU 会屏蔽 S 态所有中断，自然也包括 S 特权级时钟中断。但是可以观察到我们的应用在用尽一个时间片之后能够正常被打断。这是因为当 CPU 在 U 态接收到一个 S 态时钟中断时会被抢占，这时无论
SIE
位是否被设置都会进入 Trap 处理流程。
这时候要注意
主动交出CPU
的机制仍然需要保留.比如这个应用:
// user/src/bin/03sleep.rs
#[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
}
这里如果不执行
yield_()
就需要
等定时器中断
需要
10ms
的时间片,这样就
浪费了时间
.
具体实现执行
这里主要是对
分时多任务系统与抢占式调度
的测试应用没有实现.
我们只需在
源码
中找到具体实现就行了.
这里是一些解析和提点:
// user\src\bin\00power_3.rs
#![no_std]
#![no_main]
#[macro_use]
extern crate user_lib;
const LEN: usize = 100;
#[no_mangle]
fn main() -> i32 {
let p = 3u64;
let m = 998244353u64;
let iter: usize = 200000;
let mut s = [0u64; LEN];
let mut cur = 0usize;
s[cur] = 1;
for i in 1..=iter {
let next = if cur + 1 == LEN { 0 } else { cur + 1 };
s[next] = s[cur] * p % m;
cur = next;
if i % 10000 == 0 {
println!("power_3 [{}/{}]", i, iter);
}
}
println!("{}^{} = {}(MOD {})", p, iter, s[cur], m);
println!("Test power_3 OK!");
0
}
这个应用计算
\(p^{iter} \mod m\)
的值:
- 计算当前元素
s[cur]
乘以
p
并对
m
取模的结果，然后将这个结果存放在下一个位置
next
中。 - 更新
cur
为
next
，如果
cur
已经到达数组的末尾 (
LEN
)，则将
cur
设置为 0，实现数组的滚动使用。 - 每当迭代达到 10000 的倍数时，输出当前迭代的进度。
- 在完成所有的迭代后，输出最终的计算结果和测试通过的信息。
其余的两个app,
user\src\bin\01power_5.rs
和
user\src\bin\02power_7.rs
,只是更换了
p
的值.这里掠过.
对于最后一个应用就是我们上一节最后提到的应用
user\src\bin\03sleep.rs
.也不进行赘述.
这里具体把app都实现之后:
cd user
make build
cd ../os
make run
最后得出运行结果:
[rustsbi] RustSBI version 0.3.1, adapting to RISC-V SBI v1.0.0
.______ __ __ _______.___________. _______..______ __
| _ \ | | | | / | | / || _ \ | |
| |_) | | | | | | (----`---| |----`| (----`| |_) || |
| / | | | | \ \ | | \ \ | _ < | |
| |\ \----.| `--' |.----) | | | .----) | | |_) || |
| _| `._____| \______/ |_______/ |__| |_______/ |______/ |__|
[rustsbi] Implementation : RustSBI-QEMU Version 0.2.0-alpha.2
[rustsbi] Platform Name : riscv-virtio,qemu
[rustsbi] Platform SMP : 1
[rustsbi] Platform Memory : 0x80000000..0x88000000
[rustsbi] Boot HART : 0
[rustsbi] Device Tree Region : 0x87000000..0x87000f02
[rustsbi] Firmware Address : 0x80000000
[rustsbi] Supervisor Address : 0x80200000
[rustsbi] pmp01: 0x00000000..0x80000000 (-wr)
[rustsbi] pmp02: 0x80000000..0x80200000 (---)
[rustsbi] pmp03: 0x80200000..0x88000000 (xwr)
[rustsbi] pmp04: 0x88000000..0x00000000 (-wr)
[kernel] Hello, world!
[kernel] trap init end
power_3 [10000/200000]
power_3 [20000/200000]
power_3 [30000/200000]
power_3 [40000/200000]
power_3 [50000/200000]
power_3 [60000/200000]
power_3 [70000/200000]
power_3 [80000/200000]
power_3 [90000/200000]
power_3 [100000/200000]
power_3 [110000/200000]
power_3 [120000/200000]
power_3 [130000/200000]
power_3 [140000/200000]
power_3 [150000/200000]
power_3 [160000/200000]
power_3 [170000/200000]
power_3 [180000/200000]
power_3 [190000/200000]
power_3 [200000/200000]
3^200000 = 871008973(MOD 998244353)
Test power_3 OK!
[kernel] Application exited with code 0
power_7 [10000/160000]
power_7 [20000/160000]
power_7 [30000/160000]
power_7 [40000/160000]
power_7 [50000/160000]
power_7 [60000/160000]
power_7 [70000/160000]
power_7 [80000/160000]
power_7 [90000/160000]
power_7 [100000/160000]
power_7 [110000/160000]
power_7 [120000/160000]
power_7 [130000/160000]
power_7 [140000/160000]
power_7 [150000/160000]
power_7 [160000/160000]
7^160000 = 667897727(MOD 998244353)
Test power_7 OK!
[kernel] Application exited with code 0
power_7 [10000/160000]
power_7 [20000/160000]
power_7 [30000/160000]
power_7 [40000/160000]
power_7 [50000/160000]
power_7 [60000/160000]
power_7 [70000/160000]
power_7 [80000/160000]
power_7 [90000/160000]
power_7 [100000/160000]
power_7 [110000/160000]
power_7 [120000/160000]
power_7 [130000/160000]
power_7 [140000/160000]
power_7 [150000/160000]
power_7 [160000/160000]
7^160000 = 667897727(MOD 998244353)
Test power_7 OK!
[kernel] Application exited with code 0
Test sleep OK!
[kernel] Application exited with code 0
All applications completed!
可以看到在
sleep
期间成功运行了三种求幂任务.