# 2024q1 Homework2 (quiz1+2) contributed by < `yutingshih` > 程式碼:[linux2024-quiz](https://github.com/yutingshih/linux2024-quiz) on GitHub ## 第一週測驗題 ### 測驗 1 #### 程式運作原理 測驗題中提供的程式參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 所實作的非遞迴 (non-recursive; iterative) 快速排序法,以堆疊取代遞迴函式呼叫,避免後者所帶來的額外開銷。 其中以 `begin` 和 `end` 兩個堆疊記錄串列中尚未排序好的部分,在每一輪迭代當中,會先選定 pivot 為串列首個節點,然後將整個串列分成比 pivot 小的左半部分、pivot 本身以及比 pivot 大的右半部分,並依序將其各自的起點及終點推入 `begin` 及 `end` 堆疊當中。 例如:左半部分有 `A`、`B`、`C`、`D` 四個節點,pivot 為 `D` 節點,右半部分則有 `F`、`G`、`H` 三個節點 ``` left : A -> B -> C -> D pivot : E right : F -> G -> H ``` 接著將三者的起點和終點各自推入堆疊 ``` index | 0 1 2 3 4 ... 7 ------+--------------------- begin | A E D end | D E H ``` 在下一輪迭代則從堆疊中拿取其中的半邊,也就是子串列 `D` 到 `H` 繼續進行排序 #### 改進實作 <!-- 使用 Linux 核心風格的 List API 改寫上述程式碼,並針對鏈結串列,提出可避免最差狀況的快速排序實作,應設計效能評比的測試程式。 --> ### 測驗 2 #### 程式運作原理 先解釋 Timsort 實作中重要的函式功能及重點: - `find_run` 會從串列的開頭開始切出一段單調 (monotonic) 的子序列,若為遞減序列,則會將其調整為遞增序列後回傳 - `merge_at` 依照給定的比較函式 `cmp`,合併堆疊最上層的的兩個 runs - `merge_collapse` 則會檢查堆疊 `tp` 中最上層的三個 runs 是否滿足以下條件,若不滿足則挑選 `tp->prev->prev` 及 `tp` 中較短者與中間的 `tp->prev` 進行合併,用來確保被合併的兩個 runs 長度盡可能接近 - `tp->prev->prev` 長度大於 `tp->prev` 和 `tp` 的總和 - `tp->prev` 長度大於 `tp - `merge_force_collapse` 則不做上述條件的檢查,直接挑選 `tp->prev->prev` 及 `tp` 中較短者與中間的 `tp->prev` 進行合併 - `merge` 將兩串列合併後回傳 - `merge` 將兩串列合併後使用 `build_prev_link` 重建雙向環轉鏈結串列的鏈結 #### 改進實作 #### 整合 <!-- 將改進過的 Timsort 實作整合進 sysprog21/lab0-c,作為另一個有效的排序命令,應設計效能評比的測試程式,確保測試案例符合 Timsort 設想的資料分布樣式。 --> ## 第二週測驗題 ### 測驗 1 #### 程式運作原理 <!-- 解釋上述程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作 --> #### 測試程式 <!-- 在 Linux 核心的 cgroups 相關原始程式碼,找出 pre-order walk 程式碼並探討 --> ### 測驗 2 #### 程式運作原理 <!-- 解釋上述程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作 --> #### 測試程式 <!-- 在 Linux 核心找出 LRU 相關程式碼並探討 --> ### 測驗 3 #### 程式運作原理 `find_nth_bit` 的功能是找到第 n 個為 1 的位元,回傳其為整個搜尋範圍中的第幾個位元,並 LSB (least significant bit) 定義為第 0 個位元,若找不到,則回傳搜尋範圍的大小 `size`。 `find_nth_bit` 使用到 `FIND_NTH_BIT` 巨集及 `fns` 函式 `fns` 函式透過重複呼叫 `__ffs` n 次來尋找一個字節 (word) 中第 n 個為 1 的位元的位置,每次呼叫 `__ffs` 後都會將該位元清空,連續呼叫 n 次就相當於尋找第 n 個為 1 的位元。 `GENMASK` 巨集產生自第 `l` 到第 `h` 位元為 1 的遮罩 (mask),其中最低位編號為 0 `small_const_nbits` 檢查 `nbits` 是否為大於 0 且小於等於 `BITS_PER_LONG` 的常數 `__const_hweight8`、`__const_hweight16`、`__const_hweight32` 以及 `__const_hweight64` 分別計算最低數個位元當中有多少個為 1 的位元,`hweight_long` 則和 `__const_hweight64` 行為相同 `FIND_NTH_BIT` 首先逐字節判斷是否存在第 `num` 個位元為 1,若目標存在於當前字節,則呼叫 `fns` 函式尋找第 n 個為 1 的位元,找不到則直接回傳 `size`。 <!-- 在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例,並予以解說和分析,需要涵蓋 CPU affinity 相關的原始程式碼。 -->
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up