# 2024q1 Homework6 (integration)
contributed by <`jychen0611` >

## 自我檢查清單
>- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
>- [x] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、`MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？
> 〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。
>- [x] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree);
> 參照 [2021 年的筆記](https://hackmd.io/@linD026/simrupt-vwifi)。歡迎貢獻 LKMPG!
> $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
>- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
>- [ ] 研讀 [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) (Concurrency Managed Workqueue) 文件，對照 [simrupt](https://github.com/sysprog21/simrupt) 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
>- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
> $\to$ 搭配閱讀: [不亂的「亂數」](https://blog.cruciferslab.net/?p=599)
>- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
## 整合井字遊戲對弈
>* 在 GitHub 上 fork [simrupt](https://github.com/sysprog21/ksort)，目標是整合[第三次作業](https://hackmd.io/@sysprog/linux2024-ttt)提及的人工智慧程式碼，主體應在 Linux 核心內運作，讓二個不同的井字遊戲人工智慧演算法執行在「不同的 CPU」(善用 CMWQ) 並模擬二者的對弈，並允許使用者層級的程式藉由開啟 `/dev/simrupt` (可適度更名) 來設定二個人工智慧程式的對弈並存取彼此的棋步
* 務必在 Linux 核心模組中使用定點數
* 其一演算法必是 MCTS，另一者可參照[第三次作業](https://hackmd.io/@sysprog/linux2024-ttt)或 [jserv/ttt](https://github.com/jserv/ttt) 專案近期整合的 ELO rating system
* 查閱 CMWQ 的文件，指定前述不同的人工智慧演算法固定在不同的 CPU (如 `CPU #0` 和 `CPU #1`)，應該要能從使用者層級指定對弈的起始、暫停、恢復，和瀏覽狀態，Linux 核心模組和使用者層級的程式藉由 `/dev/simrupt` (可適度更名) 裝置檔案互動，注意需要擴充 VFS 註冊的檔案操作
* 模擬對弈過程，前述二個人工智慧演算法程式碼在執行時間，應適度停頓 (數百個 millisecond)
* 使用者層級的程式應能清楚繪製出 Linux 核心模組的對弈過程，在終端機展現 (你也可改用 SDL 一類的圖形函式庫繪製)