Linux 核心專題: 作業系統的設計和開發

執行人: HeatCrab
GitHub
專題解說影片

Reviewed by `eleanorLYJ`

linmo 用甚麼記憶體配置策略?
另外，commit 連結無法看到。

Linmo 的動態記憶體採用的是 first-fit 策略（可以參考開發紀錄中 06-12 課程討論筆記的記憶體配置策略部分）。

以下是簡單說明：當動態記憶體配置器配置記憶體時，會呼叫 malloc 函式，並使用 first-fit 策略線性地搜尋未被配置的記憶體區塊，在找到足夠大的區塊後，若剩餘的空間足夠，則進行分割。而在釋放記憶體時，藉由 free 函式標記區塊為有效空間，以減少碎片的產生。在 malloc() 正式配置記憶體之前，如果空閒的區塊（free block）超過我們定義的 COALESCE_THRESHOLD 數量（8），會呼叫函式 selective_coalesce 來合併相鄰的空閒區塊，進一步管理碎片。更多細節歡迎一起鑽研 lib/malloc.c ！

另外想確認一下，請問是所有的 commit 連結皆不可見嗎？還是是特定的呢？
HeatCrab

下方提及的每筆 commit 都無法查閱，應該是在 commit eb3f4dc 前已經被 git squash 處理，或是 commit 屬於私人 repo。
EricccTaiwan

了解！
HeatCrab

Reviewed by `EricccTaiwan`

承上討論，是否可以用其他方式呈現程式碼的改動? e.g., 利用 diff 標示、或附上連結至程式碼片段，方便讀者查看對應的程式碼。

我有更新 commit 與 issue 的內容至一個 hackmd 紀錄中，內含開發紀錄內所有被提及的 commit 與 issue ，希望這次能順利呈現開發過程！
HeatCrab

Reviewed by `salmoniscute`

想請問 app/hello.c 中建立的 task0-2，分別設定他們的 priority 為 normal、low、normal 的用意為何？

回顧 app/hello.c 中的程式碼，我們可以在 app_main() 裡發現：
mo_task_priority(2, TASK_PRIO_LOW);
這個函式呼叫後，會針對回傳的第一個參數，辨識是否有此任務的 id 存在，接著確認是否有第二個參數代表的優先級被定義在系統內，若是以上兩者皆符合條件，則藉由函式重新賦予該任務優先級。
那如果任務沒有被呼叫這個函式呢？像是 task 0 跟 task 2 ，甚至是 task1 ，他們會在呼叫 mo_task_spawn() 函式，也就是在被創建時，就被賦予系統預設的優先級定義 TASK_PRIO_NORMAL ，所以如果任務未被 mo_task_priority() 函式重新賦予優先級的話，優先級都會是預設的 TASK_PRIO_NORMAL （更多細節歡迎一起探討　kernel/task.c 與 kernel/task.h 程式碼）。

那回到最一開始的問題：

為什麼要分別設定 normal、low、normal 呢？

透過前面的說明我們可以知道，其實只有 task1 是被特別定義成較低級別的優先級的，透過這個較低級別的優先級，我們可以觀察，系統透過搶佔式排程的過程是否如同我們設計的一般運作，那根據我們的測試成果，我們知道 task1 不僅順利運作，也因為我們設計的排程演算法，在相對較高優先級的 task0 與 task2 之間獲得 CPU 時間進行執行，不僅避免了 starvation 的發生，也展現了排程器與計時器（timer）搭配所達成的系統排程公平性。

那最後再回頭看一下 task0 與 task1 ，其實這兩者的設計也是有著小巧思。儘管兩個任務因為優先級相同，在 round-robin 排程演算法下平分大部分的 CPU 執行時間，但是 task2 特別將時間列印出來，目的是為了讓測試者間接去觀察計時器在 Linmo 作業系統中跟排程器的搭配。所以其實測試結果除了會是 task0 與 task2 輪流執行，task1 偶爾獲得執行時間外，也可以藉由列印於 task2 後方的時間觀察計時器在系統中跟排程器的互動。

以下是 app/hello.c 測試結果參考：
... 
[task 1 000001]
[task 3 000003 - sys uptime: 0.021s] <- task3（我們定義的 task2）紀錄系統嘀嗒（tick）
[task 1 100001]
[task 3 100003 - sys uptime: 0.023s]
[task 1 200001]
[task 3 200003 - sys uptime: 0.025s]
[task 1 300001]
[task 3 300003 - sys uptime: 0.027s]
[task 1 400001]
[task 3 400003 - sys uptime: 0.029s]
[task 1 500001]
[task 2 000002] <--- task2（我們定義的 task1）獲得一次排程機會 
[task 3 500003 - sys uptime: 0.221s]
[task 1 600001]
[task 3 600003 - sys uptime: 0.241s]
[task 1 700001]
[task 3 700003 - sys uptime: 0.261s]
...
HeatCrab

Reviewed by `tsaiiuo`

在這兩個 commit 之後， kernel/mutex.c 的程式碼也是經歷許多更動。 mutex 在實作上不再依賴 Binary semaphore

想請問棄用 Binary semaphore 的考量為何呢？以及為何當初會想使用 Binary semaphore 在 mutex 的實作上？

semaphore 跟 mutex 都是非常經典的同步機制，那兩者可以分別這麼去想：

Semaphore:
一間可以容納 N 個人的房間，沒有鑰匙。
如果房間還沒滿，人就可以進去；如果房間滿了，就要等待有人出來。
N = 1，稱為 Binary Semaphore，用來限制對某一個資源的同時間訪問。

Mutex:
一間可以容納 1 個人的房間，有一把鑰匙。
只有一個人，和一把鑰匙。拿了鑰匙可以進去房間。

這也是為何大家說 mutex 跟 binary semaphore 很相似的原因，因為當 semaphore 的房間只可以容納 1 個人時，與 mutex 只有一個人可以持有鎖的概念雷同。
再加上藉由呼叫已經定義好的 semaphore 程式碼內的控制區塊結構，就可以完成 mutex 阻塞等待與資源配置的相關功能，無需再自行實作相關功能。

但是 mutex 這樣高度依賴 semaphore 造成的問題也顯而易見。兩者在模組間的高度耦合（high coupling）造成了 semaphore 若是出現問題，會間接導致 mutex 的異常，增加維護的難度。此外， semaphore 作為通用的同步機制，會包含 mutex 不需要的功能，這種情況也會導致不必要的記憶體與執行開銷。最後，獨立定義 mutex 的控制區塊可以使得 mutex 專注於定義自身實作邏輯的需求，不再過度依賴 semaphore 邏輯的同時，也降低了原先實作上的複雜度與維護難度。

mutex 的開發過程可以參見以下兩個 commits：
commit fff7cfb
commit 0d18664
HeatCrab

Reviewed by `Andrushika`

在實作記憶體配置相關功能時，要怎麼驗證 first-fit 的配置策略，是否真的依照預期的狀況執行呢？是有什麼工具可以把記憶體配置的過程可視化嗎？

我自己個人是分兩種情況：

如果是系統是能運行，且未受例外或是 panic 導致系統執行終止的話，使用 (QEMU) xp 與 (QEMU) info mem 這兩種指令可以確認記憶體的配置情形。

如果系統運行後直接終止，我就會使用 printf() 在需要確認的程式碼位置，一段一段作確認。儘管慢且不易，但卻是在沒有更好其他工具能使用的情況下的好辦法之一。

此外，若是報錯，可以使用 qemu log 查看錯誤回報，或是使用 Linmo 專案在 README 中 Prerequisites 的 riscv-gnu-toolchain。理論上可以使用裡面的 gnu 套件除錯，但是我也還在研究中。
若是有其他更好的辦法，也歡迎推薦給我！謝謝！
HeatCrab

Reviewed by `rota1001`

在探討 stack_check 函式的實作的時候，使用一個固定的值 STACK_CANARY 來檢查 stack 是否損毀。然而，這存在一些安全移慮，攻擊者可以偽造這個 canary 來造成核心無法察覺堆疊損毀，在某些情況下可以讓堆疊上的任意修改更容易（譬如利用 buffer overflow）。是否考慮過對於每個 kernel stack 都給予一個隨機的 canary？

收到邱冠維學長的回覆，他說因為在沒有由 MMU 來實現的記憶體隔離的情況下，使用者程式本來就能做到這些事情，所以隨機的 canary 值不會帶來什麼改善。而如果在實現記憶體隔離之後，這就是一個合理的改進了。

謝謝提供關於資訊安全的相關考量，我會在開發 MMU 的過程中將這個之前沒有顧及與思考到的部分也一併考慮進去！
HeatCrab

Reviewed by `Jordymalone`

想請問關於信用基礎演算法，有提到會為每一個即時任務配置固定的 credit，那這個 credit 是 Programmer 去定義的嗎？是否有個上限值？

這個 credit 是 Programmer 去定義的嗎？

是的！是由開發者去根據想要測試的效果去自定義的。

是否有個上限值?

沒有硬性規定的上限值，但是有受 int 資料型別的理論上限值（2,147,483,647）。
HeatCrab

任務簡述

研讀〈Operating System in 1,000 Lines 〉教學文件，理解在 RISC-V (以 RV32 為主) 如何從無到有建構作業系統核心，隨後投入 Mazu 作業系統的開發。

研讀 Operating System in 1,000 Lines 教學文件的筆記與實驗

GitHub

02. RISC-V 101

Calling Convention

Data Model

TYPE LP32 ILP32 LP64 ILP64 LLP64

CHAR 8 8 8 8 8

SHORT 16 16 16 16 16

INT 16 32 32 64 32

LONG 32 32 64 64 32

LONG LONG 64 64 64 64 64

POINTER 32 32 64 64 64

TYPE	LP32	ILP32	LP64	ILP64	LLP64
CHAR	8	8	8	8	8
SHORT	16	16	16	16	16
INT	16	32	32	64	32
LONG	32	32	64	64	32
LONG LONG	64	64	64	64	64
POINTER	32	32	64	64	64

RV32 and RV64

C TYPE	Description	RV32	RV64
char	Character value/byte	1	1
short	Short integer	2	2
int	Integer	4	4
long	Long integer	4	8
long long	Long long integer	8	8
void*	Pointer	4	8
float	Single-precision float	4	4
double	Double-precision float	8	8
long double	Extended-precision float	16	16

RISC-V 的呼叫慣例定義了函式呼叫時暫存器的使用方式與資料型態的對應關係。RV32 和 RV64 的資料模型有所不同（參照上方表格）。在函式參數傳遞時，若參數大小超過指標長度（pointer-word）的兩倍，會以參照（reference）方式傳遞。例如，函式 foo(int, double, long double) 在 RV32 中，int 使用暫存器 a0，double（64 位元）使用 a2-a3（跳過 a1 以符合奇偶暫存器對齊（even-odd　register pair）），而 long double（128 位元）因過大，改以指標存於 a4。在 RV64 中，double 與 long double 的配置更為直接，分別使用 a1 與 a2-a3。

特權指令（Privileged instructions）與 CSR （控制與狀態暫存器）

CSR

RISC-V 的特權指令用於管理核心功能，核心操作 CSR 。常見指令包括：

CSRRW（Atomic Read/Write CSR）：交換 CSR 與整數暫存器的值。
CSRRS（Atomic Read and Set Bits in CSR）：讀取 CSR 並根據位元遮罩設置特定位元。
CSRRC（Atomic Read and Clear Bits in CSR）：讀取 CSR 並清除特定位元。

這些指令根據目標暫存器（rd）與來源暫存器（rs1）是否為 x0，決定是否讀取或寫入 CSR。此外，立即數（Immediate）版本的指令（如 CSRRWI、CSRRSI、CSRRCI）使用 5 位元無符號立即數（uimm[4:0]）取代暫存器值。

Register operand

Instruction rd is x0 rs1 is x0 Reads CSR Writes CSR

CSRRW Yes - No Yes

CSRRW No - Yes Yes

CSRRS/CSRRC - Yes Yes No

CSRRS/CSRRC - No Yes Yes
Immediate operand

Instruction rd is x0 uimm = 0 Reads CSR Writes CSR

CSRRWI Yes - No Yes

CSRRWI No - Yes Yes

CSRRSI/CSRRCI - Yes Yes No

CSRRSI/CSRRCI - No Yes Yes

Instruction	rd is x0	rs1 is x0	Reads CSR	Writes CSR
CSRRW	Yes	-	No	Yes
CSRRW	No	-	Yes	Yes
CSRRS/CSRRC	-	Yes	Yes	No
CSRRS/CSRRC	-	No	Yes	Yes

Instruction	rd is x0	uimm = 0	Reads CSR	Writes CSR
CSRRWI	Yes	-	No	Yes
CSRRWI	No	-	Yes	Yes
CSRRSI/CSRRCI	-	Yes	Yes	No
CSRRSI/CSRRCI	-	No	Yes	Yes

讀到後面章節回來查文件發現，沒有找到 CSRR 跟 CSRW 的定義，但是通過教學文件可以清晰理解相關使用方法。

SRET

ISA-privilged P.58 3.3.2 Trap-Return Instructions

用於從監督者模式（S-mode）返回，通常在例外處理後恢復執行。

內嵌展開組合語言指令（Inline assembly）

內嵌展開組合語言指令允許在 C 程式碼中直接撰寫 RISC-V 組合語言，格式為：

__asm__ __volatile__(
    "assembly" 
    : output operands 
    : input operands 
    : clobbered registers
);

讓我們可以直接操作暫存器或執行特權指令等。

virt

使用 QEMU 的 virt 虛擬平台模擬 RISC-V 環境，支援 RV32 與 RV64，提供標準化的硬體介面，便於作業系統開發與測試。

04. Boot

連結器腳本（Linker Script）

定義了核心的記憶體佈局，確保程式碼、資料與堆疊正確放置。主要內容包括：

基底位址（base address）：設定核心起始位址為 0x80200000，透過 llvm-objdump -d kernel.elf 可驗證程式碼從此位址開始執行。

kernel.elf:	file format elf32-littleriscv

Disassembly of section .text:

80200000 <boot>: <- kernal 的確由 0x80200000 開始執行
80200000: 37 05 22 80  	lui	a0, 0x80220
80200004: 13 05 c5 04  	addi	a0, a0, 0x4c
80200008: 2a 81        	mv	sp, a0
8020000a: 6f 00 a0 01  	j	0x80200024 <kernel_main>
...

