Linux 核心專題: fibdrv 改進

執行人: tintinjian12999

提問清單

• ?

任務簡述

擴充 fibdrv，強化其並行處理能力，預計達成:

• 有效運算 Fibonacci 數 (至少能算到第一百萬個) 並降低記憶體開銷
• 藉由 hashtable 或 cache 一類的機制，儲存已計算的 Fibonacci 數
• 引入 workqueue，將運算要求分派給個別 CPU 核，並確保降低非必要的同步處理成本
• 修訂 fibdrv 和應用程式之間的 API，使其適合用於同步處理

TODO: 儲存已計算的 Fibonacci 數

1. 考慮到大數運算的特性，當以 key-value 形式保存時，不是儲存單純的整數值，而是指向特定結構的指標，於是當 fibdrv 嘗試釋放佔用的記憶體空間時，應有對應的操作
2. 考慮到 fast doubling 和 Fibonacci 數的特性，不用保存連續數值，而是關注第 N 個和第 2N 個 Fibonacci 數的關聯，儘量降低記憶體開銷
3. 應當善用 Linux 核心的 hashtable 或相關的資料結構

引入 workqueue，確保並行處理的效益

1. 學習 ktcp，引入 kthread 和 CMWQ 到 fibdrv，確保 Fibonacci 數的運算可發揮硬體能力

〈Concurrency Managed Workqueue(cmwq)〉提到，cmwq 是 wq 的改進，專注以下目標

• Maintain compatibility with the original workqueue API
• Use per-CPU unified worker pools shared by all wq to provide flexible level of concurrency on demand without wasting a lot of resource.
• Automatically regulate worker pool and level of concurrency

2. 確保並行處理的效益，不僅要確認結果正確，還要讓並行的 fibdrv 得以更有效的運算
3. 思考如何運用 Linux 核心的 RCU (或其他 lock-free 機制) 有效釋放並行處理過程中的記憶體資源