Race condition
一組Processes 在Shared Memory溝通方式下，若未對共享變數提供互斥存取等同歩機制，
則會造成 “共享變數之最終結果値，會因 Processes之間執行順序不同而有所不同 ”，導致不可預期之錯誤發生。
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = counter{register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 -1 {register2 = 4}
S4: producer execute counter = register1{count = 6 }
S5: consumer execute counter = register2 {count = 4}
解決方式:
- disable interrupt
- Critical Section design
Solution to critical-section problem
- Mutual Exclusion
Def：
最多只允許一個process在其Critical Section內活動，若其它processes也想進入它們本身的Critical Section，則必須等待值到該process離開Critical Section才能再擇一進入(即不允許多個processes在各自Critical Section內同時活動) - Progress
Def： - Bounded Waiting
Def：
自process提出欲進入Critical Section的請求到其獲准進入Critical Section的等待時間是有限的(⇒No starvation)
若有n個processes欲進入Critical Section，則任一process至多等待(n-1)以後必可進入Critical Section
Peterson's algorithm (software-based)
turn: 指出輪到誰進入CS了
flag[i]: 指出i 是否想進入CS
需滿足
- Mutual exclusion
- progress
- bounded waiting
Hardware
Uniprocessor- can disable interrupt
現代系統直接提供 Atomic特性的指令，讓程式碼可以在單一時間點完成，且不會被中途插斷。
- Test-and-Set
- 符合 mutual exclusion
- 不符合 progress
- 不符合 bounded waiting
- -Pi已進入 C.S.，而 Pj卡在 while loop 中等待進入 C.S.，此時若 Pi離開 C.S. 後又馬上企圖進入 C.S.，則 Pi很有可能再度先於 Pj執行 Test_and_Set 指令，而又再度進入 C.S.。∴ Pj可能 Starvation 。
- SWAP
- 符合 mutual exclusion
- 不符合 progress
- 不符合 bounded waiting
Semaphore
用來解決critical section 及 同步問題
有一個整數變數Semaphore S，通常初始為1，
有兩個atomic指令，wait ()和signal()。也是個mutex lock.
必須要保證沒有兩個process可以同時執行wait ()和signal()，也就是說要把wait ()和signal()也放入critical section。
could have busy waiting in CS implementation
Semaphore with no busy waiting
- two operations
- block: place process 在適合的waiting queue，這個process 會invoke operation
- wakeup: 將process 從 waiting queue 放到 ready queue
problems with Semaphore
- starvation
- deadlock
Deadlock
two or more processes 在等 event, 這個event是只能被其中一個waiting processes 所cause的
Starvation
process 長期無法取得資源而形成 indefinite blocking
(有deadlock 一定有starvation， 有starvation不一定有deadlock )
Priority Inversion
lower priority process hold a lock needed by high priority process.
[Ex]
p1 > p2 > p3
priority-inheritance : p3 繼承p1的優先權，使得p2無法搶奪
哲學家用餐問題
- 最多允許四個人用餐，但會造成starvation
- 只有兩邊的筷子 都可以拿，才拿。 打破 hold and wait
- 基數號 拿左 再拿右。 偶數號 拿右再拿左。 打破 circular wait
參考資料:
沒有留言:
張貼留言