2025q1 Homework5 (assessment)

contributed by < TonyLinX >

預期目標

• 檢視前 6 週學習狀況 (含程式碼審查和課堂討論)
• 隨堂測驗和作業回顧
• 導入客製化作業，讓學員選擇改進第 1 到第 4 次的作業或自訂題目 (例如貢獻程式碼到 Linux 核心)，隨後安排授課教師和學員的線上一對一討論

檢視前 6 週學習狀況 (含程式碼審查和課堂討論)

第一周的部份

make test 的最後一個 Testing case 目前還尚未通過，這部份應該可以透過 perf 來找到問題。
這個 Testing case 是在測試 q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head 的 time complexity 是否為 constant。 很神奇的是，我每次執行的結果不同，有時會通過有時不會通過。

學到的東西：

• 為何需要指標的指標
  以這段程式來說，我們期望透過 func 去將 ptrA 變成指向到 B，但只用指標是作不到這件事情，ptrA 還是指向 A，原因就在於我們改動的東西是 ptrA 複製出來的值，並非是真正的去改善 ptrA，所以為了改變一個指標的內容，我們需要使用指標的指標去 ptrA 的位址跟改它的內容。

  ​​​​int B = 2;
  ​​​​void func(int *p) { p = &B; }
  ​​​​int main() {
  ​​​​    int A = 1, C = 3;
  ​​​​    int *ptrA = &A;
  ​​​​    func(ptrA);
  ​​​​    printf("%d\n", *ptrA);
  ​​​​    return 0;
  ​​​​}
  

• 理解 Linux 風格的鏈節串列是如何實做的，以及 list_head 的使用方式。

第二周的部份

作業是我最有印象的部份，之前剛見到這些 code 的時候，又長又有一堆我不熟悉的 bit-wise 操作，第一次看的時候我完全看不懂，又沒有耐心把之前的老師的教材給看完，導致這個難度的問題，我就放棄了。不過，就在某一天，我突然想通了，我好好的把第一章跟第二章的教材給讀完，我發現題目突然沒有當初想像的那麽困難，我發現這種難度的問題我再也不會感到挫折放棄，反而是可以定下心來，把問題解完。

學到的東西：

• bitwise 操作

  • set a bit
  • clear a bit
  • toggle a bit
  • test a bit
  • the right/left most byte
  • sign bit
  • 乘上 10
  • 判斷奇偶數
  • 取絕對值 (不用分支)
  • Swap (不需要 temp)
  • 檢查一個數是不是2的次方

• 你可能沒想過的 Memory

  • overcommit（超額分配）以及 Lazy Allocation（延遲配置）：
    Linux 允許程式透過 malloc 或其他方式申請的總記憶體空間超過實際的物理記憶體（RAM）與 swap 空間的總和。這種策略稱為 overcommit，目的是讓系統更有效率地利用記憶體，因為多數程式申請的大量記憶體其實「不會全部用到」。
    當程式呼叫 malloc 申請記憶體時，系統通常只會分配一個合法的虛擬位址空間給你，而不會立刻配置實體記憶體。只有當你第一次「寫入」這塊記憶體時，才會產生 page fault（頁面錯誤），這時系統才會真正分配一個實體記憶體頁面給你使用。這種策略叫做 Lazy Allocation，目的也是考量到效率。
    雖然 Linux 預設允許 overcommit，但如果你實際存取的記憶體超過了物理 RAM + swap 的上限，系統就可能會啟動 OOM Killer，把某些程式殺掉。

• data alignment（資料對齊）
  data alignment 指的是資料在記憶體中的位址必須是某個 2 的冪次方（如 1、2、4、8）的倍數。這樣做是為了讓 CPU 存取資料更有效率。例如，int 通常要求 4 byte 對齊，代表它的位址要能被 4 整除；double 要 8 byte 對齊，位址要能被 8 整除。為何要這樣做呢？
  因為 CPU 擷取資料不會只抓取 1 byte，現在的電腦都是 32 位於或 64 位於都可以一次讀取 32 bit 或 64 bit 的資料。假設某個變數的型態為 int，若 CPU 每次都只抓取 1 byte，就必須要抓 4 次，效率低落，於是 CPU 通常一次擷取 4 或 8 byte ，並依序存取。

• Bit Fields
  Bit Field 是 struct 成員的一種特殊語法，允許你指定該成員只佔用幾個 bit。
  以下面的程式來說，unsigned int 是 4 bytes，但我們可能不需要那麽多，或許只要 2 bits 而已，那就可以透過 bit fields 來減少記憶體的浪費。

  ​​​​struct MyBits {
  ​​​​    unsigned int x : 4;  // 只用 4 bits 表示 0~15
  ​​​​    unsigned int y : 2;  // 只用 2 bits 表示 0~3
  ​​​​    unsigned int z : 1;  // 可以當成布林值
  ​​​​};
  

