【正文】 :: a piece of code uninterruptible V操作原語 V操作原語： Procedure V(var s:semaphore) :=+1。 (初值 =1） shared x,y,z:integer。 x:=x1。 同種組合資源 ：相同類型子資源構(gòu)成的組合資源。 放前： P（ S1） 取前： P（ S2） 放后： V（ S2） 取后： V（ S1） 同步 生產(chǎn)者活動(dòng) ： 消費(fèi)者活動(dòng) ： Do{ Do{ 加工一件物品 P(S2) P(S1) 箱中取一物品 物品放入箱中 V(S1) V(S2) 消耗這件物品 }While(1) }While(1) 對(duì) B和 in,out的互斥 ： Var mutex:semaphore。 in:=(in+1)mod k。 consume x。 …… , Pm: producer。 V(r_w_w) 分析：（ 1）寫者活動(dòng)正確；（ 2） RR不能同時(shí)。 (initial value is 1) Reader: P(mutex)。 讀者等待在何處？ 讀者如何被喚醒？ 程序 Program readers_writers。 begin P(mutex)。 end。 ,。 就餐條件測(cè)試 測(cè)試 I號(hào)哲學(xué)家是否具備進(jìn)食條件： Procedure test(I:0..4) If (state[I]=hungry) and (state[(I1)mod 5]eating) and (state[(I+1)mod 5]eating) Then state[I]:=eating。 共享變量： state。 12. state[I]:=thinking。 procedure test(I:0..4) begin if (state[I]=hungry)and (state[(I1)mod 5]eating) and(state[(I+1)mod 5]eating) then begin state[I]:=eating。pick_up_fork((I+1)mod 5)。 V(mutex)。 Z: supplies wrapper and tobacco. 3 smoker processes: A: possess tobacco。 V(m)。 P(w)。 V(s)。 i++) Si = Si+di； Remove all processes waiting in the queue associated with Si into ready queue； } 吸煙者問題 Solution Shared t,w,m:semaphore。w,1)。 m,1,1)。 (initial value is free) S: semaphore。 for i:=1 to 3 do V(mutex)。 (車架， 0) Semaphore wheel。 V(mutex)。 P(S)。 V(s)。 SP(w,1,1。 P(s)。 if S1=t1 and … and Sn=tn then for I:=1 to n do Si:=Sidi endfor else (1) place the executing process in the waiting queue for the first Si with Siti, (2)and set the program counter to the beginning of the SP operation so that all conditions will be reexamined when the process is reactivated. Simultaneous Voperation SV(S1,d1。 smoke。 V(t)。 (0,0,0,1) Process X process Y process Z P(s)。 cobegin ph0: philosopher(0)。 P(mutex)。 test(I)。 問題 餓死情況： 某哲學(xué)家左右鄰居至少有一個(gè)處于 eating狀態(tài)。 5. test(I)。 5. P(self[I])。 例 3. 哲學(xué)家就餐問題 Room ph0 ph4 ph3 ph2 ph1 f0 f4 f3 f2 f1 死鎖預(yù)防策略 死鎖解決方法：同時(shí)申請(qǐng)左、右兩把叉子（預(yù)先分配）。 cobegin r1: reader。 { read ops } P(mutex)。 procedure writer。 {讀操作 } P(mutex)。 {讀操作 } read_count:=read_count1。 End. 并發(fā)性提高策略 生產(chǎn)者和消費(fèi)者：不操作 B的相同分量 生產(chǎn)者的共享變量 ： B[in], in 消費(fèi)者的共享變量 ： B[out], out in=out: 滿或空 , Var mutex1,mutex2:semaphore。 :=1。 x:=B[out]。 in,out:0..k1。 申請(qǐng)： P（ S）； 釋放： V（ S）； 自動(dòng)機(jī)描述 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ù) =空 ||=等待進(jìn)程數(shù) 空閑資源數(shù) =0 ... P(S): 申請(qǐng)一臺(tái)打印機(jī) , 分配 , 空閑打印機(jī)減 1 P(S): 申請(qǐng)一臺(tái)打印機(jī) , 等待 , 等待進(jìn)程數(shù)加 1 2 自動(dòng)機(jī)描述 … 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ù) =空 ||=等待進(jìn)程數(shù) 空閑資源數(shù) =0 ... V(S): 釋放一臺(tái)打印機(jī) , 喚醒一個(gè)等待者 , 打印機(jī)分給被喚醒進(jìn)程 , 等待進(jìn)程數(shù)減 1 V(S): 釋放一臺(tái)打印機(jī) , 空閑打印機(jī)數(shù)量增 1 例 1. 生產(chǎn)者 /消費(fèi)者問題 0 1 …… k 1 箱子，容量 k B:Array[0..k1]Of item 生產(chǎn)者 消費(fèi)者 生產(chǎn)物品 放入 B中 B中取物品 消費(fèi)之 環(huán)形緩沖區(qū) 1 0 K1 in (in+1)mod k out (out+1)mod k 問題分析 生產(chǎn)者活動(dòng) ： 消費(fèi)者活動(dòng) ： do{ do{ 加工一件物品 箱中取一物品 物品放入箱中 消耗這件物品 }while(1) }while(1) 資源：箱子（同種組合） 資源：物品（同種組合） Var S1:semaphore。無書 。 ? ? 借書 借書 ? End End ? Else 無書 。 ? 幾個(gè)有用的結(jié)論 ： ? 當(dāng) =0時(shí)， ； ? 當(dāng) 0時(shí)， ||為隊(duì)列 ； ? 當(dāng) =1時(shí)，可以實(shí)現(xiàn)進(jìn)程互斥； ? 當(dāng) =0時(shí)，可以實(shí)現(xiàn)進(jìn)程同步。 Remarks: (1) semaphore is predefined data type, (2) s can be declared as needed, eg. semaphore s1,s2。 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. 進(jìn)程同步 進(jìn)程同步的概念 例：司機(jī) 售票員問題 司機(jī)活動(dòng)： 售票員活動(dòng)： do{ do{ 啟動(dòng)車輛 關(guān)車門 正常行駛 售 票 到站停車 開車門 }while(1) }while(1) 進(jìn)程同步的概念 定義： 一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點(diǎn)處需要相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為進(jìn)程同步。 while turnid do begin while blocked[1id] do {nothing} turn:=id end。 b = test_and_set(amp。 (2) test_and_set實(shí)際上是：將內(nèi)存中一個(gè)單元的內(nèi)容取出，再送一個(gè)新值。 對(duì) 一組公共變量 ： int lock (初始 =0)。 Else waiting[j]=0。key) key=test_and_set(amp。 進(jìn)程互斥的硬件實(shí)現(xiàn) 滿足有限等待性： 全局變量： int waiting[n]。target){ test_and_set=target。 While (jn)and(j==i or flag[j]!=in_cs) do j++。 當(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ìng)爭(zhēng)進(jìn)程數(shù)量是有限的 , 在最壞情況下 Pi將等待 n1個(gè)排在其前面的進(jìn)程進(jìn)入并離開臨界區(qū)后獲得進(jìn)入臨界區(qū)的資格 , 因而滿足有限等待性 . Eisenberg/Mcguire算法 enum flag[0,…,n1] (idle, want_in, in_cs)。 (0) Pi 進(jìn)入 ： 1. 2. number[i]=max{number[0],…