【文章內容簡介】 wait(Emutex)。 wait(Dmutex)。 若進程 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同步機制的基本思想是：將進程在整個運行過程中需要的所有資源 ， 一次性全部地分配給進程 ， 待進程使用完后再一起釋放 。 只要尚有一個資源未能分配給進程 ，其它所有可能為之分配的資源 ， 也不分配給他 。 亦即 ， 對若干個臨界資源的分配 ， 采取原子操作方式：要么全部分配到進程 ， 要么一個也不分配 。 由死鎖理論可知 ， 這樣就可避免上述死鎖情況的發(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時 ， 不予分配 。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量 (S＞ 1時 )或互斥信號量 (S=1時 )。 (3) Swait(S, 1, 0)。 這是一種很特殊且很有用的信號量操作 。 當 S≥1時 ， 允許多個進程進入某特定區(qū)；當 S變?yōu)?0后 ，將阻止任何進程進入特定區(qū) 。 換言之 ， 它相當于一個可控開關 。 信號量的應用 1. 利用信號量實現進程互斥 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 利用信號量實現前趨關系 圖 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 經典進程的同步問題 生產者 — 前面我們已經對生產者 —消費者問題 (The proceducerconsumer problem)做了一些描述 ， 但未考慮進程的互斥與同步問題 ， 因而造成了數據 Counter的不定性 。 由于生產者 —消費者問題是相互合作的進程關系的一種抽象 ， 例如 ， 在輸入時 ， 輸入進程是生產者 ， 計算進程是消費者；而在輸出時 ， 則計算進程是生產者 ， 而打印進程是消費者 ， 因此 ， 該問題有很大的代表性及實用價值 。 1. 利用記錄型信號量解決生產者 —消費者問題 假定在生產者和消費者之間的公用緩沖池中 ， 具有 n個緩沖區(qū) ， 這時可利用互斥信號量 mutex實現諸進程對緩沖池的互斥使用；利用信號量 empty和 full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數量 。 又假定這些生產者和消費者相互等效 ， 只要緩沖池未滿 ， 生產者便可將消息送入緩沖池；只要緩沖池未空 ， 消費者便可從緩沖池中取走一個消息 。 對生產者 — 消費者問題可描述如下： 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 在生產者 —消費者問題中應注意：首先 ， 在每個程序中用于實現互斥的 wait(mutex)和 signal(mutex)必須成對地出現； 其次 ， 對資源信號量 empty和 full的 wait和 signal操作 ， 同樣需要成對地出現 ， 但它們分別處于不同的程序中 。 例如 ， wait(empty)在計算進程中 ， 而 signal(empty)則在打印進程中 ， 計算進程若因執(zhí)行 wait(empty)而阻塞 ， 則以后將由打印進程將它喚醒；最后 ， 在每個程序中的多個 wait操作順序不能顛倒 。 應先執(zhí)行對資源信號量的wait操作 ， 然后再執(zhí)行對互斥信號量的 wait操作 ， 否則可能引起進程死鎖 。 利用 AND信號量解決生產者 — 消費者問題 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 哲學家進餐問題 1. 經分析可知 ， 放在桌子上的筷子是臨界資源 ， 在一段時間內只允許一位哲學家使用 。 為了實現對筷子的互斥使用 ，可以用一個信號量表示一只筷子 ， 由這五個信號量構成信號量數組 。 Var chopstick: array［ 0, …, 4］ of semaphore。 所有信號量均被初始化為 1， 第 i位哲學家的活動可描述為： repeat wait(chopstick［ i］ )。 wait(chopstick［ (i+1) mod 5］ )。 … eat。 … signal(chopstick［ i］ )。 signal(chopstick［ (i+1) mod 5］ )。 … think