contributed by < hankTaro >
fibdrv.c
存在著 DEFINE_MUTEX
, mutex_trylock
, mutex_init
, mutex_unlock
, mutex_destroy
等字樣,什麼場景中會需要呢?撰寫多執行緒的 userspace 程式來測試,觀察 Linux 核心模組若沒用到 mutex,到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。 搭配閱讀〈並行和多執行緒程式設計〉使用 bn
結構體,將單一數值以 int
陣列儲存,並用 size
紀錄共需要幾個 int
空間作儲存,而 capacity 作為 memory pool 的空間上限,以進行動態記憶體管理(稍後會解釋)
e.g. 需要兩個 int
空間做儲存
由於是利用多個 32 bit 儲存資料,在定義與分配記憶體空間就十分關鍵,在執行初始化與算數運算時,都需要額外執行分配空間的工作,特別是在算數運算時,需要先將輸出的空間預備好,避免 overflow , 為了避免過於頻繁的呼叫 krealloc
造成時間的浪費,這裡預先引入 memory pool,當所需 size
小於 capacity
時,便不會重新分配空間,而是單純的將 size
改為所需空間
當 capacity = 4
size = 2
時,已知輸出所需空間為 3 ,故進行 bn_resize(src, 3)
,但 3 未超過 memory pool 上限,故單純將 src->size = 3
為了方便說明,往後將 number[0]
number[1]
這種已使用的區域,取名為 block
算數運算有以下幾個重點
c == a or c == b
的運算值得注意的地方是 40 行,利用 clz
快速取得左側 0 的數量,快速取得其 size,而非使用迴圈
至於乘法運算先使用最簡單的 block 兩兩相乘後相加至對應的位置,在第二階段加速運算部分在將其改進
有一個點要注意,因為乘法中的單一 block 需要反覆與其他 block 相乘,所以其相乘結果無法存入輸入位置,需要將回傳結果的輸入備份,再以備份進行相乘,避免輸入的值遭到更改而無法正確的相乘
由於本模組要掛載至核心中,所以在 fibdrv.c
中有自定義系統呼叫
在 fib_sequence
中先使用最簡單的方法求費式數列,將回傳值存入 dest
中,再將數值轉換成字串後,使用 fib_read
中的 __copy_to_user
將字串傳回到 user space
另外要注意 fibdrv.c
中 MAX_LENGTH
定義,需要修改其上限才可以求出 F(92) 以上的值,希望不要有其他人也因為這個問題被困擾好幾天
確認計算至 1000
為止的值都是正確的
設定的方式有兩種,一個是在開機時使用 boot loader 所提供的自訂開機參數功能,手動加入 isolcpus=cpu_id 參數,或是直接加在 GRUB 的設定檔中,這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核中執行,只有那些被 taskset 特別指定的行程可使用
- 用第一種方式:
如果想讓第 0 個與第 1 個 CPU 核都被保留下來,則在開機時加入:
- 第二種方式:
修改/etc/default/grub 內的 GRUB_CMDLINE_LINUX_DEFAULT
為GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7"
,
修改完成後需sudo update-grub
來更新設定,重開機後即生效
performance.sh
之後再用 $ sudo sh performance.sh
執行參考 do_measurement.sh 將以上設定包進一個 shell script 中
在 fib_read
與 fib_write
做修改,並將 fib_read
中的呼叫導向 fib_time_proxy
,一個用於測量不同作法所需時間的函式
使用此 Python script,計算某個 fibonacci number 的時間,並去除 95% 區間之外的值
並更改 MakeFile 中新增 plot 以方便輸出圖表
由於從核心模式複製資料到使用者層級是有時間成本的,每個位元組會花費 22ns,因此 CPU time 的計算需避免計算到 copy_to_user
的時間,而 Real time 需要計算從使用者呼叫到使用者收到資料的時間,包括 Wall clock time 和其他 process 使用的 time slice 和該 process 耗費在阻塞上的時間。
觀察計算 fibonacci 的時間會發現會有震盪的奇況 每過一段時間執行時間就會往上跳一小段 是因為 cache miss,若要排除這種 cache 對執行時間所造成的影響可以藉由降低 realloc 次數,因為 realloc 可能導致需要將原本的資料搬到更大的記憶體空間而新的空間並不是在原本的附近,造成原本 cache 裡的資料需要被更新。
可以先進入計算 fib 函式,算完後,因為 cache 裡的資料已被更新,再利用 ktime 開始計算時間,再算一次取 ktime
利用 shift 而非乘法