# 並行程式的潛在問題(二)


並行/多執行緒程式往往會碰上同步問題 (Synchronization)，在前一篇文章中介紹了什麼是 Race condition 以及 Critical sections ，並且利用互斥鎖將 CS 鎖住。不過，同步問題的解法可不止一個，本篇將探討廣泛應用在 Linux kernel 的 Spinlock 。

## Spinlock 介紹

Spinlock 中文稱做自旋鎖，透過名稱我們就能大概大概猜到 Spinlock 的功用。與 Mutex 相同， Spinlock 可以用來保護 Critical section ，如果執行緒沒有獲取鎖，則會進入迴圈直到獲得上鎖的資格，因此叫做自旋鎖。

### 原子操作

原子操作可以確保一個操作在完成前不會被其他操作打斷，以 RISC-V 為例，它提供了 RV32A Instruction set ，該指令集都是原子操作 (Atomic)。

為了避免在同時間有多個 Spinlock 對相同的記憶體做存取，在 Spinlock 實現上會使用到原子操作以確保正確上鎖。
> 其實不單單是 Spinlock ，互斥鎖在實現上同樣需要 Atomic opration 。
### 用 C 語言打造簡單的 Spinlock
考慮以下程式碼:

typedef struct spinlock{
    volatile uint lock;
} spinlock_t;
void lock(spinlock_t *lock){
    while(xchg(lock−>lock, 1) != 0);
}
void unlock(spinlock_t *lock){
    lock->lock = 0;
}

