【正文】 :semaphore。 V(w)。 smoke。Sn,tn,dn)。 P(s)。 endloop endloop endloop 吸煙者問題 Solution Process A Process B Process C loop loop loop SP(m,1,1。 smoke。 procedure return(i:1..3)。 lp[i]:=used。 (車輪， 0) 例 6. 生產(chǎn)線問題 工人 1活動(dòng)： Do{ 加工一個(gè)車架 P(empty) 車架放入箱中 V(frame) }while(1) 工人 2活動(dòng)： Do{ 加工一個(gè)車輪 P(empty) 車輪放入箱中 V(wheel) }while(1) 工人 3活動(dòng)： Do{ P(frame) 箱中取一車架 V(empty) P(wheel) P(wheel) 箱中取二車輪 V(empty) V(empty) 組裝成一臺(tái)車 }while(1) 死鎖情況： K個(gè)車輪， k個(gè)或 k1個(gè)車架 死鎖防止：車架不超過 k2個(gè)（ S1） 車輪不超過 k1個(gè)（ S2） 例 6. 生產(chǎn)線問題 工人 1活動(dòng)： Do{ 加工一個(gè)車架 P(S1) P(empty) 車架放入箱中 V(frame) }while(1) 工人 2活動(dòng)： Do{ 加工一個(gè)車輪 P(S2) P(empty) 車輪放入箱中 V(wheel) }while(1) 工人 3活動(dòng)： Do{ P(frame) 箱中取一車架 V(empty) V(S1) P(wheel) P(wheel)
。 if lp[i]=free then V(S)。 (initial value is 3) mutex: semaphore。 smoke。 SV(w,1。 (0,0,0) s:semaphore。 Simultaneous Poperation SP(S1,t1,d1。 P(t)。 V(w)。 B: possess match。 end end 程序 (Cont.) 程序 (Cont.) begin for I:=0 to 4 do begin state[I]:=thinking。 {Eating}。 V(self[I]) end end。 13 test((I1)mod 5)。 臨界區(qū)域： 34, 911 Var mutex:semaphore。 V(self[I]) Remark: 自測(cè)試不需要 state[I]=hungry, 但測(cè)試左鄰右舍需要此條件。 wn: writer coend end. 分析： 問題 ：讀者源源不斷， read_count不歸 0，寫者會(huì)被餓死。 程序（ Cont.） begin read_count:=0。 read_count:=read_count+1。 Var r_w_w: semaphore。 read_count:=read_count+1。 改進(jìn)：最先進(jìn)入的 R執(zhí)行 P；最后離開的 R執(zhí)行 V； Solution2: 考慮 RR不互斥 Var read_count:integer。 C1: consumer。 end。 V(mutex)。 (=1) 互斥 生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)： Do{ Do{ 加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品 物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗這件物品 }While(1) }While(1) 程序 Program producers_consumers。 管理： Var S:semaphore。 V(mutex) V(mutex) 借書 借書 End End Else V(mutex)。 P(mutex) P(mutex) P(mutex) CR1 CR2 CRn V(mutex) V(mutex) V(mutex) …… 互斥例子：借書系統(tǒng) (revisited) ? Var mutex:semaphore。 If =0 Then wakeup() End wakeup() PCB出等待隊(duì)列，進(jìn)入就緒隊(duì)列（狀態(tài)改為就緒）。 PCBpointer queue。 turn:=0。 turn:0..1。 ? 多 CPU, 指令周期間交叉 , test_and_set, swap指令不是原子的 。key) while (key==1)。 *a:=*b。amp。 key=1。lock)。 turn=j。 While (j!=i) If (flag[j] != idle) j=turn Else j=(j+1)% n。 P2：抓到 1。 6. While (number[j]!=0)and 7. (number[j],j)(number[i],i) skip。 Definition: (a,b)(c,d) iff (ac)or(a==c and bd) Lamport面包店算法 Boolean choosing[0,…,n1]。 } 臨界區(qū) turn=0。 flag[0]=1。 turn==0)。amp。 flag[1]=false。 其余代碼 其余代碼 }while(1)。 }while(1)。 ? 可用于單 CPU和多 CPU環(huán)境中。 二層涵義： （ 1）任何時(shí)刻最多只能有一個(gè)進(jìn)程處于同一組共享變量的相同的臨界區(qū)域； （ 2）任何時(shí)刻最多只能有一個(gè)進(jìn)程處于同一組共享變量的不同的臨界區(qū)域 。 Remarks: 某些交叉結(jié)果不正確 。 ? R(pi)={a1,a2,… ,am}表示程序 pi在執(zhí)行期間所需讀取的所有變量的集合，稱為 “ 讀集 ” ； ? W(pi)={b1,b2,… ,bn}表示程序 pi在執(zhí)行期間所需改變的所有變量的集合，稱為 “ 寫集 ” 。希望打印出的數(shù)是累計(jì)數(shù)的和。 ? 在前趨圖中，沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)，沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)。 ? （ Pi， Pj） ∈→ 可記作 Pi→ Pj, 稱 Pi是 Pj的前趨， Pj是 Pi的后繼。 I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 并發(fā)程序及其特性 ? 不可再現(xiàn)性的例子 ? 進(jìn)程 P： 進(jìn)程 Q： ? A1: N:=0； B1: PRINT（ N）； ? A2: N:=N+1； B2: N:=0； ? A3: GOTO A2； B3: GOTO B1； ? 此例中進(jìn)程 P累積計(jì)數(shù)，進(jìn)程 Q將累計(jì)的結(jié)果打印出來。 程序并發(fā)執(zhí)行的條件 ? 在失去封閉性的條件下，保持可再現(xiàn)性。 錯(cuò)誤原因之 2： 涉及公共變量 (x)。 臨界區(qū)域與進(jìn)程互斥 定義 ： 多個(gè)進(jìn)程不能同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū)域，否則可能發(fā)生與時(shí)間有關(guān)的錯(cuò)誤，這種現(xiàn)象稱為進(jìn)程互斥 。 進(jìn)程互斥的軟件實(shí)現(xiàn) ? 完全用程序?qū)崿F(xiàn)，不需特殊硬件指令支持。 其余代碼 其余代碼 }while(1)。 flag[1]=false。 臨界區(qū)代碼 臨界區(qū) flag[0]=false。 while (flag[1] amp。amp。 while (turn==1) skip。 flag[1]=1。 Resolution: 若抓到相同的號(hào)，按進(jìn)程編號(hào)依次進(jìn)入。j++){ 5. While (choosing[j]) skip。 8. } (1)P1抓到 1未賦值 (2)P2抓到 1進(jìn)入臨界區(qū) (3)P1抓到 1進(jìn)入臨界區(qū) Lamport面包店算法 (Cont.) Pi離開： number[i]=0： 變量 choosing的 作用： P1：抓到 1。 j=turn。 While (flag[j]==idle) j=(j+1)% n。 Pi進(jìn)入： While test_and_set(amp。 waiting[i]=1。 While(((j!=i)amp。 temp:=*a。lock,amp。 多處理機(jī)環(huán)境下互斥 ? 單 CPU, 指令間交叉 , test_and_set, swap指令是原子的 。 CR 作業(yè) 2 Consider the following program: var blocked: array[0..1]of boolean。 blocked[1]:=false。 ? 使用方便 . 典型同步機(jī)制 ? 信號(hào)燈與 PV操作 (semaphore and PV operations) ? 管程 (monitor) ? 會(huì)合 (rendezvous) ? 條件臨界區(qū) (conditional critical region) ? 路徑表達(dá)式 (path expression) ? 事件 (event,traditional UNIX) 信號(hào)燈與 PV操作 , 1965. 信號(hào)燈與 PV操作的定義 Typedef semaphore struct{ int value。 Primitive