turn
: 現在輪到誰進去
flag[i] = true
: Pi 準備好了
Peterson's solution for process Pi
滿足Mutual exclusion
如果flag[j] == false
或turn = i
, Pi 可以進去
如果都想進去, flag[i] == flag[j] == true
然而turn
只能是其中一個
只有 Pi 或 Pj 其中一個能先進去
另一個要等他結束
滿足Progess
Pi 準備好了
如果 Pj 還沒準備好(在remainder section)
那麼flag[j] == false
Pi 可以進去
Pi 和 Pj 都準備好了
flag[i] == flag[j] == true
turn == i
Pi 進去
turn == j
Pj 進去
滿足Bounded waiting
當 Pi 離開後又想再進去一次
此時 Pi 會執行 turn = j
Pi 就進不去了
因此 Pj 最多等待一次
回傳舊值,並將舊值改為true
第一個執行 test_and_set
的 process 會將 lock 值設為 true 並回傳 false
其他想要拿 lock 的 process 會卡在 while 迴圈
回傳舊值,並比較lock的值
概念與 test_and_set
同
這兩個演算法都不滿足bounded-waiting
一個用 test_and_set()
改良的演算法可以滿足所有 critical-section 的條件
test_and_set()
waiting[i] = ture
means Pi is waiting
只有 waiting[i] == false
或 key == false
才能進入 critical path
第一個執行 test_and_wait()
的 process 會讓 lock = true
, 其他人就要等
如果沒有 process 在等,釋放 lock
如果有,讓 Pj 拿著lock,進入 critical section
滿足 Mutual exclusion
waiting[j] = false
滿足 Progress
一個行程離開 critical section 後,會把 lock 設成 false 或把 waiting[j] 設成 false
這些都會決定要讓哪個在等的行程進入 critical section
滿足 Bounded-waiting
當一個行程離開後,會scan waiting array (i, i+1, … n, 1, 2, … i-1)
任一行程最多等n-1次
dotSun, Dec 22, 2019, 8:58 PM
OS
CSIE