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