# 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