操作系統(tǒng)：第2章進(jìn)程管理2

1、2.3.1進(jìn)程同步的基本概念2.3進(jìn) 程 同 步 進(jìn)程同步的主要任務(wù)是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。例：X = fun1(y)*fun2(Z)計(jì)算fun1(y)進(jìn)程p2算完fun2(Z)?取用P2計(jì)算結(jié)果計(jì)算fun2(Z)設(shè)置計(jì)算完成標(biāo)志終 止YN進(jìn)程P1進(jìn)程P2 兩個(gè)協(xié)同工作進(jìn)程的同步P1P2P3PmC1C2C3Cn生產(chǎn)者進(jìn)程P(Sn)P(S)緩沖區(qū) 產(chǎn)品V(S)V(S0)消費(fèi)者進(jìn)程P(S0)P(S)取產(chǎn)品V(S)V(Sn)S = 1;So=0;Sn=n;例：生產(chǎn)者-消費(fèi)者(producer-consum

2、er)問(wèn)題是一個(gè)著名的進(jìn)程同步問(wèn)題。它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(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)。 盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿(mǎn)產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。 同時(shí)所有的消費(fèi)者進(jìn)程和生產(chǎn)者進(jìn)程不可以同時(shí)訪(fǎng)問(wèn)“緩沖池”這個(gè)共享資源，也就是進(jìn)程間應(yīng)通過(guò)互斥方式來(lái)共享資源。1并發(fā)進(jìn)程之間的制約關(guān)

3、系在多道程序環(huán)境下，當(dāng)程序并發(fā)執(zhí)行時(shí)，由于資源共享和進(jìn)程合作，使同處于一個(gè)系統(tǒng)中的諸進(jìn)程之間可能存在著以下兩種形式的制約關(guān)系。(1) 間接相互制約關(guān)系。同處于一個(gè)系統(tǒng)中的進(jìn)程，通常都共享著某種系統(tǒng)資源，如共享CPU、共享I/O設(shè)備等。所謂間接相互制約即源于這種資源共享。多個(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源。應(yīng)采取互斥的方式實(shí)現(xiàn)資源的共享。 (2) 直接相互制約關(guān)系。這種制約主要源于進(jìn)程間的合作。如生產(chǎn)者-消費(fèi)者問(wèn)題、司機(jī)售票員問(wèn)題。應(yīng)采取同步的方式來(lái)協(xié)調(diào)執(zhí)行的次序。2. 臨界資源定義： 臨界資源：一次只允許一個(gè)進(jìn)程使用的資源，如打印機(jī)、公共變量等。許多硬件資源如打印機(jī)、磁帶機(jī)等，都屬于臨界資源(Cr

4、itical Resource)，諸進(jìn)程間應(yīng)采取互斥方式，實(shí)現(xiàn)對(duì)這種資源的共享。*.in公用緩沖池中有n個(gè)緩沖區(qū)produceriproducer: repeat produce an item in nextp；while counter=n do no-op；bufferin:=nextp；in:=(in+1) mod n；counter:=counter+1；until false；consumer: repeatwhile counter=0 do no-op；nextc:=bufferout；out:=(out+1) mod n；counter:=counter-1；consume

5、the item in nextc； until false； consumerj生產(chǎn)者、消費(fèi)者例 雖然上面的生產(chǎn)者程序和消費(fèi)者程序在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)就會(huì)出現(xiàn)差錯(cuò)，問(wèn)題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)， ?？捎孟旅娴男问矫枋觯?register1:=counter； register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1； counter:=reg

6、ister2； 解決的辦法就是把共享變量counter作為臨界資源來(lái)處理，也就是讓生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程互斥地訪(fǎng)問(wèn)變量counter。例：register1:=counter； register1:=register1+1；counter:=register1；臨界區(qū)臨界區(qū)進(jìn) 程 A進(jìn) 程 Bregister2:=counter； register2:=register2+1；counter:=register2；3臨界區(qū)(CS，Critical Section)臨界區(qū)（段）定義： 在每個(gè)進(jìn)程中訪(fǎng)問(wèn)臨界資源的那段代碼稱(chēng)為臨界區(qū)。若能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，便可實(shí)現(xiàn)諸進(jìn)程對(duì)臨界資源的互

