2024q1 Homework2 (quiz1+2)

quiz1 測驗一

解釋程式碼的運作原理，提出改進方案並予以實作。
使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

運作原理

quick_sort

鏈結串列結構:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

L:指向被排序的鍵結串列第一個節點
R:指向被排序的鍵結串列最後一個節點
pivot :指向被排序的鍵結串列第一個節點

用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍

begin[i]:left 串列的第一個節點
end[i]:left 串列的最後一個節點
begin[i+1]: pivot 節點
end[i+1]: pivot 節點
begin[i+2]:right 串列的第一個節點
end[i+2]:right 串列的最後一個節點

1. 選擇 pivot
每次都選擇鏈結串列第一個節點作為 pivot

2. 分割鏈結串列
所有比 pivot 小的元素放在 L 串列，比pivot大的元素放在 R 串列

3. 由 begin[] 與 end[] 的範圍進行排序
每次都優先處理 R 串列去進行排序
直到 beg[i] == end[i] ，表示此串列中只有一個節點，就將該節點加入到 result 串列中。

以下方的鏈結串列為例:

p 依序走完鏈結串列，並分割鏈結串列，將所有比 pivot 小的元素放在 L 串列，比pivot大的元素放在 R 串列，如下圖:

更新 begin[] 與 end[] 的值，接著每次都優先處理 R 串列去進行排序，此時 beg[i] == end[i] ，表示 R 串列中只有一個節點，加入到 result 串列中第一個節點的位置

接著 i--，此時beg[i] == end[i] ，begin[i] 與 end[i] 的值放的是 pivot，將 pivot 節點加入到 result 串列中第一個節點的位置

接著 i--，開始處理 L 串列，進行排序直到整個串列排序完成。

改進方法

縮減 begin[]的大小

避免最差狀況的快速排序實作

平均情況:
快速排序的時間複雜度為

O (n l o g n)

最差情況:
快速排序的時間複雜度為

O (n^{2})

，當排列的元素已經按照升序或降序排列，導致每次分割都只能減少一個元素。

所以選擇 pivot 很重要，希望每次都能將串列平均分割，避免最差情況的發生，我的作法是隨機選擇 pivot。

Linux 核心風格的 List API

在 node_t 結構中新增 struct list_head list，因 Linux List API 中 list_head 的結構中已經有 prev 和 next ，因此可以把 node_t 結構中的 left、right、 next 指標移除，另外因避免快速排序最差情況的發生，需再新增一個隨機選取 pivot 的函式 rand_pivot()。

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

在 quick_sort()中不需要 end[]，因 linux list 是雙向鏈結串列，查找最後一個只需要使用 head->prev 即可找到串列最後一個節點。
在改寫 Linux 核心風格的 List API 時，發現在 list_add 時會發生 segamentation fault，進一步去檢查，發現在 quick_sort 中把 pivot 加入到 begin[i+1] 時發生錯誤，再重新審查一遍後發現是 begin[] 沒有去做 list_new()。

Linux 效能分析工具: Perf

效能測試上使用 perf 來分析選取 pivot 策略的差異，perf 是一個在 Linux 系统上用於性能分析的工具。perf stat 是一個用於監控和分析系統性能的命令。它的主要目的是執行指定的命令，並在命令執行期間保持對硬體和軟體事件發生的運行計數，並生成這些計數的統計信息。

硬體事件統計：CPU 迴圈數、快取命中率、指令執行次數等。
軟體事件統計：上下文切換次數、記憶體存取、I/O 處理時間等。

實驗分成最差情況和一般情況下隨機選取 pivot 和直接選取鏈結串列的第一個節點作為 pivot 的差異，因一般情況下指令數以及耗費時間預計會高於最差情況下，因在排序前會先打亂陣列資料，主要比較隨機 pivot 和直接選取第一個節點的平均執行時間，和觀察兩者之間的差異，特別是在不同大小的輸入資料上。

每次執行效能測試前須清除快取

$ echo 3 | sudo tee /proc/sys/vm/drop_caches

執行效能測試

$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./linux_qsort_no_rand_pivot 
$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./linux_qsort

