【正文】 Until not full。 Until false。 End 例 3 嗜眠理發(fā)師問題 理發(fā)師活動(dòng) : Repeat 。 If count 0 Then signal(stool) End。 例 3 嗜眠理發(fā)師問題 Procedure leave。 End。 If count =1 Then signal(chair)。 Else Begin full:= false。 例 3 嗜眠理發(fā)師問題 Procedure enter(var full:Boolean)。 Procedure sleep。 count:0..n+1。 VAR chair:condition。 reading_count write_count rq wq rw: 例 3 嗜眠理發(fā)師問題 (Sleepy barber’s problem) … 凳子 (n個(gè) ) 理發(fā)椅 理發(fā)室 例 3 嗜眠理發(fā)師問題 ? 一把理發(fā)椅 , 顧客理發(fā)時(shí)坐在理發(fā)椅上 , 由理發(fā)師為其理發(fā) . 沒有顧客時(shí) ,理發(fā)師在理發(fā)椅上睡覺 。 {reading} {writing} 。 讀者： 寫者： 。 End。 例 2. 讀者 /寫者問題 Begin reading_count:=0。 Begin write_count。 If (write_count1) or (reading_count0) Then wait(wq) End。 If reading_count=0 Then signal(wq) End。 Procedure finish_read。 signal(rq)。 Begin If write_count0 Then wait(rq)。 Define start_read,finish_read, start_write,finish_write。 Var rq,wq: condition。 End。 out:=0。 End。 count。 item:=B[out]。 End。 count++。 B[in]:=item。 Procedure put_in(item:integer)。 pq, cq:condition。 例 Type producer_consumer = MONITOR Var B:Array[0..n1]Of integer。 ? signal(c): ? 如 c鏈空，相當(dāng)空操作。 ? wait(c): ? 如緊急隊(duì)列非空，喚醒第一個(gè)等待者，否則釋放管程互斥權(quán) 。 ? 離開管程： ? 如緊急等待隊(duì)列非空，喚醒第一個(gè)等待者；否則開放管程。 可根據(jù)需要定義多個(gè)，用于設(shè)置等待條件。 (3) information hiding. 管程語義 ? 管程的共享變量在管程外部不可見 ， 外部只能通過調(diào)用管程中的外部子程序訪問共享變量； ? 為保證對(duì)共享變量操作的數(shù)據(jù)完整性， 規(guī)定管程互斥進(jìn)入 ； ? 管程中有等待 /喚醒機(jī)制，等待時(shí)釋放管程的互斥權(quán)，喚醒時(shí)（ P喚醒 Q）： ? P等待， Q繼續(xù)，直到 Q退出或等待； (Hoare) ? Q等待， P繼續(xù)，直到 P退出或等待； (Java) ? Signal and continue ? 被喚醒進(jìn)程需要重新檢查等待條件 ,可能再次等待 . ? 喚醒是管程中可執(zhí)行的最后一個(gè)操作。 語言特點(diǎn)： (1) modularized。 ………… 管程形式 (Cont.) Function 函數(shù)名（形參表） :返回值類型； 局部變量說明 Begin 語句序列 End。 ? 缺點(diǎn)： ? 不甚靈活，效率略低 。 ? 管程： ? 集中式同步工具：共享變量及其所有相關(guān)操作集中在一個(gè)摸塊中。 ? 缺點(diǎn)： ? 可讀性差； ? 正確性不易保證； ? 不易修改。 return(i)。 lp[i]:=used。 if lp[i]=free then V(S)。 lp[i]:=free。 P(mutex)。 procedure return(i:1..3)。 (initial value is 3) mutex: semaphore。 endloop endloop endloop 例 5. 3臺(tái)打印機(jī)管理 Var lp:array[1..3]of (free,used)。 V(s)。 smoke。 smoke。 t,1,1)。 SP(t,1,1。 endloop endloop endloop 吸煙者問題 Solution Process A Process B Process C loop loop loop SP(m,1,1。 SV(w,1。 SV(m,1。 SV(t,1。 P(s)。 (0,0,0) s:semaphore。 i=n?！?。Sn,tn,dn)。 Simultaneous Poperation SP(S1,t1,d1。 V(s)。 smoke。 smoke。 P(t)。 P(t)。 Process A Process B process C P(m)。 V(w)。 V(w)。 V(t)。 P(s)。 (2) X,Y,Z can proceed only after consumption. Traditional semaphore: Var t,m,w,s:semaphore。 B: possess match。 Y: supplies match and wrapper。 P(count) P(fork[i]) P(fork[i+1] mod 5) EAT V(fork[i+1] mod 5) V(fork[i]) V(count) until false end。 死鎖情況 ：每位哲學(xué)家拿到左叉，等待右叉。 Further improvement is left to interested students. 例 3. 哲學(xué)家就餐問題 Dining Philosophers Problem Proposed and solved by . Dijkstra, in 1965 例 3. 哲學(xué)家就餐問題 Room ph0 ph4 ph3 ph2 ph1 f0 f4 f3 f2 f1 例 3. 哲學(xué)家就餐問題 哲學(xué)家問題的解法： VAR fork Array [0..4] of Semophore=(1,1,1,1,1) philosopher(i): begin repeat THINK。 wn: writer coend end. 分析： 問題 ：讀者源源不斷， read_count不歸 0，寫者會(huì)被餓死。 w1: writer。 ……。 :=1。 程序（ Cont.） begin read_count:=0。 V(mutex)。 read_count:=read_count1。 V(mutex)。 read_count:=read_count+1。 程序（ Cont.） Procedure reader。 begin P(r_w_w)。 read_count: integer。 Var r_w_w: semaphore。 V(mutex)。 read_count:=read_count1。 V(mutex)。 read_count:=read_count+1。 Solution3: 正確解法 Var mutex:semaphore。 If read_count=0 Then V(r_w_w)。 If read_count=1 Then P(r_w_w)。 改進(jìn)：最先進(jìn)入的 R執(zhí)行 P；最后離開的 R執(zhí)行 V； Solution2: 考慮 RR不互斥 Var read_count:integer。 P(r_w_w) {讀操作 } {寫操作 } V(r_w_w)。 (init 1) 并發(fā)性提高策略 生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)： Repeat Repeat 加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1)