版本 a039cb1fcc17df994121b2c6ec0fbb921c1a7cad
thwuedwin (吳宗翰)
簡介
2025 Linux 核心設計 自我評量
成果發表和貢獻
評分：6 分
我並未在閱讀教材時發現重大的錯誤，僅針對錯字、排版等問題進行修正。
在進行期末專題時，在我深入了解 kxo 專案流程和 workqueue 實作後，發現 kxo 專案中有不必要的 memory barrier 和流程的錯誤。對此我提交了對應的 pull request 列在下方。（截至 2025/07/02，尚未被接受）
在 2025-05-27 問答簡記 中，被指派說明 malloc 中的 mutex lock，和 heap 的關聯在哪？我原本對 heap 的理解僅有「放 malloc 變數的地方」，我詳閱了 linux 手冊和 glibc 關於 malloc 的說明後，了解到 heap 在 malloc 的實作上確實是一個資料結構，也了解了其功能，並得以和同學們分享。
- 教材修改
- 2025/07/02：修正中文敘述中的半形冒號
- 2025/07/02：將誤用的「除」改為「除以」
- 2025/06/21：修正錯字，抑或運算 \(\to\) 異或運算
- 2025/07/02：glibc 的 malloc/free 實作章節修正排版，將英文單字、標點符號加上空格。
- Pull Request
作業/隨堂測驗
評分：5 分
我的作業僅完成前兩份，以我自身學習的角度獲益良多，但並沒有重要的突破，下列僅記錄我所學的收穫。
我過去對鏈結串列的理解僅停留在紙面上，對指標的操作也不熟悉，這次作業讓我認真面對指標的操作。
- 學習使用間接指標以避免需要將首節點當作特例處理，或需要額外配置暫存用節點。
- 這次作業是我第一次接觸到「快慢指標」的概念，我運用這個概念，將其應用到 q_reverseK 的實作上。q_reverseK 會將串列切割成長度為 K 的子串列，將子串列反轉。我原本的做法是用額外的計數器來取得子串列，但我受到快慢指標的啟發，使用快指標來標記子串列的結尾，便可以省去額外的計數器。
- 學習撰寫文件。我原本對文件的寫法是說明這段程式「做了什麼」。經過授課教師上課的說明，我發現更重要的是「為什麼要這樣做」、「為什麼要這樣設計」。例如 q_new 是一個配置新節點的函式，我原本認為這個函式根本不需要特別說明，只要說明參數和回傳值即可。實際上應該要說明這個函式會動態配什麼變數、由誰來管理、需要由誰來釋放。
- 從 〈Dude, is my code constant time?〉 了解到 t-test 是通過比較兩個不同的機率分布，來驗證時間複雜度。並了解到實務上，不能只看理論上提出的複雜度。
- 分析快速排序法（quick sort）的最差情況是發生在樞紐值為最大值（或最小值）的時候。
- 一般的快速排序法沒有保證為穩定（stable）排序，我透過嚴格規定插入時的順序，達成穩定的快速排序法。並使用 perf 分析快速排序法和合併排序法的效能差異。
- 作業要求實作浮點數開平方根。我這很草率地認為浮點數開平方根只需要把小數部分和指數部分分開處理，非常簡單，因此我看過就認為自己會了，沒有動手實作。但實際上有很多需要注意的細節。這是我因為沒有重視細節導致的沉痛的教訓，詳細說明我寫在後續與授課教師的互動章節內。
期末專題
評分：10 分
我分配到的期末專題是重作 kxo。我在過去做第三次作業時，因為我完全沒有接觸過核心模組，也不了解 Linux 中斷處理的機制，卻急著開始做作業，導致什麼都沒做出來。在課堂上，授課教師說：「與其把所有事草草做完，還不如把一件事做好」。因此這次開始做專題前我先詳閱了教材，了解了中斷處理機制後，再一步一步地找出 kxo 使用的 softirq 機制和其使用的回呼函式，才終於搞懂核心模組的主要流程。其中遇到許多困難，一步一步解決的過程讓我瞭解到重視細節與否的差異。
- 透過 dmesg 輸出的提示訊息，我誤以為 workqueue 是 FCFS，在我查閱文件和 workqueue.c 實作後，發現 work 是由排程器排程，不像 tasklet 是單純的排隊循序執行。重新檢視程式碼後，我才發現原來是因為 work 中有使用 mutex lock，才會產生一次只有一個 work 執行的錯覺。在閱讀 workqueue.c 實作時，我發現 queue_work 函式有使用 memory barrier，因此提交了 pull request #22。
- 作業要求兩個 AI 玩家執行在不同的 CPU 上，但我發現預設的 unbound workqueue 沒辦法達成，我使用兩個獨立的 workqueue，並透過 CPUMASK 來使 AI 只能執行在指定的 CPU 上。
- 在使用者程式暫停時關閉遊戲會造成無法重新啟動。我發現是因為關閉使用者程式時沒有重設參數，導致 device 沒有輸出，會被讀取 device 阻塞。對此我提交了 pull request #23。
若我急於開始實作，沒有靜下心詳讀文件和原始實作，一定沒辦法解決這些問題。
與授課教師的互動
評分：10 分
一對一討論時，老師問我如何實作浮點數開平方根，輸出為整數。我當下認為只需要把小數部分和指數部分分開處理，先把確保指數為偶數，若是奇數就把小數乘 2，指數減一。接者只需處理整數平方根，再乘上 \(2^{exp/2}\)。但當下發現我連 IEEE 754 的規範都沒有搞清楚。後續實作時，簡單測試就發現因為捨棄太多精度，只有在數字很小的時候是正確的。接著我不斷地試圖增加儲存的精度，但仍然會發現保留的精度不足。在一次一次的測試過程中，我都確實計算和測試，檢驗我保留的精度和開始出現錯誤的數字大小是否符合預期，並進行修正。最後我使用兩個 64 位元整數來模擬 128 位元整數進行運算，才終於可以對所有正浮點數輸出精確的結果。我最初實作的方式是 digit-by-digit 的方式，我同時也進行了牛頓法和二分搜尋法的比較。詳細過程我記錄在浮點數開平方根實作。
以下列出我在實作過程中釐清的 IEEE 754 性質
- 指數部分為 0 時為 denormal number，implicit leading bit 為 0
- 指數部分為 255 時為 inf 或 NaN
- 指數部分為 1 - 254 時為 normal number，implicit bit 為 1
- IEEE 754 四捨五入，f*f 和整數直接比較需要注意捨入誤差
在一對一討論之前，我以為我了解 IEEE 754 的規範，也以為我了解開平方根的方式。在經過這一連串的構思、實作、錯誤、修正的過程中，重視其中細節，現在我才敢說我對浮點數開平方根有一定的理解（IEEE 754 還是太深奧，我理解尚淺）。
所見所聞所感
評分：10 分
〈因為自動飲料機而延畢的那一年〉中，他們要做的事情聽起來很簡單，但實際上充斥著各種意想不到的細節，他們不斷地嘗試、不斷的錯誤，最後才成功做出飲料機。和這堂課給我的感覺一樣。在過去，若我發現浮點數精度不足，我可能會想「float 不夠，那就用 double 吧」。若我還是維持這樣的做法，我一定沒有辦法做出浮點數平方根。我在2025-06-24 問答中，部分回答被授課教師認可，這也是因為我在做專題時多次仔細地研讀 workqueue 文件才能做到。這些經驗讓我了解重視細節的重要性，在過去學校的教育中，即使不重視細節也可以拿到高分，這堂課帶給我很不一樣的經驗。重視細節的最基本就是要先把文件看懂，而不是看著函數名稱用猜的，急於開始實作。實作後也需要做實驗檢驗、在撰寫文件的過程中重新反思，才有辦法做好事情。這是我這堂課很重要的收穫。
我本身在撰寫文件時非常重視排版和用詞，這點和這堂課的理念相同。在撰寫文件的過程中我發現了很多我不好的寫作習慣。我平常太常使用「晶晶體」，有可能是我的物理背景留下的習慣。這學期我在撰寫文件時，若有常用的翻譯，便會選擇適當的中文，例如鏈結串列或是佇列，在過去我都習慣直接使用英文。我也發現我的文法混合著中文和英文，這些都是我需要持續努力的方向。
自我評量 (1 ~ 10)
\(GEOMEAN=(6\times5\times10\times10\times10)^\frac{1}{5}=7.860030856\)
方案 B：\(1 + floor(GEOMEAN)=8\)
