【正文】 (1) }While(1) 程序 Program producers_consumers。 =0。 Var S2:semaphore。 =2。 管理： Var S:semaphore。 (initial value 0) 司機活動： 售票員活動： Do{ Do{ P(S1) 關(guān)車門 啟動車輛 V(S1) 正常行駛 售 票 到站停車 P(S2) V(S2) 開車門 }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)者 /消費者問題 預(yù)備知識： 組合資源 ：若干相對獨立的資源構(gòu)成的資源集合，其中每個相對獨立的資源稱為子資源。 End End 用信號燈實現(xiàn)進程同步 后動作 先動作 P1: P2: 用信號燈實現(xiàn)進程同步 General Case: VAR S:semaphore。 Else V(mutex)。 V(mutex) V(mutex) 借書 借書 End End Else V(mutex)。 (initial value is 1) 終端 1： 終端 2： CYCLE CYCLE 等待借書者 ； 等待借書者 ； P(mutex) P(mutex) IF x=1 Then IF x=1 Then Begin Begin x:=x1。 Else 無書 。 x:=x1。 P(mutex) P(mutex) P(mutex) CR1 CR2 CRn V(mutex) V(mutex) V(mutex) …… 互斥例子：借書系統(tǒng) (revisited) ? Var mutex:semaphore。 CR1 CR2 CRn …… 用信號燈實現(xiàn)進程互斥 Var mutex: semaphore。 用信號燈實現(xiàn)進程互斥 Var mutex: semaphore。 ? 只能執(zhí)行 P操作和 V操作，所有其它操作非法。 If =0 Then wakeup() End wakeup() PCB出等待隊列，進入就緒隊列（狀態(tài)改為就緒）。 If 0 Then asleep() End asleep(): (1) 執(zhí)行此操作進程的 PCB入 （狀態(tài)改為等待）； (2) 轉(zhuǎn)處理機調(diào)度程序。 信號燈變量 PCB PCB PCB Var S:semaphore。 semaphore s。 PCBpointer queue。 ? 高效 。 P1: P2: synchronize 后 先 進程同步機制 ? 定義： 用于實現(xiàn)進程同步的工具稱為同步機制 （ synchronization mechanism） ? 同步機制要求： ? 描述能力夠用 。 P(1) parend。 turn:=0。 begin blocked[0]:=false。 Critical section blocked[id]:=false。 begin repeat blocked[id]:=true。 turn:0..1。 } lock=0。lock)。 while(b){ lock(bus)。 ? 多 CPU, 指令周期間交叉 , test_and_set, swap指令不是原子的 。(why?) (2) 影響并發(fā)性。 (3) swap實際上是：交換內(nèi)存兩個單元的內(nèi)容 。 Remarks： (1) test_and_set指令和 swap指令是原子的，不可中斷的 (在單 CPU情況下 )。key) while (key==1)。 do swap(amp。 對一個進程空間 ： int key。 }。 *a:=*b。b:boolean){ int temp: boolean。 其余部分 進程互斥的硬件實現(xiàn) 2. 硬件提供“交換”指令 void swap(int amp。 If(j==i) lock=0。amp。 臨界區(qū) J=(i+1)%n。lock)。amp。 key=1。 int key。 int lock。 滿足互斥性，進展性，不滿足有限等待性。lock)。（初始 =0)。 *target=1。 CS 滿足臨界區(qū)管理原則 ? 互斥性 ? 僅當(dāng) flag[i]==in_cs, 且對所有 j!=i, flag[j]!=in_cs時 , 進程 Pi才進入臨界區(qū)域 , 因而滿足互斥性 . ? 進展性 ? 臨界區(qū)空閑時 , 排在序列 turn, turn+1, … , n1,0,1, 2,… ,turn1最前面的申請進入臨界區(qū)的進程獲準(zhǔn)進入臨界區(qū) , 因而滿足進展性 . ? 有限等待性 ? 進程離開臨界區(qū)時 ,按循環(huán)次序 turn+1, … , n1,0,1, 2,… ,turn1確定唯一一個競爭進程為其后繼 , 所以一個進程最多等待 n1個進程進入并離開臨界區(qū)后一定能進入臨界區(qū) , 因而滿足有限等待性 . 進程互斥的硬件實現(xiàn) 1. 硬件提供“測試并建立”指令 int test_and_set(int amp。 turn=j。 Eisenberg/Mcguire算法 Pi離開： j=(turn+1)% n。 }while (j!=n)。 j=0。 While (j!=i) If (flag[j] != idle) j=turn Else j=(j+1)% n。 初始任意 0 i turn n1 先于 i 先于 i flag[i]==idle: 進程 Pi不想進入臨界區(qū) flag[i]==want_in: 進程 Pi想進入臨界區(qū) flag[i]==in_cs: 進程 Pi想進入或已進入臨界區(qū) Eisenberg/Mcguire算法 Pi進入 : Do{ flag[i]=want_in。 int turn。 情形 (2)編號最小抓到最小號的進程獲準(zhǔn)進入臨界區(qū) , 其它進程將在第一個 while循環(huán)或第二個 while循環(huán)處等待 , 因而滿足互斥性 . ? 進展性 (progress) ? 當(dāng)僅有一個進程想進入臨界區(qū)時 , 該進程可以立即進入 。 P2：抓到 1。j++){ 5. 6. While (number[j]!=0)and 7. (number[j],j)(number[i],i) skip。 3. 4. For(j=0。（ false) Int number[0,…,n1]。 6. While (number[j]!=0)and 7. (number[j],j)(number[i],i) skip。jn。 3. choosing[i]=false。 (0) Pi 進入 ： 1. choosing[i]=true。 Definition: (a,b)(c,d) iff (ac)or(a==c and bd) Lamport面包店算法 Boolean choosing[0,…,n1]。 Why? 為保證抓到不同的號，需要互斥機制。想進入臨界區(qū)的進程抓號，抓到號之后按由小到大的次序依次進入 。 其余代碼 }while(1)。 } 臨界區(qū) turn=0。 while (turn==0) skip。 P0： do{ flag[1]=1。 flag[0]=0。 flag[0]=1。 while(flag[1]) if(turn==1){ flag[0]=0。 (init 0) int turn。 其余代碼 }while(1)。 turn==0)。 while (flag[0] amp。 P1: Do{ flag[1]=true。 臨界區(qū) flag[0]=false。amp。 turn=1。 Int turn。 }while(1)。 flag[1]=false。 while(flag[0])。 flag[1]=true。 不滿足互斥性 : flag[0]=flag[1]=false. 嘗試 3 boolean flag[2]。 其余代碼 其余代碼 }while(1)。 臨界區(qū) 臨界區(qū) flag[0]=false。 flag[0]=true。 P0: P1: Do{ do{ while (flag[1]) 。 }while(1)。 turn=0。 while(turn==0)。 Busy waiting “運行”或“就緒” 嘗試 1 int turn。 ? 可用于單 CPU和多 CPU環(huán)境中。 進程互斥的實現(xiàn) ? Framework Repeat critical section remainder section Until false entry section exit section 進程互斥的實現(xiàn) ? Requirements: ? mutual exclusion(互斥進入 ): 一次只允