【正文】 5. P(self[I])。 6. 取左叉，取右叉； 7. 進食 8. 放左叉，放右叉； 9. state[I]:=thinking。 10 test((I1)mod 5)。 11. test((I+1)mod 5) false。 共享變量： state。 臨界區(qū)域： 34, 911 Var mutex:semaphore。(1) 考慮互斥問題 I號哲學(xué)家活動： 1. Repeat 2. 思考 3. P(mutex)。 4. state[I]:=hungry。 5. test(I)。 6. V(mutex)。 7. P(self[I])。 8. 取左叉，取右叉； 9. 進食 10. 放左叉，放右叉； 11. P(mutex)。 12. state[I]:=thinking。 13 test((I1)mod 5)。 14. test((I+1)mod 5)。 15. V(mutex) false。 問題 餓死情況： 某哲學(xué)家左右鄰居至少有一個處于 eating狀態(tài)。 程序 Program dining_philosophers var state:array[0..4]of (thinking,hungry,eating)。 self:array[0..4]of semaphore。 mutex:semaphore。 procedure test(I:0..4) begin if (state[I]=hungry)and (state[(I1)mod 5]eating) and(state[(I+1)mod 5]eating) then begin state[I]:=eating。 V(self[I]) end end。 程序 (Cont.) Procedure philosopher(I:0..4) begin cycle {thinking} P(mutex)。 state[I]:=hungry。 test(I)。 V(mutex)。 P(self[I])。 pick_up_fork(I)。pick_up_fork((I+1)mod 5)。 {Eating}。 put_down_fork(I)。put_down_fork((I+1)mod 5)。 P(mutex)。 state[I]:=thinking。 test((I1)mod 5)。 test((I+1)mod 5)。 V(mutex)。 end end 程序 (Cont.) 程序 (Cont.) begin for I:=0 to 4 do begin state[I]:=thinking。 self[I].value:=0 end。 :=1。 cobegin ph0: philosopher(0)。 ……. Ph4: philosopher(4)。 coend end. 例 3. 哲學(xué)家就餐問題 Room ph0 ph3 ph3 ph2 ph1 f0 f4 f3 f2 f1 例 3. 哲學(xué)家就餐問題 Room ph0 ph4 ph3 ph2 ph1 f0 f4 f3 f2 f1 例 4. 吸煙者問題 Cigarette Smokers’ Problem Patil S. S. Limitations and Capabilities of Dijkstra’s semaphore primitives for coordination among processes. MIT project MAC Computation Structure Group Memo 57, MIT, Cambridge, Mass, 1977. 吸煙者問題 problem statement 3 supplier processes: X: supplies tobacco and match。 Y: supplies match and wrapper。 Z: supplies wrapper and tobacco. 3 smoker processes: A: possess tobacco。 B: possess match。 C: possess wrapper. (1) only one of X,Y,Z can supply at a time。 (2) X,Y,Z can proceed only after consumption. Traditional semaphore: Var t,m,w,s:semaphore。 (0,0,0,1) Process X process Y process Z P(s)。 P(s)。 P(s)。 V(t)。 V(m)。 V(w)。 V(m)。 V(w)。 V(t)。 Process A Process B process C P(m)。 P(w)。 P(t)。 P(w)。 P(t)。 P(m)。 smoke。 smoke。 smoke。 V(s)。 V(s)。 V(s)。 Simultaneous Poperation SP(S1,t1,d1。…。Sn,tn,dn)。 if S1=t1 and … and Sn=tn then for I:=1 to n do Si:=Sidi endfor else (1) place the executing process in the waiting queue for the first Si with Siti, (2)and set the program counter to the beginning of the SP operation so that all conditions will be reexamined when the process is reactivated. Simultaneous Voperation SV(S1,d1?！?。Sn,dn) { for(i=1。 i=n。 i++) Si = Si+di； Remove all processes waiting in the queue associated with Si into ready queue； } 吸煙者問題 Solution Shared t,w,m:semaphore。 (0,0,0) s:semaphore。 (1) Process X Process Y Process Z loop loop loop P(s)。 P(s)。 P(s)。 SV(t,1。m,1)。 SV(m,1。w,1)。 SV(w,1。t,1)。 endloop endloop endloop 吸煙者問題 Solution Process A Process B Process C loop loop loop SP(m,1,1。 SP(w,1,1。 SP(t,1,1。 w,1,1)。 t,1,1)。 m,1,1)。 smoke。 smoke。 smoke。 V(s)。 V(s)。 V(s)。 endloop endloop endloop 例 5. 3臺打印機管理 Var lp:array[1..3]of (free,used)。 (initial value is free) S: semaphore。 (initial value is 3) mutex: semaphore。 (initial value is 1) function require:1..3。 procedure return(i:1..3)。 P(S)。 P(mutex)。 P(mutex)。 lp[i]:=free。 for i:=1 to 3 do V(mutex)。 if lp[i]=free then V(S)。 break。 lp[i]:=used。 V(mutex)。 return(i)。 例 6. 生產(chǎn)線問題 0 1 …… k 1 車架 車輪 車架，車輪 工人 1 工人 2 工人 3 例 6. 生產(chǎn)線問題 工人 1活動： Do{ 加工一個車架 車架放入箱中 }while(1) 工人 2活動： Do{ 加工一個車輪 車輪放入箱中 }while(1) 工人 3活動： Do{ 箱中取一車架 箱中取二車輪 組裝成一臺車 }while(1) semaphore empty。 (空位， k) semaphore frame。 (車架， 0) Semaphore wheel。 (車輪， 0) 例 6. 生產(chǎn)線問題 工人 1活動： Do{ 加工一個車架 P(empty) 車架放入箱中 V(frame) }while(1) 工人 2活動： Do{ 加工一個車輪 P(empty) 車輪放入箱中 V(wheel) }while(1) 工人 3活動： Do{ P(frame) 箱中取一車架 V(empty) P(wheel) P(wheel) 箱中取二車輪 V(empty) V(empty) 組裝成一臺車 }while(1) 死鎖情況： K個車輪， k個或 k1個車架 死鎖防止：車架不超過 k2個（ S1） 車輪不超過 k1個（ S2） 例 6. 生產(chǎn)線問題 工人 1活動： Do{ 加工一個車架 P(S1) P(empty) 車架放入箱中 V(frame) }while(1) 工人 2活動： Do{ 加工一個車輪 P(S2) P(empty) 車輪放入箱中 V(wheel) }while(1) 工人 3活動： Do{ P(frame) 箱中取一車架 V(empty) V(S1) P(wheel) P(wheel)