自幹作業系統 - Task and Scheduler

自幹作業系統 系列的第三篇整理 初探 Timer 原理 探索筆記，本來是想帶到怎麼實作 sleep()，不過 sleep 其實只是一個小小的應用而已，真正的核心是 task.c 以及裡面的 schedule() (排程演算法) 這兩個概念，本文就以這兩個為主整理相關的學習筆記。

1. Task 資料結構: 了解主要結構以及背景知識
2. Task State Machine: 透過狀態機了解 Task 的狀態移轉
3. Scheduler 的實作與設計: 用推演的方式整理排程演算法整個流程

避免篇幅過多，其中 Task 資料結構理會提到 Paging 和 Stack 之後再整理。

自幹作業系統 系列:

• Source Code, Demo/錄影
• 自幹作業系統 - Simple OS
• 自幹作業系統 - Networking Fundamentals
• 自幹作業系統 - 初探 Timer 原理
• 自幹作業系統 - Task and Scheduler

註：內容僅是自學的一些筆記，如果有發現資訊不正確，或者描述錯誤，請不令給予指教，感謝。

Task 資料結構

在 task.h 裡定義了一個 task_t 結構，這個結構包含以下特性:

1. 環狀鏈結串列 (Circular Linked List): 主要是為了實踐 輪詢 (Round-Robin) 機制，主要的屬性是 struct task *next 記錄著下一個 task 位置
2. 進程控制區塊 (Process Control Block, PCB): 主要記錄的是 Process 的屬性，像是 PID, Parent ID (ppid), name, 累計的 ticks, 分頁位置 … 等
3. 任務控制區塊 (Task Control Block, TCB): 包含 CPU 狀態 (esp), task 狀態, 以及等待的 Sub-Process PID.
   • esp: ESP 全名是 Extended Stack Pointer (堆疊指標暫存器) ，主要是記錄當前堆疊的 最高位址 或者說 最舊位址 。在排程器中，保存與替換 esp 是 Context Switch 的關鍵因素。除了 esp 之外，
   • state: task 現在狀態, 用來控制排程行為。

底下是完整的資料結構：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * @brief 進程控制區塊 (Process Control Block, PCB) / 任務控制區塊 (Task Control Block, TCB)
 *
 * - TCB 的執行流資訊:如 esp, state
 * - PCB 的資源管理資訊: 如 page_directory, cwd_lba
 */
typedef struct task {
    uint32_t esp;               ///< 核心堆疊指標 (Context Switch 關鍵)。當任務被切換走時，CPU 暫存器現場存於此堆疊位址。

    // === 行程身份資訊 (PCB Properties) ===
    uint32_t pid;               ///< 行程 ID (Unique Identifier)。範例：1 (Shell)。
    uint32_t ppid;              ///< 父行程 ID (Parent PID)。若為 0 則代表由核心直接建立。
    char name[32];              ///< 行程名稱。用於 ps/top 顯示，上限 31 字元 + \0。

    uint32_t total_ticks;       ///< 累計執行時間 (CPU Accounting)。統計該任務佔用 CPU 的總滴答數。

    // === 資源與記憶體管理 (PCB Properties) ===
    uint32_t page_directory;    ///< 專屬分頁目錄實體位址 (CR3)。確保行程間記憶體空間完全隔離。
    uint32_t kernel_stack;      ///< 核心堆疊頂部。進入核心模式時 TSS.esp0 的加載目標。

    // === 執行狀態與排程控制 (TCB Properties) ===
    uint32_t state;             ///< 行程當前狀態。0:RUNNING, 1:DEAD, 2:WAITING, 3:ZOMBIE, 4:SLEEPING。
    uint32_t wait_pid;          ///< 正在等待的子行程 PID。僅在 TASK_WAITING 狀態下有效。

    // === 執行環境實體資訊 ===
    uint32_t heap_start;        ///< 使用者堆積 (Heap) 起始虛擬位址。通常為 0x10000000。
    uint32_t heap_end;          ///< 使用者堆積當前邊界。隨 sbrk() 動態調整。
    uint32_t cwd_lba;           ///< 目前工作目錄 (CWD) 的 LBA。決定相對路徑檔案存取的起點。

    // === 計時器功能 ===
    uint32_t wake_up_tick;      ///< 喚醒時間點。當全域 tick >= 此值時，排程器將任務由 SLEEPING 撥回 RUNNING。

    // === 鏈結結構 ===
    struct task *next;          ///< 環狀鏈結串列指標。指向下一個任務，實現 Round-Robin 輪轉。
} task_t;

在 Simple OS 中，或者在 Linux 核心，可以把 TCB (Task Control Block) 與 PCB (Process Control Block) 兩個角色的結構當作同一個東西。但如果是 FreeRTOS 這種極輕量系統，PCB 是關於「資源的擁有權」，TCB 是關於「CPU 的執行權」。

