目的: 檢驗學員對並行和多執行緒程式設計、Linux: 不只挑選任務的排程器,和 C 語言: bitwise 操作的認知
作答表單: 測驗 1-2 (針對 Linux 核心「設計」課程)
作答表單: 測驗 3-4 (針對 Linux 核心「實作」課程)
1
以下嘗試用 lab0 提及的 setjmp 和 longjmp,搭配〈你所不知道的 C 語言: goto 和流程控制篇〉闡述的 coroutine,開發簡易的排程器,以達到〈並行和多執行緒程式設計〉提及任務切換機制。在網路伺服器的應用場景,快速切換網路連線,以縮減服務的延遲。示意:
給定程式的參考執行輸出如下:
對照 FIBONACCI 網站列出的數值
程式碼列表如下: (部分遮蔽)
其中 task0
和 task1
分別計算 Fibonacci 數的偶數和奇數項,list.h
標頭檔來自 lab0-c。請補完程式碼,使程式碼運作符合預期。作答規範:
AAAA
, BBBB
, CCCC
均為表示式,三者應當包含 task
,
和 ;
延伸問題:
2
研讀 A (Bare-Bones) User-Level Thread Library 一文後,延伸測驗 1
,我們可利用 SIGALRM
signal 來實作搶佔式多工,下方的程式建立 3 個排序的任務,原理是藉由 SIGALRM signal 來模擬作業系統的 timer 中斷,設定的時間間隔為 10 ms,於是每 10 ms 觸發模擬的 timer 中斷,帶動排程器,實作 round-robin 排程策略。留意到 trampoline 的使用:
Trampolines (sometimes referred to as indirect jump vectors) are memory locations holding addresses pointing to interrupt service routines, I/O routines, etc. Execution jumps into the trampoline and then immediately jumps out, or bounces, hence the term trampoline.
預期程式執行輸出:
注意後 3 行的順序可能是 或 。程式碼可見 sched.c (部分屏蔽)
請補完程式碼,使其運作符合預期。作答規範:
DDDD
和 EEEE
為函式名稱FFFF
是表示式,應包含 >>
運算子,但不包含小括號 (即 (
和 )
)參考資訊:
trampoline function 的展現
延伸問題:
preempt_disable
, preempt_enable
, local_irq_save
, local_irq_restore
等等coro
的實作,探討其原理3
除法運算的成本往往高於加法和乘法,於是改進的策略被引入。其中一種策略是將除法改為乘法運算,例如 在分子和分母分別乘上 後,得到等價的 ,其中對 2 的 N 次方 (power of 2) 進行除法,在無號整數的操作就等同於右移 (shift) N 個位元,又當 (除數) 的數值是已知的狀況下,可預先計算,也就是說, 可轉換為乘法和位移操作,進而減少運算成本。不過,顯然 無法總是用整數來表達 (僅在 是 power of 2 的時候才可),因此,我們可先估算,並將差值補償回去。
重新檢視 ,當我們想將 除以 時,就相當於乘以 ,所以我們可將 改為 ,我們得到整數的部分 (即 ),和小數部分 (即 ),後者乘以 就是 ,也就是餘數。下方程式碼展示這概念:
其中 __uint128_t
是 GCC extension,用以表示 128 位元的無號數值。
模除 的數學推導如下:
其中 對應到 M
無條件捨去的除法運算再補一對應到「取上界」, 故
由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator,即 malloc 和 free 函式對應的實作),特別在多核多執行緒的環境有優異表現,在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧:已知 但是 k 要取多少才能滿足我們要的精確度呢? src/div.c 提供證明。
假設 為整數
證明
證明
成立的條件為
比較 jemalloc 的快速除法與通用除法運算
O0
到 O3
都做測試測試結果:
-O0
-O1
-O2
-O3
可發現 jemalloc 的除法運算較快。
fastdiv (部分程式碼遮蔽) 運用上述技巧,提出較通用除法快的實作。以下是測試程式碼:
請補完程式碼,使 assert
巨集不會在執行時期觸發錯誤並運作符合預期。作答規範:
AAAA
, BBBB
, CCCC
, DDDD
皆為整數(
和 )
),以最精簡的形式書寫延伸問題:
fastdiv
的效率,並試圖解釋其行為4
延伸第 5 週測驗題,我們想開發一套快速的 heap allocator,其記憶體開銷約為 1.67%,並比照第 5 週提到的 TLSF,嘗試建立時間複雜度為 的實作,注意只支援 32 位元的定址空間,亦即 GiB,內部採用 best-fit 演算法。
參考執行輸出:
其原始程式碼可見 heap.c (部分遮蔽)。請補完程式碼,使其運作符合預期。作答規範:
EEEE
, FFFF
皆為整數GGGG
為 hexadecimal literal