# 作業系統 CH6 Process Synchronization
###### tags: `作業系統 Operating System`

當共享的資料同時被不同 Process / threads 存取時，因為執行順序的不確定性，很容易發生 data inconsistency 的狀況，所以需要額外的機制來確保程式的正確性，也就是 Synchronization
以下為常見的 Consumer & Producer Problem
除了 Buffer 之外， Counter 也是 share variable，要注意的是 `counter++` 及 `counter--` 在 instruction level 其實有三道指令，以 `counter++` 為例，要先將 counter 從記憶體中移到 register，加上 1 之後，再存回記憶體。由於 `context switch`, `Preemptive scheduling` 等因素， 這些指令可能不是一次執行完成，導致執行結果不符合預期

move ax, counter
add ax, 1
move counter, ax


## Race Condition
當多個 Processes 同時存取及操作 shared data 時，最終的值取決於最後一個完成執行的 Process，這個現象稱為 Race Condition
- 在 single-processor machine 中，我們可以 disable interrupt 或著使用 Non-preemptive scheduling 來達成同步，但在 User Program 中不可能使用，會影響整個系統的運作
- 通常將可能產生 Race Condition 的區域稱作 `Critical Section`

## Critical-Section Problem
- 目的：建立 Processes 之間合作的 protocol
- Problem description
- N 個 Processes 競爭使用 shared data
- 每一個 Process 存取 shared data 的 code segment 我們稱為 critical section
- 若我們確保當一個 Process 執行 critical section 時，其他 Processes 不得執行 critical section，稱之為 `mutually exclusive`，是比較暴力的解法
- 一般常見 critical section 的架構如下

## Critical-Section Requirements
1. Mutual Exclusion：
當一個 Process 執行 critical section 時，其他 Processes 不得執行 critical section
2. Progress：
若沒有 Process 在執行 critical section，且有某些 Processes 希望進入它的 critical section，則 Process 不得在未定義的情況下被推遲，一定要進的去
3. Bounded Waiting：
Process 等待進入 critical section 的期限必須受到限制，不可一直排隊等待

## Critical-Section Solution & Synchronization
### Algorithm for Two Processes
我們先以兩個 Processes 的簡單例子做講解
- 只有兩個 Process P0 & P1
- 共享變數
- int turn
- turn = i --> Pi 可進入 critical section

以上的程式碼其實並不完美，這個程式要能順利運作的前提是，兩個 Process 必須輪流執行，但 while loop，並不保證執行的順序，很有可能 Process 0 執行完一次，又想進入 critical section，但 Process 1 還沒執行到 turn = 0 這一行，P0 就會卡在 while loop ，不符合 progress

### Peterson's Solution for Two Processes
為了解決上述 Progress 的問題，我們引入另一個變數 `flag` ，用來表示 Process 是否想要進入 critical section 中，當 `flag[i] = True` 的時候，代表 Pi 已經準備好要進入 critical section，`turn = j` 代表把 key 交給別人。所以 while 條件式 `flag[j] && turn==j` 的意義為檢查其他 Process 是否可進入 critical section，確認沒有其他 Process 要進入 critical section 後，自己再進入 critical section。
要注意如果 `turn = j` 不是把 token 交給別人而是搶過來用，當某個 Process 先進入 critical section，輪到另一個 Process 時也可以 break while 迴圈，違反了 mutual exclusion

簡單的證明 Peterson's Solution
- Mutual exclusion : turn 不可能同時為 0 或 1，因此不可能同時進入 critical section
- Progress :
- 若 P1 尚未準備好 --> flag[1] = False --> P0 可以進入
- 若兩者都準備好 --> flag[0] = flag[1] = True
- 若 turn = 0 則 P0 進入，否則 P1 進入
- 以上兩種狀況，Process 都可以順利進入 critical section
- Bounded waiting :
- 若 P1 離開 critical section --> flag[1] = False --> P0 可以進入
- 若 P1 離開 critical section 後，繼續執行 while loop --> flag[1] = True --> turn = 0 (覆寫 P0 原先的 turn = 1) --> P0 可以進入
- 以上兩種狀況，P1 進入後接著進去的一定是 P0，符合 Bounded Waiting 的要求

### Producer/Consumer Problem
情況一：我們將所有程式碼都放入 critical section，如果 consumer 先 call，因為 buffer 是空的，所以 consumer 會卡在 while 迴圈 ; 這時再 call producer ，因為 consumer 已經在 critical section 裡頭， producer 無法進入導致 ==deadlock==

情況二：我們只將可能產生 race condition 的程式碼放進 critical section，雖然執行結果正確，但如果某一個 Process 進入 critical section 其他 Process 進不去，可能導致無謂的 context switch 降低效率

