【正文】 例 6. 生產(chǎn)線問題 0 1 …… k 1 車架 車輪 車架，車輪 工人 1 工人 2 工人 3 例 6. 生產(chǎn)線問題 工人 1活動(dòng)： Do{ 加工一個(gè)車架 車架放入箱中 }while(1) 工人 2活動(dòng)： Do{ 加工一個(gè)車輪 車輪放入箱中 }while(1) 工人 3活動(dòng)： Do{ 箱中取一車架 箱中取二車輪 組裝成一臺車 }while(1) semaphore empty。 P(mutex)。 V(s)。 w,1,1)。m,1)。Sn,dn) { for(i=1。 V(s)。 P(w)。 P(s)。 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。 test((I1)mod 5)。 P(self[I])。 self:array[0..4]of semaphore。 7. P(self[I])。 10 test((I1)mod 5)。 等待隊(duì)列設(shè)置（每個(gè)哲學(xué)家一個(gè)隊(duì)列）： Self: Array[0..4]Of semaphore。 rm: reader。 If read_count=0 Then V(r_w_w)。 { write ops } V(r_w_w) end。 If read_count=0 Then V(r_w_w)。 問題：對 Read_count操作的互斥問題。 (init value: 1) Reader： Writer: P(r_w_w)。 out:=0。 V(mutex)。 P(mutex)。 =k。 (initial value 0) P(S) 后動(dòng)作 先動(dòng)作 V(S) P1: P2: 用信號燈實(shí)現(xiàn)進(jìn)程同步 ? 例子：司機(jī) 售票員問題： ? 司機(jī)活動(dòng)： 售票員活動(dòng)： ? Do{ Do{ ? 關(guān)車門 ? 啟動(dòng)車輛 ? 正常行駛 售 票 ? 到站停車 ? 開車門 ? }While(1) }While(1) 用信號燈實(shí)現(xiàn)進(jìn)程同步 例子：司機(jī) 售票員問題： VAR s1,s2: semaphore。 ? End End 互斥例子：借書系統(tǒng) (revisited) Var mutex:semaphore。 (初值 =1） shared x,y,z:integer。 FIFO P操作原語 P操作原語： Procedure P(var s:semaphore) :=。 ? 可實(shí)現(xiàn) 。 Remainder until false end。 unlock(bus)。 3. 硬件提供“關(guān)中斷”和“開中斷”指令 關(guān)中斷 { Critical Region} 開中斷 Remarks: (1) 開關(guān)中斷只在單 CPU系統(tǒng)中有效 。 Pi進(jìn)入 ： key=1。a,amp。 waiting[i]=0。 局部變量： int j。 }. 對一組公共變量， int lock。 turn=i。 //0..n1。jn。 4. For(j=0。 Problem: 兩個(gè)進(jìn)程可能抓到相同的號。 while(flag[0]) if(turn==0){ flag[1]=0。 (0 or 1) do{ flag[0]=1。 turn=0。 P0: Do{ flag[0]=true。 while (flag[1])。 flag[1]=true。 臨界區(qū)代碼 臨界區(qū)代碼 turn=1。 end。 region B do region B do begin begin …… (訪問 B） …..（訪問 B） . end。 x:=x1。 ? （ 2）非封閉性：一個(gè)進(jìn)程的運(yùn)行環(huán)境可能被其它進(jìn)程所改變，從而相互影響。 I1 C1 P1 I2 C2 P2 ? : ? (1)連續(xù)性 : 指令逐條執(zhí)行 ? (2)封閉性 : 不受其它程序及外界因素影響 ? (3)可再現(xiàn)性 : 結(jié)果與推進(jìn)速度無關(guān) 并發(fā)程序及其特性 ? 程序的并發(fā)執(zhí)行 ? (1)內(nèi)部并發(fā)性 : 指一個(gè)程序內(nèi)部的并發(fā)性。 ? 結(jié)點(diǎn)間的有向邊表示偏序或前趨（ precedence relation)關(guān)系 “ → ” 。 ? 前趨圖的例子 ? P1→ P2， P1→ P3， P1→ P4， P2→ P5，P3→ P5， P4→ P5， P4→ P6， P5→ P7，P6→ P7 1 4 3 2 6 5 7 ? 程序的順序執(zhí)行 ? (1)內(nèi)部順序性：對于一個(gè)進(jìn)程來說，它的所有指令是按序執(zhí)行的。兩次執(zhí)行結(jié)果完全不同。該條件是 1966年首先由 Bernstein提出的，稱為 Bernstein條件。 進(jìn)程互斥 (mutual exclusion) ? 共享變量與臨界區(qū) ? 臨界區(qū)域與進(jìn)程互斥 ? 進(jìn)程互斥的實(shí)現(xiàn) ? 多處理機(jī)環(huán)境下的互斥 共享變量與臨界區(qū)域 ? 共享變量 （ shared variable） ? 多個(gè)進(jìn)程都需要訪問的變量。 嵌套臨界區(qū)域 shared x1,x2。 Busy waiting “運(yùn)行”或“就緒” 嘗試 1 int turn。 P0: P1: Do{ do{ while (flag[1]) 。 不滿足互斥性 : flag[0]=flag[1]=false. 嘗試 3 boolean flag[2]。 }while(1)。 臨界區(qū) flag[0]=false。 其余代碼 }while(1)。 flag[0]=0。 其余代碼 }while(1)。 (0) Pi 進(jìn)入 ： 1. choosing[i]=true。（ false) Int number[0,…,n1]。 情形 (2)編號最小抓到最小號的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 其它進(jìn)程將在第一個(gè) while循環(huán)或第二個(gè) while循環(huán)處等待 , 因而滿足互斥性 . ? 進(jìn)展性 (progress) ? 當(dāng)僅有一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí) , 該進(jìn)程可以立即進(jìn)入 。 j=0。 CS 滿足臨界區(qū)管理原則 ? 互斥性 ? 僅當(dāng) flag[i]==in_cs, 且對所有 j!=i, flag[j]!=in_cs時(shí) , 進(jìn)程 Pi才進(jìn)入臨界區(qū)域 , 因而滿足互斥性 . ? 進(jìn)展性 ? 臨界區(qū)空閑時(shí) , 排在序列 turn, turn+1, … , n1,0,1, 2,… ,turn1最前面的申請進(jìn)入臨界區(qū)的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 因而滿足進(jìn)展性 . ? 有限等待性 ? 進(jìn)程離開臨界區(qū)時(shí) ,按循環(huán)次序 turn+1, … , n1,0,1, 2,… ,turn1確定唯一一個(gè)競爭進(jìn)程為其后繼 , 所以一個(gè)進(jìn)程最多等待 n1個(gè)進(jìn)程進(jìn)入并離開臨界區(qū)后一定能進(jìn)入臨界區(qū) , 因而滿足有限等待性 . 進(jìn)程互斥的硬件實(shí)現(xiàn) 1. 硬件提供“測試并建立”指令 int test_and_set(int amp。 滿足互斥性，進(jìn)展性，不滿足有限等待性。amp。 If(j==i) lock=0。 }。 Remarks： (1) test_and_set指令和 swap指令是原子的，不可中斷的 (在單 CPU情況下 )。 while(b){ lock(bus)。 begin repeat blocked[id]:=true。 P(1) parend。 semaphore s。 ? 只能執(zhí)行 P操作和 V操作，所有其它操作非法。 x:=x1。 Else V(mutex)。 =2。 S1,S2,mutex:semaphore。 P(mutex)。 :=0。 Coend。 If read_count=1 Then P(r_w_w)。 V(mutex)。 read_count: integer。 V(mutex)。 :=1。 Further improvement is left to interested students. 例 3. 哲學(xué)家就餐問題 Dining Philosophers Problem Proposed and solved by . Dijkstra, in 1965 例 3. 哲學(xué)家就餐問題 Room ph0 ph4 ph3 ph2 ph1 f0 f4 f3 f2 f1 例 3. 哲學(xué)家就餐問題 Room ph0 ph4 ph3 ph2 ph1 f0 f4 f3 f2 f1 例 3. 哲學(xué)家就餐問題 哲學(xué)家活動(dòng)： Do{ 思考 進(jìn)食 }While(1) 進(jìn)食：需要“叉子” 叉子： 不同種 組合資源 哲學(xué)家活動(dòng)（包含資源活動(dòng)） Do{ 思考 取左叉，取右叉 進(jìn)食 放左叉，放右叉 }While(1) 死鎖情況：每位哲學(xué)家拿到左叉，等待右叉。 4. test(I)。 4. state[I]:=hungry。 15. V(mutex) false。 state[I]:=hungry。put_down_fork((I+1)mod 5)。 :=1。 (2) X,Y,Z can proceed only after consumption. Traditional semaphore: Var t,m,w,s