---
title: 2024 年 Linux 核心設計/實作課程作業 —— integration (E)
description: 引導學員開發 Linux 核心模組，預期知悉核心模組如何掛載進入 Linux 核心、Virtual File System (VFS) 概況、character device driver 撰寫，和準備對應的測試及效能分析工具
tags: linux2024
---

# M06: integration

:::warning
:warning: 請務必詳閱作業描述 [(一)](/@sysprog/linux2024-integration-a), [(二)](/@sysprog/linux2024-integration-b), [(三)](/@sysprog/linux2024-integration-c) 及 [(四)](/@sysprog/linux2024-integration-d)
:::

> 主講人: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2024 年系統軟體課程](https://www.facebook.com/groups/system.software2024/)
:mega: 返回「[Linux 核心設計/實作](https://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表

## 自我檢查清單
- [ ] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 閱讀〈[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 以上。
- [ ] 閱讀《[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) 在排序過程中的平均比較次數，並提供對應的數學證明;
> 對照 [fluxsort](https://github.com/scandum/fluxsort) 和 [crumsort](https://github.com/scandum/crumsort) 的分析和效能評比方式
- [ ] 研讀 [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 排程器互動？
> 搭配閱讀《Demystifying the Linux CPU Scheduler》
- [ ] 解釋 `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 達到並行的排序;

## :rocket: 作業主題一: 並行的混合排序
* 在 GitHub 上 fork [ksort](https://github.com/sysprog21/ksort)，目標是整合[第一週測驗](https://hackmd.io/@sysprog/linux2024-quiz1)提到的 Timsort、本次作業說明提及的 Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c)，並確保可從使用者層級的程式對裝置檔案進行設定 (如 `write` 系統呼叫)，讓這些排序實作存在於同一個 Linux 核心模組，並得以切換和比較
* 過程中需要量化執行時間，可在 Linux 核心模組和使用者空間 (userspace) 中測量。在 Linux 核心模組中，可用 ktime 系列的 API，而在使用者層級可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API，分別[用 gnuplot 製圖](https://hackmd.io/@sysprog/Skwp-alOg);
* 善用統計模型，除去極端數值，過程中應詳述你的手法;
* 需要針對不同的情境去準備測試資料;
* 考慮到產生亂數的時間和可預測性，改用 xorshift128+ 作為 PRNG，並善用 `xoro` 核心模組
* 善用 CMWQ 達成排序的並行處理，需要設計對應的檢驗程式;

## :train2: 作業主題二: 整合井字遊戲對弈
* 在 GitHub 上 fork [simrupt](https://github.com/sysprog21/simrupt)，目標是整合[第三次作業](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 一類的圖形函式庫繪製)
* 考慮到 PRNG 的效率，改用 xorshift128+ 或其他執行成本更低的演算法，並評估對於 MCTS 的影響

## :penguin: 作業要求

* 回答上述==自我檢查清單==的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 自「作業主題一」和「作業主題二」選出一項 (當然你也可都投入) 進行
* 書寫 [HackMD](https://hackmd.io/) 筆記作為開發紀錄，規範如下:
* 標題格式固定為 ==2024q1 Homework6 (integration)==，其中 "integration" 是小寫，**2024q1** 表示「2024 年第 1 季」
* 共筆內容的第二行則為 **contributed by < `你的GitHub帳號名稱` >**
* 確保你的 GitHub 帳號是有效的，留意空白字元
* 無論標題和內文中，**中文和英文字元之間要有空白字元** (對排版和文字搜尋有利)；文字訊息請避免用圖片來表示，否則不好搜尋和分類
* [共筆示範](https://hackmd.io/@sysprog/linux2022-sample-lab0) $\leftarrow$ 務必詳閱 [HackMD 教學](https://hackmd.io/s/quick-start-tw)
* 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
* 不要在筆記內加入 `[TOC]` : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
* 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，主要作為是評分和接受同儕的檢閱，不是彰顯「個人風格」的地方
* 當[在筆記中貼入程式碼](https://hackmd.io/c/tutorials-tw/%2Fs%2Fhow-to-use-code-blocks-tw)時，避免非必要的行號，也就是該手動將 `c=` 或 `cpp=` 變更為 `c` 或 `cpp`。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」裡頭程式碼展現的方式
* 留意科技詞彙的使用，請參見「[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)」
* 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
* 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
* 撰寫的過程中，可善用 ChatGPT 一類的工具，但需要明確標示並指出裡頭謬誤和不精確之處。搭配 [ChatGPT cheatsheet](https://quickref.me/chatgpt)
* 填寫 [Google 表單](https://docs.google.com/forms/d/e/1FAIpQLSdOknJZpyQUMOwSNUBys1y5hvOGFX1UikuZ-508p9uePF-CKA/viewform)，提交開發紀錄，當系統檢查完畢時，預期將在 :rocket: [作業區](https://hackmd.io/@sysprog/linux2024-homework6)見到登記的 HackMD 超連結
* :warning: 不用等到作業完成才填寫表單，當你開始進行作業時，即可填寫表單，系統會進行必要的檢查工作。

## 截止日期
Apr 29, 2024 (含) 之前
越早在 GitHub 上有動態、越早接受 code review，評分越高

## 作業觀摩
* [2023 年春季班](https://hackmd.io/@sysprog/linux2023-homework3)