【文章內(nèi)容簡介】 lock=0。 CR 作業(yè) 2 Consider the following program: var blocked: array[0..1]of boolean。 turn:0..1。 procedure P(id:integer)。 begin repeat blocked[id]:=true。 while turnid do begin while blocked[1id] do {nothing} turn:=id end。 Critical section blocked[id]:=false。 Remainder until false end。 begin blocked[0]:=false。 blocked[1]:=false。 turn:=0。 parbegin P(0)。 P(1) parend。 end. This is a software solution to the mutual exclusion problem proposed by Hyman. Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was fooled on this one. 進程同步 進程同步的概念 例：司機 售票員問題 司機活動： 售票員活動： do{ do{ 啟動車輛 關(guān)車門 正常行駛 售 票 到站停車 開車門 }while(1) }while(1) 進程同步的概念 定義： 一組進程，為協(xié)調(diào)其推進速度，在某些關(guān)鍵點處需要相互等待與相互喚醒，進程之間這種相互制約的關(guān)系稱為進程同步。 P1: P2: synchronize 后 先 進程同步機制 ? 定義： 用于實現(xiàn)進程同步的工具稱為同步機制 （ synchronization mechanism） ? 同步機制要求： ? 描述能力夠用 。 ? 可實現(xiàn) 。 ? 高效 。 ? 使用方便 . 典型同步機制 ? 信號燈與 PV操作 (semaphore and PV operations) ? 管程 (monitor) ? 會合 (rendezvous) ? 條件臨界區(qū) (conditional critical region) ? 路徑表達式 (path expression) ? 事件 (event,traditional UNIX) 信號燈與 PV操作 , 1965. 信號燈與 PV操作的定義 Typedef semaphore struct{ int value。 PCBpointer queue。 }。 semaphore s。 Remarks: (1) semaphore is predefined data type, (2) s can be declared as needed, eg. semaphore s1,s2。 信號燈變量 PCB PCB PCB Var S:semaphore。 FIFO P操作原語 P操作原語： Procedure P(var s:semaphore) :=。 If 0 Then asleep() End asleep(): (1) 執(zhí)行此操作進程的 PCB入 （狀態(tài)改為等待）； (2) 轉(zhuǎn)處理機調(diào)度程序。 Primitive:: a piece of code uninterruptible V操作原語 V操作原語： Procedure V(var s:semaphore) :=+1。 If =0 Then wakeup() End wakeup() PCB出等待隊列，進入就緒隊列（狀態(tài)改為就緒）。 Primitive: a piece of code uninterruptible 規(guī)定和結(jié)論 ? 對于信號燈變量的規(guī)定： ? 必須置一次初值，只能置一次初值，初值 =0。 ? 只能執(zhí)行 P操作和 V操作，所有其它操作非法。 ? 幾個有用的結(jié)論 ： ? 當 =0時， ； ? 當 0時， ||為隊列 ； ? 當 =1時，可以實現(xiàn)進程互斥； ? 當 =0時，可以實現(xiàn)進程同步。 用信號燈實現(xiàn)進程互斥 Var mutex: semaphore。 (初值 =1） shared x,y,z:integer。 CR1 CR2 CRn …… 用信號燈實現(xiàn)進程互斥 Var mutex: semaphore。 (初值 =1） shared x,y,z:integer。 P(mutex) P(mutex) P(mutex) CR1 CR2 CRn V(mutex) V(mutex) V(mutex) …… 互斥例子：借書系統(tǒng) (revisited) ? Var mutex:semaphore。 (initial value is 1) ? 終端 1： 終端 2： ? CYCLE CYCLE ? 等待借書者； 等待借書者； ? IF x=1 Then IF x=1 Then ? Begin Begin ? x:=x1。 x:=x1。 ? ? 借書 借書 ? End End ? Else 無書 。 Else 無書 。 ? End End 互斥例子：借書系統(tǒng) (revisited) Var 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{ ? 關(guān)車門 ? 啟動車輛 ? 正常行駛 售 票 ? 到站停車 ? 開車門 ? }While(1) }While(1) 用信號燈實現(xiàn)進程同步 例子：司機 售票員問題： VAR s1,s2: 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)者 /消費者問題 預備知識： 組合資源 ：若干相對獨立的資源構(gòu)成的資源集合，其中每個相對獨立的資源稱為子資源。 同種組合資源 ：相同類型子資源構(gòu)成的組合資源。 管理： Var S:semaphore。 (初值 =子資源個數(shù)） 例子： 2臺打印機 Var S:semaphore。 =2。 申請： P（ S）； 釋放： V（ S）； 自動機描述 2 … 1 0 1 2 P(S) P(S) P(S) P(S) P(S) V(S) V(S) V(S) V(S) V(S) =空閑資源數(shù) =空 ||=等待進程數(shù) 空閑資源數(shù) =0 ... P(S): 申請一臺打印機 , 分配 , 空閑打印機減 1 P(S): 申請一臺打印機 , 等待 , 等待進程數(shù)加 1 2 自動機描述 … 1 0 1 2 P(S) P(S) P(S) P(S) P(S) V(S) V(S) V(S) V(S) V(S) =空閑資源數(shù) =空 ||=等待進程數(shù) 空閑資源數(shù) =0 ... V(S): 釋放一臺打印機 , 喚醒一個等待者 , 打印機分給被喚醒進程 , 等待進程數(shù)減 1 V(S): 釋放一臺打印機 , 空閑打印機