# Critical Section Problem

## Race condition
* 多個行程同時對同一個資料存取
* 存取的順序影響結果
* 解決辦法 : 一次僅允許一個行程存取

## Critical Section
* 一個<font color='Orange'>程式碼片段</font>，用來放置共享變數


## Critical Section Problem
* 必須滿足下列三個要求

1. __Mutual exclusion__
- 任意時間點，只允許一個行程進入
2. __Progress__
- 不想進去的人不能妨礙別人
- 決定誰可以進去的時間是有限的
3. __Bounded waiting__
- 從請求進入到獲准的時間是有限的
* n 個行程<font color="Orange">最多等 n-1 次</font>

## Peterson's Solution
* A software-based solution
* Two process solution

int turn;
Boolean flag[2];

* `turn` : 現在輪到誰進去

* `flag[i] = true` : P~i~ 準備好了 :sunglasses:

* Peterson's solution for process P~i~

do {

    flag[i] = TRUE;
    turn = j;
    while(flag[j] && turn == j);
    
    CRITICAL SECTION
    
    flag[i] = FALSE;
    
    REMAINDER SECTION
}

1. 滿足Mutual exclusion

- 如果`flag[j] == false`或`turn = i`, P~i~ 可以進去

- 如果都想進去, `flag[i] == flag[j] == true`

- 然而`turn` <font color="Orange">只能是其中一個</font>

- 只有 P~i~ 或 P~j~ 其中一個能先進去

- 另一個要等他結束

2. 滿足Progess

1. P~i~ 準備好了

- 如果 P~j~ 還沒準備好(在remainder section)

- 那麼`flag[j] == false`

- P~i~ 可以進去
2. P~i~ 和 P~j~ 都準備好了

- `flag[i] == flag[j] == true`

- `turn == i` P~i~ 進去

- `turn == j` P~j~ 進去

3. 滿足Bounded waiting

- 當 P~i~ 離開後又想再進去一次

- 此時 P~i~ 會執行 `turn = j`

- P~i~ 就進不去了

- 因此 P~j~ 最多等待一次

## Synchronization Hardware

### Atomic operation
* 不會被中斷或是context switch
* 一旦開始執行就會執行到結束

### Test and Set

boolean test_and_set(boolean *target)    {
    boolean *rv = target;
    *target = true;
    
    return rv;
}

// initialize varible lock to false
do    {
    while(test_and_set(&lock));
    // critical section
    lock = false;
    // remainder section
    
} while(true);

* 回傳舊值，並將舊值改為true
* 只有第一次會是false

* 第一個執行 `test_and_set` 的 process 會將 lock 值設為 true 並回傳 false
* 其他想要拿 lock 的 process 會卡在 while 迴圈

### Compare and Swap

int compare_and_swap(int *value, int expected, int new_value)    {
    int temp = *value;
    
    if(*value == expected)
        *value = new_value;
    
    return temp;
}

// initialize varible lock to false
do    {
    while(compare_and_swap(&lock, 0, 1) != 0);
    // critical section
    lock = 0;
    // remainder section
    
} while(true);

* 回傳舊值，並比較lock的值
* 如果是 false(0) 把 lock 值改為 true(1)
* 如果是 true(1) 就還是 true(1)

* 概念與 `test_and_set` 同

### 小結

* 這兩個演算法都<font color="Orange">不滿足bounded-waiting</font>

* 一個用 `test_and_set()` 改良的演算法可以滿足所有 critical-section 的條件

### 修正後的 `test_and_set()`

// initialize varible lock to false
do    {
    waiting[i] = true;
    key = true;
    while(waiting[i] && key)
        key = test_and_set(&lock);
    waiting[i] = false;
    
    // critical section
    
    j = (i+1) % n;
    while((j != i) && !waiting[j])
        j = (j+1) % n;
    
    if(j == i)
        lock = false;
    else
        waiting[j] = false;
        
    //remainder section
    
} while(true)

* `waiting[i] = ture` means P~i~ is waiting

* 只有 `waiting[i] == false` 或 `key == false` 才能進入 critical path

* 第一個執行 `test_and_wait()` 的 process 會讓 `lock = true` ， 其他人就要等

* 如果沒有 process 在等，釋放 lock

* 如果有，讓 P~j~ 拿著lock，進入 critical section

<div style="border-top:1px dashed #cccccc;height: 1px;overflow:hidden"></div>

1. 滿足 Mutual exclusion
* 一個行程離開，一個行程獲得機會進去
* `waiting[j] = false`

2. 滿足 Progress
* 一個行程離開 critical section 後，會把 lock 設成 false 或把 waiting[j] 設成 false

* 這些都會決定要讓哪個在等的行程進入 critical section

3. 滿足 Bounded-waiting
* 當一個行程離開後，會scan waiting array (i, i+1, ... n, 1, 2, ... i-1)

* 任一行程最多等n-1次

---

#### last edit
> [name=dot] [time=Sun, Dec 22, 2019, 8:58 PM]

[HOME PAGE](/@dot/B1LEoYNRS) :stuck_out_tongue:
{%hackmd theme-dark %}
###### tags : `OS` `CSIE`