依據 fibdrv 作業規範,繼續投入 Linux 核心模組和相關程式的開發。
假設成年兔子為 a
,幼年兔子為 b
,且兔子不死亡
一般遞迴
矩陣運算 Q-matrix
又可改寫成
Fast Doubling
其中
最後得到
作業說明中的虛擬碼
這裡 Fast Doubling 利用 比 兩倍小的 來算出 ,遞迴的深度則被限制在 內,這可以大幅減少重複的計算
參考:Calculating Fibonacci Numbers by Fast Doubling
n 小於 2,直接回傳,不會經過迴圈
從 n 的 MSB 開始,依序計算該數的費氏數,直到 n 的 LSB 或剩下之 bit 皆為 0,則提前跳出迴圈
先用 h
記錄實際的數字共有幾個 bit (不含 leading 0s),接著從 MSB 開始計算首項費氏數,再藉由迴圈依次增加 n >> j
的 bit 數,以計算後續的費氏數
複雜度分析
解釋 fast doubling 為什麼用 2k 跟 2k + 1
例如:長度為 n 個 bit 的數字 與 長度為 n+1 個 bit 的數字 具有以下關係:
剛好就是 binary number 的進位規則
使用 __builtin_clzll
function 做硬體上的計算加速
clz
(Count Leading Zero) 可以計算數字 n
前面有幾個 0,加速取得 h
的速度
Linux kernel 不支援 VLA,因此使用 Dynamic Programming 與空間重複利用的技巧,避免動態陣列的使用,同時將 space complexity 從 降到
Linux 核心限制使用 VLA 的因素
在 The Linux Kernel is now VLA-Free 有提到 Linux kernel 不再允許 VLA 的使用C99 具有 VLA (Variable-Length Array) 的特性,允許執行時期再決定陣列佔用的空間大小,但可能會造成 stack overflow 等安全疑慮
根據教材 你所不知道的 C 語言:函式呼叫篇,攻擊者可以利用 stack-based-buffer-overflow 來執行惡意程式碼,從而對系統造成威脅此外,Linus Torvalds 也說過:USING VLA'S IS ACTIVELY STUPID! It generates much more code, and much slower code (and more fragile code), than just using a fixed key size would have done.』
在 Linux 核心中具有兩種計時方式
jiffies 是 Linux kernel 較早期存在的計時方法,使用作業系統從開機以來的計時器中斷發生的次數作為計時的依據,此全域變數稱作 ticks
數。計時器中斷為週期性的中斷事件,以固定的時間間隔觸發,利用間隔固定的特性便能達到測量時間的目的。
通常情況下,jiffies 的精度為毫秒級別,具體的精度取決於 tick rate 的大小。例如 1000Hz 表示每秒觸發 1000 次的 timer interrupt,因此 jiffies 的增加速度為每毫秒一次。
jiffies 轉換為秒的公式為
由以上程式碼可知,假如系統原先設定的 tick rate (HZ)
不大於 ,其時間精度是無法達到 ns 等級的。
hrtimer 是在 2.6.16 開始有的新的計時機制,裡面使用了 ktime_t
這個資料結構來進行計時。書中提到,原本基於 jiffies
的計時機制 timer wheel
在許多層面上有許多缺失,並幾乎無法再優化/整合了,包括:
- The forced handling of low-resolution and high-resolution timers in the same way leads to a lot of compromises, macro magic and #ifdef mess.
- The unpredictable [O(N)] overhead of cascading leads to delays which necessitate a more complex handling of high resolution timers, which in turn decreases robustness.
- The timer wheel data structure is too rigid for high-res timers.
因此實作 hrtimer
的設計考量包括
ktime_t 結構體定義如下
其結構體內有一型態為 64 位元的有號整數 tv64
跟據 Linux 原始碼 include/linux/ktime.h, ktime_t
的單位為奈秒 (ns)
透過呼叫 Linux kernel API ktime_get()
,可以取得相對於系統啟動時間的偏移量,因此藉由計算出兩次 ktime_get()
的時間差異,便可知其之間的程式碼執行時間花費
在 read 的時候,計算 fib,並同時將所花時間儲存在 kt
中
接著 write 的時候,將 kt
的值轉換成 nanoseconds 再回傳給 client
client
中順序呼叫 read
和 write
,即可取得所花費的 kernel time
執行 sudo ./client
後,成功輸出計算費氏數時間,輸出如下
參考 yanjiew1 的做法,利用
fib_read
傳入size
作為使用不同演算法的條件
使用 gnuplot 製圖,確認 fast doubling 確實加速費氏數的計算,同時發現 __builtin_clzll
大幅降低時間開銷
NOTE: 此處時間為 kernel mode 中計算的時間,還未加入 user space 的時間開銷比較
使用 taskset
預留 cpu 給效能測試使用
$ sudo vim /etc/default/grub
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=5"
$ sudo update-grub
$ sudo init 6
將作業說明提到的方法寫成一個 script,包括:
最後使用 taskset -c 5 ./client
指定 client 使用 cpu 5 進行費氏數計算
參考 時間測量與效能分析
計算 50 次費氏數的平均,並將離散值做處理,用以得到較平滑的效能比較圖
去除的 outlier 以超過兩個標準差為條件,移除離 50 次平均值太遠的數據
以常態分佈曲線來看,當我們排除兩個標準以外的數據後,代表此統計手法是在 95% 之信賴區間內取樣平均
閱讀 fibdrv 作業規範,包含「作業說明錄影」和「Code Review 錄影」,本著「誠實面對自己」的心態,在本頁紀錄所有的疑惑,並與授課教師預約討論。
過程中,彙整 Homework3 學員的成果,挑選至少三份開發紀錄,提出值得借鏡之處,並重現相關實驗。
Todo: 嘗試使用
mlock
改善 page fault 的情況
2020 - KYG-yaya573142
Todo: 嘗試使用sysfs
willwillhi1
回答「自我檢查清單」的所有問題,需要附上對應的參考資料和必要的程式碼,以第一手材料 (包含自己設計的實驗) 為佳
fibdrv.c
存在著 DEFINE_MUTEX
, mutex_trylock
, mutex_init
, mutex_unlock
, mutex_destroy
等字樣,什麼場景中會需要呢?撰寫多執行緒的 userspace 程式來測試,觀察 Linux 核心模組若沒用到 mutex,到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。 搭配閱讀〈並行和多執行緒程式設計〉fibdrv 中的 mutex 使用在 open
和 release
的部份,也就是一次只允許一個 thread 能夠存取 character device
現在嘗試將 mutex lock 移除
撰寫簡單的 POSIX thread 程式來測試
例如:thread-1
和 thread-2
都同時打開 fibdrc device,讀取 fib(0) ~ fib(49),並且為了使用延遲讓兩個 thread 交替執行,營造 race condition 的情況
這邊可以看到前幾項發生錯誤了,thread-2 讀取 fib(2) 的值為 2,說明在 thread-2 設定好的 offest 並將要透過 read() 進入 kernel space 讀取之前,file offset 被 thread-1 更動過了,造成錯誤結果
因此我們需要在 device 被 open() 時將 mutex 上鎖,而 release() 時將 mutex 解鎖,保持同時只有一個 thread 能夠控制 device driver
理解其中的技巧並導入到 fibdrv 中,並留意以下:
commit 4105efe
Todo: 分析細部的程式實作方法,並思考能否加速
參考 bakudr18
CASE 1:
CASE 2:
修改 verify.py
使 python 腳本可透過參數更動測試的項數大小
修改 client.c
在編譯 client 時添加 -D
flag 用作條件編譯
執行
得到輸出
確認在 以前其演算法的正確性
因為要測量運算完成後,把資料從核心搬到使用者模式,及使用者模式收到資料的時間。故在使用者模式取得到時間要能跟核心模式進行對應。
在使用者模式可以用 clock_gettime
函式來取得時間,其中又有不同的 clock id 。跟據 Linux 核心 ktime API 文件,在 Linux 核心內,以 ktime_get
函式所取得的時間可以對應到 CLOCK_MONOTONIC
的時間。
從 clock_gettime
取得的時間結構定義如上,我們可以簡單的將 tv_sec
* 來換算成與 ktime 對應的 nanoseconds
通過 user time - kernel time 可以得出 copy_to_user
system call 的花費時間
依據 Hierarchical performance measurement and modeling of the Linux file system 研究指出,從核心模式複製資料到使用者層級的時間成本是,每個位元組達 22ns。也就是當數字越大,需傳遞的字串越長,時間花費就越多
如圖所示,隨著 n 增加,system call 開銷明顯可見地大幅增加
當把 n 設到 500 時程式執行的效率越來越差
有產生階梯圖的狀況,每次階梯的產生剛好發生在 的數值超過一個
uint64_t
可表示的大小時,與 paul90317 同學遇到相似的結果,但原因可能有待釐清
在作業三說明中,老師有給出三種提升效能的方法
針對第一種降低資料傳遞量的做法,可以將 bn
結構體先回傳到 user space,再去做 bn_to_str
的操作
Todo: 減少
bn_to_str()
迴圈和分支的使用情況
實驗證明,copy_to_user
複製 bn
結構體比複製字串還來的節省時間
system call overhead 維持在 1000 ns 左右,比複製字串的 2000 ns 好上許多
參照 Schönhage–Strassen algorithm,在上述大數運算的程式碼基礎之上,改進乘法運算,確保在大多數的案例均可加速,需要有對應的驗證機制。