# Linux 核心專題: 同步處理機制
> 執行人: JeffBla
> [解說影片](https://youtu.be/Doc_10o-2Sw)

## 任務簡述
回顧[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)教材，探究 Linux 核心的同步處理機制，理解其原理、重新實作，並量化分析。
> 搭配 [Linux 同步處理機制](https://hackmd.io/@sysprog/BksNlMFh1x)及 [Linux 核心設計: Synchronization](https://hackmd.io/@RinHizakura/rJhEpdyNw)

## TODO: 回顧教材和報告
> 研讀以下材料、紀錄問題和提出對應教材的改進
> * [並行程式設計教材修訂](https://hackmd.io/@sysprog/H1dCuDxQR)
> * [《Concurrency Primer》校訂和範例撰寫](https://hackmd.io/@sysprog/BkNqX71L0)

## [並行程式設計教材修訂](https://hackmd.io/@sysprog/H1dCuDxQR)

> 搭配 union 在組合語言的地方(第 13 行)雖然只有改 slock 的話 owner 會被更新 lockval(0) + (1 << TICKET_SHIFT)(4)。
>
> 然而 next 的值卻不被改變，因為原先 lockval 就是來自 slock 也就是 [next|owner] 。而現在雖然只改變 lockval 但因為等待 lock 的數量不會多到這個情況，所以會變動到的只有 owner。

[spinlock_types.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock_types.h#L9)

#define TICKET_SHIFT	16

被更新的是 next

------------------------------
        slock (32 bit)
------------------------------
next (16 bit) | owner (16 bit)
------------------------------
             1| TICKET_SHIFT
------------------------------

修改後的敘述

> 在這段組合語言中（第 13 行左右），透過 lockval + (1 << TICKET_SHIFT) 的操作，我們對 slock（32-bit 的 union 值）加上一個常數，這個常數剛好只會改變 next（高 16 bits），而不會改動 owner（低 16 bits）。因為 lockval 原本是從 slock 複製出來的，也就是 lockval = [next | owner]，加上 (1 << 16) 僅僅是把 next

### qspinlock

在超過三個 cpu 使用時（owner and successors）會退化成 MCS lock

==Q: where is the node->count used?==

/*
* Ensure that we increment the head node->count before initialising
* the actual node. If the compiler is kind enough to reorder these
* stores, then an IRQ could overwrite our assignments.
*/
barrier();

node->locked = 0;
node->next = NULL;
pv_init_node(node);

### [藉由 spinlock 的調整，改善多核處理器建立 TCP 連線效能](/BJv5HGD3m)

inet_unhash 解法為避免在別的處理器執行，其中的舉例為
> 避免這種情況的發生，例如藉由外部的機制或者工具，對行程和處理器進行綁定，從而避免行程在多個處理器間來回。

另一種可行方法：利用 `workqueue` 或 `smp_call_function_single` ，從 `sk->sk_hashcpu` 拿到當初插入時的 CPU，然後再安排一個工作到那顆 CPU 上去執行真正的 `inet_unhash`。

> 提出此一例子的原因為單純的概念講述讓我無法真正了解老師這句話的意思，有個實際例子可以將所學連結

### [從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/0WkZfkdtTfucKiV35wxRAA?view)

$$
P_k = \dfrac{\frac{1}{T_{arrive}^k(n-k)!}\prod_{i=0}^k (E+ic)}{\sum_{i=0}^{n}\frac{1}{T_{arrive}^i(n-i)!}\prod_{j=0}^i (E+jc)}
$$

公式錯誤，應為

$$
P_k = \dfrac{\frac{1}{T_{arrive}^k(n-k)!}\prod_{i=1}^k (E+ic)}{\sum_{i=0}^{n}\frac{1}{T_{arrive}^i(n-i)!}\prod_{j=1}^i (E+jc)}
$$

## TODO: 探討 MCS lock 和 qspinlock
> 比照[從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability)，設計數學分析 (機率統計/排隊理論) 來量化 Linux 核心的 qspinlock (建構於 MCS lock 之上)

### 討論 MCS lock

根據 [Non-scalable locks are dangerous](https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf)

其各穩定階段的機率為

$$
P_k = \dfrac{\frac{1}{T_{arrive}^k(n-k)!}\prod_{i=1}^k (E+ic)}{\sum_{i=0}^{n}\frac{1}{T_{arrive}^i(n-i)!}\prod_{j=1}^i (E+jc)}
$$

然而 MCS 消彌 CPU cache coherence，因此 service rate 就從 $s_k = \frac{1}{s+c \cdot k/2}$ 變成 $s_k = \frac{1}{s+c'}$ 其 $c'$ 為移交 lock 給下一個 CPU 所做的 cache coherence。

$$
P_k = \dfrac{\frac{1}{T_{arrive}^k(n-k)!}\prod_{i=1}^k (E+c')}{\sum_{i=0}^{n}\frac{1}{T_{arrive}^i(n-i)!}\prod_{j=1}^i (E+c')}
$$

也就是

$$
P_k = \dfrac{\lambda^k \cdot \frac{1}{(n-k)!}}{{\sum_{i=0}^{n} \lambda^i \frac{1}{(n-i)!}}}
$$

for $\lambda = \frac{E+c'}{T_{arrive}}$

如此一來，可以求出等待核心的期望值
$$
E[k] = \sum_{k=0}^{n} k \cdot P_k
$$

### 討論 qspinlock

qspinlock 結合 ticket spinlock 與 MCS lock 因此我們可以借用兩者機率合併的 conditional function 概念
$$
f(x) =
\begin{cases}
\frac{1}{s+c'} & \text{if } k > 3 \\
\frac{1}{s+c*k/2} & \text{if } k \le 3
\end{cases}
$$

然而因為上式直接把兩個機率分布直接合併切分，違反科摩哥洛夫第二公設（歸一化）：
> $P(\Omega) = 1$
> for Ω 為整個樣本空間

因此考慮單純的 ticket-like lock 被使用情形與 lock 退化成 MCS-like lock ，嘗試將兩者機率利用以上兩種情形的發生機率進行合併。

定義 $P_{fast}$ 為當 qspinlock 處於 ticket-like lock 狀態時的機率，而 $P_{queue}$ 為處於 MCS lock 狀態的機率。

$$
P^{qspinlock}_{k} = P_{fast} * P^{ticket}_{k} + P_{queue} * P^{MCS}_k
$$

然而，此式的意思為 qspinlock 進入到 ticket-like lock 的機率與進入到 MCS lock 的機率互斥，省略 qspinlock 的轉移機制（進入到 MCS lock 表示進入過 ticket-like lock，並因為等待鎖的人數過多，所以轉移成 MCS lock）。

鑑於此，最好的方法就是從[論文](https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf)模型利用條件函數與 Birth-Death Process 重新推導。

Arrival rate
$$
a_k = (n-k)/T_{arrive}
$$

Service rate
$$
s_k =
\begin{cases}
\frac{1}{s+c'} & \text{if } k > 3 \\
\frac{1}{s+c*k/2} & \text{if } k \le 3
\end{cases}
$$

當其 Markov model 其內狀態穩定時
$$
P_k \cdot s_k = P_{k-1} \cdot a_{k-1}
$$
故
$$
P_{k} = P_0 \cdot \prod\limits_{i=1}^{k} \frac{a_{i-1}}{s_i}
$$

其 $P_0$ 由 $\sum\limits_{k=0}^{\infty} P_k = 1$ 導出。然而 $P_k$ 的導出非常雜亂，因此先採用模擬的方法，透過改變參數，了解模型與 qspinlock 在不同程度的效果。

### 模型模擬

| 參數 | 意義 |
|------|-------------------------------|
| 𝑛 | CPU中的核數 |
| 𝑎 | 單核平均嘗試 acquire lock 間隔 |
| 𝑠 | critical section 的執行時間 |
| 𝑐 | 多核競爭造成的延遲增加率 |
| 𝑐′ | 鎖移交所需的 cache coherence 時間|

利用 [google colab](https://colab.research.google.com/drive/1CNgmsyu3AeeuThe5Zhib0ReZxQM4GRH7?usp=sharing)

當 critical section 只有幾個 cycles 且 CPU 要求進入 lock 的頻率低時

n = 200  # total number of cores
a = 50000.0  # average time between lock acquisitions
s = 100.0  # critical section time
c = 400.0
c_prime = 250.0



上兩圖分別為穩定狀態的機率分佈與論文提出的 Speedup 衡量方法。前者可以看到 100 核的機率分佈在前面下切時有小跳動，表現出 qspinlock 切換模式的特性，而此參數所得出的期望值為 $2.27<3$，在 qspinlock 的表現只有 ticket-like lock，其在 Speedup 的表現也如論文相似，後者隨著核數上升在 140 到達了飽和，也是 qspinlock 的瓶頸 - 服務速度。

當 critical section 較大且 CPU 要求進入 lock 的頻率低時

n = 200  # total number of cores
a = 50000.0  # average time between lock acquisitions
s = 500.0  # critical section time
c = 400.0
c_prime = 250.0



若將執行 critical section 時間拉長，如前圖其期望值會落在 $33.34>3$， qspinlock 會在超過 3 時會轉移成 MCS lock，也就是說，一個長的 critical section 會倒置 qpinlock 高機率轉移成 MCS lock ，另外，下面那張圖與第一個案例對比，發現其飽和臨界點與上限變小了。

同樣的，若以服務速度來看，如果提昇到達的速度（a 變小），也同樣會造成飽和臨界點與上限變小。

從模型模擬結果可以觀察到，qspinlock 在處理器核數增加初期展現出接近 ticket lock 的初期線性 speedup 表現，代表在低至中度競爭下，進入的 ticket-like fast path 能有效分散鎖的競爭壓力，讓每個新增的處理器核都能帶來近似的效能提升。
隨著處理器核數進一步增加，模擬結果顯示 speedup 並不會持續線性成長，而是趨於飽和。這種飽和行為反映出在高競爭情況下，qspinlock 進入 MCS-like queueing phase，藉由排隊來減少 cache bouncing 與 active spinning 的開銷，使得效能不再上升，但也沒有顯著下降。

總結來說，qspinlock 模型呈現出：
* 初期與 ticket lock 類似的線性 speedup
* 高負載下轉為穩定但飽和的 throughput
* 成功避免了傳統 spinlock 在大量處理器核數下的效能崩潰
* 這也驗證了 qspinlock 設計上的雙重目標：在輕載時快速、在重載時穩定。

## TODO: 探討 Futex 的應用和驗證
> 參照 [Futex 驗證和評估](https://hackmd.io/@sysprog/B1PfD838R)和[實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-mutex)，重現相關實驗、理解 futex 的驗證，並探討以 futex 為基礎的 lock 提升方案