【正文】 (choosing[j]) skip。 4. For(j=0。 2. number[i]=max{number[0],…,number[n1]}+1。（ false) Int number[0,…,n1]。 Resolution: 若抓到相同的號(hào)，按進(jìn)程編號(hào)依次進(jìn)入。 Problem: 兩個(gè)進(jìn)程可能抓到相同的號(hào)。 Lamport面包店算法 算法思想 ：設(shè)置一個(gè)發(fā)號(hào)者，按 0,1,2,…, 發(fā)號(hào)。 ? 可用于單 CPU和多 CPU環(huán)境中。 進(jìn)程互斥的實(shí)現(xiàn) ? Framework Repeat critical section remainder section Until false entry section exit section 進(jìn)程互斥的實(shí)現(xiàn) ? Requirements: ? mutual exclusion(互斥進(jìn)入 ): 一次只允許一個(gè)進(jìn)程進(jìn)入關(guān)于同一組公共變量的臨界區(qū) ； ? Progress(空閑讓進(jìn) ): 臨界區(qū)空閑時(shí)，放行一個(gè)進(jìn)入者 ； ? bounded waiting(有限等待 ): 一個(gè)想要進(jìn)入臨界區(qū)的進(jìn)程在等待有限個(gè)進(jìn)程進(jìn)入并離開臨界區(qū)后獲得進(jìn)入臨界區(qū)的機(jī)會(huì) 。 region x1,x2 do region y1,y2 do begin begin …… ……. region y1,y2 do region x1,x2 do begin begin ……. ……. end end end。 嵌套臨界區(qū)域 shared x1,x2。 臨界區(qū)域與進(jìn)程互斥 定義 ： 多個(gè)進(jìn)程不能同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū)域，否則可能發(fā)生與時(shí)間有關(guān)的錯(cuò)誤，這種現(xiàn)象稱為進(jìn)程互斥 。 region B do region B do begin begin …… (訪問 B） …..（訪問 B） . end。 ? 臨界區(qū)域 （ critical region） ? 訪問共享變量的 程序段 。 必須去掉導(dǎo)致不正確結(jié)果的交叉。 錯(cuò)誤原因之 2： 涉及公共變量 (x)。 x:=x1。 ? 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} ? 可見，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}。 ? 若有兩條語(yǔ)句 c=a+b和 v=c1，則它們的 “ 讀集 ” 和“ 寫集 ” 分別為： ? R(c:=a+b)={a,b}， R(v:=c1)={c} ? W(c:=a+b)={c}， W(v:=c1)={v} 程序并發(fā)執(zhí)行的條件 ? 若兩個(gè)程序 p1， p2滿足如下條件，則能夠保持可再現(xiàn)性，因而可以并發(fā)執(zhí)行。 程序并發(fā)執(zhí)行的條件 ? 在失去封閉性的條件下，保持可再現(xiàn)性 。 ? （ 2） 非封閉性 ：一個(gè)進(jìn)程的運(yùn)行環(huán)境可能被其它進(jì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ā)性。 ? 例 : 輸入 (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)也是順序的。 ? 前趨圖的例子 ? 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)程來(lái)說，它的所有指令是按序執(zhí)行的。 ? 在前趨圖中，沒有前趨的結(jié)點(diǎn)稱為 初始結(jié)點(diǎn) ，沒有后繼的結(jié)點(diǎn)稱為 終止結(jié)點(diǎn) 。 ? → ={（ Pi， Pj） | Pj啟動(dòng)之前 Pi必須已經(jīng)完成 }。第四章 互斥、同步與通訊 ? 并發(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)程。 ? 結(jié)點(diǎn)間的有向邊表示偏序或前趨（ precedence relation)關(guān)系 “ → ” 。 ? （ Pi， Pj） ∈→ 可記作 Pi→ Pj, 稱 Pi是 Pj的前趨， Pj是 Pi的后繼。 ? 每個(gè)結(jié)點(diǎn)可以有一個(gè)權(quán)重 (weight)，它可以表示該結(jié)點(diǎn)所包含的 程序量或計(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)說，所有進(jìn)程的活動(dòng)是依次執(zhí)行的。 I1 C1 P1 I2 C2 P2 ? : ? (1)連續(xù)性 : 指令逐條執(zhí)行 ? (2)封閉性 : 不受其它程序及外界因素影響 ? (3)可再現(xiàn)性 : 結(jié)果與推進(jìn)速度無(wú)關(guān) 并發(fā)程序及其特性 ? 程序的并發(fā)執(zhí)行 ? (1)內(nèi)部并發(fā)性 : 指一個(gè)程序內(nèi)部的并發(fā)性。 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； ? 并發(fā)執(zhí)行結(jié)果不唯一 并發(fā)程序及其特性 ? 并發(fā)程序的特性 ? （ 1） 間斷性 ：程序交叉執(zhí)行。 ? （ 3） 不可再現(xiàn)性 ：由于交叉的隨機(jī)性，并發(fā)程序的多次執(zhí)行可能對(duì)應(yīng)不同的交叉，因而不能期望重新運(yùn)行的程序能夠再現(xiàn)上次運(yùn)行的結(jié)果。 ? R(pi)={a1,a2,… ,am}表示程序 pi在執(zhí)行期間所需讀取的所有變量的集合，稱為 “ 讀集 ” ； ? W(pi)={b1,b2,… ,bn}表示程序 pi在執(zhí)行期間所需改變的所有變量的集合，稱為 “ 寫集 ” 。該條件是 1966年首先由 Bernstein提出的，稱為 Bernstein條件 。 與時(shí)間有關(guān)的錯(cuò)誤 例：圖書借閱系統(tǒng) （ x:某種 書冊(cè)數(shù)，設(shè)當(dāng)前 x=1.） 終端 1： 終端 2： CYCLE CYCLE 等待借書者； 等待借書者； IF x=1 Then IF x=1 Then Begin Begin x:=x1。 借書 借書 End End Else 無(wú)書 Else 無(wú)書 End End 1 2 3 4 與時(shí)間有關(guān)的錯(cuò)誤 (Cont.) 錯(cuò)誤原因之 1： 進(jìn)程執(zhí)行交叉 (interleave)。 Remarks: 某些交叉結(jié)果不正確 。 進(jìn)程互斥 (mutual exclusion) ? 共享變量與臨界區(qū) ? 臨界區(qū)域與進(jìn)程互斥 ? 進(jìn)程互斥的實(shí)現(xiàn) 共享變量與臨界區(qū)域 ? 共享變量 （ shared variable） ? 多個(gè)進(jìn)程都需要訪問的變量。 一組公共變量 CR1 CR2 CRn ……. 表示 共享變量 : shared 一組變量 臨界區(qū)域 : region 一組變量 do 語(yǔ)句＞ 例子： shared B:array[0,..,n1]of integer。 end。 Remarks: 互斥是相對(duì)于公共變量而言的。 shared y1,y2。 end。 進(jìn)程互斥的軟件實(shí)現(xiàn) ? 完全用程序?qū)崿F(xiàn)，不需特殊硬件指令支持。 ? 有忙式等待問題。想進(jìn)入臨界區(qū)的進(jìn)程抓號(hào)，抓到號(hào)之后按由小到大的次序依次進(jìn)入 。 Why? 為保證抓到不同的號(hào)，需要互斥機(jī)制。 Definition: (a,b)(c,d) iff (ac)or(a==c and bd) Lamport面包店算法 Boolean choosing[0,…,n1]。 (0) Pi 進(jìn)入 ： 1. choosing