【正文】 repeat Swait(full, mutex)。 Ssignal(mutex, full)。 buffer(in) ∶ = nextp。 begin parbegin producer:begin repeat … produce an item in nextp。 buffer:array［ 0, …, n1］ of item。 應(yīng)先執(zhí)行對資源信號量的wait操作 ， 然后再執(zhí)行對互斥信號量的 wait操作 ， 否則可能引起進程死鎖 。 end parend end 第二章 進 程 管 理 在生產(chǎn)者 —消費者問題中應(yīng)注意：首先 ， 在每個程序中用于實現(xiàn)互斥的 wait(mutex)和 signal(mutex)必須成對地出現(xiàn)； 其次 ， 對資源信號量 empty和 full的 wait和 signal操作 ， 同樣需要成對地出現(xiàn) ， 但它們分別處于不同的程序中 。 consumer the item in nextc。 signal(mutex)。 nextc ∶ = buffer(out)。 end 第二章 進 程 管 理 consumer:begin repeat wait(full)。 signal(full)。 in ∶ = (in+1) mod n。 wait(mutex)。 begin parbegin proceducer:begin repeat … producer an item nextp。 buffer:array［ 0, …, n1］ of item。 又假定這些生產(chǎn)者和消費者相互等效 ， 只要緩沖池未滿 ， 生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空 ， 消費者便可從緩沖池中取走一個消息 。 由于生產(chǎn)者 —消費者問題是相互合作的進程關(guān)系的一種抽象 ， 例如 ， 在輸入時 ， 輸入進程是生產(chǎn)者 ， 計算進程是消費者；而在輸出時 ， 則計算進程是生產(chǎn)者 ， 而打印進程是消費者 ， 因此 ， 該問題有很大的代表性及實用價值 。 end。 wait(g)。 begin wait(e)。 signal(g)。 begin wait(d)。 signal(f)。 begin wait(c)。 signal(e)。 begin wait(b)。 signal(d)。 S2。 end。 signal(a)。 semaphore ∶ = 0,0,0,0,0,0,0。 remainder section until false。 第二章 進 程 管 理 end process 2: begin repeat wait(mutex)。 critical section signal(mutex)。 第二章 進 程 管 理 信號量的應(yīng)用 1. 利用信號量實現(xiàn)進程互斥 Var mutex:semaphore ∶ = 1。 當(dāng) S≥1時 ， 允許多個進程進入某特定區(qū)；當(dāng) S變?yōu)?0后 ，將阻止任何進程進入特定區(qū) 。 (3) Swait(S, 1, 0)。 (2) Swait(S, 1, 1)。 第二章 進 程 管 理 一般 “ 信號量集 ” (1) Swait(S, d, d)。 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。 為此 ， 在 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。 亦即 ， 對若干個臨界資源的分配 ， 采取原子操作方式：要么全部分配到進程 ， 要么一個也不分配 。 于是 Dmutex=1 B阻塞 第二章 進 程 管 理 AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源 ， 一次性全部地分配給進程 ， 待進程使用完后再一起釋放 。 于是 Emutex=0 process A: wait(Emutex)。 若進程 A和 B按下述次序交替執(zhí)行 wait process A: wait(Dmutex)。 wait(Emutex)。 第二章 進 程 管 理 3. AND型信號量 在兩個進程中都要包含兩個對 Dmutex和 Emutex的操作 ， 即 process A: process B: wait(Dmutex)。 若加 1后仍是 ≤0， 則表示在該信號量鏈表中 ， 仍有等待該資源的進程被阻塞 ， 故還應(yīng)調(diào)用 wakeup原語 ， 將 的第一個等待進程喚醒 。 此時 的數(shù)目 。 end 第二章 進 程 管 理 在記錄型信號量機制中 ， 資源的數(shù)目 ， 因而又稱為資源信號量 ， 對它的每次 wait操作 ，意味著進程請求一個單位的該類資源 ， 因此描述為 ∶ =； 當(dāng) ＜ 0時 ， 表示該類資源已分配完畢 ， 因此進程應(yīng)調(diào)用 block原語 ， 進行自我阻塞 ， 放棄處理機 ， 并插入到信號量鏈表 。 begin ∶ = +1。 begin ∶ = 。 L:list of process。 記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的 。 但在采取了 “ 讓權(quán)等待 ” 的策略后 ， 又會出現(xiàn)多個進程等待訪問同一臨界資源的情況 。 因此 ， 該機制并未遵循 “ 讓權(quán)等待 ” 的準則 ， 而是使進程處于 “ 忙等 ” 的狀態(tài) 。 signal(S): S ∶ =S+1。 這兩個操作一直被分別稱為 P、 V操作 。 (4) 讓權(quán)等待。 (2) 忙則等待。 until false。 (counter=4) 第二章 進 程 管 理 3. 臨界區(qū) (critical section) repeat critical section。 (register 2=4) counter ∶ = register 1。 (register 1=6) register 2 ∶ = counter。 如果生產(chǎn)者進程先執(zhí)行左列的三條機器語言語句 ， 然后消費者進程再執(zhí)行右列的三條語句 ， 則最后共享變量 counter的值仍為 5；反之 ， 如果讓消費者進程先執(zhí)行右列的三條語句 ， 然后再讓生產(chǎn)者進程執(zhí)行左列的三條語句 ， counter值也還是 5， 但是 ， 如果按下述順序執(zhí)行： register 1 ∶ = counter。 counter ∶ = register 2。 register 2∶ = register 21。 register 2∶ = counter。 第二章 進 程 管 理 雖然上面的生產(chǎn)者程序和消費者程序 ， 在分別看時都是正確的 ， 而且兩者在順序執(zhí)行時其結(jié)果也會是正確的 ， 但若并發(fā)執(zhí)行時 ， 就會出現(xiàn)差錯 ， 問題就在于這兩個進程共享變量 counter。 consumer the item in nextc。 out ∶ = (out+1) mod n。 consumer: repeat while counter=0 do noop。 counter ∶ = counter+1。 buffer［ in ∶ = nextp。 第二章 進 程 管 理 producer: repeat … produce an item in nextp。 在生產(chǎn)者和消費者進程的描述中 ， noop是一條空操作指令 ， while condition do noop語句表示重復(fù)的測試條件 (condication)， 重復(fù)測試應(yīng)進行到該條件變?yōu)?false(假 )， 即到該條件不成立時為止 。 counter: 0, 1, …, n。 var buffer:array［ 0, 1, …, n1］ of item。 生產(chǎn)者和消費者兩進程共享下面的變量： 第二章 進 程 管 理 Var n, integer。 此外 ， 還引入了一個整型變量 counter, 其初始值為 0。 由于這里的緩沖池是組織成循環(huán)緩沖的 ， 故應(yīng)把輸入指針加1表示成 in∶ =(in+1)mod n；輸出指針加 1表示成 out∶ =(out+1) mod n。 第二章 進 程 管 理 我們可利用一個數(shù)組來表示上述的具有 n個 (0， 1， …， n1)緩沖區(qū)的緩沖池 。 為使生產(chǎn)者進程與消費者進程能并發(fā)執(zhí)行 ， 在兩者之間設(shè)置了一個具有 n個緩沖區(qū)的緩沖池 ， 生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中； 消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費 。 第二章 進 程 管 理 2. 臨界資源 (Critical Resouce) 生產(chǎn)者 消費者 (producerconsumer)問題是一個著名的進程同步問題 。 第二章 進 程 管 理 進 程 同 步 進程同步的基本概念 1. 兩種形式的制約關(guān)系 (1) 間接相互制約關(guān)系。 激活原語先將進程從外存調(diào)入內(nèi)存 ， 檢查該進程的現(xiàn)行狀態(tài) ， 若是靜止就緒 ， 便將之改為活動就緒；若為靜止阻塞便將之改為活動阻塞 。 第二章 進 程 管 理 2. 進程的激活過程 當(dāng)發(fā)生激活進程的事件時 ， 例如 ， 父進程或用戶進程請求激活指定進程 ， 若該進程駐留在外存而內(nèi)存中已有足夠的空間時 ， 則可將在外存上處于靜止就緒狀態(tài)的進程換入內(nèi)存 。 為了方便用戶或父進程考查該進程的運行情況而把該進程的 PCB復(fù)制到某指定的內(nèi)存區(qū)域 。 第二章 進 程 管 理 進程的掛起與激活 1. 當(dāng)出現(xiàn)了引起進程掛起的事件時 ， 比如 ， 用戶進程請求將自己掛起 ， 或父進程請求將自己的某個子進程掛起 ， 系統(tǒng)將利用掛起原語 suspend( )將指定進程或處于阻塞狀態(tài)的進程掛起 。 第二章 進 程 管 理 3. 當(dāng)被阻塞進程所期待的事件出現(xiàn)時 ， 如 I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達 ， 則由有關(guān)進程 (比如 ， 用完并釋放了該 I/O設(shè)備的進程 )調(diào)用喚醒原語 wakeup( )， 將等待該事件的進