---
# System prepended metadata

title: 作業系統 ch6 Synchronization
tags: [作業系統]

---

---
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 的程式碼
![](https://i.imgur.com/gJmos6D.png)

---

### 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