7、斥訪(fǎng)問(wèn)。為此，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對(duì)欲訪(fǎng)問(wèn)的臨界資源進(jìn)行檢查，看它是否正被訪(fǎng)問(wèn)。因此，必須在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，把這段代碼稱(chēng)為進(jìn)入?yún)^(qū)(entry section)。相應(yīng)地，在臨界區(qū)后面也要加上一段稱(chēng)為退出區(qū)(exit section)的代碼，用于將臨界區(qū)正被訪(fǎng)問(wèn)的標(biāo)志恢復(fù)為未被訪(fǎng)問(wèn)的標(biāo)志。 進(jìn)程中除上述進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其它部分的代碼，在這里都稱(chēng)為剩余區(qū)。這樣，可把一個(gè)訪(fǎng)問(wèn)臨界資源的循環(huán)進(jìn)程描述如下：repeatentry sectioncritical section；exit sectionremainder section；until false

8、； .Request printerprint.Print.Request plotterprintplotprintplotfree plotterprintfree printer.Request plotterplot.Plot.Request printerprintplotprintplotfree printerplotfree plotter.P1P2CS指那一段？P1，P2若不制約，會(huì)出現(xiàn)什么問(wèn)題？臨界區(qū)例4同步機(jī)制應(yīng)遵循的規(guī)則(臨界區(qū)調(diào)度準(zhǔn)則）為實(shí)現(xiàn)進(jìn)程互斥地進(jìn)入自已的臨界區(qū)，通常是在系統(tǒng)中設(shè)置專(zhuān)門(mén)的同步機(jī)構(gòu)來(lái)協(xié)調(diào)各進(jìn)程間的運(yùn)行。所有同步機(jī)制都應(yīng)遵循下述四條準(zhǔn)則：(1) 空閑

9、讓進(jìn)。當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。(2) 忙則等待。當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪(fǎng)問(wèn)，因而其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪(fǎng)問(wèn)。 (3) 有限等待。對(duì)要求訪(fǎng)問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。(4) 讓權(quán)等待。當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。 2.3.2信號(hào)量機(jī)制1整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)用于表示資源數(shù)目的整型量S，它與一般整型量不同，除初始化外，僅能

10、通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作(Atomic Operation) wait(S)和signal(S)來(lái)訪(fǎng)問(wèn)。這兩個(gè)操作被分別稱(chēng)為P、V操作。Wait(S)和signal(S)操作可描述為：wait(S)： while S=0 do no-op；S:=S-1；signal(S)：S:=S+1； 有忙等現(xiàn)象wait(S)和signal(S)是兩個(gè)原子操作，因此，它們?cè)趫?zhí)行時(shí)是不可中斷的。亦即，當(dāng)一個(gè)進(jìn)程在修改某信號(hào)量時(shí)，沒(méi)有其他進(jìn)程可同時(shí)對(duì)該信號(hào)量進(jìn)行修改。2記錄型信號(hào)量在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S0，就會(huì)不斷地測(cè)試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”的狀

11、態(tài)。為此，在記錄型信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表指針L，用于鏈接上述的所有等待進(jìn)程。type semaphore=recordvalue: integer；L: list of process；end 信號(hào)量: 有一個(gè)整型變量; 有一個(gè)相關(guān)的等待隊(duì)列; 除了初始化外,只能對(duì)其做wait,signal 操作（P、V操作）相應(yīng)地，wait(S)和signal(S)操作可描述為： procedure wait(S)var S：semaphore；beginS.value:=S.value-1；if S.value0 then block(S.L

12、)； end procedure signal(S)var S: semaphore；beginS.value:=S.value+1；if S.value=0 then wakeup(S.L)； end S.value的初值表示系統(tǒng)中某類(lèi)資源的數(shù)目，因而又稱(chēng)為資源信號(hào)量。對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類(lèi)資源，使系統(tǒng)中可供分配的該類(lèi)資源數(shù)減少一個(gè)，當(dāng)S.value0，表示可用資源個(gè)數(shù)；當(dāng)mutexwait(P)-wait(Q)-signal(Q)-signal(P)wait(Q)-wait(P)-signal(Q)-signal(P)=1 and and Sn=1 thenf

