2024q1 Homework6 (integration)

contributed by < nosba0957 >

檢查清單

• 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

在 /linux/kernel/module/main.c 中的 load_module 函式中可以找到 simplfy_symbols 函式的呼叫，在 simplify_symbols 內看到 case SHN_UNDEF: 內呼叫 resolve_symbol_wait 再呼叫到 resolve_symbol。最後找到 find_symbol 函式，其中使用到 list_for_each_entry_rcu。再深入查看可以在 find_exported_symbol_in_section 找到 bsearch，在 include/linux/bsearch.h 可以看到 bsearch 的實作，也就是透過 binary search 找到 symbol。MODULE_LICENSE 的影響是若此核心模組宣告非為 GPL，則其無法使用透過 EXPORT_SYMBOL_GPL 的 symbol。從 strace 中看到的系統呼叫有，mmap，mprotect，fstat，fcntl等。

• 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;

在 simrupt.c 中有三個 mutex lock，read_lock, consumer_lock, producer_lock。在 simrupt_work_func 中呼叫 fast_buf_get 的時候使用到 consumer_lock，保護 fast_buf_get 中 ring->buf[tail] 和 ring->tail 的讀取。而 produce_lock 則是為了保護 produce_data 中，將值存入 rx_fifo 的操作。而 read_lock 是在 simrupt_read 中，也就是當這個核心模組被讀取時，用來保護 kfifo_to_user 這個函式執行。

排序的改進

Bottom-up heapsort / lib/sort.c

在 Bottem-up heapsort 第一步驟要先建立 heap，bottom-up-reheap 總共執行

$\lfloor \frac{n}{2}\rfloor$ 次，而 bottom-up-reheap 由三個函式組成。

bottom-up-reheap(m, i)
    j = leaf-search(m, i);
    j = bottom-up-search(i, j);
    interchange(i, j);

leaf-search

首先是 leaf-search。由於 heap 插入時會先將節點新增在 array 的最後方，所以 heap 必為 complete binary tree，除了最後一層沒有填滿以外，其他層都是填滿的。並且最後一層要先從左側插入。所以分析比較次數時先分析 perfect binary tree。此 binary tree 共有

$k$ 層(從第

$0$ 層 ~ 第

$k-1$ 層)。第

$0$ 層找到 special leaf 所需要的比較次數為

$k-1$ 次。第

$1$ 層需要

$k-2$ 次。而第

$0$ 層有 1 個節點，第

$1$ 層有

$2^1=2$ 個節點。而前面提到 bottom-up-reheap 會執行

$\lfloor \frac{n}{2}\rfloor$ 次，所以 leaf-search 會從 第

$\lfloor \frac{n}{2}\rfloor$ 個節點執行到第

$1$ 個節點。所以要總和所有比較次數

$$\begin{array}{rl}\sum _{i=0}^{k-2}{2}^i\times (k-1-i)& =2^0\times (k-1)+2^1\times (k-2)+...+2^{k-2}\times 1\\ & =(2^k-1)-k\\ & =n-\lceil lo{g}_2(n+1)\rceil \end{array}$$
接下來計算沒有填滿節點的最後一層。若該層只有 1 個節點，則對其親代節點的比較次數沒有影響。如左下圖，即使 special path 選擇到 2，也只有走到 4 這一個結果。若是有 2 個節點，如右下圖，則會讓 9 和 10 的親代節點多 1 次比較次數。

設第

$k$ 層有

$i$ 個節點，計算此

$i$ 個節點在 worst-case 會新增多少比較次數。此

$i$ 個節點的親代共

$\lceil \frac{i-1}{2}\rceil$ 個節點會受影響，再上一層(第

$k-2$ 層)有

$\lceil \frac{i-1}{2^2}\rceil$ 節點也會多 1 次比較次數。所以將受影響的節點次數相加

$$\sum _{j=1}^k\lceil \frac{i-1}{2^j}\rceil \le i-2+k$$
所以 worst-case 情況，比較次數為 perfect binary tree 的比較次數加上最後一層新增的

$i$ 個節點在 worst-case 情況的次數。

$$(2^k-1-k)+(i-2+k)=n-2$$
接下來是新增此