重複執行 5 次該程序，並顯示每個 event 的變化區間。
觀察的 event 分別為快取的命中率、快取的存取、指令數和執行的 cycle 數。

worst case 的情況下(排序的順序為升序或降序)：

測試 100000 筆資料

  Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):

           17,1340      cache-misses                     #    7.08% of all cache refs           ( +- 19.31% )
          241,9193      cache-references                                                        ( +-  4.59% )
       3,2687,3138      instructions                     #    2.56  insn per cycle              ( +-  0.02% )
       1,2752,6925      cycles                                                                  ( +-  0.53% )

           0.03275 +- 0.00447 seconds time elapsed  ( +- 13.64% )

 Performance counter stats for './linux_qsort' (5 runs):

           17,5439      cache-misses                     #   15.18% of all cache refs           ( +- 19.82% )
          115,5482      cache-references                                                        ( +-  0.18% )
       3,6791,2078      instructions                     #    3.19  insn per cycle              ( +-  0.02% )
       1,1530,0504      cycles                                                                  ( +-  1.76% )

           0.02647 +- 0.00122 seconds time elapsed  ( +-  4.59% )

測試 1000 筆資料

Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):

              5820      cache-misses                     #   22.02% of all cache refs           ( +- 28.89% )
            2,6429      cache-references                                                        ( +-  4.96% )
         3900,0168      instructions                     #    4.22  insn per cycle              ( +-  0.02% )
          924,3143      cycles                                                                  ( +-  3.14% )

           0.00822 +- 0.00137 seconds time elapsed  ( +- 16.72% )

 Performance counter stats for './linux_qsort' (5 runs):

              4940      cache-misses                     #   23.56% of all cache refs           ( +- 40.92% )
            2,0971      cache-references                                                        ( +-  7.79% )
          380,2888      instructions                     #    2.31  insn per cycle              ( +-  0.09% )
          164,9545      cycles                                                                  ( +-  2.61% )

           0.00603 +- 0.00311 seconds time elapsed  ( +- 51.58% )

測試 10筆資料

 Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):

              3549      cache-misses                     #   17.13% of all cache refs           ( +- 41.67% )
            2,0712      cache-references                                                        ( +-  2.02% )
          103,6432      instructions                     #    1.23  insn per cycle              ( +-  0.37% )
           84,3458      cycles                                                                  ( +-  0.97% )

         0.0015844 +- 0.0000369 seconds time elapsed  ( +-  2.33% )

 Performance counter stats for './linux_qsort' (5 runs):

              4262      cache-misses                     #   19.76% of all cache refs           ( +- 40.00% )
            2,1571      cache-references                                                        ( +-  7.35% )
          104,3593      instructions                     #    1.25  insn per cycle              ( +-  0.41% )
           83,4795      cycles                                                                  ( +-  3.44% )

           0.00492 +- 0.00288 seconds time elapsed  ( +- 58.52% )

一般情況：

測試 100000 筆資料

 Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):

           18,6967      cache-misses                     #    7.09% of all cache refs           ( +- 14.72% )
          263,6204      cache-references                                                        ( +-  1.68% )
       3,2716,9090      instructions                     #    2.56  insn per cycle              ( +-  0.04% )
       1,2779,8557      cycles                                                                  ( +-  0.37% )

           0.03144 +- 0.00288 seconds time elapsed  ( +-  9.16% )

 Performance counter stats for './linux_qsort' (5 runs):

           13,1878      cache-misses                     #    2.92% of all cache refs           ( +- 31.84% )
          452,2847      cache-references                                                        ( +-  2.92% )
       3,7541,7692      instructions                     #    2.07  insn per cycle              ( +-  0.01% )
       1,8132,7720      cycles                                                                  ( +-  0.65% )

           0.04373 +- 0.00391 seconds time elapsed  ( +-  8.93% )

測試 1000 筆資料

 Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):

              5773      cache-misses                     #   26.58% of all cache refs           ( +- 30.05% )
            2,1721      cache-references                                                        ( +-  4.27% )
          360,6218      instructions                     #    2.15  insn per cycle              ( +-  0.06% )
          167,3905      cycles                                                                  ( +-  1.24% )

         0.0027962 +- 0.0000931 seconds time elapsed  ( +-  3.33% )

 Performance counter stats for './linux_qsort' (5 runs):

              4256      cache-misses                     #   18.23% of all cache refs           ( +- 42.39% )
            2,3345      cache-references                                                        ( +-  3.09% )
          392,6116      instructions                     #    2.10  insn per cycle              ( +-  0.04% )
          187,4003      cycles                                                                  ( +-  0.80% )

          0.003057 +- 0.000155 seconds time elapsed  ( +-  5.06% )

