【正文】 ， 使同處于一個(gè)系統(tǒng)中的諸進(jìn)程之間可能存在著以下兩種形式的制約關(guān)系 。 同處于一個(gè)系統(tǒng)中的進(jìn)程，通常都共享著某種系統(tǒng)資源，如共享 CPU、共享 I/O設(shè)備等。 第二章 進(jìn) 程 管 理 (2) 直接相互制約關(guān)系。 例如，有一輸入進(jìn)程 A通過(guò)單緩沖向進(jìn)程 B提供數(shù)據(jù)。 第二章 進(jìn) 程 管 理 2. 臨界資源 在第一章中我們?cè)?jīng)介紹過(guò)，許多硬件資源如打印機(jī)、磁帶機(jī)等，都屬于 臨界資源 (Critical Resouce)，諸進(jìn)程間應(yīng)采取互斥方式，實(shí)現(xiàn)對(duì)這種資源的共享。 第二章 進(jìn) 程 管 理 生產(chǎn)者 消費(fèi)者 (producerconsumer)問(wèn)題是一個(gè)著名的進(jìn)程同步問(wèn)題。 為使生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有 n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中；消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。 第二章 進(jìn) 程 管 理 我們可利用一個(gè)數(shù)組來(lái)表示上述的具有 n個(gè) (0， 1， … ， n1)緩沖區(qū)的緩沖池。由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加 1表示成 in:= (in+1)mod n； 輸出指針加 1表示成 out:= (out+1) mod n。此外，還引入了一個(gè)整型變量 counter，其初始值為 0。生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量： 第二章 進(jìn) 程 管 理 Var n， integer； type item=…； var buffer: array［ 0， 1， …， n1］ of item； in， out: 0， 1， …， n1； counter: 0， 1， … ， n； 第二章 進(jìn) 程 管 理 指針 in和 out初始化為 1。 在生產(chǎn)者進(jìn)程中使用一局部變量 nextp，用于暫時(shí)存放每次剛生產(chǎn)出來(lái)的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變量 nextc，用于存放每次要消費(fèi)的產(chǎn)品。生產(chǎn)者對(duì)它做加 1操作，消費(fèi)者對(duì)它做減 1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)， ?？捎孟旅娴男问矫枋觯? register1:=counter； register2:=counter； register1:=register1+1； register2:=register21； counter:=register1； counter:=register2； 第二章 進(jìn) 程 管 理 假設(shè) counter的當(dāng)前值是 5。讀者可以自己試試，倘若再將兩段程序中各語(yǔ)句交叉執(zhí)行的順序改變，將可看到又可能得到 counter=6的答案，這表明程序的執(zhí)行已經(jīng)失去了再現(xiàn)性。 第二章 進(jìn) 程 管 理 3． 臨界區(qū) 由前所述可知，不論是硬件臨界資源，還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問(wèn)。 顯然，若能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，便可實(shí)現(xiàn)諸進(jìn)程對(duì)臨界資源的互斥訪問(wèn)。 如果此刻該臨界資源未被訪問(wèn) ， 進(jìn)程便可進(jìn)入臨界區(qū)對(duì)該資源進(jìn)行訪問(wèn) ， 并設(shè)置它正被訪問(wèn)的標(biāo)志；如果此刻該臨界資源正被某進(jìn)程訪問(wèn) ， 則本進(jìn)程不能進(jìn)入臨界區(qū) 。 相應(yīng)地 ， 在臨界區(qū)后面也要加上一段稱為 退出區(qū) (exit section)的代碼 ， 用于將臨界區(qū)正被訪問(wèn)的標(biāo)志恢復(fù)為未被訪問(wèn)的標(biāo)志 。 這樣 ， 可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下： repeat entry section critical section； exit section remainder section； until false； 第二章 進(jìn) 程 管 理 4． 同步機(jī)制應(yīng)遵循的規(guī)則 為實(shí)現(xiàn)進(jìn)程互斥地進(jìn)入自已的臨界區(qū) ， 可用軟件方法 ，更多的是在系統(tǒng)中設(shè)置專門的同步機(jī)構(gòu)來(lái)協(xié)調(diào)各進(jìn)程間的運(yùn)行 。 當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí) ， 表明臨界資源處于空閑狀態(tài) ， 應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū) ， 以有效地利用臨界資源 。當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問(wèn)，因而其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問(wèn)。 對(duì)要求訪問(wèn)臨界資源的進(jìn)程 ， 應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū) ， 以免陷入 “ 死等 ” 狀態(tài) 。當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。 很長(zhǎng)時(shí)間以來(lái) ， 這兩個(gè)操作一直被分別稱為 P、 V操作 。 亦即，當(dāng)一個(gè)進(jìn)程在修改某信號(hào)量時(shí)，沒(méi)有其他進(jìn)程可同時(shí)對(duì)該信號(hào)量進(jìn)行修改。 第二章 進(jìn) 程 管 理 2． 記錄型信號(hào)量 在整型信號(hào)量機(jī)制中的 wait操作，只要是信號(hào)量 S≤0，就會(huì)不斷地測(cè)試。 記錄型信號(hào)量機(jī)制則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。 為此 ， 在信號(hào)量機(jī)制中 ， 除了需要一個(gè)用于代表資源數(shù)目的整型變量 value外 ， 還應(yīng)增加一個(gè)進(jìn)程鏈表指針 L， 用于鏈接上述的所有等待進(jìn)程 。 它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為： 第二章 進(jìn) 程 管 理 type semaphore=record value: integer； L: list of process； end 第二章 進(jìn) 程 管 理 相應(yīng)地， wait(S)和 signal(S)操作可描述為： procedure wait(S) var S： semaphore； begin :=； if 0 then block()； end procedure signal(S) var S: semaphore； begin :=+1； if =0 then wakeup()； end 第二章 進(jìn) 程 管 理 在記錄型信號(hào)量機(jī)制中， 資源的數(shù)目，因而又稱為資源信號(hào)量?？梢?jiàn)，該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。對(duì)信號(hào)量的每次 signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，使系統(tǒng)中可供分配的該類資源數(shù)增加一個(gè)，故:=+1操作表示資源數(shù)目加 1。如果 1，表示只允許一個(gè)進(jìn)程訪問(wèn)臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量，用于進(jìn)程互斥。在有些應(yīng)用場(chǎng)合，是一個(gè)進(jìn)程需要先獲得兩個(gè)或更多的共享資源后方能執(zhí)行其任務(wù)。當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。相應(yīng)地，在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì) Dmutex和 Emutex的操作，即 process A: process B: wait(Dmutex)； wait(Emutex)； wait(Emutex)； wait(Dmutex)； 第二章 進(jìn) 程 管 理 若進(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)程 A和 B處于僵持狀態(tài)。我們稱此時(shí)的進(jìn)程 A和 B已進(jìn)入 死鎖狀態(tài) 。 第二章 進(jìn) 程 管 理 AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。 亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么把它所請(qǐng)求的資源全部分配到進(jìn)程，要么一個(gè)也不分配。為此，在 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 Si1， and set the program count of this process to the beginning of Swait operation endif Ssignal(S1， S2， …， Sn) 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)量集 在記錄型信號(hào)量機(jī)制中， wait(S)或 signal(S)操作僅能對(duì)信號(hào)量施以加 1或減 1操作，意味著每次只能獲得或釋放一個(gè)單位的臨界資源。此外，在有些情況下，當(dāng)資源數(shù)量低于某一下限值時(shí)，便不予以分配。基于上述兩點(diǎn)，可以對(duì) AND信號(hào)量機(jī)制加以擴(kuò)充，形成一般化的“信號(hào)量集”機(jī)制。 第二章 進(jìn) 程 管 理 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 Siti and set its program counter to the beginning of the Swait Operation. endive 第二章 進(jìn) 程 管 理 Ssignal(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)。 (2) Swait(S， 1， 1)。 (3) Swait(S， 1， 0)。當(dāng) S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng) S變?yōu)?0后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。 第二章 進(jìn) 程 管 理 信號(hào)量的應(yīng)用 1． 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 為使多個(gè)進(jìn)程能互斥地訪問(wèn)某臨界資源，只須為該資源設(shè)置一互斥信號(hào)量 mutex，并設(shè)其初始值為 1，然后將各進(jìn)程訪問(wèn)該資源的臨界區(qū) CS置于 wait(mutex)和 signal(mutex)操作之間即可。當(dāng)訪問(wèn)臨界資源的進(jìn)程退出臨界區(qū)后，又應(yīng)對(duì) mutex執(zhí)行 signal操作，以便釋放該臨界資源。 設(shè)有兩個(gè)并發(fā)執(zhí)行的進(jìn)程 P1和 P2。 我們希望在 S1執(zhí)行后再執(zhí)行 S2。同樣，我們可以利用信號(hào)量，按照語(yǔ)句間的前趨關(guān)系 (見(jiàn)圖 212)，寫出一個(gè)更為復(fù)雜的可并發(fā)執(zhí)行的程序。為使各程序段能正確執(zhí)行，應(yīng)設(shè)置若干個(gè)初始值為“ 0”的信號(hào)量。 第二章 進(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) 程 管 理 圖 212 前趨圖舉例 S4S5S3S1S6S2第二章 進(jìn) 程 管 理 管程機(jī)制 1． 管程的定義 系統(tǒng)中的各種硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)抽象地描述其資源特性，即用少量信息和對(duì)該資源所執(zhí)行的操作來(lái)表征該資源，而忽略