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