$i$ 個節點時，情況是 best-case 的比較次數。best-case 的情況是在根節點到最後一個節點的路徑上，路徑中的節點進行 leaf-search 時直接指向右節點，會少一次比較次數。這條路徑上共有

$\lceil lo{g}_{2}n\rceil -1$ 個節點。所以 best-case 的比較次數為

$$n-\lceil lo{g}_2(n+1)\rceil -\lceil lo{g}_{2}n\rceil +1$$
最後論文總結 best-case 和 worst-case 的比較次數相近。所以以

$n+\mathrm{\Theta }(logn)$ 表示。

buttom-up-search

分析 heapsort 和 bottom-up search 的比較次數。heapsort 每次 comparison 時，要先比較其底下的 2 個子節點，選出小的子節點(min-heap)後再將自己和那個子節點比，所以需要 2 次比較次數。

$b(1)...b(d)$ 用來描述 special path 路徑上的節點，總長度為

$d$ 且不包含 root。設

$x$ 為 root，此處的

$j$ 是我們要找到

$b(j)<x<b(j+1)$。

	$j=0$	$0<j<d$	$j=d$
heapsort	$2$	$2(j+1)$	$2d$
buttom-up search	$d$	$d-j+1$	$1$

用

$l_{HS}$ 表示 heapsort 比較次數的一半，

$l_{BUS}$ 表示 buttom-up search 的比較次數。因為 buttom-up reheap 會執行

$\lfloor \frac{n}{2}\rfloor$ 次， buttom-up search 也會執行

$\lfloor \frac{n}{2}\rfloor$ 次。所以目標是算出 buttom-up search 的比較次數。

$L_{HS},L_{BUS},D$ 這三個隨機變數，代表

$l_{HS},l_{BUS},d$ 的總和。所以現在目標是要計算

$E(L_{BUS})$。

	$l_{HS}+l_{BUS}$
$0<j<d$	$d+2$
$j=0orj=2$	$d+1$

為了計算

$E(L_{BUS})$，論文提供 heapsort 在 heap creation phase 的平均比較次數為

$({\alpha }_1+2{\alpha }_2-2)n+\mathrm{\Theta }(logn)$，平均 interchange 次數為

$({\alpha }_1+{\alpha }_2-2)n+\mathrm{\Theta }(logn)$。並且論文中推算出

$E(D),E(L_{HS})$。但我想不出

$E(D)$ 是如何計算的。

$$\begin{array}{rl}E(D)& =n+\mathrm{\Theta }(logn)\\ E(L_{HS})& =({\alpha }_1/2+{\alpha }_2-1)n+\mathrm{\Theta }(logn)\end{array}$$

接下來假設

$T$ 是呼叫 bottom-up search 時情況為

$j=0orj=d$ 的呼叫次數。而

$\lfloor \frac{n}{2}\rfloor -T$ 則為情況是

$0<j<d$ 的呼叫次數。

$$\begin{array}{rl}E(L_{BUS})& =E(T)\times (E(d)+1-E(l_{HS}))+(\lfloor \frac{n}{2}\rfloor -E(T))\times (E(d)+2-E(l_{HS}))\\ & =(3-\frac{{\alpha }_1}{2}-{\alpha }_2)n+E(T)+\mathrm{\Theta }(logn)\end{array}$$
接下來計算其中

$E(T)$，

$T$ 的情況為

$j=0orj=d$，所以分成兩部分討論。首先

$j=0$ 表示要執行到根節點。若某 subtree 有 r 個節點，則根節點的機率為

$\frac{1}{r}$。允許

$\mathrm{\Theta }(logn)$ 的誤差，從 perfect binary tree 的倒數第 2 層(第

$k-2$ 層)來看，約有

$\frac{n}{2^2}$ 個子樹，每個子樹有 3 個節點。再往上一層(第

$k-3$ 層)，約有

$\frac{n}{2^3}$ 個子樹，每個子樹有 7 個節點。所以可以推算當有

$\frac{n}{2^h}$ 個子樹，每個子樹會有

$2^h-1$ 個節點。所以根節點的機率為

$\frac{1}{2^h-1}$。計算

$E(T)$ 中

$j=0$ 的部分，

$\beta n+\mathrm{\Theta }(logn)$，其中

