# Chap. 03 - Process concepts
> 課程內容 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
>
**Note:** [#process](#Q-請說明何謂-process-) [# context switch](#Q-請說明何謂-context-switch-) [# IPC](#Q-請簡單說明何謂-IPC-)
## Content
* [Process concepts](#Process-concept)
* [1. Threads](#1-Threads)
* [2. Process state](#2-Process-state)
* [3. Process control block](#3-Process-control-block)
* [4. Context switch](#4-Context-switch)
* [Process Scheduling](#Process-Scheduling)
* [1. Scheduling](#1-Scheduling)
* [2. Scheduler](#2-Scheduler)
* [2.1 Long-term scheduler](#21-Long-term-scheduler)
* [2.2 Short-term scheduler](#22-Short-term-scheduler)
* [2.3 Medium-term scheduler](#23-Medium-term-scheduler)
* [Operations on processes](#Operations-on-processes)
* [1. Tree of processes](#1-Tree-of-processes)
* [2. Process creation](#2-Process-creation)
* [2.1 Unix/Linux process creation](#21-UnixLinux-process-creation)
* [2.2 Unix/Linux example](#22-UnixLinux-example)
* [3. Process termination](#3-Process-termination)
* [Interprocess communication](#Interprocess-communication)
* [1. Shared memory](#1-Shared-memory)
* [1.1 Consumer & producer problem](#11-Consumer-amp-producer-problem)
* [2. Message passing](#2-Message-passing)
* [2.1 Direct communication](#21-Direct-communication)
* [2.2 Indirect communication](#22-Indirect-communication)
* [2.3 Synchronization](#23-Synchronization)
* [3. Socket (略)](#3-Socket-略)
* [4. Remote procedure calls (略)](#4-Remote-procedure-calls-略)
## Process concepts
> [!Important]
> **Program v.s. Process**
>
> Program(程式)：指的是**儲存在 disk 中**的可執行檔，**尚未被執行**
> Process(行程)：被**載入到記憶體**之中已經**開始執行**的 program
<img src="https://hackmd.io/_uploads/SJ9SwUBmyx.png" width=500>
(process 在記憶體中的 memory map)
一個被載入到記憶體之中的 process 包含了以下部分:
1. Code segment/text section：被讀取到記憶體之中的**程式碼**
* 通常已經被編譯為 instruction
2. Data section：即**全域變數**(global variables)
3. Stack：**區域變數**(local variable)和**被呼叫函式**(function)
4. Heap：**動態分配**(dynamic allocated)的變數或類別(classes)
再次強調 program 是一項**被動(passive)**的個體，它是儲存在磁碟內的(可執行)檔案，而 process 是一項主動(active)的個體，它具備
* 程式計數器(program counter)來指出下一個要執行的指令
* 與該 process 相關的資料
因此廣義來說被載入到記憶體的 process 還包含了以下兩項:
5. Current activity：管理程式的資料或是程式的當前狀態
* 例如程式計數器(program counter)或暫存器內容(register content)
6. A set of associated resource：與該 process 有關的資源(resource)
* 例如 open file handlers
:::info
data section、stack 與 heap 指的都是變數(variables)
:::
> [!Tip] **Interview Ques.**
> ##### Q: 請說明何謂 process ?
> Process 就是載入到記憶體中開始執行的程式，每個 process 會包含四個部分:
> * code segment: 儲存程式碼或指令
> * data section: 儲存全域變數
> * stack: 儲存區域變數或被呼叫函式
> * heap: 儲存動態建立的內容
### 1. Threads
> Threads 不是念脆！:rolling_on_the_floor_laughing:
執行緒(threads)**包含在 process 中**(process 可視為 threads 的**容器**)，又稱為**輕量化的 process**(lightweight process)。它是**使用 CPU core 的基本單位**。Threads 與 process 的長相與管理基本相同，但少了一些記憶體管理。
<img src="https://hackmd.io/_uploads/HkoLvUBQyg.png" width=400>
因為 process 可視為 threads 容器，所以一個 process 內可以有很多個 threads，這些 **threads 之間彼此會共享==部分==記憶體**，包含：
* code section
* data section
* OS resource
但同時每個 threads 又會有自己的
* Thread ID
* Program counter
* Register set
* Stack
### 2. Process state
一個 program 被啟動為 process 並載入到記憶體後會經過以下 5 個狀態(非依序進行)
* New
* 從 program **載入到記憶體**的啟動過程
* 會初始化該段記憶體空間
* Ready
* 啟動後**停留在記憶體中的狀態**
* **等待分配到 CPU 資源**後才開始執行，通常是用 **queue** 來儲存在等待的多個 process，又稱為 read queue
* Running
* 分配到 CPU 資源後**開始執行** instruction
* CPU 每個時間點只允許執行一個 process
* Waiting
* **等待某個事件(Ex: I/O)發生的狀態**
* 因為**某些指令不會用到 CPU 資源**，或是**需要等待其他指令完成**才能繼續進行，這個時候的狀態就稱為 wait，同樣是存在一個 queue 之中
* 等該**事件完成後**不會馬上開始 running，而是**回到 ready 狀態**等待再次執行
* Terminated
* 執行完成的狀態
Process 的五個狀態順序可由下圖表示
<img src="https://hackmd.io/_uploads/Hkw_vISmkg.png" width=600>
1. New -> Ready (admitted)
* 啟動後**儲存==在記憶體中等待== CPU 資源**
* 從 new 到 ready 的過程需要 OS 的准許(admit)，某些情況下(Ex: 記憶體空間不夠)會被 OS 擋掉無法啟動
2. Ready -> Running (scheduler dispatch)
* Scheduler(排程器)會將 process 送到 CPU 開始執行
* 此階段會使用 queue 來對等待中的 process 進行管理與排程
3. Running -> Ready (interrupt)
* 從執行狀態**回到等待狀態通常是因為自主發出 ==interrupt 的影響==所導致**
* 例如執行太久，長期霸佔 CPU 資源，則 timer 就會發出 interrupt 中斷執行
4. Running -> Terminated (exit)
* 簡單的 process 執行完後結束，釋放資源
5. Running -> Waiting (I/O or event wait)
* 當需要**等待 I/O** 或**其他事件**進行時，就會進入 waiting
* Waiting 中的**管理與排程也是透過 queue 實現**
6. Waiting -> Ready (I/O or event completion)
* 當 **I/O 或其他事件完成**時，該 process 會離開 wait queue **進入 ready queue 並等待下次的執行**
:::info
* CPU 在任何時間點都只允許執行一個 process
* Process 大部分的時間都是在 ready 或 wait 中等待
:::
以下圖為例，當一個新的 process 被建立(new)之後的生命週期如下:
* 進入到 ready queue **等待執行**
* 分配到 CPU 資源後**開始執行**
* 執行一段時間後(假設尚未結束)
1. 收到 I/O request 並在 I/O wait queue **等待 I/O 事件完成**，完成後**重新回到 ready queue**
2. 執行時間到發生 interrupt 後進入 ready queue **再次等待資源**分配
3. 建立子程序(i.e., 非 I/O 的事件發生)並在 child termination wait queue 等待子程序完成，完成後**重新回到** ready queue
(中間的每個都是 wait queue 但屬性不同)
### 3. Process control block
PCB(process control block)是一個用來**紀錄與 process 相關資訊的區塊，所有==跟 process 相關的資訊都會儲存在 PCB 中==**，例如：
* Process state
* Program counter
* CPU register
User 每 new 一個 process 後，都會**由 OS 建立該 process 的 PCB 並==存放在 kernel space 之中==**，以 linked list queue 的方式串聯，如下圖所示。
### 4. Context switch
> [!Important]
> **Def.** Context switch
>
> Kernel **saves** the state of the old process and **loads** the saves state for the new process.
因為 CPU 每次只允許執行一個 process，所以在 ready 或 wait 狀態的其他 processes 都會儲存在 memory 之中。而 context switch 指的是在 CPU 的 process 和其他在 memory 中的 process 交換的過程，流程如下圖所示。
<img src="https://hackmd.io/_uploads/HJBF_IHmJg.png" width=500>
以 P$_0$ 與 P$_1$ 分別表示 process 0 與 process 1，PCB$_0$ 與 PCB$_1$ 分別表示兩者的 PCB。
1. 一開始由 P$_0$ 使用 CPU 的資源執行(此時 P$_1$ 為閒置(idle)狀態)
* 接收到 interrupt 或 system call 後被中斷
* 由 OS 將 P$_0$ 的資訊**儲存**到 PCB$_0$ 之中
* 再由 OS **載入** PCB$_1$ 的資訊
2. P$_1$ 開始執行(此時 P$_0$ 為閒置(idle)狀態)
* CPU 再次接收到 interrupt 或 system call 後中斷執行
* 由 OS 將 P$_1$ 的資訊**儲存**到 PCB$_1$ 之中
* 再由 OS **載入** PCB$_0$ 的資訊
3. 繼續執行 P$_0$ (此時 P$_1$ 為 idle 狀態)
要注意的是在 context switch 的過程是**由 OS 負責**將 process 的執行狀態儲存/載入到 PCB 之中，且**不論是 P$_0$ 還是 P$_1$ 都是處於 idle 狀態**。
Context switch 的速度取決於
* 記憶體執行的速度
* 暫存器的數量
* 特殊用來執行 save/load 的 instructions
因為 2 個 process 在 context switch 的過程中都是 idle 狀態，會**浪費 CPU 資源(overhead)但又無法避免**，因此是一個 trade-off 的問題。
可以使用硬體支援(hardware support) 的方式改善，例如將 PCB 儲存在 register 之中，在 register 進行切換，提升速度。
> [!Tip] **Interview Ques.**
> ##### Q: 請說明何謂 context switch ?
> 當作業系統需要切換 CPU 執行的 process 時，將目前 process 的執行狀態保存到它的 PCB 之中，再從下一個要執行的 process 的 PCB 載入之前的狀態，讓 CPU 可以繼續執行下一個 process。是 CPU 在不同 process 之間切換的機制。
## Process Scheduling
### 1. Scheduling
Process scheduling (排程)的概念源自於
* Multi-programming：CPU 隨時都在執行 process，最大化 CPU 的使用率
* Time-sharing：OS 把 CPU 執行的時間切成小片段，頻繁的在不同使用者間切換與互動
而 Process scheduling 的過程就是在不同的 queue 之間做切換
* Job queue
* 將 program **從 disk 載入到記憶體**中成為 process
* 對應到 process state 中的 new state
* Ready queue
* 常駐在記憶體中**等待執行**的 process
* 對應到 process state 中的 ready state
* Device queue
* 正在等待 I/O device 的 process(每個 device 都有自己的 queue)
* 對應到 process state 中的 waiting state
:::info
基本上，只要有 queue 的儲存結構就需要 scheduling 做管理
:::
### 2. Scheduler
Scheduling(排程)指的是一種策略或機制，用來**管理 CPU 或其他系統資源**，簡單來說是「什麼時候分配資源給哪個 process」的決策過程。
Scheduler(排程器)是執行 scheduling 的實體，根據 scheduling 的策略來決定具體 process 的調度。
| Scheduler | Example | Function | State |
| :-: | :-: | :-: | :-: |
| Short-term scheduler | CPU scheduler | 從 memory 中選擇 process 載入到 CPU 中執行 | Ready :arrow_right: Run |
| Long-term scheduler | Job scheduler | 從 disk 中選擇 process 載入到 memory | New :arrow_right: Ready |
| Medium-term scheduler | | 選擇 process 在 memory 與 disk 中做 swap | Ready :arrow_right: Wait |
#### 2.1 Long-term scheduler
又稱為 job scheduler，通常是人為觸發。新的程式被執行，狀態：New state :arrow_right: Ready state。Job scheduler 主要用來**控制 degree of multi-programming**(有多少程式在記憶體中)。太少會導致 CPU 發生 idle，太多會導致 trashing，因為有太多 process 爭搶有限資源。
但因為現在的電腦 memory 較大，比較少用到 long-term scheduler。
#### 2.2 Short-term scheduler
又稱為 CPU scheduelr。因為 **CPU 是屬於 time-sharing system**，所以 CPU scheduler 發生頻率較高。主要**用來==選擇欲執行的 process== 並==從記憶體載入到 CPU 中==分配資源**。狀態：Ready state :arrow_right: Run state。
#### 2.3 Medium-term scheduler
讓程式在 memory 與 disk 之間切換的 scheduler，跟虛擬記憶體的概念結合。為了解決 moemory 空間有限的問題，有時會拿 disk 使用來釋放(free-up)記憶體。
執行兩種動作：
* Swap out：將 **process 從 memory 移出到 disk**，減少 degree of multi-programming
* Swap in：將 **process 從 disk 載入到 memory** 中執行
## Operations on processes
### 1. Tree of processes
每個 process 只要被創建出來，就會被**指派一個==唯一==的識別碼(processor identifier, pid)**，在 OS 中會使用 **tree** 的資料結構來表示所有 processes 之間的關係。
> 可以使用 `ps -ael` 指令在 Unix/Unix-like system 中查看
<img src="https://hackmd.io/_uploads/SkEQ7fdQyg.png" width=500>
### 2. Process creation
當 process 被創建以後，每個 parent process 與其 child process 是**分屬於不同程式**，但彼此之間又會有關係，從以下三點討論。
1. 資源共享的方式(resource sharing)分為 3 種
* Share all resource
* Share subset of parent;s resource
* Share no resource
2. 執行順序分為 2 種
* Execute concurrently(同時執行)
* Parent wait until children terminate(children 優先執行)
3. 記憶體空間的有 2 種創建方式
* Child 完全**複製** parent 的所有狀態
* Child 載入另一支程式，並透過 message passing 與 parent 分享資訊
#### 2.1 Unix/Linux process creation
以 Unix/Linux system 為例，在進行 process creation 的時候可能會用到以下幾個 system call
* `fork()` system call
* 這個 system call 用來**創建**一個新的 child process
* 在記憶體空間上會**完全複製** parent 的所有內容
* 在使用 `fork()` 創建 child process 後，parent 與 child 會**同時執行**
* Return value：使用 `fork()` 後會分別給 child 與 parent 一個回傳值
* 對 child 來說 `fork()` 的回傳值 = 0
* 對 parent 來說 `fork()` 的回傳值 = child 的 PID
* `execlp()` system call
* 載入一個新的 binary file(i.e., program)到記憶體中
* 清空 child process 的記憶體內容(code segment, heap, ...)並塞入新的 program
* `wait()` system call
* 是由 progrmmer 下的指令
* 會強制讓 parent 進入等待狀況直到某個 child 完成
以下使用圖像表示 Unix/Linux system 在呼叫 `fork()` 後的結果。當 parent 呼叫 `fork()` 後會創建一個新的 child process，這時在記憶體空間的創建上有兩種方式。
第一種是過去早期的實作方式，child 會完全複製 parent 的內容，缺點是可能造成記憶體空間或資源的浪費。第二種使用 Copy-On-Write(COW) 技術(上中圖)，只會複製 parent 與 child 不同的部分，並隨著後續需求再慢慢增長。
#### 2.2 Unix/Linux example
```c=
#include <stdio.h>
void main(){
int A = fork(); // fork another process
if (A == 0){
printf("This is from child process\n");
execlp("/bin/ls", "ls", NULL);
}
else{
printf("This is from parent process\n");
int pid = wait(&status);
printf("Child %d completes", pid);
}
printf("Process Ends %d\n", A);
}
/* Output(random):
* This is from child process (from child)
* This is from parent process (from parent)
* a.out hello.c readme.txt (from child)
* Child 43185 completes (from parent)
* Process End 32185 (from parent)
*/
```
在呼叫 `fork()` 後，可以想像成在記憶體中**複製了一份相同的程式**(children process)，並依照該程式(準確來說應該較 process)是 parent 還是 child 來回傳不同的 A 值。
如果是 child process(i.e., A = 0) 則會執行新的 binary file。如果是 parent process(A != 0) 則會等到 child process 執行完成後回傳 child 的 PID 再開始後續動作。
此外，因為 parent 與 child 是共同執行的，實際上的執行順序是由 OS 排程決定，所以輸出結果的順序不一定。
<img src="https://hackmd.io/_uploads/BJpLfc0X1l.png" width=600>
:::info
此處的 `fork()` 其實是 C 的 library，但它也會呼叫 system call 的 `fork()`，只是兩者名稱相同。
:::
> How many processes are created in the following program ?
> Ans：<font color="ffffff">8</font>(反白看答案)
```c=
#include <stdio.h>
#incldue <unistd.h>
int main(){
for (int i=0; i<3; i++){
fork();
}
return 0;
}
```
> [!Note]
> * 當我們執行一支程式或點擊 .exe 執行檔時就會**由 OS 自動創建**一個新的 process 並**載入該程式**到記憶體執行。
> * 一般在寫 code 常會看到創建 process 的動作。手動創建一個新的 process 的目的通常是**為了讓它同時或獨立完成一段可平行處理**的工作
### 3. Process termination
當 process 執行完成或呼叫 `exit()` system call 後都會結束 process。此時會**釋放所有的資源**。此外，parent 也可以藉由指定 PID 來決定要終止哪個附屬於自己的 child process。
## Interprocess communication
> [!Important]
> **Definition：** Interprocess communication(IPC)
>
> A set of methods for the exchange of data among multiple threads in one or more processes.
| | Shared memory | Mesage passing |
| :-: | :-: | :-: |
| Implement | Pointer | System call |
| How to access data | use memory address | `send()` and `receiver()` function call |
| Advantage | Faster | More efficient for small data |
| Problem | Synchronization | Slow |
| When to use | Thread programming | |
所謂的 IPC 指的是**在==多個 processes 或 threads 之間溝通的機制==**。IPC 的目的包括(但不限於)以下：
* Information sharing
* Computation speedup
* Convenience
* Modularity
IPC 的方法可分為 4 種，以下簡述之，後面有詳細介紹。以 memory 的概念可分為兩種：(1) shared memory 與 (2) message passing。另外兩種常用在網路上：(3) sockets 與 (4) remote procedure calls
<img src="https://hackmd.io/_uploads/SyPDHuW4yl.png" width=500>
Shared memory 的方法中，會**由 OS 為兩個 process 分配一塊共用的 memory space**，透過這個**共用的空間**來進行 communication。
* 優點：速度較快，直接使用 memory address 來存取資料即可
* 缺點：需要更多的同步化(synchronization)過程
Message passing 方法中會**將資料複製到 kernel space 中**，再透過 kernel space 將資料複製一份到另一個 process 之中。
* 優點：對小資料來說更有效，不用同步化
* 缺點：速度較慢，因為會使用 system call 來進行資料的複製
Socket 是用在網路中建立通信的端點，透過 IP 與 port 來分別辨識另一台主機與主機上的 process 並進行溝通與交換數據。
Remote procedure calls 是一種允許 process 調用另一個地址空間中的函數或方法的方法。
> [!Tip] **Interview Ques.**
> ##### Q: 請簡單說明何謂 IPC ?
> IPC(InterProcess Communication)是多個不同的 process 之間交換資料的一種機制，常見的方式有 shared memory 與 message passing 兩類:
> * Shared memory 是(透過系統呼叫)由作業系統分配一塊能被多個 process 存取的共享區塊，這些 process 可以在這塊記憶體中存取資料，速度較快但會需要額外的同步機制
> * Message passing 是 process 之間透過 OS 來傳送與接收訊息。資料會經過 OS 複製到 kernel 再從 kernel 複製到另一個 process
### 1. Shared memory
多個 process 藉由 pointer 去**存取相同區塊的 memory space 做讀/寫**。但理論上因為 OS 的保護(potection)機制，所以是不可能提供一塊空間讓多個獨立的 processes 共享，不過可以藉由**特殊的 system call** 來
創建這個 shared space。大致流程下：
* 使用 system call 向 OS 提出建立 shared space 的需求
* 向 OS 提出存取 shared space 的需求
當 shared space 被創建出來後就**不會再由 OS 做管理**，OS 只負責創建，後續管理要由 user 自行處理。
但是，當兩個以上的 process 要對 shared memory 進行存取時，就會產生同步化(synchronization)的問題。
#### 1.1 Consumer & producer problem
以 consumer & producer problem 來描述 shared memory 的機制。假設有兩個 process，一個 Producer process, P 用來不斷**產生資訊**，另一個 Consumer process, C 用來不斷**移除資訊**。這兩個 process 會透過一個**緩衝區**(buffer)進行溝通，buffer 的 size 為 B 且使用 circular array 的方式實作。
<img src="https://hackmd.io/_uploads/ryQlDcb4kl.png" width=500>
兩個 process 對緩衝區的使用上可能出現以下兩個問題：
1. 緩衝區不足(deficiency)：指的是 C 嘗試在 buffer 為空的情況下取出資料
2. 緩衝區溢出(overflow)：指的是 P 嘗試在 buffer 為滿的情況下存入資料
要管理 process 對 buffer 的使用與存取，至少要有以下 4 個 function 或 pointer：
* Next free：`in`
* 指向**下一個閒置的記憶體空間**，讓 P 能夠塞入資訊
* First available：`out`
* 指向**下一個可用的數據**，讓 C 能夠取出資訊
* Empty：`in == out`
* 判斷緩衝區是否為空
* Full：`(in + 1) % B == out`
* 判斷緩衝區是否為滿的狀況
當緩衝區是空的或是滿的時，呈現狀況如下圖所示。此時會發現到如果使用 `in == out` 來判斷緩衝區狀況的話，**無法準確判斷何時為空與何時為滿**。
為此必須**犧牲一塊空間不能擺放資訊**並當作 buffer 為滿的情況，如下圖。也就是說 buffer **最多只能允許使用 (B-1) 的空間**。
:::info
指標(`in` or `out`)移動位置的算式為：`NextPtr = (ptr + 1) % B`
:::
此處的 buffer 與 in/out 指標就是 P 與 C 兩個 process 之間共享的 shared memory
```c=
// global data structure
# define BUFSIZE = 10;
int buffer[BUFSIZE]; // create a shared memory space
int in = out = 0; // initial the two pointer
// for producer
while (1){
while (((in + 1) % BUFSIZE) == out)
; // wait if buffer is full
buffer[in] = nextProduced;
in = (in + 1) % BUFSIZE;
}
// for consumer
while (1){
while (in == out)
; // wait if buffer is empty
nextConsumed = buffer[out];
out = (out + 1) % BUFSIZE;
}
```
### 2. Message passing
Message passing 除了 process 之間的溝通外，還包含了同步化(synchronization)的概念，不像 shared memory 無法做到同步溝通。
此外，為了做到 process 之間的溝通，message-passing system 必須包含以下兩個要素：
* Establish a communication link(溝通管道)
* Exchange a message via send/receive(溝通方式)
* `send(msg)`：message-passing system 提供的一個 **function call**，用來**將 message 發送給另一個 process**，且 message 的大小是可變的
* `receive(msg)`：message-passing system 提供的一個 **function call**，用來**從另一個 process 接收 message**
溝通管道(communication link)的實作有兩個層面需要考慮：
* 物理(physical)層面
* 聚焦在用什麼樣的方式來建立兩個 process/computer 之間的連線，屬於 hardware 層面的考量
* 例如：shared memory、HW bus 或 network
* 邏輯(logical)層面
* 討論溝通的方式與行為，聚焦在 `send()` 與 `receive()` 的特性，包含以下
* **Direct or indirect communication**
* Symmetric or asymmetric communication
* **Blocking or non-blocking**
* Automatic explicit buffering
* Send by copy or send by reference
* Fixed-sized messages or variable-sized messages
(此處僅討論粗體字)
#### 2.1 Direct communication
> [!Important]
> **Definition**
>
> Processes must name each other explicitly
有方向性的溝通(direct communication)指的是 process 之間必須**指定發送或接收**的對象，例如：
* `send(P, msg)` 表示寄送 message 給 process P
* `receive(Q, msg)` 表示僅接收來自 process Q 的 message
##### 特性
因為已經指定收發對象，所以系統(message-passing system)會自動建立 process 之間的連結(link)，不需要 user 手動設置。
同時因為有指定對象，所以只能做到 **one-to-one** 的關係，無法支援多對多或是廣播(broadcast)。
溝通方向有分為單向(unidirection)與雙向(bidirection)，前者指的是只能從 process P 到 process Q，後者指的是可以互相傳遞。
##### Example
以前面的 producer-consumer problem 為例：
```c=
// producer
while(1){
send(consumer, nextProduced);
}
// consumer
while(1){
receive(producer, nextConsumed);
}
```
#### 2.2 Indirect communication
無方向性的溝通(indirection communication)可以想像成是寄信，**所有的 message 都會發送至 mailbox** 或是**從 mailbox 取得**。
* 每個 mailbox 會有一個唯一的識別 ID
* Process 之間可以透過**共享 mailbox** 來做到 communication
* `send(A, msg)` 表示發送一個 message 到 mailbox A
* `receive(A, msg)` 表示從 mailbox A 取得一個 message
##### 特性
只有在兩個 process 之間有**共享一個相同的 mailbox 的情況**下才能建立 process 之間的 link，而且 link 必須由 programmer 手動建立。
因為 message 都是由 mailbox 間接接收與發送，所以可以支援多對多(many-to-many)的關係。此外，link 可以是單向(unidirection)或雙向(bidirection)的。
Mailbox 事實上也是一支程式，可以由 OS 或某個 process 進行管理。
##### 問題
Indirection communication 雖然不用指定對象，但在接收 message 訊息上還是會面臨到類似同步化的問題。以下圖為例，當 P1 發送 message 到 mailbox 後，由 P2 與 P3 接收訊息，此時會產生兩個問題：
* 需要確保同一時間只能有一個 process 接收 message？
* 如果只有一個 process 接收，那是哪一個先接收？
##### 解決方式
(1) 限制 link 的關係
每次只允許 linke 連接兩個 process，將問題簡化成是 direction
(2) 限制 receive 操作
透過同步機制或其他方式，每次只允許一個 process 能夠從 mailbox 中讀取訊息
(3) 選擇 receiver
系統會自動選擇一個接收者來讀取訊息。由 receiver 發出請求後再由 mailbox 決定，當 mailbox 決定後會在通知 sender 被哪個 process 接收。
#### 2.3 Synchronization
在 message-passing system 中 sender 與 receiver 的設計同樣會遇到同步化(synchronization)的問題，不論是 sender 或 receiver 兩者都可以再分為 blocking sender/receiver 或 non-blocking sender/receiver，且 blocking/non-blocking sender 與 blocking/non-blocking receiver 之間沒有一定的對應關係。
:::info
Blocking = synchronous
Non-blocking = asynchronous
:::
(1) Blocking send
Sender 的作用會被阻擋(block)直到之前發出的 message 被 receiver 或 mailbox 接收後才能繼續發送 message。
(2) Non-blocking send
Sender 可以不斷操作，不用等 receiver 接收 message
(3) Blocking receive
在 message 送達前 receiver 會被阻擋(block)不能接收訊息
(4) Non-blocking receive
不論 message 有沒有送到，receiver 都會有一個 return value
##### Buffer implement
緩衝區的設計可以適時的幫助 sender 與 receiver 在收發訊息上遇到的問題，主要用來暫存訊息，避免直接同步，根據 buffer 容量的限制可以分為：
(1) Zero capacity
緩衝區不會儲存任何訊息，表示 sender 與 receiver 必須完全同步，適用於 blocking 的設計。
(2) bounded capacity
緩衝區的容量有限，可以儲存部分訊息，讓 sender 或 receiver 不必完全同步。但如果緩衝區滿了，sender 就會被阻塞(block)
(3) Unbounded capacity
緩衝區的容量沒有任何限制，sender 不會被阻擋(block)
:::info
同步化(synchronization)的意義是確保兩者間訊息傳遞的可靠性與一致性，訊息的發送與接收會發生在可以預測的時間點上。發送者與接收者必須等待彼此達到某個同步點後再繼續執行後續動作。
Blocking 的設計就是限制 sender 與 receiver 的動作來達到同步進行。
:::
不論是同步化的 blocking 模式或非同步化的 non-blocking 模式其實都可以使用 buffer 的設計來改善各自的缺點。
(1) Buffer 對 blocking 的影響
雖然 blocking sender/receiver 本身就已經包含了同步化機制，但也因為同步機制，所以其中一方必須等另一方完成動作後才能繼續操作。因此效能可能會被另一方拖累。
當加入了 buffer 的設計後，sender/receiver 就可以提高發送/接收的速度，不必等待對方完成後再接續進行。提高同步化機制下的收發效率。
(2) Buffer 對 non-blocking 的影響
因為 Non-blocking 沒有同步機制，所以當 sender/receiver 尚未完成發送/接收訊息時，此時又有新的訊息要接收/發送，可能就會發生錯誤或是遺失部分資訊。
當加入了 buffer 的設計後，receiver 可以從 buffer 中接收資訊，避免 sender 還沒發送完而導致 receiver 返回錯誤通知。或是 sender 將資訊發送至 buffer 中，避免 receiver 還沒接收完之前的訊息導致新訊息的遺失。
| 特性 | Blocking mode | Non-blocking mode |
| :- | :- | :- |
| Sender | 緩衝區滿時，發送者阻塞 | 緩衝區滿時，發送者繼續執行或記錄錯誤|
| Receiver | 緩衝區空時，接收者阻塞 | 緩衝區空時，接收者返回 NULL 或錯誤 |
| 使用時機 | 需要高可靠性、同步的系統 | 需要高效率、低延遲的系統 |
| buffer 作用 | 提高同步機制下的效率 | 提供緩衝機制，減少訊息丟失 |
### 3. Socket (略)
### 4. Remote procedure calls (略)
Sign in with Wallet
Connect another wallet