# 作業系統- Inter Process Communication

<style>
.red{
color:red;
}
</style>

## Outline
* [IPC方式](#IPC方式)
* [何謂 Race condition](#Race-Condition)
* [Critical Section Design ](#C.S.-設計方法)
* [Message Passing](#Message-Passing)

## IPC方式
* Shared Memory v.s. Message Passing

| 比較項目\方式 |Shared Memory | Message Passing |
| -------- | -------- | -------- |
| 資料量 | 多 | 少 |
| 通訊速度 | 快 | 慢(需System Call 讓 kernel 處理) |
|分散式系統 |不適合->無法擁有共同記憶體空間 (因設備分散各地) | 適合 |
| 互斥存取控制 | 需要 | 不需要 |
***
## Race Condition
**定義：多個Processes 同時存取及處理同一個資料，其結果可能因執行順序而有所不同**
* 例子
<img src="https://blog.cloudxlab.com/wp-content/uploads/2021/04/Screenshot-163-1.png" width="600" heigh="400" alt="race condition">

## How to solve race condition

1. Disable Interrupt
要存取變數時就不讓其他 Process Access
* 在Single Processor System很好用->可以完全避免其他process使用(因為只有一個CPU)
* 而Multiprocessor System較難實現->只關閉一顆CPU不一定能使其他Process不使用此共享變數，但全關processor效能又很差
**最大問題：風險太高(若允許user process 使用->萬一不enable 則全部東西都無法取得CPU的資源)故只開放給 Kernel developer使用**
2. Critical Section Design
將所有共享變數包在臨界區間中(意即一個program可以有很多個C.S.)
**設計主軸：如何設計一個好的進入C.S.的控制碼**
Process需要提出申請才能進入
## C.S.必須滿足的三大性質
1. Mutual Exclusion:
在同一時間點內只能有一個process在臨界區間中
2. Progress:
* 不想進入C.S. 之 Process 不能影響 or 阻擋 or 參與決策使別人不能進入C.S.
* 決策誰可以進入C.S.之時間是有限的，不能發生deadlock

3. Bounded Waiting:
N 個 processes 最多等 N - 1 次就要可以進入C.S.中->No starvation, 要公平對待

**也不能對Process的執行速度有任何假設**

### 當有Process正在C.S.中我們要如何讓其他 Process 卡住？
- Disable Interrupt
- Busy Waiting
使用loop，判斷條件符合就卡住自己
* 優點：若卡住時間<<兩次context switch 則效益比 disable interrupt 高
* 缺點：浪費系統效能(空轉:spinlock)

目前廣泛利用於multicore的系統中
- Non-Busy Waiting
Process go to sleep(waiting state)直到同步事件發生後才會來ready state->兩次context switch
優缺點與busy waiting 相反

## C.S. 設計方法
[1. Software -> Peterson solution](#Software-based-solution)
[2. Hardware supported](#Hardware-Supported)
[3. Semaphore](#Semaphore-號誌)
[4. Monitor](#Monitor)
- 架構圖
<img src = 'https://drive.google.com/uc?export=view&id=1iYW48LL6oUrc3d-L0Eja9_Y3tdDfy0G6' width="600" heigh="400" alt="CS Design architecture">

### Software based solution

#### Peterson Solution
靠純軟體方式來進入C.S.。
**但因為現今電腦架構，processor or compiler會調換指令順序已達最佳效率，所以有可能出錯**
eg. Pi

while (true){
    flag[i] == True;
    turn = j;
    while ( flag[j] && turn == j);
    
    /* critical section */
    
    flag[i] == False;
    
    /* remainder section */
    
}

eg. Pj

while (true){
    flag[j] == True;
    turn = i;
    while ( flag[i] && turn == i);
    
    /* critical section */
    
    flag[j] == False;
    
    /* remainder section */
    
}

註：先表示你想要，再將執行權(turn)交給對方->順序錯就炸了
所以 compiler 換到這兩行 peterson's solution 就沒用了
互換後就沒有mutual exclusion了

### Hardware Supported
- [Memory Barrier](#Memory-Barrier-又稱-memory-fence)
- [Hardware Instructions](#Hardware-Instructions)
- test&set()
- compare&swap() (CAS指令)
- [Atomic Variables](#Atomic-Variables)

#### Memory Barrier 又稱 memory fence
因為資料被改動時不一定所有 processor 都知道，所以讓所有 processor 都知道的話就不會有 race condition
若此指令被執行->系統將確保所有load store都要按照順序執行
解決亂序執行的問題(out-of-order)
又因為此是一個low level operations 故只提供kernel developer使用，application 開發使用者無法使用
#### Hardware Instructions
- test&set():傳回參數舊值、將值改為True
**特別注意，此為硬體指令，只是利用高階語言模擬幫助理解**

boolean test&set(boolean *target){
    boolean ret = *target;
    *target = True;
    return ret; // return 舊值
}

但須特別留意，以下此種方法是沒有滿足C.S.的設計條件的

//沒有滿足bounded waiting的test&set
boolean lock = false; //共享變數宣告

while True{
    while (test&set(&lock)); //若第一個搶到 則return False跳出迴圈 進入C.S.
    
    /* C.S. */
    
    lock = false;
    
    /*R.S. */
    
}

問題出在哪？
等於是把鑰匙(lock)丟在地上看誰先搶到誰就可以進來C.S.
-->解法就是：把要進來的人排隊，即新增一個可以記錄排隊的資料結構

//滿足bounded waiting的test&set
//共享變數
boolean lock = false; 
boolean waiting[0...n-1]; //initial = False

//區域變數
lock = False;
int j; 

// Pi code //
while True{
    waiting[i] = True; //Pi想進
    key = True;
    while (waiting[i] && key){
        key = test&set(&lock); // 若是第一個 則取得false lock -> 跳出迴圈到C.S.
    }
    waiting[i] = False; //不用等了就是你
    
    /* C.S. */
    
    j = (j+1) % n // n為總process數。circular linked list的概念
    while ((j != i ) && !waiting[j]) //遍歷一圈
        j = (j+1) % n
    if (j == i)
        lock = False; //代表沒人想進去，鑰匙丟地上
    else
        waiting[j] = False; //幫Pj解除spinlock
    
    /*R.S. */
    
}

<span class = 'red'>若今移除 C.S. 之後的waiting[i] = False敘述將發生什麼 error ?</span>

-> [*Progress*](#C.S.必須滿足的三大性質) 中的 (1) Pj 不想進入 C.S.但被指定進 (2) 而Pj進入後使 lock = True
造成 deadlock 未來沒有 Process 可以進
假設情況：在 Waiting queue 中 僅 Pi & Pj 想進入 C.S.而 Pi優先執行進入 C.S. 然而在 Pi 完成後並沒有將自身的 waiting[i] 設為False 由 Pj 接續進入 C.S. 待執行完後退出 C.S. 發現 Pi 之 waiting[i] = True 則讓 Pi 進入 C.S.(但實際上 Pi 並沒有要進)
就發生 **不想進去卻進去** **且不讓別人進** 的情況

- compare&set():
**傳回參數舊值、確定*value與expected相同->value = new_value**
**特別注意，此為硬體指令，只是利用高階語言模擬幫助理解**

int CAS(int *value, int expected, int new_value){
    int temp = *value;
    if(*value == expected){ // 與test&set不一樣的地方：要看是不是expected
        *value = new_value;
    }
    return temp; // 回傳舊值
}

實際用於C.S.之實例

// 此範例一樣未符合bounded waiting 之特性->why?一樣鑰匙掛空中誰搶到是誰的
int lock = 0; // 共享變數，如同test&set中的boolean lock = Fasle;

while (True){
    while(CAS(&lock, 0, 1)!= 0); //若lock原先為0->return 0離開迴圈但把它變成1
    
    /* C.S. */
    
    lock = 0;
    
    /* R.S. */
    
}

e.g. 執行流程解釋：
T0 : int lock = 0 // initialize
T1 : Pi拿到CPU執行進入區code，先執行 CAS(&lock, 0, 1) 執行後傳回0，跳出spinlock前往C.S.
T2 : Pj想進 C.S. 則執行 CAS(&lock, 0, 1) 但執行後回傳1，則卡在spinlock中直到 Pi 離開 C.S.
T3 : Pk, Pl, Pm 也想進，但如果依照搶到 CPU 順序會使 bounded waiting 被打破 ->因為可能Pj搶不到，餓死。

**解決方法：建立一個 list 去存類似順序的東西，用circular linked list 去遍歷**

// 有符合 bounded waiting 性質的CAS

//共享變數設置
int lock = 0;
boolean waiting[0...n-1] = False

//區域變數(每個 process 獨自擁有)
int key, j;

while (True){
    waiting[i] = True;
    key = 1;
    
    while(waiting[i] && key == 1){
        key = CAS(&lock, 0, 1) // 若沒人在C.S.則value = expected ->return 0跳出spinlock
    }
    waiting[i] = False; //不用等直接進 C.S.
    
    /* C.S. */
    
    j = (i + 1) % n;
    while((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = 0;
    else
        waiting[j] = False;
        
    /* R.S. */
    
}

#### Atomic Variables
> atomic 意即不可分割 ->代表這些變數在做存取讀取修正都必須一起完成

故在上述 test&set() 及 CAS() 都有使用到的共享變數均須使用 Atomic Variables 去做宣告
->才能實施真正意義的mutual exclusion
**<span class = "red">(本身指令並無提供互斥的機制，只是提供一種工具來設計解決 C.S. 問題)**</span>
使用例子:共享變數
雖然有 Atomic Variables 的協助，但還是不能完全解決race condition

### Mutex lock
即透過一個 boolean variable available去指示 lock 是否 available
也提供兩個 atomic operations:
- acquire() : 取得 lock // 進入 C.S.必須先 acquire
- release() : 釋放 lock // 離開 C.S. 必須 release

// 二元表 lock 值僅能為 0 or 1
故無法統計出有多少 Process 卡在裏面(也可以使用後面定義的 wait()以及 signal())
至於 acquire() ＆ release()要怎麼製作才能保證 atomic 呢？
->用硬體指令 e.g. CAS 來製作 mutex lock

// 此地使用 spinlock 求解
boolean Available = True;
    
Acquire(){
    while (! Available); // 無法 available 時 spinlock
    available = False;
    }
    
Release(){
    available = True; // 將 available 打開供其他 process 使用
    }

若要使用 CAS 則將 spinlock 裡的判斷式改成 (CAS(available, 0, 1)!= 0) 即可
### Semaphore 號誌
除了 Semaphore OS 還提供 mutex lock 來達到互斥存取(均屬 system call )
原因：hardware-based 太複雜去使用，且無法提供給開發者使用
而 mutex lock 類似一種二元號誌( binary semaphore )

#### Semaphore
Semaphore 是一種方便的工具讓我們進行互斥存取，但也有很多誤用問題需討論
- 定義：semaphore是一個整數變數，除了設定初值以外，只能透過兩個 atomic operations 來存取

Wait(S){
    while (S<=0); // 卡在這
    S--; //消耗一次
    }

Signal(S){
    S++; //相當於喚醒 給他補充一次
    }

以上均 based on atomic operations 否則會 race condition

    Semaphore mutex = 1 // 1:初值

誤用情形：
1. wait() signal() 順序顛倒 ->違反互斥
2. 一直使用 wait() 則會使quota用完 -> deadlock
3. 多個 semaphore 使用容易順序安排不當 -> 互斥及 deadlock 都會炸

使用一個經典同步問題來做範例 － Reader and Writer Problem
但又此問題有兩種類別
1. First 對 reader 有利
2. Second 對 writer 有利
因兩種分析方式雷同 此地挑第一型作討論
#### 第一型之 Reader and Writer
說明：
有一組資料被很多 Reader and Writer 所共享 而分成兩種類型的process
- Reader 僅 read 文件 不會進行 update
- Writer 會進行 read and write

所以 Reader 與 Reader 間可以同時進行，但 Reader and Writer 需要互斥存取，當然 Writer and Writer 之間也要
而 First class 中沒有 reader 會需要一直等 writer -> Writer 會 starvation

// 初值設定
Semaphore rw_mutex= 1 ,mutex = 1; //rw 給 rw & ww 互斥條件滿足 mutex為 read_count的互斥存取控制
int read_count = 0 // 統計reader個數 reader來++ 反之--

// Writer Process Code
Writer(){
    while(True){
        wait(rw_mutex);
    
        /* writing */
        
        signal(rw_mutex);
    }
}

// Reader Process Code
Reader(){
    while(True){
        wait(mutex); // 變更read_count必要步驟
        read_count++;
        if (read_count == 1) wait(rw_mutex) // 你是第一個reader 偵測有無writer正在寫 有的話等他 沒有的話就換你去讀且阻擋writer
        signal(mutex); 
        
        /* reading */
    
        wait(mutex);
        read_count--;
        if (read_count == 0) signal(rw_mutex); // 確定沒有reader 要讀取 就放writer 進來
        signal(mutex)
    }    
}

**先前曾經提及的二元號誌與計數型號誌就差異在初值設定可否為0, 1以外之數(也可以負數)**
若此時 semaphore C 為負數 (e.g. -N 則表 N 個process卡在wait( C ))

如何利用 Binary Semaphore 去實現 Counting Semaphore //典型問題， Counting Semaphore都用來控制存取有限的資源

// 初值設定
int c; //可以不用是 0, 1 -> 即Counting Semaphore初值
binary_semaphore S1 = 1; // 防止 C race condition
binary_semaphore S2 = 0; // 如果 C<0 就卡住 process

wait(c){
    wait(S1); //要使用就先扣quota
    C--;
    if(C<0){ //代表quota用完了 就等別人救
        signal(S1);
        wait(S2);
    }
    else signal(S1); // 可以正常使用就退出對c的互斥存取
}
    
signal(c){
    wait(S1);
    C++; //加回quota
    if(C<=0){ // -1 + 1 = 0 所以要加等於 代表先前有人卡住
        signal(S2);
    }
    signal(S1);
}<

除了此分類外還可以使用 '有無使用 busy-waiting' 來區分
不使用 busy-waiting(spinlock) 即使用system call 讓 process 去睡覺 (sleep()) 而當可以使用時再給他 wakeup()即可
註：以上由 OS 提供

### Monitor
<img src = 'https://i.imgur.com/FMpiMLI.png' alt = 'Monitor'>
- 雖然 Semaphore 好用，但凡數量一多有可能使用不當會造成很多問題，所以我們改用另一種機制來使programmer更方便使用同步工具
- 為一種 ADT 包含三個部分
1. 共享變數宣告區
2. programmer defined function
3. 初值設定區

優點：
- 本身保證互斥存取->同一個時間內僅能讓一個 Process 呼叫 monitor中的某個function 執行
> The monitor construct ensures that only one process at a time is **active** within the monitor.
- 此為高階語言，對 programmer 較為方便使用

#### 變數設置
condition x, y, z...
這個變數只有兩個operations
1. wait(): 不像semaphore的 比較像block()這個 system call
2. signal(): 不像semaphore的 比較像wakeup()這個 system call
而等待的 waiting queue 通常使用 FIFO queue，當然也可以使用 priority queue
e.g. 如果用的是 priority queue 則在wait()中會書寫成 priority依據，像是x.wait(time)

#### Monitor 種類
有三種，而至於會分三種類型是因為以下情境。
假想情境：現在 P 在 Monitor 中，也就是 Active。而 Q 在 waiting queue (in monitor) 中等待 signal，若 P 執行 signal() 則 Q 就會往下執行，但就會變成兩個 Process 同時在 Monitor 中 -> 違反互斥。
**所以，需要解決執行 signal() 的 process 或被 signal() 的 process 誰能夠在 monitor 中執行**
以下均以 P 代表執行 signal() 之 process (救命恩人)
Q 為被 signal() 拯救的 process
- 種類一：P 救完就去睡覺，等 Q 執行完畢再繼續執行 ->overall 最優
Hoare monitor
- 種類二：P 救完但繼續執行到結束或自己發I/O，再讓 Q 執行
但在 P 繼續執行過程很有可能將 Q 所需之資源、可以恢復執行的條件給改變使 Q 無法正常執行 -> Q 不保證可以繼續執行

- 種類三：和一很像，但 P 會立即離開 monitors 來到 entry queue ->效能較一差勁
Concurrent C & Pascal used it.

❖ Type 1 & Type 3 屬於 Signal and wait, Type 2 屬於 Signal and continue

#### Implement Monitor using Semaphore

三大條件必須滿足：
1. 設計需符合上述種類一
2. 互斥性質
3. 須展現wait() and signal()

// initialize
Semaphore mutex = 1;
Semaphore next = 0; // 卡住 P
int next_count = 0; // 統計 P 數量
Semaphore x_sem = 0; // 卡住 Q
int x_count = 0; // Q 個數

//about function f

wait(mutex);

/* doing f */

if (next_count >0 ) signal(next); // 接下來有人在等就拯救他，因為他曾經救過你(救命恩人)
else signal(mutex); // 沒人等就放 entry queue的人進來

// 設計 wait()時要站在 Q 的立場
wait(){
    x_count++;
    if (next_count >0) signal(next);
    else signal(mutex);
    wait(x_sem);// Q 被卡住
    x_count--; // Q 被拯救後才來執行這行，減少 Q 數量
}

//設計 signal()要站在救命恩人(p)的立場
signal(){
    next_count++;
    signal(x_sem);//先救 Q ->若無 Q 在等待執行這行也沒問題，直接通過
    wait(next); // 等 Q 回來救你，P 卡在這
    next_count--; // 直到 P 被救 -> P數量 -1
}

### Priority Inversion
發生情境：當 high priority process 正在執行時，需要的資源正被 low priority process 把持住，所以需要等 low priority process 執行完將其釋放才能獲得資源，但又因為 low priority 得不到 cpu 執行，故 high priority process 會等很久
解法：先暫時將 high priority 的優先權繼承給 low priority process 讓他趕快做完釋放資源。

## Message Passing

也是一個機制可以使 Process Synchronize 執行，且不需要共同的 Shared memory 空間 -> distributed system 適用

- 步驟：
1. 建立 communciation link
2. 傳輸
3. 傳輸完畢釋放 link

也須有兩個system call 支援：send & receive

- 種類：
- direct 一組 process 一條 link
- synchronous 收送均需指定
- asynchronous 收方指定即可 (like email)
- indirect 共享 mailbox -> 可以有多條 links

direct 缺點：limited modularity

### Synchronization
message passing 可以是blocking and non-blocking
所以有四種組合，若收送均為 blocking -> 稱為 rendezvous

## Reference:
H.Y. operating system