2024q1 Homework2 (quiz1+2)

contributed by < PochariChun >

Quiz 1

Quiz 1 -1 程式碼解釋

Quiz 1 的函式是一個使用非遞迴方法實做的快速排序, 其中以自定義的結構體 node_t, 作為鏈結串列的節點, 並透過間接指標 **list 來操作 node_t 節點的內部元素:

What is 'AAAA'?

AAAA 出現在 list_length 函式中, 這個函式先 判斷 間接指標現在指向的點 *left 和指向的點的下一個點 (*left)->next 是否存在, 存在則重複執行 AAAA 這個動作. 不存在就回傳現在指向的節點位址 *left.

已知 *left 指向尾端時為 NULL, 迴圈中止. 可判斷 AAAA 這個動作是 "透過間接指標走訪", 可以推斷是 linked list 和非連續記憶體 中提過的間接指標指向 next 的走訪技術, 也就是 AAAA = (*left)->next.

What is 'BBBB'?

BBBB 出現在 list_length 函式中, 最後回傳的是數字 n, 因為 n 的初始值為 0, 加上函式名稱為計算長度, 故推斷 n 是用於計算走訪節點數量的計數器.
函式接著 判斷 間接指標 現在指向的點 *left 是否存在, 存在則重複執行計數器加一, 和 BBBB 這個動作.
已知 *left 指向尾端時為 NULL, 迴圈中止. 故 BBBB 這個動作同樣是 "透過間接指標走訪", 也就是 BBBB = (*left)->next.

What is 'CCCC', 'DDDD', 'EEEE'?

這三個敘述都在非遞迴快速排序的主函式中, 這個函式用兩個儲存指標的陣列 begin[ ] 和 end[ ] 作為堆疊，去儲存尚未排列好的串列, 以 stack 達到取代遞迴的方式。
begin[ ] 代表尚未排列好的串列開頭, end[ ]則代表尚未排列好的串列結尾,
一開始先假定輸入的整串連結串列是未排序的, 就將整串串列開頭放入 begin[0], 尾端節點放入 end[0]。

接著從 begin 和 end 兩個 代表未排序的 stack 之中 "取出" 最上方串列, 使用 L 和 R 兩個指標分別指向現在處理的串列的開頭和結尾. 也就是取出的 begin 和 end.

如果 L 不等於 R, 就根據現在未排序串列中的 pivot 分類串列, 分別成為數值小於 pivot 的串列, pivot ,和數值大於 pivot 的串列.

如果 L, R 指向同個位置，就表示現在 stack 最上層的串列是已經排序完畢，可以把這個節點加入結果串列最後 (最大)的位置. 於是透過 i-- 可以做到從 stack 中 pop 的效果,

取出: 並非真正意義上從 stack 陣列取出, 而是使用 L 和 R 指標分別指向這些開頭節點, 最後要將分類結果存入 stack 時, 無視 stack 最上方那筆資料, 從那個位置開始存入三個分類結果

確定 L 和 R 之後, 使用底下迴圈走訪 pivot 後續的節點的值, 如果比較大, 就把這個節點加入 right 連結串列之中, 沒有比較大就加入 left 連結串列,
由於是走訪, 故 CCCC = p->next

while (p) {
                node_t *n = p;
                p = CCCC;
                list_add(n->value > value ? &right : &left, n);
            }

將這個串列 分類 成 "小於 pivot 的 left", "pivot", "大於 pivot 的 right" 的三個串列, 將這些串列的開頭和結尾指標 依序存入 begin 和 end 兩個 stack 的 i ~i +2 層.
故 DDDD = list_tail(&left),
故 EEEE = list_tail(&right),
這樣可以用 stack 模擬原本使用遞迴呼叫來實做快速排序的方式,

最後可歸納出這個函式的運行原理:

• 從 begin 和 end 兩個 代表未排序的 stack 之中 "取出" 最上方串列, 將此串列開頭和結尾分別作為 L 和 R.
  1. 如果 L 不等於 R, 將這個串列 分類 成 "小於 pivot", "pivot", "大於 pivot" 的三個串列, 將這些串列的開頭和結尾指標 依序存入 begin 和 end 兩個 stack .
  2. 如果 L, R 指向同個位置，就把這個 stack 的節點加入結果串列之前.

重複這兩個過程, 直到清空整個 stack, 最後回傳 result 就是由小到大排序好的結果.

Linux 核心風格的List API 改寫

改進實作

延伸問題

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

Quiz 1 -2

a >>= 1; 意思 跟a >>1

​​​​a >>= 1;

a >>= 1; 是就地修改變數 a 的值，而 a >> 1 僅僅是一個右移運算的結果，不會修改 a 的值。

Quiz 2

Quiz 2 -1

延伸問題

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

Quiz 2 -2

延伸問題

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

Quiz 2 -3

延伸問題

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