.text 區段：使用 KEEP(*(.text.boot)) 保留啟動程式碼（boot 函式），確保其位於 .text 區段開頭，防止連結器在最佳化時丟棄此區段。
.bss 區段：記錄未初始化資料的起始位址（__bss），在 C 中以 extern char[] 定義。
核心堆疊：配置 128KB 空間（. += 128 * 1024），並記錄堆疊頂部位址（__stack_top），供 boot 函式初始化堆疊指標（sp）。
對齊（align）：使用 ALIGN(4) 將目前位址（由位置計數器 . 表示）調整到最接近的下一個 4 位元組對齊的位址，確保所有區段對齊到 4 位元組，符合 RISC-V 架構需求。

參考資料：

__attribute__((naked))

使用 __attribute__((naked)) 定義的函式，編譯器不會產生 prologue 與 epilogue 程式碼，僅包含內嵌展開組合語言。這確保啟動流程完全由開發者控制，適用於低階初始化。

The naked attribute tells the compiler not to generate any other code than the inline assembly. –- 10. Process
Compiler-specific Function, Variable, and Type Attributes

05. Hello World!

SBI

RISC-V Supervisor Binary Interface Specification
SBI is an "API for OS".

ECALL（Environment Call）

ISA-privilged P.57 3.3.1 Environment Call and Breakpoint

核心透過 ecall 指令觸發 SBI 功能，參數由暫存器 a0 至 a7 傳遞：

EID：指定 SBI 的某個 Extension ，儲存在暫存器 a7 。
FID：指定某個 EID Extension下的具體功能，儲存在暫存器 a6 。

例如，函式 putchar 透過 SBI 的 Console Putchar 功能（EID=0, FID=1）輸出字元：

void putchar(char ch) {
    sbi_call(ch, 0, 0, 0, 0, 0, 0, 1);
}

執行 ecall 後，CPU 跳躍至機器模式（M-mode）的例外處理程式（由 mtvec 暫存器指定），OpenSBI 負責處理並輸出字元至除錯控制台。

wfi（Wait for Interrupt）

ISA-privilged P.58 3.3.3 Wait for Interrupt

作用是讓硬體執行緒（hardware thread，hart）進入等待狀態，暫停執行指令，以降低功耗並等待中斷或特定條件來觸發恢復。它適用於所有特權模式，包括機器模式（M-Mode）、監督者模式（S-Mode）及使用者模式（U-Mode），不過若 mstatus 暫存器的 TW 位（Timeout Wait）設為 1，較低特權模式可能引發例外非法指令。作為一 32 位指令，WFI 結構簡單，無需額外參數，透過內嵌展開組合語言嵌入核心程式碼，確保執行時不被編譯器優化移除。

在作業系統中，WFI 常見於核心的閒置迴圈，使用在無任務處理時讓 CPU 進入低功耗狀態。一旦啟用且待處理的中斷發生，例如 Timer 或外部裝置觸發，CPU 會跳躍至 trap 處理器（由 mtvec 暫存器指定），處理完畢後從 WFI 後的下一指令繼續執行。值得注意的是，WFI 的行為不受全局中斷位（mstatus.MIE 或 SIE）或委派暫存器（mideleg）的直接限制，即使中斷被禁用，它仍能檢測本地啟用的待處理中斷，展現高度靈活性。硬體實現上，部分系統可能將 WFI 視為無操作（NOP），不進入等待狀態，因此軟體需檢查中斷暫存器（mip 或 sip），並在無中斷時重新執行 WFI，以確保正確運作。

在教學文件中，WFI 出現於 kernel_main 的無限迴圈，位於初始化輸出（"Hello World!"）之後

for (;;) {
    __asm__ __volatile__("wfi");
}

此設計使核心在完成初步任務後進入閒置狀態，避免 CPU 空轉，同時保持對中斷的反應能力。在 QEMU 模擬環境中，WFI 模擬等待中斷的行為，降低模擬器資源消耗。

在 common.h 中定義的 printf 函式支援可變參數：

void printf(const char *fmt, ...);

... 表示接受任意數量的參數， fmt 決定參數的解釋方式。並使用 #pragma once 防止標頭檔重複包含，提升編譯效率。

Variadic function builtins：Clang Language Extensions

06. C Standard Library

strcpy 的風險
strcpy 函式將來源字串（含結尾空字元）複製到目標緩衝區，但不檢查目標緩衝區大小。若來源字串過長，可能導致緩衝區溢位，引發程式錯誤或安全漏洞。因此，教學文件建議改用更安全的替代函式。

WARNING
The strcpy function continues copying even if src is longer than the memory area of dst. This can easily lead to bugs and vulnerabilities, so it's generally recommended to use alternative functions instead of strcpy. Never use it in production!
For simplicity, we'll use strcpy in this book, but if you have the capacity, try implementing and using an alternative function (strcpy_s) instead.

strcpy_s 的優勢

strcpy_s 是一個邊界檢查函式，需指定目標緩衝區大小（destsz），具備以下優點：

防止緩衝區溢位，確保複製不超過指定大小，保護記憶體安全。
若參數無效（如空指標或緩衝區過小），返回返回非零值，並將目標緩衝區的第一個字元設為零（除非指標無效）。
strcpy_s 明確禁止截尾，如果來源字串過長，它會拒絕複製並返回錯誤，從而避免未終止字串的問題。

strcpy_s 實作

以下是 common.c 中 strcpy_s 的實作，包含參數檢查與安全複製邏輯：

errno_t strcpy_s(char *dst, size_t dstsz, const char *src) {
    if (!dst || !src || dstsz == 0) {
        if (dst && dstsz) dst[0] = '\0';
        return EINVAL;
    }
    size_t src_len = 0;
    const char *s = src;
    while (*s) src_len++, s++;
    src_len++; /* 包含空字元 */
    if (src_len > dstsz) {
        dst[0] = '\0';
        return ERANGE;
    }
    memcpy(dst, src, src_len);
    return 0;
}

此實作先檢查參數有效性，計算來源字串長度（含空字元），確認目標緩衝區足夠大後進行複製，並在錯誤時清空目標緩衝區。

07. Kernal Panic

巨集設計技巧

巨集常用 do {} while(0) 結構封裝多行程式碼，確保巨集展開後行為如同單一語句。這種設計有幾個好處：

統一語法：巨集使用時需加分號，與一般語句一致。
避免語法錯誤：在條件語句（如 if-else）中，展開後不會因缺少大括號導致錯誤，即 dangling else
範圍隔離：巨集內的變數不會與外部衝突。

例如，若未使用 do-while，巨集展開可能導致語法錯誤：

#define MY_MACRO() { printf("Line 1\n"); printf("Line 2\n"); }
if (condition) MY_MACRO(); else printf("Else block\n");

展開後，else 會錯誤地綁定到第二個 printf，造成語法問題。使用 do {} while(0) 可避免此問題。
另外，巨集支援多行定義時，透過反斜線（\）將程式碼連續起來，忽略換行符號，確保程式碼清晰。

08. Exception

例外處理流程（Life of an exception）

