Try   HackMD

M01: lab0

主講人: jserv / 課程討論區: 2024 年系統軟體課程

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
返回「Linux 核心設計/實作」課程進度表

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
作業要求

  • 在 GitHub 上 fork lab0-c
  • 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
  • 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能
  • 確保 qtest 提供的 web 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 linenoise 套件就無法使用，請提出改善機制
    • 提示: 使用 select 系統呼叫
  • 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
  • 在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作 (可選定 Xorshift)，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
  • 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。
    • 注意：現有實作存在若干致命缺陷，請討論並提出解決方案
    • 在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。
  • 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
  • 除了修改程式，也要建立 HackMD 筆記，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
    • 詳閱第 1 週所有教材及作業描述 (一), (二), (三), (四), (五)，記錄你的啟發和疑惑
    • 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
    • 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
    • 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
  • HackMD 筆記作為開發紀錄，規範如下:
    • 標題格式固定為 2024q1 Homework1 (lab0)，其中 "lab0" 是小寫，2024q1 表示「2024 年第 1 季」
    • 共筆內容的第二行則為 contributed by < 你的GitHub帳號名稱 >
      • 確保你的 GitHub 帳號是有效的
    • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)；文字訊息請避免用圖片來表示，否則不好搜尋和分類
    • 共筆示範
      ←       務必詳閱 HackMD 教學
    • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
    • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
    • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，主要作為是評分和接受同儕的檢閱，不是彰顯「個人風格」的地方
    • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
    • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
    • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」
    • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
    • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
    • 撰寫的過程中，可善用 ChatGPT 一類的工具，但需要明確標示並指出裡頭謬誤和不精確之處。搭配 ChatGPT cheatsheet
  • 填寫 Google 表單，提交程式碼和開發紀錄，當系統檢查完畢時，預期將在
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    作業區見到登記的 HackMD 與 GitHub 超連結
    • Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More →
      不用等到作業完成才填寫表單，當你開始進行作業時，即可填寫表單，系統會進行必要的檢查工作。
  • 本課程鼓勵學員相互觀摩，從而進行良性互動及批評，但要注意以下:
    • 當你參照其他學員作業的材料時，應該指明出處並加上對應的超連結
    • 善用 HackMD 的留言功能，在其他學員的筆記內文，留下你的想法、指出錯誤，和提及你對此的改進等等
  • 截止日期：
    • Mar 4, 2024 (含) 之前
    • 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高

作業觀摩

Last changed by 
 
sysprog
System Software Programming
1
7929
Published on HackMD