contributed by < YiChianLin
>
linux-headers
套件linux-headers
套件以正確安裝於開發環境得到以下結果:
由安裝 Ubuntu Linux 登入帳號名稱: Lin
輸出結果為: root
產生結果:
fibdrv.ko
得到以下輸出結果:
fibdrv.ko
在 Linux 核心掛載後的行為先透過 insmod
將模組載入核心,才會在 /dev/fibonacci
產生檔案
* The Linux Kernel Module Programming Guide
* Linux 核心模組運作原理
MODULE_VERSION
所指定的版本號碼為 0.1
輸出結果為: 0.1
兩道命令輸出皆為 0
,意味著目前的 reference counting
crtl + shift + p
進入命令列/etc/default/grub
內的 GRUB_CMDLINE_LINUX_DEFAULT
參數因此在第 15 個核心是空閒可被使用的
do_measurement.sh
在專案中,方便在多次測試的時候省去許多指令,改寫自 KYG-yaya573142 中 do_measurement.sh
Linux kernel
中,原因是如果使用到 VLS
傳入的值若有宣告上的問題,在記憶體分配上就會產生錯誤,例如:VLA
終是可允許的宣告方式,在如果 k
在某些情況傳入的時候是 -1
的情況呢?,透過 (unsigned int)
的強制轉型下,就會在 kernel space
中宣告出一個 4294967295 的陣列長度,而型態又為 long long
(8 bytes)的形式,在記憶體的佔用上就會暴增,甚至可能造成系統的錯,所以要避免在 kernel space
的 VLA
宣告改變方式實作:
F(93)
時會產生 overflow
的現象以 F(10) 舉例來說:
十進制數字轉為二進制 : 1010 = 10102
可表示成:
k = 0 F(0) , F(1)
k = 1 F(1) , F(2) 1
k = 2 F(2) , F(3) 0
k = 3 F(5) , F(6) 1
k = 4 F(10) 0
每一階層對應到二進位的 1 或 0 有兩種計算的方式
k1
, k2
分別為每一階層的兩斐波那契數在迴圈宣告 i
時會發現 1U << 31
每次的計算會從第 32 位開始計算,所以面對有效位元少的數字,可透過 clz / ctz 去除掉不必要無效位元的計算
參考 gcc 文件
Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
透過此函式可找出二進位數字由左位至右到第一個 1 前佔有幾個 0 位元的數量
time.h
的 clock_gettime()
在第一個引數 CLOCK_MONOTONIC
為單調遞增時間,時間會穩定持續增加不會因系統時間改變而有變動,適合用於量測程式的執行效率
ktime_get
fibdrv.c
中加入 #include <ktime>
)可在 fibdrv.c
中改寫 fib_write
函式,可透過引數中的 size
作為切換算法的依據
其對應執行的程式:
client_plot.c
(擷取部份)使用 gnuplot
繪製三種方法的運行時間結果 (分別為 原始 iterative
、 fast doubling
、 使用 ctz
類函數)
n = 90
後的表現,在設定中若超過 n = 93
則值都會與 n = 92
相同),在 fast doubling
演算法的表現上所花的時間大幅減少ctz
類相關的函式卻慢於未使用的方法,還要思考此種狀況的原因client.c
加入 clock_gettime()
函數,計算運算過程中從 user space
將值傳入 kernel space
中所花的時間user space
的總花費時間扣除, kernel space
的計算時間可以獲得 system call
所耗費的時間kernel space
再由 ktime 的方式計算
iterative 在 user space
、 kernel space
、 user to kernel
的傳遞時間(在 user space
約花費 250 ~ 300 nanoseconds)
fast doubling 在 user space
、 kernel space
、 user to kernel
的傳遞時間(在 user space
約花費 230 ~ 250 nanoseconds)
在前幾個 F(n)
的計算中可以看到,所花的時間上都會異常的高
可透過 mlock 系列的系統呼叫,確保特定的 page 不會被 swap out
mlockall
將啟用行程的虛擬地址空間加鎖,以防止出現 page swapMCL_CURRENT
對所有已經使用的行程地址空間上鎖MCL_FUTURE
對所有將使用的行程地址空間上鎖在使用後狀況還未改善(待研究)
kernel space
計算所花的時間很短 (大概 20 - 30 nanoseconds),觀察淺藍色的時間分布線,可看出在 user space
要傳入到 kernel space
所花的時間佔了大部分iterative
方式隨著數值越大所花費的時間越大,在 fast doubling
方法下計算花費的時間比較平緩fibdrv.c
vmalloc
的方式再 kernel space
中配置記憶體,分別為 F(0), F(1),填入 '0'
與 '1'
還有結尾符 '\0'
k == 0
與 k == 1
的時候,分別對應回傳 '0'
與 '1'
strlen
)fib0
與 fib1
變數取代下一個數值進行下一輪的計算copy_to_user
把計算的結果賦值到從 user space
的 buf
變數kernel space
使用後的記憶體空間釋放使用的方法與在 user space 的 malloc 方式相似
strlen()
類似,在 kernel space
中不能使用標準函式庫'\0'
計算其字串長度kernel space
不能使用 malloc
等函式,使用到 vmalloc
的配置記憶體方式,申請一片連續的虛擬地址空間,但在實體的記憶體上不一定為連續vfree()
my_strlen()
找出 fib0
與 fib1
的字串長度作為走訪每個字元的依據與迴圈的停止條件vmalloc
新增儲存結果的變數,其空間大小為 128 (計算到 F(500) )需要 110 多位數fib0[--len1] = '1'
、 fib1[--len2] = '4'
, 透過 ASCII 的編碼方式可以透過 - 48
或 - '0'
( '0'
的 ASCII 編碼為 48 )的方式將字元的數字轉成整數的形式在進行相加
sum
變數為儲存相加後的未進的整數部份,可透過對 10 的模除獲得carry
變數透過 sum / 10
可得知有沒有進位,會用在下一次的加法考量中sum
模除結果再轉成字元形式填入 result
的倒數的位數中carry
進位的產生,則在 result
的下一位中多 1
的進位數值字元fib0
、 fib1
變數的值,由 tmp
指向 fib0
的舊資料, fib0
更新為 fib1
, fib1
更新為 result
(從有字串的地方開始)copy_to_user()
函式,將從 kernel space
的 result
傳送資料副本給 user space
的 buf
引數:
to
為要傳送資料 (user space)from
複製來源的資料地址 (kernel space)n
資料長度tmp
所指的位址,使用 vfree
釋放在 kernel space
的佔用記憶體空間,還有整個運算結束後,將 fib0
與 fib1
釋放num 為 unsigned long long
的指標陣列型態,主要用來存取數字的計算結果
size 為 unsigned int
陣列的數量,用於調整陣列的大小
初始化結構
現今的電腦中的 CPU 大部分為多核架構,在多核系統中使用處理器的親和性 (process affinity)讓行程(process)在特定的 CPU 核心中持續執行,不受作業系統排程的干擾。
將行程綁定在特定的 CPU 核心上有許多優點,例如一個 cache bound 的程式跟其他比較耗費 CPU 計算的程式一起執行時,將程式綁定在特定的 CPU 核心可減少 cache miss 的狀況。另外在兩個行程頻繁的藉由共享記憶體進行資料交換時,將兩個行程都綁定在同一個 NUMA 節點中也可增進執行效率。
使用指令
lscpu
可發現其中一項NUMA node(s): 1
也就是大部分的 CPU 的能力還不到使用不同 NUMA 的架構,稍微查了一下別人的電腦,使用到多核Intel(R) Xeon(R) CPU E5-2690
才有NUMA node(s): 2
想必 CPU 的效能要極高規格,或是多電腦系統組成才有機會使用到
查看指定行程的處理器親和性
輸出結果:
加上 -c
參數
輸出結果:
輸出結果:
不能使用 USER:root 的行程否則會產生錯誤(推測是一些背景程式,沒有相當的權限不能任意更動)
錯誤訊息:
輸入以下指令,完成 linux 設定
performance.sh
:之後再用 $ sudo sh performance.sh
執行
Type I
與 Type II
型,而建立的方式分別是在原生機器上的硬體做配置,另一種則是在原生機器中的作業系統建立Type II
在程式執行的過程中會受到原生機器的作業系統影響,效率通常會比較低Type I
直接使用到機器上的硬體資源,不受其他作業系統的影響,如: KVM (此次作業可允許的虛擬機器架構)And what are virtual CPUs? Well, in most platforms they are also a kind of special task and they want to run on some CPUs … therefore we need a scheduler for that! This is usually called the "double-scheduling" property of systems employing virtualization because, well, there literally are two schedulers: one — let us call it the host scheduler, or the hypervisor scheduler — that schedules the virtual CPUs on the host physical CPUs; and another one — let us call it the guest scheduler — that schedules the guest OS's tasks on the guest's virtual CPUs.
若假設兔子是長生不死的狀態,而每一個月都會繁衍出下一代兔子,新生的兔子生長過一個月後即可在繁衍出下一代,而兔子的數量即為斐波那契數
In the year 1202 Leonardo Pisano, sometimes referred to as Leonardo Fibonacci,
proposed a model of the growth of a rabbit population to be used as an exercise
in addition. The student is told that rabbits are immortal, rabbits mature at the
age of one month, and all pairs of fertile rabbits produce one pair of offspring each month.
所以根據這樣的規則可以產生, 像這樣的數列,因此這樣的關係式可定義數學方程式為:
對於 階 個數字,可表示為: and
將前 個數字相加,為 階斐波那契數,而常見的斐波那契數為 2 階的形式
參考至論文第 18 頁的數學推導
以數學歸納法(Mathematical Induction)證明以下關係式:
若 ,帶入式中可得:
又因 ,所以可化簡為:在 時成立
若 ,帶入式中可得:
又因 ,所以可化簡為:
再由 的結果 帶入可得:
因此也關係式也成立
若 與 成立,證明 :
將 式 相加可得:
移項整理:
根據斐波那契數定義可將相加項結合,因此得證:
得證後,當 與 時可得到:
所以在計算 時可利用上式化簡,分別用 ,可簡短計算的時間
參考至論文第 14 頁
最一開始的關係 、,先假設成年兔子有 a 隻,未成年兔子為 b 隻可得出關係:
而其中的 為 Q-matrix ,可得關係:
帶入 整理可得:
由上述 Q-Matrix 的結果將展開可得:
lsmod
的輸出結果有一欄名為 Used by
,這是 “each module’s use count and a list of referring modules”,但如何實作出來呢?模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢?
搭配閱讀 The Linux driver implementer’s API guide » Driver Basics