關於任務排程 - ianchen0119/AwesomeCS GitHub Wiki

本文目標

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

常見的排程演算法

FCFS (First-Come First-Served)

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

RR (Round-Robin)

上面提到的 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

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();

  // 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;
// ...
  • 為了避免 Timer Interrupt 出現巢狀中断的情況,在處理中斷之前, trap_handler() 會將 timer interrupt 關閉,等到處理完成後再打開。

是說這一步有點多餘,因為 RISC-V 處理器進入中斷後的預設情況下會暫時停止處理其他 Interrupt,之後我再發個 PR 把它修掉 XD

  • timer_handler() 執行完畢後,trap_handler() 會將 mepc 指向 os_kernel(),做到任務切換的功能。 換言之,如果中斷不屬於 Timer Interrupt,Program counter 則會跳回進入中斷前的狀態,這個步驟定義在 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 不放,系統也就不會被惡霸卡住而整個癱瘓了,這就是現代作業系統中最重要的行程管理機制

Reference