Task State Machine

為了讓我自己可以更有效率了解整個實作，我用 【聊聊 API First 開發策略】 裡提到的 API 設計方法論 - 有限狀態機 的方法，整理如下圖：

狀態包含以下：

1. RUNNING: 表示 Process 正在使用 CPU
2. SLEEPING: 表示 Process 收到 sleep 指令、或者從等待中變成在睡覺
3. WAITING: 表示 Process 正在等待下一個狀態
4. ZOMBIE: 表示 Process 已結束，但父行程尚未 wait() 回收它
5. DEAD: 表示 Process 已經結束了，準備被 GC 回收資源。還找得到資訊。
6. Reclaimed: Process 已經被回收，已經找不到資訊。

而針對 task 處理的動作，定義在 task.h 則有以下：

• init_multitasking()
• create_user_task()
• exit_task()
• sys_kill()
• sys_sleep()
• sys_wait()
• sys_fork()

Scheduler

初始 [kernel_main] Task

整個 Simple OS 啟動的第一個行程叫做 [kernel_main, PID=0]，這個 Process 標誌著從 Kernel Space 切換到 User Space 的橋接，透過交棒給 [shell, PID=1] Process 完成整個程序，把作業系統的主控權交給使用者。

註：目前 Simple OS 實作的版本還在單人多工狀態，大概類似於 DOS 吧 XDD

在原始碼中 main.c 主要的步驟如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/// 略 ...
if (entry_point != 0) {
    kprintf("Creating Initial Process (Shell)...\n\n");

    // 1) 啟動排程器 (Timer IRQ0 開始跳動)
    init_multitasking();

    // 為 Shell 分配專屬的 User Stack
    uint32_t ustack1_phys = (uint32_t) pmm_alloc_page();
    map_page(0x083FF000, ustack1_phys, 7);

    // 2) 建立 Ring 3 主任務
    create_user_task(entry_point, 0x083FF000 + 4096);

    kprintf("[Kernel] Dropping to idle state. Enjoy your GUI!\n");

    // 3) Kernel 功成身退，把自己宣告死亡！
    exit_task();
}

整理狀態改變如下圖：

• (1) init_multitasking(): 建立 [kernel_main] process, PID=0、建立 [idle_task] process, PID=9999, current_task 指向 PID=0
  • 核心任務 (Kernel Task)：Kernel 啟動時第一個 Process (PID=0)。SimpleOS 裡的實作是完成 Shell 喚醒與交棒後，Kernel Task 就會自殺 sys_exit()，然後被 GC 回收。
  • 閒置任務 (Idle Task)：當系統無事可做時執行。當 Shell 也在等待輸入（WAITING）或睡眠（SLEEPING），且環狀串列中沒有其他任務在跑時，排程器會跳過死掉的 kernel_main，並因為找不到 RUNNING 的任務而切換到 idle_task 執行 hlt (Halt, CPU 進入休眠直到下一個中斷)。
• (2) create_user_task():
  • 2.1) 建立 [shell] process, PID=1, 這時候 current_task 還是指向 kernel_main
  • 2.2) current_task 指向 [shell] process，然後 [kernel_main] 狀態還是 RUNNING
• (3) exit_task(): 執行 exit_task()，[kernel_main] 狀態變成 DEAD，等待下次 scheduler 執行時，會 GC 回收。

Preemptive Round-Robin Scheduling

排程演算法是作業系統裡非常核心的部分，Simple OS 實作最簡單、且容易理解的 Round-Robin (輪詢) 方法。下圖用三個正在執行的 Process，嘗試解釋 task.c#schedule() 如何透過 環狀鏈結串列 (Circular Linked List) 實現 公平 的時間分配。

• 步驟 1,2,3 代表 timer 每次計算的 tick，詳細參閱 初探 Timer 原理.
• 紅框 (current_task)：是動態移動的，代表目前 CPU 暫存器裡正在跑的任務現場。

摘要上圖表示的重點：

• 環狀鏈結串列 (Circular Linked List)：
  • 在圖中可以看到 PID#1 -> PID#2 -> PID#3 -> PID#1 三個 Process 的結構形成一個閉環。
  • schedule() 每次執行的核心動作就是：next_run = current_task->next;。這就像是撥動轉盤，讓 CPU 的使用權傳給下一位。
• 公平執行 (Fairness)：
  • 如 時刻 (1) 到 時刻 (2) 的變化。只要任務狀態是 RUNNING，排程器就會按順序分發時間片。
  • 這確保了沒有任何一個任務會霸佔 CPU，這就是 搶佔式多工 (Preemptive Multitasking) 的精髓。
