【正文】 ,number[n1]}+1。 2. number[i]=max{number[0],…,number[n1]}+1。 P1： Lamport面包店算法 算法思想 ：設(shè)置一個(gè)發(fā)號(hào)者，按 0,1,2,…, 發(fā)號(hào)。 其余代碼 }while(1)。 Dekkel算法 int flag[2]。 其余代碼 }while(1)。 不滿足進(jìn)展性 : flag[0]=flag[1]=true, 進(jìn)程 P1和進(jìn)程 P2都不能進(jìn)入臨界區(qū) . Peterson算法 boolean flag[2]。 (false,false) do{ do{ flag[0]=true。 while (flag[0])。 P0: P1: do{ do{ while (turn==1) 。 shared y1,y2。 ? 臨界區(qū)域 （ critical region） ? 訪問(wèn)共享變量的程序段 。 ? R(p1)∩ W(p2)∪ R(p2)∩ W(p1)∪ W(p1)∩ W(p2)=Φ 程序并發(fā)執(zhí)行的條件 ? 例如，有如下四條語(yǔ)句： ? S1: a:=x+y ? S2: b:=z+1 ? S3: c:=ab ? S4: w:=c+1 ? R(S1)={x,y}， R(S2)={z}， R(S3)={a,b}，R(S4)={c} ? W(S1)={a}， W(S2)=， W(S3)={c}，W(S4)={w} ? 可見(jiàn)，R(S1)∩ W(S2)∪ R(S2)∩ W(S1)∪ W(S1)∩ W(S2)=Φ，因而 S1和 S2可以并發(fā)執(zhí)行；而 S1 和 S3不能并發(fā)執(zhí)行，因?yàn)?W(S1)∩ R(S3)={a}； S2和 S3也不能并發(fā)執(zhí)行，因?yàn)?W(S2) ∩ R(S3)=；同樣， S3和S4不能并發(fā)執(zhí)行，因?yàn)?W(S3)∩ R(S4)={c}。 ? 進(jìn)程 Q執(zhí)行完 B1后被中斷，進(jìn)程 P對(duì) N執(zhí)行加 1操作，然后進(jìn)程 Q執(zhí)行 B2，在這種情況下進(jìn)程 P的累計(jì)數(shù)將被丟失。 ? S1： a:=x+y ? S2： b:=az ? S3： c:=a+b ? S4： d:=c+5 S1 S2 S3 S4 ? (2)外部順序性：對(duì)于多個(gè)進(jìn)程來(lái)說(shuō)，所有進(jìn)程的活動(dòng)是依次執(zhí)行的。第四章 互斥、同步與通訊 ? 并發(fā)進(jìn)程 (concurrent processes) ? 進(jìn)程互斥 (mutual exclusion) ? 進(jìn)程同步 (synchronization) ? 進(jìn)程高級(jí)通訊 (munication) ? ? 前趨圖（ precedence graph） ? 有向無(wú)環(huán)圖，圖中每個(gè)結(jié)點(diǎn)表示一個(gè)語(yǔ)句、一個(gè)計(jì)算步驟、或一個(gè)進(jìn)程。 ? 例 : 輸入 (I)、計(jì)算 (C)、打印 (P)三個(gè)活動(dòng)構(gòu)成的進(jìn)程，每個(gè)進(jìn)程的內(nèi)部活動(dòng)是順序的，即 Ii→ Ci→ Pi，多個(gè)進(jìn)程的活動(dòng)也是順序的。 并發(fā)程序及其特性 ? 并發(fā)程序的特性 ? （ 1）間斷性：程序交叉執(zhí)行。 與時(shí)間有關(guān)的錯(cuò)誤 例：圖書(shū)借閱系統(tǒng) （ x:某種 書(shū)冊(cè)數(shù)，設(shè)當(dāng)前 x=1.） 終端 1： 終端 2： CYCLE CYCLE 等待借書(shū)者； 等待借書(shū)者； IF x=1 Then IF x=1 Then Begin Begin x:=x1。 一組公共變量 CR1 CR2 CRn ……. 表示 共享變量 : shared 一組變量 臨界區(qū)域 : region 一組變量 do 語(yǔ)句＞ 例子： shared B:array[0,..,n1]of integer。 region x1,x2 do region y1,y2 do begin begin …… ……. region y1,y2 do region x1,x2 do begin begin ……. ……. end end end。 while(turn==0)。 flag[0]=true。 flag[1]=true。 Int turn。 P1: Do{ flag[1]=true。 (init 0) int turn。 P0： do{ flag[1]=1。想進(jìn)入臨界區(qū)的進(jìn)程抓號(hào)，抓到號(hào)之后按由小到大的次序依次進(jìn)入 。 3. choosing[i]=false。 3. 4. For(j=0。 int turn。 }while (j!=n)。 *target=1。 int lock。lock)。 其余部分 進(jìn)程互斥的硬件實(shí)現(xiàn) 2. 硬件提供“交換”指令 void swap(int amp。 對(duì)一個(gè)進(jìn)程空間 ： int key。 (3) swap實(shí)際上是：交換內(nèi)存兩個(gè)單元的內(nèi)容 。lock)。 Critical section blocked[id]:=false。 P1: P2: synchronize 后 先 進(jìn)程同步機(jī)制 ? 定義： 用于實(shí)現(xiàn)進(jìn)程同步的工具稱(chēng)為同步機(jī)制 （ synchronization mechanism） ? 同步機(jī)制要求： ? 描述能力夠用 。 信號(hào)燈變量 PCB PCB PCB Var S:semaphore。 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥 Var mutex: semaphore。 Else 無(wú)書(shū) 。 End End 用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步 后動(dòng)作 先動(dòng)作 P1: P2: 用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步 General Case: VAR S:semaphore。 Var S2:semaphore。 Procedure producer cycle produce a product P(S1)。 out:=(out+1)mod k。 in:=0。 (init 1) 并發(fā)性提高策略 生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)： Repeat Repeat 加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品 物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗這件物品 Until false Until false 例 2. 讀者 /寫(xiě)者問(wèn)題 P. T. Courtois 1971 Communication of the ACM, , 667669. ACM: Association for Computing Machinery 解法 1：寫(xiě)者可能餓死 解法 2：寫(xiě)者優(yōu)先 例 2. 讀者 /寫(xiě)者問(wèn)題 Problem Statement: 一組公共數(shù)據(jù) DB R1 …… Rm W1 …... Wn 要求 ：（ 1） RR可以同時(shí) （ 2） RW不可同時(shí) （ 3） WW不可同時(shí) accessing Solution1: 不考慮 RR不互斥 Var r_w_w:semaphore。 If read_count=0 Then V(r_w_w)。 read_count:=read_count1。 begin P(r_w_w)。 read_count:=read_count1。 ……。 哲學(xué)家狀態(tài)描述（增加了 hungry狀態(tài)）： State: Array[0..4]Of (thinking,hungry,eating)。 6. 取左叉，取右叉； 7. 進(jìn)食 8. 放左叉，放右叉； 9. state[I]:=thinking。 6. V(mutex)。 程序 Program dining_philosophers var state:array[0..4]of (thinking,hungry,eating)。 V(mutex)。 state[I]:=thinking。 ……. Ph4: philosopher(4)。 P(s)。 Process A Process B process C P(m)。 smoke?！?。 SV(t,1。 SP(t,1,1。 V(s)。 P(mutex)。 return(i)。 (空位， k) semaphore frame。 lp[i]:=free。 endloop endloop endloop 例 5. 3臺(tái)打印機(jī)管理 Var lp:array[1..3]of (free,used)。 t,1,1)。 SV(m,1。 i=n。 V(s)。 P(t)。 V(t)。 Y: supplies match and wrapper。 test((I+1)mod 5)。 pick_up_fork(I)。 mutex:semaphore。 8. 取左叉，取右叉； 9. 進(jìn)食 10. 放左叉，放右叉； 11. P(mutex)。 11. test((I+1)mod 5) false。 (initial value is 0)。 w1: writer。 V(mutex)。 程序（ Cont.） Procedure reader。 V(mutex)。 Solution3: 正確解法 Var mutex:semaphore。 P(r_w_w) {讀操作 } {寫(xiě)操作 } V(r_w_w)。 Cobegin P1: producer。 V(S1)。 B[in]:=product。 =0。 (init