【正文】 re: Var t,m,w,s:semaphore。 V(w)。 smoke。Sn,tn,dn)。 P(s)。 endloop endloop endloop 吸煙者問題 Solution Process A Process B Process C loop loop loop SP(m,1,1。 smoke。 procedure return(i:1..3)。 lp[i]:=used。 ? 缺點(diǎn)： ? 不甚靈活，效率略低 。 可根據(jù)需要定義多個(gè)，用于設(shè)置等待條件。 例 Type producer_consumer = MONITOR Var B:Array[0..n1]Of integer。 count++。 End。 Define start_read,finish_read, start_write,finish_write。 If reading_count=0 Then signal(wq) End。 End。 VAR chair:condition。 Else Begin full:= false。 If count 0 Then signal(stool) End。 Until not full。 例 3 嗜眠理發(fā)師問題 Procedure leave。 例 3 嗜眠理發(fā)師問題 Procedure enter(var full:Boolean)。 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ā)椅上睡覺 。 例 2. 讀者 /寫者問題 Begin reading_count:=0。 Procedure finish_read。 Var rq,wq: condition。 count。 B[in]:=item。 ? signal(c): ? 如 c鏈空，相當(dāng)空操作。 (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è)操作。 ? 管程： ? 集中式同步工具：共享變量及其所有相關(guān)操作集中在一個(gè)摸塊中。 if lp[i]=free then V(S)。 (initial value is 3) mutex: semaphore。 smoke。 SV(w,1。 (0,0,0) s:semaphore。 Simultaneous Poperation SP(S1,t1,d1。 P(t)。 V(w)。 B: possess match。 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。 :=1。 V(mutex)。 read_count: integer。 V(mutex)。 If read_count=1 Then P(r_w_w)。 Coend。 :=0。 P(mutex)。 S1,S2,mutex:semaphore。 =2。 Else V(mutex)。 x:=x1。 ? 只能執(zhí)行 P操作和 V操作，所有其它操作非法。 semaphore s。(why?) (2) 影響并發(fā)性。 do swap(amp。b:boolean){ int temp: boolean。 臨界區(qū) J=(i+1)%n。 int key。（初始 =0)。j++){ 5. While (choosing[j]) skip。 Resolution: 若抓到相同的號(hào)，按進(jìn)程編號(hào)依次進(jìn)入。 進(jìn)程互斥的實(shí)現(xiàn) ? Framework Repeat critical section remainder section Until false entry section exit section 進(jìn)程互斥的實(shí)現(xiàn) ? Requirements: ? mutual exclusion(互斥進(jìn)入 ): 一次只允許一個(gè)進(jìn)程進(jìn)入關(guān)于同一組公共變量的臨界區(qū) ； ? Progress(空閑讓進(jìn) ): 臨界區(qū)空閑時(shí)，放行一個(gè)進(jìn)入者 ； ? bounded waiting(有限等待 ): 一個(gè)想要進(jìn)入臨界區(qū)的進(jìn)程在等待有限個(gè)進(jìn)程進(jìn)入并離開臨界區(qū)后獲得進(jìn)入臨界區(qū)的機(jī)會(huì) 。 region B do region B do begin begin …… (訪問 B） …..（訪問 B） . end。 x:=x1。 ? （ 2） 非封閉性 ：一個(gè)進(jìn)程的運(yùn)行環(huán)境可能被其它進(jìn)程所改變，從而相互影響。 ? 在前趨圖中，沒有前趨的結(jié)點(diǎn)稱為 初始結(jié)點(diǎn) ，沒有后繼的結(jié)點(diǎn)稱為 終止結(jié)點(diǎn) 。 ? （ Pi， Pj） ∈→ 可記作 Pi→ Pj, 稱 Pi是 Pj的前趨， Pj是 Pi的后繼。 I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 并發(fā)程序及其特性 ? 不可再現(xiàn)性的例子 ? 進(jìn)程 P： 進(jìn)程 Q： ? A1: N:=0； B1: PRINT（ N）； ? A2: N:=N+1； B2: N:=0； ? A3: GOTO A2； B3: GOTO B1； ? 并發(fā)執(zhí)行結(jié)果不唯一 并發(fā)程序及其特性 ? 并發(fā)程序的特性 ? （ 1） 間斷性 ：程序交叉執(zhí)行。 與時(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。 一組公共變量 CR1 CR2 CRn ……. 表示 共享變量 : shared 一組變量 臨界區(qū)域 : region 一組變量 do 語句＞ 例子： shared B:array[0,..,n1]of integer。 end。 Why? 為保證抓到不同的號(hào)，需要互斥機(jī)制。jn。 }. 對(duì)一組公共變量， int lock。 局部變量： int j。 waiting[i]=0。a,amp。 Pi進(jìn)入 ： key=1。 3. 硬件提供“關(guān)中斷”和“開中斷”指令 關(guān)中斷 { Critical Region} 開中斷 Remarks: (1) 開關(guān)中斷只在單 CPU系統(tǒng)中有效 。 }。 Primitive: a piece of code uninterruptible 規(guī)定和結(jié)論 ? 對(duì)于信號(hào)燈變量的規(guī)定： ? 必須置一次初值，只能置一次初值，初值 =0。 (initial value is 1) ? 終端 1： 終端 2： ? CYCLE CYCLE ? 等待借書者； 等待借書者； ? IF x=1 Then IF x=1 Then ? Begin Begin ? x:=x1。無書 。 (初值 =子資源個(gè)數(shù)） 例子： 2臺(tái)打印機(jī) Var S:semaphore。 Var B:Array[0,…,k1]Of item。 V(S2) end Procedure consumer cycle P(s2)。 程序