• 狀態過濾 (State Filtering)：
  • 當 schedule() 指向到 PID#3 時，會執行程式碼中的 while (next_run->state != TASK_RUNNING) 檢查。
  • 因為 PID#3 狀態是 SLEEPING (灰色虛線框)，排程器會立刻再次執行 next_run = next_run->next，直接跳過睡眠中的任務，把 CPU 交給下一個準備好的任務（PID#1）。

這套演算法雖然簡單，在 Simple OS 中卻是重要的核心架構，它保證了即便應用程式 sleep 在睡覺，shell 依然能靈敏地回應使用者的輸入。

問題

Q1: 當 Timer 的頻率為 100Hz，下跑 100 個任務，OS 會不會卡頓？

作業系統不會因為任務變多而邏輯崩潰，但會變得很「卡頓」。

1) 時間片的數學題：

init_timer(100) 意即 1s / 100=10ms，系統每 10ms 就會發出一次中斷，Round-Robin (RR) 演算法的輪詢過程，這 10ms 就是一個 時間片 (Time Slice) 。

• 如果有 10 個任務：每個任務每 100ms 就能輪到一次（10ms x 10 = 100ms）。人類感官會覺得還算流暢。
• 如果有 100 個任務：每個任務每 1 秒鐘才能輪到一次（10ms x 100 = 1000ms）。這意味著你點一下滑鼠，那個 App 要等 1 秒鐘才有機會被 CPU 執行 10ms。

2) 管理開銷 (Overhead):

真正的危機在於 Context Switch（上下文切換）的代價。每次 schedule() 執行時，CPU 都要：

1. 保存舊任務的暫存器到堆疊；
2. 呼叫 switch_task；
3. 切換分頁表（刷新 TLB，這很昂貴）；
4. 恢復新任務的暫存器。

假設上下文切換需要 0.1ms：

• 10 個任務：每 10ms 花 0.1ms 管理，損耗 1%。
• 100 個任務：管理成本依然是每 10ms 花 0.1ms，但累積起來的 延遲（Latency） 會讓使用者覺得系統當機了。

系統不會倒，但會發生 「Thrashing（抖動）」。當 CPU 跑管理程式（排程、GC）的時間比例過高，真正跑 User App 的進度就會趨近於零。

Q2: task.c#ready_queue 的用途是什麼？

task.c 裡 ready_queue 扮演的是「錨點」與「主環入口」的角色。

1. 作為環狀鏈結串列的「根」:

雖然 current_task 會在環裡面跑來跑去，但我們需要一個全域指標永遠指著這個環的某個固定點。

• 用途：當你要執行 task_get_process_list（如 ps 指令）或是 task_gc 時，你需要一個起點來遍歷整個環。如果沒有 ready_queue，一旦 current_task 發生錯誤或遺失，整個進程鏈結都會在記憶體中「失蹤」。

2. 解決「Idle 迷航」問題:

• 情境：當所有任務都在 SLEEPING 或 WAITING 時，current_task 會指到 Idle Task。
• 問題：Idle Task 是獨立於環外的「降落傘」。如果沒有 ready_queue 幫你記住主環在哪裡，當下一次中斷發生在 Idle 狀態時，排程器會因為 idle_task->next 沒有指向主環而無法喚醒任何人。

ready_queue 就像是那個環的「存檔點」，確保排程器隨時可以跳回主要任務群進行掃描。

3. 管理任務的新增與刪除

• 新增：當 fork 一個新任務，會把它插在 ready_queue 的後面。
• 刪除：當任務 DEAD 時，task_gc 會從 ready_queue 開始找，確保即便當前跑的是 idle_task，也能正確清理主環裡的垃圾。

current_task 決定了 「現在是誰」，而 ready_queue 定義了 「我們總共有誰」。

目前 RR 演算法是「遍歷整個環」來找下一個。隨著任務變多，schedule() 的速度會越來越慢 O(N)。在現代 Linux 核心中，會將 ready_queue 改造成 Completely Fair Scheduler (CFS，完全公平排程演算法）來達到 log(N) 的效率。

註：CFS 實作為 紅黑樹 (Red-Black Tree)，相關可以參閱 Linux 核心設計: Scheduler(2): 概述 CFS Scheduler 深入介紹。

延伸閱讀

自幹作業系統 系列

• 自幹作業系統 - Simple OS
• 自幹作業系統 - Networking Fundamentals
• 自幹作業系統 - 初探 Timer 原理
• 自幹作業系統 - Task and Scheduler

站內文章

• 聊聊 API First 開發策略

參考資料

• Linux 核心設計: 不只是執行單元的 process
• Linux 核心設計: Scheduler(2): 概述 CFS Scheduler