【正文】 Begin :=k。 ……, Cn: consumer。 (initial value is 0) Reader: read_count:=read_count+1。 If read_count=1 Then P(r_w_w)。 mutex:semaphore。 If read_count=1 Then P(r_w_w)。 :=1。 策略 ：一旦有寫者等待，新到達(dá)讀者等待，正在讀的讀者都結(jié)束后，寫者進(jìn)入。 Z: supplies wrapper and tobacco. 3 smoker processes: A: possess tobacco。 V(m)。 P(w)。 V(s)。 i++) Si = Si+di； Remove all processes waiting in the queue associated with Si into ready queue； } 吸煙者問題 Solution Shared t,w,m:semaphore。w,1)。 m,1,1)。 (initial value is free) S: semaphore。 for i:=1 to 3 do V(mutex)。 ? 優(yōu)點： ? 高效，靈活。 (2) abstract data type。 ? 執(zhí)行此操作的進(jìn)程（線程）進(jìn)入 c鏈尾。 Begin If(count==n)Then wait(pq)。 out:=(out+1)%n。 例 2. 讀者 /寫者問題 寫者優(yōu)先 Type readers_writers = Monitor。 End。 If write_count0 Then signal(wq) Else signal(rq) End。 。 Begin If count=0 Then wait(chair) End。 End。 顧客活動 : Repeat (full)。 Begin count:=0。 count:=count+1。 stool:condition。 Var rw:readers_writers。 例 2. 讀者 /寫者問題 Procedure start_write Begin write_count++。 例 2. 讀者 /寫者問題 Procedure start_read。 Begin in:=0。 signal(cq)。 count, in, out: integer。 管程隊列 PCB PCB … c1 PCB PCB … c2 PCB PCB … PCB PCB … 入口隊列 緊急隊列 Monitor 管程成分 PCB PCB … c1 PCB PCB … c2 PCB PCB … PCB PCB … 入口隊列 緊急隊列 初始化代碼 共享變量 操作 操作 操作 … 進(jìn)入與離開 ? 進(jìn)入管程： ? 申請管程互斥權(quán)。 管程的提出 ? 70年代初 , By ? , , . ? 背景 : Structured programming 管程的提出 (Cont.) ? 構(gòu)造操作系統(tǒng)的 PCM方法 ? P： process ? C： class ? M： monitor ? Example system ? solo 管程形式 Type monitor_name=MONITOR(形參表 ) 共享變量說明 define 本管程內(nèi)定義，本管程外使用的子程序名表； use 本管程外定義，本管程內(nèi)使用的子程序名表； Procedure 過程名（形參表）； 局部變量說明 Begin 語句序列 End。 V(mutex)。 P(S)。 V(s)。 SP(w,1,1。 P(s)。 if S1=t1 and … and Sn=tn then for I:=1 to n do Si:=Sidi endfor else (1) place the executing process in the waiting queue for the first Si with Siti, (2)and set the program counter to the beginning of the SP operation so that all conditions will be reexamined when the process is reactivated. Simultaneous Voperation SV(S1,d1。 smoke。 V(t)。 (0,0,0,1) Process X process Y process Z P(s)。 例 3. 哲學(xué)家就餐問題 解決死鎖的辦法：限制最多 4位哲學(xué)家同時進(jìn)餐， VAR fork Array [0..4] of Semophore=(1,1,1,1,1) VAR count : semophore =4 philosopher(i): begin repeat THINK。 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) 后動作 先動作 V(S) P1: P2: 用信號燈實現(xiàn)進(jìn)程同步 ? 例子：司機(jī) 售票員問題： ? 司機(jī)活動： 售票員活動： ? Do{ Do{ ? 關(guān)車門 ? 啟動車輛 ? 正常行駛 售 票 ? 到站停車 ? 開車門 ? }While(1) }While(1) 用信號燈實現(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) :=。 ? 可實現(xiàn) 。 Pi離開 ： lock=0。 *b:=temp。(!waiting[j])) j=(j+1)%n。 While(waiting[i]amp。 Pi離開： lock=0。 情形 (2)編號最小抓到最小號的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 其它進(jìn)程將在第一個 while循環(huán)或第二個 while循環(huán)處等待 , 因而滿足互斥性 . ? 進(jìn)展性 (progress) ? 當(dāng)僅有一個進(jìn)程想進(jìn)入臨界區(qū)時 , 該進(jìn)程可以立即進(jìn)入 。 (0) Pi 進(jìn)入 ： 1. choosing[i]=true。 ? 有忙式等待問題。 Remarks: 互斥是相對于公共變量而言的。 Remarks: 某些交叉結(jié)果不正確 。 ? R(pi)={a1,a2,… ,am}表示程序 pi在執(zhí)行期間所需讀取的所有變量的集合，稱為 “ 讀集 ” ； ? W(pi)={b1,b2,… ,bn}表示程序 pi在執(zhí)行期間所需改變的所有變量的集合，稱為 “ 寫集 ” 。 ? S1： a:=x+y ? S2： b:=az ? S3： c:=a+b ? S4： d:=c+5 S1 S2 S3 S4 ? (2)外部順序性 ：對于多個進(jìn)程來說，所有進(jìn)程的活動是依次執(zhí)行的。第四章 互斥、同步與通訊 ? 并發(fā)進(jìn)程 (concurrent processes) ? 進(jìn)程互斥 (mutual exclusion) ? 進(jìn)程同步 (synchronization) ? 進(jìn)程高級通訊 (munication) ? ? 前趨圖（ precedence graph） ? 有向無環(huán)圖 ，圖中每個結(jié)點表示一個語句、一個計算步驟、或一個進(jìn)程。 ? 例 : 輸入 (I)、計算 (C)、打印 (P)三個活動構(gòu)成的進(jìn)程，每個進(jìn)程的內(nèi)部活動是順序的，即 Ii→ Ci→ Pi，多個進(jìn)程的活動也是順序的。 ? 若有兩條語句 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í)行的條件 ? 若兩個程序 p1， p2滿足如下條件，則能夠保持可再現(xiàn)性，因而可以并發(fā)執(zhí)行。 必須去掉導(dǎo)致不正確結(jié)果的交叉。 嵌套臨界區(qū)域 shared x1,x2。 Lamport面包店算法 算法思想 ：設(shè)置一個發(fā)號者，按 0,1,2,…, 發(fā)號。 2. number[i]=max{number[0],…,number[n1]}+1。 當(dāng)有多個進(jìn)程想進(jìn)入臨界區(qū)時其二元組 (nu