---
# System prepended metadata

title: 2023q1 Homework5 (assessment)

---

# 2023q1 Homework5 (assessment)
contributed by <`yanjiew1`>

## 想問老師的問題

:::info
Fence 和 Barrier 的不同？
:::

:::info
Userspace RCU 實作有 `rcu-qsbr` 、 `rcu-signal` 和 `rcu-generic` 。想詢問 Linux Kernel 比較接近哪一種實作方式？
:::

:::info
[《Linux 核心設計: RCU 同步機制》](https://hackmd.io/@sysprog/linux-rcu)文章提到：「該狀態和 CS 相對，執行緒一旦離開 CS 就歸類於靜默狀態。每個 reader 在離開 CS 時記錄一下自身狀態，writer 檢查這個狀態，當所有執行緒都都離開 CS 時，就可釋放舊節點所在的記憶體。」

考慮 QSBR 演算法。如果 Reader 離開 CS 後又很快進入 CS ，導致沒有一個時間點時所有執行續都離開 CS ，那麼會不會 Writer 就永遠等不到時間可以釋放記憶體？

> Writer 只需要等其他執行續都離開一次 CS 即可，即使其他執行緒又重新進入 CS 也沒關係。　
:::

:::info
過去沒有上過大學的相關數學課。若要加強電腦科學所需的基礎數學，會建議怎麼加強？有沒有推薦的書？

> 老師的回答： Linux Kernel 需要的數學基礎：
> - 統計、機率
> - 線性代數 （出現在 Linux 內的 DRM 子系統）
> - 離散數學
> - 計算理論（離散數學先學）
>
> 加強方式 => 遇到就去學、去看相關的課
:::

:::info
在描述一個整數中的某一個位元時，我們通常會把最右邊位元作為第 0 位元，然後往左邊數嗎？如果寫在共筆文件內，需要特別說明數的方式嗎？

> 左邊和右邊是不正確的說法，因為左邊和右邊不一定最最高位或最低位，可以寫 MSB 和 LSB 。
:::

:::info
在 [quiz3 的第 3 題](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-3)，有一段程式
```c
/* Implementation of LFSR (linear feedback shift register)
 * on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1
 * (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1)
 */
static void lfsr(uint64_t *up)
{
    uint64_t new_bit =
        ((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
    /* don't have to map '+1' in polynomial */
    *up = ((*up) >> 1) | (new_bit << 63);
    /* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}
```

註解題到了一個多項式 `x^64 + x^61 + x^34 + x^9 + 1` ，但我看不太出來這個多項式跟程式碼中 `uint64_t new_bit = ((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;` 的關聯性。想詢問老師這二個部份的關聯，或能不能請老師給些題示？

> 我知道了，多項式的次方跟 64-bit 整數第幾位數正好是相反的。第 0 位是 `x^64` ，第 1 位是 `x^63` 故式子中 `(*up) >> 3` 是代表 `x^(64-3)` 為 `x^61` 以此類推。
> `lib/random32.c` 內有說明。 PRNG 用 LFSR 去產生。

需要再了解 LFSR 與 Galois field GF(2) 的關聯；還有多項式怎麼定義的
"irreducible polynomial"　=> "不可約多項式"

:::

:::info
如果想要成為像 Linus Torvalds 或像老師一樣對系統軟體很專精很厲害，能對 Linux 核心和開放原始碼軟體有貢獻的人，老師會怎麼建議學習的方向？

> 抱歉問了不專業的問題 QQ
:::

:::info
想詢問老師對於讀博士的看法是什麼? 若希望自已能更專精在電腦科學領域，能做出對資訊產業有貢獻的事，會建議讀博士嗎? 另外會建議在台灣讀博士，還是去美國或加拿大的學校讀呢？
:::


## 〈因為自動飲料機而延畢的那一年〉心得

我覺得我的人生（職涯），是從我現在 28歲才開始。

過去從沒這麼積極的為興趣和專業而學習。過去一直對電腦都保持著熱情，但因為自已在高職階段，因為自已情緒困擾和個人原因，沒有繼續讀資訊反而去讀英語系，後來又雙主修了視覺藝術與設計系。大學時又得了憂鬱症，我的資訊的專業就在此延誤了。

文章中有一句「然後我發現一個原本以為只有在資工系發生的現象，那就是『資工系的學生不會寫程式，機械系的學生不會做機械』。」我看也有同感，因為我大學是讀英文系和視覺藝術與設計學系，但覺得自已英文和畫畫二項都沒學好，畢業後反而去寫程式。當然大學時，因為憂鬱症，結果什麼都沒學好，但是也發現英文和畫畫都不是我的興趣，我的興趣是電腦。話又說回來，英文真的很重要，現在我也要好好去練習英文去考雅思檢定。

目前 28 歲，又回到了資工系學習。努力加上一點運氣，讓我考上了台大資工系。

自從進了碩士開始，發現自已有電腦科學的各種想學的知識和技能，包含系統軟體、編譯器、機器學習等。又發現許多理論基礎我還不會，像是微積分、離散數學、機率、資訊理訊等。但碩士只有二年，感覺短短時間要補足這些基礎不是那麼容易，我能做的就是盡力去做。我可以選擇專心跟著實驗室的計畫，找出論文題目，寫出論文，早早畢業；但我選擇另一條路，想好好學習補足之前沒學到的。

現在的我，要在資訊領域更專精，期許自己能像 Jserv 一樣或像 Linus Torvalds ，可以對開放原始碼有很多的貢獻，也能成為在資訊領域有影響力的人。

Jserv 真的是我很欣賞的老師，它在資訊領域的貢獻除了教學、指導學生外，還貢獻各種開放原始碼專案。我特別「開放原始碼」這一詞吸引。我小時候一直是開放原始碼的愛好者，大家都用 Microsoft Word 時，我用 OpenOffice 。只要有開放原始碼的選項可以用，我不會去用非開放原始碼軟體。有一陣子也把自已的電腦灌成 Ubuntu 。在大學時，使用 Adobe Illustrator 和 Adobe Photoshop 來做電繪的作業時，真的很希望自已也能寫一套開放原始碼且可以取代 Adobe Illustrator 和 Adobe Photoshop 的軟體，而且是能被大家所使用的，但後來知道這是很難的事，就沒有特別再去想了。

這學期我上 Jserv 老師開設的 Linux 核心課程，我寫這門旁聽課作業和閱讀教材花的時間，遠比我在台大上的任何課花的時間還多，也比做實驗室的研究多很多。我每週估計可能有15 ~ 20小時以上花在這門課上。有時做作業，有時看教材，有時思考研究這門課的延伸問題。我承認偶爾也有偷賴的時候，例如這次清明連假回台南時，雖然有帶電腦，但沒辦法專心做事，比較多時在享受在台南時光和陪伴家人，先前的二二八連假跟家人去台中玩。但其他空閒時間大多數都是花在這門課上。這門課沒有學分，因為台大的規定讓我沒辦法跨校選課，所以成績單上的記錄都不會有，但這它卻是我這學期花最多心思的課程。

既然決定好好學，就要把 Linux 核心學好，為自已未來的專業鋪路，也希望我能對 Linux 核心、開放原始碼軟體有所貢獻。最近也一直思考未來要不要讀博士，讓自已更加專精，更能成為在資訊產業有影響力的人。

## 教材閱讀

我忘記記錄之前閱讀教材筆記，現在開始記錄。

### C11 的 Atomic 操作及同步機制

- Sequentially consistent 與 Acquire Release 差別
  - C11 裡的 Acquire Release 是要搭配其他的 Acquire Release 一起使用，才能確保執行正確。
  - 例如在 x86 Acquire Release 沒有處理 Store-Load 的 Memory Barrier ，因為 C11 內，使用 Acquire 或 Release 這二種 Memory Order 不要求 Store-Load 必須不能重排。但是 Sequentially consistent 則確保任何情況下都不能重排。 (TODO: 再寫清楚一點)
    - 應該說 load-acquire 要配合 store-release ，也就是讀取到被另一個 store-release 寫入的值時，在 store-release 之前的動作都已完成。因為 x86 是 TSO ，不會重排 Load-Load, Load-Store 和 Store-Store ，故 acquire 和 release 都不必加 Memory Barrier 。
    - 因為 load-acquire 和 store-release 這些 semantics 不會需要考慮 store-load 重排，但在某些其他場合可能會需要，故仍然要有 sequence-consistent 這樣的記憶體排列。 
- C11 規格書閱讀

### 並行多執行緒程式設計

- Lock-free 程式設計

Lock-free 與 Wait-free


### 《Linux 核心實作 (2023): 第 9 週課程》心得

看到老師點進這篇文章《精通數位邏輯對 coding 有什麼幫助？》有所感觸。高等教育所教會希望我們不是只能做單一的事或研究。覺得自己要再補強數學，比較進階的電腦科學領域的東西，似乎都需要數學基礎。


## 作業連結

## 其他筆記

### 其他筆記連結

- [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)
- [第一次嘗試貢獻 Linux 核心](https://hackmd.io/@yanjiew/linux2023q1-1st_contrib)
- [關於紅黑樹](https://hackmd.io/@yanjiew/rbtree01)

### Linux 核心記憶體配置筆記

- `kmalloc` 使用 Slub Allocator 適合配置較小的記憶體，速度快，配置出來在實體位址是連續的。配置大空間可能失敗。
- `vmalloc` 開銷大，需要修改 Page Table 及 Flush TLB 。會直接配置 Pages 。
- `kvmalloc` 無法事先估算所需空間時使用。會先嘗試用 `kmalloc` ，若失敗才用 `vmalloc` 。

`kvfree` 可用來釋放 `kmalloc` 、 `vmalloc` 或 `kvmalloc` 的空間。


## 第九週作業檢討筆記

Trace code 技巧：
- 需要 Domain Know-how
- 不要看程式：
  - 用 GDB Trace （對並行程式要小心，可能不能好 Trace）
  - 把一段程式搬出來 

數學分析素養
- Fibonacci Driver 先分析要用的記憶體，一次配置好

HPC 伺服器與個人電腦差別：
- I/O 速度
- 高速網卡 、 RDMA 網路
- ECC Correction

注意細節

可改進 Linux 的地方
- 不同檔案系統的 unicode.c

學習 Unicode

學習 `/lib/math`
- GCD 不用除法，不用減法 (Binary GCD)
- SQRT: 不用浮點數，不用乘法和除法
- Prime Number: 找質數 （與 GPU Driver 有關）
  - 跟 RCU 有關 


永續：
- 數學分析
- 測試方法
- 文件撰寫

避免 cache 影響效能測試方法：
- 做 2 次運算 => 計算第 2 次時間。讓第一次 cache miss 忽略。


Fibdrv 相關 keywords：
- 大數運算
- 效能分析
- Mutex 同步相關
  - 查表
  - hash table

## 下半學期可能可以努力的目標

:::info
需要再跟老師確認方向
:::

之前作業改進
- Fibdrv:
  - 大數運算
- Quiz2: 計算 UTF-8 內的字數。使用真實資料分析，畫圖

寫之後的作業

核心貢獻
- 貢獻 Shivers Sort 排序演算法
- Filesystem 內的 'unicode.c' 改進
- 其他...
- 

學習 Rust