測試 10 筆資料

 Performance counter stats for './linux_qsort_no_rand_pivot' (5 runs):

              4312      cache-misses                     #   23.12% of all cache refs           ( +- 40.36% )
            1,8653      cache-references                                                        ( +-  5.29% )
          103,6244      instructions                     #    1.23  insn per cycle              ( +-  0.16% )
           84,0002      cycles                                                                  ( +-  3.29% )

         0.0012722 +- 0.0000279 seconds time elapsed  ( +-  2.19% )

 Performance counter stats for './linux_qsort' (5 runs):

              4039      cache-misses                     #   19.44% of all cache refs           ( +- 36.90% )
            2,0777      cache-references                                                        ( +-  2.39% )
          103,2732      instructions                     #    1.16  insn per cycle              ( +-  0.17% )
           88,8412      cycles                                                                  ( +-  3.26% )

          0.001064 +- 0.000126 seconds time elapsed  ( +- 11.84% )

最差情況

輸入資料大小	100000	1000	10
選取第一個節點作`pivot`	0.03275 s	0.00822 s	0.0015844 s
隨機選取節點作`pivot`	0.02647 s	0.00603 s	0.00492 s

一般情況

輸入資料大小	100000	1000	10
選取第一個節點作`pivot`	0.03144 s	0.0027962 s	0.0012722 s
隨機選取節點作`pivot`	0.04373 s	0.003057 s	0.001064 s

總結：

隨機 pivot 可以減少最壞情況下的執行時間，因為它避免了選擇最差的 pivot。
直接選取第一個節點的方法簡單，但在已排序情況下導致效能下降。
選擇 pivot 的方法和數據的特性（例如數據是否已經部分排序）可能會影響 quick_sort 的效率。因此，在使用 quick_sort 時，選擇合適的 pivot 選擇策略是很重要的。

quiz1 測驗二

解釋上述程式碼的運作原理，提出改進方案並予以實作。
將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。

運作原理

主要想法:
想要利用資料中已存在排序好的子序列來最小化比較和交換的次數。

Tim Peter發現在現實世界中，許多資料都是由部分排序好的序列組合而成。他提出的策略是先找出這些已排序的子序列（也就是所謂的run），然後透過不斷合併這些子序列來完成整個資料範圍的排序。儘管在處理隨機資料時，Timsort的效能稍遜於理論上的極限值

O (n l o g n)

，但對於部分已排序的資料，其表現卻相當出色。

Timsort的改進主要集中在三個方面：

加快合併過程。
減少合併的次數。
在某些情況下尋找比合併排序更有效的排序方法。

Timsort 使用一組堆疊 (stack) 來存儲run，這樣做是為了減少掃描整個資料範圍以產生run所需的記憶體開銷。在這個過程中，Timsort使用merge_collapse函式來確保堆疊上的run長度保持平衡。該函式主要檢查堆疊頂端的3個run是否滿足以下原則：

A的長度要大於B和C的長度總和。
B的長度要大於C的長度。

如果不符合這些條件，函式將決定是否進行合併。這樣做確保了堆疊中run的長度平衡，並且由於合併只能在相鄰的兩個run之間進行，以確保排序的穩定性，因此合併操作僅可能採取A和BC 以及 AB和C 兩種形式。這使得Timsort在執行時能夠兼顧高效和穩定性。

例如，考慮 3 段 run: A 的長度為 30，B 的長度為 20，C 的長度為 10，由於 A 的長度不大於 B 加 C 的總和（亦即

A <= B + C

），且 C 的長度小於 A，因此會選擇將 C 與 B 進行合併，形成兩個新的 run

A: 30
BC: 30

藉此，不僅確保堆疊中 run 的長度平衡，且因合併只能在相鄰的兩個 run 間進行，以確保排序的穩定性，因此合併操作僅可能採取

