2023q1 Homework5 (assessment)

contributed by <yanjiew1>

想問老師的問題

Fence 和 Barrier 的不同？

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

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

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

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

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

老師的回答： Linux Kernel 需要的數學基礎：

• 統計、機率
• 線性代數 （出現在 Linux 內的 DRM 子系統）
• 離散數學
• 計算理論（離散數學先學）

加強方式 => 遇到就去學、去看相關的課

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

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

在 quiz3 的第 3 題，有一段程式

/* 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"　=> "不可約多項式"

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

抱歉問了不專業的問題 QQ

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

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

我覺得我的人生（職涯），是從我現在 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 核心貢獻嘗試
• 第一次嘗試貢獻 Linux 核心
• 關於紅黑樹

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

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

需要再跟老師確認方向

之前作業改進

• Fibdrv:
  • 大數運算
• Quiz2: 計算 UTF-8 內的字數。使用真實資料分析，畫圖

寫之後的作業

核心貢獻

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

學習 Rust