2025q1 Homework5 (assessment)

contributed by < HenryChaing >

研讀課程教材

繼上次作業三之後，接著要繼續研究第三週後續的教材。

---

並行程式設計: 排程器原理

• 首先講到的是並行程式設計的排程器原理，這裡要研究的排程器是使用者空間的任務排程器，我們會探討多個任務之間的轉換方式以及事件驅動。任務間又分成協同式多工以及搶佔式多工，協同式多工又可解釋成非搶佔式多工，它的 context switch 可以透過 setjmp/longjmp 完成，使用這兩個函式完成的是流程的控制。

• 而接下來的搶佔式多工，我們會接收 SIGALRM signal 來判別任務需進行切換。這些都是使用者空間進行任務切換的方法，Linux 核心的排程器還會處理到行程間的切換。最後是事件驅動，在 NGINX 當中事件驅動會由執行緒池指派的執行緒完成任務並回傳給行程，因此得知事件驅動有助於解決例行任務以及任務間的護衛效應。

---

你所不知道的 C 語言：函式呼叫篇

• 首先這章提到了程式中的函式有別於數學中的函數，因為函數是一種一(多)對一的對應關係，而函式卻有多對多的可能，因此兩者應視為不同。接著講到了 function prototype，在早期這項宣告並未被採納，因此容易造成編譯時期的缺陷，例如主程式中呼叫函式卻給定錯誤的引數數量或形態，由於沒有在主函式前進行 function prototype ，因此編譯器無法判斷這個引數是否妥當。有了 function prototype 編譯器也得以做到更多最佳化。接著也提到了參數以及引數的差異，以及 argc/argv 分別代表引數計數以及引數陣列。

• 接著會分析 ELF 目的檔在虛擬記憶體當中以及在實體記憶體當中的面貌，以及 C 語言程式觀察資料分布。在虛擬記憶體當中，此時由 ELF 產生的 Process image 共可分成四個區塊，首先是核心的資料以及程式碼，這個區塊在經由記憶體管理單元映射後會對應到實體記憶體較低的位址，也就是核心所在的區段，其他 Process image 與核心相關的片段也會映射至此。再來是動態鏈結函式庫的區塊，這裡通常只會紀錄使用到的檔案以及函式名稱，之後會由動態鏈結器將相關函式庫的程式片段產生 image 放置實體記憶體當中。最後是執行區域，這是由原本 ELF 檔的所有 section 組成，也是可以實際對應到原始程式碼行為的區塊，可以對應到以 C 來說的程式碼指令、全域變數、靜態變數。

• 最後我們觀察到函式的回傳值，編譯結果皆是直接放在暫存器當中，以 x86 指令架構來說若回傳只有一個整數值，則直接儲存於 %eax 32位元暫存器，若是回傳兩個或四個整數(??)，則會動用到數個64位元暫存器如 %rax , %rdx ，而回傳值使用暫存器

---

你所不知道的 C 語言：遞迴呼叫篇

• 在本章開頭提到了 「遞迴（recurse）只應天上有，凡人該當用迴圈（iterate）」 ，這裡點出的是遞迴會比迴圈更消耗電腦資源，但是在接下來的案例介紹會指出，遞迴可以透過編譯器最佳化來彌補效能缺失，並且遞迴在演算法領域可說是層出不窮並且是解決問題最有效的方法。

