任務排程（Task Scheduling）

本文目標#

學習基本的排程演算法
閱讀原始碼以理解排程器的實際運作

常見的排程演算法#

FCFS (First-Come First-Served)#

FCFS 是所有排程演算法中最簡單的，所有的任務都會被放進 Queue 當中，最先到的任務會優先被處理，直到處理完畢或是該任務主動讓出使用權，作業系統才會處理下一個任務。

RR (Round-Robin)#

上面提到的 FCFS 排程方法有一個顯而易見的缺點，如果有一個任務需要非常長時間才會完成，甚至是該任務不會有結束的時候（http server、system monitor），這樣就會產生霸佔問題，讓其他進入排程的任務永遠分配不到硬體資源。

RR 演算法解決了 FCFS 的霸佔問題，在 RR 中會設定一個基本時間，每個任務都可以獲得基本時間的硬體資源，如果任務很長的話就會被分次執行。

假設排程器的基本時間為一個 Unit，任務需求如下：

Task1：3 Units
Task2：1 Unit
Task3：4 Units

此時，在作業系統上的任務執行順序會像是：

Task1 -> OS -> Task2 -> OS -> Task3 -> OS -> Task1 -> OS -> Task3 -> OS -> Task1 -> OS -> Task3 -> OS -> Task3

SJF (Shortest Job First)#

最短優先演算法會讓所需最短時間的任務被優先執行，如果有複數個任務所需的時間一樣短，就會採用 FCFS 的策略執行。

PS (Priority Scheduling)#

PS 會為每個任務賦予一個優先權，優先權較高的任務將優先被執行，如果有複數個任務的優先權相同，就會採用 FCFS 的策略執行。其實 SJF 就可以算是 PS 的一種，只是它以時間單位作為優先權。

不過，PS 不像 SJF 會有任務所需時間減短的情況產生，這有可能會讓優先權較低的任務永遠分配不到硬體資源，這個情況又稱飢餓（Starvation）現象。為了解決這個問題，PS 會引入老化的機制，讓執行過但未完成的任務的優先權降低，確保每個任務都能分配到硬體資源。

原始碼觀摩：mini-riscv-os#

在 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--) 的迴圈取回控制權。）

User Application 初始化#

作業系統（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();

  *(reg_t *)CLINT_MTIMECMP(id) = *(reg_t *)CLINT_MTIME + interval;

  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 的動作。

為了避免 Timer Interrupt 出現巢狀中斷的情況，在處理中斷之前，trap_handler() 會將 timer interrupt 關閉，等到處理完成後再打開。
timer_handler() 執行完畢後，trap_handler() 會將 mepc 指向 os_kernel()，做到任務切換的功能。換言之，如果中斷不屬於 Timer Interrupt，Program counter 則會跳回進入中斷前的狀態。

補充：在 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 不放，系統也就不會被卡住而整個癱瘓，這正是現代作業系統最重要的行程管理機制。

原文出處#

原書/iThome：https://ithelp.ithome.com.tw/articles/10277165