---
# System prepended metadata

title: Race Condition、Critical Section (L18_C_D L19 )
tags: [10501 資訊工程學系 作業系統]

---

<!-- (L19_A) -->
## [Decision Mode](https://www.kshuang.xyz/doku.php/operating_system:course_concept:cpu_scheduling?#x02_decision_mode)

排成進行的時機是由 Decision Mode 決定的，一般分為 Non-preemptive 與 Preemptive 兩種

進行 CPU scheduling 的可能時機有下列四種:

1. 當一個 process 的狀態由 running 轉為 waiting 時
2. 當一個 process 的狀態由 running 轉為 ready 時 e.g. time sharing 因為 timeout 回到 ready
3. 當一個 process 的狀態由 waiting 轉為 ready 時
4. 當一個 process 的狀態由 running 轉為 terminate 時
### Non-preemptive:

Non-preemptive 不可搶奪型，又稱 cooperative scheduling 合作式排程

- 一個 Process 除非自行放棄 CPU 的使用權，否則其他 Processes 不能奪取其 CPU 使用權
    - process 等待 I/O, semaphore wait
    - process terminates
- Non-preemptive scheduling 只可能發生在上面的 1. 4. 兩個時機點

### Preemptive:

Preemptive 可搶奪型

- 不論正在執行的 process 是否可繼續執行，必要時 CPU 使用權可能被搶奪
- Preemptive scheduling 在上述的四個時間點皆會發生
- 適用於 real-time system, time sharing system
- context switch 次數較多，overhead 較大

## Race Condition 13:51
- **Race condition**: the situation where several processes **access and manipulate shared data concurrently.** The final value of the shared data **depends upon which process finishes last.**
    * 一群 process/thread 同時存取或使用 shared data，會造成 data 的值不如預期。
- To prevent race condition, concurrent processes must be **synchronized**.
    - On a single-processor machine, we could **disable interrupt** or use **non-preemptive CPU scheduling**
- Commonly described as **critical section problem**.

### The Critical-Section Problem

* Purpose: 避免 race condititon.
* Purpose: a protocol for processes to cooperate.
* Problem description
    * N Processes are competing to use some shared data
    * Each process has a **code segment,** called **critical section,** in which the shared data is accessed
    * Ensure that when one process is executing in its critical section, **no other process is allowed to execute in its critical section** -> mutually exclusive
* General code section structure
    * Only one process can be in a critical section
```c=
do {
    entry_section();
        // critical section
    exit_section();
        // remainder section
} while(1);
```

### Critical Section Requirement
1. **Mutual Exclusion** : if process P is excution in its CS, no other processes can be execution in their CS.
    - 只有一個人可以進 CS。
3. **Progress** : **if no process is executing in its CS** and there exit some processes that wish to enter their CS, these **processes cannot be postponed (推遲) indefinitely (無限期).**
    - 只要沒有人等著要進 CS，Process 可以重複進。
5. **Bounded Waiting** : **A bound must exist** on the number of times that **other processes are allowed to enter their CS** after a process has made a request to enter its CS.
    - 等待進 CS 的時間有一定的期限。

## CS Solution 18_D

### SW Solution 3:51
* Only 2 processes, $P_0$ and $P_1$
* Shared variables
    * int turn; // initially turn = 0
    * turn = i -> $P_i$ can enter its critical section
```c=
/* Process 0 */
do {
    while(turn != 0);
        // critical section
    turn = 1;
        // remainder section
} while(1);
    
/* Process 1 */
do {
    while(turn != 1);
        // critical section
    turn = 0;
        // remainder section
} while(1);
```
> Progress 有問題 (P0 連續做兩次時，第二次會進不去)

## Peterson's (2 thread scenario)
* int turn; (initially turn = 0)
* turn = i -> $P_i$ can enter its critical section
* boolean flag[2]; (initially flag[0])
* flag[i] = true -> $P_i$ ready to enter its critical section
```c=
// for process i
do {
    flag[i] = TRUE;
    turn = j;
    while(flag[j] && turn == j);
    // critical section
    flag[i] = FALSE;
    // remainder section
} while(1);
```
>Enter CS when either:
>1. a process gets its turn
>2. the other process is not ready

