【文章內容簡介】 ar mutex:semaphore。 (initial value is 1) 終端 1： 終端 2： CYCLE CYCLE 等待借書者 ； 等待借書者 ； P(mutex) P(mutex) IF x=1 Then IF x=1 Then Begin Begin x:=x1。 x:=x1。 V(mutex) V(mutex) 借書 借書 End End Else V(mutex)。無書 。 Else V(mutex)。無書 。 End End 用信號燈實現(xiàn)進程同步 后動作 先動作 P1: P2: 用信號燈實現(xiàn)進程同步 General Case: VAR S:semaphore。 (initial value 0) P(S) 后動作 先動作 V(S) P1: P2: 用信號燈實現(xiàn)進程同步 ? 例子：司機 售票員問題： ? 司機活動： 售票員活動： ? Do{ Do{ ? 關車門 ? 啟動車輛 ? 正常行駛 售 票 ? 到站停車 ? 開車門 ? }While(1) }While(1) 用信號燈實現(xiàn)進程同步 例子：司機 售票員問題： VAR s1,s2: semaphore。 (initial value 0) 司機活動： 售票員活動： Do{ Do{ P(S1) 關車門 啟動車輛 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. 生產者 /消費者問題 預備知識： 組合資源 ：若干相對獨立的資源構成的資源集合，其中每個相對獨立的資源稱為子資源。 同種組合資源 ：相同類型子資源構成的組合資源。 管理： Var S:semaphore。 (初值 =子資源個數(shù)） 例子： 2臺打印機 Var S:semaphore。 =2。 申請： P（ S）； 釋放： V（ S）； 例 1. 生產者 /消費者問題 0 1 …… k 1 箱子，容量 k B:Array[0..k1]Of item 生產者 消費者 生產物品 放入 B中 B中取物品 消費之 環(huán)形緩沖區(qū) 1 0 K1 in (in+1)mod k out (out+1)mod k 問題分析 生產者活動 ： 消費者活動 ： do{ do{ 加工一件物品 箱中取一物品 物品放入箱中 消耗這件物品 }while(1) }while(1) 資源：箱子（同種組合） 資源：物品（同種組合） Var S1:semaphore。 Var S2:semaphore。 =k。 =0。 放前： P（ S1） 取前： P（ S2） 放后： V（ S2） 取后： V（ S1） 同步 生產者活動 ： 消費者活動 ： Do{ Do{ 加工一件物品 P(S2) P(S1) 箱中取一物品 物品放入箱中 V(S1) V(S2) 消耗這件物品 }While(1) }While(1) 對 B和 in,out的互斥 ： Var mutex:semaphore。 (=1) 互斥 生產者活動： 消費者活動： 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 B:Array[0,…,k1]Of item。 S1,S2,mutex:semaphore。 in,out:0..k1。 Procedure producer cycle produce a product P(S1)。 P(mutex)。 B[in]:=product。 in:=(in+1)mod k。 V(mutex)。 V(S2) end Procedure consumer cycle P(s2)。 P(mutex)。 x:=B[out]。 out:=(out+1)mod k。 V(mutex)。 V(S1)。 consume x。 end。 程序 Begin :=k。 :=0。 :=1。 in:=0。 out:=0。 Cobegin P1: producer。 …… , Pm: producer。 C1: consumer。 ……, Cn: consumer。 Coend。 End. 并發(fā)性提高策略 生產者和消費者：不操作 B的相同分量 生產者的共享變量 ： B[in], in 消費者的共享變量 ： B[out], out in=out: 滿或空 , Var mutex1,mutex2:semaphore。 (init 1) 并發(fā)性提高策略 生產者活動： 消費者活動： Repeat Repeat 加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品 物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗這件物品 Until false Until false 例 2. 讀者 /寫者問題 P. T. Courtois 1971 Communication of the ACM, , 667669. ACM: Association for Computing Machinery 解法 1：寫者可能餓死 解法 2：寫者優(yōu)先 例 2. 讀者 /寫者問題 Problem Statement: 一組公共數(shù)據 DB R1 …… Rm W1 …... Wn 要求 ：（ 1） R