13、or i:=1 to n doSi:=Si-1；endforelseplace the process in the waiting queue associated with the first Si found with Si=t1 and and Sn=tn thenfor i:=1 to n doSi:=Si-di；endforelsePlace the executing process in the waiting queue of the first Si with Si1時(shí))或互斥信號(hào)量(S=1時(shí))。(3) Swait(S，1，0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S1時(shí)

14、，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)。 2.3.4管程機(jī)制1管程的定義 系統(tǒng)中的各種硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)抽象地描述其資源特性，即用少量信息和對(duì)該資源所執(zhí)行的操作來(lái)表征該資源，而忽略了它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。例如，對(duì)一臺(tái)電傳機(jī)，可用與分配該資源有關(guān)的狀態(tài)信息(busy或free)和對(duì)它執(zhí)行請(qǐng)求與釋放的操作，以及等待該資源的進(jìn)程隊(duì)列來(lái)描述。又如，一個(gè)FIFO隊(duì)列，可用其隊(duì)長(zhǎng)、隊(duì)首和隊(duì)尾以及在該隊(duì)列上執(zhí)行的一組操作來(lái)描述。 利用共享數(shù)據(jù)結(jié)構(gòu)抽象地表示系統(tǒng)中的共享資源，而把對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施的操作定義為一組過(guò)程，如資源的請(qǐng)求

15、和釋放過(guò)程request和release。進(jìn)程對(duì)共享資源的申請(qǐng)、釋放和其它操作，都是通過(guò)這組過(guò)程對(duì)共享數(shù)據(jù)結(jié)構(gòu)的操作來(lái)實(shí)現(xiàn)的，這組過(guò)程還可以根據(jù)資源的情況，或接受或阻塞進(jìn)程的訪(fǎng)問(wèn)，確保每次僅有一個(gè)進(jìn)程使用共享資源，這樣就可以統(tǒng)一管理對(duì)共享資源的所有訪(fǎng)問(wèn)，實(shí)現(xiàn)進(jìn)程互斥。 管程定義：代表共享資源的數(shù)據(jù)結(jié)構(gòu)，以及由對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施操作的一組過(guò)程所組成的資源管理程序，共同構(gòu)成了一個(gè)操作系統(tǒng)的資源管理模塊。管程被請(qǐng)求和釋放資源的進(jìn)程所調(diào)用。Hansan為管程所下的定義是：“一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)”。由上述的定義

16、可知，管程由四部分組成： 管程的名稱(chēng)； 局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說(shuō)明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程； 對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語(yǔ)句。圖2-13管程的示意圖 管程的語(yǔ)法描述如下：type monitor_name = MONITOR；define ；use ；procedure ()；beginend; function ()：值類(lèi)型；beginend； begin ；end 局部于管程內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，僅能被局部于管程內(nèi)部的過(guò)程所訪(fǎng)問(wèn)，任何管程外的過(guò)程都不能訪(fǎng)問(wèn)它；局部于管程內(nèi)部的過(guò)程也僅能訪(fǎng)問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。管程相當(dāng)于圍墻，它把共享變量和對(duì)它進(jìn)行操作的若干過(guò)程圍了起來(lái)，

