# 2022q1 Homework1 (quiz1) contributed by < [2020leon](https://github.com/2020leon) > ## [作業要求](https://hackmd.io/@sysprog/B166rc3Jq) - [ ] 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)^從測驗一到測驗四^，附帶的「==延伸問題==」也需要完成 - 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz) - [ ] 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb), [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 和 [參考題解](https://hackmd.io/@RinHizakura/BysgszHNw) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。 - [x] 將你的共筆加到 [2022q1 Homework1 (作業區)](https://hackmd.io/@sysprog/linux2022-homework1) ## [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1) ### 測驗 `1` #### 測驗 `1` 資料結構 從題目中萃取資料結構。 ```c struct hlist_node { struct hlist_node *next, **pprev; }; struct hlist_head { struct hlist_node *first; }; typedef struct { int bits; struct hlist_head *ht; } map_t; struct hash_key { int key; void *data; struct hlist_node node; }; ``` ![](https://i.imgur.com/QYQLqvC.png) - `map_t` 為一雜湊表的實做，其最主要的成員為 `ht` ，即一指向 `struct hlist_head` 的指標。而 `bits` 則為定義其大小。然 `bits` 並非直接定義 `map_t` 的大小，其值表示以二為底的指數。更明確來說， `map_t` 的大小為二的 `bits` 次方。此可由以下巨集得知及函式實做得知 ```c #define MAP_HASH_SIZE(bits) (1 << bits) ``` ```c map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits)); ``` - `struct hlist_head` 僅為 `struct hlist_node` 的包裝 - `struct hlist_node` 內含 `next` 指向下一個節點，及 `pprev` 指向前一個節點的 `next` 成員 - `struct hash_key` 可理解為繼承 `struct hlist_node` 的結構，用於儲存資料本身 #### 測驗 `1` 填空 本題主要針對下方函式填空。 ```c void map_add(map_t *map, int key, void *data) { struct hash_key *kn = find_key(map, key); if (kn) return; kn = malloc(sizeof(struct hash_key)); kn->key = key, kn->data = data; struct hlist_head *h = &map->ht[hash(key, map->bits)]; struct hlist_node *n = &kn->node, *first = h->first; AAA; if (first) first->pprev = &n->next; h->first = n; BBB; } ``` 該函式主要目的為新增一筆資料至 hash table 中。藉 `first->pprev = &n->next` 可知該函式會將欲插入的資料放置至 list 的頭位置，因此 `AAA` 或 `BBB` 要分別針對 `n` 的 `pprev` 和 `next` 賦值。其中 `n->next = first` 、 `n->pprev = &h->first` （ `h` 為指向該 list 的頭結構 `struct hlist_head` 的指標），最後根據選項將上述二賦值式分別填入其中。 | 陳述式 | 答案 | | ----- | ---------------------- | | `AAA` | `n->next = first` | | `BBB` | `n->pprev = &h->first` | ### 測驗 `2` #### 測驗 `2` 資料結構 從題目中萃取資料結構。 ```c struct ListNode { int val; struct ListNode *next; }; ``` - `struct ListNode` 為一簡單的單向 linked list #### 測驗 `2` 填空 ```c struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; if (COND1) { /* Remove all duplicate numbers */ while (COND2) head = head->next; return deleteDuplicates(head->next); } head->next = deleteDuplicates(head->next); return head; } ``` 本題需針對上述程式碼中的 `COND1` 及 `COND2` 進行填空。藉由觀察上述程式碼可發現其為一遞迴函式：藉遞迴的方式將重複的數字移除。 填空時可由內而外解題。由於本函式的目的為將重複的數字移除，故先推論 `COND2` 為 `head->val == head->next->val` ，又因在比較時須確保 `head->next` 不為 `NULL` ，因此其應為 `head->next && head->val == head->next->val` 。再看 `COND1` ，由於只有含重複數字的 list 才需進入該區塊，因此條件同 `COND2` 。 | 陳述式 | 答案 | | ------- | -------------------------------------------- | | `COND1` | `head->next && head->val == head->next->val` | | `COND2` | `head->next && head->val == head->next->val` | #### 避免遞迴版本 ```c struct ListNode *_deleteDuplicates(struct ListNode *head) { struct ListNode *_head = NULL, **pptr = &_head; while (head) { while (head && head->next && head->val == head->next->val) { /* Remove all duplicate numbers */ while (head->next && head->val == head->next->val) head = head->next; head = head->next; } *pptr = head; if (head) { pptr = &head->next; head = head->next; } } return _head; } ``` #### Circular Doubly-linked List 版本 參見：[linux2022-lab0#q_delete_dup](https://hackmd.io/@6649/linux2022-lab0#q_delete_dup) ### 測驗 `3` #### 測驗 `3` 資料結構 ```c typedef struct { int capacity, count; struct list_head dhead, hheads[]; } LRUCache; typedef struct { int key, value; struct list_head hlink, dlink; } LRUNode; ``` - `LRUCache` 內含四個成員： `capacity` 為定義快取的大小、 `count` 為紀錄目前有效內容的變數、 `dhead` 為快取的所在、 `hheads` 為 flexible array member ，內容為所有的資料 - `LRUNode` 為用於儲存資料的結構，內含四個成員： `key` 為搜尋時的唯一值， `value` 為所儲存的資料、 `hlink` 為在 `LRUCache::hheads[]` 中的 `struct list_head` 結構、 `dlink` 則為在 `LRUCache::dhead` 中的 `struct list_head` 結構 #### 測驗 `3` 填空 本題需針對下方各區塊程式碼的 `MMM1` 、 `MMM2` 、 `MMM3` 及 `MMM4` 進行填空，其均為 Linux 核心風格的 list 巨集，以 `list_` 開頭。 首先是 `MMM1` 。 ```c void lRUCacheFree(LRUCache *obj) { LRUNode *lru, *n; MMM1 (lru, n, &obj->dhead, dlink) { list_del(&lru->dlink); free(lru); } free(obj); } ``` 其答案應為 `list_for_each_entry_safe` 。藉由函式名稱得知此函式應會刪除所有的節點，因此在所有 `list_for_each_` 開頭及 `_safe` 結尾的巨集均為候選，再來根據資料型態可知應填 `list_for_each_entry_save` 。 再來是 `MMM2` 。 ```c int lRUCacheGet(LRUCache *obj, int key) { LRUNode *lru; int hash = key % obj->capacity; MMM2 (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); return lru->value; } } return -1; } ``` 該函式功能為遍歷 `obj->hheads[hash]` 以尋找對應的值，並將找到的值放入 `obj->dhead` 中。根據功能及資料型態，答案應為 `list_for_each_entry` 。 最後是 `MMM3` 及 `MMM4` 。 ```c void lRUCachePut(LRUCache *obj, int key, int value) { LRUNode *lru; int hash = key % obj->capacity; MMM3 (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); lru->value = value; return; } } if (obj->count == obj->capacity) { lru = MMM4(&obj->dhead, LRUNode, dlink); list_del(&lru->dlink); list_del(&lru->hlink); } else { lru = malloc(sizeof(LRUNode)); obj->count++; } lru->key = key; list_add(&lru->dlink, &obj->dhead); list_add(&lru->hlink, &obj->hheads[hash]); lru->value = value; } ``` `MMM3` 的功能同 `MMM2` ，因此填 `list_for_each_entry` 。 `MMM4` 是要在快取已滿的情況下從相關的 list 移除節點。觀察 `lRUCacheGet` 與 `lRUCachePut` 可知最新的節點會在 list 的頭部，為符合 LRU ，須將位在最尾端的節點移除，因此答案應為 `list_last_entry` 。 | 陳述式 | 答案 | | ------ | -------------------------- | | `MMM1` | `list_for_each_entry_save` | | `MMM2` | `list_for_each_entry` | | `MMM3` | `list_for_each_entry` | | `MMM4` | `list_last_entry` | ### 測驗 `4` #### 測驗 `4` 資料結構 ```c struct seq_node { int num; struct list_head link; }; ``` - `struct seq_node` 內含兩個成員： `num` 用於儲存數字、而 `link` 則是用於串接其他 `struct list_head` 物件用的 #### 測驗 `4` 填空 本題需要填空的空格為 `LLL` 及 `RRR` 。 ```c int longestConsecutive(int *nums, int n_size) { int hash, length = 0; struct seq_node *node; struct list_head *heads = malloc(n_size * sizeof(*heads)); for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; i < n_size; i++) { if (!find(nums[i], n_size, heads)) { hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(*node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } for (int i = 0; i < n_size; i++) { int len = 0; int num; node = find(nums[i], n_size, heads); while (node) { len++; num = node->num; list_del(&node->link); int left = num, right = num; while ((node = find(LLL, n_size, heads))) { len++; list_del(&node->link); } while ((node = find(RRR, n_size, heads))) { len++; list_del(&node->link); } length = len > length ? len : length; } } return length; } ``` 此函式輸入一個整數陣列，輸出 Longest Consecutive Sequence 的長度。函式 `longestConsecutive` 上半部將整數陣列轉換成 `struct list_head` 。觀察 `LLL` 及 `RRR` 的位置，可知其嘗試在 list 中尋找是否有鄰近的數字。觀察變數 `left` 和 `right` 的宣告，可得其初始值均為 `num` ，也就是 `node->num` 。因此在尋找鄰近數字時，應尋找已經加一或減一的數值。綜觀選項， `LLL` 應填入 `--left` ，而 `RRR` 應填入 `++right` 。 | 陳述式 | 答案 | | ----- | --------- | | `LLL` | `--left` | | `RRR` | `++right` |
Last changed by  
 