A + (B + C)

或

(A + B) + C

的形式進行。此舉讓 Timsort 在執行時兼顧高效又穩定。

處理相鄰子序列的合併過程中，直接在記憶體中進行操作會面臨挑戰，因為大量的記憶體操作不僅難以實作，效率也未必理想。因此，Timsort採用了使用臨時記憶區的策略，其大小設定為兩個子序列（A、B）中較短者的長度。

當A的長度小於B時，會先將A序列暫存。一種直觀的合併方法是從A和B的開頭開始進行逐對比較，將較小的元素放置於A的原位置，這一過程持續進行直到A和B完全排序，類似於經典的合併排序，也稱為逐對合併（one-pair-at-a-time）。

然而，考慮到A和B都是已排序的序列，可以進一步改進：首先尋找B的首個元素（即B[0]）在A中的排序位置，這樣就能確定A中有一段是小於B[0]的，可以將這部分元素放回A。接著，尋找剩餘A的首個元素在B中的位置，如此反覆進行，直到完成排序。這種方法被稱為Galloping mode。

例如，考慮以下情況：

A: [3, 5, 7, 9, 11]
B: [6, 8, 10, 12, 13, 17]

顯然A較短，因此先將A放入暫存記憶區temp。然後找到B[0]在A中的位置，即A[1]和A[2]之間，因為B[0]=6，所以A[0] 到 A[1] 都可以直接放回A序列。然後，將temp的首個元素放到B中適當的位置，如此反覆進行。

這種改進方案在大多數情況下效果顯著，但對於隨機資料序列而言，可能比逐對合併更慢。因此，在Timsort中有一個機制決定是否要啟動Galloping mode。

相對於合併排序，Timsort的改進包括：

降低快取失效（cache miss）
減少記憶體開銷
降低比較次數

傳統的合併排序會從合併樹的最底層開始合併，這導致每進行一層的合併就要掃過整個序列，這對快取不友好。Timsort優化了這一點，利用Galloping mode和臨時記憶區的策略，在適當時機進行合併，從而降低快取失效和記憶體開銷，同時減少比較次數，提高了效率。

Galloping mode

在Timsort中，當資料呈現非均勻分布且存在叢集(Clusters)特性時，會啟用Galloping演算法。初始時無法得知資料分布情況，但在使用傳統的「逐對比較」方式時，若連續進行多次比較都來自同一個Run，就會推測資料可能具有叢集特性，進而切換至Galloping模式。判斷是否切換的條件是有一個名為MIN_GALLOP的常數，默认值為7，即當進行了7次連續比較，且來自同一個Run時，就會啟動Galloping模式。一旦進入Galloping模式，如果從同一個Run找到的連續資料次數小於MIN_GALLOP，則會回到傳統的「逐對比較」模式。

Galloping Mode：

進入 Galloping 模式時，Timsort 需要不斷尋找某個數字在已排序陣列中的位置。
假設 A 是較短的序列，我們要找 A[0] 在 B 序列中應排序的位置。
傳統的二分查找是一種選擇，但 Timsort 使用了另一種演算法，稱為 Galloping Search（也稱為指數搜尋）。
Galloping Search 透過跳躍式地尋找，更快地確定 B[0] 在 A[0] 中的位置，從而將整個 A 的一部分移動到正確的位置。

1. 初始化堆疊大小
stk_size 被設置為 0，用來紀錄堆疊中的 run 數量

2. 建單向鏈表
如果 head == head->prev，那麼函數將返回。
否則，它將把雙向鏈表轉換為單向鏈表。

3.找到下一個 run 並合併
在一個循環中尋找下一個 run (find_run 函數來完成)，並在每次找到一個 run 時合併它 (merge_collaps 來合併)。

4. 強制合併所有 run
當所有的輸入都被處理後，將強制合併所有剩餘的 run (merge_force_collapse 來強制合併)。

5. 最終合併並重建鏈接
最終的合併(merge_final )，並重建雙向鏈表的鏈接(build_prev_link)。

quiz2 測驗一

解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

運作原理