17、所有進(jìn)程要訪(fǎng)問(wèn)臨界資源時(shí)，都必須經(jīng)過(guò)管程(相當(dāng)于通過(guò)圍墻的門(mén))才能進(jìn)入，而管程每次只準(zhǔn)許一個(gè)進(jìn)程進(jìn)入管程，從而實(shí)現(xiàn)了進(jìn)程互斥。管程主要有以下特性： (1) 模塊化。管程是一個(gè)基本程序單位，可以單獨(dú)編譯。(2) 抽象數(shù)據(jù)類(lèi)型。管程中不僅有數(shù)據(jù)，而且有對(duì)數(shù)據(jù)的操作。(3) 信息掩蔽。管程中的數(shù)據(jù)結(jié)構(gòu)只能被管程中的過(guò)程訪(fǎng)問(wèn)，這些過(guò)程也是在管程內(nèi)部定義的，供管程外的進(jìn)程調(diào)用，而管程中的數(shù)據(jù)結(jié)構(gòu)以及過(guò)程(函數(shù))的具體實(shí)現(xiàn)外部不可見(jiàn)。 管程和進(jìn)程區(qū)別(1) 雖然二者都定義了數(shù)據(jù)結(jié)構(gòu)，但進(jìn)程定義的是私有數(shù)據(jù)結(jié)構(gòu)PCB，管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如消息隊(duì)列等；(2) 二者都存在對(duì)各自數(shù)據(jù)結(jié)構(gòu)上的操作，但進(jìn)程是

18、由順序程序執(zhí)行有關(guān)的操作，而管程主要是進(jìn)行同步操作和初始化操作；(3) 設(shè)置進(jìn)程的目的在于實(shí)現(xiàn)系統(tǒng)的并發(fā)性，而管程的設(shè)置則是解決共享資源的互斥使用問(wèn)題； (4) 進(jìn)程通過(guò)調(diào)用管程中的過(guò)程對(duì)共享數(shù)據(jù)結(jié)構(gòu)實(shí)行操作，該過(guò)程就如通常的子程序一樣被調(diào)用，因而管程為被動(dòng)工作方式，進(jìn)程則為主動(dòng)工作方式；(5) 進(jìn)程之間能并發(fā)執(zhí)行，而管程則不能與其調(diào)用者并發(fā)；(6) 進(jìn)程具有動(dòng)態(tài)性，由“創(chuàng)建”而誕生，由“撤銷(xiāo)”而消亡，而管程則是操作系統(tǒng)中的一個(gè)資源管理模塊，供進(jìn)程調(diào)用。 2條件變量在利用管程實(shí)現(xiàn)進(jìn)程同步時(shí)，必須設(shè)置同步工具，如兩個(gè)同步操作原語(yǔ)wait和signal。當(dāng)某進(jìn)程通過(guò)管程請(qǐng)求獲得臨界資源而未能滿(mǎn)足時(shí)

19、，管程便調(diào)用wait原語(yǔ)使該進(jìn)程等待，并將其排在等待隊(duì)列上，如圖2-13 所示。僅當(dāng)另一進(jìn)程訪(fǎng)問(wèn)完成并釋放該資源之后，管程才又調(diào)用signal原語(yǔ)，喚醒等待隊(duì)列中的隊(duì)首進(jìn)程。 但是僅僅有上述的同步工具是不夠的?？紤]一種情況：當(dāng)一個(gè)進(jìn)程調(diào)用了管程，在管程中時(shí)被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期間，如果該進(jìn)程不釋放管程，則其它進(jìn)程無(wú)法進(jìn)入管程，被迫長(zhǎng)時(shí)間地等待。為了解決這個(gè)問(wèn)題，引入了條件變量condition。通常，一個(gè)進(jìn)程被阻塞或掛起的條件(原因)可有多個(gè)，因此在管程中設(shè)置了多個(gè)條件變量，對(duì)這些條件變量的訪(fǎng)問(wèn)，只能在管程中進(jìn)行。 管程中對(duì)每個(gè)條件變量都須予以說(shuō)明，其形式為：Var x，y：condition。對(duì)條件變量的操作僅僅是wait和signal，因此條件變量也是一種抽象數(shù)據(jù)類(lèi)型，每個(gè)條件變量保存了一個(gè)鏈表，用于記錄因該條件變量而阻塞的所有進(jìn)程，同時(shí)提供的兩個(gè)操作即可表示為x.wait和x.signal，其含義為： x.wait：正在調(diào)用管程的進(jìn)程因x條件需要被阻塞或掛起，則調(diào)用x.wait將自己插入到x條件的等待隊(duì)列上，并釋放管程，直到x條件變化。此時(shí)其它進(jìn)程可以使用該管程。 x.signal：正在調(diào)用管程的進(jìn)程發(fā)現(xiàn)x條件發(fā)生了變化，則調(diào)用