## Bakery Algorithm (n processes)
- 在進入 critical section 之前，每一個 Process 會抽號碼牌
- 號碼牌數字最小的先進入 critical section (注意可能有相同的號碼牌，如下方程式碼以 `max` 實作，而 `max` 指令其實有好幾行)
- 號碼牌數字的產生一定是 non-decreasing order; i.e. 1,2,3,3,4,5,5,5...
- 若兩個 Process Pi & Pj 有相同的號碼牌，則 PID 小的先進入
- `choosing[i]` 為是否正在抽號碼牌的 flag，在與其他 Process j 比較之前，我們必須等待 Process j 抽完號碼牌。考慮一個狀況， Process j 比 i 晚抽完號碼牌，但號碼與 i 一樣大，又 j 的 PID 比 i 小，所以 Process j 應該要先執行 ; 如果在 j 還沒抽號碼牌之前就進行比較，此時 num[j] = 0，程式會以為 j 不要執行，反而先執行 i，當 j 抽完號碼牌之後發現數字與 i 相同，因此也可以進入 critical section，但這時 i 已經在裡頭，導致 deadlock。


## Pthread Lock/Mutex Routines


## Condition Variables (CV)
- Condition Variables 代表一個條件，符合該條件時可以觸發 thread 執行某些動作
- 三種 CV 的操作
- wait() : 直到其他 thread 呼叫 signal()/broadcast()，thread 處於等待狀態
- signal() : 喚醒一個等待中的 thread
- broadcast() : 喚醒所有等待中的 thread
- 在 Pthread 中，CV type 為 `pthread_cond_t`
- 使用 `pthread_cond_init()` 來初始化
- `pthread_cond_wait (&theCV, &somelock)`
- `pthread_cond_signal (&theCV)`
- `pthread_cond_broadcast (&theCV)`

上圖執行順序如下：
1. action() 進入 CS，呼叫 `thread_cond_wait` 並==釋放 lock==
2. counter() 取得 lock 進入 CS
3. counter() 呼叫 `singal()` ，action() 被喚醒，注意這時候 action() 是沒有 lock 的
4. counter() 釋放 lock
5. action() 取得 lock 並執行函式

### ThreadPool Implementation
一次創建一定數量的 threads，讓系統不用一直增刪 threads，並且讓系統可以有效控制 threads 的數量，避免過多的 context switch 反而降低效率，達到效能最佳化。

創建 threads 後，為了讓 threads 執行不同的 function，會建立一個 `threadpool_task_t` 的結構體，存放函式及對應參數的指標，因此 threads 在經過 while loop 被喚醒之後，執行目前看到 `threadpool_task_t` 的函式，等於處理了一個 request，處理完成後進入 wait 狀態，等待下次被喚醒。而 threads 要如何知道被喚醒，其中一個方式是透過 Condition Variable 判斷
以下程式碼為一個簡單的範例：
1. 創建 threads pool 以及 task 的 queue
2. thread 執行 while loop 處於 wait 狀態
3. 若 thread 被喚醒則離開 while loop，並執行 queue 中 pool->head 的函式
4. 執行後 pool->head 加 1，再判斷該值是否等於 `queue_size`，若相等表示已經執行到最後一個函式，將 `pool->head` 設為 0
5. 離開 critical section 執行任務

 

## Hardware Support
Critical Section Problem 的發生是因為 shared variable 的修正可能被打斷，若某些指令我們可以一行完成，就可以避免 race condition 的問題。前面都是在說軟體上的支援，若硬體可以將指令變成 `atomic instructions` ，就沒有同步的問題
- atomic : 無法中斷執行的最小單元
- 例如 : `TestAndSet(var)`, `Swap(a,b)`

### Atomic Test And Set()
注意以下程式碼不符合 Bounded waiting

### Atomic Swap()
先 call Swap 的取得進入 critical section 的權力，執行完成後將 token 還給 lock。注意以下程式碼不符合 Bounded waiting

## Semaphores
- `Samaphores` 是一個通用的同步處理工具，其紀錄某個資源有多少 units 可以去使用
- 若 # of record = 1 --> binary semaphore, 但其實用 mutex lock 就好
- 若 # of record > 1 --> counting semaphore
- 利用兩個 atomic operations `wait` & `signal` 來存取 (注意與 critical section 的 wait & signal 不同)
- 簡單的 Spinlock 以 semaphore 實作
- Semaphore 為 POSIX 標準庫之一，不屬於 Pthread，所以使用上不限於 thread ，也可以用於 Process