建立一棵二元樹的，使用了前序(preorder)和中序(inorder)來建立這棵樹。
透過前序遍歷可以確定節點的上下關係（越前面的越在上面），而中序遍歷可以確定節點的左右關係（越前面的越在左邊）
利用前序遍歷的第一個元素來確定根節點的值，並在中序遍歷中找到該元素，將其左邊的元素視為左子樹，右邊的元素視為右子樹。

結構:

struct hlist_node {
    struct hlist_node *next, **pprev;
};
struct hlist_head {
    struct hlist_node *first;
};

這邊的 pprev 宣告為指標的指標
可以發現:

只有鏈結串列的尾端指標內容是 NULL。
next 指向相鄰的節點本身，而 pprev 指向指著自身節點的指標。

這樣設計的好處是，當需要刪除的節點是第一個節點時，可以直接透過 *pprev = next 來修改指標的指向。

另外，hlist 是一種特別針對雜湊表設計的鏈結串列。雖然雙向鏈結串列也可以用來實作雜湊表，但因為需要在開頭和結尾各使用 2 個指標，所以在 bucket 很大的情況下，會增加記憶體的使用量。

struct TreeNode:
二元樹節點的結構，包含一個整數值和兩個指向左右子節點的指標。

struct order_node：
用於存儲數字和其在陣列中的索引。它還包含一個 hlist_node 結構，用於將 hlist_node 添加到雜湊表中。

hlist_add_head：
將一個節點添加到雜湊表的頭部。

find：
在雜湊表中查找一個數字並返回其在中序的索引。如果找不到該數字，則返回-1。

dfs：
一個遞迴函數，用於建立二元樹。它先建立一個新的節點，然後在中序遍歷的結果中找到該節點的值，利用前序遍歷的第一個元素來確定根節點的值，並在中序遍歷中找到該元素，將其左邊的元素視為左子樹，右邊的元素視為右子樹，並以此劃分左右子樹。然後對左右子樹進行遞迴調用。

//左子樹
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size);
//右子樹
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,idx + 1, in_high, in_heads, size);

以下方 preorder[], inorder[] 為例:

preorder[0]	preorder[1]	preorder[2]	preorder[3]	preorder[4]	preorder[5]
3	9	12	20	15	7

inorder[0]	inorder[1]	inorder[2]	inorder[3]	inorder[4]	inorder[5]
12	9	3	15	20	7

root = 3，其對應中序的索引為 2，
其左右子樹的範圍便是

左子樹	右子樹
inorder[in_low]~inorder[idx-1]	inorder[idx+1]~inorder[in_high]
inorder[0] ~inorder[1]	inorder[3]~inorder[5]

對應回前序，其左右子樹的範圍便是

左子樹	右子樹
preorder[pre_low+1]~preorder[pre_high- (idx-in_low)]	preorder[pre_high -(idx-in_low)+1]~preorder[pre_high]
preorder[1]~preorder[2]	preorder[3]~preorder[5]

//左子樹
tn->left = dfs(preorder, 1, 2, inorder, 0, 1, in_heads, size);
//右子樹
tn->right = dfs(preorder,3 , 5, inorder,3, 5, in_heads, size);

buildTree：
用於建立二元樹。藉由呼叫 node_add 函式將 inorder 的節點建立一個雜湊表(雜湊函式為 : |val| % inorderSize。最後，它調用 dfs 函數來建立二元樹。

為了能快速找到值所對應中序的索引，我們建立一個雜湊表加快查詢，以值為3為例，當我們要找值為3其在中序的索引，我們會遍歷 hash = 3 % 5 ->heads[3]，第一個便是我們所要找的節點。

Linux 核心的 cgroups 相關原始程式碼

在 linux/kernel/cgroup/cgroup.c 中 css_next_descendant_pre 利用 pre-order walk 來尋找下一個後代。 css_for_each_descendant_pre 會使用 css_next_descendant_pre 尋找下一個後代，來進行 pre-order traversal 。

css_next_descendant_pre:

struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
			struct cgroup_subsys_state *root)
{
	struct cgroup_subsys_state *next;

	cgroup_assert_mutex_or_rcu_locked();

	/* if first iteration, visit @root */
	if (!pos)
		return root;

	/* visit the first child if exists */
	next = css_next_child(NULL, pos);
	if (next)
		return next;

