Linux 核心專題: 同步處理機制

執行人: JeffBla

任務簡述

回顧並行和多執行緒程式設計教材，探究 Linux 核心的同步處理機制，理解其原理、重新實作，並量化分析。

搭配 Linux 同步處理機制及 Linux 核心設計: Synchronization

TODO: 回顧教材和報告

研讀以下材料、紀錄問題和提出對應教材的改進

• 並行程式設計教材修訂
• 《Concurrency Primer》校訂和範例撰寫

搭配 union 在組合語言的地方(第 13 行)雖然只有改 slock 的話 owner 會被更新 lockval(0) + (1 << TICKET_SHIFT)(4)。

然而 next 的值卻不被改變，因為原先 lockval 就是來自 slock 也就是 [next|owner] 。而現在雖然只改變 lockval 但因為等待 lock 的數量不會多到這個情況，所以會變動到的只有 owner。

spinlock_types.h

#define TICKET_SHIFT	16

被更新的是 next

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

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 連線效能

inet_unhash 解法為避免在別的處理器執行，其中的舉例為

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

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

從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

$$P_k={\displaystyle \frac{\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={\displaystyle \frac{\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 可擴展能力議題，設計數學分析 (機率統計/排隊理論) 來量化 Linux 核心的 qspinlock (建構於 MCS lock 之上)

討論 MCS

根據 Non-scalable locks are dangerous

其各穩定階段的機率為

$$P_k={\displaystyle \frac{\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^{\prime }}$ 其

$c^{\prime }$ 為移交 lock 給下一個，下個 CPU 所做的 cache coherence。

$$P_k={\displaystyle \frac{\frac{1}{T_{arrive}^k(n-k)!}\prod _{i=1}^k(E+c^{\prime })}{\sum _{i=0}^n\frac{1}{T_{arrive}^i(n-i)!}\prod _{j=1}^i(E+c^{\prime })}}$$

也就是

$$P_k={\displaystyle \frac{{\lambda }^k\cdot \frac{1}{(n-k)!}}{\sum _{i=0}^n{\lambda }^i\frac{1}{(n-i)!}}}$$

for

$\lambda =\frac{E+c^{\prime }}{T_{arrive}}$

如此一來，可以求出等待核心的期望值

$$E[k]=\sum _{k=0}^{n}k\cdot P_k$$

討論 qspinlock

qspinlock 結合 wild spinlock 與 MCS lock 因此其穩定階段的機率為將兩者機率合併的 conditional function

$$f(x)=\{\begin{array}{ll}{x}^2& \text{if }x\ge 0\\ -x& \text{if }x<0\end{array}$$

TODO: 探討 Futex 的應用和驗證

參照 Futex 驗證和評估和實作輕量級的 Mutex Lock，重現相關實驗、理解 futex 的驗證，並探討以 futex 為基礎的 lock 提升方案