2024q1 Homework5 (assessment)

contributed by < MathewSu-001 >

注意書寫規範！

閱讀〈因為自動飲料機而延畢的那一年〉

紀錄閱讀〈因為自動飲料機而延畢的那一年〉的啟發，特別在學習本課程 5 週之後的感想，應具體描述你在課堂、課後創作，和觀摩其他學員的成果時，理解到系統軟體的開發態度、對細節的重視，以及理論和實務的融會貫通。

看完這篇的感觸就是，這根本就是我大四畢業專題的坎坷路程。

成大系統系的畢業專題就是，打造一艘無人船並且完成指定任務，我被分配到的工作就是，識別數字閘門並且行經它。很喜歡文章作者的一段話

硬體設計就是不斷的重複「設計、製造、修正」的循環，想像中的設計會經過有誤差的方式被製造出來，製造出來的產品在現實中運作的效果不如預期，找到問題的根源後再重新修正，機械設計就是重複這樣的循環。只有把東西生出來做實驗，你才會知道該如何改進。

沒有實際將船放入水中作測試，根本不會知道船體搖晃程度會影響到識別結果；也不會知道水中倒影也會影響到識別；甚至 LED 光板也會影響到成果。

這也證實了老師一直強調的一件事，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。如果沒有將所有細節都考慮進去的話，那麼實做 出來的結果只是一團亂而已。

「實作」

簡述想投入的專案

參照 2023 年期末專題，簡述你想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個。

1. 作業3 ttt 來不及做，想要將該作業完成。
2. 透過 Netfilter 自動過濾廣告

儘管我們可在網頁瀏覽器中透過像是 AdBlock 這類的 extension 來過濾廣告，但需要額外的設定和佔用更多系統資源，倘若我們能透過 netfilter，直接在核心層級過濾網路廣告，那所有應用程式都有機會受益。

• 參考資訊:
  • How to drop 10 million packets per second
  • Use the iptables firewall to block ads on your Linux machine
  • nBlock
  • 2020 年開發紀錄
• 執行人: ItisCaleb → 開發紀錄

3. 紅黑樹實作改進

重做第 3 週測驗題 的測驗一及第 4 週測驗題的測驗一，彙整其他學員的成果，連同延伸問題

• 執行人: koty6069 → 開發紀錄
• 執行人: LiChiiiii → 開發紀錄
• 執行人: EdwardCKC → 開發紀錄

TODO: 針對定點數開平方根程式碼 (fixed_sqrt)，提出其有效輸入的最大值並檢驗

注意 MSB

在查閱了 __builtin_clz(x) 的描述後發現，其內容是這麼寫道：

Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

也就是說他在傳入值時，已經將 x 的資料型態轉換為 unsigned ，只有 32 位元。當與老師進行討論時，老師特地要我檢查超過

$2^{16}$ 的數值也能夠理解了。

我在作業三浮點數轉換成定點數過程中，我將 fraction bits 設為 16 。因此一旦浮點數值超過

$2^{16}$ 和轉換成定點數後，就會造成資料損失，並且回傳值永遠都一樣。

因此我將原本的 __builtin_clz(x) 轉換為 __builtin_clzl ，在 GCC 中的解釋如下：

Built-in Function: int __builtin_clzl (unsigned long)
Similar to __builtin_clz, except the argument type is unsigned long.

根據 Q (number format) ， UQ47.16 可以表示的最大值為

$2^{47}-2^{-16}$。所以在沒有進行其他程式碼的改動下，測試最大值得結果如下，結果的差異沒有很多：

$ gcc -o ./sqrt sqrt.c  -lm
$ ./sqrt 
number = 140737488355328, float result = 11863283.203031, and fixed result = 11863283.199219

487663e

TODO: 閱讀 https://hackmd.io/@sysprog/concurrency 並動手確認

7 月 7 日中午前完成
涵蓋概念, 排程器原理, 執行順序, Atomics 操作, POSIX Threads, 實作輕量級的 Mutex Lock, Lock-free 程式設計, 案例: Ring buffer