【文章內(nèi)容簡介】 wait(Emutex)。 wait(Dmutex)。 若進(jìn)程 A和 B按下述次序交替執(zhí)行 wait process A: wait(Dmutex)。 于是 Dmutex=0 process B: wait(Emutex)。 于是 Emutex=0 process A: wait(Emutex)。 于是 Emutex=1 A process B: wait(Dmutex)。 于是 Dmutex=1 B阻塞 AND同步機(jī)制的基本思想是：將進(jìn)程在整個運(yùn)行過程中需要的所有資源 ， 一次性全部地分配給進(jìn)程 ， 待進(jìn)程使用完后再一起釋放 。 只要尚有一個資源未能分配給進(jìn)程 ，其它所有可能為之分配的資源 ， 也不分配給他 。 亦即 ， 對若干個臨界資源的分配 ， 采取原子操作方式：要么全部分配到進(jìn)程 ， 要么一個也不分配 。 由死鎖理論可知 ， 這樣就可避免上述死鎖情況的發(fā)生 。 為此 ， 在 wait操作中 ， 增加了一個 “ AND”條件 ， 故稱為 AND同步 ， 或稱為同時 wait操作 ， 即 Swait(Simultaneous wait)定義如下： Swait(S1, S2, …, Sn) if Si≥1 and … and Sn≥1 then for i ∶ = 1 to n do Si ∶ = Si1。 endfor else place the process in the waiting queue associated with the first Si found with Si＜ 1, and set the program count of this process to the beginning of Swait operation endif Ssignal(S 1, S 2, …, S n) for i∶ = 1 to n do Si=Si+1。 Remove all the process waiting in the queue associated with Si into the ready queue. endfor。 4. 信號量集 Swait(S1, t1, d1, …, Sn, tn, dn) if Si≥t1 and … and Sn≥tn then for i∶ =1 to n do Si∶ =Sidi。 endfor else Place the executing process in the waiting queue of the first Si with Si＜ ti and set its program counter to the beginning of the Swait Operation. endif signal(S1, d1, …, Sn, dn) for i ∶ =1 to n do Si ∶ = Si+di。 Remove all the process waiting in the queue associated with Si into the ready queue endfor。 一般 “ 信號量集 ” (1) Swait(S, d, d)。 此時在信號量集中只有一個信號量 S， 但允許它每次申請 d個資源 ， 當(dāng)現(xiàn)有資源數(shù)少于 d時 ， 不予分配 。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量 (S＞ 1時 )或互斥信號量 (S=1時 )。 (3) Swait(S, 1, 0)。 這是一種很特殊且很有用的信號量操作 。 當(dāng) S≥1時 ， 允許多個進(jìn)程進(jìn)入某特定區(qū)；當(dāng) S變?yōu)?0后 ，將阻止任何進(jìn)程進(jìn)入特定區(qū) 。 換言之 ， 它相當(dāng)于一個可控開關(guān) 。 信號量的應(yīng)用 1. 利用信號量實(shí)現(xiàn)進(jìn)程互斥 Var mutex:semaphore ∶ = 1。 begin parbegin process 1: begin repeat wait(mutex)。 critical section signal(mutex)。 remainder seetion until false。 end process 2: begin repeat wait(mutex)。 critical section signal(mutex)。 remainder section until false。 end parend 利用信號量實(shí)現(xiàn)前趨關(guān)系 圖 210 前趨圖舉例 S4S5S3S1S6S2 Var a,b,c,d,e,f,g。 semaphore ∶ = 0,0,0,0,0,0,0。 begin parbegin begin S1。 signal(a)。 signal(b)。 end。 begin wait(a)。 S2。 signal(c)。 signal(d)。 end。 begin wait(b)。 S3。 signal(e)。 end。 begin wait(c)。 S4。 signal(f)。 end。 begin wait(d)。 S5。 signal(g)。 end。 begin wait(e)。 wait(f)。 wait(g)。 S6。 end。 parend end 4 經(jīng)典進(jìn)程的同步問題 生產(chǎn)者 — 前面我們已經(jīng)對生產(chǎn)者 —消費(fèi)者問題 (The proceducerconsumer problem)做了一些描述 ， 但未考慮進(jìn)程的互斥與同步問題 ， 因而造成了數(shù)據(jù) Counter的不定性 。 由于生產(chǎn)者 —消費(fèi)者問題是相互合作的進(jìn)程關(guān)系的一種抽象 ， 例如 ， 在輸入時 ， 輸入進(jìn)程是生產(chǎn)者 ， 計算進(jìn)程是消費(fèi)者；而在輸出時 ， 則計算進(jìn)程是生產(chǎn)者 ， 而打印進(jìn)程是消費(fèi)者 ， 因此 ， 該問題有很大的代表性及實(shí)用價值 。 1. 利用記錄型信號量解決生產(chǎn)者 —消費(fèi)者問題 假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中 ， 具有 n個緩沖區(qū) ， 這時可利用互斥信號量 mutex實(shí)現(xiàn)諸進(jìn)程對緩沖池的互斥使用；利用信號量 empty和 full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量 。 又假定這些生產(chǎn)者和消費(fèi)者相互等效 ， 只要緩沖池未滿 ， 生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空 ， 消費(fèi)者便可從緩沖池中取走一個消息 。 對生產(chǎn)者 — 消費(fèi)者問題可描述如下： Var mutex, empty, full:semaphore ∶ = 1,n,0。 buffer:array［ 0, …, n1］ of item。 in, out: integer ∶ = 0, 0。 begin parbegin proceducer:begin repeat … producer an item nextp。 … wait(empty)。 wait(mutex)。 buffer(in) ∶ = nextp。 in ∶ = (in+1) mod n。 signal(mutex)。 signal(full)。 until false。 end consumer:begin repeat wait(full)。 wait(mutex)。 nextc ∶ = buffer(out)。 out ∶ = (out+1) mod n。 signal(mutex)。 signal(empty)。 consumer the item in nextc。 until false。 end parend end 在生產(chǎn)者 —消費(fèi)者問題中應(yīng)注意：首先 ， 在每個程序中用于實(shí)現(xiàn)互斥的 wait(mutex)和 signal(mutex)必須成對地出現(xiàn)； 其次 ， 對資源信號量 empty和 full的 wait和 signal操作 ， 同樣需要成對地出現(xiàn) ， 但它們分別處于不同的程序中 。 例如 ， wait(empty)在計算進(jìn)程中 ， 而 signal(empty)則在打印進(jìn)程中 ， 計算進(jìn)程若因執(zhí)行 wait(empty)而阻塞 ， 則以后將由打印進(jìn)程將它喚醒；最后 ， 在每個程序中的多個 wait操作順序不能顛倒 。 應(yīng)先執(zhí)行對資源信號量的wait操作 ， 然后再執(zhí)行對互斥信號量的 wait操作 ， 否則可能引起進(jìn)程死鎖 。 利用 AND信號量解決生產(chǎn)者 — 消費(fèi)者問題 ar mutex, empty, full:semaphore ∶ = 1, n, 0。 buffer:array［ 0, …, n1］ of item。 in out:integer ∶ = 0, 0。 begin parbegin producer:begin repeat … produce an item in nextp。 … Swait(empty, mutex)。 buffer(in) ∶ = nextp。 in ∶ = (in+1)mod n。 Ssignal(mutex, full)。 until false。 end consumer:begin repeat Swait(full, mutex)。 nextc ∶ = buffer(out)。 out ∶ = (out+1) mod n。 Ssignal(mutex, empty)。 consumer the item in nextc。 until false。 end parend end 哲學(xué)家進(jìn)餐問題 1. 經(jīng)分析可知 ， 放在桌子上的筷子是臨界資源 ， 在一段時間內(nèi)只允許一位哲學(xué)家使用 。 為了實(shí)現(xiàn)對筷子的互斥使用 ，可以用一個信號量表示一只筷子 ， 由這五個信號量構(gòu)成信號量數(shù)組 。 Var chopstick: array［ 0, …, 4］ of semaphore。 所有信號量均被初始化為 1， 第 i位哲學(xué)家的活動可描述為： repeat wait(chopstick［ i］ )。 wait(chopstick［ (i+1) mod 5］ )。 … eat。 … signal(chopstick［ i］ )。 signal(chopstick［ (i+1) mod 5］ )。 … think