Synchronization (Spinlock and Semaphores)
===
---

###### tags: `OS` `Linux`
這篇紀錄 kernel 有用到的同步機制 Spinlock & Semaphores
會寫這篇原因是在看 Kernel 時有看到，但有點忘記原理了
索性寫一篇筆記記著

---

**目錄:**
[TOC]

# 基本概念
每個機制被發明出來，都是為了解決某一個問題
那麼 Synchronization 的機制是為了解決什麼問題
以下簡單解釋這個問題

那 開始囉

---

現在的系統，是會切換執行的程序，以達到多工
但是實際想想這個過程，如果有兩個程序都是會改動同一個變數(若想了解怎麼達成這個操作，可以估狗 Processes Communication, C Thread)
假設是 i++ 這種操作
以下開始要想得很 "實際"，也就是要在組語 Level 思考

兩個程序都會
1. Load i 這個變數到 register e.g. rax
2. 對這個 register 做加 1
3. 再 restore 回 i 的記憶體位置

好，再想一下，程序是會切換的麻
如果執行過程如下:
1. 程序 A 執行第一步驟後，被切到程序B
2. B 直接執行完
3. 再換 A 執行完

這樣 i 就會是原本的值 +1 而已

再來想另外一種執行過程:
1. 程序 A 全部執行完
2. B 再全部執行完

這樣 i 就會是原本的值 +2

只是簡單的 i++
就會造成寫扣的人無法預測程式未來的走向

# spinlock
## 想像概念
中文翻譯成自旋鎖
為了解釋這東西的概念，我們延續基本概念中 i++ 的例子

兩個程序都會
1. Load i 這個變數到 register e.g. rax
2. 對這個 register 做加 1
3. 再 restore 回 i 的記憶體位置

的部分

假設若兩個程序都執行 i++ (記憶體位置上為同一個 i)
我們要的結果是 A 先執行完整個 i++ 1~3 步驟
再換 B 執行整個 i++ 1~3 步驟

好 前提講完了

接下來，想像一下有一個房間(Critical Section)
在裡面的人(程序)，可以執行 1~3 步驟

原本的問題就是，好幾個不同的人(程序)可以一起進入這個房間(Critical Section)執行 1~3 步驟
導致上述的執行順序問題

spinlock 就是這個房間房門的喇叭鎖

因為實際上，一個時間點上，只會有一個人(程序)在走動(執行) ~~如果只有一個CPU的話啦~~
所以不會有同時兩個人一起進入同一個房間的問題
=> 一次只會有一個人進房間

spinlock 的機制就是，先進到這個房間的人，會先鎖門，再執行要執行的 Code
如果程序被切換，第二個要進入這個房間的人就會被鎖在外面，幫QQ
在房間裡面的人執行完後，離開房間時解開了喇叭鎖，接下來就看其他在房間外面的人誰先進來鎖門囉

## Pseudo Code
講完譬喻法的部分看一下 Code

acquire() {
    while (!available); /* busy wait */
    available = false;
}
release() {
    available = true;
}

`available` 代表有沒有鎖門
`acquire` 做的事情就是，如果門鎖起來，就等，爆等，直到門解鎖了，再換我來鎖門
`release` 就是把門解鎖

然後 Program 要寫成類似這樣

do {
    acquire()
    // critical section
    release()
    // remainder section
} while (true); 

在進到**我不想跟其他 Process 一起執行的 Code**(也就是 Critical Section)前 call `acquire`
離開 Critical Section 時 call `release`

# Semaphores
看到這邊，應該對 "在 Process 會被切換的前提下，控制 Process 執行流程" 有一點概念了
這邊就直接來看 Code 了

## Pseudo Code

typedef struct{
    int value;
    struct process *list;
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        block(S); // add this process to S->list;
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0){
        wakeup(S); // remove a process P from S->list;
    }
} 

這三段看完後，可以知道一些特性

1. semaphore value:
semaphore 這個 struct 裡的欄位 value
需要初始化
目前的值是多少，就表示還有多少 Processes 能進 Section

下面舉個例子

    semaphore S = {
        .value = 5
    };

Process:

    do {
        wait(&S);
        // Section
        signal(&S);
    } while (TRUE);

這個例子中，執行在 Section 中的最多有 5 個 Processes

2. No busy waiting:
spinlock 用 white loop (busy waiting) 達到 `卡著 Process 不讓它進 Critical Section` 的作法
只是執行 white loop 也是在占用 CPU，這部分就顯得很浪費 CPU

而Semaphores 的實作是:

    若發現 Semaphore->value 小於 0:
        呼叫 Block() 將此 Process 掛進 Wait queue
    之後有 Process 離開 Section，call 了 signal():
        放一個在 Wait queue 的 Process 進 Section

不是用 busy waiting，而是直接 block 掉這個 Process
相比之下，這個機制就比較聰明