# Linux 核心專題: 重作 kxo
> 執行人: thwuedwin
> [專題解說錄影](https://youtu.be/IhoBgpiCI1U)
## 任務描述
以[第三份作業](https://hackmd.io/@sysprog/linux2025-kxo)為基礎、搭配課堂討論和觀摩學員的成果，重新投入 kxo 開發。過程中可參照其他學員的成果 (但要實驗和指出其缺失)，務必清楚標示。
### Reviewed by `Mike1117`
>由此可見，在目前這種小型資料量下，傳輸時間主要受到其他因素影響，而非資料大小。因此，壓縮棋盤資料並未顯著降低通訊成本，也使解碼與維護更加複雜，我認為在實務上並不划算。
請問你認為「其他因素」中，哪一項最有可能是主因？
>[name=thwuedwin]
>我認為 blocking IO 造成等待輸入資料的時間成本可能會是主因。從 `weiso131` 的建議開始我做了一些討論和實驗，詳細可以參考他的建議和我的回答。
### Reviewed by `Andrewtangtang`
好奇關於 workqueue CPU affinity 設定的動機是什麼，在實質上有對於整體的效能有任何影響或改善嗎？
>[name=thwuedwin]
>設定 affinity 單純出於作業要求。我認為設定工作只能在同一個 CPU 上跑會讓效能變差。kxo 專案中，在 AI 執行時，會使用 `get_cpu()`，讓其他行程無法搶佔。若設定只能在一個 CPU 上執行，會造成其他行程更有可能會 migrate。舉例來說，我設定 $\text{AI}_1$ 只能在 CPU 0 執行，當他佔用 CPU 時，其他本來在 CPU 0 上的行程更可能會被排程到其他 CPU 上。若是執行在不同的 CPU 上，可以由排程器選擇更適合執行的 CPU。我的想法簡單來說就是固定 CPU 會影響原本排程器的策略，所以負載會更重。
### Reviewed by `weiso131`
>由此可見，在目前這種小型資料量下，傳輸時間主要受到其他因素影響，而非資料大小。因此，壓縮棋盤資料並未顯著降低通訊成本，也使解碼與維護更加複雜，我認為在實務上並不划算。
根據圖表中的信息，我推測你應該是直接測量 `read()` 在 `xo-user.c` 的等待時間，你認為壓縮棋盤資料並未顯著降低通訊成本，但我在 [baa717a](https://github.com/sysprog21/kxo/commit/baa717a747a1352cd1fed31e7edbbb8f7afc345d) 看到你嘗試將 `char table[16]` 轉換成 4 bytes 的壓縮資料，在這種情況下， `read` 需要的等待時間可能就會增加。比較理想的情況應該是把 `char table[16]` 完全替換成壓縮資料的版本，或是直接將傳遞一步棋的資料(這必須確保同個棋盤不會被兩個以上的使用者 `read()`)。
此外，直接比較平均值似乎不是一個好的方法，應該使用 t test 。
>[name=thwuedwin][time=Thu, Jul 3, 2025 9:17 PM]
>先回答第一個部分，你提到我在壓縮資料的時候可能會造成 `read` 的等待時間增加。我確實是直接量 `read()` 的時間。我的做法是把 `draw_board` 的繪製部分，更改成壓縮資料。所以原本的實作中繪製棋盤得成本，在我的實作中變成壓縮資料的成本。
>接著考慮此成本會不會影響到 `read`。核心模組輸出資料到使用者層級程式的流程是，`draw_board` 將資料繪製後，放入 `draw_buffer`。接著 `produce_board` 將 `draw_buffer` 的資料透過 `kfifo_in` 放入 kfifo。`produce_board` 執行完後，再由呼叫 `produce_board` 的函式（具體來說是 `drawboard_work_func` 和 `timer_handler`）使用 `wake_up_interruptible` 來將等待 IO 的程式喚醒。因此 `read` 的時間確實可能會包含 `draw_board` 所需的時間。
>我先針對原本的實作進行 10000 次 `read` 時間的採樣。繪製出兩種資料量下的執行時間分布圖，可以看到兩者的曲線幾乎重疊。你提到可以使用 t-test，我用 python [scipy 函式庫](https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.ttest_ind.html)提供的 `stats.ttest_ind` 函式來進行測試，結果是沒有統計上的差異。但在我的理解中，t-test 只適用於常態分布，以分佈圖來看，我不認為在這個情況下 t-test 的結果有重要的意義。若有人有更好的統計方式，歡迎給我建議。
>很好的提問和建議，感謝！
>
>[name=thwuedwin][time=Thu, Jul 3, 2025 10:32 PM]
>我嘗試將 `draw_board` 函式移除，直接將核心模組維護的棋盤 `table` 放入 kfifo 輸出。一樣測試 10000 次 `read()`。並將其和原本的資料畫在一起。
>
>現在看不出這根尖尖的是什麼，我將它放大一點
>原本的資料竟然被縮得這麼小。因為這張圖的概念類似機率密度函數，因此曲線下的面積積分是 1，綠色的曲線這麼高就代表執行時間在橫軸上的分布很窄。這代表執行時間非常穩定。`draw_board` 不只導致效率變差，還會讓 `read` 所需的時間變得很不穩定。平均的執行時間前兩者為 0.135，而移除 `draw_board` 後下降至 `0.103`。再次謝謝 `weiso131` 非常好的建議！
### Reviewed by `fcu-D0812998`
>我曾嘗試將 affinity_scope 設為 cpu，並開啟 affinity_strict，希望限制 work 綁定到某個 CPU。但即使如此，當 work 被重新加入時，仍有可能在不同的 CPU 上執行。
你認為可能是甚麼原因造成這樣的設定無法達到你想要的效果?
>[name=thwuedwin]
>work 會在哪個 CPU 上執行，是在 work 加入 workqueue 時決定。設定 CPU affinity 可以保證的是這個 work 執行到一半，因為中斷或處理 IO 等任何理由被重新排程時，會保證重新執行時會在設定好的 affinity scope 上執行。當 work 被重新加入 workqueue 時，不一定會跟上一次有相同的 affinity scope。
在 [workqueue.h](https://elixir.bootlin.com/linux/v6.16-rc3/source/include/linux/workqueue.h#L246) 中可以找到`queue_work` 的定義，他會呼叫 `queue_work_on(WORK_CPU_UNBOUND, wq, work)`，這個函式會將 work 放到指定的 CPU 上，這邊傳入的是 `WORK_CPU_UNBOUND`。在檢查完 work 沒有在 workqueue 後，會呼叫 `__queue_work(cpu, wq, work)`。在 `__queue_work` 的實作內可以找到，若傳入的 `cpu` 參數為`WORK_CPU_UNBOUND`，則會呼叫 `wq_select_unbound_cpu()`，由此函式來決定 work 會運行在哪個 cpu 上。
## TODO: 重作 kxo
> [實作程式碼](https://github.com/thwuedwin/kxo)
### kernel module 流程 - IRQ
Interrupt Request (IRQ) 是由**硬體**發出中斷訊號，此時接受訊號的行程必須停下來處理中斷。中斷流程（interrupt context）中有幾個重要的限制：
- 中斷處理時間要盡可能短
- 不能呼叫會阻塞（blocking）的函數
因此 Linux 將中斷處理機制分為 top half 和 bottom half。
Top half 處理最關鍵、無法推遲的工作，例如：
- 確認中斷來源
- 回應硬體，避免重複傳送訊號
- **排定延遲工作（bottom half）**
其餘任務會被推遲至 bottom half 執行，也常被稱作 softirq。而 deferred work 是 Linux 核心提供的一種機制，用來安排任務在稍後以適當的 context 執行。Linux 核心透過這類機制來處理 bottom half。
本專案 deferred work 機制包括：
- timer_list
- tasklet
- [workqueue](https://docs.kernel.org/core-api/workqueue.html)
本專案透過 timer 觸發的 softirq 模擬硬體中斷作為主要流程。當 userspace 程式開啟裝置時，核心模組會排定一個 timer。當時間到達後，核心會呼叫處理函式 `timer_handler`。此函式會重新排定下一次 timer，因此會週期性地執行。
在 `timer_handler` 中，會啟動對應的 tasklet 作為延遲處理。tasklet 被執行時，會依據目前的遊戲狀態，將對應玩家和繪製棋盤的 work 加入 workqueue，負責 AI 運算和繪製棋盤。
`timer_handler` 運行於 softirq context，但會呼叫 `local_irq_disable()` 模擬 IRQ 中的 top half。tasklet 和 workqueue 則對應 bottom half。簡略的 kernel module 流程如下圖，這個流程會週期性的發生
接著我會說明不同的 deferred work 機制，最後才說明專案的整體流程。
#### 核心模組 - [Deferred work](https://linux-kernel-labs.github.io/refs/heads/master/labs/deferred_work.html#workqueues)
在開始後續討論之前，我想先釐清幾個常見的混淆點：
1.softirq 是什麼？
softirq（software interrupt request）是由軟體觸發的中斷機制，由 Linux 核心在編譯期間定義。使用者不應自行新增 softirq。以下是 Linux kernel 5.10.14 中定義的 softirq 類型，其中 TIMER_SOFTIRQ 與 TASKLET_SOFTIRQ 分別對應 timer 和 tasklet 的實作。
```c
enum {
HI_SOFTIRQ = 0,
TIMER_SOFTIRQ,
NET_TX_SOFTIRQ,
NET_RX_SOFTIRQ,
BLOCK_SOFTIRQ,
IRQ_POLL_SOFTIRQ,
TASKLET_SOFTIRQ,
SCHED_SOFTIRQ,
HRTIMER_SOFTIRQ,
RCU_SOFTIRQ,
NR_SOFTIRQS
};
```
在某些文件中，softirq 與 bottom half 常被混用，需特別注意。本文為避免混淆，將不以 softirq 作為 bottom half 的代稱。
2. 誰執行 deferred work？
雖然文件中將 deferred work 分為 kernel threads 與 softirq 兩類，workqueue 屬於前者，timer 和 tasklet 屬於後者。但實際上 softirq 也由專門的 kernel threads `ksoftirqd` 處理，而 workqueue 則由 `kworker` 負責。可使用 `ps aux` 命令查看。
3. tasklet 並非由排程器排程
tasklet 並非由 CPU 排程器排程。不過，英文文件中普遍使用 "schedule" 一詞描述安排 tasklet。為了討論方便，本文後續也將以「排程」來表示安排 tasklet 延遲執行的過程。
儘管實作細節各異，前述三種 deferred work（timer、tasklet、workqueue）有一個共通點：它們皆以一個 struct 儲存指定的處理函式，並在被排程時呼叫對應函式。以下為 kxo 中的使用實例：
- `timer_setup(&timer, timer_handler, 0);`
- `static DECLARE_TASKLET_OLD(game_tasklet, game_tasklet_func);`
- `static DECLARE_WORK(drawboard_work, drawboard_work_func);`
其中，timer 的機制相對簡單。透過 `mod_timer()` 可設定在指定時間後執行 `timer_handler`。值得注意的是，`timer_handler` 中包含 `WARN_ON_ONCE(!in_softirq())` 的偵錯語句，但該警告在測試中未被觸發，顯示 `timer_handler` 確實執行於 softirq context。這代表該函式不可被搶佔，並應避免執行過久或阻塞操作。
Tasklet 則透過 `tasklet_schedule()` 進行排程，與 timer 一樣執行於 softirq context。此外，tasklet 只能在觸發排程的 CPU 上執行，不能遷移（migrate）。
與前兩者不同，kxo 預設使用的 unbound workqueue **不執行於 softirq context**。因此 work function 可以被搶佔、允許執行較長時間，且可以在不同 CPU 之間遷移。由於作業要求 AI 雙方必須在不同 CPU 上執行，這涉及 workqueue 的設計與 CPU affinity。我將在後續章節中深入探討相關細節。
在 kxo 專案中， timer 週期性觸發 software interrupt，由 `timer_handler` 檢查遊戲是否已分出勝負，若是，則輸出結果並重設棋盤。否則呼叫 `ai_game` 進一步排程 tasklet。
在 `game_tasklet_func` 中，可以看到 tasklet 的職責是根據目前的遊戲狀態，將對應的 work 放入 workqueue。具體來說，透過變數 `turn` 判斷由哪位玩家下棋，並在 `finish` （代表上一位玩家已經完成）時，才才將下一位玩家的 ai work 加入 workqueue。無論挑選到哪位玩家，都會排程 `drawboard_work` 用於輸出當前棋盤。程式碼如下：
```
if (finish && turn == 'O') {
WRITE_ONCE(finish, 0);
smp_wmb();
queue_work(kxo_workqueue, &ai_one_work);
} else if (finish && turn == 'X') {
WRITE_ONCE(finish, 0);
smp_wmb();
queue_work(kxo_workqueue, &ai_two_work);
}
queue_work(kxo_workqueue, &drawboard_work);
```
觀察此段程式碼時，我產生了一個疑問：預設的 `delay` 為 100 毫秒，而 AI 的執行時間約為數毫秒至數百毫秒，經常超過 timer 的週期。依此推論，`drawboard_work` 應該會比 `ai_work` 更頻繁地被排入 workqueue，導致相同的棋盤被重複輸出多次。然而，從實際輸出的提示訊息來看，`drawboard_work` 與 `ai_work` 的執行次數相近。
理論上兩者的執行次數可能不同，可能出現同一棋盤被重複輸出，或某一步棋未被輸出的情況，但後者發生的機率極低，前者則相對常見。
造成這種現象的主因在於 `drawboard_work` 與 `ai_work` 共用了 mutex lock，彼此會互相等待鎖的釋放。雖然從程式碼邏輯上看起來執行順序應為：
`ai_one -> drawboard -> ai_two -> drawboard`
但實際上有可能出現如下情況，導致相同的棋盤被輸出兩次：
`ai_one -> drawboard -> drawboard -> ai_two`
更極端的狀況是：
`ai_one -> drawboard -> ai_two -> ai_one -> drawboard`
這可能導致 `ai_two` 落子的棋盤畫面被 `ai_one` 的下一步覆蓋，從而遺漏該次輸出。
不過這類情況相對罕見，主要是因為 AI 的執行時間通常較長（多為數百毫秒），而 timer 的 delay 僅為 100 毫秒，因此 `drawboard_work` 較頻繁地被排入 workqueue。由於 Linux 的 workqueue 機制會忽略已在隊列中的 work，因此重複排程不會造成執行次數暴增。在系統負載不高的情況下，`drawboard_work` 通常能順利取得鎖，避免棋盤更新遺漏。
#### 使用者層級程式和核心模組互動
使用者層級程式和核心模組互動主要透過兩個管道
1. 透過 sysfs，由使用者程式控制核心模組的運作
2. 透過 kxo 裝置檔案，經由 kfifo 將對弈資訊（棋盤和棋步）傳送至使用者層級
首先說明 sysfs 的部分。在插入核心模組會呼叫的 `kxo_init` 函式內，可以找到 `ret = device_create_file(kxo_dev, &dev_attr_kxo_state)`。
這個函式會透過虛擬檔案系統建立對應的裝置屬性，使得使用者層級可以透過對應的`show` 和 `store` 函式讀寫參數。使用者層級程式會透過修改 `display` 和 `end` 屬性來影響核心模組的行為。
- 將 `end` 設定為 '1' 表示遊戲結束，此時 `timer_handler` 將不再重新排程 timer，對弈流程終止。
- 將 `display` 設定為 '0' 表示遊戲暫停，核心模組仍持續運作，但不會將對弈資料輸出至 kfifo。
另一個管道則是透過 kfifo。核心模組會透過一個 $N\times N$ 陣列儲存目前的棋盤狀態，其中 $N$ 為棋盤邊長。並透過 `draw_board`轉換成符合格式的文字輸出，儲存至 `draw_buffer`。之後再由 `produce_board` 將資料寫入 kfifo，供使用者層級程式讀取。
#### 使用者層級程式
使用者層級程式 `xo-user.c` 使用 `select()` 同時監聽 stdio 和裝置檔案的輸入。stdio 設為 raw input mode，當使用者按下快捷鍵時，會呼叫對應的處理函式 `listen_kerboard_handler`，透過 sysfs 通知核心模組。kxo 中，預設的快捷鍵包含
- Crtl+P：暫停 / 重啟核心模組輸出
- Crtl+Q：結束遊戲。
我注意到原本的程式碼中，若在暫停遊戲的狀態下關閉程式，重新執行時會因 `display` 參數未重設，導致核心模組不輸出資料。由於裝置檔案為阻塞式讀取，程式會因此卡住。我提交了 [Pull Request](https://github.com/sysprog21/kxo/pull/23)，修正在開啟裝置檔案時重設 `display`，避免該問題發生。
裝置資料的讀取部分，會呼叫函式將接收到的資料轉換為棋盤圖樣進行輸出，這部分將在後續章節進一步說明。
整體流程為：
### 降低核心和使用者層級之間的通訊成本
> 相關 commit：[baa717a](https://github.com/sysprog21/kxo/commit/baa717a747a1352cd1fed31e7edbbb8f7afc345d)
本節嘗試透過壓縮儲存格式來降低核心與使用者層級之間的通訊成本，但實驗結果顯示，在目前的資料量下，並未帶來明顯效益。
原始實作中，核心模組會將棋盤內容繪製為人類可讀的棋盤樣式，再透過 kfifo 傳送至使用者層級程式。以 $4 \times 4$ 棋盤為例，每次傳輸長達 66 bytes。然而，實際上每個格子僅有三種狀態：`O`、`X` 或空白字元，因此理論上僅需 2 bits 即可表示。若使用緊密編碼，整個棋盤資料可壓縮為 4 bytes。
為評估壓縮效益，我進行了 1000 次傳輸測試，並將執行時間最長的 5% 作為離群值移除。結果顯示兩種資料格式的平均傳輸成本幾乎相同：原始格式（66 bytes）平均耗時約 0.114 秒，壓縮格式（4 bytes）為 0.116 秒。如圖所示，上圖為 66 bytes 的傳輸時間，下圖為 4 bytes 的傳輸時間：
由此可見，在目前這種小型資料量下，傳輸時間主要受到其他因素影響，而非資料大小。因此，壓縮棋盤資料並未顯著降低通訊成本，也使解碼與維護更加複雜，我認為在實務上並不划算。
### CPU affinity 與 workqueue
> 相關 commit：[585a5bb](https://github.com/sysprog21/kxo/commit/585a5bb50454737ecefbdea67a83dfb341e2d4d5)
作業要求中提到，兩個 AI 玩家應分別運行在不同的 CPU 上進行對弈。由於 AI 是透過 workqueue 來排程，這項需求與 workqueue 的行為息息相關。Workqueue 是由 kernel threads 的機制實作，主要可以分成 `WQ_UNBOUND` 和 `WQ_BH`，可在建立 workqueue 時指定。顧名思義，unbound workqueue 的 work 不綁定 CPU，允許 work 在不同的 CPU 上遷移。而 BH 則是 bottom half 的縮寫，可用來實現 bottom half 。
在 kxo 中，work function 會進行以下測試：
```c
WARN_ON_ONCE(in_softirq());
WARN_ON_ONCE(in_interrupt());
```
這代表 kxo 預設使用的 unbound workqueue 不是在 softirq context 中執行，可被搶佔、可發生 CPU 遷移。若改用 BH workqueue，這些警告會觸發，說明該 work 是以 bottom half 的方式執行，不可搶佔、不可遷移。
根據 Linux 核心文件的建議，除非工作具有嚴格的低延遲需求，否則建議使用 unbound workqueue。但這與作業要求不同，因為 unbound workqueue 不保證 work 會分佈在不同 CPU 上執行。
即使改用 BH workqueue，也只能保證單一 work 執行期間不會被遷移，但仍可能多個 work 被排在同一個 CPU 上。因此，為了保證兩個 AI work 分別運行於不同 CPU 上，必須額外設定更細緻的 affinity 規則。
Linux 核心提供了 `WQ_SYSFS` 這個旗標，在建立 workqueue 時加入，即可透過 sysfs 調整 workqueue 的屬性：
```shell
$ ls /sys/devices/virtual/workqueue/kxod/
affinity_scope affinity_strict cpumask max_active nice per_cpu power subsystem uevent
```
其中
- `affinity_scope`：定義 affinity 的範圍，預設是 cache，代表以 CPU 的快取作為邊界來分組。
- `cpumask`：定義哪些 CPU 可執行該 workqueue，十六進位形式（轉成二進位後，每一位代表一個 CPU）。
- `affinity_strict`：若設定為 1，表示嚴格遵守 affinity 規則，否則只是 best-effort。
```shell
$ cat /sys/devices/virtual/workqueue/kxod/affinity_scope
default (cache)
$ cat /sys/devices/virtual/workqueue/kxod/cpumask
fffff
```
我曾嘗試將 `affinity_scope` 設為 `cpu`，並開啟 `affinity_strict`，希望限制 work 綁定到某個 CPU。但即使如此，當 work 被重新加入時，仍有可能在不同的 CPU 上執行。
因此，我採取更直接的方法：建立兩個獨立的 workqueue，並將它們綁定到不同的 CPU：
- kxo_ai_oned 綁定至 CPU 0，cpumask = 00001
- kxo_ai_twod 綁定至 CPU 1，cpumask = 00002
透過 `dmesg` 觀察執行紀錄：
```shell
$ sudo dmesg | grep ai
[ 209.616342] kxo: [CPU#0] start doing ai_one_work_func
[ 210.037012] kxo: [CPU#0] ai_one_work_func completed in 410803 usec
[ 210.136175] kxo: [CPU#1] start doing ai_two_work_func
[ 210.139328] kxo: [CPU#1] ai_two_work_func completed in 3077 usec
[ 210.239957] kxo: [CPU#0] start doing ai_one_work_func
[ 210.534154] kxo: [CPU#0] ai_one_work_func completed in 287292 usec
[ 210.551989] kxo: [CPU#1] start doing ai_two_work_func
[ 210.552728] kxo: [CPU#1] ai_two_work_func completed in 719 usec
[ 210.656067] kxo: [CPU#0] start doing ai_one_work_func
[ 210.794226] kxo: [CPU#0] ai_one_work_func completed in 134910 usec
[ 210.864062] kxo: [CPU#1] start doing ai_two_work_func
[ 210.864409] kxo: [CPU#1] ai_two_work_func completed in 329 usec
[ 210.968105] kxo: [CPU#0] start doing ai_one_work_func
[ 211.083404] kxo: [CPU#0] ai_one_work_func completed in 112585 usec
```
可以觀察到 `ai_one` 和 `ai_two` 分別穩定執行於 CPU 0 和 CPU 1。
原本我希望在建立 workqueue 時，透過 `struct workqueue_attrs` 直接設定其 affinity，但相關 API 並未公開。最後，我改採在使用者空間透過 sysfs 寫入來修改 workqueue 屬性，達成需求。
> 題外話：bound 和 bounded 的差異
> bind, bound, bound：此時 bound 是 bind 的過去式或過去分詞。unbound 就是取過去分詞作為形容詞，加上 un- 字首代表沒有，意思是「沒有綁定」。
> bound, bounded, bounded：bound 單獨作為名詞也有邊界的意思。在討論數學或物理時，經常將其作為動詞，代表「限制在某範圍內」。
### 使用者層級程式動態選擇玩家 AI
> 相關 commit：[4ebb90a](https://github.com/thwuedwin/kxo/commit/4ebb90a111708abb584d4bd92d62e53410f15c45)
在核心模組參數 `kxo_attr` 中，新增了 AI 選擇的參數。當使用者按下 Crtl+A 時，會將遊戲暫停並切換到選擇 AI 的畫面，使用者可以透過數字鍵來為兩位玩家分別選擇 AI。在核心模組中定義了 AI 函式的原型
```c
typedef int (*ai_func_t)(const char *table, char player);
```
但原先的 `negamax_predict` 函式沒有遵守此規範，因此額外定義了一個 wrapper function。
```c
int negamax_wrapper(const char *table, char player)Add commentMore actions
{
char table_copy[N_GRIDS];
for (int i = 0; i < N_GRIDS; i++) {
table_copy[i] = table[i];
}
return negamax_predict(table_copy, player).move;
}
```
### `queue_work` 內的 memory barrier
`queue_work` 函式會檢查 work 是否已經在 workqueue 內。若該 work 不在 workqueue 內，會將該 work 加入。否則什麼事都不做，不會重複加入。在將 work 放入 workqueue 的過程中，會使用到 `smp_wmb()`，因此若加入成功就會保證 memory order 不變。在 kxo 的流程中，`ai_one_work` 和 `ai_two_work` 在 `queue_work` 時都保證不在 workqueue 內，因此該處不需要額外的 memory barrier。對此我提交了 [Pull Request](https://github.com/sysprog21/kxo/pull/22)。
## TODO: 觀摩其他學員的成果
> 紀錄你的啟發、你進行的驗證，以及後續改進
### 減少使用者層級和核心模組通訊成本
我參考了 [Andrewtangtang](https://hackmd.io/@Andrewyuntang/linux2025-homework3#使用-ftrace-進行效能分析)，發現我原本只用的圖表實際上沒什麼意義。於是我重新製圖為箱型圖。且我也有發現和他一樣的，減少資料量後反而通訊成本增加的情況。
下圖為重做的箱型圖，我的情況是箱體（25 % 到 75 %）大致相同，但 4 bytes 的離群值明顯更多更廣。
### loadavg
在 Linux 核心中可以透過 `/proc/loadavg` 來查看系統的負載。作業要求說明我們應該針對不同 AI 計算負載的機制。因此我嘗試計算每個 CPU 各自的負載。[loadavg.c](https://elixir.bootlin.com/linux/v6.16-rc2/source/kernel/sched/loadavg.c) 的做法是，他會每五秒讓每個 CPU 個別計算當前在該 CPU runqueue 的 task 數量。但這個做法是透過 `sched_tick()` 這個函式週期性地進行。這邊會產生幾個問題
1. `sched_tick` 應該是個成本較低的做法，但無法使用這個方法。在核心模組中可能可以用 timer 來實作，但我認為會增加額外的成本。
2. 最重要的是，取得 runqueue 數量的 API 並沒有公開
因此我認為很難實作 per-CPU loadav。
上述是我原本的想法，但我發現會有這樣的想法是因為我對 loadavg 的理解完全是錯的。loadavg 指的一定是系統整體的負載，從定義上就不存在 per-CPU loadavg。
會有這樣的誤解是我把 loadavg 和 cpu usage 搞混了。使用 `htop` 輸出的是 CPU usage，只的是單一 CPU 所使用的時間，100 % 代表所有時間 CPU 都在工作，可能是一個 CPU bound 的工作。而 load 則是看有多少工作在等待執行，必須要考慮系統有幾個核，因此只會有系統整體的負載。
我瀏覽了同學的作業後，發現 [wurrrrrrrrrr](https://hackmd.io/@Guanchun0803/linux2025-homework3#統計不同-AI-實作機制對系統負載的使用率) 有實作這個要求。他是以 AI 的執行時間計算，先不論做法是否正確，他算的一定是 CPU usage 而不是 loadavg。他的實作中有使用到 `EXP_1`，這是被定義在 `linux/sched/loadavg.h` 中的常數，他的意義是 `/* 1/exp(5sec/1min) as fixed-point */`。但這位同學的實作並沒有保證 5 秒計算一次，會導致錯誤的計算結果。
我目前沒有想到可以在不使用未開放 API 的情況下，計算 loadavg 的方法。
## 參考資料
- [kxo 作業說明](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo)
- [kernel 文件 - deferred work](https://linux-kernel-labs.github.io/refs/heads/master/labs/deferred_work.html#workqueues)
- [kernel 文件 - workqueue](https://docs.kernel.org/core-api/workqueue.html)
Sign in with Wallet
Connect another wallet