L04: fibdrv

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

返回「Linux 核心設計/實作」課程進度表

自我檢查清單

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
  $\to$ 搭配閱讀〈並行和多執行緒程式設計〉

作業要求

• 回答上述自我檢查清單的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳

  如果你在 2023 年 3 月 1 日前，已從 GitHub sysprog21/fibdrv 進行 fork，請依據 Alternatives to forking into the same account 一文，對舊的 repository 做對應處置，然後重新 fork

• 詳閱第 2 和第 3 週所有教材及作業描述 (一), (二), (三), (四), (五)，記錄你的啟發和疑惑
• 在 GitHub 上 fork fibdrv，目標是修正 Fibonacci 數計算並改善 fibdrv 核心模組的計算效率，過程中需要量化執行時間，可在 Linux 核心模組和使用者空間 (userspace) 中測量
  • 原本的程式碼只能列出到
    $Fibonacci(100)$ 而且部分輸出是錯誤的數值，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
  • 務必研讀上述 Linux 效能分析的提示 的描述，降低效能分析過程中的干擾;
  • 在 Linux 核心模組中，可用 ktime 系列的 API;
  • 在 userspace 可用 clock_gettime 相關 API;
  • 善用統計模型，除去極端數值，過程中應詳述你的手法
  • 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
  • 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 /dev/fibonacci 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
    
• 用 printk 固然方便，但其執行時間易受各種因素而不穩定，除了透過統計來觀察，也可改用核心的 sysfs 介面，後者可讓我們自行宣告 show 和 store 介面來提供讀寫操作，可參見 Sample kobject implementation (注意: 切換到對應的 Linux 核心版本)。
• 逐步縮減 Fibonacci 的執行時間，過程中要充分量化
• 嘗試研讀 sysprog21/bignum 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
• 當
  $Fib(n)$ 隨著
  $n$ 越來越大時，由 Linux 核心傳遞字串形式的十進位就成為效能瓶頸
  • 儘量降低由核心傳遞到應用程式的資料量
  • 確保應用程式不需要過多的計算量才可重現 Fibonacci 數列
  • BONUS: 研讀〈Integer Encoding Algorithm 筆記〉所提及的策略，在 Linux 核心模組先對數值進行編碼和壓縮，再由應用程式予以顯示
    $Fib(n)$ 數值

繳交方式

編輯 Homework3 作業區共筆，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

截止日期

Mar 21, 2023 (含) 之前
越早在 GitHub 上有動態、越早接受 code review，評分越高

作業觀摩

• 2022 年春季班
• 2021 年春季班
• 2020 年春季班