# 2024q1 Homework5 (assessment)
contributed by < `yeh-sudo` >

## 改進測驗題

* [第 2 週測驗題 - 測驗 `1`](https://hackmd.io/godDgeeFQGGO1tWZtU9LSQ?view#%E6%B8%AC%E9%A9%97-11)
* [第 2 週測驗題 - 測驗 `2`](https://hackmd.io/godDgeeFQGGO1tWZtU9LSQ?view#%E6%B8%AC%E9%A9%97-21)
* [第 2 週測驗題 - 測驗 `3`](https://hackmd.io/godDgeeFQGGO1tWZtU9LSQ?view#%E6%B8%AC%E9%A9%97-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](https://preshing.com/20120612/an-introduction-to-lock-free-programming/)

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


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

- [ ] Lock-Free Data Structure

在 CMU 的教材 [Lock-Free Programming](https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf) 討論 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

:::info
> 在 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 嗎？
:::

## 簡述想投入的專案

### [高效網頁伺服器](https://hackmd.io/@sysprog/linux2023-projects#%E9%AB%98%E6%95%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8)

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

### [simplefs](https://hackmd.io/@sysprog/linux2023-projects#simplefs)

我自己實習的公司是生產 NAS 與各種儲存裝置的，而 NAS 中運作的作業系統就是 Linux ，公司也積極尋求 [Linux 核心的開發者](https://career.synology.com/zh-tw/HQ/position/154)，透過這個專案，可以了解檔案系統的運作原理，並且透過這個專案找到工作。

### [改進 Linux 核心的 lib/{list_}sort.c](https://hackmd.io/@sysprog/linux2023-projects#%E6%94%B9%E9%80%B2-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-liblist_sortc)

因為在 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 週](https://hackmd.io/@sysprog/linux2024-quiz8), [第 9 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz9)
[並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)
[從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability)
[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched): M:N threading model
[並行程式設計: 建立相容於 POSIX Thread 的實作](https://hackmd.io/@sysprog/concurrency-thread-package)