2023 年暑期 Linux 核心課程第 1 次作業

作業須知

1. 繳交作業的學員在符合下述規範並獲得授課教師確認後，會收到《Concurrency Primer》和《Demystifying the Linux CPU Scheduler》這二本 尚未公開釋出 的電子書草稿
2. 繳交期限為 8 月 13 日，可優先作答下方測驗題
   $\alpha$ 到
   $\gamma$ 並及早填寫作答表單，至於測驗題
   $\delta$ 可在指定的 HackMD 建立後，再逐步改進和補充
   • 作答表單
   • 授課教師會斟酌批改學員提交的作業並藉由 HackMD 上互動，學員越早提交，效果越好
3. 所有程式碼都該符合 C99 或 C11 規範，可搭配 GNU extension
4. 作答儘量用簡短的程式碼，且二元運算子 (binary operator，如 + [加法], - [減法], * [乘法], ^, & [逐位元 AND] 等等) 和運算元 (operand) 之間用一個空白字元 (不多不少!) 區隔，如 (v >> c)、逗點 (,) 後應該有空白或換行符號，並避免非必要的小括號 (即 ( 和 ))，也該刪去 (trim) 起始/結尾的空白字元
   • 程式碼排版風格可見 .clang-format
5. 顧及批改的便利，本測驗採用 Google 表單自動比對參考答案，難免會有疏漏的答案組合 (特別是程式碼風格的落差)，請發訊息到授課教師的 Facebook 粉絲專頁告知和討論
6. 一旦上述表單提交後，會由授課教師以電子郵件聯繫 (來自 <[e-mail]>)，通知課程事宜和提供電子書

測驗

$\alpha$

搭配 Linux 核心原始程式碼巨集: container_of, Linux 核心的紅黑樹

考慮 S-Tree^{名稱沒特別意思，不用去Google搜尋} 是個嘗試兼具 AVL tree 和 red-black tree 部分特性的 binary search tree (BST) 實作，著重在快速的 insert/delete 操作且合理的 lookup 速度。

測試情境為:

1. 隨機插入 0 到 98 之間的數值到 S-Tree，操作 100 次
2. 自 S-Tree 移去 0 到 98 之間的隨機數，操作 100 次

參考輸出如下:

[ After insertions ]
0
4
7
9
10
12
13
14
15
16
17
18
20
21
22
24
26
27
29
34
35
36
38
40
42
43
44
46
48
50
51
54
55
56
57
58
64
66
67
69
70
74
76
77
78
79
80
81
84
85
87
91
92
94
95
97
98
Removing...
52  65  76  30  44  90  16  70  14  93  
80  12  93   6  67  70  48  32  40  89  
31  90  10  42  75  75  42   5  20  37  
80  72   1  57   2  45  47  16  17  61  
10  95  73   4   2  39  73  48  71  14  
39   3   5  47  45  78  21  85  81  42  
23  62  13  22  19  13  68  66  30  83  
26  38  77  97  43  79  37  15  26   7  
27  65   8  32  14  51   9  35  38  88  
75  59  51  87  82  68  98  51  33  27  

[ After removals ]
0
18
24
29
34
36
46
50
54
55
56
58
64
69
74
84
91
92
94

注意到以下特性:

1. 節點內含數值由小到大輸出
2. [ After removals ] 的輸出不包含 Removing 指定的數值
3. 程式碼執行時，不會觸發任何 assertion

原始程式碼可見 main.c (部分遮蔽)

作答規範:

• AAAA, BBBB, CCCC, DDDD, EEEE, FFFF, GGGG 均該包含 st_ 開頭的函式或巨集，且不包含 ; 字元
• 補完程式碼，使其運作符合預期
• 必須符合 .clang-format 規範的程式碼排版風格
• 以最精簡的形式撰寫

延伸問題:

1. 解釋上述程式碼運作原理
2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作
3. 設計效能評比程式，探討上述程式碼和 red-black tree 效能落差

---

測驗

$\beta$

搭配 你所不知道的 C 語言: bitwise 操作, 你所不知道的 C 語言：記憶體管理、對齊及硬體特性

以下程式碼可針對給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址:

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return MMMM;       
    }
    return (((sz + mask) / alignment) * alignment);
}

已知 alignment 不為 0，參考執行輸出:

align_up(120, 4) = 120
align_up(121, 4) = 124
align_up(122, 4) = 124
align_up(123, 4) = 124

請填補上述 MMMM 標注的程式碼，使得執行結果符合預期。限制只能用 +, -, |, &, ^, ~, <<, >> 等運算子，不得出現 ternary conditional operator (即 ? 搭配 :)，且不該出現 alignment

必須符合 .clang-format 規範的程式碼排版風格

延伸問題:

1. 說明上述程式碼的運作原理
2. 在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法

---

測驗

$\gamma$

搭配 並行和多執行緒程式設計

考慮用 POSIX Thread 改寫的 qsort(3p) 實作，測試程式用法:

usage: qsort-mt [-stv] [-f forkelements] [-h threads] [-n elements]
	-l	Run the libc version of qsort
	-s	Test with 20-byte strings, instead of integers
	-t	Print timing results
	-v	Verify the integer results
Defaults are 1e7 elements, 2 threads, 100 fork elements

選項 -l 可指定使用 glibc (或系統預設的 libc) 的 qsort。原始程式碼可見 qsort-mt.c (部分遮蔽)
編譯方式:

$ gcc -Wall -o qsort qsort_mt.c -lpthread

請補完程式碼，使其運作符合預期。作答規範:

• HHHH 和 JJJJ 都包含 pthread_ 開頭的函式，且均不包含 ; 字元
• 以最精簡的形式撰寫
• 必須符合 .clang-format 規範的程式碼排版風格

延伸問題:

1. 解釋上述程式碼運作原理
2. 以 Thread Sanitizer 找出上述程式碼的 data race 並著手修正
3. 研讀 專題: lib/sort.c，提出上述程式碼效能改進之規劃並予以實作

---

測驗

$\delta$

回答上述測驗題

$\alpha$ 到

$\gamma$ 的所有延伸問題，建立 HackMD 頁面、設定權限為「已登入者可編輯」(這樣授課教師才能給予眉批)、用固定網址發布筆記 (建議命名為 linux2023-summer-quiz)，並依據下方格式來答覆延伸問題:

• 標題: linux2023: 你的 GitHub 帳號名稱
• 內文: 用 ## 開頭並標注題目，如 ## 測驗
  $\alpha -1$ 表示「測驗
  $\alpha$」的第一個延伸問題

書寫規範:

• 參照〈資訊科技詞彙翻譯〉及〈詞彙對照表〉，使用精準且符合台灣風格的科技詞彙
• 無論標題和內文中，中文和英文字元之間要有空白字元或標點符號 (對排版和文字搜尋有利)
• 文字訊息請避免用圖片來表示，否則不好搜尋和分類，尊重視覺障礙者的閱讀權益

延伸閱讀:

• HackMD: 筆記權限設定
• HackMD: 用固定網址發布筆記