• 遞迴對初學階段的人較不友善的原因在於它不是生活中常見的思考邏輯，但是熟悉後可以將遞迴看成遞迴條件以及終止條件兩者，並且也可以呼應離散數學中的函數表達，以指數移動加權平均 EWMA 為例:

  $S_t=\{\begin{array}{ll}\alpha \cdot Y_t+(1-\alpha )\cdot S_{t-1},& \text{t > 0}\\ Y_0,& \text{t = 0}\end{array}$

  此時若

  $Y[0...t]$ 為已知的陣列以及
  $\alpha$ 為已知衰變率，並且我們要求時間點
  $t$ 的指數移動加權平均
  $S_t$ ，我們就可以透過遞迴的方式求出結果，其中
  $t>0$ 為遞迴條件，等於零時則是終止條件。

• 延伸指數移動加權平均的討論，我們會發現它是個尾部遞迴( Tail Recursion )，因此它的遞迴樹會是左(右)斜的形式，時間複雜度只與其呼叫次數有關，這與迴圈形式擁有相同的時間複雜度。但是我們必須考慮到遞迴會使用到堆疊來儲存程式狀態，因此效能實際上會較迴圈弱，但是時又並非如此，由於編譯器最佳化的採用，編譯器會判斷尾部遞迴所使用到的堆疊有許多不必要的資料，因此會將其最佳化到與迴圈擁有同樣的結果。

• 演算法中會運用到大量遞迴原因在於演算法經常出現的 分而治之法 (divide & conquer) 以及 動態規劃法 (dynamic programming) 皆需要運用到遞迴。本篇討論較多的是分而治之法，採用分治法最重要的是減少合併成本(以合併排序角度)，以時間角度觀察，在均勻分割的情況下若合併成本只有

  $O(n)$ ，則時間函數可以寫成
  $T(n)=2\cdot T(n/2)+O(n)$ ，進而得到時間函數等於
  $O(nlogn)$ ，這節主要說明有些演算法遞迴會是較為直觀的形式。

---

Linux 核心設計: 不只挑選任務的排程器

• 因為填寫這次的表單而仔細瀏覽了這個章節。首先提到排程器是一種將任務映射到處理器的函數，並且任務的數量時常遠大於處理器的數量，稱為 oversubscribed 。接著探討到了排程器的成本，而我們聚焦到了 context switch 所需的時間訂為排程器的時間成本，也執行了皆以 I/O 為主的行程來測量排程的時間成本。

• 接著探討了排程器的設計。包含 run queue 要設計成唯一讓行程排隊，又或是設計成多個以資源為主的 run queue 並且佇列空時會主動向其他佇列要求行程執行。還有考量行程要一次使用資源到執行結束又或是制定 time slice 限制每個行程的單次執行時間。也探討到了要用什麼排程演算法來決定行程執行順序以及時間。最後也是這章重視的主題就是佇列的實作要用何種資料結構，要重視 insert/delete/select 這幾個操作所需的時間。

• 在 Linux 2.6 之前，排程器的時間複雜度為

  $O(n)$ ，但以即時行程來說這樣的負擔太高，因此在經過諸多資料結構設計的考量後， Linux 2.6 的排程器時間複雜度來到了
  $O(1)$ ，他採用的是 bitmap + priority queue ，查詢 bitmap 以及 dequeue 接只需
  $O(1)$ 時間。

• 最後講到了 Rate Monotonic Scheduling (RMS) 及 Earliest Deadline First (EDF) 這兩項即時處理所採用的排程方法，其中 RMS 是依據任務的出現頻率來決定優先權，而 EDF 則是依據截止期的長短來決定優先權。這兩者皆會總和執行時間對週期的比值來評估是否所有任務皆可在截止期前完成。

---

你所不知道的C語言: 未定義/未指定行為篇

• 首先文章提到了何謂未定義行為，以及它與未指定行為的差別。首先未定義行為 (Undefined behavior, UB) 指的是程式行為並未在規範內(以 C 來說就是 ISO/IEC 9899 規範)。而未指定行為 (Unspecified behavior) 則是指會因為編譯器或是平台 ABI 而改變的程式行為。

• 而 C 語言之所以有 UB ，主要是依賴編譯器的最佳話來作消除，例如除以零或是有號數溢位等等行為就會再編譯階段遭到指令消除。但這也導致某些邏輯上會執行的程式碼，在最佳化開啟後遭到消除而不會執行。

• 常見的 UB 有被列點出來，包括有號數溢位、左(右)移 n 位元整數 n 個位元、除以零、參照 NULL 指標、讀取位初始化變數等等，執行這些原本有 UB 的程式，最佳化後的結果可能會不如預期。

---

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

閱讀心得

首先我認為作者值得稱讚的是，以工程務實的態度完成了這台自動飲料機，就算學校給予了這麼多理論以及實驗課，實際在實作時還是會遭遇許多未知並且需要花上許多心力以及時間來解決的問題，重點是之中有許多事情是學校未教授的，需要實際投入才會遇到的問題。就像是文章提及的 資工系不會寫程式 、 機械系不會機構設計 、 電工系不會焊接，更有趣的是這些同學解決問題的辦法都是來自於他們之前相關的實作經驗，並且也花上了他們許多心力。

作者與他的夥伴從最初的認為事情一蹴可及，到最後飲料機完成的領悟一切皆是巧思並且每個過程皆是關鍵，我認為這才是作者最大的成長。作者遇到的大問題包含最開始的自動放置飲料杯、茶湯的盛放、飲料冰塊的適量供給、飲料果糖的配置、放置設備的不銹鋼桌、網站架構的配置 等等問題，當然還有最重要的資金欠缺的問題，他們都嘗試以各自的專業以及向其他專家求助的方式解決問題，而這項堅持及實作精神是我認為他們這十四個月沒有白費的原因，當然還有在這之中獲得的經驗。

課程心得

而這篇文章回映到課程這六週的實作經驗，也就是在這堂課前六週的收穫以及感悟。首先真的有體悟到要有訓練才會得到收穫，因為有了第一週實作佇列的訓練，我才能在第三、四次作業完成井字遊戲融入到專案當中以及在不參考程式碼的情況下實作出 AVL Tree 並且能插入、搜尋、刪除、調整。以及第一週所學到的 Valgrind 也成功運用在 Timsort 的分析以及井字遊戲融入專案時的除錯。

再來還有第二次作業其實關連到排序、前中序建樹、快取記憶體 等資料結構以及計算機結構課程的概念，這些也是因為在準備研究所考試時就先打好基礎，所以才有辦法快速作答以及進行相關分析，相比第四次作業由於與離散數學中的數論極度相關而對這塊較不熟悉的我花了較久的時間及較多的心力來回答第四次作業的問題。或許能在第二次作業做出成果也要感謝之前的付出。再來第三次作業之所以在井字遊戲能有較快的發揮其實一部分原因是因為對於作業系統排程這章節的掌握，以及大學時親手用 Java 做出的作品四子棋與此遊戲相似，因此才有機會在兩週的時間趕出這項半成品，若對併行程式有更多理解，或許搶佔式的實作也可一併完成，可惜先前的培育併不夠我完成這項任務。

在觀察其他人作業時，也不難發現四年的培育真的對人影響極大，有電機系的學長修了第二次本課程，所以可以看到精簡有力的程式碼以及清楚的邏輯觀念，也有疑似第一次接觸到電腦科學領域的萌新。雖然投入就有機會得到回報，但從這次課程作業其實可以發覺到每個人的領悟能力各有不同，身邊真的有洞察力很好的同學可以找到程式碼的缺陷，有時候真的會羨慕這樣的表現，而不像我投入了大量時間還是覺得自己非常不足。

從這堂課其實可以明顯感受到老師對於我們素養的培育尤其看重，先從最基礎的程式能力訓練起，也會帶入我們本該知道的資料結構、演算法、離散數學、作業系統以及計算機組織的預備知識，還有對程式效能的重視以及精確的漢語表達。這些才是程式人員該具備的基礎能力，有了這些才有那麼點機會對 Linux 核心進行貢獻。

改進作業測驗題

第三週測驗_測驗五

• 改進內容: 在沒有分支的情況下，實作輸入值為零的例外處理。

第四週測驗_測驗二

• 改進內容: 將賽局判定機制引入井字遊戲，重點在於模運算的特化。

第四週測驗_測驗三

• 改進內容: 將 XTree 進行改進，引入 rbtree, AVL_tree 相關機制。

希望投入的專案

回顧 Linux 核心的 bitops 並尋求貢獻程式碼的機會

這項專案發現 Linux 核心的 include/asm-generic/bitops ，充滿了許多有機會改進的程式碼實作，首先作者提到 ffs 以及 __ffs 的結果會不同，但原因在於標頭檔說明 ffs 是從 1 起算，而後者則從零開始，源自於使用情境不同。作者還提到了 bitops 中的 ffs/fls 對輸入為零的例外處理方式不一，會因為使用者不同採用不同的處理方式。

作者所做的優化是將 ffs/fls 轉為他所實作的巨集，並且發現在 loop unrolling 後，不僅效能沒有改變，還能將前面例外處理以及實作不同的問題解決掉，統一了 bitops 中 ffs/fls 不一致的問題。

看到後來才發現作者似乎早就知道問題所在，也因此訂了這個主題，QQ。

vwifi 虛擬無線網路裝置驅動程式和實驗環境

整理 2022 年報告，解說 Linux 核心的 cfg80211 無線網路框架及 vwifi 運作原理，並善用 namespace 準備無線網路測試環境，預計完成以下:

• 比照 Testing a Linux Routing Daemon in a Simulated Environment，準備多個 SSID/STA 的網路測試環境，並改進現有 vwifi 的 CI 流程
• 研讀 vwifi 原始程式碼，並改進標註為 FIXME 的 TODO 的程式碼片段
• 撰寫 vwifi 運作原理的英文描述，日後可整合進 The Linux Kernel Module Programming Guide

以 eBPF 建構 TCP 伺服器

依據 ktcp 的指示，我們可在 sysprog21/khttpd 的程式碼基礎之上，打造出高效且穩定的網頁伺服器，不過 Linux 核心模組建構和維護的成本極高，本任務嘗試以 eBPF 來建構 TCP 伺服器。需要確保在 Linux v5.15+ 運作。

教材提問

1. 為什麼不使用區間變數而使用動態配置，區間變數紀錄的指標數值依舊可以回傳且代表合併後的串列第一個節點位址。（教材來源： 你所不知道的 C 語言: linked list 和非連續記憶體）