contributed by < lorian0738
>
fibdrv.c
存在著 DEFINE_MUTEX
, mutex_trylock
, mutex_init
, mutex_unlock
, mutex_destroy
等字樣,什麼場景中會需要呢?撰寫多執行緒的 userspace 程式來測試,觀察 Linux 核心模組若沒用到 mutex,到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。 搭配閱讀〈並行和多執行緒程式設計〉檢查 Linux 核心版本
輸出:
安裝 linux-headers 套件
輸出:
確認 linux-headers 套件已正確安裝於開發環境
$ dpkg -L linux-headers-5.4.0-66-generic | grep "/lib/modules"
輸出:
檢驗目前的使用者身份
輸出:
預期為「不是 root 的使用者名稱」,例如 jserv (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。
由於測試過程需要用到 sudo,請一併查驗:
輸出:
預期輸出是 root
安裝後續會用得到的工具
取得原始程式碼
編譯並測試
注意:這個指令會先卸載再掛載再卸載,在額外執行時會發現沒有掛載到,故可以僅輸入 $ make 編譯就好
預期:
實際輸出:
=> 符合預期
觀察產生的 fibdrv.ko
預期可得以下輸出:
實際輸出:
好奇 vermagic 是什麼,但維基百科沒有,網站中提到:
因此可能是因為 kernel 配置不同而比預期輸出多了 modversions
觀察 fibdrv.ko 核心模組在 Linux 核心掛載後的行為
輸出:
輸出:
新建立的裝置檔案 /dev/fibonacci,注意到 236 這個數字,在你的電腦也許會有出入。試著對照 fibdrv.c,找尋彼此的關聯。
輸出:
預期輸出是 0.1(相同),這和 fibdrv.c 透過 MODULE_VERSION 所指定的版本號碼相同。
輸出:
輸出:
這兩道命令的輸出都是 0,意味著目前的 reference counting。
查看指定行程的處理器親和性 (PID = process ID)
輸入:
輸出:
十六進位的 ff 轉成二進位的格式會是 11111111,這 8 個 1 分別代表該行程可以在第 0 到第 7 個 CPU 核中執行,最低(LSB; 最右邊)的位元代表第 0 個 CPU 核
輸入:
輸出:
使用 isolcpus 這個 Linux 核心起始參數,讓特定的 CPU 核在開機時就被保留下來
設定的方式:
isolcpus=cpu_id
參數於是只有那些被 taskset 特別指定的行程可使用這些 CPU 核
選擇直接加在 GRUB 設定檔中,保留第 0 個 CPU 核:
首先編譯產生執行檔
接著利用 taskset 將執行檔綁定在特定 cpu
因為前面保留第 0 個 cpu:
其中 0x1 表示第 0 個 cpu
抑制 address space layout randomization (ASLR)
設定 scaling_governor 為 performance。準備以下 shell script,檔名為 performance.sh
首先以 sudo vi performance.sh
建立檔案並填入以下:
再執行
針對 Intel 處理器,關閉 turbo mode
it lets the CPU run at its base clock speed when handling light workloads, then jump to a higher clock speed for heavy workloads.
因此這會讓 CPU 至少一直以基本時脈速度運行,對效能測試會有影響
參考教材以新的資料結構 ktime_t
測量時間,如下:
改完後下 make check 指令會看到:
client.c 中,原本 write 的部份:
其中在 unistd.h
中可見
可知 write 的功能是將存在 BUF 的 N 個 bytes 傳給 FD,回傳寫入的字數
其中 BUF 的意思是 buffer
FD 根據維基百科,指的是 file descriptor:檔案描述子,為 Unix 或 Unix-like 作業系統常用的詞,是一個檔案或讀寫操作的行程唯一標識符 (process-unique identifier),例如 pipe 或 network socket,通常為非負整數,負數保留於沒有值或是錯誤。
這個函式也作為一個 cancellation point,問了 chatGPT:
看不懂為什麼很多字前面後面都要加上__,有待釐清…
還是不知道要怎麼做,因此參考了同學的想法,因為要做完計算 kt 的值才會是對的,因此先用 read
做計算,再 call wite
的函式才會對
read:
因此改成:
改完以後輸出:
但這樣改的話迴圈中 sz = read(fd, buf, 1);
的 sz 沒有用到,會 commit 不了,因為程式會認為它佔用空間卻沒有實質影響。可以直接寫在後面的迴圈就好,而計算時間後應該輸出成檔案再用 gnuplot 繪製。
根據教材 gnuplot 語法解說和示範 可知應該將想繪製的資料做成 txt 或 csv 檔再用附檔名為 gp 的檔案讀取繪圖
首先準備 csv 檔:(於 client.c 的檔案中)
w+ 表示為了讀出和寫入而打開檔案,在檔案已存在的前提下,會把原來的內容覆蓋掉; 如果檔案不存在就創建一個新的。(參考)
若開啟失敗則報錯
將 nth Fibonacci 和 Fast Doubling 寫入檔案的第一列作為標題
迴圈中首先計算 Fibonacci,算完後取得花費時間 time,再將該迴圈計算第 i 個費波那契數與取得的 time 逐列寫入檔案中
最後關閉檔案
寫 gp 檔
首先下指令:
會出現:
不知道 Terminal type 是什麼意思,搜尋後得知 gnuplot 無法識別有效的終端機,因此要輸入以下進行設定:
會輸出:
因為找不到 wxt, qt, x11, aqua 等可以直接看輸出圖形的形式,因此直接將圖片輸出另存成 png 檔
可以利用 help 取得更多資訊,例如:
輸出:
進行設定:
輸出:
接著直接寫腳本後續利用比較方便,輸入 vim gnuplot.gp
或直接用 VS code 創建檔案:
設定圖片標題、座標軸名稱、字體字形、輸出檔案名稱、以及要用來繪製圖形的行列
最後輸入以下繪圖:
終於得到圖片:
註:因為是寫完 Fast Doubling 才開始研究計算時間的方法,因此這邊輸出的圖行為 Fast Doubling 的時間,也尚未考慮其他影響時間的因素,因排版關係 Fast Doubling 的實作也在此部份後面(連結)
commit 時沒有先用 clang-format -i
確認格式,才注意到註解應該都要在 //
後空一格再寫、#include
的順序是有照字母排的,這樣確實比較好看
教材提到:進行效能分析時,要考慮到 copy_to_user 函式的時間開銷,特別留意到資料大小成長後造成的量測誤差
考慮到硬體加速 F(n) 的手法
clz / ctz 一類的指令
在 fibdrv.c 中 static long long fib_sequence(long long k)
計算 Fibonacci 的值:
而教材中提到 Fast Doubling 手法:
示範案例:
求解 :1010 = 10102
i | start | 4 | 3 | 2 | 1 | result |
---|---|---|---|---|---|---|
n | - | 1010 | 1010 | 1010 | 1010 | - |
F(m) | F(0) | F(0*2+1) | F(1*2) | F(2*2+1) | F(5*2) | F(10) |
a | 0 | 1 | 1 | 5 | 55 | 55 |
b | 1 | 1 | 2 | 8 | 89 | - |
可以更快速的計算,參考給的 sudo code 後改寫如下:
首先計算 k 的 leading zero bits 個數,左移 k 使 MSB 移至最高位(前面的 0 都可以略過計算)。
迴圈中先求出 F(2k) 和 F(2k+1) 的值分別紀錄在 t1 和 t2,確認現在是做到 2k 還是 2k+1,若最高位為0,則表示是 2k,回傳 t1;若最高位為 1,則表示是 2k+1,回傳 t2,紀錄 a 為 2k+1的值、b 為 F(2k+2) = F(2k) + F(2k+1),方便後續計算,最後將 k 左移一位,表示乘以 2。
但要將這段修改 commit 時卻得到訊息:
才想到因為 k 是有號數,移動有號數造成 SAR (arithmetic right-shift)算術右移;移動無號數是 SHR (logical right-shift) 邏輯位移。
而我原本想做的是邏輯右移,但在有號的情況下,做算數位移最高位元不會變,因此不能右移 63 個位元。
改成將 1 左移到 64位元的最高位元,與 k 做 & 運算,若非 0 則表示現在 k 的最高位為 1
上述方法使用硬體加速直接計算 leading zero bits,繪圖比較
原本想法是在程式中將已經做好的 csv 讀取後再與新獲得的時間重新做一個新的 csv 檔
經過同學友善提示之後,直接將沒有用 clz 計算的時間輸出成另一個檔名再用 Linux 的 paste 功能合併成一個檔案(合併在右邊),如下:
-d 表示更改兩個檔案資料之間的分隔,原本預設是 tab,這裡改成逗號
再來寫兩個想要合併的檔案,在 > 之後寫合併的檔名
然而這樣做出來的檔案會僅以逗號分隔,但是 csv 檔應該要用逗號加空白分隔,例如預期:
1, 1, 1
但會做出
1, 1,1
這會導致 gnuplot 在讀 csv 檔的時候讀不到第三欄
目前為了確認繪製正確先手動加入空白分隔,應該要找到更自動化的方法解決這個問題
目前解法 1:在做成要合併的 csv 前就加好空格
目前解法 2:放棄使用 csv 檔,改用 txt 檔也能畫圖
更改 gnuplot.gp
:
輸出圖形:
可看出運用 clz 的加速效果
但這張圖沒有綁定 cpu 再進行測定,透過上述綁定後再測:
可看出在某些情況下用 clz 會表現的比較好
但對於下面這張圖跑的時間整體比上面那張還久有點困惑,照理來說跑在獨立的 cpu 整體表現應該要比較好,與同學們討論後認為可能是因為這都只是跑一次的結果,應該要平均比較準確,且只跑 100 個有點少,速度原本就非常快,且還沒有做大數運算,可能要跑多一點再觀察
也輸出了與一開始作法的比較圖,比更改後的表現還好,應該要能跑更多之後再來測