	/* no child, visit my or the closest ancestor's next sibling */
	while (pos != root) {
		next = css_next_child(pos, pos->parent);
		if (next)
			return next;
		pos = pos->parent;
	}

	return NULL;
}

這個函式主要用於在樹中進行深度優先搜索，直到遍歷完整棵樹為止。

quiz2 測驗二

解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
在 Linux 核心找出 LRU 相關程式碼並探討

運作原理

LRU 緩存（Least Recently Used）是一種常見的緩存演算法，當緩存達到其容量時，會先淘汰最長時間未被訪問的數據。

結構:
list_head:
雙向鏈表用於實現 LRU 策略

hlist_head,hlist_node:
用於雜湊表，雜湊表則用於快速查找鍵值。

LRUNode：
每個節點包含一個鍵（key）、一個值（value）、一個雜湊表節點（hlist_node）和一個雙向鏈表節點（list_head）。

LRUCache：
主要的緩存結構，包含緩存的容量（capacity）、當前的數量（count）、一個雙向鏈表頭（dhead）和一個雜湊表頭陣列（hhead）。

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

struct list_head {
    struct list_head *next, *prev;
};

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

hlist_head 和 hlist_node 結構:

list_head 結構:

LRUCache 結構:

LRUNode 結構:

lRUCacheCreate：
用於創建一個新的 LRU 緩存，並初始化其容量和數量。

lRUCacheFree：
用於釋放 LRU 緩存的所有節點和緩存本身。

lRUCacheGet：
用於獲取指定 key 的 value。如果找到指定 key，則將其對應的節點移到雙向鏈表的頭部，並返回其值。

lRUCachePut：
用於增加或更新一個鍵值對。如果鍵已經存在，則更新其值並將其節點移到雙向鏈表的頭部。如果鍵不存在，則建立一個新的節點，並將其添加到雙向鏈表的頭部和雜湊表中。如果此時緩存已滿，則還需要從雙向鏈表的尾部淘汰一個最近最少使用的節點。

lRUCacheGet 和 lRUCachePut 的時間複雜度都是 O(1)。這是因為雜湊表可以在常數時間內完成查找操作，而雙向鏈表可以在常數時間內加入、刪除和移動節點的操作。這對於需要快速響應的緩存系統來說非常重要。

quiz2 測驗三

解釋上述程式碼的運作原理
在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。

運作原理

用來操作位元組（bit）

BITMAP_LAST_WORD_MASK(nbits):
產生一個遮罩，該遮罩的最後 nbits 位元為 0，其餘位元為 1。

BIT_MASK(nr):
產生一個遮罩，該遮罩的第 nr 位元為 1，其餘位元為 0。

BIT_WORD(nr):
計算第 nr 位元所在的 word 的索引。

__const_hweight8(w), __const_hweight16(w), __const_hweight32(w), __const_hweight64(w):
計算一個 8 位元、16 位元、32 位元或 64 位元的數字中，有多少位元為 1。

hweight_long(w):
計算一個長整數中，有多少位元為 1。

__ffs(word):
找出一個字中，最低位的 1 在哪一位。

__clear_bit(nr, addr):
清除位址 addr 中的第 nr 位元。

fns(word, n):
找出一個字中，第 n 個 1 在哪一位。

find_nth_bit(addr, size, n):
在一個記憶體區域中，找出第 n 個 1 的位元位置

Reference

2024q1 第 1 週測驗題
 2024q1 第 2 週測驗題
 Linux 核心的 hash table 實作
 Linux 效能分析工具: Perf

2024q1 Homework2 (quiz1+2)

quiz1 測驗一

運作原理

quick_sort

改進方法

縮減 begin[]的大小

避免最差狀況的快速排序實作

Linux 核心風格的 List API

Linux 效能分析工具: Perf

quiz1 測驗二

運作原理

Galloping mode

quiz2 測驗一

運作原理

Linux 核心的 cgroups 相關原始程式碼

quiz2 測驗二

運作原理

quiz2 測驗三

運作原理

Reference

Read more

2024q1 Homework5 (assessment)

2024q1 Homework4 (quiz3+4)

2024q1 Homework1 (lab0)