# 2025q1 Homework3 (kxo)
contributed by <`Hande1004`>
## 螢幕顯示當下的時間
為了讓螢幕能夠更新當下的時間，我在 `xo-user.c` 中引入 `<time.h>` 並在每次顯示棋盤的下方顯示時間。
```diff
else if (read_attr && FD_ISSET(device_fd, &readset)) {
+ time_t now = time(NULL);
+ const struct tm *t = localtime(&now);
FD_CLR(device_fd, &readset);
printf("\033[H\033[J"); /* ASCII escape code to clear the screen */
...
printf("%s", display_buf);
+ printf("\n%04d-%02d-%02d %02d:%02d:%02d\n",
+ t->tm_year + 1900, t->tm_mon + 1, t->tm_mday,
+ t->tm_hour, t->tm_min, t->tm_sec);
}
```
最後棋盤顯示的畫面是長這樣的：
```
|X|O|O
-------
O|X| |
-------
|X|X|
-------
| | |
-------
2025-05-14 03:27:40
```
## 使棋盤呈現畫面在使用者層級
在原本的 `main.c` 程式中，是利用 `draw_board()` 這個函式在核心層級繪製棋盤畫面。然而，Kernel 本身應該專注於邏輯判斷與系統資源的管理，像是棋盤繪製這類與畫面呈現、格式控制、字串操作相關的工作，本質上屬於使用者介面的範疇，並不涉及核心資源或安全邏輯，放在使用者層級會更為妥當。
在原本的 `draw_board()` 函式中，AI 下棋的結果會被整理成完整的棋盤字串並儲存在 `draw_buffer[]` 中，隨後透過 `kfifo_in()` 寫入核心模組中的 FIFO 緩衝區 `rx_fifo.buffer`，再透過 `kfifo_to_user()` 傳送至使用者空間的緩衝區。這樣的流程確實可以完成棋盤畫面的傳輸與顯示。
然而，當我將棋盤繪製的工作移至使用者層級後，便無需再將整張棋盤畫面傳送出去。取而代之，我設計了一套編碼與解碼的對應邏輯：核心僅需傳送一個經過壓縮後的狀態變數（`draw_state`），而使用者端則根據該變數進行解碼與繪製。
這樣的改動大幅減少了核心與使用者空間之間的資料傳輸量。實際上，畫出棋盤的關鍵資訊只包含每個格子是 `X`、`O` 或空白 (` `)，因此完全無需傳送包含字元格式與排版的完整棋盤字串。透過這樣的編碼設計，我成功地將每步棋所需傳送的資料大小，從原本的 66 bytes 減少為僅 4 bytes
這次的設計發想主要源自於位元壓縮的概念。由於每一個格子的狀態只需要三種可能：`X`、`O` 或空白（` `），因此只需使用 2 個 bits 即可表示（例如：00 表示空白，10 表示 X，11 表示 O）。整個棋盤共有 16 個格子，總共只需 16 × 2 = 32 bits，恰好可以壓縮在一個 `unsigned int` 變數中。
透過這種方式，我能夠以一個 4-byte 的變數完整表示整張棋盤的狀態，取代原本以文字格式傳送整個棋盤（66 bytes）的方式，進一步壓縮核心與使用者層級之間的傳輸成本，同時保留所有必要資訊，讓使用者端可以自行進行解碼與繪製。
`static void encoding(char *table)` :
這在個函式中，我把 `X` 編碼成 `10` ， `O` 編碼成 `11`，而空白設計成 `00` ，為了進行編碼，我使用 Linux 核心中的 `__set_bit()` 函式，將對應的位元設定到變數中。具體實作如下：
> commit [336170f](https://github.com/sysprog21/kxo/commit/336170fdd88795d20671f5911dc9bff25e2d34bc)
```c
for (int i = 0; i < N_GRIDS; i++) {
switch (table[i]) {
case 'X':
__set_bit((N_GRIDS-1-i)*2 + 1, &val); // 10b
break;
case 'O':
__set_bit((N_GRIDS-1-i)*2, &val); // 11b
__set_bit((N_GRIDS-1-i)*2 + 1, &val);
break;
}
}
```
`static void decoding(unsigned int decoding_val, char *display_buf)` :
在解碼中透過位移與位元遮罩，每次取出 2 個 bits 進行解碼，將壓縮後的棋盤狀態還原成對應的 `X`、`O` 或空格，並依序填回 `table[]`。
```c
char table[N_GRIDS];
memset(table, ' ', sizeof(table));
for (int i = N_GRIDS - 1; i > 0; i--) {
unsigned int val = (decoding_val >> (i << 1)) & 0x3;
switch (val)
{
case 0x0:
table[N_GRIDS - 1 - i] = ' ';
break;
case 0x2:
table[N_GRIDS - 1 - i] = 'X';
break;
case 0x3:
table[N_GRIDS - 1 - i] = 'O';
break;
}
}
```
接者我把改完的程式碼用 perf 做分析：
本次效能比較是針對一次完整棋局進行測量，每場遊戲由 AI 自動進行至結束，平均執行時間為 10 秒。每種版本各執行 5 次並取平均，過程中每一步棋皆即時傳送資料至使用者層級並更新畫面，以符合作業即時互動需求。比較項目包括 CPU cycles、instructions、context switches 及 cache misses，作為評估改寫後資料壓縮與結構調整之效能指標。
| 指標 | 原始版本（`draw_buffer`） | 壓縮版本（`__set_bit`） |
|------------------|--------------------------|--------------------------|
| cycles | 50,320,915,329 | 50,814,543,779 |
| instructions | 49,519,140,777 | 50,059,946,678 |
| insn per cycle | 0.98 | 0.99 |
| context-switch | 5,069 | 5,115 |
| cache-misses | 3,357,735 | 3,080,508 |
透過上述 perf 效能比對可以發現，除了 cache-misses 數量明顯下降之外，其餘指標如 cycles、instructions 以及 context-switches 在原始版本與壓縮版本之間差異不大。這表示，儘管我將每一盤棋的資料量從約 66 bytes 壓縮為 4 bytes，整體效能卻未明顯提升。
我認為主要原因在於資料的實際傳輸單位仍是以一個 page 大小為基本單位，再加上每走一步棋就立即將資料透過 `kfifo_in()` 傳送至使用者空間，並非累積多步再一次傳送。因此即使單筆資料變小了，傳輸成本（包含中斷喚醒、系統呼叫、I/O 費用）並未因此顯著降低。
雖然降低 byte 數可以提高批次傳送的數量（例如每幾步累積後再一次傳送）理論上可能進一步減少傳輸次數與系統呼叫，但如果改為延遲傳送，可能會導致畫面無法同步顯示每一步棋的下法，影響互動性與觀察體驗，因此此處在效能與即時性之間做了取捨。
至於 cache-misses 數量的下降，我推測是因為我在核心中使用了 `__attribute__((aligned(64)))` 將 `draw_state` 這個狀態變數對齊至 64 bytes，這正好與一般 CPU cache line 的大小一致。由於每次只傳送對齊良好的 4-byte 整數，且資料位置穩定，CPU 快取在讀寫時能更有效利用整條 cache line，從而降低了 cache miss 發生的機率。
## 引入若干 coroutine
在此部分，我將整個實作整合於 xo-user.c 中，包含兩個 AI（$AI_1$、$AI_2$）、鍵盤事件處理與棋盤繪製功能。參考了 [coro](https://github.com/sysprog21/concurrent-programs/blob/master/coro/coro.c) 所採用的 coroutine 實現方式，我設計了多個任務函式：`task_O()`、`task_X()`、`task_draw()` 與 `task_keyboard_handler()`。這些任務經由 `schedule()` 進行排程管理，並透過 `task_switch()` 負責任務切換，以實現 coroutine 並行執行的效果。
> 參考了 [wurrrrrrrrrr](https://hackmd.io/@Guanchun0803/linux2025-homework3#%E3%80%88%E4%B8%A6%E8%A1%8C%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%EF%BC%9A%E6%8E%92%E7%A8%8B%E5%99%A8%E5%8E%9F%E7%90%86%E3%80%89%EF%BC%8C%E5%BC%95%E5%85%A5%E8%8B%A5%E5%B9%B2-coroutine) 後發現要實作在 user 端需將原本的 game.c、mct.c、negamax.c、xoroshiro.c 和 zobrist.c 等檔案改成可以實做在 user 端的形式。
根據題目的要求：
> 當按下 Ctrl-P 時暫停或回復棋盤畫面更新 (但運算仍持續)、當按下 Ctrl-Q 時離開「電腦 vs. 電腦」的對弈。
因此，我用兩個變數去控制這兩件事情：
```c
struct user_attr {
int display;
int end;
};
```
`display == 1` 表示要顯示棋盤，`display == 0` 則表示暫停顯示棋盤。
`end == 1` 表示結束對奕， `end == 0` 則表示繼續對奕。
為了實作 coroutine 我用到了 linux 提供的兩個函式 [setjmp()](https://man7.org/linux/man-pages/man3/setjmp.3.html) 跟 [longjmp()](https://man7.org/linux/man-pages/man3/longjmp.3p.html)。
`int setjmp(jmp_buf env)` :
用來儲存當前程式執行環境（包含程式計數器、堆疊指標與部分暫存器狀態等）至 `env` 緩衝區的函式。當 `setjmp()` 被首次呼叫時，會回傳整數值 0，代表正常執行流程。若之後透過 `longjmp() `使用相同的 `env` 進行跳，`setjmp()` 會再次返回，但這次回傳的值會是由 `longjmp()` 所指定的非零值（若 `longjmp()` 指定的值為 1，則 `setjmp()` 會回傳 1）。這種機制讓程式能夠從不同的位置非正常跳回至先前設定的執行點，實現非區域性的跳。
`void longjmp(jmp_buf env, int val)` :
此函式用來將程式的控制流程跳回先前由對應的 `setjmp(env)` 所儲存的執行環境 `env`。當呼叫 `longjmp()` 時，`setjmp()` 會重新返回，但這次的回傳值是由 `val` 指定的非零整數（若 `val` 為零，則實際回傳值會被強制為 1），以此讓程式知道是由 `longjmp()` 跳轉回來，實現非區域控制流的跳轉。此函式不會返回呼叫者，而是直接將控制權轉移回之前儲存的執行點。
為了管理不同任務的執行環境以及將其加入到任務列，寫了個 `struct`。
```c
struct task {
jmp_buf env;
struct list_head list;
};
```
`in main()` :
因為 coroutine 需自己去決定排程的順序，因此，這邊用了一個函式指標的陣列去儲存每個函式，用這樣的方式去決定起始的執行順序，接著透過全域的指標傳進 `schedule()`
```c
static void (**tasks)(void);
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
int main
{
...
void (*registered_tasks[])(void) = {
task_O, task_keyboard_handler, task_draw, task_keyboard_handler,
task_X, task_keyboard_handler, task_draw, task_keyboard_handler
};
tasks = registered_tasks;
ntasks = ARRAY_SIZE(registered_tasks);
schedule();
...
}
```
接下來為了執行 coroutine 我用了 coro 所使用的幾個函式，這幾個函式就是主要負責排程，切換的。
`task_add()` :
在這段函式中會將傳進來的任務加入到以 `tasklist` 為 head 的任務列中。
```c
static void task_add(struct task *task)
{
list_add_tail(&task->list, &tasklist);
}
```
`task_switch()` :
這個函式會去找出任務列（ `tasklist` ）的第一個任務，把它從任務列中移除，並且用全域的指標 `cur_task` 來記住當前的 `task`， 這主要是以防 `longjmp()` 回去時，任務函式裡的區域變數會失效，導致讀取到錯誤的記憶體位置。
```c
static struct task *cur_task;
static void task_switch()
{
if (!list_empty(&tasklist)) {
struct task *t = list_first_entry(&tasklist, struct task, list);
list_del(&t->list);
cur_task = t;
longjmp(t->env, 1);
}
}
```
`schedule()` :
此函式會首先設置一個 `setjmp` 的儲存點，並將相關的執行環境資訊存入 `sched` 變數中。接著，`while` 迴圈利用先前提到的函式陣列指標（`tasks`），依序呼叫每個需要排程任務的對應函式。當每個任務都執行一次後，便會跳出 `while` 迴圈。這樣的設計是因為排程器在第一次呼叫時，主要負責將任務按照設定順序排好，而實際的任務執行會透過 `setjmp(sched)` 和 `task_switch()` 來切換並執行所有任務。
```c
static jmp_buf sched;
void schedule(void)
{
static int i;
setjmp(sched);
while (ntasks-- > 0) {
tasks[i++]();
printf("Never reached\n");
}
task_switch();
}
```
上述的幾個函式便是執行 coroutine 的關鍵，接下來是針對這次作業的部份，我改了四個函式，分別對應 AI 下 `O` (`task_O`) 、 AI 下 `X` (`task_X`) 、畫棋盤（`task_draw`） 、 鍵盤事件（`task_keyboard_handler`），這幾個函式主要的實作方式跟老師原本寫於 xo-user.c 和 main.c 的基本相同，因此，我只說明針對 coroutine 所需的修改。
為了讓排程器能夠順利的把每個任務都排進任務列（`tasklist`）中，需要在每個 task 的對應函式都先寫好第一次呼叫時的設定。
```c
struct task *task = malloc(sizeof(struct task));
INIT_LIST_HEAD(&task->list);
if (setjmp(task->env) == 0) {
task_add(task);
longjmp(sched, 1);
}
```
根據這段程式碼，每個任務從 `schedule()` 呼叫對應函式時，因為是首次呼叫，所以這邊的 `if` 會成立，也就會把此任務加入到任務列，並且透過 `longjmp` 回 `schedule` 的 `while` 中，去呼叫下一個任務的對應函式。
接下來當所有任務都被排程器排程後，就會透過 `task_switch()` 中的 `longjmp` 跳回任務列的第一個函式，此時會跳回到上方的那個程式碼的 `setjmp` ， 但因為跳回的回傳不等於 0，因此，會往下繼續走，並且真正的去執行所要執行的任務，跳回函式後需先判斷 `end` 是否等於 1 ，如果等於 1 就表示使用者有輸入 CTRL Q 的命令，也就要結束整個程式；比較特別的時如果使用者有輸入 CTRL P 的話，那 `task_draw` 就不會執行畫棋盤，而是直接跳回 `task_switch()` 換下一個任務執行。
```c
task = cur_task;
while (!attr_obj.end) {
if (setjmp(task->env) == 0) {
... //這邊是要執行的任務內容
task_add(task);
task_switch();
}
```
在真正執行時，也會去判斷是否為執行的第一次 `setjmp` ，如果是才會去執行裡面的任務，當裡面的任務執行完，會在透過 `task_add` 把此任務放進任務列的最後一個，就是因為這個的原因，可以讓任務列一直照著一開始的順序去一一執行，在透過 `task_switch` 去切換下一個任務；在這邊如果是下一次的 `longjmp` 回來，那 `if` 這邊就不會成立，會跳出判斷式，我把一些檢查機制放在 `if` 之外，像是檢查棋盤是否 `win` 或是顯示時間這些非主要的任務，接下來又會因為 `while` 成立，重新去設置 `setjmp` （透過 `while` 回去重新設置的 `setjmp` 也是首次設置），故回傳0，就這樣任所有任務都能按順序的正確執行。
在 `attr_obj.end == 1` 時，`while` 會不成立，我在 `while` 外寫了釋放 malloc 的程式碼，並且讓它回到排程器一一把每個任務的 malloc 釋放，並且結束整個程式。
```c
free(task);
longjmp(sched, 1);
```
### 實做期間遇到的問題
起初閱讀 coro 的實作程式碼時，我誤以為 `task = cur_task` 只是單純用來標示當前執行的任務指標，並無實質作用。主要原因是因為我以為 `longjmp()` 跳回 `setjmp()` 的過程就像一般函式呼叫一樣，區域變數的值會被妥善保存，因此 `task` 指標仍會指向之前 malloc 的有效記憶體地址。基於這個想法，我在自己的程式中忽略了這行，結果導致執行時出現 `segmentation fault` ， 這個錯誤花了我許久了時間，因為即使是問高級一點的 LLM 也無法幫我找出這個 bug。
後來，重新仔細檢視 coro 程式碼後，我意識到 `cur_task` 的作用其實是透過全域變數的特性，來保存當前任務的正確指標，因為 `longjmp()` 跳回後，區域變數 `task` 所持有的指標值不會自動回復，其內容和指向的位置都是不確定的。若直接使用該指標，將會造成記憶體存取錯誤。
因此，我在每次 `longjmp()` 跳回及 `task_switch()` 後，重新將 `task` 設定為 `cur_task`，這樣確保 `task` 始終指向正確的任務記憶體。經過此修正後，整個程式成功地執行了 coroutine 的排程與切換。
> [Commit e0b10b8](https://github.com/sysprog21/kxo/commit/e0b10b896c2f4831a41bf964690190f06575a654)
## 運用定點數來統計不同 AI 實作機制對系統負載的使用率
在解決完 coroutine 的問題後，我參考了 [Load Average](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-a#Load-Average) 想去求兩個 AI（Negamax 與 MCTS）在對弈過程中各自的 CPU 負載情況，因此，我參考了文中提供的 `calc_load()` 函式與 Linux 的 Load Average 概念，但發現該演算法是以整體系統層級為設計基礎，透過計算當下 RUNNABLE + UNINTERRUPTIBLE 的 process 數量進行平均負載估算。然而，我的程式架構是以 Coroutine-based 為主，所有邏輯都在單一 thread 中切換任務，因此同時存在幾個 runnable 任務對我來說不具實質意義，因為無論有幾個 coroutine 被安排，都只能逐一執行，並沒有真正的多工。
此外，`calc_load()` 的時間平均演算法（基於指數移動平均，EMA）預設會定期呼叫並更新歷史狀態，但我的程式是透過鍵盤輸入 CTRL Q 結束的，並沒有定時更新機制，這會導致 α 值無法合理設定。因此，若強行仿照 Linux 的 Load Average 公式實作，會因不符合 coroutine 環境與執行模式而失去準確性與意義。
為了解決上述問題，我選擇改用更直觀且符合我情境的「負載率」定義：
負載率 = AI 執行的 CPU 時間 / 程式總執行時間
具體來說，我使用 `CLOCK_THREAD_CPUTIME_ID` 測量每個 AI coroutine 實際消耗的 CPU 時間，並在 `main()` 中紀錄整體 `wall-clock` 時間，再將兩者相除，並使用定點數實作避免浮點運算限制。
```c
#define FIXED_SHIFT 16
#define FIXED_ONE (1 << FIXED_SHIFT)
int main()
{
struct timespec wall_start, wall_end;
clock_gettime(CLOCK_MONOTONIC, &wall_start);
...
clock_gettime(CLOCK_MONOTONIC, &wall_end);
uint64_t delta_wall_ns = (wall_end.tv_sec - wall_start.tv_sec) * 1000000000UL +
(wall_end.tv_nsec - wall_start.tv_nsec);
uint64_t load_x = (ai_state.total_cpu_ns_X << FIXED_SHIFT) / delta_wall_ns;
uint64_t load_o = (ai_state.total_cpu_ns_O << FIXED_SHIFT) / delta_wall_ns;
printf("ai negamax load ratio : %lu.%04lu\n", load_x >> FIXED_SHIFT, ((load_x & (FIXED_ONE - 1)) * 10000) >> FIXED_SHIFT);
printf("ai mcts load ratio : %lu.%04lu\n", load_o >> FIXED_SHIFT, ((load_o & (FIXED_ONE - 1)) * 10000) >> FIXED_SHIFT);
return 0;
}
```
對於 MCTS 和 Negamax 兩個 AI，我是在它們每次計算下一步棋的時候，用時間量測的方式紀錄它們實際用了多少 CPU 時間。這樣可以累積出每個 AI 在整體執行期間內的運算量，用來計算它們的負載比例。
```c
void task_X(void)
{
...
struct timespec start, end;
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
move = negamax_predict(board, 'X').move;
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
uint64_t delta_ns = (end.tv_sec - start.tv_sec) * 1000000000UL +
(end.tv_nsec - start.tv_nsec);
ai_state.total_cpu_ns_X += delta_ns;
...
}
```
透過紀錄每個 AI 個別的運算時間，並與整體程式執行時間進行比較，即可估算出這兩個 AI 的負載比例，反映其在整體執行期間所佔用的處理資源。
最後呈現螢幕上的結果如下：
```
| |O|
-------
| | |O
-------
X| |X|
-------
| | |
-------
2025-07-02 18:47:30
Stopping the tic-tac-toe game...
ai negamax load ratio : 0.0036
ai mcts load ratio : 0.9961
```
測量結果顯示，Negamax 的平均負載率僅為 0.36%，而 MCTS 的負載率高達 99.6%。這代表在整體遊戲的執行過程中，幾乎所有的 CPU 運算都被 MCTS 所佔據，推論其演算法在每一步選擇上需要進行大量模擬與計算，相對於 Negamax 的遞迴樹搜索來說，運算成本明顯更高。
:::danger
說好的進度呢？
:::
Sign in with Wallet
Connect another wallet