### [Proof of Peterson's Solution](https://youtu.be/IOx8vtDzGO0?t=650)
```c=
// for process 0
do {
    flag[0] = true;
    turn = 1;
    while(flag[1] && turn == 1);
    // critical section
    flag[0] = false;
    // remainder section
} while(1);
```
```c=
// for process 1
do {
    flag[1] = true;
    turn = 0;
    while(flag[0] && turn == 0);
    // critical section
    flag[1] = false;
    // remainder section
} while(1);
```
#### Mutual exclusion:
* If $P_0$ CS -> flag[1] == false || turn == 0
* If $P_1$ CS -> flag[0] == false || turn == 1
* Assume both processes in CS -> flag[0] == flag[1] == true
    ->turn == 0 for $P_0$ to enter, turn == 1 for $P_1$ to enter
    * **However, "turn" will be either 0 or 1** because its value will be set for both processes, but only one value will last.
    * **Therefore, $P_0, P_1$ can't in CS at the same time!**

#### [Progress](https://youtu.be/IOx8vtDzGO0?t=812)
* $P_0$ wishes to enter its CS
    1. If $P_1$ is not ready -> flag[1] = false -> $P_0$ can enter
    2. If both are ready -> flag[0] == flag[1] ==true
        * If turn == 0 then $P_0$ enter, otherwise $P_1$ enters
:::success
Either case, some waiting process can enter CS!
:::

#### [Bounded waiting (e.g., $P_0$ wishes to enter its CS)](https://youtu.be/IOx8vtDzGO0?t=981)
1. Once $P_1$ exists CS -> flag[1] == false -> $P_0$ can enter
2. If $P_1$ exists CS && reset flag[1] == true 
    -> turn == 0 (overwrite $P_0$ setting) -> $P_0$ can enter
:::success
把 key 交給別人，防止特定 process 一直執行
:::


## Define Critical section

### 1. 假如程式碼都包在 CS
```c=
// Consumer
while(TRUE) {
    entry_section();
    while(counter == 0); // 假如一開始執行 consumer
                         // 程式會卡在這等 counter
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
    computing();
    exit_section();
}
```
```c=
// Producer
while(TRUE) {
    entry_section(); // 因為 Consumer 卡在 cs 出不來
                     // Producer 也卡在 entry
    nextItem = getItem(); 
    while(counter == BUFFER_SIZE);
    buffer[in] = nextItem;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
    computing();
    exit_section();
}
```
:::warning
Deadlock, if Consumer enter CS first!
:::
### 2. CS with computing

```c=
// Producer process
while(TRUE) {
    nextItem = getItem();
    while(counter == BUFFER_SIZE);
    buffer[in] = nextItem;
    in = (in + 1) % BUFFER_SIZE;
    entry_section();
    counter++;
    computing();
    exit_section();
}
```
```c=
// Consumer process
while(TRUE) {
    while(counter == 0);
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    entry_section();
    counter--;
    computing();
    exit_section();
}
```
:::warning
Poor performance
:::

## [Bakery Algotithm (n processes)](https://youtu.be/IOx8vtDzGO0?t=1418)
* Before enter its CS, each **process receives a # (number, 號碼牌)**
* Holder of the **smallest # enters CS**
* The numbering scheme always generates **# in non-decreasing order**; 
    i.e., 1,2,3,3,4,5,5,5
* If processes $P_i$ and $P_j$ receive the **same #, if i < j (PID), then $P_i$ is served first**
* Notation:
    * $(a,b) < (c,d)\rightarrow \ \text{if}\ a < c\ \ \text{or}\ \ \text{if}\ a == c\ \&\&\ b < d$
:::success
* Bounded-waiting because processes enter CS on a First-Come, First Served basis
:::
```c=
// process i :
do {
    choosing[i] = TRUE;
    nums[i] = max(num[0], num[1], num[2], ... , num[n - 1]) + 1; // get ticket
    choosing[i] = FALSE;
    for(j = 0; j < n; j++) {
        while(choosing[j]);                                      // ticket 還沒抽完，卡在 line 4
        while((num[j] != 0) && ((num[j], j) < (num[i], i)));     // 比 ticket 的大小，再比 PID
    }
    // critical section
    num[i] = 0;
    // reminder section
} while(1);
```
```c=2
// choosing 用意在於，怕其他 process 正在抽號碼牌，等他抽完再比大小
choosing[i] = TRUE;
...
choosing[i] = FALSE;
...
    while(choosing[j]);
...
```
### Why cannot compare when num is being modified?
* Without locking
    1. Let 5 be the current maximum number
    2. If $P_1$ and $P_4$ take number together, but $P_4$ finishes before $P_1$
        * $P_1 = 0, P_4 = 6$ ->$P_4$ will enter the CS
    3. After $P_1$ takes the number
        * **$P_1 = P_4 = 6$ -> $P_1$ will enter the CS as well!**
