【正文】 mber[i],i)最小的進(jìn)程獲準(zhǔn)進(jìn)入 , 因而確定進(jìn)入臨界區(qū)進(jìn)程的決策將在有限時(shí)間內(nèi)確定 . ? 有限等待性 (bounded waiting) ? 對(duì)任意一個(gè)想要進(jìn)入臨界區(qū)的進(jìn)程 Pi, 設(shè)其抓到號(hào)碼為number[i], 按二元組 (number[i],i)次序排在 Pi之前的競(jìng)爭(zhēng)進(jìn)程數(shù)量是有限的 , 在最壞情況下 Pi將等待 n1個(gè)排在其前面的進(jìn)程進(jìn)入并離開(kāi)臨界區(qū)后獲得進(jìn)入臨界區(qū)的資格 , 因而滿足有限等待性 . 滿足臨界區(qū)管理原則 ? 互斥性 ? 僅當(dāng) flag[i]==in_cs, 且對(duì)所有 j!=i, flag[j]!=in_cs時(shí) , 進(jìn)程 Pi才進(jìn)入臨界區(qū)域 , 因而滿足互斥性 . ? 進(jìn)展性 ? 臨界區(qū)空閑時(shí) , 排在序列 turn, turn+1, … , n1,0,1, 2,… ,turn1最前面的申請(qǐng)進(jìn)入臨界區(qū)的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 因而滿足進(jìn)展性 . ? 有限等待性 ? 進(jìn)程離開(kāi)臨界區(qū)時(shí) ,按循環(huán)次序 turn+1, … , n1,0,1, 2,… ,turn1確定唯一一個(gè)競(jìng)爭(zhēng)進(jìn)程為其后繼 , 所以一個(gè)進(jìn)程最多等待 n1個(gè)進(jìn)程進(jìn)入并離開(kāi)臨界區(qū)后一定能進(jìn)入臨界區(qū) , 因而滿足有限等待性 . 進(jìn)程互斥的硬件實(shí)現(xiàn) 1. 硬件提供“測(cè)試并建立”指令 int test_and_set(int amp。 滿足互斥性，進(jìn)展性，不滿足有限等待性。amp。 If(j==i) lock=0。 }。 Remarks： (1) test_and_set指令和 swap指令是原子的，不可中斷的 (在單 CPU情況下 )。 ? 高效 。 If 0 Then asleep() End asleep(): (1) 執(zhí)行此操作進(jìn)程的 PCB入 （狀態(tài)改為等待）； (2) 轉(zhuǎn)處理機(jī)調(diào)度程序。 CR1 CR2 CRn …… 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥 Var mutex: semaphore。 (initial value is 1) 終端 1： 終端 2： CYCLE CYCLE 等待借書(shū)者 ； 等待借書(shū)者 ； P(mutex) P(mutex) IF x=1 Then IF x=1 Then Begin Begin x:=x1。 (initial value 0) 司機(jī)活動(dòng)： 售票員活動(dòng)： Do{ Do{ P(S1) 關(guān)車門(mén) 啟動(dòng)車輛 V(S1) 正常行駛 售 票 到站停車 P(S2) V(S2) 開(kāi)車門(mén) }While(1) }While(1) Classical synchronization problems 1. Producers and consumers problem 2. Readers and writers problem 3. Dining philosophers problem 4. Cigarette smokers problem 5. Sleepy barbers problem etc. 例 1. 生產(chǎn)者 /消費(fèi)者問(wèn)題 預(yù)備知識(shí)： 組合資源 ：若干相對(duì)獨(dú)立的資源構(gòu)成的資源集合，其中每個(gè)相對(duì)獨(dú)立的資源稱為子資源。 =0。 B[in]:=product。 V(S1)。 Cobegin P1: producer。 P(r_w_w) {讀操作 } {寫(xiě)操作 } V(r_w_w)。 Solution3: 正確解法 Var mutex:semaphore。 V(mutex)。 程序（ Cont.） Procedure reader。 V(mutex)。 w1: writer。 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。 P(s)。 Process A Process B process C P(m)。 smoke?！?。 SV(t,1。 SP(t,1,1。 V(s)。 P(mutex)。 return(i)。 ………… 管程形式 (Cont.) Function 函數(shù)名（形參表） :返回值類型； 局部變量說(shuō)明 Begin 語(yǔ)句序列 End。 ? 離開(kāi)管程： ? 如緊急等待隊(duì)列非空，喚醒第一個(gè)等待者；否則開(kāi)放管程。 pq, cq:condition。 End。 out:=0。 Begin If write_count0 Then wait(rq)。 If (write_count1) or (reading_count0) Then wait(wq) End。 讀者： 寫(xiě)者： 。 count:0..n+1。 If count =1 Then signal(chair)。 End 例 3 嗜眠理發(fā)師問(wèn)題 理發(fā)師活動(dòng) : Repeat 。 Until false。 End。 Procedure sleep。 {reading} {writing} 。 Begin write_count。 signal(rq)。 End。 item:=B[out]。 Procedure put_in(item:integer)。 ? wait(c): ? 如緊急隊(duì)列非空，喚醒第一個(gè)等待者，否則釋放管程互斥權(quán) 。 語(yǔ)言特點(diǎn)： (1) modularized。 ? 缺點(diǎn)： ? 可讀性差； ? 正確性不易保證； ? 不易修改。 lp[i]:=free。 endloop endloop endloop 例 5. 3臺(tái)打印機(jī)管理 Var lp:array[1..3]of (free,used)。 t,1,1)。 SV(m,1。 i=n。 V(s)。 P(t)。 V(t)。 Y: supplies match and wrapper。 wn: writer coend end. 分析： 問(wèn)題 ：讀者源源不斷， read_count不歸 0，寫(xiě)者會(huì)被餓死。 程序（ Cont.） begin read_count:=0。 read_count:=read_count+1。 Var r_w_w: semaphore。 read_count:=read_count+1。 改進(jìn)：最先進(jìn)入的 R執(zhí)行 P；最后離開(kāi)的 R執(zhí)行 V； Solution2: 考慮 RR不互斥 Var read_count:integer。 C1: consumer。 end。 V(mutex)。 (=1) 互斥 生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)： Do{ Do{ 加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品 物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗這件物品 }While(1) }While(1) 程序 Program producers_consumers。 管理： Var S:semaphore。 V(mutex) V(mutex) 借書(shū) 借書(shū) End End Else V(mutex)。 P(mutex) P(mutex) P(mutex) CR1 CR2