透過範例程式碼，可以注意到幾點:
- lock 的 `volatile` 關鍵字
使用 `volatile` 關鍵字會讓編譯器知道該變數可能會在不可預期的情況下被存取，所以不要將該變數的指令做優化以避免將結果存在 Register 中，而是直接寫進記憶體。
- lock 函式
[`xchg(a,b)`](https://zh.m.wikibooks.org/zh-hant/X86%E7%B5%84%E5%90%88%E8%AA%9E%E8%A8%80/%E5%9F%BA%E6%9C%AC%E6%8C%87%E4%BB%A4%E9%9B%86/IA32%E6%8C%87%E4%BB%A4:xchg) 可以將 a, b 兩個變數的內容對調，並且該函式為原子操作，當 lock 值不為 0 時，執行緒便會不停的自旋等待，直到 lock 為 0 (也就是可供上鎖)為止。
- unlock 函式
由於同時間只會有一個執行緒獲得鎖，所以在解鎖時不怕會有搶占存取的問題。也因為這樣，範例就沒有使用原子操作了。

## Spinlock 的演進
從剛剛的介紹可以得知，執行緒是否能獲取 Spinlock 與投入順序並沒有太大的關係，而是取決於哪一個處理器核心最快查覺到 spinlock 狀態的變化，更精確的說法是，哪個處理器核心的 Cache 更快與主記憶體內容同步。
> 可參考處理器的快取[策略](https://zhuanlan.zhihu.com/p/33445834)。

### Wild spinlock

Wild spinlock 類似於我們剛剛實作的簡易自旋鎖:

typedef struct spinlock{
    volatile uint lock;
} spinlock_t;
void lock(spinlock_t *lock){
    while(xchg(lock−>lock, 1) != 0);
}
void unlock(spinlock_t *lock){
    lock->lock = 0;
}

不過，這種作法是有明顯的缺陷的，在前面筆者有提到:
> 執行緒是否能獲取 Spinlock 與投入順序並沒有太大的關係，而是取決於哪一個處理器核心最快查覺到 spinlock 狀態的變化，更精確的說法是，哪個處理器核心的 Cache 更快與主記憶體內容同步。

假設在 8 核心處理器中，如果 8 個核心都希望搶占同一個 lock ，便會有些核心始終搶不到 lock ，造成 CPU 空轉的現象(瞎忙)。
### Ticket spinlock

為了解決這個問題，科學家為 spinlock 添增了搶票的機制，就好比我們去郵局需要領號碼牌。這樣一來，我們就可以確保每個 CPU 都可以獲取到鎖。

struct spinlock {
        unsigned short owner;
        unsigned short next;
};


void spin_lock(struct spinlock *lock)
{
        unsigned short next = xadd(&lock->next, 1);
        while (lock->owner != next);
}


void spin_unlock(struct spinlock *lock)
{
        lock->owner++;
}

> 範例程式碼取自 Ref[3] 。

其中， `xadd(a ,b)` 也是屬於 x86 的原子操作，它會返回 a 值並將 a + b 的結果寫回記憶體。
當 Owner 等於 `spin_lock()` 中 next 的值時，也就代表號碼牌叫到該執行緒了，這時候，該執行緒就可以跳出迴圈並進入到 CS ，等到結束執行 CS 後，在將 lock 的擁有者交給下一個執行緒。

### Ticket spinlock 的效能問題

假設現在有 4 核心的處理器，並且每個核心的執行緒都想要存取 Spinlock ，這時候，概念有點像是:
1. CPU0 從主記憶體存取 spinlock 到 Cache，並且獲得 lock 的所有權。
2. CPU0 會將 next 值更新到主記憶體中。
3. CPU1 從主記憶體存取 spinlock 到 Cache。
4. CPU1 Invalid CPU0 快取的 Spinlock 並更新 Next 的值，隨即發現 `next!=owner` ，所以進行等待。
5. CPU2 從主記憶體存取 spinlock 到 Cache。
6. CPU2 Invalid CPU1 快取的 Spinlock 並更新 Next 的值，隨即發現 `next!=owner` ，所以進行等待。
7. CPU3 從主記憶體存取 spinlock 到 Cache。
8. CPU3 Invalid CPU2 快取的 Spinlock 並更新 Next 的值，隨即發現 `next!=owner` ，所以進行等待。
9. 就在此時， CPU0 釋放了 Lock ，重新 Cache 鎖並且更新 owner 的值並且 Invalid 所有其他 CPU 快取的 Spinlock 。
10. CPU1 發現 Cache 的 `lock->owner` 失效了，重新進行了 Cache 並獲得鎖 (`next == lock->owner`)。
11. 以此類推...

> 貼心提醒: 每個執行緒所持有的 next 值之所以不用考慮 Cache 是否 Valid ，是因為在第一次嘗試 lock 時，我們就已經複製一份 next 的值到屬於 Thread 自己的 Stack 囉!

透過上面的解說可以發現: 當搶佔鎖的執行緒一多，就會造成 Cache 被反覆的更新。這樣不止會浪費通道頻寬，更會增加存取速度的延遲。
也因為這樣，電腦科學家又設計了其他 Spinlock 試圖解決這些問題。
### MCS spinlock

為了避免 Cache 被反覆的更新，電腦科學家提出了 MCS spinlock ，其設計理念是讓每一個 CPU 各自持有一個 spinlock ，每個獨立核心只需要觀察和維護各自的 lock 即可。

參考 [lwn.net](https://lwn.net/Articles/590243/) ， MCS Lock 的結構如下方所示:

struct mcs_spinlock {
	struct mcs_spinlock *next;
	int locked; /* 1 if lock acquired */
    };

上面提到每個 CPU 都會持有一份 spinlock ，不只如此， MCS Spinlock 還會有一個 Main lock 做為這個資料結構的 head 。
#### Main lock 的初始狀態
當 Main lock 被初始化時，其狀態如下圖:
#### CPU 獲取鎖

當有 CPU 嘗試獲取鎖時， CPU 會建立一個屬於自己的 MCS spinlock ，然後與 Main lock 做原子操作，若 Main lock 的 next 為 Null (Main lock 指向 Null) 的話，代表目前沒有人在排隊，我們就可以讓 Main lock 指向 CPU 持有的 MCS spinlock 然後持有鎖，這邊的原子操作的概念為:

swap(main_lock, cpu_lock){
    ret = main_lock;
    &main_lock->next = cpu_lock;
    &main_lock->locked = &cpu_lock->locked;
    return ret;
}

經過原子交換， MCS spinlock 的狀態會變成這樣:
#### 當鎖已經被他人持有時

延續剛才的範例， CPU1 已經持有了 spinlock ，現在多了一個 CPU2 嘗試存取鎖。經過原子操作， Main lock 會指向 CPU2 持有的 lock :
不過，從 Main lock 的狀態可以看出目前 spinlock 已經被他人佔有 (`main_lock->next != null`)所以 CPU2 只能等待，這時會將 CPU1 的 MCS lock 指向 CPU2 所持有的 MCS lock :
#### 當鎖被釋放

當 CPU1 完成任務，會對 Main lock 做比較和交換，若 Main lock 指向自己，代表沒有其他人在排隊，便只要更新 Main lock 的 locked 值並讓 Main lock 指向 Null ，最後將 CPU1 持有的 MCS spinlock 釋放即可:
除了上述的狀況，如果 Main lock 指向的不是自己，那我們只要將 CPU2 的 locked 值改變，再釋放自身持有的 MCS spinlock :
> MCS spinlock 是由 qspinlock 演變而來，有興趣的話可以參考[ spinlock 前世今生](https://zhuanlan.zhihu.com/p/133445693)一文。
## Spinlock v.s. Mutex
既然兩者都是用來將 CS 鎖住，為何還需要這兩個鎖呢?我們可以從其設計思維與運作方法了解這兩個鎖分別適用在哪些場景。
### Busy-waiting
> 在軟體工程中，忙碌等待是一種以行程反覆檢查一個條件是否為真為根本的技術，條件可能為鍵盤輸入或某個鎖是否可用。忙碌等待也可以用來產生一個任意的時間延遲，若系統沒有提供生成特定時間長度的方法，則需要用到忙碌等待。不同的電腦處理器速度差異很大，特別是一些處理器設計為可能根據外部因素動態調整速率。
> -- 維基百科

Spinlock 便是實踐 Busy-waiting 的鎖。
### Sleep-waiting

維基百科上並沒有對 Sleep-waiting 做介紹，所以筆者用更簡單的例子說明:
假設我們今天在湯X熊遊樂場，當 A 機台已經有兩個小朋友占用，如果以 Busy-waiting 的方法來看，我們會傻傻的站著等到小朋友玩夠了，才換我們上去玩。而 Sleep-waiting 則是讓我們先去做其他事情，等到小朋友玩夠了再通知我們過去玩。

Mutex lock 便是實踐 Sleep-waiting 的鎖。
## 總結

在介紹完 Spinlock 、 Mutex 與 Spinlock 的差別後，筆者再補充一下這兩個鎖適合應用在哪些場景:
- spinlock
spinlock 適合用來保護一段簡單的操作，設想現在我們在排隊的機台，每個人只能使用 5 秒，那根本不值得讓我們離開去做別的事情，待在原地排隊是更好的選擇。
- Mutex lock
相反的， Mutex lock 適合拿來保護一段區域，以排吃到飽餐廳為例，當輪到我們入場時，店家會使用電話告知。因此在這段等待的時間，我們就可以到商場周邊晃晃避免空等。

> BTW: 學習 spinlock 時不難發現在 Linux 中真的使用了大量的 Linked-list ，學習並行程式的同步問題之餘還能看到多個 Linked-list 的延伸，可以說是一石二鳥(嗎)。
## Reference
- [semaphore, mutex, spin lock](https://descent-incoming.blogspot.com/2015/11/semaphore-mutex-spin-lock.html)
- [获取自旋锁和禁止中断的时候为什么不能睡眠?](https://www.zhihu.com/question/28821201)
- [spinlock 前世今生](https://zhuanlan.zhihu.com/p/133445693)
- [Linux 核心設計: 多核處理器和 spinlock](https://hackmd.io/@sysprog/multicore-locks?type=view)
- [Spinlock & MCS Lock](https://ithelp.ithome.com.tw/articles/10213132)