6649
290

Read more

2022q1 Homework1 (lab0)

contributed by < 2020leon > 作業要求 [x] 在 GitHub 上 fork lab0-c參閱 Git 教學和 GitHub 設定指引 ^附教學影片^ [x] 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

2/23/2024
2022q1 Project (cpumemory)

contributed by < 2020leon > 目標 [ ] 閱讀 Ulrich Drepper 於 2007 年撰寫的論文《 What Every Programmer Should Know About Memory 》(版次: 1.0) [ ] 嘗試執行第六章提及的程式碼 [ ] 翻譯和校訂《每位程式開發者都該有的記憶體知識》 環境 $ uname -a

6/30/2022
2022q1 Homework3 (quiz3)

contributed by < 2020leon > 作業要求 [ ] 重新回答第 3 周測驗題^從測驗一到測驗十一^，附帶的「==延伸問題==」也需要完成 解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析 [ ] 比照 課前測驗參考解答: Q1, Linked list 題目分析 和 參考題解 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。 [x] 將你的共筆加到 2022q1 Homework3 (作業區)

3/21/2022
2022q1 Homework3 (fibdrv)

contributed by < 2020leon > 作業要求 自我檢查清單 [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗; [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說 [ ] 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本; [ ] 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？ [ ] lsmod 的輸出結果有一欄名為 Used by，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？

3/19/2022
Read more from 6649
Published on HackMD