2024q1 Homework5 (assessment)

contributed by < yeh-sudo >

改進測驗題

• 第 2 週測驗題 - 測驗 1
• 第 2 週測驗題 - 測驗 2
• 第 2 週測驗題 - 測驗 3

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

「這個領域實在是太過廣博，現實如同真理般，給予和狂妄自負的傢伙相對應的絕望，對於沒有準備好的人毫不留情。我覺得自己像無頭蒼蠅一樣亂撞，做什麼都徒勞無功。」

在學習課程教材時，常常讓我有一種無力感，一方面是基礎不夠扎實，經過大學四年，我連最基本的 C 語言都沒有完全掌握，基本的語言特性與規格都沒有完全掌握了，更不用說編譯器的行為，如何最佳化等等議題，從第一週的指標與鏈結串列，到 bitwise 操作以及編譯器，每一個議題都可以再深深的往下挖，可以有許多延伸資料，有許多相關的議題可以討論，但時間總是不夠，看完一個錄影三個小時，就要花上可能一天來理解教材內容，教材內又還會延伸往另一個教材或是連結，怎麼學都學不完，看著教材內容發呆，想著我還要多久才能精通這些東西，讓自己寫出來的東西是可以被這個世界接受的，是安全、優美且可以重複被利用的，另外，看看別人寫的作業，跟我寫的作業，我努力絞盡腦汁想要做出自己想要的成果，或是想要用新的方法測試，但總是有同學可以想到更特別且合理的方法，觀摩同學的作業，也讓我體會到自身的不足，雖然很無力很累，但我開始學著注意細節，注意讓程式碼更安全，這堂課學的東西，可能比我之前每個學期學的還要多。
雖然現在才學期中，但我想學期末這門課結束時，是一個全新的開始，因為 Linux 核心每天都在變化，每天都有許多貢獻者貢獻程式碼，這堂課指引我們一個明確探討 Linux 核心與其他系統軟體的方向，這學期結束，我想是時間來好好複習計算機組織、作業系統與編譯器等等課程，到時候再回頭看這門課，一定會有不一樣的感受，搞不好能有機會貢獻程式碼到 Linux 核心。

研讀課程教材

並行程式設計 - 概念

Concurrency vs. Parallelism

Concurrency 為程式架構，著重於拆分工作，以 Android 手機來說，運作時會有多個驅動程式，但彼此間都是獨立的，有時會互相合作，我們要去確保程式之間的執行順序。 Parallelism 著重規劃， 將能夠並行的程式，分配給不同硬體單元，可能是 CPU 或是 GPU ，使其同時執行。

Linux 核心設計: 淺談同步機制

什麼時候需要進行同步？

• 多個 CPU 要存取一個記憶體位置時
• 執行緒在 barrier 等待另外一個執行緒執行
• CPU 中斷處理，例如： IPI (Inter-Processor Interrupt)

作業系統提供的機制

1. Locks

• Coarse-grained Lock
  持有時間較長，並且可以延長持有時間，但運用 lock 本身較複雜，保護一個區域，要還原的代價較大。
• Fine-grained Lock
  持有時間很短，不用鎖住整個區域，但資源管理代價較大。真實世界中往往在 coarse-grained 與 fine-grained 之間取捨。

2. Atomic Instructions

確保整個操作在不同處理器上， load 與 store 不會交錯。

An atomic instruction guarantees that the entire operation is not interleaved with any other CPU.

• Examples

1. Atomic increment/decrement
   確保共享資源的執行順序不會交錯。
2. Compare and swap (CAS)
   ​​​​int compareAndSwap(int *loc, int expectedValue, int valueToStore) {
   ​​​​    ATOMIC {
   ​​​​        int val = *loc;
   ​​​​        if (val == expected) {
   ​​​​            *loc = valueToStore;
   ​​​​        }
   ​​​​        return val;
   ​​​​    }
   ​​​​}
   

• Lock-Free Programming

文章中用一張圖來定義 lock-free。

所以， lock-free 不一定是指有沒有使用 mutex ，而是指程式被某一種方法鎖定的可能性。

• Lock-Free Data Structure

在 CMU 的教材 Lock-Free Programming 討論 lock-free 的資料結構。

3. Atomic Instructions + Locks

1. Set counter to 1
2. Set the value to 0, go ahead
3. If get < 0, waiting
4. Increment and decrement counter are atomic operations.

Waiting Strategies

• Spinning: 在迴圈中不斷檢驗 atomic counter ，如果變為 1 ，則嘗試使用 atomic decrement 取得 lock 。
• Blocking: 沒有搶到 lock 就加入 wait-queue 然後休眠，等待有人 unlock 後才會被喚醒。

Linux Lock Strategies

• Blocking: mutex, semaphore
• Non-blocking: spinlocks, seqlocks, completions

在 Linux 核心中，起初僅有 semaphore 這個核心物件 (kernel object)，直到 v2.6.16 核心才將 mutex 自 semaphore 實作中抽離。儘管 Mutex 與 Semaphore 兩者都是休眠鎖，但 Linux 核心實作 mutex 時，運用加速技巧，將上鎖區分以下三個步驟：

Fast path: 嘗試使用 atomic operation，減少 counter 數值來獲得鎖。
Mid path: 上一步若失敗，嘗試使用特化的 MCS spinlock 等待，再取鎖。當持鎖的 thread 還在執行，且系統不存在更高優先權的任務時，即可推定，持鎖的 thread 很快就會把鎖釋放出來，因此會使用一個特化的 MCS spinlock 等待鎖被釋放。特化的 MCS spinlock 可在被重新排程時，退出 MCS spinlock queue。當走到這步時，就會到 Slow path。
Slow path: 鎖沒有辦法取得，只好把自己休眠。走到這一步，mutex 才會將自己加入 wait-queue 然後休眠，等待有人 unlock 後才會被喚醒。

這段描述在 Linux 核心中 mutex 的實作方法，其中 wait-queue 與 spinlock 都有用到，這樣還算是 blocking 的 lock 嗎？

簡述想投入的專案

高效網頁伺服器

在修這堂課之前，我有自學後端與一點網頁設計，但在都端的學習上，都是用別人現成的框架例如 Fastapi 或是 Flask 等，這些框架都是在網頁伺服器上執行，像 Fastapi 是在 Uvicorn 上執行的，我想透過這個專案，完成一個網頁伺服器，或是修改現有的專案，以便於之後再這個網頁伺服器上開發自己的開源後端框架，並學習並行程式設計等相關議題。

simplefs

我自己實習的公司是生產 NAS 與各種儲存裝置的，而 NAS 中運作的作業系統就是 Linux ，公司也積極尋求 Linux 核心的開發者，透過這個專案，可以了解檔案系統的運作原理，並且透過這個專案找到工作。

改進 Linux 核心的 lib/{list_}sort.c

因為在 lab0-c 與第一次測驗中，都有提及排序演算法，我覺得我當時的作業都還有延伸的空間，以及尋求改進 Linux 核心中排序演算法的機會。

---

pthread_rwlock_rdlock
RAID
fs, fs cache, dentry,
database
sysfs, procfs, …
Flash, SSD, block-based
storage medium
spinlock (unsleepable) vs. mutex (sleepable) 差異 (教科書)
spinlock: IRQ (interrupt request), fs (i-node),
seqlock

TODO:
https://github.com/sysprog21/cserv
第 8 週, 第 9 週測驗題
並行程式設計: Atomics 操作
從 CPU cache coherence 談 Linux spinlock 可擴展能力議題
並行程式設計: 排程器原理: M:N threading model
並行程式設計: 建立相容於 POSIX Thread 的實作