### Non-busy waiting Implementation
Busy waiting (SpinLock) 因為 while loop，執行效率沒有被最佳化，所以相對 busy waiting 就有 non-busy waiting 的實作方式，但 system call 要考慮 context switch、re-scheduing 的影響，成本比 while 來得高。一般來說，等待時間很短的，我們會用 busy waiting，反之則使用 non-busy waiting
- Semaphore 為一個有 `queue` 的結構體，包含 Semaphore 的值以及有哪些 Processes 等待被執行
- wait() & signal()
- 使用 system calls: sleep() & wakeup()
- 一樣必須為 `atomic` 的操作
- 必須先進行 `value--(++)` 操作，避免進入 if 區域後被 sleep 無法執行
- 由於 `value--(++)` 還有 queue 的 insert, delete 等，必須確保 `wait()` & `signal()` 為 atomic 操作
- single-processor : 透過 disable interrupts
- multi-processor :
- HW Support (e.g. Test-And-Set, Swap)
- SW Support (Peterson's solution, Bakery algorithm)
- Semaphore with Critical Section
- 將 `value--(++)` 以及 queue 的操作包進 critical section
- 因為 `sleep()` 及 `wakeup()` 為 system calls，無須擔心同步的問題， OS 會妥善處理，所以不用包進 critical section 中(也不該包進去)

### Cooperation Synchronization
- 有些情況不同 Process 間的執行順序很重要，考慮兩個 thread P1 & P2 分別執行 S1 & S2，S2 必須在 S1 完成後才可執行
- 實作方式 : 利用 shared variable `semaphore sync` ，以下程式碼確保 S1 一定先執行完成
- 更複雜的情況概念相同，由上述兩個 Processes 的例子做延伸

## Classical Synchronization Problems
常見的問題如下：
1. Bounded-Buffer (Producer-Consumer) Problem
2. Reader-Writers Problem
3. Dining-Philosopher Problem

### Reader-Writers Problem
- 標準在處理 I/O 會遇到的問題
- A set of shared data objects
- A group of processes
- reader processes (read shared objects)
- writer processes (update shared objects)
- writer process 對 shared object 有獨佔權
- 不同的種類
- first RW problem : 只要確定 writer 有 access 的獨佔權即可，不關心 reader 要等多久，或要做什麼事情。reader 取得 token 時，可以傳給其他 reader，可能造成 writer 一直被其他 reader 插隊，永遠拿不到 lock
- second RW problem : 不只要確定 writer 的 access 權限，另外當 writer ready 且 object 被釋放時，writer 的優先性必須高於 reader ，不可有新的 reader 進來插隊

#### First Reader-Writer Algorithm
- writer 為 binary semaphore
- Reader 共享一個 block
- `readcount` 計算有幾個人要讀
- 當 `readcount > 1` 時，代表已經有 reader 拿了 lock，所以這個 reader 也可以讀
- 當 `readcount = 1` 時，因為是第一個 reader，可能要等 writer 結束才可讀取
- 當 `readcount= 0` 代表最後一個讀的，讀完後要 signal writer
- `readcount` 為 shared variable，必須受到保護
- Writer可能會有 ==starvation problem== ，因為只要有 reader 在讀，其他 reader 都可以進入 critical section，造成 writer 一直在等待狀態

// mutual exclusion for write 
semaphore wrt=1
// mutual exclusion for readcount
semaphore mutex=1
int readcount=0;

// writer
Writer(){
    while(TRUE){
        wait(wrt);
        // Writer Code
        signal(wrt);
    }
}

// reader
Reader(){
    while(TRUE){
        wait(mutex);
        readcount++;
        if(readcount==1)
            wait(wrt);
        signal(mutex);
        
        // Reader Code

        wait(mutex);
        readcount--;
        if(readcount==0)
             signal(wrt);
        signal(mutex);
    }
}

### Dining-Philosopher Problem
- 5 個人坐在 5 張椅子上，且有 5 支筷子
- 每個人只會思考或是吃飯
- 思考時與剩下 4 個人沒有互動
- 每個人要用餐需要兩支筷子
- 一個人 1 次只能拿 1 支筷子
- 吃完飯後，將兩支筷子都放下
- 若每個人都拿其中一邊的筷子，就 deadlock 了
- starvation problem

## Monitor
雖然 semaphores 提供非常便利及有效的同步機制，但正確性主要是依賴 programmer
- 所有存取 shared data object 的 processes 都需確保 `wait()` & `signal()` 的執行順序及位置正確
- 但是人總有可能犯錯
- 可以將 Monitor 想成一個特殊 class (high level language construct)，每一個 Monitor 都有可能發生 race condition 的 local variable (對應下圖的 shared data) 需要保護，而要操作這些 var 必須透過 Monitor 的 method。
- Monitor 與 OO 最重要的差異為，Monitor 一次只有一個 thread 可以執行其 method。(但可以很多個 threads 同時 call 這個 method，只是會處於 inactive 狀態)
- monitor 利用 queue 做排程，確保一次只有一個 process 是 active 的，保護 shared data

### Monitor Condition Variables
- 為了允許 process 等待 monitor，需要宣告 condition variable，例如 `condition x, y;`
- condition variable 只能與 `wait()` 及 `signal()` 一起使用
- x.wait()
代表調用這個 operation 的 process 被閒置，直到其他 process 完成為止
- x.signal()
啟動一個等待中的 process，若沒有 process 處於等待狀態，則 `signal()` 操作沒有任何影響。與其相反，semaphore 的 `signal()` 一定會改變 semaphore 的狀態 (`wait` 把 counter 減 1; `signal` 把 counter 加 1)
- 在 monitor 當中，condition variable 不是 counter 而是一個佇列，所以 x.wait() 類似把 process 放到 waiting queue (enqueue)，而 signal 則是在 dequeue，所以如果 queue 是空的，signal 就沒有任何作用
- Monitor 可以有很多個 threads 存在，但一次只有一個 active

### Dining Philosophers Example
#### monitor type
- 建立三個狀態 `thinking`, `hungry` & `eating`
- 建立 shared variable `self[5]`，存放每個人的狀態
- P.S. 可以用 shared variable 都還算好解決，難解的是無法得知他人狀態的問題
- 定義 4 個 method

monitor dp {
    enum {thinking, hungry, eating} state[5]; //current state
    condition self[5]; //delay eating if can’t obtain chopsticks
    void pickup(int i) // pickup chopsticks
    void putdown(int i) // putdown chopsticks
    void test(int i) // try to eat
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

- void pickup(int i)
- 將狀態設為 `hungry`，代表要吃東西了
- 測試拿筷子後是否可以吃
- 若狀態沒有改變，表示測試失敗，把自己放到 wating queue

    void pickup(int i) {                
    state[i] = hungry;                  
    test(i); // try to eat               
    if (state[i] != eating)                  
        // wait to eat                   
        self[i].wait();             
    }      

- void putdown(int i)
- 吃完了將狀態改為 `thinking`
- 告知左右兩邊進行測試，看有沒有辦法吃

    void putdown(int i) {
    state[i] = thinking;
    // check if neighbors are waiting to eat
    test((i+4) % 5); 
    test((i+1) % 5);
    }

- void test(int i)
- 若左右兩邊的人都沒在吃，代表左右兩邊手上都沒筷子，還要確認自己是否想吃東西
- 都符合的話，將狀態改為 `eating` 並喚醒 thread/process

    // try to let Pi eat (if it is hungry)
    void test(int i) {
        if ( (state[(i + 4) % 5] != eating) &&(state[(i + 1) % 5] != eating) 
            && (state[i] == hungry) ) {
        //No neighbors are eating and Pi is hungry
            state[i] = eating;
            self[i].signal(); // If Pi is suspended, resume it
                              // If Pi is not suspended, no effect
        }
    } 

### Atomic Transactions
- Transactions : 執行一個單一邏輯函式的指令集合
- Atomic Transactions : 執行單一邏輯函式，一次全部執行，或完全不執行
- Atomic Transactions 在 database system 系統中是個非常重要的議題

#### File I/O Example
- Transactions 為一系列讀寫的動作
- 透過 `commit` 以及 `abort` 來確認動作完成
- transaction 成功 : commit --> terminated
- transaction 失敗 : abort --> roll back
- abort 的 transaction 必須回溯，取消所有做過的改變，這個性質的確保為 system 的責任

#### Log-Based Recovery
- 紀錄所有 transaction 的步驟及做過的改變
- Stable storage : 絕對不會丟失儲存的資料
- Write-ahead logging : 基本上 log 紀錄需包含以下資訊
- Transaction name
- Data item name
- Old & new values
- Special events: (Ti starts), (Ti commits)
- Log 用來重建被改動資料的原始狀態
- 利用 `undo(Ti)` 及 `redo(Ti)` 來復原資料
-
#### Checkpoints
Logging 的問題是沒有時間觀念，從系統打開到系統崩潰為止一直紀錄，因此需要 checkpoint 留存系統還原點 (例如強制關機時 word 沒有存檔，重開後系統會問你是否要還原至關機瞬間的狀態)，從 checkpoint 來做 roll back 的動作
- 當 failure 發生時，必須查看 log 來確認哪些 transactions 要重新執行
- 搜尋的過程很花時間
- 並非所有 transactions 都需要重新執行
- 利用 checkpoints 來減少上述 overhead
- 輸出所有 log 紀錄來達到 stable storage
- 輸出所有被更動的資料來達到 stable storage
- 輸出紀錄 `checkpoint` 的 log 來達到 stable storage

## Refernece
1. [清大開放課程 - 作業系統](https://www.youtube.com/watch?v=aK0_PBLWCAM&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV&index=38)
2. [Operating System Concept 9th edition](https://www.os-book.com/OS9/slide-dir/index.html)