2024q1 Homework2 (quiz1+2)
contributed by <YeeeLiang>
第一周 測驗1
延伸問題
1. 原始程式碼的解釋:
- 節點結構 (node_t):
代表鏈結串列中的一個節點。
包含指向左右子節點,以及一個指向下一個節點的指標。
- 串列操作函數:
list_add: 在串列的開頭添加一個節點。
list_tail: 返回串列的尾部。
list_length: 返回串列的長度。
list_construct: 建構一個新節點並將其添加到串列的開頭。
list_free: 釋放串列佔用的記憶體。
- quick_sort:
使用輔助堆疊(begin 和 end)實現快速排序的非遞迴,來跟蹤子串列。
- main:
創建一個整數陣列,對其進行洗牌,構建一個鏈結串列,使用快速排序進行排序。
2. 改寫的程式碼:
第一周 測驗2
延伸問題
- run_size 函數:計算當前非遞減順序的元素序列(run)的大小。
- merge 函數:將兩個run合併為一個。
- build_prev_link 函數:為合併後的run建立前一個連結。
- merge_final 函數:在合併主run後,合併剩餘的runs。
- find_run 函數:在輸入列表中找到下一個run。
- merge_at 函數:在指定位置合併兩個相鄰的runs。
- merge_force_collapse 函數:強制折疊,不斷合併相鄰的runs。
- merge_collapse 函數:根據設定條件合併runs。
- timsort 函數:協調整個Timsort演算法,查找並合併runs,直到堆疊被折疊。
- 改進後程式碼:
第二周 測驗1
延伸問題
1.
這段程式碼主要是用在構建二叉樹,基於給定的先序遍歷(preorder)和中序遍歷(inorder)序列,通過深度優先搜索(DFS)的方式構建對應的二叉樹。其中,使用了哈希表(Hash table)和鍊錶(linked lists)的概念,來實現尋找元素在中序序列中的索引功能。
程式碼中的主要結構和功能包括:
- 定義一個單向鏈錶的節點結構 struct hlist_node 和一個哈希鏈錶的頭結構 struct hlist_head。
- 定義一個二叉樹節點的結構 struct TreeNode。
- 使用了一個哈希鏈錶結構 struct order_node 來保存中序序列中元素的值、索引,並連接到哈希鏈錶中。
- 構建二叉樹的主函數 buildTree,可初始化哈希鏈錶,並調用 dfs 開始構建二叉樹。dfs 為使用 DFS 遞迴構建二叉樹的函數 。
- 程式碼中使用了哈希值計算索引的方式,可以考慮使用現有的哈希函數,而非簡單的 (num < 0 ? -num : num) % size。
- 記憶體管理:在程式中使用了 malloc 分配內存,但缺乏相應的 free 釋放內存的操作。
- 沒有處理例外情況:程式碼沒有處理 malloc 失敗的情況,應該在分配內存後,設置檢查是否成功。
2.
cgroups(Control Groups)是 Linux 內核中的一個機制,用於限制、分類和監控進程及其資源的使用。cgroup 組成一個樹狀結構,而其中每個節點代表一個 cgroup。Pre-order walk是一種樹狀結構中的走訪方式,它會先訪問父節點,然後再訪問子節點。
pre-order walk 程式碼:
第二周 測驗2
延伸問題
1.
雙向鏈表(struct list_head):
- 用於根據元素的使用情況維護緩存中元素的順序。
- INIT_LIST_HEAD:初始化一個空的雙向鏈表。
- __list_add:在指定的元素之後將新元素添加到鏈表中。
- __list_del:從鏈表中刪除元素。
哈希表(struct hlist_head):
- 用於根據鍵快速訪問緩存中的元素。
- INIT_HLIST_HEAD:初始化一個空的哈希表。
- hlist_add_head:將新元素添加到哈希表中。
- hlist_del:從哈希表中刪除元素。
LRUCache 結構:
- 維護一個雙向鏈表(dhead)來跟蹤元素的使用順序。
- 使用哈希表數組(hhead)以便高效地根據鍵訪問緩存元素。
- LRUNode 結構表示緩存中的鍵值對,具有雙向鏈表節點和哈希表節點。
LRUCache 操作:
- lRUCacheCreate:初始化並分配 LRUCache 結構的內存。
- lRUCacheFree:釋放 LRUCache 結構及其元素使用的內存。
- lRUCacheGet:從緩存中檢索與給定鍵相關聯的值。
- lRUCachePut:在緩存中插入或更新鍵值對。
改進的地方:
- 在 lRUCachePut 中的 list_move 函數存在潛在問題:因為在為 cache 分配值之前,它就已被移動。這可能導致未定義的行為。應該在分配值之前移動項目(&c->link)而不是 &cache->link。
- lRUCacheFree函數使用list_entry 從列表中訪問 LRUNode,但雙向鏈表的用法為 list_entry。故應該更改為list_entry。
2.
在 Linux 核心的虛擬記憶體管理和緩存中,LRU 策略的實現是系統性能的關鍵部分。這些代碼確保了對於使用頻率較低的頁面進行有效管理,以最大程度地減少對物理內存和磁盤 I/O 的需求。
LRU相關程式碼:
第二周 測驗3
延伸問題
1.
這是一組用於操作和搜尋位元,在由無號長整數陣列表示的位圖巨集和內嵌函數。旨在以高效的方式進行位元操作和搜尋,1並考慮到不同的字大小(8、16、32 和 64 位元)。find_nth_bit 函數是核心部分,提供了在位圖中查找第 n 個設置位元位置的通用方法。
位元操作巨集:
- BITS_PER_LONG:定義了無號長整數中的位元數(假定為 64 位元)。
- BIT_MASK(nr):創建具有第 n 位元設置的位遮罩。
- BIT_WORD(nr):確定包含第 n 位元的無號長整數的索引。
- BITMAP_LAST_WORD_MASK(nbits):為位圖中的最後一個單詞創建一個位遮罩。
向上取整的除法巨集:
- DIV_ROUND_UP(n, d):將 n 除以 d 並向上取整。
位元計數巨集:
- __const_hweight8(w):計算 8 位元字中設置位元的數量。
- __const_hweight16(w)、__const_hweight32(w)、__const_hweight64(w):將位元計數擴展到 16、32 和 64 位元。
- hweight_long(w):使用 64 位元計數的包裝函數,對無號長整數進行計數。
最小值巨集:
查找第 n 個設置位元:
- FIND_NTH_BIT(FETCH, size, num):查找在由 FETCH 定義的位圖中的第 n 個設置位元的位置。它使用輔助函數 hweight_long 和 fns 來實現。
查找第一個設置位元的函數:
- __ffs(word):查找字中第一個設置位元的位置。
清除位元的函數:
- __clear_bit(nr, addr):在給定地址上清除第 n 位元。
查找第 n 個設置位元的函數:
- find_nth_bit(addr, size, n):查找由 addr 和 size 指定的位圖中的第 n 個設置位元的位置。
其他巨集:
- small_const_nbits(nbits):檢查位元數是否是常數且在單個無號長整數的範圍內。
- GENMASK(h, l):生成具有第 l 到第 h 位元設置的遮罩。
2.
find_nth_bit
函數通常用於在位元運算中找到某個位元序列的第 n 個設定(或清除)的位元,可應用在 CPU affinity 設定中。而在 Linux 核心中,CPU affinity 相關的原始碼通常與進程排程和任務管理有關。
一個常見的使用案例是在 sched.h
中,可能會涉及到 cpumask_t 類型的位元遮罩,而 find_nth_bit
可能用於在這些位元遮罩中找到特定的 CPU。