本文目标
FCFS 是所有排程演算法中最简单的，所有的任务都会被放进 Queue 当中，最先到的任务会优先被处理，直到处理完毕或是该任务主动让出使用权，作业系统才会处理下一个任务。
上面提到的 FCFS 排程方法有一个显而易见的缺点，如果有一个任务需要非常长时间才会完成，甚至是该任务不会有结束的时候 (http server, system monitor)，这样就会产生霸占问题，让其他进入排程的任务永源分配不到硬体资源。
RR 演算法解决了 FCFS 的霸占问题，在 RR 中，会设定一个基本时间，每个任务都可以获得基本时间的硬体资源，如果任务很长的话就会被分次执行:
| 任务 | 所需时间 |
|---|---|
| Task1 | 3 Units |
| Task2 | 1 Unit |
| Task3 | 4 Units |
假设排程器的基本时间为一个 Unit，此时，在作业系统上的任务执行顺序会像是这样:
Task1 -> OS -> Task2 -> OS -> Task3 -> OS -> Task1 -> OS -> Task3 -> OS -> Task1 -> OS -> Task3 -> OS -> Task3
最短优先演算法会让所需最短时间的任务被优先执行，如果有复数个任务所需的时间一样短，就会采用 FCFS 的策略执行。
PS 会为每个任务赋予一个优先权，优先权较高的任务将优先被执行，如果有复数个任务的优先权相同，就会采用 FCFS 的策略执行。
其实 SJF 就可以算是 PS 的一种，只是他以时间单位作为优先权。
不过，PS 不像是 SJF 会有任务所需时间减短的情况产生，这有可能会让优先权较低的任务永远分配不到硬体资源，这个情况又称饥饿 (Starvation) 现象。
为了解决这个问题，PS 会引入老化的机制，让执行过但未完成的任务的优先权降低，确保每个任务都能分配到硬体资源。
在 mini-riscv-os 的 05-Preemptive 中，透过时间中断的机制完成了简易的 RR 排程器:
void user_task0(void)
{
lib_puts("Task0: Created!\n");
while (1) {
lib_puts("Task0: Running...\n");
lib_delay(1000);
}
}
其中的 lib.c 内的 lib_delay() 是个延迟回圈，并不会交还控制权。
void lib_delay(volatile int count)
{
count *= 50000;
while (count--);
}
相反的，作业系统会透过时间中断，强制取回控制权。(由於 lib_delay 延迟较久，所以作业系统通常会打断其 while (count--) 的回圈取回控制权)
作业系统 (os.c) 一开始会呼叫 user_init()，让使用者建立 task (在本范例中会在 user.c 当中建立 user_task0 与 user_task1 )。
#include "os.h"
void user_task0(void)
{
lib_puts("Task0: Created!\n");
while (1) {
lib_puts("Task0: Running...\n");
lib_delay(1000);
}
}
void user_task1(void)
{
lib_puts("Task1: Created!\n");
while (1) {
lib_puts("Task1: Running...\n");
lib_delay(1000);
}
}
void user_init() {
task_create(&user_task0);
task_create(&user_task1);
}
然後作业系统会在 os_start() 里透过 timer_init() 函数设定时间中断，接着就是进入 os_main() 的主回圈里，该回圈采用 Round-Robin 的大轮回排班方法，每次切换就选下一个 task 来执行 (若已到最後一个 task，接下来就是第 0 个 task)。
#include "os.h"
void os_kernel() {
task_os();
}
void os_start() {
lib_puts("OS start\n");
user_init();
timer_init(); // start timer interrupt ...
}
int os_main(void)
{
os_start();
int current_task = 0;
while (1) {
lib_puts("OS: Activate next task\n");
task_go(current_task);
lib_puts("OS: Back to OS\n");
current_task = (current_task + 1) % taskTop; // Round Robin Scheduling
lib_puts("\n");
}
return 0;
}
在 05-Preemptive 的中断机制中，笔者修改了中断向量表:
.globl trap_vector
# the trap vector base address must always be aligned on a 4-byte boundary
.align 4
trap_vector:
# save context(registers).
csrrw t6, mscratch, t6 # swap t6 and mscratch
reg_save t6
csrw mscratch, t6
# call the C trap handler in trap.c
csrr a0, mepc
csrr a1, mcause
call trap_handler
# trap_handler will return the return address via a0.
csrw mepc, a0
# load context(registers).
csrr t6, mscratch
reg_load t6
mret
当中断发生时，中断向量表 trap_vector() 会呼叫 trap_handler():
reg_t trap_handler(reg_t epc, reg_t cause)
{
reg_t return_pc = epc;
reg_t cause_code = cause & 0xfff;
if (cause & 0x80000000)
{
/* Asynchronous trap - interrupt */
switch (cause_code)
{
case 3:
lib_puts("software interruption!\n");
break;
case 7:
lib_puts("timer interruption!\n");
// disable machine-mode timer interrupts.
w_mie(~((~r_mie()) | (1 << 7)));
timer_handler();
return_pc = (reg_t)&os_kernel;
// enable machine-mode timer interrupts.
w_mie(r_mie() | MIE_MTIE);
break;
case 11:
lib_puts("external interruption!\n");
break;
default:
lib_puts("unknown async exception!\n");
break;
}
}
else
{
/* Synchronous trap - exception */
lib_puts("Sync exceptions!\n");
while (1)
{
/* code */
}
}
return return_pc;
}
跳到 trap_handler() 之後，它会针对不同类型的中断呼叫不同的 handler，所以我们可以将它视为一个中断的派发任务中继站:
+----------------+
| soft_handler() |
+-------+----------------+
|
+----------------+-------+-----------------+
| trap_handler() | | timer_handler() |
+----------------+ +-----------------+
|
+-------+-----------------+
| exter_handler() |
+-----------------+
trap_handler 可以根据不同的中断类型，将中断处理交给不同的 handler，这样子做就可以大大的提高作业系统的扩充性。
#include "timer.h"
// a scratch area per CPU for machine-mode timer interrupts.
reg_t timer_scratch[NCPU][5];
#define interval 20000000 // cycles; about 2 second in qemu.
void timer_init()
{
// each CPU has a separate source of timer interrupts.
int id = r_mhartid();
// ask the CLINT for a timer interrupt.
// int interval = 1000000; // cycles; about 1/10th second in qemu.
*(reg_t *)CLINT_MTIMECMP(id) = *(reg_t *)CLINT_MTIME + interval;
// prepare information in scratch[] for timervec.
// scratch[0..2] : space for timervec to save registers.
// scratch[3] : address of CLINT MTIMECMP register.
// scratch[4] : desired interval (in cycles) between timer interrupts.
reg_t *scratch = &timer_scratch[id][0];
scratch[3] = CLINT_MTIMECMP(id);
scratch[4] = interval;
w_mscratch((reg_t)scratch);
// enable machine-mode timer interrupts.
w_mie(r_mie() | MIE_MTIE);
}
static int timer_count = 0;
void timer_handler()
{
lib_printf("timer_handler: %d\n", ++timer_count);
int id = r_mhartid();
*(reg_t *)CLINT_MTIMECMP(id) = *(reg_t *)CLINT_MTIME + interval;
}
看到 timer.c 之中定义的 timer_handler()，它会将 MTIMECMP 做 reset 的动作。
/* In trap_handler() */
// ...
case 7:
lib_puts("timer interruption!\n");
// disable machine-mode timer interrupts.
w_mie(~((~r_mie()) | (1 << 7)));
timer_handler();
return_pc = (reg_t)&os_kernel;
// enable machine-mode timer interrupts.
w_mie(r_mie() | MIE_MTIE);
break;
// ...
trap_handler() 会将 timer interrupt 关闭，等到处理完成後再打开。是说这一步有点多余，因为 RISC-V 处理器进入中断後的预设情况下会暂时停止处理其他 Interrupt，之後我再发个 PR 把它修掉 XD
timer_handler() 执行完毕後，trap_handler() 会将 mepc 指向 os_kernel()，做到任务切换的功能。trap_vector() 中:csrr a0, mepc # a0 => arg1 (return_pc) of trap_handler()
补充
在 RISC-V 中，函式的参数会被优先存进 a0 - a7 暂存器，如果不够用，才会存入 Stack。
其中，a0 与 a1 暂存器还有作为函式返回值的作用。
最後，记得在 Kernel 开机时导入 trap 以及 timer 的初始化动作:
void os_start()
{
lib_puts("OS start\n");
user_init();
trap_init();
timer_init(); // start timer interrupt ...
}
透过时间中断强制取回控制权，我们就不用担心有恶霸行程把持 CPU 不放，系统也就不会被恶霸卡住而整个瘫痪了，这就是现代作业系统中最重要的行程管理机制。
前言 这篇适合给first time leader，特别是刚被promote成team leade...
昨天写了BFS模板&一题模板题，今天放几题比较复杂的~~ 例题实战 909. 蛇梯棋 这题最...
专案介绍 这个专案会带你使用HTML和CSS，打造专属於你的个人履历网页。 预览图： 首先，我们从H...
Method 操作方法 在熟悉 selector 後，就可以开始采用物件连结的方式进行各种作业 最基...
是否该用云端平台 在正式使用k8s的时候，部署k8s最好的情况是使用云端平台。 一来机器规格可以依照...