• 理解 Linux 風格的 hash 如何實做的

  • 為什麼 hlist_head 只設計成一個 first 指標？
    因為在 hash table 的 bucket 裡，通常只需要一個指標來指向這個 bucket 的第一個節點。如果採用和 list_head 一樣的雙向鏈結設計（同時有 next 和 prev），每個 bucket 都會多浪費一個指標的記憶體。好的 hash table 衝突較少，所以某些情況下 bucket 數量會非常多，這會造成大量不必要的記憶體開銷。為了節省空間，hlist_head 只保留一個指向第一個節點的指標。
  • 為何需要指標的指標 (**pprev)？
    若 hlist_node 採用的是單指標，由於 hlist_node 是兩個指向 hlist_node 的指標，所以在鍊結串列的第一個 hlist_node 它的 *pprev 只能指向 NULL，所以說當你要移除第一個 hlist_node 時，就要特殊處理。為了解決這個特殊例子，才需要指標的指標 (**pprev)。每個節點的 pprev 指向「指向這個節點的那個指標」（可能是 bucket 的 first，也可能是前一個節點的 next），這樣的設計可以讓我們在刪除任何節點時，直接把前一個節點（或 bucket head）指向它的指標，改為指向下一個節點，然後再把下一個節點的 pprev 一起更新，確保鏈結完整，無需額外尋找上一個節點的位置。

待完成：

• GDB
• 多執行緒的教材
  • 針對多執行緒環境設計的 Memory allocator
  • rpmalloc 探討
• glibc 的 malloc/free 實作

第三周的部份

學到的東西：

• Improving accuracy: Number summation
  知道 Kahan 的修正方式，主要的核心概念是在每次加法前，使用一個變數 corr 來記錄上一次加法產生的浮點誤差，並在下一次計算中調整輸入值以補償這些誤差，使得總和更精確。

給自己的評語

我比較的對象是剛學習這堂課的自己。剛開始接觸這門課時，我其實沒有足夠的耐心去完整閱讀教材，總是急於進展，結果反而陷入挫折感當中。那時候的我一度感到迷惘，也逐漸對自己失去了信心。
不過現在我想通了。這幾天，我重新靜下心來，把老師提供的教材從頭到尾仔細看了一遍。我意識到自己雖然已經落後了幾週的進度，但我並不打算放棄。相反地，我希望能在剩下的幾週中，全力以赴彌補過去的不足。
我也開始思考一個期末專案的方向，想要做一個與 Linux kernel 有關的專案，嘗試解決一個真實存在的問題。

閱讀心得 - 因為自動飲料機而延畢的那一年

從這個故事中，我學到了一件非常重要的事——知識就是力量。光有熱情與努力，並不足以讓事情真正推動起來。這個故事也讓我回想起大學時，和朋友們一起進行的各種計畫。那時候，我們常因為不熟悉其他領域的知識，導致許多問題處理起來格外吃力。久而久之，這些困難逐漸消磨了大家的熱情，最終許多計畫都不了了之。對我而言，裡面有一句話特別深刻、也非常受用：

「Jserv 說：你不能現在就放棄。要是現在就放棄的話，將來遇到這種等級的困難時，你只會選擇逃避。」好友 F 補充道：「而且你會一輩子被他笑。」

我正在修習 Linux 這門課，坦白說，心態常常崩潰。我常常想：為什麼這個世界進步得這麼快？為什麼我都不知道這些事？是不是我真的能力太差？雖然我不是從很有名的大學推甄到成功大學，但在我原本的學校中，我的表現其實一直不差。那為什麼我和這堂課的同學差距這麼大？這種無力感與挫折感一天天加重，讓我開始害怕去接觸這門課的知識。我甚至不知道自己該怎麼辦才好。不過，看完這篇文章後，我重新找回了一些信心。也讓我想起老師常說的一句話：「誠實面對自己」。即便自己的程度真的不夠好，只要願意正視問題、勇敢補足不足，那就不需要感到可恥。反正缺什麼，就補什麼。

研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e，並提出問題

• 如何在 無浮點運算單元（FPU） 的嵌入式環境中實作幾何平均（geometric mean）計算，使其能有效避免 overflow 並將誤差控制在小數點後第六位以內？
  後續與老師討論結果
• 在 thread pool 的實作中，我採用了 lock-free 設計（基於 ring buffer + semaphore），以避免 main thread enqueue 與 worker thread dequeue 所可能產生的鎖競爭。然而，在實際測試中，其 throughput 卻明顯低於傳統的 lock-based 設計（基於 mutex + condition variable）。請問造成這個現象的可能原因是什麼？

期末專案討論

職缺

• Software Engineer, Server System, Google Cloud Platform
• Linux系統軟體工程師

自己的想法

我自己上網查了部分主流公司，每間公司都有開放出與 Linux kernel develope 的職缺，曾經也在成大的 seminar 上詢問某科技公司的講者，也告訴我會有 linux kernel 開發經驗是非常不錯的，因為有許多人都還不會與 kernel 溝通，所以在這堂課的期末專題，我想開發關於 linux kernel 相關的專案。

我自己感興趣的專案就是: kxo, 並行程式設計, 虛擬化和容器化, 檔案系統

閱讀內容：

• 並行程式設計: 排程器原理
• Scheduling Internals
• KVM : Linux 虛擬化基礎建設