---
tags: linux2023
---
# [2023 年暑期 Linux 核心課程](https://hackmd.io/@sysprog/linux2023-summer)第 1 次作業
:::warning
:warning: 作業須知
1. 繳交作業的學員在符合下述規範並獲得授課教師確認後，會收到《Concurrency Primer》和《Demystifying the Linux CPU Scheduler》這二本 **尚未公開釋出** 的電子書草稿
2. 繳交期限為 8 月 13 日，可優先作答下方測驗題 $\alpha$ 到 $\gamma$ 並及早填寫[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSchjBeTO5la96o1rMkUsYcTqPAAWdNqr1oHraqHkUiCHtraVw/viewform)，至於測驗題 $\delta$ 可在指定的 [HackMD](https://hackmd.io/) 建立後，再逐步改進和補充
* ==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSchjBeTO5la96o1rMkUsYcTqPAAWdNqr1oHraqHkUiCHtraVw/viewform)==
* 授課教師會斟酌批改學員提交的作業並藉由 HackMD 上互動，學員越早提交，效果越好
3. 所有程式碼都該符合 C99 或 C11 規範，可搭配 [GNU extension](https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html)
6. 作答儘量用簡短的程式碼，且二元運算子 (binary operator，如 `+` [加法], `-` [減法], `*` [乘法], `^`, `&` [逐位元 AND] 等等) 和運算元 (operand) 之間用一個空白字元 (不多不少!) 區隔，如 `(v >> c)`、逗點 (`,`) 後應該有空白或換行符號，並避免非必要的小括號 (即 `(` 和 `)`)，也該刪去 (trim) 起始/結尾的空白字元
* 程式碼排版風格可見 [.clang-format](https://github.com/sysprog21/concurrent-programs/blob/master/.clang-format)
7. 顧及批改的便利，本測驗採用 Google 表單自動比對參考答案，難免會有疏漏的答案組合 (特別是程式碼風格的落差)，請發訊息到[授課教師的 Facebook 粉絲專頁](https://www.facebook.com/JservFans)告知和討論
8. 一旦上述表單提交後，會由授課教師以電子郵件聯繫 (來自 `<embedded.master2015@gmail.com>`)，通知課程事宜和提供電子書
:::
### 測驗 $\alpha$
> 搭配 [Linux 核心原始程式碼巨集: `container_of`](https://hackmd.io/@sysprog/linux-macro-containerof), [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)
考慮 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](https://gist.github.com/jserv/4dfaf78cf516cc20f4bc55ce388c195d) (部分遮蔽)
作答規範:
* `AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE`, `FFFF`, `GGGG` 均該包含 `st_` 開頭的函式或巨集，且不包含 `;` 字元
* 補完程式碼，使其運作符合預期
* 必須符合 [.clang-format](https://github.com/sysprog21/concurrent-programs/blob/master/.clang-format) 規範的程式碼排版風格
* 以最精簡的形式撰寫
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作
3. 設計效能評比程式，探討上述程式碼和 red-black tree 效能落差
:::
---
### 測驗 $\beta$
> 搭配 [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise), [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
以下程式碼可針對給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址:
```c
#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`，參考執行輸出:
```cpp
align_up(120, 4) = 120
align_up(121, 4) = 124
align_up(122, 4) = 124
align_up(123, 4) = 124
```
請填補上述 `MMMM` 標注的程式碼，使得執行結果符合預期。限制只能用 `+`, `-`, `|`, `&`, `^`, `~`, `<<`, `>>` 等運算子，不得出現 [ternary conditional operator](https://en.wikipedia.org/wiki/%3F:) (即 `?` 搭配 `:`)，且不該出現 `alignment`
> 必須符合 [.clang-format](https://github.com/sysprog21/concurrent-programs/blob/master/.clang-format) 規範的程式碼排版風格
:::success
延伸問題:
1. 說明上述程式碼的運作原理
2. 在 Linux 核心原始程式碼找出類似 `align_up` 的程式碼，並舉例說明其用法
:::
---
### 測驗 $\gamma$
> 搭配 [並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)
考慮用 POSIX Thread 改寫的 [qsort(3p)](https://man7.org/linux/man-pages/man3/qsort.3p.html) 實作，測試程式用法:
```
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](https://gist.github.com/jserv/38bca4ebfea1c434e1dfc15337f80eeb) (部分遮蔽)
編譯方式:
```shell
$ gcc -Wall -o qsort qsort_mt.c -lpthread
```
請補完程式碼，使其運作符合預期。作答規範:
* `HHHH` 和 `JJJJ` 都包含 `pthread_` 開頭的函式，且均不包含 `;` 字元
* 以最精簡的形式撰寫
* 必須符合 [.clang-format](https://github.com/sysprog21/concurrent-programs/blob/master/.clang-format) 規範的程式碼排版風格
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 以 [Thread Sanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual) 找出上述程式碼的 data race 並著手修正
3. 研讀 [專題: lib/sort.c](https://hackmd.io/@sysprog/B146OVeHn)，提出上述程式碼效能改進之規劃並予以實作
:::
---
### 測驗 $\delta$
回答上述測驗題 $\alpha$ 到 $\gamma$ 的所有延伸問題，建立 [HackMD](https://hackmd.io/) 頁面、設定權限為「==已登入者可編輯==」(這樣授課教師才能給予眉批)、用固定網址發布筆記 (建議命名為 `linux2023-summer-quiz`)，並依據下方格式來答覆延伸問題:
* 標題: linux2023: **你的 GitHub 帳號名稱**
* 內文: 用 `## ` 開頭並標注題目，如 `## 測驗` $\alpha-1$ 表示「測驗 $\alpha$」的第一個延伸問題
書寫規範:
* 參照〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉及〈[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)〉，使用精準且符合台灣風格的科技詞彙
* 無論標題和內文中，中文和英文字元之間要有空白字元或標點符號 (對排版和文字搜尋有利)
* 文字訊息請避免用圖片來表示，否則不好搜尋和分類，尊重視覺障礙者的閱讀權益
延伸閱讀:
* [HackMD: 筆記權限設定](https://hackmd.io/s/how-to-set-permissions-tw)
* [HackMD: 用固定網址發布筆記](https://hackmd.io/s/how-to-share-note-tw)
Sign in with Wallet
Connect another wallet