<!-- (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
### Atomic Swap()
## Threadpool L20_B 05:23
>Next : [Semaphore (L20)](/FCNp5iL6Th-eWepZjbRFyg)
Sign in with Wallet
Connect another wallet