【正文】 lem Statement: 一組公共數(shù)據(jù) DB R1 …… Rm W1 …... Wn 要求 ：（ 1） RR可以同時(shí) （ 2） RW不可同時(shí) （ 3） WW不可同時(shí) Solution1: 不考慮 RR不互斥 Var r_w_w:semaphore。 C1: consumer。 in:=0。 end。 out:=(out+1)mod k。 V(mutex)。 Procedure producer cycle produce a product P(S1)。 (=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 S2:semaphore。 管理： Var S:semaphore。 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。 V(mutex) V(mutex) 借書 借書 End End Else V(mutex)。 Else 無書 。 P(mutex) P(mutex) P(mutex) CR1 CR2 CRn V(mutex) V(mutex) V(mutex) …… 互斥例子：借書系統(tǒng) ? Var mutex:semaphore。 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥 Var mutex: semaphore。 If =0 Then wakeup() End wakeup() PCB出等待隊(duì)列，進(jìn)入就緒隊(duì)列（狀態(tài)改為就緒）。 信號(hào)燈變量 PCB PCB PCB Var S:semaphore。 PCBpointer queue。 P1: P2: synchronize 后 先 進(jìn)程同步機(jī)制 ? 定義： 用于實(shí)現(xiàn)進(jìn)程同步的工具稱為同步機(jī)制 （ synchronization mechanism） ? 同步機(jī)制要求： ? 描述能力夠用 。 (3) swap實(shí)際上是：交換內(nèi)存兩個(gè)單元的內(nèi)容 。key) while (key==1)。 對(duì)一個(gè)進(jìn)程空間 ： int key。 *a:=*b。 其余部分 進(jìn)程互斥的硬件實(shí)現(xiàn) 2. 硬件提供“交換”指令 void swap(int amp。amp。lock)。 key=1。 int lock。lock)。 *target=1。 8. } Lamport面包店算法 (Cont.) Pi離開 ： number[i]=0： 臨界區(qū)操作 滿足臨界區(qū)管理原則 ? 互斥性 (mutual exclusion) ? 多個(gè)進(jìn)程競(jìng)爭(zhēng)進(jìn)入臨界區(qū)時(shí) , 下述條件之一成立 : (1)一個(gè)進(jìn)程抓到最小號(hào) , (2)若干進(jìn)程抓到最小號(hào) . 情形 (1)抓到最小號(hào)的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) 。 4. For(j=0。（ false) Int number[0,…,n1]。 Problem: 兩個(gè)進(jìn)程可能抓到相同的號(hào)。 ? 可用于單 CPU和多 CPU環(huán)境中。 region x1,x2 do region y1,y2 do begin begin …… ……. region y1,y2 do region x1,x2 do begin begin ……. ……. end end end。 臨界區(qū)域與進(jìn)程互斥 定義 ： 多個(gè)進(jìn)程不能同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū)域，否則可能發(fā)生與時(shí)間有關(guān)的錯(cuò)誤，這種現(xiàn)象稱為進(jìn)程互斥 。 ? 臨界區(qū)域 （ critical region） ? 訪問共享變量的 程序段 。 錯(cuò)誤原因之 2： 涉及公共變量 (x)。 ? R(p1)∩ W(p2)∪ R(p2)∩ W(p1)∪ W(p1)∩ W(p2)=Φ 程序并發(fā)執(zhí)行的條件 ? 例如，有如下四條語句： ? 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} ? 可見，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}。 程序并發(fā)執(zhí)行的條件 ? 在失去封閉性的條件下，保持可再現(xiàn)性 。例： ? S1： a:=x+2； ? S2： b:=y+4； ? S3： c:=a+b； ? S4： d:=c+6； ? S5： e:=cd； 2 1 4 3 5 并發(fā)程序及其特性 ? 程序的并發(fā)執(zhí)行 ? (2)外部并發(fā)性 : 指多個(gè)程序之間的并發(fā)性。 ? 前趨圖的例子 ? 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)部順序性 ：對(duì)于一個(gè)進(jìn)程來說，它的所有指令是按序執(zhí)行的。 ? → ={（ Pi， Pj） | Pj啟動(dòng)之前 Pi必須已經(jīng)完成 }。 ? 結(jié)點(diǎn)間的有向邊表示偏序或前趨（ precedence relation)關(guān)系 “ → ” 。 ? 每個(gè)結(jié)點(diǎn)可以有一個(gè)權(quán)重 (weight)，它可以表示該結(jié)點(diǎn)所包含的 程序量或計(jì)算時(shí)間 。 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ā)性。 ? （ 3） 不可再現(xiàn)性 ：由于交叉的隨機(jī)性，并發(fā)程序的多次執(zhí)行可能對(duì)應(yīng)不同的交叉，因而不能期望重新運(yùn)行的程序能夠再現(xiàn)上次運(yùn)行的結(jié)果。該條件是 1966年首先由 Bernstein提出的，稱為 Bernstein條件 。 借書 借書 End End Else 無書 Else 無書 End End 1 2 3 4 與時(shí)間有關(guān)的錯(cuò)誤 (Cont.) 錯(cuò)誤原因之 1： 進(jìn)程執(zhí)行交叉 (interleave)。 進(jìn)程互斥 (mutual exclusion) ? 共享變量與臨界區(qū) ? 臨界區(qū)域與進(jìn)程互斥 ? 進(jìn)程互斥的實(shí)現(xiàn) 共享變量與臨界區(qū)域 ? 共享變量 （ shared variable） ? 多個(gè)進(jìn)程都需要訪問的變量。 end。 shared y1,y2。 進(jìn)程互斥的軟件實(shí)現(xiàn) ? 完全用程序?qū)崿F(xiàn)，不需特殊硬件指令支持。想進(jìn)入臨界區(qū)的進(jìn)程抓號(hào)，抓到號(hào)之后按由小到大的次序依次進(jìn)入 。 Definition: (a,b)(c,d) iff (ac)or(a==c and bd) Lamport面包店算法 Boolean choosing[0,…,n1]。 3. choosing[i]=false。 6. While (number[j]!=0)and 7. (number[j],j)(number[i],i) skip。target){ test_and_set=target。 Pi進(jìn)入： While test_and_set(amp。 進(jìn)程互斥的硬件實(shí)現(xiàn)