---
# System prepended metadata

title: '2022q1 [Homework1](https://hackmd.io/@sysprog/linux2022-homework1) ([quiz1](https://hackmd.io/@sysprog/B166rc3Jq))'
tags: [linux2022]

---

# 2022q1 [Homework1](https://hackmd.io/@sysprog/linux2022-homework1) ([quiz1](https://hackmd.io/@sysprog/B166rc3Jq))
contributed by < [`kuihao`](https://github.com/kuihao) >
###### tags: `linux2022`
[**測驗說明:** Linux 實作 (2022) 第 1 週課程 (B)](https://youtu.be/7hOS8pMuZY0?t=4823)

---
## 測驗 1
### 題目：[補完程式碼](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-1)
* AAA = ?
    * `(a) /* no operation */`
    * `(b) n->pprev = first`
    * `(c) n->next = first`
    * `(d) n->pprev = n`
* BBB = ?
    * `(a) n->pprev = &h->first`
    * `(b) n->next = h`
    * `(c) n->next = n`
    * `(d) n->next = h->first`
    * `(e) n->next = &h->first`
#### ==作答區==
#### **解題策略**
### 延伸題目
1. 解釋上述程式碼運作原理
2. 研讀 Linux 核心原始程式碼 [include/linux/hashtable.h](https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h) 及對應的文件 [How does the kernel implements Hashtables?](https://kernelnewbies.org/FAQ/Hashtables)，解釋 hash table 的設計和實作手法，並留意到 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 的 `GOLDEN_RATIO_PRIME`，探討其實作考量
#### ==作答區==
#### **解題策略**

## 測驗 2
### 題目: [補完程式碼](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-2)
* COND1 = ?
* COND2 = ?
### 延伸問題:
* 嘗試避免遞迴，寫出同樣作用的程式碼
* 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

## 測驗 3
### 題目: [補完程式碼](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-3)
### 延伸問題:
* 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
* 在 Linux 核心找出 LRU 相關程式碼並探討

## 測驗 4
### 題目: [補完程式碼](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-4)
### 延伸問題:
* 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
* 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼

## 個人紀錄
- [x] 2022/03/14 看完 [Linux 實作 (2022) 第 1 週課程 (B)](https://youtu.be/7hOS8pMuZY0?t=4823) 