Try   HackMD

2024q1 Homework6 (integration)

contributed by <jychen0611 >

自我檢查清單

  • 研讀上述 Linux 效能分析的提示 描述,在自己的實體電腦運作 GNU/Linux,做好必要的設定和準備工作
    從中也該理解為何不希望在虛擬機器中進行實驗;
  • 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+),解釋 insmod 後,Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關),以及藉由 strace 追蹤 Linux 核心的掛載,涉及哪些些系統呼叫和子系統?
    Linux 核心模組運作原理〉列出的程式碼較舊,歡迎編輯頁面,更新到 Linux v6.1 以上。
  • 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式,並探討能否改寫為 lock-free;
    參照 2021 年的筆記。歡迎貢獻 LKMPG!
    搭配閱讀〈並行和多執行緒程式設計
  • 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數,並提供對應的數學證明;
  • 研讀 CMWQ (Concurrency Managed Workqueue) 文件,對照 simrupt 專案的執行表現,留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU,Linux 核心如何做到?CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動?
  • 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文),並利用 ksort 提供的 xoro 核心模組,比較 Linux 核心內建的 /dev/random/dev/urandom 的速度,說明 xoroshiro128+ 是否有速度的優勢?其弱點又是什麼?
    搭配閱讀: 不亂的「亂數」
  • 解釋 ksort 如何運用 CMWQ 達到並行的排序;

整合井字遊戲對弈

  • 在 GitHub 上 fork simrupt,目標是整合第三次作業提及的人工智慧程式碼,主體應在 Linux 核心內運作,讓二個不同的井字遊戲人工智慧演算法執行在「不同的 CPU」(善用 CMWQ) 並模擬二者的對弈,並允許使用者層級的程式藉由開啟 /dev/simrupt (可適度更名) 來設定二個人工智慧程式的對弈並存取彼此的棋步
    * 務必在 Linux 核心模組中使用定點數
    * 其一演算法必是 MCTS,另一者可參照第三次作業jserv/ttt 專案近期整合的 ELO rating system
    * 查閱 CMWQ 的文件,指定前述不同的人工智慧演算法固定在不同的 CPU (如 CPU #0CPU #1),應該要能從使用者層級指定對弈的起始、暫停、恢復,和瀏覽狀態,Linux 核心模組和使用者層級的程式藉由 /dev/simrupt (可適度更名) 裝置檔案互動,注意需要擴充 VFS 註冊的檔案操作
    * 模擬對弈過程,前述二個人工智慧演算法程式碼在執行時間,應適度停頓 (數百個 millisecond)
    * 使用者層級的程式應能清楚繪製出 Linux 核心模組的對弈過程,在終端機展現 (你也可改用 SDL 一類的圖形函式庫繪製)