【正文】 S: semaphore。 (initial value is 3) mutex: semaphore。 (initial value is 1) function require:1..3。 procedure return(i:1..3)。 P(S)。 P(mutex)。 P(mutex)。 lp[i]:=free。 for i:=1 to 3 do V(mutex)。 if lp[i]=free then V(S)。 break。 lp[i]:=used。 V(mutex)。 return(i)。 條件臨界區(qū) Conditional Critical Region ? 略 管程（ Monitor） ? PV操作： ? 分散式同步機制：共享變量操作， PV操作，分散在整個系統(tǒng)中或各個進程中。 ? 缺點： ? 可讀性差； ? 正確性不易保證； ? 不易修改。 ? 優(yōu)點： ? 高效，靈活。 ? 管程： ? 集中式同步工具：共享變量及其所有相關(guān)操作集中在一個摸塊中。 ? 優(yōu)點： ? 可讀性好； ? 正確性易于保證； ? 易于修改。 ? 缺點： ? 不甚靈活，效率略低 。 管程的提出 ? 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。 ………… 管程形式 (Cont.) Function 函數(shù)名（形參表） :返回值類型； 局部變量說明 Begin 語句序列 End。 …………… Begin 共享變量初始化語句序列 End。 語言特點： (1) modularized。 (2) abstract data type。 (3) information hiding. 管程語義 ? 管程的共享變量在管程外部不可見 ， 外部只能通過調(diào)用管程中的外部子程序訪問共享變量； ? 為保證對共享變量操作的數(shù)據(jù)完整性， 規(guī)定管程互斥進入 ； ? 管程中有等待 /喚醒機制，等待時釋放管程的互斥權(quán)，喚醒時（ P喚醒 Q）： ? P等待， Q繼續(xù)，直到 Q退出或等待； (Hoare) ? Q等待， P繼續(xù)，直到 P退出或等待； (Java) ? Signal and continue ? 被喚醒進程需要重新檢查等待條件 ,可能再次等待 . ? 喚醒是管程中可執(zhí)行的最后一個操作。 (Hansen) ? Signal and leave Hoare管程設(shè)施 ? 入口等待隊列： ? 每個管程變量一個，用于排隊進入； ? 緊急等待隊列： ? 每個管程變量一個，用于喚醒等待； ? 內(nèi)部等待隊列： ? var c: condition。 可根據(jù)需要定義多個，用于設(shè)置等待條件。 管程隊列 PCB PCB … c1 PCB PCB … c2 PCB PCB … PCB PCB … 入口隊列 緊急隊列 Monitor 管程成分 PCB PCB … c1 PCB PCB … c2 PCB PCB … PCB PCB … 入口隊列 緊急隊列 初始化代碼 共享變量 操作 操作 操作 … 進入與離開 ? 進入管程： ? 申請管程互斥權(quán)。 ? 離開管程： ? 如緊急等待隊列非空，喚醒第一個等待者；否則開放管程。 條件變量操作 ? Var c:condition。 ? wait(c): ? 如緊急隊列非空，喚醒第一個等待者，否則釋放管程互斥權(quán) 。 ? 執(zhí)行此操作的進程（線程）進入 c鏈尾。 ? signal(c): ? 如 c鏈空，相當(dāng)空操作。 ? 否則喚醒第一個，執(zhí)行此操作的進程（線程）進入緊急隊列。 例 Type producer_consumer = MONITOR Var B:Array[0..n1]Of integer。 count, in, out: integer。 pq, cq:condition。 define put_in, get_out。 Procedure put_in(item:integer)。 Begin If(count==n)Then wait(pq)。 B[in]:=item。 in:=(in+1)%n。 count++。 signal(cq)。 End。 例 Procedure get_out(Var item:integer) Begin If(count==0)Then wait(cq)。 item:=B[out]。 out:=(out+1)%n。 count。 signal(pq)。 End。 Begin in:=0。 out:=0。 count:=0。 End。 例 2. 讀者 /寫者問題 寫者優(yōu)先 Type readers_writers = Monitor。 Var rq,wq: condition。 reading_count,write_count:integer。 Define start_read,finish_read, start_write,finish_write。 例 2. 讀者 /寫者問題 Procedure start_read。 Begin If write_count0 Then wait(rq)。 reading_count++。 signal(rq)。 End。 Procedure finish_read。 Begin reading_count。 If reading_count=0 Then signal(wq) End。 例 2. 讀者 /寫者問題 Procedure start_write Begin write_count++。 If (write_count1) or (reading_count0) Then wait(wq) End。 Procedure finish_write。 Begin write_count。 If write_count0 Then signal(wq) Else signal(rq) End。 例 2. 讀者 /寫者問題 Begin reading_count:=0。 write_count:=0。 End。 Var rw:readers_writers。 讀者： 寫者： 。 。 {reading} {writing} 。 。 reading_count write_count rq wq rw: 例 3 嗜眠理發(fā)師問題 (Sleepy barber’s problem) … 凳子 (n個 ) 理發(fā)椅 理發(fā)室 例 3 嗜眠理發(fā)師問題 ? 一把理發(fā)椅 , 顧客理發(fā)時坐在理發(fā)椅上 , 由理發(fā)師為其理發(fā) . 沒有顧客時 ,理發(fā)師在理發(fā)椅上睡覺 。 ? N個凳子 , 顧客等待理發(fā)用 . 凳上坐滿顧客時 , 新進入的顧客退出理發(fā)室 . 例 3 嗜眠理發(fā)師問題 TYPE sleepybarber=MONITOR。 VAR chair:condition。 stool:condition。 count:0..n+1。 Define sleep, enter, leave。 Procedure sleep。 Begin If count=0 Then wait(chair) End。 例 3 嗜眠理發(fā)師問題 Procedure enter(var full:Boolean)。 Begin If count=n+1 Then full:=true。 Else Begin full:= false。 count:=count+1。 If count =1 Then signal(chair)。 Else wait(stool)。 End。 End。 例 3 嗜眠理發(fā)師問題 Procedure leave。 Begin count:=count1。 If count 0 Then signal(stool) End。 Begin count:=0。 End 例 3 嗜眠理發(fā)師問題 理發(fā)師活動 : Repeat 。 Cuthair。 Until false。 顧客活動 : Repeat (full)。 Until not full。 Cuthair 管程與 PV操作的等價性 用 PV操作可以構(gòu)造管程 用管程可以構(gòu)造 PV操作