# Process Synchronization

###### tags: `IT鐵人`

由於電腦同時會執行許多程式，不同程式可能會共用其中幾個變數。
舉例來說，一個停車場要標示裡面還剩多少位置時，如果二樓有一台車走了，一樓也有一台車走了，理論上要多出兩個空位，但如果同步的問題沒有處理好，可能導致二樓跟一樓取走原本剩餘的車位數量，減去一之後丟回去告訴中控，這時候中控就會只有收到減去一的結果，導致外面公告的數字跟停車場內的實際數字不一樣。


## Process Communication

不同的Process溝通的方式主要有兩種，分別為Shared Memory及Message Passing，以下分別介紹。

### Shared Memory

Process之間向OS申請一個shared memory space，可以在這之間宣告一些shared variables，Process可藉由write, read這些shared variables，達到溝通的目的。

有點像是在冰箱上貼便利貼，規定這個冰箱給某兩個process溝通，像是有些家庭會在冰箱上貼一些"晚餐在裡面，自己微波"或是通知隔天的行程之類的。

這種做法OS不用特別支援，只要提供shared memory就好，所以主要責任在programming身上，比如說不同的process(家人)不可以同時搶memory(便條紙)，發生的話稱為Race condition，需要額外寫避免發生的程式碼。

適用於大量資訊溝通，而且這種溝通方式速度快(不用kernel介入)，不適合分散式系統。

### Message Passing

兩個Process要溝通時要建立Communication link，並且此link要能互相傳輸，溝通完即釋放。

就像是講電話，撥通電話號碼後交給電信業者處理，溝通完掛電話連接就斷了。

這種方式就需要OS提供支援，如果兩個Process同時請求溝通，OS要能處理。像是Line通話會在兩人同時撥電話的時候接不到對方來電，OS就要想辦法避免這種狀況發生。

因為需要kernel介入，所以溝通速度慢並且適用於少量的Message，適合用在分散式系統。

## Race Condition

這邊簡單介紹Race Condition以及解決方法，前面用停車場的例子簡單介紹了一下，我們底下用程式的例子來解釋：

假設有一個變數"x"初始值為5，會被兩個process使用到，P1會執行x=x+1，P2會執行x=x-1，這時候根據不同的執行順序會有4,5,6三種結果，以下分別舉一個例子說明：

|x=4|x=5|x=6|
|-|-|-|
|P1,P2同時取得x的初始值x=5|P1先取得x的數值且計算並存入x=6|P1,P2同時取得x的初始值x=5|
|P1,P2對取得的值進行計算x1=6, x2=4|P2取得x的數值且計算並存入x=5|P1,P2對取得的值進行計算x1=6, x2=4|
|P2在P1之後存回x, x=5 => 6 => 4||P1在P2之後存回x, x=5 => 6 => 4|

由於我們不知道Process之間如何交錯，所以要避免這種情況發生。

## Race Condition 解決方法

解決方法有兩種主要做法，第一種是Disable Interrupt，第二種是Critical Section Design。

### Disable Interrupt


這個做法是在處理共享變數時Disable Interrupt，完成存取後才Enable Interrupt，如此一來在這期間CPU不會被Preempted交給其他Process。

這個做法非常簡單暴力，就像是圍起封鎖線不准進入一樣，在單核心的情況下適合使用這種作法。如果是多核心的情況，禁止某個CPU Preempted以後，可能會被其他的CPU Preempted，如果禁止所有CPU Preempted，則Performance會變得非常差。

並且如果讓User任意Disable Interrupt，萬一User遲遲沒有Enable Interrupt，則CPU永遠不會交給其他Process使用。

### Critical Section Design


Critical Section的作用代表這塊很重要，一次只能有一個Process待在Critical Section中，Critical Section Design的想法是由Programmer在Critical Section的前後寫控制碼，分為Entry Section以及Exit Section。

Critical Section Design必須滿足三點，分別為Mutual Exclusion、Progress、Bounded Waiting，以下詳細介紹這三個要素。

|要素|內容|
|-|-|
|Mutual Exclusion|任何時間點最多只允許一個Process在自己的C.S.活動。|
|Progress|不想進入C.S.的Process不可阻礙其他想進入C.S.的Process進入C.S.。多個Process想進入C.S.時必須在有限時間內決定誰可進入，不可讓所有Process卡住。|
|Bounded Waiting|No Starvation。Process在提出進入C.S.的申請後，最多等n-1次(n個Process)即可進入C.S.。|

至於實際的設計方式，經過多次的改良之後解釋起來會有點小複雜，有興趣的同學就去查查吧~
底下提供其中一個範例，還有其他更難理解的Algorithm。


這篇就到這邊了！Race Condition是在多核心的時候會發生的問題，科技的進展同時會產生更多問題需要解決，那我們下篇見囉~

| 上一篇 | 下一篇 |
|-|-|
|[Deadlock](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/Hy6Ot7s7Y)|[Memory Management](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/HkrX_NsNF)