# 2025q1 Homework5 (assessment)
contributed by < `I-Ying-Tsai` >
## 選擇並改進三題測驗題目
## 閱讀心得：《因為自動飲料機而延畢的那一年》
在《因為自動飲料機而延畢的那一年》這篇文章中，作者用親身經歷揭示了從 0 到 1 開發產品時所必須面對的現實挑戰與成長曲線。最令我印象深刻的是，理想與現實之間的落差：在腦中模擬的設計往往很完美，然而當真正動手製作、接觸市場時，才會意識到現實世界的複雜性遠超過想像。這樣的經歷，讓人明白「了解現實世界的需求」是工程與創業成功的關鍵第一步。只有親自從零開發一項解決問題的產品，才能真正掌握它的全部細節、理解它的不足，也才有可能創造出屬於團隊的專業技術價值。
在閱讀過程中，我也思考了一個問題：如果先去研究那些市場上已經存在、被廣泛使用的自動化機器，了解其從機械結構到軟體設計的邏輯，然後再根據自己的理解進行修改或整合，這樣的路徑是否能更短一些？
## 課程教材與 CS:APP 閱讀心得
Chapter 2
:::danger
移除非必要的 `::: warning`，內容比標示更關鍵。
不要濫用粗體字 (即 `**`)
:::
**Q** : 在關於 [**MCS spinlock** 上鎖的程式碼](https://hackmd.io/@sysprog/linux-spinlock-scalability?stext=9161%3A516%3A0%3A1747541216%3ApnjiRT) 中，`while (0 == &node->locked)` 這裡為什麼是取 `node->locked` 的地址而不是取它的值?
**A** : 我對比 Linux 核心中關於 MCS spinlock 的程式碼，發現 `struct mcs_spinlock` 的定義如下 ：
``` c
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked; /* 1 if lock acquired */
int count; /* nesting count, see qspinlock.c */
};
```
其中可以發現 locked 是 `1` 時表示的是拿到鎖的狀態，而 `0` 則是還在等待拿鎖的狀態。但這依然沒有解決我的問題，因為這不就驗證了我覺得應該要取 `node->locked` 的值了嗎？於是我去查看了關於 **MCS Spinlock** 的實作後發現了其中有一行註解 ：
``` c
/*
* Lock acquired, don't need to set node->locked to 1. Threads
* only spin on its own node->locked value for lock acquisition.
* However, since this thread can immediately acquire the lock
* and does not proceed to spin on its own node->locked, this
* value won't be used. If a debug mode is needed to
* audit lock status, then set node->locked value here.
*/
```
我這時候突然想到 **MCS Spinlock** 實作的目的就是為了解決大量請求 `Curr` 造成 `Cache line` 爆炸的問題，所以才讓每個 `CPU` 都可以在自己的 `node->locked` 上自旋等待直到拿到鎖（關鍵思想為：應該是要現在拿鎖的人完成工作後主動告知：「我釋放鎖了！」，而不是其他 `CPU` 每隔一段時間就來催促說：「阿你到底好了沒？」 ），所以其實 `node->locked` 的值根本不重要，只要我知道我這個節點前面已經沒有其他人了（ 也就是釋放鎖的人主動告知的信息，這也是為甚麼檢查 `0 == &node->locked` ），我就可以直接拿到鎖，之所以可以這樣做，可以先查看解鎖的邏輯：
``` c
/*
* Releases the lock. The caller should pass in the corresponding node that
* was used to acquire the lock.
*/
```
發現說釋放鎖的時候，原本持有鎖的 `CPU` 需要移除相對應的節點。
**Q** : 為何需要 **CPU barrier** ？
**A** : 翻閱算盤書中 **barrier** 和 **fence** 出現的章節中，有幾個很常出現的重點：
- **1 :** `Synchronization`
- **2 :** `Parallelism`
以及從 **第 6.5 節** 中看到一句話說 :
`“To ensure correct synchronization across processors, RISC-V includes the fence instruction. It creates a memory barrier to enforce ordering constraints between memory operations.”`
於是可以得知 **CPU barrier** 的設計目的是避免記憶體操作的重排破壞同步邏輯，因為為了效能，**CPU** 常會重排記憶體操作( **Memory Ordering** )，而這些重排對 **單一執行緒** 無害，但會在 **多執行緒/多核** 中造成錯誤觀察順序。
而 **fence** 是讓程式設計者主動告訴硬體說這些記憶體操作的順序不能動
引用書中的例子：
``` c
// Core A
x = 1;
fence();
flag = 1;
// Core B
if (flag == 1)
assert(x == 1);
```
如果 A 核寫了變數但沒 `fence`，B 核可能讀不到最新值導致 `assert(x == 1)` 有可能不會成功執行。
**Q** : `spinlock` 裡頭使用 `barrier` 的方式和考量
**A** : 回顧 `spinlock` 的邏輯，其重點在 `my_ticket` 和 `curr_ticket` 這兩個變數上，先到的人先拿 `my_ticket` ，然後 `my_ticket++` ( 注意這邊會有 **cache coherence** 的開銷 )，接著進入自旋等待並不斷查看 `curr_ticket` 是否等於 `my_ticket` （注意這邊每次更新 `curr_ticket` ，也會產生 **cache coherence** 的開銷）。
然而就像前面所述，**CPU** 會為了提昇效能而 **重排指令**，而 `my_ticket` 和 `curr_ticket` 的更新並沒有資料相依，所以這些指令也有可能被 **CPU** 重排，但這會造成什麼結果呢？
- 我們可以先看一段在 Linux 核心中對於 `spinlock` 的實現部份中，在註解裡被提及的例子：
``` c
/*
* { X = 0; Y = 0; }
*
* CPU0 CPU1
*
* WRITE_ONCE(X, 1); WRITE_ONCE(Y, 1);
* spin_lock(S); smp_mb();
* smp_mb__after_spinlock(); r1 = READ_ONCE(X);
* r0 = READ_ONCE(Y);
* spin_unlock(S);
*/
```
這裡原本會是 **CPU0** 寫 `X` 為 `1` ，**CPU1** 寫 `Y` 為 `1` 後，兩邊各自得到 `r0 = 1` 和 `r1 = 1` ，然而如果這邊沒有 `Memory Barrier` 的存在來確保寫入的順序一定在 `Memory Barrier` 後面的那些指令 ( 讀取 ) 的前面的話，有可能 `r0` 會拿到 `0` ，或`r1` 會拿到 `0`，或兩個都拿錯。
- 另一個例子是：
``` c
/*
* { X = 0; Y = 0; }
*
* CPU0 CPU1 CPU2
*
* spin_lock(S); spin_lock(S); r1 = READ_ONCE(Y);
* WRITE_ONCE(X, 1); smp_mb__after_spinlock(); smp_rmb();
* spin_unlock(S); r0 = READ_ONCE(X); r2 = READ_ONCE(X);
* WRITE_ONCE(Y, 1);
* spin_unlock(S);
*/
```
一樣如果沒有 **Barrier** 的話，可能會出現：
- **CPU2** 看到 **CPU1** 的 `Y` 寫入（`r1 = 1`）
- 但卻看不到 **CPU0** 的 `X` 寫入（`r2 = 0`）
- 同時 **CPU1** 又看到 **CPU0** 的 `X`（`r0 = 1`）
:::danger
搭配閱讀 [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics)
:::
## 探討 memory order
在討論記憶體順序 (memory order) 時，有二個互補概念需要清楚區分：
1. 語言層面: 對 C11 而言，重點在抽象機器 (abstract machine) 的行為，及 `<stdatomic.h>` 所定義的語義；硬體細節應被視為下層實作，可透過語言本身的記憶體模型予以抽象處理。
2. 處理器架構層面: 理解目標硬體能提供哪些基本保證。早於 C/C++ 記憶體模型成型之前，並行程式設計仰賴的是硬體慣例與文件，例如《Intel® 64 and IA-32 Architectures Software Developer’s Manual》描述的排序規則與 barrier 指令。
### 快取一致性 (cache coherence) 與程式正確性
快取一致性協定 (如 MESI) 的主要目標是確保持有同一記憶體位置多份副本的快取行在任何時刻觀察到相同的值。此機制對並行程式「正確性」並無直接影響，因為它對軟體透明；開發者真正需要面對的，是快取一致性在多核處理器系統中帶來的延遲與頻寬成本。
值得注意的是：若多執行緒同時對同一快取行進行競爭寫入，只要其中一方獲得所有權並成功寫入，其結果最終將於系統內達成一致。這常被描述為「寫入操作具有全域順序」的基礎。
### Store Buffer 與一致性模型
寫入緩衝區 (Store Buffer) 允許 CPU 在尚未與快取同步前，先將寫入暫存於每核處理器的 buffer，以隱藏記憶體存取延遲。它雖不破壞快取一致性，但會使觀察到的記憶體順序 weak 化；此時若程式未適當插入記憶體屏障，就可能產生資料競爭。
### 亂序執行 (OoO) 與記憶體屏障
硬體可在 CPU 管線內自由重排尚未產生可見副作用的指令，最後透過 in-order commit 維持指令語義。對軟體而言，真正關注的是：
* 何時僅靠編譯器屏障 (compiler barrier) 即可抑制重排？
* 何時必須使用記憶體屏障 (memory barrier) 以約束硬體行為？
### x86 記憶體模型：TSO 概覽
x86/x64 架構對回寫式快取區域提供以下關鍵保證（摘自 Intel SDM Vol. 3A §8.2.3）：
* Load-Load、Store-Store、Load-Store 皆維持原始程式順序。
* 唯一允許的重排為 Store-Load，且僅限於不同記憶體位置。
* `LOCK` 前綴或序列化指令 (如 `MFENCE`, `CPUID`) 會形成全域順序點。
* 其他處理器觀察到單一處理器的多次寫入時，其順序一致。不同處理器對同一位置的寫入則無全域排序保證。
在這種模型下，C11 `memory_order_acquire` / `memory_order_release` 通常可直接映射為普通載入／儲存，不需要額外 `MFENCE`。編譯器只需插入對應的編譯器屏障，確保不得將操作合併或重排到不合法的位置。
### C11 Atomics 對照範例
下面的程式在所有支援 C11 的 x86 系統上皆能正確運作，而沒有顯式 `asm` 屏障。對順序較 weak 的架構 (如 Armv8-A) 同一程式仍能藉由編譯器自動插入 `dmb ish` 等指令獲得正確行為。
```c
#include <stdatomic.h>
#include <stdio.h>
static _Atomic int flag = 0;
static int data = 0;
void producer(void)
{
data = 42;
atomic_store_explicit(&flag, 1, memory_order_release);
}
void consumer(void)
{
while (atomic_load_explicit(&flag, memory_order_acquire) == 0)
;
printf("%d\n", data);
}
```
### Linux 核心的對應操作
* `smp_load_acquire(p)` 與 `atomic_load_explicit(p, memory_order_acquire)` 對等。
* `smp_store_release(p, v)` 與 `atomic_store_explicit(p, v, memory_order_release)` 對等。
* `smp_mb()` 對應 `atomic_thread_fence(memory_order_seq_cst)`。
在使用者空間撰寫程式時，盡量選用 C11 介面即可；核心程式碼則依 [LKMM](https://lpc.events/event/17/contributions/1551/attachments/1326/2662/lkmm.2023.11.14b.pdf) 定義使用對應巨集。
:::danger
TODO: 研讀上方 LKMM 投影片 (可找對應的錄影)，紀錄你的認知和提問。
:::
### atomic 的硬體支援
Intel 保證下列基本存取為 atomic：
* 8/16/32 位元對齊讀寫 (Intel486 及以上)
* 64 位元對齊讀寫 (Pentium 及以上)
* Cache line 內的未對齊 16/32/64 位元讀寫 (P6 及以上)
對讀取-修改-寫入操作 (`fetch_add`, `compare_exchange`) 仍須 `LOCK` 前綴或 `XCHG` 隱含鎖定。
### volatile 的定位
`volatile` 的正式用途在於：
* 與記憶體對應之裝置暫存器 (MMIO)。
* 在訊號處理器中讀寫 `volatile sig_atomic_t` 物件。
針對跨執行緒同步，請使用 `_Atomic` 與記憶體順序標註；若因特定原因必須採行 `volatile`，務必確定已理解目標編譯器與硬體對其的實作定義行為。
Linux 核心的 `READ_ONCE`、`WRITE_ONCE` 透過暫時的 `volatile` 轉型以阻擋編譯器重排，並在必要時搭配顯式 barrier。此機制基於 LKMM 的規範，不表示在一般 C 程式中可直接運用。
### 參考資訊
* Intel® 64 and IA-32 Architectures Software Developer’s Manual, Vol. 3A, Chapter 8.
* ARM® Architecture Reference Manual for ARMv8-A, Chapter D5 (Memory Model).
* Linux memory-barriers.txt 及 LKMM 文件。
## 期末專題構想簡述
Sign in with Wallet
Connect another wallet