---
title: 2024 年 Linux 核心設計/實作課程作業 —— lab0 (F)
image: https://i.imgur.com/robmeiQ.png
description: 改寫自 CMU Introduction to Computer Systems 課程第一份作業，擴充 GNU/Linux 開發工具的使用並強化自動分析機制。
tags: linux2024
---

# M01: [lab0](https://hackmd.io/@sysprog/linux2024-lab0)

> 主講人: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2024 年系統軟體課程](https://www.facebook.com/groups/system.software2024/)
:mega: 返回「[Linux 核心設計/實作](https://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表

## :penguin: 作業要求

* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
* :warning: 在提交程式變更前，務必詳閱 [如何寫好 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)，讓程式碼更精簡且有效
* 參閱「[2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review)」，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
* 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能
* 詳閱[改進 `lib/list_sort.c`](https://hackmd.io/@sysprog/Hy5hmaKBh)^含解說錄影^
* 確保 `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
* 除了修改程式，也要建立 HackMD 筆記，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2024-lab0-a), [(二)](/@sysprog/linux2024-lab0-b), [(三)](/@sysprog/linux2024-lab0-c), [(四)](/@sysprog/linux2024-lab0-d), [(五)](/@sysprog/linux2024-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/CSAPP-ch10)
* [HackMD](https://hackmd.io/) 筆記作為開發紀錄，規範如下:
* 標題格式固定為 ==2024q1 Homework1 (lab0)==，其中 "lab0" 是小寫，**2024q1** 表示「2024 年第 1 季」
* 共筆內容的第二行則為 **contributed by < `你的GitHub帳號名稱` >**
* 確保你的 GitHub 帳號是有效的
* 無論標題和內文中，**中文和英文字元之間要有空白字元** (對排版和文字搜尋有利)；文字訊息請避免用圖片來表示，否則不好搜尋和分類
* [共筆示範](https://hackmd.io/@sysprog/linux2022-sample-lab0) $\leftarrow$ 務必詳閱 [HackMD 教學](https://hackmd.io/s/quick-start-tw)
* 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
* 不要在筆記內加入 `[TOC]` : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
* 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，主要作為是評分和接受同儕的檢閱，不是彰顯「個人風格」的地方
* 當[在筆記中貼入程式碼](https://hackmd.io/c/tutorials-tw/%2Fs%2Fhow-to-use-code-blocks-tw)時，避免非必要的行號，也就是該手動將 `c=` 或 `cpp=` 變更為 `c` 或 `cpp`。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」裡頭程式碼展現的方式
* HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 `diff` 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
* 留意科技詞彙的使用，請參見「[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)」
* 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
* 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
* 撰寫的過程中，可善用 ChatGPT 一類的工具，但需要明確標示並指出裡頭謬誤和不精確之處。搭配 [ChatGPT cheatsheet](https://quickref.me/chatgpt)
* 填寫 [Google 表單](https://docs.google.com/forms/d/e/1FAIpQLScSXtolQ4jXIafsBEnQ8I0HScUHt-IkVC9tvI_W3zJbXPP4Ag/viewform)，提交程式碼和開發紀錄，當系統檢查完畢時，預期將在 :rocket: [作業區](https://hackmd.io/@sysprog/linux2024-homework1)見到登記的 HackMD 與 GitHub 超連結
* :warning: 不用等到作業完成才填寫表單，當你開始進行作業時，即可填寫表單，系統會進行必要的檢查工作。
* 本課程鼓勵學員相互觀摩，從而進行良性互動及批評，但要注意以下:
* 當你參照其他學員作業的材料時，應該指明出處並加上對應的超連結
* 善用 HackMD 的留言功能，在其他學員的筆記內文，留下你的想法、指出錯誤，和提及你對此的改進等等
* 截止日期：
* Mar 4, 2024 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高

## 作業觀摩
* [2023 年春季班](https://hackmd.io/@sysprog/linux2023-homework1)
* [2022 年春季班](https://hackmd.io/@sysprog/linux2022-homework1)
* [2021 年春季班](https://hackmd.io/@sysprog/linux2021-homework1)
* [2020 年秋季班](https://hackmd.io/@sysprog/2020-homework1)
* [2020 年春季班](https://hackmd.io/@sysprog/linux2020-homework1)