# Operating System #6_1

## Race Condition

* 如果你學過計算機組織，應該知道<b>count++</b>實際上實作為：
1. R1 = count
2. R1 = R1 + 1
3. count = R1
* 而<b>count--</b>則是：
1. R2 = count
2. R2 = R2 - 1
3. count = R2
---
- 想想看，今天若有兩個Processes P1和P2，分別對同一個共享資料做了++和--，你想像中可能過程是這樣：(假設count初始化為5)
1. `R1 = count` ... R1 = 5, count = 5
2. `R1 = R1 + 1` ... R1 = 6, count = 5
3. `count = R1` ... R1 = 6, count = 6
4. `R2 = count` ... R2 = 6, count = 6
5. `R2 = R2 - 1` ... R2 = 5, count = 6
6. `count = R2` ... R2 = 5, count = 5
- 看起來似乎沒有問題。然而實際上卻可能因為中斷的關係，變成以下這樣：
1. `R1 = count` ... R1 = 5, count = 5
2. `R1 = R1 + 1` ... R1 = 6, count = 5
3. `R2 = count` ... R2 = 5, count = 5 (中斷切至P2)
4. `count = R1` ... R1 = 6, count = 6
5. `R2 = R2 - 1` ... R2 = 4, count = 6
6. `count = R2` ... R2 = 4, count = 4
- 這樣的情形造成了資料不同步的錯誤，我們稱這樣的狀況為**Race Condition**，因為兩個Processes就像是在賽跑一樣，途中有可能會彼此超前。

## Critical Section Protocol

* 為了解決這樣的問題，同步化(Synchronization)是必須的。Critical Section (CS) 是一種解決方法。
* CS的特性是，在眾多Processes中如果他們都擁有CS，那麼同一時間只能有一個Process在CS裡面。
* 注意，在執行CS的Process還是可能被中斷，CS是利用同一時間只有一個Process在使用共享資料來避免不同步的問題。
* 如果一段Code要滿足CS，必須擁有以下特性：
* Mutual Exclusion
* Progress
* Bounded Waiting

### Mutual Exclusion

* 如果已經有個Process在CS內了，不能有其他Process在CS裡面。
* 如果要你證明：先假設Pi和Pj都可以進入CS，再找出矛盾推翻。

### Progress

* 如果現在沒有Process在CS內，而且有一些Processes想要進去CS內，則他們必須在**有限時間內**決定誰要進去。
* 除了想進去的Processes能夠決定誰要進去之外，其他的Processes是無法去影響他們的決策的。
* 隱含著不會有、不能有DeadLock的要素。
* 如果要你證明：
1. 如果沒有Process在CS裡面，要進去的一定進得去。
2. 多個要進入，有限時間內進得去。

### Bounded Waiting

* 對於想進入CS的Process來說，必須要在**有限時間內**成功進入CS。
* 不能有Process永遠進不去。
* 如果有N個Processes想進入CS，則每個Process最多等待n-1次即可進入。
* 隱含著不會有starvation的要素。
* 如果要你證明：
* 找出上限次數。

## Peterson’s solution

do {
    flag[i] = TRUE;
    turn = j;
    while (flag[j] && turn == j);
    //critical section
    flag[i] = FALSE;
    //remainder section
} while (1);

* `flag[i]`: 代表Pi對進入CS有興趣。
* `turn`: 代表現在是誰的回合。

1. 先表示自己有興趣進入CS。
2. 將回合給對方(對方優先進入)。
3. 如果不是自己的回合，使用`while()`卡住自己。
4. 結束時將自己變成沒有興趣。

## Memory Barriers

* 有時CPU執行程式時，為了增進效率，可能會在不影響結果的前提下偷換程式碼的執行順序。
* 然而這樣可能會在多個Processes共享資源時產生不同步。
* Memory barrier指強制系統按照順序來執行。

## Compare and Swap

* 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;
}

* 看起來很簡單，不過他擁有一個特性，這個Function受到硬體支援，因此內部執行時**絕對不會被中斷**。
* 使用這個Function就能用幫助我們完成一些CS。
* 範例：

while (true) {
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1)
        key = compare_and_swap(&lock,0,1);
    waiting[i] = false;
    /* critical section */
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = 0;
    else
        waiting[j] = false;
    /* remainder section */
}

## Bakery Algorithm

do {
    Choosing[i] = TRUE;
    Number[i]= Max(Number[0],…Number[n-1])+1;
    Choosing[i] = FALSE;
    for(j=0; j<n; j++){
        while(Choosing[j]) ;
        while((Number[j]!=0)&&((Number[j],j)<(Number[i],i)));
    }
    // critical section
    Number[i]=0
    // remainder section
} while (TRUE);

* `Choosing[0, …, n-1]`: 代表每個processes抽號碼牌了沒。
* `Number[0, …, n-1]`: 代表每個processes抽到的號碼。
---
- 藉由`Choosing[0, …, n-1]`確保每個人都抽號碼牌了才進去比較階段。
- 如果沒有`Choosing[0, …, n-1]`，可能會在比較時才有process抽號碼，導致同時有兩個一起進去CS，造成問題。
- 不保證號碼不會重複，當號碼重複時用pid來比較。
- 號碼小、pid小的優先執行。

## Atomic Variables

* Atomic Variables指該變數是原子等級的，即最小單位。當它進行`++`或`--`等運算時，不會在中途被中斷。
* 當你的共享資料只做簡單的運算，就可以直接使用Atomic Variables來避免不同步的問題了。

## Busy Waiting

* 上述幾種避免資料不同的方法，可以發現都是使用`while()`來卡住process，避免同時有多個processes進入CS。
* 然而這樣的方法其實CPU依然花費資源在無謂的迴圈中等待，這樣的等待方法我們稱作**Busy Waiting**。
* 很顯然的，我們需要更好的方法來解決同步問題。

## Semaphore

* Semaphore是一種不必Busy Waiting的同步工具。
* 它的使用方法大致上長這樣：

Semaphore mutex; // initialized to 1
do {
    wait (mutex);
    // critical Section
    signal (mutex);
    // remainder section
} while (TRUE);

* 如果process前面有`wait()`就必須等候其他process執行`signal()`來喚醒它。
* 內部的實作是遇到`wait()`時將該process搬到waiting queue中等待，`signal()`才將它搬回ready queue；如此一來就可以在排程時不選擇到明明就不會做事的process。

- 
- output is 1 2 1 2 1 2。

###### tags: `note`