---
tags: 作業系統
---

# 作業系統 ch6 Synchronization
- concurrent(1個CPU n個process), shared data inconsistently
- race condition: result is not stable, which is depend on excute order
- critical section: 產生 race condition 的程式碼

---

### solution of critical section
- mutual exclusion
- progress
- if X don't want to entry, X can't effect Y entry
- no deadlock: pick one within limited time
- bounded waiting (no starvation)

---
### solution
- OS: non-premptive
- Peterson's solution
- 2 process
- turn, flag[i]
- i want entry, turn = j (禮讓)

- Hardware: atomic instruction
- test_and_set: while(test_and_set(&Lock));
- compare_and_swap: while(compare_and_swap(&Lock,0,1)) ,expected:0, new_value:1
- only kernal mode can use

- Mutex Locks(spinLock): os provide software solution
- acquire(lock), release(unlock)
- busy waiting: can't entry also can't leave CPU
- as binary Semaphore
- mutex init = 1（沒人），<=0 （有人 不能進入）

- Semaphore
- solve busy waiting by waiting queue
- wait() -> signal()
- semaphore < 0 => can't entry critical section
- must make sure no two process execute wait ()和signal() at same time
- wait ()、signal() put in critical section
- signal() { semaphore++ } // 讓別人進入

- Semaphore without busy waiting
- data | value、waiting queue
- operation | block(in wait, if value<0)、wakeup(in signal if value <= 0)

- Monitor
- high-level abstraction data type
- x.wait(), suspend util x.signal()

- memory transaction(compare_and_swap) is a sequence of read-write operation that are atomic