【文章內(nèi)容簡介】 ” 現(xiàn)象的進程同步機制 。 但在采取了 “ 讓權(quán)等待 ” 的策略后 ， 又會出現(xiàn)多個進程等待訪問同一臨界資源的情況 。 為此 ， 在信號量機制中 ， 除了需要一個用于代表資源數(shù)目的整型變量 value外 ， 還應(yīng)增加一個進程鏈表 L， 用于鏈接上述的所有等待進程 。 記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的 。 它所包含的上述兩個數(shù)據(jù)項可描述為： 第二章 進 程 管 理 type semaphore=record value:integer。 L:list of process。 end 相應(yīng)地， wait(S)和 signal(S) procedure wait(S) var S: semaphore。 begin ∶ = 。 if ＜ 0 then block(S,L) end procedure signal(S) var S: semaphore。 begin ∶ = +1。 if ≤0 then wakeup(S,L)。 end 第二章 進 程 管 理 在記錄型信號量機制中 ， 資源的數(shù)目 ， 因而又稱為資源信號量 ， 對它的每次 wait操作 ，意味著進程請求一個單位的該類資源 ， 因此描述為 ∶ =； 當 ＜ 0時 ， 表示該類資源已分配完畢 ， 因此進程應(yīng)調(diào)用 block原語 ， 進行自我阻塞 ， 放棄處理機 ， 并插入到信號量鏈表 。 可見 ， 該機制遵循了 “ 讓權(quán)等待 ” 準則 。 此時 的數(shù)目 。 對信號量的每次 signal操作 ， 表示執(zhí)行進程釋放一個單位資源 ， 故 ∶ =+1操作表示資源數(shù)目加 1。 若加 1后仍是 ≤0， 則表示在該信號量鏈表中 ， 仍有等待該資源的進程被阻塞 ， 故還應(yīng)調(diào)用 wakeup原語 ， 將 的第一個等待進程喚醒 。 如果 1， 表示只允許一個進程訪問臨界資源 ， 此時的信號量轉(zhuǎn)化為互斥信號量 。 第二章 進 程 管 理 3. AND型信號量 在兩個進程中都要包含兩個對 Dmutex和 Emutex的操作 ， 即 process A: process B: wait(Dmutex)。 wait(Emutex)。 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個資源 ， 當現(xiàn)有資源數(shù)少于 d時 ， 不予分配 。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量 (S＞ 1時 )或互斥信號量 (S=1時 )。 (3) Swait(S, 1, 0)。 這是一種很特殊且很有用的信號量操作 。 當 S≥1時 ， 允許多個進程進入某特定區(qū)；當 S變?yōu)?0后 ，將阻止任何進程進入特定區(qū) 。 換言之 ， 它相當于一個可控開關(guān) 。 第二章 進 程 管 理 信號量的應(yīng)用 1. 利用信號量實現(xià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 第二章 進 程 管 理 2. 利用信號量實現(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 第二章 進 程 管 理 經(jīng)典進程的同步問題 生產(chǎn)者 — 前面我們已經(jīng)對生產(chǎn)者 —消費者問題 (The proceducerconsumer problem)做了一些描述 ， 但未考慮進程的互斥與同步問題 ， 因而造成了數(shù)據(jù) Counter的不定性 。 由于生產(chǎn)者 —消費者問題是相互合作的進程關(guān)系的一種抽象 ， 例如 ， 在輸入時 ， 輸入進程是生產(chǎn)者 ， 計算進程是消費者；而在輸出時 ， 則計算進程是生產(chǎn)者 ， 而打印進程是消費者 ， 因此 ， 該問題有很大的代表性及實用價值 。 第二章 進 程 管 理 1. 利用記錄型信號量解決生產(chǎn)者 —消費者問題 假定在生產(chǎn)者和消費者之間的公用緩沖池中 ， 具有 n個緩沖區(qū) ， 這時可利用互斥信號量 mutex實現(xiàn)諸進程對緩沖池的互斥使用；利用信號量 empty和 full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量 。 又假定這些生產(chǎn)者和消費者相互等效 ， 只要緩沖池未滿 ， 生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空 ， 消費者便可從緩沖池中取走一個消息 。 對生產(chǎn)者 — 消費者問題可描述如下： 第二章 進 程 管 理 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)者 —消費者問題中應(yīng)注意：首先 ， 在每個程序中用于實現(xiàn)互斥的 wait(mutex)和 signal(mutex)必須成對地出現(xiàn)； 其次 ， 對資源信號量 empty和 full的 wait和 signal操作 ， 同樣需要成對地出現(xiàn) ， 但它們分別處于不同的程序中 。 例如 ， wait(empty)在計算