【正文】 相對(duì)獨(dú)立的資源稱為子資源。 CR1 CR2 CRn …… 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥 Var mutex: semaphore。 ? 高效 。 }。amp。 當(dāng)有多個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)其二元組 (number[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ìn)程數(shù)量是有限的 , 在最壞情況下 Pi將等待 n1個(gè)排在其前面的進(jìn)程進(jìn)入并離開臨界區(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)程離開臨界區(qū)時(shí) ,按循環(huán)次序 turn+1, … , n1,0,1, 2,… ,turn1確定唯一一個(gè)競爭進(jìn)程為其后繼 , 所以一個(gè)進(jìn)程最多等待 n1個(gè)進(jìn)程進(jìn)入并離開臨界區(qū)后一定能進(jìn)入臨界區(qū) , 因而滿足有限等待性 . 進(jìn)程互斥的硬件實(shí)現(xiàn) 1. 硬件提供“測試并建立”指令 int test_and_set(int amp。 Lamport面包店算法 算法思想 ：設(shè)置一個(gè)發(fā)號(hào)者，按 0,1,2,…, 發(fā)號(hào)。 必須去掉導(dǎo)致不正確結(jié)果的交叉。 ? 例 : 輸入 (I)、計(jì)算 (C)、打印 (P)三個(gè)活動(dòng)構(gòu)成的進(jìn)程，每個(gè)進(jìn)程的內(nèi)部活動(dòng)是順序的，即 Ii→ Ci→ Pi，多個(gè)進(jìn)程的活動(dòng)也是順序的。 ? S1： a:=x+y ? S2： b:=az ? S3： c:=a+b ? S4： d:=c+5 S1 S2 S3 S4 ? (2)外部順序性 ：對(duì)于多個(gè)進(jìn)程來說，所有進(jìn)程的活動(dòng)是依次執(zhí)行的。 Remarks: 某些交叉結(jié)果不正確 。 ? 有忙式等待問題。 情形 (2)編號(hào)最小抓到最小號(hào)的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 其它進(jìn)程將在第一個(gè) while循環(huán)或第二個(gè) while循環(huán)處等待 , 因而滿足互斥性 . ? 進(jìn)展性 (progress) ? 當(dāng)僅有一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí) , 該進(jìn)程可以立即進(jìn)入 。 While(waiting[i]amp。 *b:=temp。 ? 可實(shí)現(xiàn) 。 (初值 =1） shared x,y,z:integer。 (initial value 0) P(S) 后動(dòng)作 先動(dòng)作 V(S) P1: P2: 用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步 ? 例子：司機(jī) 售票員問題： ? 司機(jī)活動(dòng)： 售票員活動(dòng)： ? Do{ Do{ ? 關(guān)車門 ? 啟動(dòng)車輛 ? 正常行駛 售 票 ? 到站停車 ? 開車門 ? }While(1) }While(1) 用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步 例子：司機(jī) 售票員問題： VAR s1,s2: semaphore。 P(mutex)。 out:=0。 問題：對(duì) Read_count操作的互斥問題。 { write ops } V(r_w_w) end。 rm: reader。 (0,0,0,1) Process X process Y process Z P(s)。 smoke。 P(s)。 V(s)。 V(mutex)。 管程隊(duì)列 PCB PCB … c1 PCB PCB … c2 PCB PCB … PCB PCB … 入口隊(duì)列 緊急隊(duì)列 Monitor 管程成分 PCB PCB … c1 PCB PCB … c2 PCB PCB … PCB PCB … 入口隊(duì)列 緊急隊(duì)列 初始化代碼 共享變量 操作 操作 操作 … 進(jìn)入與離開 ? 進(jìn)入管程： ? 申請(qǐng)管程互斥權(quán)。 signal(cq)。 例 2. 讀者 /寫者問題 Procedure start_read。 Var rw:readers_writers。 count:=count+1。 顧客活動(dòng) : Repeat (full)。 Begin If count=0 Then wait(chair) End。 If write_count0 Then signal(wq) Else signal(rq) End。 例 2. 讀者 /寫者問題 寫者優(yōu)先 Type readers_writers = Monitor。 Begin If(count==n)Then wait(pq)。 (2) abstract data type。 for i:=1 to 3 do V(mutex)。 m,1,1)。 i++) Si = Si+di； Remove all processes waiting in the queue associated with Si into ready queue； } 吸煙者問題 Solution Shared t,w,m:semaphore。 P(w)。 Z: supplies wrapper and tobacco. 3 smoker processes: A: possess tobacco。 :=1。 mutex:semaphore。 (initial value is 0) Reader: read_count:=read_count+1。 程序 Begin :=k。 Var B:Array[0,…,k1]Of item。無書 。 Primitive: a piece of code uninterruptible 規(guī)定和結(jié)論 ? 對(duì)于信號(hào)燈變量的規(guī)定： ? 必須置一次初值，只能置一次初值，初值 =0。 3. 硬件提供“關(guān)中斷”和“開中斷”指令 關(guān)中斷 { Critical Region} 開中斷 Remarks: (1) 開關(guān)中斷只在單 CPU系統(tǒng)中有效 。a,amp。 局部變量： int j。jn。 end。 與時(shí)間有關(guān)的錯(cuò)誤 例：圖書借閱系統(tǒng) （ x:某種 書冊(cè)數(shù)，設(shè)當(dāng)前 x=1.） 終端 1： 終端 2： CYCLE CYCLE 等待借書者； 等待借書者； IF x=1 Then IF x=1 Then Begin Begin x:=x1。 ? （ Pi， Pj） ∈→ 可記作 Pi→ Pj, 稱 Pi是 Pj的前趨， Pj是 Pi的后繼。 ? （ 2） 非封閉性 ：一個(gè)進(jìn)程的運(yùn)行環(huán)境可能被其它進(jìn)程所改變，從而相互影響。 region B do region B do begin begin …… (訪問 B） …..（訪問 B） . end。 Resolution: 若抓到相同的號(hào)，按進(jìn)程編號(hào)依次進(jìn)入。（初始 =0)。 臨界區(qū) J=(i+1)%n。 do swap(amp。 semaphore s。 x:=x1。 =2。 P(mutex)。 Coend。 V(mutex)。 V(mutex)。 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。 V(w)。 Simultaneous Poperation SP(S1,t1,d1。 SV(w,1。 (initial value is 3) mutex: semaphore。 ? 管程： ? 集中式同步工具：共享變量及其所有相關(guān)操作集中在一個(gè)摸塊中。 ? signal(c): ? 如 c鏈空，相當(dāng)空操作。 count。 Procedure finish_read。 reading_count write_count rq wq rw: 例 3 嗜眠理發(fā)師問題 (Sleepy barber’s pro