* With locking
    * $P_4$ will hace to wait until $P_1$ finish taking the number
    * **Both $P_1 \& P_4$ will have the new number "6" before comparison**

## [Pthread Lock / Mutex Routines](https://youtu.be/nNcqTc-00WA)
* To use mutex, it must be declared as of **type** ***pthread_mutex_t*** and initialized with ***pthread_mutex_init()***
* A mutex is destroyed with ***pthread_mutex_destroy()***
* A critical section can then be protected using ***pthread_mutex_lock()*** and ***pthread_mutex_unlock()***
```c=
#include "pthread.h"
pthread_mutex mutex;
pthread_mutex_init(&mutex, NULL);  // specify default attribute for the mutex
pthread_mutex_lock(&mutex);
// critical section
pthread_mutex_unlock(&mutex);
pthread_mutex_destroy(&mutex)
```

## [Condition Variavles (CV)](https://youtu.be/nNcqTc-00WA?t=180)
* CV represent some **condition** that a thread can : 
    * Wait on, until the condition occurs; or
    * Notify other waiting threads thar tke condition has occurred
* Three operations on condition variables : 
    * ***wait()*** --- **Block** until another thread calls signal() ot broadcast() on the CV
    * ***signal()*** --- Vake up **one thread** waiting on the CV
    * ***broadcast()*** -- Wake up all threads waiting on the CV
* In Pthread, CV **type** is a ***pthread_cond_t***
    * Use ***pthread_cond_init()*** to initialize
    * ***pthread_cond_wait(&theCV, &somelock)***
    * ***pthread_cond_signal(&theCV)***
    * ***pthread_cond_broadcast(&theCV)***

### [Using Condition Variable](https://youtu.be/nNcqTc-00WA?t=1362)
* Example:
    * A threads is designed to **take action when x = 0;**
    * Another thread is responsible for decrementing the counter
```c=
pthread_cond_t cond;
pthread_cond_init(cond, NULL);
pthread_mutex_t mutex;
pthread_mutex_init(mutex, NULL);
```
#### action
```c=
action() {
    pthread_mutex_lock(&mutex);
    if(x != 0) pthread_cond_wait(cond, mutex);
    pthread_mutex_unlock(&mutex);
    take_action();
}
```
1. Lock mutex
2. Wait()
    1. put the thread into **sleep & releases the lock**
    2. **Wake up**, but the thread is locked
    3. **Re-acquire lock** and resume execution
:::success
Another reason why condition variable op. MUST within mutex lock
1. action 進入 pthread_cond_wait(cond, mutex) 時，會 release lock (mutex)，這樣 counter 才可以進入 critical section
2. 當 counter call pthread_cond_signal 時，action 雖然在 cs 裡，但沒有 lock (mutex)。lock 在 counter 那。
3. 當 counter release lock 時，action 才可以 re-acquire lock，再繼續執行。
:::

3. Release the lock

#### counter
```c=
counter() {
    pthread_mutex_lock(&mutex);
    x--;
    if(x == 0) pthread_cond_signal(cond);
    pthread_mutex_unlock(&mutex);
}
```
1. Lock mutex
2. Signal()
3. Releases the lock
:::success
1. mutex 保護 trigger condition var 的變數 (int x)
2. 在 signal 時 (pthread_cond_signal(cond))，要確保 condition var 要為 0
:::


## Hardware Support 10:05 
* The CS problem occurs because the modifiaction of a shared variable may be **interrupted**
* **If disable interrupts when in CS..**
    * not feasible in multiprocessor machine
    * clock interrupts cannot fire in any machine
* HW support solution: **atomic instructions**
    * atomic: **as one uninterruptible unit**
    * examples: ***TestAndSet(var)***, ***Swap(a,b)***

### Atomic TestAndSet()
```c=
bool TeatAndSet(bool &lock) {
    // execute atomically:
    // return the value of "lock" and set "lock" to TRUE
    bool value = lock;
    lock = true;
    return value;
}

do{
    while(TestAndSet(lock));
    // critical section
    lock = FALSE;
    // remainder sectio
} while(1);
```

- Mutual exclusion ? Yes
- Progress ? Yes
- Bounded-Wait ? No
![](https://i.imgur.com/cmNdg20.png)

### Atomic Swap()
![](https://i.imgur.com/RTxtudR.png)

## Threadpool L20_B 05:23
![](https://i.imgur.com/Eelk7NR.png)
![](https://i.imgur.com/bR424zk.png)
![](https://i.imgur.com/V8D7vLt.png)
>Next : [Semaphore (L20)](/FCNp5iL6Th-eWepZjbRFyg)