檢查與委派暫存器：CPU 檢查 medeleg 暫存器，決定由哪個模式（通常是監督者模式 S-mode 或機器模式 M-mode）處理例外。OpenSBI 預設將使用者模式（U-mode）和 S-mode 的例外轉交給 S-mode 處理。`
保存狀態：CPU 將目前執行狀態（例如程式計數器 PC 與暫存器值）保存到特定的 CSR 中，包括 scause（例外原因）、stval（附加資訊）、sepc（例外指令位址）與 sstatus（狀態）。
跳躍處理程式：CPU 將 PC 設置為 stvec 暫存器中的位址，跳躍至核心的例外處理程式。
處理例外：例外處理程式保存通用暫存器至堆疊（形成 trap frame），然後呼叫 handle_trap 函式，根據 scause 和 stval 分析並處理例外。
恢復狀態並繼續執行：處理完成後，恢復保存的暫存器，執行 sret 指令，從例外發生點繼續執行。

委派暫存器

ISA-privilged P.40 3.1.8 Machine Trap Delegation (medeleg and mideleg) Registers

medeleg 和 mideleg 暫存器控制例外與中斷的委派，支援將特定例外或中斷從 M-mode 轉交給 S-mode 處理。medeleg 管理同步例外，每個位元對應一種例外類型，設為 1 表示轉交給 S-mode。mideleg 則管理中斷，類似地控制委派行為。這兩個暫存器為 WARL（Write Any, Read Legal）類型，硬體只接受合法值。

其中，在文件中提到：

CPU checks the medeleg register to determine which operation mode should handle the exception. In our case, OpenSBI has already configured to handle U-Mode/S-Mode exceptions in S-Mode’s handler.

這表示 OpenSBI 已預先配置 medeleg，將 U-Mode 和 S-Mode 的例外委派到 S-Mode 處理。也就是說， medeleg 的某些位元被設為 1，對應的例外會由 stvec 指向 S-Mode 的 exception handler。

關鍵 CSR

ISA-privilged Ch 12

stvec：儲存 S-mode 例外處理程式的基底位址，需 4 位元組對齊（透過 __attribute__((aligned(4))) 達成）。
scause：記錄例外或中斷原因，高位區分中斷（1）或例外（0），低位為具體原因編碼。
stval：儲存與例外或中斷相關的附加資訊，內容因例外或中斷類型而異。
sepc：記錄例外發生時的 PC 值。
sstatus：決定例外發生後要恢復的操作模式（例如從 S-Mode 返回 U-Mode）。

sscratch：用於臨時儲存堆疊指標（sp），在 kernel_entry 中保存與恢復堆疊狀態。

__asm__ __volatile__(
    "csrw sscratch, sp\n"  // 保存 sp 到 sscratch
    "addi sp, sp, -4 * 31\n"  // 配置 stack space
    ...
    "csrr a0, sscratch\n"  // 從 sscratch 恢復 sp
    "sw a0, 4 * 30(sp)\n"  // 將原始 sp 存入 trap_frame
);

09. Memory Alloctation

在連結器腳本中， . += 64 * 1024 * 1024; 配置 64MB 的記憶體空間，並使用 . = ALIGN(4096) 確保起始位址對齊到 4KB。

. = ALIGN(4096);
__free_ram = .;
. += 64 * 1024 * 1024; /* 64MB */
__free_ram_end = .;

__free_ram 記錄可用記憶體的起始位址，__free_ram_end 標記結束位址。此空間用於動態配置記憶體頁面。

函式 alloc_pages(uint32_t n) 負責配置指定數量的記憶體頁面（每頁 4KB），目前採用簡單的 Bump Allocator 演算法。該演算法從 __free_ram 開始，依序配置連續頁面，並更新目前位址指標。雖然簡單，但無法釋放記憶體，容易造成記憶體浪費。作者建議未來改進為支援記憶體回收的演算法，如 free list。

此 "free" 不是「自由」，而是「空閒」和「有效的空間」

10. Process

行程控制塊（PCB）
透過 struct 定義 PCB 的細節

struct process {
    int pid;             // Process ID
    int state;           // Process state: PROC_UNUSED or PROC_RUNNABLE
    vaddr_t sp;          // Stack pointer
    uint8_t stack[8192]; // Kernel stack (獨立，用於保存 CPU 暫存器、
                         // 返回位址和局部變數，支援上下文切換)
};

行程管理設計

#define PROCS_MAX 8       // Maximum number of processes
struct process procs[PROCS_MAX]; // All process control structures.

透過靜態陣列配置行程控制結構，實現簡化的行程管理。在程式碼中，定義最大行程數量 PROCS_MAX 為 8，並使用全域陣列 struct process procs[PROCS_MAX] 儲存所有行程控制結構。這種設計類似 Linux 核心早期版本採用 NR_TASK 定義任務數量上限並以陣列配置的方式，旨在避免使用動態堆積（heap）配置。透過靜態陣列，行程控制結構的記憶體在編譯時配置於核心的資料分段，無需運行時的動態記憶體管理，簡化了分頁表設置與記憶體保護的複雜性，確保記憶體使用的可預測性與高效性。

上下文切換

Callee-saved registers are registers that a called function must restore before returning.

上下文切換在 switch_context 函式中達成，負責保存與恢復行程的執行狀態。RISC-V 中，callee-saved 暫存器（s0 至 s11）由被呼叫函式負責保存，因此切換時僅需處理這些暫存器。caller-saved 暫存器（如 a0）由呼叫者保存至堆疊，無需額外處理。在 create_process 中，初始化新行程的核心堆疊，預設保存 callee-saved 暫存器與返回位址（ra）。

    // Stack callee-saved registers. These register values will be restored in
    // the first context switch in switch_context.
    uint32_t *sp = (uint32_t *) &proc->stack[sizeof(proc->stack)];
    *--sp = 0;                      // s11
    *--sp = 0;                      // s10
    *--sp = 0;                      // s9
    *--sp = 0;                      // s8
    *--sp = 0;                      // s7
    *--sp = 0;                      // s6
    *--sp = 0;                      // s5
    *--sp = 0;                      // s4
    *--sp = 0;                      // s3
    *--sp = 0;                      // s2
    *--sp = 0;                      // s1
    *--sp = 0;                      // s0
    *--sp = (uint32_t) pc;          // ra

例外處理調整

為支援行程切換，異常處理程式進行了以下改進：

在 yield 函式中，在上下文切換前，將下一個行程的核心堆疊位址寫入 sscratch 暫存器。因為當例外或中斷發生時，系統需要使用可信任的核心堆疊，而不是使用者堆疊（可能指向無效位址，如 0xdeadbeef）。透過預先設置 sscratch，確保例外處理程式能正確切換到下一個行程的核心堆疊。
在 kernel_entry 中，使用 csrrw 指令交換 sp 與 sscratch，立即切換至核心堆疊，保存原始堆疊指標以便恢復。處理完成後，重置 sscratch 為核心堆疊底部，確保後續異常處理的堆疊一致性。

11. Page Table

The table that maps virtual addresses to physical addresses is called a page table. By switching page tables, the same virtual address can point to different physical addresses.

使用 SV32 構成分頁表

SV32 是 RISC-V 指令集架構（ISA）為 32 位元系統設計的虛擬記憶體管理機制，透過分頁表達成虛擬位址到實體位址的映射。它主要應用於監督者模式（Supervisor Mode），確保應用程式與核心的記憶體空間隔離，提升系統安全性和穩定性。SV32 支援記憶體保護與隔離，讓每個行程擁有獨立的虛擬定址空間。

SV32 將 32 位元虛擬位址分為三部分（視覺化程式）：

VPN[1]	VPN[0]	Offset
10 bits	10 bits	12 bits

除了 SV32 ，RISC-V 還提供適用於 64 位元系統的虛擬記憶體模式，例如 Sv39 和 Sv48。Sv39 使用三級分頁表，支援 39 位元虛擬位址，能處理更大的定址空間，適合需要更高記憶體容量的應用場景。Sv48 則進一步擴展至四級分頁表，支援 48 位元虛擬位址，提供更廣泛的記憶體管理能力，適用於高效能伺服器或複雜系統。SV32 的設計在簡化結構與降低複雜度的同時，確保高效的位址轉換與記憶體隔離，特別適合嵌入式系統或輕量級作業系統。

man_page 函式實作

首先，函式根據權限需求設置旗標（flags），指定頁面是否可讀（PAGE_R）、可寫（PAGE_W）或可執行（PAGE_X）。在第一級分頁表中，函式使用第一級索引（vpn1）定位項，將第二級分頁表的實體位址（pt_paddr）轉換為實體頁碼（PPN），方法是除以頁面大小（PAGE_SIZE = 4KB），然後左移 10 位以符合分頁表項（page table entry，PTE）格式，再附加有效位（PAGE_V）標記項可用。接著，函式從第一級項提取 PPN，右移 10 位後乘以頁面大小，轉換為第二級分頁表的實體位址，並將其轉為指標以存取第二級分頁表。在第二級分頁表中，函式根據第二級索引（vpn0）設置目標頁面的映射，將實體位址（paddr）轉為 PPN，結合權限旗標與有效位，完成映射。由於分頁表儲存的是 PPN 而非完整實體位址，所有位址轉換均需除以頁面大小，確保映射精確無誤。

上下文切換中的分頁表同步

為達成行程間的記憶體隔離，核心在 yield 函式中改進上下文切換邏輯，同步交換行程的分頁表，確保每個行程使用獨立的虛擬定址空間。改進的程式碼透過內嵌展開組合語言達成關鍵操作：

__asm__ __volatile__(
    "sfence.vma\n"
    "csrw satp, %[satp]\n"
    "sfence.vma\n"
    "csrw sscratch, %[sscratch]\n"
    :
    : [satp] "r" (SATP_SV32 | ((uint32_t) next->page_table / PAGE_SIZE)),
      [sscratch] "r" ((uint32_t) &next->stack[sizeof(next->stack)])
);

程式碼首先執行虛擬記憶體位址同步（sfence.vma），確保切換分頁表前，所有先前的記憶體存取操作完成，同時清除 TLB ，避免舊分頁表項干擾後續位址轉換，防止分頁錯誤（page fault）。接著，程式碼將新行程的分頁表位址寫入 satp 暫存器（Supervisor Address Translation and Protection），啟用新分頁表的位址轉換。satp 的值由 Sv32 模式標誌（SATP_SV32）與新行程第一級分頁表位址（next->page_table）組成，後者除以頁面大小轉換為實體頁碼（PPN）。切換分頁表後，再次執行 sfence.vma，確保 TLB 完全更新，後續指令基於新分頁表進行位址轉換，防止不一致行為。最後，程式碼將新行程的核心堆疊頂部位址寫入 sscratch 暫存器，確保例外發生時，核心使用正確的堆疊保存狀態，無需手動查找堆疊位置。

此改進達成了多項功能：

透過分頁表切換確保行程間的記憶體隔離，防止資料混淆與安全漏洞
透過 TLB 同步保證位址轉換一致性；支援例外處理，讓核心在例外發生時使用正確堆疊
啟用 Sv32 分頁模式，為虛擬記憶體管理提供硬體基礎。

若不切換分頁表，所有行程將共用同一記憶體映射，導致嚴重的安全與穩定性問題。

Examining page table contents

(qemu) info registers 

CPU#0
 V      =   0
 pc       80000530
 mhartid  00000000
 ...
 satp     80080255
 ...

計算第一層實體位址：
得到 PPN = (0x80080255 & 0x03FFFFF) * 4096 = 0x80255000
又 VPN[1] = 0x80200000 >> 22 = 512

(qemu) xp /x 0x80255000+512*4
0000000080255800: 0x20095801

計算第二層實體位址：
(0x20095801 >> 10) * 4096 = 0x80256000
接著 VPN[0] = (0x80200000 >> 12) & 0x3ff = 512

(qemu) xp /x 0x80256000+512*4
0000000080256800: 0x2008004f

最後得 PPN = 0x2008004f >> 10 = 0x80200000

接著列出整個第一層級：

(qemu) xp /1024x 0x80255000
0000000080255000: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255010: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255020: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255030: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255040: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255050: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255060: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255070: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255080: 0x00000000 0x00000000 0x00000000 0x00000000
...
0000000080255800: 0x20095801 0x20095c01 0x20096001 0x20096401
0000000080255810: 0x20096801 0x20096c01 0x20097001 0x20097401
0000000080255820: 0x20097801 0x20097c01 0x20098001 0x20098401
0000000080255830: 0x20098801 0x20098c01 0x20099001 0x20099401
0000000080255840: 0x20099801 0x00000000 0x00000000 0x00000000
...

在 0000000080255800 開始，也就是第512個，因為核心基底是 0x80200000，且他的 VPN[1] 是 0x200 。

最後檢視一下生成出的分頁表：

(qemu)info mem
vaddr    paddr            size     attr
-------- ---------------- -------- -------
80200000 0000000080200000 00001000 rwx--a-
...

attr：

V（Valid）：分頁表項是否有效。
R（Readable）：允許讀取。
W（Writable）：允許寫入。
X（Executable）：允許執行。
U（User）：允許使用者模式存取。
A（Accessed）：分頁是否被存取過。
D（Dirty）：分頁是否被寫入過。

12. Application

核心使用 llvm-objcopy 將二進位檔案 shell.bin 轉換為目的碼 shell.bin.o，以便鏈結至核心：

$ OBJCOPY -Ibinary -Oelf32-littleriscv shell.bin shell.bin.o

透過程式碼，我們可以知道，_binary_shell_bin_start 作為指向 shell.bin 二進位內容的指標和 _binary_shell_bin_size 取得 shell.bin 的大小。

extern char _binary_shell_bin_start[];
extern char _binary_shell_bin_size[];

void main(void) {
    uint8_t *shell_bin = (uint8_t *) _binary_shell_bin_start;
    printf("shell_bin size = %d\n", (int) _binary_shell_bin_size);
    printf("shell_bin[0] = %x (%d bytes)\n", shell_bin[0]);
}

透過 llvm-nm 命令檢查 shell.bin.o：

$ llvm-nm shell.bin.o
00010260 D _binary_shell_bin_end
00010260 A _binary_shell_bin_size
00000000 D _binary_shell_bin_start

接著驗證 _binary_shell_bin_size：

$ llvm-nm shell.bin.o | grep _binary_shell_bin_size
00010260 A _binary_shell_bin_size

$ ls -al shell.bin
-rwxrwxr-x 1 heatcrab heatcrab 66144  6月  2 19:33 shell.bin

$ python3 -c 'print(0x10260)'
66144

最後透過 llvm-objdump 命令確認 .text.start 的確在 0x1000000

$ llvm-objdump -d shell.elf

shell.elf:	file format elf32-littleriscv

Disassembly of section .text:

01000000 <start>:
 1000000: 37 05 01 01  	lui	a0, 0x1010
 1000004: 13 05 05 26  	addi	a0, a0, 0x260
 1000008: 2a 81        	mv	sp, a0
 100000a: 11 20        	jal	0x100000e <main>
 100000c: 11 20        	jal	0x1000010 <exit>

0100000e <main>:
 100000e: 01 a0        	j	0x100000e <main>

01000010 <exit>:
 1000010: 01 a0        	j	0x1000010 <exit>

13. User Mode

改進行程的建立

更新 create_process 函式，新增傳入參數，以支援載入二進位映像：

struct process *create_process(const void *image, size_t image_size)

image 指向二進位資料（如 _binary_shell_bin_start），image_size 為資料大小。核心初始化行程的核心堆疊，將返回位址（ra）設為 user_entry，負責切換至使用者模式。

使用者模式切換

接著設置 user_entry 的初始 sp：

*--sp = (uint32_t) user_entry;  // ra

它主要負責切換到使用者模式並跳躍到 USER_BASE

在 kernel.h 中定義：

#define SSTATUS_SPIE (1 << 5)

這個定義是，在 08. Exception 中提到過的 sstatus 這個 CSR 暫存器中的 SPIE 這個位元。它屬於 sstatus 暫存器中的第五位，所以透過左移五位定義。它的目標是處理從 supervisor mode 回到 low-privilaged mode 。它將會在 user_entry 中被使用到。

接著在 kernel.c 中定義 user_entry ：

__attribute__((naked)) void user_entry(void) {
    __asm__ __volatile__(
        "csrw sepc, %[sepc]        \n"
        "csrw sstatus, %[sstatus]  \n"
        "sret                      \n"
        :
        : [sepc] "r" (USER_BASE),
          [sstatus] "r" (SSTATUS_SPIE)
    );
}

csrw sepc, %[sepc] ：將 USER_BASE（0x1000000）的值寫入 sepc 暫存器。

sepc 暫存器指定了當執行 sret 指令時，將跳躍到的 PC 位址。而 USER_BASE 是使用者應用程式的虛擬起始位址（即 shell.bin 的載入位址），確保進入使用者模式後，從應用程式的入口點（0x1000000）開始執行。
csrw sstatus, %[sstatus] ：將 SSTATUS_SPIE 寫入 sstatus 暫存器。

設置 SPIE 為 1 表示在進入使用者模式後，允許恢復之前的監督者模式中斷狀態。

In this book, we don't use hardware interrupts but use polling instead, so it's not necessary to set the SPIE bit. However, it's better to be clear rather than silently ignoring interrupts.
sret ：執行「Supervisor Return」指令，從 S-Mode 返回到 U-Mode 。

最後 create_process 新增一個 for 迴圈來管理使用者分頁。

關於 volatile

在 C 語言中，volatile 關鍵字用於指示編譯器不要對特定變數或記憶體操作進行最佳化，確保程式碼行為符合開發者的意圖。在使用者程式範例中，程式碼透過 volatile 存取特定記憶體位址：

#include "user.h"

void main(void) {
    *((volatile int *) 0x80200000) = 0x1234;
    for (;;);
}

這段程式碼將值 0x1234 寫入記憶體位址 0x80200000，並使用 volatile 修飾指標，保證寫入操作實際執行。volatile 的作用在於防止編譯器因最佳化而移除或重排這一寫入操作，因為該位址可能對應記憶體映射的輸入輸出（memory-mapped I/O）設備，寫入行為必須精確執行以與硬體交互。無限迴圈 for (;;); 確保程式在寫入後持續運行，避免結束。

volatile 的行為與其禁止編譯器最佳化的特性密切相關。編譯器通常會假設變數值不會在程式控制流之外改變，因此可能移除看似無用的讀寫操作。然而，volatile 明確告知編譯器，該變數可能由外部因素修改，必須保留所有讀寫操作並按程式碼順序執行。這對於記憶體映射 I/O 至關重要，因為硬體設備的行為依賴特定的寫入時序與順序。

然而，使用 volatile 存取記憶體映射 I/O（如範例中的 0x80200000）具有平台依賴性，屬於非可攜性用法。該位址在 RISC-V 與 QEMU 環境中可能對應特定設備，但在其他平台或硬體上可能無效或導致未定義行為。因此，開發者需深入了解目標平台的記憶體映射與 C/C++ 實作細節，確保程式碼正確性。

14. System Call

系統呼叫實作

核心定義 syscall 函式，處理使用者程式的系統呼叫請求。使用者程式將系統呼叫編號（sysno）存入暫存器 a3，參數存入 a0、a1、a2，執行 ecall 觸發異常。核心的異常處理程式接管後，根據 a3 執行對應服務，並將返回值存入 a0 傳回使用者程式。

~~Shell 與 Kernel 的比較~~

特性	Shell	Kernel
定義	Shell 是一個使用者介面程式，提供使用者與作業系統（核心）交互的環境。	Kernel 是作業系統的核心，負責管理硬體資源和提供系統服務。
位置	user space 作為使用者與核心之間的橋樑。	kernel space 直接與硬體交互。
功能	1. 接受使用者輸入的命令並解釋執行 2. 提供命令列介面（CLI）或腳本執行 3. 呼叫系統呼叫與核心交互	3. 管理行程、記憶體、硬體設備 2. 處理系統呼叫 2. 排程任務和中斷管理
執行環境	作為使用者行程運行，透過系統呼叫請求核心服務。	運行在 S-mode ，直接控制硬體或透過 SBI 與 M-mode 交互。
類型	多種類型（如 Bourne Shell、Bash、C Shell），內文簡單自定義 shell。	可分為微核心、整塊性核心、混合式核心等設計，教學文件實作的較偏向於整塊性核心。
與硬體的關係	間接，透過核心存取硬體資源。	直接，管理 CPU、記憶體、I/O 設備等硬體資源。
教學文件中的交互	使用者輸入命令（如 `hello`），透過 `getchar` 讀取，`putchar` 輸出結果。	處理系統呼叫，呼叫 `sbi_call` 輸出到 debug console 與硬體交互。

特性 Shell Kernel

定義 Shell 是一個使用者介面程式，提供使用者與作業系統（核心）交互的環境。 Kernel 是作業系統的核心，負責管理硬體資源和提供系統服務。

位置 user space
作為使用者與核心之間的橋樑。 kernel space
直接與硬體交互。

功能 1. 接受使用者輸入的命令並解釋執行
2. 提供命令列介面（CLI）或腳本執行
3. 呼叫系統呼叫與核心交互 3. 管理行程、記憶體、硬體設備
2. 處理系統呼叫
2. 排程任務和中斷管理

執行環境 作為使用者行程運行，透過系統呼叫請求核心服務。運行在 S-mode ，直接控制硬體或透過 SBI 與 M-mode 交互。

類型多種類型（如 Bourne Shell、Bash、C Shell），內文簡單自定義 shell。可分為微核心、整塊性核心、混合式核心等設計，教學文件實作的較偏向於整塊性核心。

與硬體的關係 間接，透過核心存取硬體資源。直接，管理 CPU、記憶體、I/O 設備等硬體資源。

教學文件中的交互 使用者輸入命令（如 hello），透過 getchar 讀取，putchar 輸出結果。處理系統呼叫，呼叫 sbi_call 輸出到 debug console 與硬體交互。

monolithic kernel 不能翻譯為「宏核心」，參見淺談 Microkernel 設計和真實世界中的應用

shell 和 kernel 層級差異太大，沒有比較的必要。

參考 wikipedia ，將 monolithic kernel 的翻譯更正為「整塊性核心」。

根據淺談 Microkernel 設計和真實世界中的應用與 wikipedia 等資料，簡單對 microkernal 與 monolithic kernel 做比較。

特性	Monolithic Kernel (整塊性核心)	Microkernel (微核心)
結構與設計	所有功能運行於 kernel space ，作為單一二進位執行檔以監管者模式執行，應用程式透過系統呼叫交互	核心僅負責基本功能（如定址空間管理、執行緒管理、行程間通訊），服務運行於 user space，透過訊息傳遞交互
設計理念	整合所有組件為單一核心，強調簡單性與高效能	最小化核心功能，模組化服務，強調穩定性與彈性
示例作業系統	GNU/Linux、FreeBSD、Solaris、OpenVMS	QNX（黑莓 10）、L4 家族（seL4）、MINIX 3、Mach（GNU Hurd、Mac OS X 基礎）
優點	設計簡單，通訊成本低，函式呼叫高效，能動態載入或解除安裝模組以提升靈活性	耦合度低，易於除錯與移植，單一組件失效不影響整體，程式碼精簡（如 MINIX 3 小於 6000 行）
缺點	移植性差，模組錯誤可能導致系統崩潰，程式碼高度耦合	行程間通訊（IPC）耗時，涉及環境切換導致延遲，造成效能不如整塊性核心
應用場景	桌面與伺服器系統（如 Linux），適合高性能需求	即時系統（如 QNX 汽車系統）、嵌入式設備、高安全性場景（如 seL4 軍事應用）
運作方式	單一核心空間處理所有系統呼叫，硬體直接交互	多行程結構，核心作為中介，服務獨立運行，支援分散式系統
效能與穩定性	執行速度快，但穩定性依賴設計完善，硬體複雜性增加挑戰	第二代微內核（如 L4）優化 IPC 提升效能，數學驗證（如 seL4）確保穩定性
發展趨勢	主流地位穩固，支援動態模組化，混合核心（如 Windows NT、Mac OS X）融合其特性	在虛擬化、雲端、嵌入式領域崛起，第一代（如 Mach）較「胖」，第二代（如 QNX、L4）更精簡
程式碼規模	較大，依賴模組化減少核心空間大小	通常小於 10,000 行，減少潛在 Bug

15. Disk I/O

virtio specification

Virtqueue 結構與運作

Virtqueue 是 VirtIO 的核心資料結構，用於管理磁碟請求（request），包含描述子域（Descriptor Area）、可用環（Available Ring）與已用環（Used Ring）。運作流程如下：

驅動程式在描述子域中填寫描述子，指定請求的記憶體位址（例如讀寫的緩衝區）、長度（通常為 512 bytes，扇區（Sector）大小）和其他屬性（例如是否可寫）。一個請求可能由多個描述子組成，形成一個連鎖描述子（descriptor chain），以支援 Scatter-Gather I/O 。
驅動程式將連鎖描述子的頂部描述子索引（head descriptor index）加入可用環的 ring 陣列。接著更新可用環的 index ，表示有新請求。
驅動程式寫入 virtio 的 MMIO 暫存器（VIRTIO_REG_QUEUE_NOTIFY），通知裝置有新的請求等待處理。
裝置從可用環讀取連鎖描述子的頂部描述子索引，並根據描述子的資訊，存取指定的記憶體區域（例如讀取或寫入資料）。處理完成後，裝置將連鎖描述子的頂部描述子索引寫入已用環的 ring 陣列，並更新 index。
驅動程式檢查已用環的 index ，確認請求是否完成（在教學文件中透過忙碌等待實做），最後根據已用環的資訊，處理結果（例如檢查狀態或複製讀取的資料）。

Virtqueue 程式碼實現

在 kernel.h 中定義的 Virtqueue 結構使用 __attribute__((packed)) 確保與裝置記憶體布局一致，並設定 VIRTQ_ENTRY_NUM 為 16，限制每個 Virtqueue 最多支援 16 個描述子。

初始化 Virtqueue 的 virtq_init 函式負責配置記憶體並確保對齊頁面大小。函式將 Virtqueue 的索引初始化為 0，並透過 virtio_reg_write32 函式寫入記憶體映射輸入輸出（MMIO）暫存器，設置 Virtqueue 的參數，包括根據索引選擇目標佇列、寫入 VIRTIO_REG_QUEUE_NUM 定義佇列大小、確保佇列對齊，以及設置佇列的實體位址。最後，函式返回 Virtqueue 結構的指標，供後續輸入輸出操作使用。

提交請求的 virtq_kick 函式將描述子索引加入可用環，使用模運算防止陣列溢位。為確保記憶體操作順序，函式呼叫 __sync_synchronize()，避免編譯器或 CPU 重排指令。隨後，函式寫入 VIRTIO_REG_QUEUE_NOTIFY 暫存器，通知裝置處理新請求。

檢查請求狀態的 virtq_is_busy 函式透過比較 last_used_index 與 used_index，判斷裝置是否仍在處理請求，若索引不同則表示處於忙碌狀態。

處理輸入輸出請求的 read_write_disk 函式首先透過 virtio_blk_req 結構建立請求，指定目標扇區編號與讀寫類型。接著，函式構建描述子鏈，包含三個描述子：第一個描述子指向唯讀的請求（type、reserved、sector），佔 16 位元組（4 + 4 + 8），設置 VIRTQ_DESC_F_NEXT 旗標表示後續還有描述子；第二個描述子指向資料緩衝區（data），長度為 512 位元組（SECTOR_SIZE），位址從請求結構偏移 16 位元組計算，若為讀取操作則設置 VIRTQ_DESC_F_WRITE 旗標允許裝置寫入，否則保持唯讀，並附加 VIRTQ_DESC_F_NEXT；第三個描述子指向狀態欄位（status），長度為 1 位元組，位址偏移 528 位元組（4 + 4 + 8 + 512），設置 VIRTQ_DESC_F_WRITE 旗標允許裝置寫入完成狀態（0 表示成功）。函式透過 virtq_kick 提交請求，採用忙碌等待監控處理進度，完成後檢查 status 欄位，並在讀取操作時將資料複製到指定緩衝區。

執行之後，發現 .txt 檔案可以被完整寫入，但是 capacity 總是表示為 0

$ ./run.sh

virtio-blk: capacity is 0 bytes
first sector: Lorem ipsum dolor sit amet, consectetur adipiscing ...

$ head lorem.txt 
hello from kernel!!!
amet, consectetur adipiscing elit. In ut magna consequat, cursus velit ...

16. File System

基於 Tar 格式的檔案系統

在 kernel.c 中實作了一個基於 tar 格式的簡單檔案系統，將檔案內容儲存於記憶體，並透過系統呼叫提供應用程式存取。該檔案系統以 tar 檔案作為儲存媒介，利用其簡單的結構模擬檔案系統功能，適合教學用途。核心透過 fs_init 函式在系統啟動時從磁碟讀取 tar 檔案，逐一解析並儲存至 files 陣列。該函式走訪所有磁區，使用 read_write_disk 函式將磁碟內容載入 disk 的緩衝區，並透過偏移量 off 追蹤當前位置，將 disk[off] 轉為 tar_header 結構以存取檔案標頭。檔案大小由 oct2int 函式從八進位字串解析，隨後設置 files 陣列中的檔案狀態（in_use 為真）、檔名、內容及大小，並將偏移量推進至下一個檔案標頭，確保與磁區大小對齊。fs_flush 函式將 files 陣列中的檔案內容重新格式化為 tar 檔案並寫回磁碟。首先，生成空的 disk 緩衝區，走訪有效檔案，為每個檔案生成 tar_header 後，設置檔名、權限（"000644"）、格式（"ustar"）、版本（"00"）及檔案類型（'0' 表示普通檔案）。檔案大小轉為八進位字串，檢查碼初始為空格字元的 ASCII 值乘以欄位長度，再計算開頭所有位元總和，最後更新檢查碼。檔案內容複製至開頭後的資料區，偏移量依磁區對齊推進，最後透過 read_write_disk 函式將緩衝區寫回磁碟。fs_lookup 函式根據檔名在 files 陣列中查找檔案，逐一比較檔名，若匹配則返回檔案指標，否則返回空指標。oct2int 函式將 tar 開頭的八進位字串轉為十進位整數，支援檔案大小的解析。

系統呼叫與使用者指標存取

檔案系統透過 readfile 和 writefile 命令，系統呼叫支援應用程式存取檔案，分別對應 SYS_READFILE 和 SYS_WRITEFILE ，用來接受檔名、緩衝區指標及長度作為參數。藉由 handle_syscall 函式處理這些呼叫，並呼叫 fs_lookup 函式查找檔案，若未找到則返回錯誤。讀取時，核心將檔案內容複製至使用者緩衝區；寫入時，將使用者緩衝區內容複製至檔案並呼叫 fs_flush 函式來更新磁碟。為確保安全，核心需處理使用者指標存取，因為直接引用使用者提供的指標（如檔名或緩衝區）可能導致存取核心記憶體的風險。

在 RISC-V 中，監督者模式（S-mode）預設無法存取使用者模式（U-mode）分頁，除非設置 sstatus 暫存器的 SUM 位元（Supervisor User Memory access）。核心在 user_entry 函式中設置 SSTATUS_SUM，允許監督者模式存取使用者分頁，解決分頁錯誤問題，但需謹慎驗證指標有效性以避免安全漏洞。

06-12 課程討論筆記

Timer：作業系統的心臟

Linux 核心設計: Timer 及其管理機制

Timer 與排程器（Scheduler）的關係

Timer 是作業系統的主體元件（core component），常被喻為作業系統的心臟，因其驅動排程器運作，確保系統資源的有效配置與多工處理。作業系統仰賴排程器決定行程的執行順序與時間配置，而排程器的運作依賴 Timer 提供定期的時間中斷，觸發行程切換與資源重新配置。在 Linux 核心中， Timer 透過硬體時鐘產生固定週期的时间中斷，稱為系統嘀嗒（system ticks），每次中斷促使排程器檢查當前行程的執行狀態，決定是否切換至其他行程，實現分時多工（time-sharing multitasking）。 Timer 還支援行程的超時處理與延遲操作，例如喚醒處於睡眠狀態的行程或處理逾時事件，確保系統即時響應。若無 Timer 的驅動，排程器將無法有效運作，行程可能長期佔用 CPU，導致系統停滯。因此， Timer 作為時間管理的基礎，支撐作業系統的動態運行，猶如心臟為系統提供節奏。

OS Tick 與節拍器角色

OS tick 是作業系統用於計量時間的基本單位，透過硬體 Timer 產生的週期性中斷達成，猶如節拍器為系統提供穩定的時間節奏。在 Linux 核心中，OS tick 通常以固定頻率（例如每毫秒一次）觸發，驅動排程器更新行程的執行時間、檢查系統資源狀態，並執行時間相關的操作，如 Timer 超時或延遲任務的處理。每個 tick 代表一個時間片（time slice），作業系統利用這些時間片配置 CPU 資源，確保多行程公平執行。OS tick 的頻率影響系統的即時性與開銷：較高的頻率提升響應速度，但增加中斷處理的負擔；較低的頻率則降低效能。

記憶體配置策略

連續記憶體配置中的 first-fit 與 best-fit 策略

作業系統在動態記憶體配置中常採用 first-fit 與 best-fit 兩種連續配置策略，以從可用記憶體區塊中選擇合適區塊（Block）滿足行程需求。first-fit 從可用區塊清單開頭開始搜索，選取第一個大小足以滿足需求的區塊進行配置。其簡單的實現方式確保快速搜索，一旦找到合適區塊即停止，減少計算開銷。然而，first-fit 可能過早分割較大區塊，產生較多小碎片，降低記憶體利用效率。相較之下，best-fit 走訪所有可用區塊，選擇大小最接近需求的最小區塊，旨在減少分割後的剩餘空間，保留較大區塊供後續使用。此策略有助於提升記憶體利用率，但因需檢查整個清單，時間開銷較高，效率在區塊數量多時下降。

外部碎片（External Fragmentation）的產生、影響與解決方案

外部碎片是指連續記憶體配置中，可用記憶體區塊分散於已配置區塊之間，儘管總可用記憶體足夠，但因不連續而無法滿足較大記憶體需求的現象。first-fit 策略從清單開頭配置，易將大區塊分割成小片段，增加外部碎片。best-fit 雖選擇最小合適區塊，但頻繁配置與釋放仍可能生成分散的小區塊，累積外部碎片。外部碎片降低記憶體利用率，限制系統配置較大連續記憶體的能力，影響效能。為解決外部碎片，作業系統可採用記憶體壓縮，透過重新排列已配置區塊合併分散的可用區塊，形成較大連續空間，但此過程需暫停行程並耗費 CPU 資源，適用性受限。另一常見方法是使用分頁機制，將記憶體分割為固定大小的分頁，行程的虛擬位址透過分頁表映射至非連續的實體分頁，徹底消除外部碎片，儘管可能引入內部碎片。進階策略包括記憶體池或伙伴系統（buddy system），透過預配置固定大小的區塊或合併相鄰空閒區塊，減少碎片產生。這些解決方案在複雜度與效能間權衡，需根據系統需求選擇適宜方法，以提升記憶體利用效率並維持穩定性。

記憶體管理單元（MMU）與寫入時才複製（Copy-on-Write, CoW）機制

記憶體管理單元（MMU）

是電腦硬體中負責處理 CPU 記憶體存取請求的主體元件，透過將程式使用的虛擬位址映射至實體記憶體位址，實現高效的記憶體管理。它利用分頁或分段機制，將虛擬記憶體空間分割成小單位（通常為分頁），確保不同程式或行程的記憶體存取互不干擾。MMU 管理 CPU 快取與匯流排仲裁（bus arbitration），在較簡單的架構中也負責儲存裝置切換。其記憶體保護功能為每個行程配置獨立的虛擬定址空間，透過作業系統管理的分頁表與 MMU 的權限檢查，防止行程直接存取彼此記憶體，提升安全性，阻擋惡意或錯誤程式危害敏感資料。若行程因存取無效位址引發分頁錯誤，MMU 通知作業系統終止該行程，確保其他行程不受影響，維持系統穩定性。這種隔離支援多工處理（multitasking），讓多個程式同時運行，每個程式認為自己獨占記憶體，提高系統效率。MMU 利用分頁表項或 TLB 設置讀、寫、執行權限，防止存取未配置記憶體，保護核心記憶體免受使用者程式修改，同時支援虛擬記憶體，讓程式無需關心實體記憶體位置，簡化設計並提升記憶體使用效率。

寫入時才複製（Copy-on-Write, CoW）機制

一種延遲複製的記憶體管理策略，旨在減少不必要的記憶體複製，提升實體記憶體使用效率。當多個行程共享同一記憶體分頁時，作業系統不會立即複製分頁，而是等到某行程嘗試修改時才進行複製。例如，執行 fork() 操作時，子行程（child process）繼承親代行程（parent process）的記憶體，初始共享相同的實體分頁，這些分頁被標記為唯讀。當任一行程試圖寫入共享分頁時，作業系統檢測到違反唯讀權限，觸發分頁錯誤，隨即複製分頁到新的實體記憶體位置，更新寫入行程的分頁表，授予寫入權限，其他行程繼續使用原始分頁。CoW 的優勢在於節省記憶體，僅在必要時配置新頁面，適用於行程創建場景，如 fork() 操作中的親代行程與子行程共享記憶體，或多行程共享唯讀資料，僅需一份實體副本。CoW 常與需求分頁（demand paging）結合，進一步最佳化虛擬記憶體管理。

MMU 與 CoW 的關係

MMU 與 CoW 機制搭配可達成高效的虛擬記憶體管理與行程隔離。MMU 透過分頁表項將 CoW 的共享分頁標記為唯讀，確保行程無法直接修改共享記憶體。當行程嘗試寫入時，MMU 因權限違反觸發分頁錯誤，其硬體分頁錯誤訊號快速通知作業系統，啟動 CoW 的複製流程。作業系統的分頁錯誤處理程式複製頁面到新的實體記憶體，更新寫入行程的分頁表，授予寫入權限，確保其他行程不受影響。MMU 的 TLB 加速虛擬位址轉換，分頁表項記錄權限資訊，支援 CoW 的精確權限檢查。這種搭配減少記憶體複製開銷，僅在寫入時配置新頁面，節省實體記憶體，同時保證行程間的記憶體隔離，修改後的頁面僅對寫入行程可見，維護系統安全與穩定。

注意用語:

task 是「任務」;work 是「工作」
「陷阱」在漢語是貶義，但在 CPU 語境中，trap 是常見操作，沒有貶義，因此不要翻譯 trap
避免「中斷處理（trap）」這樣的書寫方式，針對語境去聲明
避免濫用「協同」，其意義是「共同」。可將「與 SUM 和 MPRV 欄位協同」改為「搭配 SUM 和 MPRV 欄位」
TLB 不要翻譯為「轉譯後備緩衝區」，保留原文
區分 trigger (觸發) 和 drive (驅動)，前者著重事件，例如「觸發」中斷、「觸發」排程器，後者著重於狀態的變遷，例如裝置「驅動」程式 (讓硬體從沒有作用，到開啟特定功能)

TLB 與 TLB miss

TLB 機制

TLB 是 MMU 中的一種高效硬體快取（cache），專為加速虛擬位址到實體位址的轉換而設計。快取是一種位於 CPU 內部的高速記憶體，用於儲存頻繁存取的資料，以減少對較慢主記憶體的存取次數，從而提升系統效能。TLB 作為快取，儲存最近使用的分頁表項，包含虛擬頁碼（virtual page numbers，VPN）與實體頁框號（physical frame numbers）的映射，以及讀、寫、執行等權限資訊，顯著降低查詢主記憶體分頁表的時間成本。TLB 位於 CPU 內部，靠近 MMU，採用全關聯（fully associative）或集合關聯（set-associative）的記憶體結構，支援快速查找。當 CPU 發出虛擬位址的存取請求時，MMU 檢查 TLB，若找到對應的分頁表項（即 TLB hit），即可直接獲取實體頁框號，結合偏移量計算實體位址，實現高效轉換。這種快取機制大幅提升分頁系統的地址轉換效率，對虛擬記憶體的效能至關重要。TLB 項由作業系統或 MMU 硬體管理，在行程切換或分頁表修改時更新，確保映射資訊的正確性。

TLB miss

當 TLB 無法提供虛擬位址的對應分頁表項時，發生 TLB miss 。MMU 需查詢主記憶體中的分頁表以獲取映射資訊。此過程涉及多級分頁表的逐層查詢，造成多次存取記憶體，導致較高的延遲。查詢完成後，MMU 將找到的分頁表項載入 TLB，必要時根據特定策略替換舊項，隨後完成位址轉換。若分頁表中無有效映射，例如分頁尚未載入記憶體， MMU 會觸發分頁錯誤，交由作業系統處理。作業系統可能從磁碟載入所需分頁，更新分頁表，並重新載入 TLB，確保後續存取順利進行。為降低 TLB miss 的開銷，現代 CPU 支援定址空間識別碼（Address Space Identifiers），允許不同行程的 TLB 項共存，減少行程切換時的清除需求。

proncons problem fix

為什麼需要兩組 sem
sem 改成 mutex
執行解釋運作

proncons 出現第二個消費者

Linmo

相傳宋太祖年間，福建莆田有個女孩出生時沒哭，父親便取名「默」，稱林默。因當時習俗，女孩單名常加個「娘」字，所以又叫「林默娘」。她就是後來人們熟知的媽祖，天上聖母。本專案取名 Linmo，以致敬天上聖母在凡間的姓氏。

Linmo 目前支援 RV32I，特徵:

Minimal kernel footprint
Lightweight task model where all tasks share the same memory region
Preemptive and cooperative scheduling based on priority round-robin and a user-defined real-time scheduler
Task synchronization and communication via semaphores, pipeline channels, or message queues
Software timers with callback support
Dynamic memory allocation
A small C library bundled with a data structures library

筆記

程式碼的設計

在 kernel/task.c 中，對於 yeild 相關程式碼的定義如下：
```
void yield(void);

