# Linux 核心專題: 重作 kxo
> 執行人: Hande1004
> [期末專題影片](https://youtu.be/pT7olsaTLYk)
> [GitHub](https://github.com/Hande1004/kxo)
### Reviewed by `thwuedwin`
請問你在實作 coroutine 時，對核心模組，主要是 `main.c` 的部分，進行了什麼修改？兩場遊戲同時進行時，核心模組的流程會如何改變？遊戲的棋盤等資料要怎麼正確的輸出到使用者層級？
> [name=hande1004]
> 我在做 coroutine 的實做時，沒有用到 main.c 的部份，而是開一個新的檔案在 user 端，把全整個實做全部寫在這個檔案中，也就是純粹為 coroutine 寫了個新的實做，因此，沒有跟核心互動的問題。
### Reviewed by `Andrewtangtang`
想請問你是如何監聽鍵盤事件放進排程的 list 中？如何去使 AI 可以定時被喚醒去做下棋的動作。
> [name=hande1004]
> 為鍵盤事件設立一個任務，並在每個任務之間都放入鍵盤事件任務，讓每下一步棋後都能夠監聽鍵盤事件。
```c
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();
```
### Reviewed by `HeLunWu0317`
請問在實作coroutine時，有沒有遇過編譯且執行多次後，遊戲對弈過程壞掉的情況，棋盤顯示的符號會出問題，此時就算去執行原專案也一樣出問題，重新加載kxo.ko模組也無法解決，只有重開機等一陣子才恢復。
> [name=hande1004]
> 我並沒有遇過這樣的問題，而且我的 coroutine 實作是獨立的檔案，不需要加載模組就能執行，如果你是有遇到這樣的問題，可能對你的問題幫助有限。
### Reviewed by `otischung`
[`in main()`](https://hackmd.io/@sysprog/BkUeXjIVxl?stext=2184%3A12%3A0%3A1751430557%3A_JgcHZ) 是指 In `main()` function 還是 `int main()`？
> [name=hande1004]
> `int main()` 以更正，感謝。
### Reviewed by `fcu-D0812998`
請問你在測量 `MCTS` 和 `Negamax` 負載時，是用 `CLOCK_THREAD_CPUTIME_ID` 去計算整個 `coroutine` 週期的 CPU 時間，那這樣會把每次 `coroutine` 切換時的 `context switch overhead` 也算進去。你覺得這樣的測量結果能真實反映兩個 AI 的計算量差異嗎？
> [name=hande1004]
> 我是用 `CLOCK_THREAD_CPUTIME_ID` 去計算沒錯，但是我只讓他計算單次 ai 運算的部分，也就是用 ai 運算的那一行程式碼的上下行做測量而已，算完 ai 的部分後會再用全域變數記住總共的運算時間，所以不會有因為 context switch 造成的多餘運算的問題。
### Reviewed by `RealBigMickey`
當初我在做這個作業時初始也是想使用 setjmp 與 longjmp ，但因這兩個函式屬於 libc 所以無法使用，利用 inline assembly 自己寫的結果也會被擋下來，因 kernel 不允許隨變更改 stack pointer 。無奈之下最後我使用 workqueues 來實做。因此想請問你是怎麼繞過這些問題的呢？
> [name=hande1004]
> 我獨立開一個檔案來寫 coroutine 的部分，其中沒有用到 main.c 的東西也就不會有互相引響的問題。
### Reviewed by `h0w726`
可以將完整程式碼放在 GitHub 上，方便大家觀摩。
> [name=hande1004]
> 已放上 github
## 任務描述
以[第三份作業](https://hackmd.io/@sysprog/linux2025-kxo)為基礎、搭配課堂討論和觀摩學員的成果，重新投入 kxo 開發。過程中可參照其他學員的成果 (但要實驗和指出其缺失)，務必清楚標示。
## TODO: 重作 kxo
> 注意定點數運算誤差的分析和消除
> 考慮到 MCTS 在定點數的實作，留意累積誤差和亂數品質的議題
> 務必處理好 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;
};
```
`int 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 的遞迴樹搜索來說，運算成本明顯更高。
## TODO: 觀摩其他學員的成果
> 紀錄你的啟發、你進行的驗證，以及後續改進
Sign in with Wallet
Connect another wallet