$$\beta =\sum _{h=2}^{\mathrm{\infty }}\frac{1}{2^h(2^h-1)}=0.1066952...$$

接下來計算

$E(T)$ 中

$j=d$ 的部分。在原版 heapsort 的 reheap 中，比較次數為

$c$，interchange 次數為

$i$，special object 的子代節點數量為

$s$。可以用算式

$c=2i+s$ 表示。interchange 的係數為 2 是因為 reheap 要先比較該節點的兩個子節點的數值大小，再比較該節點和其子節點中數值小的節點，才會進行 interchange。而 s 是因為

$j=d$ 的情況下，reheap 會一直往下直到葉節點，所以比較次數和 special path 的最後一組子代節點有關。接下來透過隨機變數

$C,I,S$ 代表

$c,i,s$ 的總和。而

$E(C),E(I)$ 在前面論文有直接提供。

$$\begin{array}{rl}E(S)& =E(C)-2E(I)\\ & =[({\alpha }_1+2{\alpha }_2-2)n+\mathrm{\Theta }(logn)]-2[({\alpha }_1+{\alpha }_2-2)n+\mathrm{\Theta }(logn)]\\ & =(-{\alpha }_1+2)n+\mathrm{\Theta }(logn)\end{array}$$

要計算

$E(T)$ 中

$j=d$，也就是要計算 special object 在葉節點的期望值。所以透過

$E(S)$ 來計算

$s=0$ 的期望值，也就是 special object 沒有子代節點的情況。

$s$ 有三種可能性，

$s\in \{0,1,2\}$。其中

$s=1$ 的情況如下圖，

$s=1$ 的情況表示 special object 為 5 號節點，且 reheap 的節點在

$1\to 2\to 5\to 10$ 的路徑上才會發生，共

$logn$ 次。當

$n$ 夠大時可以忽略。

所以計算

$s\in \{0,2\}$，而

$E(S)=\lfloor \frac{n}{2}\rfloor \times E(s)$。

$p_{s=0},p_{s=2}$ 為

$s=0$ 和

$s=2$ 的機率。

$$\begin{array}{rl}E(s)& =0\times p_{s=0}+2\times p_{s=2}\\ & =2\times p_{s=2}\\ \lfloor \frac{n}{2}\rfloor \times E(s)& =p_{s=2}\times \lfloor \frac{n}{2}\rfloor \times 2\\ E(S)& =p_{s=2}\times \lfloor \frac{n}{2}\rfloor \times 2\\ p_{s=2}& =\frac{E(S)}{\lfloor \frac{n}{2}\rfloor }\times \frac{1}{2}\\ & =2-{\alpha }_1+\mathrm{\Theta }(n^{-1}logn)\end{array}$$
而

$p_{s=0}$ 則為

$1-p_{s=2}$，所以

$p_{s=0}={\alpha }_1-1+\mathrm{\Theta }(n^{-1}logn)$。接下來可以計算

$E(T)$ 中

$j=d$ 的部分，也就是

$$\lfloor \frac{n}{2}\rfloor p_{s=0}=(\frac{{\alpha }_1}{2}-\frac{1}{2})n+\mathrm{\Theta }(logn)$$
總和

$j=0,j=d$，計算出

$E(T)=(\frac{{\alpha }_1}{2}-\frac{1}{2}+\beta )n+\mathrm{\Theta }(logn)$，再帶回計算

$E(L_{BUS})$

$$\begin{array}{rl}E(L_{BUS})& =(3-\frac{{\alpha }_1}{2}-{\alpha }_2)n+E(T)+\mathrm{\Theta }(logn)\\ & =(\frac{7}{2}-{\alpha }_1-{\alpha }_2+\beta )n+\mathrm{\Theta }(logn)\end{array}$$
所以可以總結出在 heap creation phase 的 buttom-up reheap 的比較次數為

$$\begin{array}{rl}n+\mathrm{\Theta }(logn)+E(L_{BUS})& =n+\mathrm{\Theta }(logn)+(\frac{7}{2}-{\alpha }_1-{\alpha }_2+\beta )n+\mathrm{\Theta }(logn)\\ & =(\frac{9}{2}-{\alpha }_1-{\alpha }_2+\beta )n+\mathrm{\Theta }(logn)\\ & \approx 1.649271n\end{array}$$

Selection phase