<style>
.red {
color: #e13c2f;
font-weight: bold;
}
.green {
color: #21923f;
font-weight: bold;
}
.blue {
color: #2e7ced;
font-weight: bold;
}
</style>
### 參考資料
- [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics#wait-free-amp-lock-free)
- [Linux 核心設計: 淺談同步機制](https://hackmd.io/@owlfox/SyVVY3EgI/https%3A%2F%2Fhackmd.io%2Fs%2FSJpp-bN0m)
- [延伸閱讀](https://hackmd.io/@Chang-Chia-Chi/OS/https%3A%2F%2Fhackmd.io%2F%40Chang-Chia-Chi%2FOS-CH6)
---
- Cooperating process 合作流程
- Affect or be affected by other processes executing in the system
(影響系統中執行的其他進程或受其影響)
- Cooperating processes can either
- directly share a logical address space
- be allowed to share data only through shared memory
- message passing
- Concurrent access to shared data may result in **data inconsistency**
(並發存取共享資料可能會導致資料不一致)
## Background
- Producer-consumer problem
- Solution
- Producer process
```c
while (true) {
/* produce an item in next_produced */
while (count == BUFFER_SIZE) // buffer 滿了，等到有空間為止
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
```
- Consumer process
```c
while (true) {
while (count == 0)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
/* consume the item in next_consumed */
}
```
- This solution are **correct *separately***, they may not function correctly when executed concurrently
- A shared variable
- Counter (counter is in memory)
- Counter++
```
register1 = counter
register1 = register1 + 1
counter = register1
```
- Counter\-\-
```
register2 = counter
register2 = register2 - 1
counter = register2
```
- Assume the initial value of the counter is 5
- T0: producer execute `register1 = counter` {register1 = 5}
- T1: producer execute `register1 = register1 + 1` {register1 = 6}
- T2: consumer execute `register2 = counter` {register2 = 5}
- T3: consumer execute `register2 = register2 - 1` {register2 = 4}
- T4: producer execute `counter = register1` {counter = 6}
- T5: consumer execute `counter = register2` {counter = 4}
- **Race condition**
- **Several processes** access and manipulate the **same data concurrently** and the outcome of the execution depends on the particular order in which the access takes place
- 當多個 processes 同時存取及操作 share data 時，**最終的值**取決於**最後一個完成執行的 process** (最後一個 instruction)，這個現象稱為 race condition
- 通常將可能產生 race condition 的區域稱作 **critical section**
- 多個 process 共享同個資源 & Context Switch
- <font class='red'>因為 process 的執行順序不同，而造成結果不同</font>
- Process synchronization and coordination among cooperating processes
## The Critical Section Problem
- <font class='green'>Critical section</font>（簡稱 CS）
- The critical section problem
- Design a protocol that the processes can use
```c
while (True) {
entry section
critical section
exit section
remainder section
}
```
- Entry section
- 進入 critical section 時, 要先問能不能進入
- <font class='green'>Critical section</font>
- <font class='red'>會用到共同 buffer 的地方</font>
- Exit section
- 離開 critical section
- Remainder section
- 剩下的程式碼
- A solution to the critical section problem <font class='blue'>must satisfy three requirements</font>
- <font class='blue'>Mutual exclusion 相互排斥</font>
- 避免兩個 process 拿到同一個 pid。
- <font class='red'>當一個 process 在執行他的 critical section 時，其他 process 都無法進入自己的 critical section</font>
- <font class='blue'>Progress</font>
- <font class='red'>如果沒有 process 在執行 critical section, 且有 process 想要執行 critical section, 則必須讓此 process 去執行 critical section</font>
- <font class='blue'>Bounded waiting</font>
- 限制等待次數，避免無止盡的等待。
- <font class='red'>不會永遠都是同一個 process 在執行他的 critical section 也可以說一個 process 不會被無限插隊</font>
- Two general approaches are used to handle critical sections in OS
- Preemptive kernels
- 能有效率地換 process，執行起來會更好
- Non-preemptive kernels
- 一個一個跑，不會互相起衝突
## Peterson's Solution
- Peterson’s solution is restricted to **two processes** that alternate execution between their critical section and remainder section
(僅限兩個 processes 的時候)
> The structure of process $P_i$ in Peterson's solution:
```c
while (true) {
// entry section
flag[i] = true; // 代表我想進入 critical section
turn = j; // 但我把執行權讓給 j
// 如果 j 也想執行 -> j 執行 critical section
// 如果 j 不想執行 -> i 執行 critical section
while (flag[j] && turn == j);
critical_section();
// exit section
flag[i] = false; // 代表我不想進入 critical section 了
// 因為已經執行完了
remainder_section();
}
```
- The two processes share two variables:
```
int turn; // turn=i，就代表是 i 進入 Critical Section
boolean flag[2]; // flag 是用來記錄，process 是否「想」進入 Critical Section
```
- Prove
- **Mutual exclusion**: turn 不可能同時為 0 或 1，因此不可能同時進入 critical section
- **Progress**
- 若 P1 尚未準備好 --> flag[1] = false --> P0 可以進入
- 若兩者都準備好 --> flag[0] = flag[1] = true
- 若 turn = 0 則 P0 進入，否則 P1 進入
- 以上兩種狀況，process 都可以順利進入 critical section
- **Bounded-waiting**
- 若 P1 離開 critical section --> flag[1] = false --> P0 可以進入
- 若 P1 離開 critical section 後，繼續執行 while loop --> flag[1] = true --> turn = 0 (覆寫 P0 原先的 turn = 1) --> P0 可以進入
- 以上兩種狀況， P1 進入後接著進去的一定是 P0，符合 bounded waiting 的要求
## Hardware Support for Synchronization
==考點：哪三個方法及各自的做法（可能是程式碼填空）==
- Three hardware support for synchronization
- <font class='red'>Memory barriers</font>
- <font class='red'>Hardware instruction</font>
- <font class='red'>Atomic variables</font>
### Memory Barriers
- Memory model
- **Strongly** ordered
- 某個 processor 修改了記憶體，其他 processor 能立即看到變更
- 效率會降低
- **Weakly** ordered
- 某個 processor 修改了記憶體，其他 processor **不一定**能立即看到變更
- **Memory barriers** (Memory fences)
- <font class='blue'>執行 memory barrier 時，系統會確保在執行任何讀取或寫入前完成之前的讀取或寫入工作。</font>
- memory barrier 之前的所有 write operation 都要寫入記憶體，memory barrier 之後的 read operation 都可以獲得同步屏障之前的結果。
- Exmaple: 確保 thread 1 輸出是 100
- Thread 1
```
while (!flag)
memory barrier();
print x;
```
- Thread 2
```
x = 100;
memory barrier();
flag = true;
```
### Hardware Instructions
- Many modern computer systems provide special **hardware instructions** that allow us either to test and modify the content of a word or swap the contents of two words ==**atomically**== (one uninterruptable unit)
#### <font class='red'>`test_and_set()`</font>
The **definition** of the atomic `test_and_set()` instruction.
```c
/* return the old value of lock, and set lock to true */
boolean test_and_set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
```
**Mutual-exclusion** implementation with `test_and_set()`.
```c
do {
while (test_and_set(&lock)) // obtain lock
; /* do nothing */
critical_section();
lock = false; // release lock
remainder_section();
} while (true);
```
#### <font class='red'>`compare_and_swap()`</font>
The **definition** of the atomic `compare_and_swap()` instruction.
```c
/* return the old value of lock, if lock == expected, set lock to new value */
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
```
**Mutual exclusion** with the `compare_and_swap()` instruction.
```c
while (true) {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
critical_section();
lock = 0;
remainder_section();
}
```
Bounded-waiting mutual exclusion with `compare_and_swap()`.
```c=
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 */
}
```
```
line 2: 表示 i 想進入 critical section，現在在 waiting 等
line 3: set key to 1
line 4: 當我在 waiting 且 key = 1 的時候
line 5: 只有 waiting = false 且 key = 0 的人才可以進入 critical section
- 如果 lock = 0，表示沒有人在 critical section，
那麼把 key 設成 0 並且取得 lock (lock = 1)
- 如果 lock = 1，表示有人在 critical section，
那我就必須繼續等，直到取得 lock
line 6: waiting = false (準備進入 critical section)
line 7: critical section
line 8: 找到 i 的下一個人 j
line 9: 找到下一個在 waiting 的 j (只有 waiting[j] = true 才會脫離迴圈)
line 10: 如果 waiting[j] = false 就繼續找下一個 j，直到找到下一個想進入
critical section 的人 (還沒執行過 critical section 的人)
line 11: 如果 i = j，表示大家都執行過 critical section 了
line 12: 將 lock 解開
line 13: 如果 i != j，表示還有人沒進去過 critical section
line 14: waiting[j] = false 讓 j 停止 waiting，進入 critical section
==>
Prove bounded waiting:
當一個 process 離開 critical section 的時候，他會依序掃描 waiting 那個陣列去找到
下一個 waiting = true 的人 (想進入 critical section 但還沒進去過的)，讓他變
成下一個進入 critical section 的人，所以所有 process 最多只需要等待 n - 1 輪就
可以進入 critical section，符合 bounded waiting #
```
The `increment()` function is implemented using CAS instruction:
```c
increment(&sequence);
void increment(atomic_int *v) {
int temp;
do {
temp = *v;
} while (temp != compare_and_swap(v, temp, temp + 1));
// 因為 v 會一直等於 temp，所以 v 會一直被設定成 temp + 1，就可以達成 increment
}
```
- Satisfy **all** the critical section requirements
### Atomic Variables
- Atomic variables can be used in to **ensure mutual exclusion** in situations where there may be a data race on a single variable while it is being updated.
## Mutex Locks
- OS designers build software tools to solve the critical section problem
- mutex lock
```c
acquire() {
while (!available)
; /* busy wait */
available = false;
}
release() {
available = true;
}
while (true) {
acquire_lock();
critical_section();
release_lock();
remainder_section();
}
```
- Disadvantage
- **Busy waiting**
## Semaphores
- [號誌 (程式設計) - Wiki](https://zh.wikipedia.org/zh-tw/信号量)
- A semaphore S is an **integer variable** that is accessed only through two standard **atomic** operations.
- `wait()`
- P
- To test
- semaphores - 1
- `signal()`
- V
- To increment
- semaphores + 1
- All modifications to the integer value of the semaphore in the `wait()` and `signal()` operations must be executed **atomically**.
- When one process modifies the semaphore value, no other process can **simultaneously** modify that same semaphore value
### Semaphore Usage
- Binary semaphore
- Range only between 0 and 1
- Mutex lock
- Counting semaphore
- Range over an unrestricted domain
- The semaphore is **initialized to the number of resources available**
- To use a resource
- `wait()`
- decrementing
- To release a resource
- `signal()`
- incrementing
---
- Assume that $P_1$ and $P_2$ that wants the statement $S_1$ to happen before the statement $S_2$
- In process $P_1$:
```
S1;
signal(synch);
```
- In process $P_2$:
```
wait(synch);
S2;
```
- 因為 P~2~ 必須等待 synch 被 P~1~ 釋放，所以 S~1~ 一定會比 S~2~ 先執行。
### Semaphore Implementation
- Busy waiting problem
- The block operation places a process into a waiting queue associated with the semaphore
- Waiting state
- Change the process from the **waiting state** to the ==**ready state**==
- `wakeup()`
## Monitors
- Errors may occur when semaphores are used (next page)
- High-level synchronization constructs
- The monitor type
---
- Violating the mutual exclusion requirement
```
signal(mutex);
...
critical section
...
wait(mutex);
```
- A deadlock will occur
```
wait(mutex);
...
critical section
...
wait(mutex);
```
- Violating the mutual exclusion requirement; or a deadlock will occur
- A process omits the `wait(mutex)`, or the `signal(mutex)`, or both.
### Monitor Usage
- **Abstract Data Type (ADT)**
- Encapsulates **data** with a set of **functions** to operate on that data that are independent of any specific implementation of the ADT
- Pseudocode syntax of a monitor:
```
monitor monitor_name
{
/* shared variable declarations */
function P1 (...) {
...
}
function P2 (...) {
...
}
.
.
.
function Pn (...) {
...
}
initialization code ( ...) {
...
}
}
```
---
- A programmer who needs to write a **tailor-made synchronization** scheme can define one or more variables of type *condition*.
- Condition variables
- Condition x, y
- The operation `x.wait()` means that the process invoking this operation is suspended until another process invokes `x.signal()`
- The operation `x.signal()` resumes **exactly one** suspended process
### Implementing a Monitor Using Semaphores
- Mutual exclusion within a monitor is ensured
### Resuming Processese within a Monitor
- Process resumption order within a monitor
- Solution 1: FCFS
- Solution 2: Conditional wait
- `x.wait(c)`
- c: priority number
```
monitor ResourceAllocator {
boolean busy;
condition x;
void acquire(int time) {
if (busy) x.wait(time);
busy = true;
}
void release() {
busy = false;
x.signal();
}
initialization_code() {
busy = false;
}
}
```
## Liveness
### Deadlock
- Deadlocked
- Two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes
### Priority Inversion
- Priority inversion
- When a higher-priority process needs to read or modify kernel data that are currently being accessed by a **lower-priority process** (or a chain of lower-priority processes)
- Kernel data are protected with a lock
- Priority-inheritance protocol
- All processes that are accessing resources needed by a higher-priority process **inherit the higher priority until they are finished with the resources**.
- When they are finished, their priorities revert to their original values.
## Evaluation
- **CAS (compare-and-swap)**-based approaches
- optimistic
- Mutual exclusion locking
- pessimistic
| | CAS protection | Traditional synchronization |
| -------------------:|:--------------:|:---------------------------:|
| Uncontended | Faster | |
| Moderate contention | Faster |
Sign in with Wallet
Connect another wallet