...

void _yield(void) __attribute__((weak, alias("yield")));

...

/* Cooperative context switch, called by a task voluntarily. */
void yield(void)
{
    ...
    stack_check();
    ...
}

...

void mo_task_yield(void)
{
    _yield();
}
```
先定義了核心層的 yield 函式負責協作式上下文切換，操作核心控制塊（kcb）與任務控制塊（tcb），透過呼叫 setjmp 和 longjmp 保存與恢復上下文，實現任務間的切換。接著以弱別名（weak alias）定義 _yield 函式，允許特定平台在編譯時提供客製化的上下文切換流程，例如針對特定暫存器或中斷機制的處理，而無需修改核心程式碼。若平台未提供自訂 _yield ，系統則回退至核心的 yield 函式實作，保證通用情況下的正常運作。這種靈活性讓核心程式碼保持平台無關，同時為硬體適配提供彈性。最後， mo_task_yield 函式作為公開 API，進一步保護核心邏輯，防止應用程式直接操作敏感的任務列表或上下文切換機制，降低誤用風險。它簡化使用者介面，與其他任務管理 API（如 mo_task_spawn、mo_task_delay）保持一致的命名風格，提升易用性。

在 yield 函式的實作中，執行上下文切換前，yield 會呼叫 stack_check 函式，檢查當前任務堆疊是否損壞，方法是驗證堆疊兩端的「金絲雀值」（STACK_CANARY），這是一種用於檢測堆疊溢出或記憶體損壞的魔術數字。透過這一核心級保護機制，系統能在潛在問題影響穩定性前及早發現異常，確保上下文切換的可靠性。

canary testing
magic number
靜態內嵌展開函式（static inline function）是 C 語言中常用於標頭檔的技術，旨在提升性能並保持模組化。

inline 屬性建議編譯器將函式程式碼直接嵌入呼叫處，取代傳統的函式跳躍，從而消除堆疊操作與呼叫開銷。例如，list_is_empty() 這樣的簡單檢查函式若每次呼叫都產生開銷，會影響效率；內嵌後，它直接展開為 return !list || list->length == 0U; 的高效檢查。static 則限制函式可見性，僅在包含標頭檔的編譯單元內有效，避免多檔案包含時的多重定義錯誤，減少連結器負擔。

在 include/lib/list.h 中，使用靜態內嵌展開函式定義與設計鏈結串列操作與相關函式，每個函式（如 list_create()、list_pushback()、list_pop()）遵循單一職責原則，專注於單一功能，保持程式碼清晰且易於維護，內嵌展開後也不會過於膨脹。為確保健壯性，函式內置錯誤檢查，處理無效輸入或記憶體配置失敗的情況，返回合理值（如 NULL）。鏈結串列採用頭尾哨兵節點設計，簡化邊界條件處理，減少條件檢查，使靜態內嵌展開函式更高效。同時，串列儲存 void * 資料指標，支援任意資料類型，確保函式的通用性與靈活性。

TODO：跟巨集的差異

Enable MMU for kernel isolation #1

ISA-privilged P.129 12.2. Supervisor Instructions
ISA-privilged P.133 12.3. Sv32: Page-Based 32-bit Virtual-Memory Systems
當前實作進度（暫存與整理中）

參考教學文件，我學習使用 SV32 初始化作業系統的 MMU ，但卻發現其實有很多細節需要好好注意，所以我決定再次好好了解 SV32 的分頁表架構，以及其他在實作上，需要考量到的議題與知識背景。

我目前對於 SV32 的認知如同前述在教學文件理解的一般粗淺，我只知道他是一個適用於監督者模式，確保應用程式與核心記憶體空間隔離的記憶體管理機制。閱讀完 ISA-privilged 後，我對 SV32 分頁表有更深層的認知。如同前面整理的一樣，SV32 的虛擬位址由 32 位元分割成 10 位元的

V P N [1]

、 10 位元的

V P N [0]

與 12 位元的

o f f s e t

，實體位址空間則由 34 位元，分別分割成 10 位元的

P P N [1]

、 12 位元的

P P N [0]

與 12 位元的

o f f s e t

。

V P N [1]

會指向第一級分頁表，而

V P N [0]

則會指向第二級的分頁表，其中，第一級分頁表中的分頁表項目（PTE），指向第二級分頁表的定址。儘管下圖是一張 SV32 的 magapage 示意圖，但是這張圖卻很好的展示了有關 SV32 實作分頁表的基礎概念。在圖片來源的原文網址中提到了 megapage 的大小計算：

1 P a g e = 4 K i B

1 P T E \to 1 P a g e

1 P a g e T a b l e \to 1024 P T E s

4 K i b \times 1024 = 4 M i B

SV32 的分頁表項的格式如下圖：

前 12 位元是

P P N [1]

，中間 10 位元是

P P N [0]

（若為 leaf 則為 0），最後則是共計 10 位元的權限設定，包括以下：

RSW (Reserved for Supervisor Use, 位9:8)：保留給監督者使用。
D (Dirty, 位7)：1 表示分頁被寫入，硬體可選擇性更新。
A (Accessed, 位6)：1 表示分頁被存取，硬體可選擇性更新。
G (Global, 位5)：1 表示全局分頁（在所有ASID間共享），保留供未來使用，需清零。
U (User, 位4)：1 表示使用者模式可存取，0 僅限特權模式（M/S模式）。
X (eXecutable, 位3)：分頁可執行。
W (Writable, 位2)：分頁可寫。
R (Readable, 位1)：分頁可讀。
V (Valid, 位0)：有效位，1 表示 PTE 有效，0 表示無效（觸發分頁錯誤）。

下方則是一張虛擬位址被配置到分頁表中轉換成實體位址的示意圖：

轉換過程的第一步是配置記憶體，每一級分頁表需要對齊 4 KiB，然後初始化 satp 暫存器，它包含了

P P N

以及 ASID ，負責用來分辨不同的定址空間。接著就開始填充分頁表：第一級分頁表根據

V P N [1]

指向第二級分頁表或直接映射 megapage ；第二級分頁表則根據

V P N [0]

映射 4KiB 分頁，設定權限和 V 位。完成後，用 SFENCE.VMA 指令同步 TLB，確保映射的有效性。測試時要特別注注意檢查轉換位址的正確性，如果發生分頁錯誤，則需要調整 PTE ，並檢查相關的 CSRs 暫存器，像是 scause 和 stval 。

接續前述談到的 TLB ，當分頁表更新之後，TLB 內部可能還有存在舊有的映射紀錄，導致與當前的分頁表不一致。這時候 SFENCE.VMA 就是一個很關鍵的指令，透過圖片我們可以清楚知道 rs1 指定虛擬位址，rs2 指定 ASID：

藉由執行指令後， TLB 會根據 rs1 與 rs2 來決定無效化舊有的映射內容的範圍，並後續轉換映射新的分頁表。其中，如果 rs1 與 rs2 都是

x 0

，則會直接清空所有的 TLB entry 。這種作法儘管適用於廣泛更新，但在頻繁的使用下，卻會容易發生 TLB miss 影響系統的效能。此外，硬體處理 TLB 的無效化可能會有延遲，軟體必須考慮時序的問題，避免轉換發生錯誤。

提到 TLB 就不得不談有關快取（cache）的部分，VIVT （Virtual Indes Virtual Tag）架構下的快取使用虛擬位址進行索引和標籤比對，意味著快取查找完全基於虛擬位址，無需等待 TLB。這樣的原因導致查找的速度很快，但同時也容易產生 aliasing 的問題，也就是不同任務的虛擬位址可能指向了不同的實體位址，導致快取中的資料不一致。相比之下，VIPT （Virtual Indes Phisical Tag）快取用虛擬位址索引，但標籤檢查用使用實體位址，必須依賴 TLB 提供實體頁框號（physical frame numbers）。使用上儘管比 VIVT 更靈活，允許不同的任務共享快取中的資料，但是仍舊有機會發生 aliasing 的問題，這次問題發生的原因則是不同任務的虛擬位址可能指向了同一個實體位址，導致快取中有多份副本的產生。

其中有一種解決辦法是 Page Coloring，主要原理是將實體記憶體非頁依照快取集合（set）分為不同的「顏色」，並在配置分頁時選擇特定顏色的實體分頁，確保虛擬位址映射到快取中的同一集合中。通過限制實體分頁的配置，使不同虛擬位址索引到相同的快取集合，藉此消除衝突，確保快取只儲存一份資料副本，解決 VIVT 和 VIPT 快取的 aliasing 問題同時，提高快取命中率並維持資料一致性。

TODO：
實作部分
~~- 除錯完成，確保原先程式皆可正常運作。~~
根據期末展示報告當天與老師的簡單問答，先從實作 PMP（physical memory protection）開始
先閱讀 ISA-privilged 3.6 與 3.7

理論

linus talk about page coloring

突發所想，光是 linmo 如此體量小的程式碼，我就有點無從下手了…，想到一個多月前觀看教材時，會查找 linux 核心的程式碼，當時對那個龐大的程式碼只是感嘆，現在真的參與開發才能理解，要為其作出貢獻是一件多麼難能可貴的事情。

Exception occurs in condition variable application #6

透過程式報錯確認：

[EXCEPTION] code=1 (Instruction access fault), epc=80000538

這意味著異常是由於嘗試存取無效的指令記憶體位址（或記憶體權限問題）引起的。 epc=80000538 是異常發生時的程式計數器（PC），指向引發異常的指令，但目前無法直接映射到具體程式碼行

調整 mutex_tester() 函式，提供更好的除錯資訊，以及藉由 kernel/task.c 中的 mo_task_cancel() 函式，增加條件判斷式，檢查任務是否持有互斥鎖或在條件變數等待列表中，並執行命令後得到：

Linmo is starting...
...
produced 126
consumed 126
produced 127
trylock busy – OK
[EXCEPTION] code=1 (Instruction access fault), epc=80000538

並在少數情況下得到：

Linmo is starting...
...
consumed 128
produced 129
consumed 129
trylock succeeded – unlocking
timedlock succeeded – unlocking
cannot cancel self – entering idle loop
[EXCEPTION] code=1 (Instruction access fault), epc=80000538

為了測試 mutex_tester() 函式是否為造成問題的主因，我先將其自 app_main() 中進用，結果發現依舊會報錯 [EXCEPTION] ，可以確認問題與 mutex_tester() 函式以及其內使用的函式無關。

接著我將視角轉至 app_main() 末端的程式碼 return 。透過將回傳的數值由 1 更改為 0 ，也就是從搶佔模式變成非搶佔模式後發現，程式碼不再報錯。綜合以上的推論，猜測問題是發生在上下文切換或是中斷處理（定時器）的過程中。

首先，我嘗試修復 longjmp 函式中，未回傳 mepc 的狀況，並透過 _panic() 函式增加回傳mepc 與堆疊指標（sp）的日誌輸出，得到以下資訊：

Linmo is starting...
heap_init(), 130013020 bytes free
task 0: entry=80000334 stack=800029c0 size=4096
task 1: entry=80000288 stack=80003a40 size=4096
task 2: entry=8000022c stack=80004ac0 size=4096
task 3: entry=80000200 stack=80005b40 size=4096
Task 0 produced 0
Task 0 (producer) signaling

*** STACK CORRUPTION: task 0 base=800029c0 size=u

*** KERNEL PANIC (4294950924) – stack corruption
Panic: mepc=0, sp=80003970

接著，我對 kernel/mutex.c 中的 mo_cond_wait() 函式新增 while 迴圈 while (mo_mutex_trylock(m) != ERR_OK) 確保函式在 CRITICAL_ENTER/CRITICAL_LEAVE 之間不會被定時器中斷打斷後。

修復後的通過命令測試顯示，*** STACK CORRUPTION 問題消失，輸出如下：

Linmo is starting...
...
Task 0 produced 35
Task 0 (producer) signaling
Task 1 consumed 35
Task 1 (consumer) signaling
Task 3 (idle) yielding
Task 0 produced 36
Task 0 (producer) signaling
Task 1 consumed 36
Task 1 Task 3 (idle) yielding
(consumer) signaling
trylock busy – OK
Task 2 (mutex_tester) yielding
Task 3 (idle) yielding
[EXCEPTION] code=1 (Instruction access fault), epc=80000544

根據測試結果，修復 longjmp 、mo_cond_wait 函式有效解決了 *** STACK CORRUPTION 問題，但例外非法指令需進一步測試。

已被老師解決
commit e708a4a
commit a96b267

避免 ChatGPT 風格的書寫方式，清楚書寫自己的認知

瀏覽完老師的 commit 更動後，我發現我查找錯誤的方向不太正確。儘管後續，程式碼在處理上下文切換的部分的確有不完善之處，但是關於 app/cond.c 的例外錯誤修正，我應該更關注在行程同步的部分，並透過理論知識去確認 kernel/mutex.c 與 kernel/semaphore.c 程式碼，有沒有需要改進與修正之處。所以我決定先再次複習行程同步的相關知識：

Semaphore 是一種靈活的同步機制，透過一個計數器管理多執行緒對共享資源的存取，廣泛應用於資源配置與任務協調。並且分為兩大類： Counting semaphore ，或稱為 General semaphore ，允許任意非負整數計數，適合控制有限資源； Binary semaphore 則限制計數為 0 或 1，與 mutex 作法相似，但更為通用。執行緒透過 wait 操作檢查並減少計數器，若資源不足則阻塞，並透過 signal 增加計數器並喚醒等待中的執行緒。

Mutex 確保同一時間僅一個執行緒能存取共享資源，適合保護臨界區段以防止資料競爭。 mutex 強調所有權，僅鎖的持有者可以解鎖，以此提升安全性。執行緒透過 lock 取得鎖，若鎖已被佔用則阻塞，並透過 unlock 釋放鎖來喚醒等待者，至於 trylock 則是提供非阻塞存取（non-blocking access）。部分 mutex 支援遞迴鎖定，允許同一個執行緒進行多次鎖定。條件變數則是一種與 mutex 搭配的同步機制，允許執行緒在特定條件滿足時被喚醒，有效避免忙碌等待的資源浪費。執行緒透過 wait 釋放相關的 mutex 並進入等待狀態，直到條件滿足後才重新取得鎖，而 signal 是喚醒一個等待執行緒，broadcast 則是喚醒所有等待者。

綜上可以理解為何在設計 Linmo 作業系統時，老師選擇將 sempahore 相關的程式碼，單獨寫進 kernel/semaphore.c ，並將 mutex 與條件變數的內容合放在 kernel/mutex.c 之中。

mutex 和 semaphore 保留原文，不要翻譯，不然會跟漢語的「互斥」(有時描述二個人不合拍，王不見王) 混淆

收到

接著回頭看 commit 內容。在 commit e708a4a 中，老師對所有函式新增空指標檢查來防止為定義的行為，並在遇到錯誤處理時回傳更精確的巨集定義（像是 ERR_FAIL、ERR_TASK_BUSY）。而在條件變數的 wake 操作中，則是明確使用 CRITICAL_ENTER 和 CRITICAL_LEAVE 來保護與等待鏈結串列，

-/* wake exactly one waiter if present */
-static void cond_wake_one(cond_t *c)
+/* Wake exactly one waiter */
+static void cv_wake_one(cond_t *c)
 {
-    list_node_t *n = list_foreach(c->waiters, first_node, NULL);
-    if (n) {
-        tcb_t *t = n->data;
-        list_remove(c->waiters, n);
+    CRITICAL_ENTER();
+    if (!list_is_empty(c->waiters)) {
+        tcb_t *t = (tcb_t *) list_pop(c->waiters);
         t->state = TASK_READY;
     }
+    CRITICAL_LEAVE();
 }

並簡化鏈結串列的處理程式碼，棄用 list_foreach 改使用 list_is_empty 和 list_pop 函式。至於等待機制則以低功耗的 mo_task_wfi() 或 mo_task_yield() 取代 mo_task_delay(1)，降低功耗。

 int mo_cond_wait(cond_t *c, mutex_t *m)
 {
     /* omitted */
 
-    mo_task_wfi();           /* sleep until signaled      */
-    return mo_mutex_lock(m); /* re-acquire mutex          */
+    /* Release the mutex while sleeping */
+    mo_mutex_unlock(m);
+    mo_task_yield(); /* switch away */
+
+    /* Re-acquire before returning */
+    return mo_mutex_lock(m);
 }

調整完 kernel/mutex.c 後，老師接著調整 app/cond.c 的程式碼。重點在於 mutex_tester() 在使用 mo_task_cancel() 函式後加入無限迴圈，不斷呼叫 mo_task_wfi()，避免未定義行為觸發異常。idle_task() 則將原先使用的 mo_task_yield() 函式替換為 mo_task_wfi() ，藉此降低不必要切換，提升系統穩定性與功耗效率。通過以上更動，來解決 app/cond.c 在執行一段時間後在 produced N / consumed N 卡住的問題。

老師在 commit a96b267 中寫道：

Both producer and consumer now wrap each mo_cond_wait() call in a loop that re-checks the buffer-state predicate.

但由於 while 迴圈在消費者與生產者任務中的程式碼，在本次的 commit 內容中其實並未受到新增或更動，而是維持原樣。所以我選擇將其默認為原先在設計 app/cond.c 程式碼時就有被考量進去的部分，而非解決 issue #6 的關鍵。

在設計上，producer 和 consumer 函式中，新增 while (data_ready) 和 while (!data_ready) 迴圈，是用來確保任務在喚醒後重新檢查條件。防止發生像是，當有一方呼叫 mo_cond_wait() 時，此時對方也任務發送了 mo_cond_signal()，則 signal 操作可能被忽略，間接導致任務進入 mo_cond_wait() 後無法被 wake 操作，造成死結（deadlock）的發生或是系統卡住。

在這兩個 commit 之後， kernel/mutex.c 的程式碼也是經歷許多更動。 mutex 在實作上不再依賴 Binary semaphore ，而是改成使用 mutex_t（包含等待中的 tcb 鏈結串列 waiters、擁有者 ID owner_tid 及魔術數字 magic）與 cond_t（包含等待中的 tcb 鏈結串列 waiters 及魔術數字 magic）結構，並新增 mutex_block_atomic 函式封裝阻塞邏輯，降低上下文切換的開銷並與條件變數共用 list_t 架構定義，提升一致性。接著恢復 mo_cond_timedwait 函式，但這次使用 deadline 計算超時並支援動態任務移除，解決之前因為競爭條件（race condition）選擇移除該功能的限制，同時新增 mutex 擁有權檢查，確保安全。此外，針對條件變數的部分，移除了 cv_wake_one/all 並將其明確定義為 mo_cond_signal/broadcast 來處理單一或所有執行緒的 wake 操作。最後則是在例外的處理上更為嚴謹，新增魔術數字驗證結構的完整性；無效操作會觸發 panic；支援各式錯誤訊息回報（如 ERR_NOT_OWNER、ERR_TIMEOUT），來提升系統的除錯功能。有趣的是，原先是使用 CRITICAL_ENTER 和 CRITICAL_LEAVE 來保護與等待鏈結串列，現在則是更改為使用 NOSCHED_ENTER/LEAVE 保護關鍵區段。

NOSCHED_ENTER/LEAVE 巨集被定義於 include/sys/task.h 之中，相較於 CRITICAL_ENTER/LEAVE ，這兩個巨集是設計類似 Linux 核心的 enable_preempt 和 disable_preempt，負責處理輕量的臨界區段，並主要用於保護被共享於任務之間的資料，特色是僅禁用排程器的 timer 中斷，但是允許硬體中斷，所以僅是阻止任務的切斷，而不會如同 CRITICAL_ENTER/LEAVE 禁用所有中斷的發生。

接著來總整理 kernel/mutex.c 的程式碼。定義 mo_mutex_lock 與 mo_mutex_unlock 函式，分別代表 mutex 的 lock 與 unlock 操作。兩者首先都先確保 mutex 的有效性。在 mo_mutex_lock 中，選擇使用非遞迴的鎖設計，捨棄遞迴鎖定的複雜性，以減少記憶體和計算開銷。若 mutex 已經被佔用，呼叫 mutex_block_atomic，將任務加入 waiters 鏈結串列中，並將任務設為 TASK_BLOCKED 狀態，最後藉著 _yield 讓出 CPU，來確保阻塞任務不浪費 CPU 資源。至於 mo_mutex_unlock 函式則將等待任務從鏈結串列的頭部取出，也是一種 FIFO 順序，而整個解鎖的過程被 NOSCHED 巨集保護，確保擁有者 id 的修改屬於 atomics 操作。其他函式如 mo_mutex_trylock 則是如同 mutex 的 trylock 操作一樣，提供非阻塞鎖定，若 mutex 空閒則立即獲取，否則返回 ERR_TASK_BUSY，這適合需要快速失敗的場景，減少阻塞開銷。mo_mutex_timedlock 則是如前述一樣支援超時等待，若在指定時間內未獲鎖則返回 ERR_TIMEOUT 。

再來看 kernel/semaphore.c 的實作手法。 Linmo 的 semaphore 是屬於 counting semaphore 。首先程式碼定義了一個控制區塊，並命名為 sem_t 的資料結構：

/* Semaphore Control Block structure. */
struct sem_t {
    queue_t *wait_q;        /**< Queue of tasks blocked on this semaphore. */
    volatile int32_t count; /**< Number of available resources (tokens). */
    uint16_t max_waiters;   /**< Maximum capacity of wait queue. */
    uint32_t magic;         /**< Magic number for validation. */
};

這個結構包含一個計數器，用來追蹤可用資源數量；一個 FIFO 等待佇列，負責儲存因資源不足而阻塞的任務；還有最大等待數與魔術數字，分別限制佇列的容量以及負責驗證 semaphore 的有效性。並定義了 mo_sem_create 函式負責動態配置並初始化 semaphore，semaphore 的 signal 函式被定義為 mo_sem_signal ，負責喚醒最早等待的任務或增加計數。mo_sem_wait 則是 semaphore 的 wait ，會在資源可用時減少計數，或將任務加入佇列之中，並標記為阻塞。但要注意的是，此時 semaphore 並沒有交出 NOSHECD 的鎖，藉此確保 atomics 操作的同時，也防止 race condition 的發生。，而 mo_sem_trywait 提供非阻塞檢查，僅在資源充足且無等待者時成功。其中，在 mo_sem_wait 與 mo_sem_trywait 這兩個函式中，特別設計一個判斷式，參考註解，也可以稱呼他為快速路徑，用意是讓程式在在資源充足且沒有任何等待者時，可以直接存取，藉此減少佇列操作的開銷，降低 CPU 負擔。而在程式碼的實作中，採用 FIFO 等待隊列是為了確保任務公平性，避免高優先級任務長期霸占，導致其他任務飢餓。此外， kernel/semaphore.c 也同樣的使用 NOSCHED_ENTER/LEAVE 這兩個巨集來保護計數器與佇列操作，防止多任務環境中 race condtion 。

考慮是否要整理有關 app 目錄中與同步行程有關的測試程式碼

注意用語：dirctory 是「目錄」，不是「資料夾」，atomics 用於並行程式設計和 CPU 行為時，不要翻譯為「原子」，真要翻譯，也該是「最小操作」。
參見 atomic 教材

藉此機會再次複習了 atomics 再並行程式上的相關知識。並再三考量後，決定先將「原子性」這個補述刪除。

Unexpected stall in message queue application #8

根據 app/mqueues.c 的程式碼，預期它應該依以下原理運作：

app_main 創建四個訊息佇列（mq1 ~ mq4），並置放一條虛設的初始訊息（payload 為 0） mq1 佇列之中（enqueue），觸發 task1 執行，隨後返回 1 啟用搶佔式排程。
task1 開始忙碌等待 mq1 的訊息，直到收到回覆訊息後將其列印出，並從佇列中移除（dequeue）。接著將計數器 val（初始 0，逐次遞增）作為 payload 置放 mq2 佇列中，並格式化字串 str（例如 "hello 0 from t1…"）後，將其置放 mq3 佇列中，最後讓出 CPU。

將整數 val 轉換為 void *（(void *) (size_t) val）
task2 檢查 mq2 訊息，收到後輸出訊息與 task1 的計數器（例如 "message 0"），然後將自己的計數器 val（初始 200，逐次遞增）置放 mq4 佇列中，並讓出 CPU。
task3 檢查 mq3 訊息，收到後輸出訊息與 task1 的字串（例如 "message: hello 0 from t1…"），然後將自己的計數器 val（初始 300，逐次遞增）置放 mq4 佇列中，並讓出 CPU。
task4 等待 mq4 至少兩條訊息，收到後輸出 task2 和 task3 的計數器（例如 "messages: 200 300"），延遲 100 毫秒後向 mq1 回傳虛設訊息，觸發 task1 後開始下一次迭代，形成任務間的訊息循環，最後讓出 CPU。

但根據輸出結果，當執行到步驟5時，整個程式運作停止進展（stall）：

task 1 enters...
task 2 enters...
message 0
task 3 enters...
message: hello 0 from t1...
task 4 enters...
messages: 200 300
(stall)

經過老師提示，推測是在上下文切換時出問題，導致無法順利回傳訊息給 mq1 佇列繼續觸發 task1 所造成的。通過觀察 arch/riscv/hal.c 與 arch/riscv/hal.h 程式碼發現， setjmp 函式保存了 18 個欄位的上下文，包括通用暫存器、 mcause 和 mepc 等，但未保存 mstatus 暫存器。此外， longjmp 函式在恢復上下文時同樣未處理 mstatus 的恢復，導致恢復的任務可能處於錯誤的中斷狀態或特權模式。為解決此問題，修補程式碼在 setjmp 和 longjmp 中新增對 mstatus 暫存器的處理。

首先藉由在 setjmp 函式新增讀取 mstatus 暫存器並保存至 jmp_buf 的第 18 個欄位，並將 jmp_buf 大小從 18 擴展至 19 以容納新欄位。並在 longjmp 函式中，使用 csrw 指令恢復 mstatus，確保中斷狀態和其他系統狀態在通用暫存器恢復前正確設置。

commit 762cb7c

在經過以上的修復後， app/mqueues.c 可以順利運行：

...
task 1 enters...
task 2 enters...
message 44
task 3 enters...
message: hello 44 from t1...
task 4 enters...
messages: 244 344

mstaus（機器狀態暫存器，Machine status register）

ISA-privilged P.29 3.1.6. Machine Status Registers

mstatus 暫存器是 RISC-V 架構在機器模式（M-mode）下的核心控制與狀態暫存器（CSR），負責管理執行環境，在 RV32 中為 32 位元，包含多個欄位，每個欄位對應特定的控制或狀態功能。

mstatus 暫存器透過 MIE、MPIE 和 MPP 欄位管理特權模式與中斷狀態。 MIE（位元 3）控制機器模式是否允許全局中斷，設為 1 時允許中斷觸發，設為 0 則禁用，影響所有由 mie 暫存器指定的中斷類型。 MPIE（位元 7）負責保存進入 trap 前的 MIE 狀態，當處理器進入 trap 時，MIE 會被清零以防止中斷干擾，MPIE 則記錄原 MIE 值；執行 mret 指令時， MPIE 的值恢復至 MIE，確保中斷狀態正確還原。MPP（位元 12:11）記錄 trap 前的特權模式，值為 00 表示 U-mode、01 表示 S-mode、11 表示 M-mode，執行 mret 時，處理器切換至 MPP 指定的模式。MPP 屬於 WARL（Write Any Values, Reads Legal Values）欄位，僅接受硬體支援的模式值。這些欄位形成狀態堆疊，確保例外發生或中斷處理中能正確保存與恢復環境，對於上下文切換至關重要。

MPRV、MXR 和 SUM 欄位共同管理記憶體存取與保護。MPRV（位元 17）控制修改特權功能，當設為 1 時，顯式記憶體存取使用 MPP 指定的特權模式進行權限檢查，而非當前模式，適用於模擬低特權模式存取，例如除錯（debug）或虛擬化場景。MXR（位元 19）允許將標記為可執行（分頁表項 PTE.X=1）的頁面視為可讀，當設為 1 時，支援從可執行頁面讀取資料，適合動態程式碼生成等應用。SUM（位元 18）控制監督者模式（S-mode）對使用者模式（U-mode）記憶體的存取，當設為 1 時，S-mode 可存取標記為 U-mode（PTE.U=1）的頁面，這在系統呼叫中尤為重要，例如安全存取使用者緩衝區。這些欄位確保記憶體存取的靈活性和安全性，是實現記憶體隔離的核心。

FS 欄位（位元 14:13）則是管理浮點數單元的上下文狀態，分為 Off（00）、Initial（01）、Clean（10）和 Dirty（11）四種狀態。當 FS 設為 00 時，執行浮點數指令會觸發例外非法指令；其他狀態則表示浮點數單元的不同使用情況。FS 欄位在上下文切換時幫助核心判斷是否需要保存浮點數暫存器，從而優化性能。在 RV32I 環境中，由於通常不支援浮點數擴展，FS 一般設為 00，簡化核心設計並降低開銷。

而 mstatus 暫存器常與其他 CSRs 配合，像是 mepc 暫存器記錄 trap 發生時的程式計數器，與 MPP 欄位配合，確保從 trap 返回時恢復正確的執行環境。 mcause 暫存器記錄 trap 原因，與 mstatus 的中斷欄位共同決定異常處理流程。 mie 暫存器受 MIE 欄位的控制，藉此決定開始的中斷類型。至於 satp 暫存器則是管理 S-mode 的分頁表轉換，搭配 SUM 和 MPRV 欄位，實現準確的記憶體存取管理。

'hello' and 'cond' application have no progress #10

在我繳交 commit 762cb7c 後，app/hello.c 與 app/cond.c 皆無法順利地執行，顯示出我在針對修復 app/mqueues.c 的程式碼更改後，沒有再次確認與檢查原有的程式碼是否有符合預期行為。

commit 784b235

結合上方關於 mstatus 暫存器的整理與老師提交 commit 針對 arch/riscv/hal.c 的更新內容，可以發現造成應用程式碼發生問題的原因，在於我並未正確處理 mstatus 的中斷啟用狀態（MIE），導致 timer 中斷無法觸發，進而影響多任務切換和同步機制的正常運作。

本課程中，所有的「核心」皆指作業系統的「核心」，針對其他語意，可改用「主要」、「關鍵」一類的詞彙替代

好的，之後會注意論述。

在 commit 中老師新增了 MSTATUS_MIE 和 MSTATUS_MPP_MACH 兩個巨集，分別對應 mstatus 的位元 3（機器模式中斷啟用）和位元 12:11（前一特權模式設為機器模式）。接著在 setjmp 函式中，原本是直接保存 mstatus 暫存器，但由於發生 trap 時 MIE 會被硬體清零，保存的值總是 MIE=0，導致後續恢復時中斷被禁用，timer 中斷無法觸發排程器。所以透過組合語言從 mstatus.MPIE（位元 7）提取中斷前的 MIE 狀態，經過移位和位元操作重建正確的 MIE 值，再保存到 jmp_buf 中，來確保上下文切換時中斷狀態能反映任務執行時的實際情況，除此之外，老師在 _context_init 函式中為新任務的 mstatus 暫存器設置了明確的初始值，將 MSTATUS_MIE 設為 1（啟用中斷）並指定 MSTATUS_MPP_MACH（機器模式），讓 app/hello.c 的任務切換和 app/cond.c 的同步操作恢復正常。

MSTATUS_MIE 和 MSTATUS_MPP_MACH 兩個巨集在 commit 851faac 之後，被定義在 arch/risc/csr.h 中。

Provide implementation hints for context switch #9

在老師的建議下，我參考了 linux 核心的 CPU Scheduler implementation hints for architecture specific code 文件，撰寫了關於 linmo 作業系統在 RISC-V (RV32I) 架構下的上下文切換與機器狀態管理相關內容。

commit a7a27c2

首先介紹了上下文切換的概念，其中額外針對 setjmp 與 longjmp 兩個函式做重新定義與額外說明。這兩個函式傳統上用於例外處理，但在 Linmo 作業系統中被重新賦予功能，專門用於儲存與恢復任務的 CPU 狀態。setjmp 函式負責將當前任務的 CPU 狀態保存至 jmp_buf 結構，該結構定義為包含 19 個 uint32_t 元素，涵蓋：

12 個通用暫存器（s0–s11）
4 個指標（gp、tp、sp、ra）
3 個控制狀態暫存器（CSRs，mcause, mepc, mstatus）。

在排程器選擇下一個任務後，longjmp 函式會從選定任務的 jmp_buf 恢復 CPU 狀態，繼續執行該任務於上次 setjmp 呼叫時的中斷點。接著，繼續探討機器狀態（mstate）的管理，聚焦在 mstatus 暫存器。其中特別提到，若 mstatus 處理不當，可能干擾排程的正確性，導致中斷遺失或任務執行異常。因此，在 longjmp 函式中，mstatus 被優先恢復，以確保中斷狀態在其他暫存器恢復前正確設定，維持系統穩定性。此外，對於新任務，系統會透過 hal_context_init 函式初始化其 jmp_buf，包括設定 MSTATUS_MIE 和 MSTATUS_MPP_MACH 兩個巨集，確保新任務開始時中斷功能已啟用，支援正常的排程與執行。

`rtsched` program does not work as expected #3

commit f5e44cb

這個問題已經被老師解決，但我想藉此機會回顧 commit 內容的同時，複習與整理排程器在 Linmo 作業系統中的實作。

Linux 核心設計: 不只挑選任務的排程器

Linmo 作業系統的排程器藉由定義在 include/sys/task.h 與 include/sys/timer.h 裡的資料結構，為任務的管理與 timer 操作提供基礎。單一任務由任務控制區塊（tcb_t）負責，其中分別定義了 16 位元的優先級編碼器（較高的 8 個位元為靜態定義的基礎優先級，較低的 8 個位元則為動態的計數器）以及負責處理即時排成的優先級指標兩種。而 timer 的主要資料則是由 timer 控制區塊（timer_t）來管理，像是 deadline_ticks 與回傳函式等，就是由它負責，並在最後藉由核心控制區塊（kcb_t）將 timer 與任務的管理做整合，由它負責管理全域核心的狀態。

不要寫為「高 8 位」，而該書寫「較高的 8 個位元」。「位」是量詞。

我參考 Linux 的任務生命週期狀態圖，繪製了一版 Linmo 作業系統的：

其實原先在 Linmo 作業系統的 include/sys/task.h 裡，是只有定義 TASK_STOPPED 、 TASK_READY 、 TASK_RUNNING 、 TASK_BLOCKED 與 TASK_SUSPENDED 這五種狀態。但是其實在設計上，系統仍舊有考慮 Created 與 Terminated ，所以再三考量後，我學習 Linux 核心，將象徵初始與結束的這兩狀態，加入週期圖中。

整個任務的生命週期，開始於 Created 狀態，當應用程式呼叫 mo_task_spawn 函式時，系統為任務配置記憶體（DEFAULT_STACK_SIZE）並初始化任務控制區塊（tcb_t），象徵著一個新的任務誕生。然而，此時任務尚未正式進入系統管理，任務會先被 Initialized ，轉為 TASK_STOPPED 狀態，但尚未有資格被安排排程。隨後，mo_task_spawn 函式將任務加入核心控制區塊（kcb_t）的任務鏈結串列中，完成 Admitted 轉換，任務變成 TASK_READY 狀態，等待排程器配置 CPU 時間。當排程器透過 dispatcher() 函式觸發，接著依賴 timer 的 _timer_tick_handler 更新系統嘀嗒，

/* The main entry point from the system tick interrupt. */
void dispatcher(void)
{
    kcb->ticks++;
    _timer_tick_handler();
    _dispatch();
}

隨後呼叫 dispatch 或 schedule_next_task 函式從 TASK_READY 狀態的任務中選擇一個，轉換為 TASK_RUNNING 狀態，開始在 CPU 上執行。timer 在此階段透過 kcb->timer_list 管理活躍中的 timer，並依據 deadline_ticks 排序。當 mo_timer_start 函式被呼叫，然後啟動 timer 時，根據當前 mo_ticks() 加上轉換後的週期（MS_TO_TICKS(period_ms)）設定，代表 timer 的 deadline 時間。以系統滴答為單位，deadline_ticks 確保 timer 事件在預定時間觸發：

設定 period_ms = 1000 且 F_TIMER = 1000 時，deadline_ticks 為當前 kcb->ticks 加上 1000 嘀嗒，_timer_tick_handler 函式在恰好 1000 嘀嗒後執行回傳呼叫，誤差僅取決於硬體計時器的精準度。

若任務執行中因為系統嘀嗒中斷，或者是主動呼叫 mo_task_yield 與 mo_task_wfi 其中一個函式，任務會因為 Interrupt 返回到 TASK_READY 狀態，等候下次排程，藉著排程器與 timer 兩者之間的搭配，來確保狀態切換時機的及時性。

當任務呼叫 mo_task_delay 函式或進入 _sched_block 等待資源時，會因 I/O or Delay Wait 轉換為 TASK_BLOCKED 狀態，此時 timer 發揮關鍵作用，藉由 _timer_tick_handler 函式檢查每嘀嗒過期的 timer，delay_update 則根據 kcb->ticks 遞減 tcb_t::delay，當延遲到期，任務由 timer 時間基礎觸發，經排程器恢復至 TASK_READY 狀態，重新參與排程。此外，任務在 TASK_RUNNING 的狀態下，也可能因為有管理需求被要求暫停。當呼叫 mo_task_suspend 函式時，任務因 Suspended 轉換進入 TASK_SUSPENDED 的狀態，被暫停或是排除於排程之外。此時 timer 與排程器的協同暫停，但系統仍透過嘀嗒維持時間進展，直到 mo_task_resume 函式觸發 Resumed 轉換，任務才會從 TASK_SUSPENDED 回到 TASK_READY 的狀態，等待重新執行。任務生命週期的終點則發生在應用程式呼叫 mo_task_cancel 函式時，任務會從 TASK_RUNNING 狀態直接轉為 Terminated 狀態，藉由 find_task_node_by_id 函式找到任務，並使用 list_remove 函式從將任務從鏈結串列中移除，最後釋放堆疊和 tcb_t 的記憶體，標誌任務的結束。整個 cancelled 過程無需 timer 的參與，交由排程器獨立執行。

系統的排程模式則分為兩種：搶佔式與協同式，由 app_main() 函式的回傳值決定。若回傳 1，系統啟用搶占式排程，硬體 timer 中斷會定時觸發任務切換，確保高優先級或即時任務能迅速搶佔 CPU；若回傳 0，則進入協同式排程，任務必須主動呼叫 mo_task_yield 函式來讓出 CPU 的控制權。儘管協同式排程能精確的控制切換時機，但若任務未及時讓出，就會造成 CPU 資源配置不均，影響系統公平性。

在搶佔式排程中，公平性透過加權 Round-Robin 與 timer 中斷的搭配來達成。系統利用 task_priorities 定義的優先級結構，讓每個任務的優先級由靜態優先級與動態計數器組成。排程器在每次 timer 中斷時，透過 find_next_ready_task() 函式檢查任務的鏈結串列，遞減動態計數器，當計數器歸零時選擇該任務執行，並重置計數器為基礎優先級值。

以 app/hello.c 為例子，定義三個任務的優先級如下：

任務 task0：TASK_PRIO_NORMAL = 0x1F1F（較低 8 位元的基礎優先級 0x1F）
任務 task1：TASK_PRIO_LOW = 0x7F7F（較低 8 位元的基礎優先級 0x7F）
任務 task2：TASK_PRIO_NORMAL = 0x1F1F（較低 8 位元的基礎優先級 0x1F）

排程過程：

初始狀態：task0 和 task2 的計數器 = 0x1F（31），task1 的計數器 = 0x7F（127）。
第一次 timer 中斷：排程器檢查任務列表，task0 的計數器減至 0，task0 被選中執行，計數器重置為 0x1F；task2 的計數器減少，task1 減少。
第二次中斷：task2 的計數器減至 0，task2 執行，計數器重置為 0x1F；task0 減少，task1 減少。
重複此過程，task0 和 task2 因優先級相同，輪流執行，每次中斷幾乎均分 CPU 時間；task1 需一段時間的中斷後直到計數器歸零，才執行一次。
timer 的定期觸發確保排程週期穩定，task1 雖執行頻率低，仍透過中斷獲得機會。

從以上過程我們可以得到，因為 task0 和 task2 的優先級相同，所以它們在每次 timer 中斷時輪流執行，均分 CPU 時間，實現 round-robin 排程的公平性。而 task1 儘管有著較低的優先級，但是藉由 timer 中斷，系統排程保證它可以週期性的執行，防止飢餓（starvation）的發生。

相較於搶佔式排程，協同式的公平性高度依賴任務的設計與執行邏輯。在 app/coop.c 中，除了 task2 因為 mo_task_delay(50) 函式呼叫的影響，會較晚被排程器加入排程，三個任務皆透過 mo_task_yield() 函式定時呼叫，確保每次迴圈後讓出 CPU，使排程器能按順序（task0 → task1 → task2）選擇下一個任務，從而實現均等的 CPU 時間配置。但是這種公平性設計並非系統強制保證，而是由開發者透過合理的程式設計實現。如果某一個任務突然被 mo_task_yield() 所遺漏，或是任務的執行時間過長，可能導致其他任務無法及時執行，造成不公平。相較於搶佔式排程的自動排程，協同式排程的公平性更脆弱。

最後回頭看即時排程器。它與加權 round-robin 排成器的設計在 Linmo 中形成互補的排程結構，task_priorities 透過固定優先級級別（TASK_PRIO_CRIT 至 TASK_PRIO_IDLE）和動態計數器實現加權輪詢（polling），適用於一般任務的公平分配。而即時排程器透過 rt_prio 欄位以及自定義的邏輯優先處理關鍵任務，繞過 task_priorities 的計數器限制。以app/rtsched.c 為例子。

這份位於 app 目錄的測試用程式碼提供了一個具體的應用實例。程式碼定義了五個任務（task0 至 task4），其中特別針對任務 0 到 2 設定了即時優先級，3 跟 4 則沒有。並自定義了一個基於信用的即時排程器 custom_sched 。這個函式採用信用基礎演算法，主要是為每個即時任務配置固定的信用值（credits），以控制其 CPU 時間。具體來說，app_main 函式初始化了三個即時任務的優先級結構 custom_prio_t ，並透過 mo_task_rt_priority 函式將這些信用值與任務關聯：

static custom_prio_t priorities[3] = {
    {.credits = 3, .remaining = 3}, /* Task 0 */
    {.credits = 4, .remaining = 4}, /* Task 1 */
    {.credits = 5, .remaining = 5}, /* Task 2 */
};

這些信用值代表任務在執行週期中獲得的 CPU 時間份額，信用越高，任務在該週期內的能執行的次數越多。custom_sched 函式每次選擇任務時，會遞減該任務的 remaining 信用值（初始值等於 credits），當 remaining 減至 0 時，重新從 credits 載入，並尋找下一個即時任務，確保每個任務按其信用比例獲得公平的執行機會。例如，任務 2 因為擁有 5 個信用，會比任務 0（3 個信用）獲得更多執行時間。這種信用驅動的分配方式避免了單一任務壟斷 CPU，實現了即時任務間的公平性。同時，當所有即時任務的信用耗盡或無任務可執行時，系統切換至 round robin 排程，task3 和 task4 按 task_priorities 的動態計數器輪流執行，保證非即時任務的執行機會。這種雙層排程的機制確保了即時任務的優先性與非即時任務的公平性之間的平衡。

回顧 commit 內容，原始程式碼因無條件參考 task_node->data 導致 NULL 指標錯誤並崩潰，藉由在走訪 kcb->tasks 鏈結串列時檢查節點的有效性，並跳過 head、tail 及空資料節點等，最後在無即時任務時安全地回傳 -1 ，修復錯誤，避免系統例外發生。

app/rtsched.c

後續開發與筆記記錄

~~[Linmo 開發紀錄](https://hackmd.io/@HeatCrab/ryNbWsmBxg)~~

更新在本頁面，專案開發出來，就是要讓他人指教，方可獲得進步的空間。

好的

因為我將 Linux 系統重新安裝到了新的磁碟上，等同於重灌了整個 Linux 系統，所以要重啟 Linmo 專案也需要安裝相對應的套件。

參考 <Operating System in 1,000 Lines> 教學文件，先安裝 QEMU：

$ sudo apt update && sudo apt install -y clang llvm lld qemu-system-riscv32 curl

接著安裝 riscv-gnu-toolchain，先安裝必要套件：

$ sudo apt-get install -y autoconf automake autotools-dev curl python3 python3-pip python3-tomli libmpc-dev libmpfr-dev libgmp-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev libexpat-dev ninja-build git cmake libglib2.0-dev libslirp-dev

接著將創建一個目錄並將檔案 clone 下來：

$ mkdir -p ~/riscv-toolchain
$ cd ~/riscv-toolchain

$ git clone https://github.com/riscv-collab/riscv-gnu-toolchain
$ cd riscv-gnu-toolchain

最後設定安裝路徑之後開始編譯，過程會花一點時間大概 20 分鐘左右：

$ ./configure --prefix=~/riscv --with-arch=rv32i --with-abi=ilp32
$ make -j$(nproc)

最後一個步驟，驗證是否編譯成功：

$ riscv-none-elf-gcc --version

riscv-none-elf-gcc () 15.1.0
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

但是我的 toolchain 編譯後 none 是 unknown ，所以為了確定能正常編譯 Linmo 專案，我選擇針對我的 toolchain 建立 Symbolic Link：

$ ln -s riscv32-unknown-elf-gcc riscv-none-elf-gcc
$ ln -s riscv32-unknown-elf-ld riscv-none-elf-ld
$ ln -s riscv32-unknown-elf-as riscv-none-elf-as
$ ln -s riscv32-unknown-elf-objcopy riscv-none-elf-objcopy
$ ln -s riscv32-unknown-elf-ar riscv-none-elf-ar
$ ln -s riscv32-unknown-elf-objdump riscv-none-elf-objdump
$ ln -s riscv32-unknown-elf-size riscv-none-elf-size

最後根據 Linmo 專案中的 README，我們執行以下命令確認結果：

$ make clean
$ make
$ make hello
$ make run

並預期得到以下的輸出結果：

Ready to launch Linmo kernel + application.
Linmo kernel is starting...
Heap initialized, 130012136 bytes available
task 1: entry=80000234 stack=80002c84 size=4096
task 2: entry=800001f4 stack=80003d34 size=4096
task 3: entry=80000184 stack=80004db0 size=4096
task0 has id 1
task1 has id 2
task2 has id 3
Scheduler mode: Preemptive
[task 1 100000]
[task 3 300000 - sys uptime: 0.013s]
[task 1 100001]
[task 3 300001 - sys uptime: 0.033s]
[task 1 100002]
[task 3 300002 - sys uptime: 0.053s]
[task 1 100003]
[task 3 300003 - sys uptime: 0.073s]
[task 1 100004]
[task 3 300004 - sys uptime: 0.093s]
[task 1 100005]
[task 2 200000]
[task 3 300005 - sys uptime: 0.123s]
[task 1 100006]
...

Jim Huang

2025/06/11 15:29:33

設備

device 的翻譯是「裝置」，而非「設備」(equipment)

2025/06/11 15:30:04

遍歷

注意用語，見 https://hackmd.io/@sysprog/it-vocabulary

403 Forbidden - HackMDBuild together with Markdown

HackMD

JimC

2025/06/12 09:45:58

更正用法為「走訪」，更貼切實際程式碼實作。

2025/06/16 15:21:45

腳本

老師我在 wikipedia 上查到使用指令碼，所以我以後就使用腳本為主嗎？ https://zh.wikipedia.org/zh-tw/%E8%85%B3%E6%9C%AC

2025/06/16 15:30:45

既然 instruction 翻譯為「指令」，跟其沒有詞源關聯者 (如 script)，就不該包含「指令」

2025/06/16 16:43:03

了解

2025/06/17 06:50:26

核心組件

老師我想問 core component 這個詞應該翻譯成「核心組件」還是「核心元件」呢？另外 core 一樣是翻譯成核心嗎？

2025/06/17 07:03:54

processor core 的 core 是「核」; core component 的 core 是「主體」。「核心」只拿來描述 OS kernel

2025/06/18 08:12:46

注意用語！

2025/06/18 16:21:32

通過

pass 是「通過」; via/through 是「藉由」

2025/06/18 16:21:55

后

尊重你所在地的文化！

2025/06/18 17:52:41

chedule 找不到 READ

call 是「呼叫」，而非「調用」

2025/06/18 18:02:23

2025/06/19 07:01:21

優化

注意詞彙，見 https://hackmd.io/@sysprog/it-vocabulary

2025/06/20 03:47:37

完善

完善是形容詞，而非動詞，見: https://dict.revised.moe.edu.tw/dictView.jsp?ID=161584

2025/06/20 03:50:11

為解決此問題，修補程式碼在 setjmp 和 longjmp 中新增對 mstatus 暫存器的處理

提交修改時，要確保現有程式碼的行為符合預期

2025/06/20 13:51:21

2025/06/21 07:18:47

enqueue

參考國立清華大學的大家來學外語網站，將 en 字根翻譯為置於…之中。 https://m99.nthu.edu.tw/~s9922110/eng/Prefix_en/ (Edited)

2025/06/21 07:20:38

dequeue

參考國立清華大學的大家來學外語網站以及 linmo/lib/queue.c 的註釋與程式碼，將 de 字根翻譯為移除。 https://m99.nthu.edu.tw/~s9922110/eng/Prefix_de/

2025/06/22 09:25:29

〈Operating System in 1,000 Lines https://operating-system-in-1000-lines.vercel.app/en/ 〉教學文件

老師我剛剛發現有同學貢獻了繁體中文的版本，我是否有需要參考內文的翻譯來修正我筆記內，某些專有名詞的翻譯呢？ https://operating-system-in-1000-lines.vercel.app/tw/

2025/06/22 09:28:11

以課程規範的用以為主

2025/06/22 09:29:08

2025/06/23 08:24:30

魔術數字

老師，我發現在 Linmo 中很常使用 magic number 來制定一些界線規範，或測試，這些數字通常是依循什麼來設計的？或者說有沒有相關的教材連結閱讀。

2025/06/23 08:55:11

參見 https://en.wikipedia.org/wiki/Hexspeak

2025/06/23 10:35:26

有趣的是，原先是使用 CRITICAL_ENTER 和 CRITICAL_LEAVE 來保護與等待鏈結串列，現在則是更改為使用 NOSCHED_ENTER/LEAVE 保護關鍵區段的。

老師我發現我看了許久，還是不太明白為何在 mutex.c 與 semaphore.c 中選擇使用 NOSCHED_*，是因為這些程式碼是處理行程，與 timer 有最直接關係，所以選擇設計一個控制 machine-level timer interrupt 的巨集嗎？還是有什麼其他用意呢？

2025/06/23 11:48:25

類似 Linux 核心的 enable_preempt 和 disable_preempt

Peter Chen; Kohan Chen

2025/06/27 05:48:41

commit a96b267 https://github.com/sysprog21/linmo/commit/a96b2671588cff08a9d26f3c14bb051019a31236

連結已失效，專案不存在。

2025/06/27 06:46:19

因為當前的專案還是 private 狀態，等到老師正式發布後，應該就能可見了！