---
tag: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < [eddielin0926](https://github.com/eddielin0926) >
## :penguin: 作業要求
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [ ] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
* 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制
* 提示: 使用 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫
- [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
- [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作 (可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift))，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
* 參見: [由大數法則理解訊息熵 (entropy) 的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_)
* 參見: [The Linux Pseudorandom Number Generator Revisited](https://eprint.iacr.org/2012/251.pdf)
- [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。
* 注意：現有實作存在若干致命缺陷，請討論並提出解決方案
* 在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 percentile 的處理，但在 [lab0-c](https://github.com/sysprog21/lab0-c) 則無。
- [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2023-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2023-lab0-a), [(二)](/@sysprog/linux2023-lab0-b), [(三)](/@sysprog/linux2023-lab0-c), [(四)](/@sysprog/linux2023-lab0-d), [(五)](/@sysprog/linux2023-lab0-e)，記錄你的啟發和疑惑
* 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
- [ ] 截止日期：
* Feb 28, 2023 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高
## :gear: 開發環境
```shell
❯ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
❯ neofetch --off
eddie@eddie-laptop
------------------
OS: Ubuntu 20.04.5 LTS on Windows 10 x86_64
Kernel: 5.15.79.1-microsoft-standard-WSL2
Uptime: 11 hours, 4 mins
Packages: 1212 (dpkg), 8 (snap)
Shell: zsh 5.8
Theme: Adwaita [GTK3]
Icons: Adwaita [GTK3]
Terminal: /dev/pts/2
CPU: 11th Gen Intel i5-1135G7 (8) @ 2.419GHz
GPU: 6240:00:00.0 Microsoft Corporation Device 008e
Memory: 1455MiB / 7807MiB
```
## :pencil: 開發過程
### 修改 `queue.ch`
#### q_new
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
#### q_free
`list_for_each` 和 `list_for_each_safe` 的差別在於是否能在迭代的過程中進行刪除，透過額外的指標來記錄下一個節點的位置，讓迴圈能夠繼續進行。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, l) {
element_t *el = list_entry(node, element_t, list);
free(el->value);
list_del(node);
free(el);
}
free(l);
}
```
:::danger
避免張貼完整程式碼，開發紀錄著重於你的想法、遭遇到的問題，以及你如何持續改進程式碼。
:notes: jserv
> 已移除
:::
Sign in with Wallet
Connect another wallet