操作系統(tǒng)課件第二章

1、第二章第二章 進(jìn)程管理進(jìn)程管理 Process Management 在傳統(tǒng)的操作系統(tǒng)中，作為資源分配和在傳統(tǒng)的操作系統(tǒng)中，作為資源分配和獨(dú)立運(yùn)行的基本單位是獨(dú)立運(yùn)行的基本單位是進(jìn)程進(jìn)程。OSOS所具有的所具有的四大特征也都是基于進(jìn)程而形成的。四大特征也都是基于進(jìn)程而形成的。 第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理2.4 經(jīng)典進(jìn)程同步問(wèn)題經(jīng)典進(jìn)程同步問(wèn)題 Classical process synchronization problem一、生產(chǎn)者一、生產(chǎn)者-消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題(producer and consumer problem)(producer and con

2、sumer problem)若干進(jìn)程通過(guò)有限的共享緩沖區(qū)（緩沖池）交換數(shù)據(jù)。若干進(jìn)程通過(guò)有限的共享緩沖區(qū)（緩沖池）交換數(shù)據(jù)。“生產(chǎn)者生產(chǎn)者”進(jìn)程不斷進(jìn)程不斷將信息放入緩沖區(qū)將信息放入緩沖區(qū);“消費(fèi)者消費(fèi)者”進(jìn)程不斷進(jìn)程不斷從緩沖區(qū)中取出信息從緩沖區(qū)中取出信息；共享緩沖區(qū)共有共享緩沖區(qū)共有N個(gè)；個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作沖區(qū)進(jìn)行操作。設(shè)緩沖池為循環(huán)存儲(chǔ)結(jié)構(gòu)。設(shè)緩沖池為循環(huán)存儲(chǔ)結(jié)構(gòu)第二章第二章 進(jìn)程管理進(jìn)程管理r 1）緩沖池不滿就可放入，不空就可取出；）緩沖池不滿就可放入，不空就可取出；r 2）不允許消費(fèi)者到空緩沖中取消息（判空，則阻塞）；）不

3、允許消費(fèi)者到空緩沖中取消息（判空，則阻塞）；r 3）不允許生產(chǎn)者向滿緩沖中放消息（判滿，則阻塞）；）不允許生產(chǎn)者向滿緩沖中放消息（判滿，則阻塞）；r 4）對(duì)緩沖池的操作要求互斥。）對(duì)緩沖池的操作要求互斥。供應(yīng)方向供應(yīng)方向使用方向使用方向主要考慮的問(wèn)題：主要考慮的問(wèn)題： 緩沖區(qū)滿或空；緩沖區(qū)滿或空； 競(jìng)爭(zhēng)條件。競(jìng)爭(zhēng)條件。第二章第二章 進(jìn)程管理進(jìn)程管理 (2)(3)要求同步要求同步，需設(shè)置，需設(shè)置私有信號(hào)量私有信號(hào)量:n empty生產(chǎn)者進(jìn)程的私用信號(hào)量（初值為生產(chǎn)者進(jìn)程的私用信號(hào)量（初值為n)；n full消費(fèi)者進(jìn)程的私用信號(hào)量（初值為消費(fèi)者進(jìn)程的私用信號(hào)量（初值為0） (4)要求互斥要求互斥，

4、設(shè)置，設(shè)置公用信號(hào)量公用信號(hào)量n mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥（初值為（初值為1）。）。 第二章第二章 進(jìn)程管理進(jìn)程管理生產(chǎn)者消費(fèi)者動(dòng)畫演示（生產(chǎn)者消費(fèi)者動(dòng)畫演示（1）第二章第二章 進(jìn)程管理進(jìn)程管理生產(chǎn)者消費(fèi)者動(dòng)畫演示（生產(chǎn)者消費(fèi)者動(dòng)畫演示（2）第二章第二章 進(jìn)程管理進(jìn)程管理生產(chǎn)者消費(fèi)者動(dòng)畫演示（生產(chǎn)者消費(fèi)者動(dòng)畫演示（3）第二章第二章 進(jìn)程管理進(jìn)程管理生產(chǎn)者消費(fèi)者動(dòng)畫演示（生產(chǎn)者消費(fèi)者動(dòng)畫演示（4）第二章第二章 進(jìn)程管理進(jìn)程管理produce(data)；Begin wait(empty); wait(mutex); 送數(shù)據(jù)入緩沖區(qū)單元送數(shù)

5、據(jù)入緩沖區(qū)單元 Signal(mutex)； Signal(full);End；consume(data)；Begin wait(full); Wait(mutex); 消費(fèi)；消費(fèi)； signal(mutex); Signal(empty)；End；各生產(chǎn)者進(jìn)程使用的過(guò)程各生產(chǎn)者進(jìn)程使用的過(guò)程produce (data)各消費(fèi)者使用的過(guò)程各消費(fèi)者使用的過(guò)程consume (data)可描述如下：可描述如下：第二章第二章 進(jìn)程管理進(jìn)程管理注：注：一般說(shuō)來(lái)：一般說(shuō)來(lái)：singalsingal原語(yǔ)是釋放資源原語(yǔ)是釋放資源的，可以任意順序出現(xiàn)，的，可以任意順序出現(xiàn)，waitwait原語(yǔ)不然，原語(yǔ)不然，

6、如果次序混亂將造成如果次序混亂將造成死鎖死鎖。第二章第二章 進(jìn)程管理進(jìn)程管理設(shè)有設(shè)有n個(gè)緩沖區(qū)，為實(shí)現(xiàn)對(duì)緩沖池的互斥操作：個(gè)緩沖區(qū)，為實(shí)現(xiàn)對(duì)緩沖池的互斥操作：l互斥信號(hào)量互斥信號(hào)量mutex；資源信號(hào)量資源信號(hào)量empty表示空緩沖的個(gè)表示空緩沖的個(gè)數(shù)，數(shù)，full表示滿緩沖的個(gè)數(shù)；表示滿緩沖的個(gè)數(shù)；l 定義數(shù)組定義數(shù)組buffer 表示緩沖區(qū)。表示緩沖區(qū)。l 輸入指針輸入指針in指示下一個(gè)可放消息的緩沖區(qū)；指示下一個(gè)可放消息的緩沖區(qū)；輸出指針輸出指針out指示下一個(gè)可取消息的緩沖區(qū)。指示下一個(gè)可取消息的緩沖區(qū)。var mutex,empty,full：semaphore ：1，n，0； bu

7、ffer：array0，n-1 of item; in , out : integer：=0，0；第二章第二章 進(jìn)程管理進(jìn)程管理parbegin producer:begin repeat producer an item in nextp; wait(empty); wait(mutex) ; buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full) ; until false; endconsumer: begin repeat wait(full) ; wait(mutex); nextc:=buffer(out);

8、 out:=(out+1) mod n; signal(mutex); signal(empty); until false; endParend第二章第二章 進(jìn)程管理進(jìn)程管理1）wait(mutex)和和signal(mutex)必成對(duì)出現(xiàn)必成對(duì)出現(xiàn)2）empty和和full的的wait和和signal操作也必成對(duì)出現(xiàn)，操作也必成對(duì)出現(xiàn)，但是在不同的進(jìn)程中。但是在不同的進(jìn)程中。3）wait原語(yǔ)順序不能顛倒，原語(yǔ)順序不能顛倒，signal原語(yǔ)順序可任意。原語(yǔ)順序可任意。思考：思考： P82P82習(xí)題習(xí)題2323、2424 第二章第二章 進(jìn)程管理進(jìn)程管理parbegin producer:beg

9、in repeat producer an item in nextp; buffer(in):=nextp; in:=(in+1) mod n; until false; endconsumer: begin repeat nextc:=buffer(out); out:=(out+1) mod n; until false; endParend第二章第二章 進(jìn)程管理進(jìn)程管理二、哲學(xué)家進(jìn)餐問(wèn)題二、哲學(xué)家進(jìn)餐問(wèn)題（Dining Philosopher Problem）準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐進(jìn)進(jìn)餐餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐進(jìn)餐進(jìn)餐 五個(gè)哲學(xué)家，共用一張五個(gè)哲學(xué)家，共用一張圓桌，五支筷子。圓桌，五支筷子。 哲學(xué)

10、家有兩種狀態(tài)：哲學(xué)家有兩種狀態(tài)：“思考思考”和和“進(jìn)餐進(jìn)餐”。 進(jìn)餐時(shí)只能取靠近他的進(jìn)餐時(shí)只能取靠近他的左右的筷子，而且拿到兩左右的筷子，而且拿到兩支時(shí)才可進(jìn)餐。完后，放支時(shí)才可進(jìn)餐。完后，放下筷子繼續(xù)思考。下筷子繼續(xù)思考。第二章第二章 進(jìn)程管理進(jìn)程管理r 基本工作：思考，進(jìn)餐。基本工作：思考，進(jìn)餐。r 同步？同步？r 互斥？互斥？ 臨界資源為筷子。一只筷子臨界資源為筷子。一只筷子(編號(hào)為編號(hào)為i) 一個(gè)互斥信號(hào)量一個(gè)互斥信號(hào)量 可定義一個(gè)信號(hào)量數(shù)組來(lái)描述五支筷子。可定義一個(gè)信號(hào)量數(shù)組來(lái)描述五支筷子。 var chopstick:array0.4 of semaphore 所有信號(hào)量初值為所有

11、信號(hào)量初值為1， :=1, 1, 1, 1, 1;第二章第二章 進(jìn)程管理進(jìn)程管理Var chopstick: array 0.4 of semaphore:=1, 1, 1, 1, 1; Begin Parbegin process i ( i=0, 1, 2, 3, 4): begin Repeat until false; end parendend哲學(xué)家進(jìn)餐活動(dòng)可描述為：哲學(xué)家進(jìn)餐活動(dòng)可描述為： Think； wait(chopsticki)； wait(chopsticki+1 mod 5)； eat ； signal(chopsticki； signal(chopsticki+1 m

12、od 5)；此算法有無(wú)問(wèn)題？此算法有無(wú)問(wèn)題？第二章第二章 進(jìn)程管理進(jìn)程管理r 1) 規(guī)定在拿到左筷子后，先檢查右筷子是否可用。若不可規(guī)定在拿到左筷子后，先檢查右筷子是否可用。若不可 用，則先放下左筷子，等一段時(shí)間再重復(fù)整個(gè)過(guò)程。用，則先放下左筷子，等一段時(shí)間再重復(fù)整個(gè)過(guò)程。 但該方法可能出現(xiàn)但該方法可能出現(xiàn)“饑餓饑餓”現(xiàn)象現(xiàn)象哲學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐“死鎖死鎖”問(wèn)題解決方法問(wèn)題解決方法r 2）至多允許四個(gè)人同時(shí)進(jìn)餐，保證至少一個(gè)能進(jìn)餐。）至多允許四個(gè)人同時(shí)進(jìn)餐，保證至少一個(gè)能進(jìn)餐。 設(shè)一個(gè)信號(hào)量設(shè)一個(gè)信號(hào)量v，初值為，初值為4。r 3）規(guī)定奇數(shù)號(hào)人先拿左筷子，后拿右筷子；偶數(shù)號(hào)人先拿）規(guī)定奇數(shù)號(hào)人

13、先拿左筷子，后拿右筷子；偶數(shù)號(hào)人先拿右筷子，后拿左筷子。五個(gè)哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲右筷子，后拿左筷子。五個(gè)哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后再競(jìng)爭(zhēng)偶數(shù)號(hào)筷子。最后總有一個(gè)哲學(xué)家能獲得兩只筷得后再競(jìng)爭(zhēng)偶數(shù)號(hào)筷子。最后總有一個(gè)哲學(xué)家能獲得兩只筷子。子。第二章第二章 進(jìn)程管理進(jìn)程管理0123401234r 4）用）用AND信號(hào)量機(jī)制信號(hào)量機(jī)制可獲得最簡(jiǎn)潔解法。可獲得最簡(jiǎn)潔解法。第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理AND信號(hào)量實(shí)現(xiàn)哲學(xué)家就餐描述信號(hào)量實(shí)現(xiàn)哲學(xué)家就餐描述var chopstick:array 0,4 of semaphore:=(1,1,1,1,1);proc

14、ess i repeat think; eat; until false; 哲學(xué)家問(wèn)題對(duì)于多個(gè)競(jìng)爭(zhēng)進(jìn)程互斥地訪問(wèn)有限資源哲學(xué)家問(wèn)題對(duì)于多個(gè)競(jìng)爭(zhēng)進(jìn)程互斥地訪問(wèn)有限資源( (如如I/OI/O設(shè)備設(shè)備) )這一類問(wèn)題的建模十分有用。這一類問(wèn)題的建模十分有用。 第二章第二章 進(jìn)程管理進(jìn)程管理 一個(gè)數(shù)據(jù)對(duì)象被多個(gè)進(jìn)程共享。其中有些進(jìn)程要求讀，另一個(gè)數(shù)據(jù)對(duì)象被多個(gè)進(jìn)程共享。其中有些進(jìn)程要求讀，另一些進(jìn)程要求寫或修改。要求讀的進(jìn)程稱為一些進(jìn)程要求寫或修改。要求讀的進(jìn)程稱為“reader進(jìn)程進(jìn)程”；其它的稱為其它的稱為“writer進(jìn)程進(jìn)程”。允許多個(gè)允許多個(gè)reader進(jìn)程同時(shí)執(zhí)行；不進(jìn)程同時(shí)執(zhí)行；不允許一

15、個(gè)允許一個(gè)writer進(jìn)程和其它進(jìn)程和其它reader進(jìn)程或進(jìn)程或writer進(jìn)程同時(shí)訪問(wèn)進(jìn)程同時(shí)訪問(wèn)共享對(duì)象。共享對(duì)象。l a、多個(gè)、多個(gè)reader可同時(shí)訪問(wèn)這組共享數(shù)據(jù)可同時(shí)訪問(wèn)這組共享數(shù)據(jù)并發(fā)并發(fā)；l b、多個(gè)、多個(gè)writer不可同時(shí)訪問(wèn)這組共享數(shù)據(jù)不可同時(shí)訪問(wèn)這組共享數(shù)據(jù)互斥；互斥；l c、reader與與writer不可同時(shí)訪問(wèn)這組共享數(shù)據(jù)不可同時(shí)訪問(wèn)這組共享數(shù)據(jù)互斥互斥 它為數(shù)據(jù)庫(kù)訪問(wèn)建立了一個(gè)模型。它為數(shù)據(jù)庫(kù)訪問(wèn)建立了一個(gè)模型。 三、讀者三、讀者-寫者問(wèn)題寫者問(wèn)題（Reader/Writer ProblemReader/Writer Problem）第二章第二章 進(jìn)程管理進(jìn)程

16、管理r1r2rnwRreadcount信號(hào)量設(shè)置信號(hào)量設(shè)置 Wmutex：W/R和和W/W的互斥。的互斥。 Rmutex：讀者對(duì)讀者對(duì)readcount的互斥操作。的互斥操作?？刂谱兞吭O(shè)置：控制變量設(shè)置：Readcount 記錄讀的個(gè)數(shù)。記錄讀的個(gè)數(shù)。第二章第二章 進(jìn)程管理進(jìn)程管理申請(qǐng)申請(qǐng)Rmutex若若readcount=0申請(qǐng)申請(qǐng)Wmutexreadcount+1 讀操作讀操作釋放釋放Rmutex申請(qǐng)申請(qǐng)Rmutexreadcount1若若readcount=0釋放釋放Wmutex釋放釋放Rmutexvar rmutex,wmutex:semaphore:=1,1 readcount:in

17、teger:=0;parbegin reader:begin wait(rmutex) if readcount=0 then wait(wmutex) readcount:=readcount+1 signal(rmutex) 讀操作讀操作 wait(rmutex) readcount:=readcount-1 if readcount=0 then signal(wmutex) signal(rmutex)endwriter:begin wait(wmutex) 寫操作寫操作 signal(wmutex) EndParend 讀者寫者問(wèn)題描述讀者寫者問(wèn)題描述第二章第二章 進(jìn)程管理進(jìn)程管理問(wèn)

18、？問(wèn)？n 若一個(gè)若一個(gè)Writer進(jìn)程正在寫，則進(jìn)程正在寫，則Reader進(jìn)程和其他進(jìn)程和其他Writer進(jìn)程的狀態(tài)和進(jìn)程的狀態(tài)和所執(zhí)行到的位置？所執(zhí)行到的位置？n 本算法為讀者優(yōu)先算法，即當(dāng)讀者進(jìn)行讀時(shí)，寫者必須等待，直到所本算法為讀者優(yōu)先算法，即當(dāng)讀者進(jìn)行讀時(shí)，寫者必須等待，直到所有讀者均離開，寫者才能進(jìn)入。存在的問(wèn)題是什么？有讀者均離開，寫者才能進(jìn)入。存在的問(wèn)題是什么？n 寫者優(yōu)先：寫者優(yōu)先：如果一個(gè)讀者申請(qǐng)進(jìn)行讀操作時(shí)已有另一寫者在等待訪問(wèn)如果一個(gè)讀者申請(qǐng)進(jìn)行讀操作時(shí)已有另一寫者在等待訪問(wèn)共享資源，則該讀者必須等到?jīng)]有寫者處于等待狀態(tài)后才能開始讀操共享資源，則該讀者必須等到?jīng)]有寫者處于

19、等待狀態(tài)后才能開始讀操作。存在的問(wèn)題是什么？作。存在的問(wèn)題是什么？n 公平策略：規(guī)則公平策略：規(guī)則l 1：在一個(gè)讀序列中，若有寫者等待，則不允許新來(lái)讀者開始執(zhí)行。：在一個(gè)讀序列中，若有寫者等待，則不允許新來(lái)讀者開始執(zhí)行。l 2：在一個(gè)寫操作結(jié)束時(shí)，所有等待讀者應(yīng)比下一個(gè)寫者有更高優(yōu)：在一個(gè)寫操作結(jié)束時(shí)，所有等待讀者應(yīng)比下一個(gè)寫者有更高優(yōu)先權(quán)。先權(quán)。問(wèn)：對(duì)于該公平策略，應(yīng)如何予以解決呢？問(wèn)：對(duì)于該公平策略，應(yīng)如何予以解決呢？第二章第二章 進(jìn)程管理進(jìn)程管理var RN integer; L,mx:semaphore:=RN,1; begin parbegin reader: begin repea

20、t Swait(L,1,1)； Swait(mx,1,0); perform read operation Ssignal(L,1); until false; endwriter:begin repeat Swait(mx,1,1;L,RN,0);perform write operation Ssignal(mx,1);until false;endparendend 信號(hào)量集機(jī)制解決讀者寫者問(wèn)題信號(hào)量集機(jī)制解決讀者寫者問(wèn)題第二章第二章 進(jìn)程管理進(jìn)程管理四、打瞌睡的理發(fā)師問(wèn)題四、打瞌睡的理發(fā)師問(wèn)題 理發(fā)店里有一位理發(fā)師，一把理理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和發(fā)椅和N N把供等候理發(fā)的顧客

21、坐的把供等候理發(fā)的顧客坐的椅子椅子； 理發(fā)師為理發(fā)椅上的顧客理發(fā)，理發(fā)師為理發(fā)椅上的顧客理發(fā)，沒有顧客就在理發(fā)椅上睡覺；沒有顧客就在理發(fā)椅上睡覺； 第一個(gè)顧客到來(lái)第一個(gè)顧客到來(lái)，他必須先喚醒，他必須先喚醒理發(fā)師理發(fā)師； 如如果顧客來(lái)時(shí)理發(fā)師正在果顧客來(lái)時(shí)理發(fā)師正在忙忙，若若有空椅子有空椅子，則則坐下來(lái)等；否則離開坐下來(lái)等；否則離開。第二章第二章 進(jìn)程管理進(jìn)程管理說(shuō)說(shuō) 明：明：理發(fā)師和每位顧客都分別是一個(gè)進(jìn)程。理發(fā)師和每位顧客都分別是一個(gè)進(jìn)程。r 理發(fā)師：理發(fā)師：看是否有顧客，若沒有，在理發(fā)椅上睡覺；否則，看是否有顧客，若沒有，在理發(fā)椅上睡覺；否則，為等待最久的顧客服務(wù)，等待人數(shù)減為等待最久的顧

22、客服務(wù)，等待人數(shù)減1。r 顧客：顧客：先看有無(wú)空座位先看有無(wú)空座位(等候的顧客數(shù)是否少于椅子數(shù)等候的顧客數(shù)是否少于椅子數(shù))，若有則等，等待人數(shù)加若有則等，等待人數(shù)加1；若理發(fā)師正瞌睡，則將其喚醒；若理發(fā)師正瞌睡，則將其喚醒；否則，離開。否則，離開。r 理發(fā)師和顧客的關(guān)系？理發(fā)師和顧客的關(guān)系？l變量變量waiting，用于記錄等候的顧客數(shù)，初值為，用于記錄等候的顧客數(shù)，初值為0。由于它。由于它不是信號(hào)量，因此可對(duì)其進(jìn)行增減等操作。不是信號(hào)量，因此可對(duì)其進(jìn)行增減等操作。l設(shè)顧客座椅數(shù)（設(shè)顧客座椅數(shù)（chairs）為常量）為常量5。第二章第二章 進(jìn)程管理進(jìn)程管理# define CHAIRS 5 /

23、*為等待的顧客準(zhǔn)備的椅子數(shù)為等待的顧客準(zhǔn)備的椅子數(shù)*/semaphore customers=0; /*等待服務(wù)的顧客數(shù)等待服務(wù)的顧客數(shù)*/ semaphore barbers=0; /*等待顧客的理發(fā)師數(shù)等待顧客的理發(fā)師數(shù)*/ semaphore mutex=1; /*用于互斥用于互斥*/ int waiting=0; /*等待的顧客等待的顧客(還沒理發(fā)的還沒理發(fā)的)*/ 三個(gè)信號(hào)量三個(gè)信號(hào)量nCustomers：用來(lái)記錄等候理發(fā)的顧客數(shù)用來(lái)記錄等候理發(fā)的顧客數(shù)(不包括正在理不包括正在理發(fā)的顧客發(fā)的顧客)，初值為，初值為0；nBarbers：等候顧客的理發(fā)師數(shù)，初值為等候顧客的理發(fā)師數(shù)，初值

24、為0；nMutex：用于對(duì)用于對(duì)waiting 變量的互斥。變量的互斥。信號(hào)量設(shè)置和變量定義信號(hào)量設(shè)置和變量定義第二章第二章 進(jìn)程管理進(jìn)程管理Void customers(void) wait(mutex); /*互斥進(jìn)入臨界區(qū)互斥進(jìn)入臨界區(qū)*/ If(waiting0 S0 表示有表示有S S個(gè)資源可用個(gè)資源可用S=0 S=0 表示無(wú)資源可用表示無(wú)資源可用S0 S0 則則| S | S |表示表示S S等待隊(duì)列中的進(jìn)程個(gè)數(shù)等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S): P(S): 表示申請(qǐng)一個(gè)資源表示申請(qǐng)一個(gè)資源 V(S)V(S)： 表示釋放一個(gè)資源。表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于信號(hào)量的初值應(yīng)

25、該大于等于0 01 信號(hào)量的物理含義：信號(hào)量的物理含義：第二章第二章 進(jìn)程管理進(jìn)程管理l 當(dāng)為當(dāng)為互斥操作互斥操作時(shí)，它們同處于時(shí)，它們同處于同一進(jìn)程同一進(jìn)程; ;l 當(dāng)為當(dāng)為同步操作同步操作時(shí)，則時(shí)，則不在同一進(jìn)程不在同一進(jìn)程中出現(xiàn)中出現(xiàn); ;l 如果如果P(S1)P(S1)和和P(S2)P(S2)兩個(gè)操作在一起，那么兩個(gè)操作在一起，那么P P操作的順操作的順序至關(guān)重要序至關(guān)重要, ,一個(gè)同步一個(gè)同步P P操作與一個(gè)互斥操作與一個(gè)互斥P P操作在一起操作在一起時(shí)時(shí)同步同步P P操作在互斥操作在互斥P P操作前操作前；l 而兩個(gè)而兩個(gè)V V操作的順序無(wú)關(guān)緊要。操作的順序無(wú)關(guān)緊要。2 P.V操作

26、必須成對(duì)出現(xiàn)操作必須成對(duì)出現(xiàn):第二章第二章 進(jìn)程管理進(jìn)程管理優(yōu)點(diǎn)：優(yōu)點(diǎn)： 簡(jiǎn)單，而且表達(dá)能力強(qiáng)簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用（用P.V操作可解決任何同步互斥操作可解決任何同步互斥問(wèn)題）。問(wèn)題）。缺點(diǎn)：缺點(diǎn)： 不夠安全；不夠安全；P.V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)現(xiàn)復(fù)雜?；コ鈫?wèn)題時(shí)實(shí)現(xiàn)復(fù)雜。3 P.V操作的優(yōu)缺點(diǎn)操作的優(yōu)缺點(diǎn)第二章第二章 進(jìn)程管理進(jìn)程管理2.5 管程機(jī)制管程機(jī)制 Monitor Mechanism 信號(hào)量機(jī)制為互斥、同步問(wèn)題的解決提供了有效靈活的工信號(hào)量機(jī)制為互斥、同步問(wèn)題的解決提供了有效靈活的工具，但要求在訪問(wèn)臨界資源的進(jìn)程中自

27、備具，但要求在訪問(wèn)臨界資源的進(jìn)程中自備wait和和signal操作，操作，加長(zhǎng)了進(jìn)程的長(zhǎng)度，還易產(chǎn)生死鎖。加長(zhǎng)了進(jìn)程的長(zhǎng)度，還易產(chǎn)生死鎖。signal(mutex) CSwait(mutex)wait(mutex) CSwait(mutex)遺漏了遺漏了wait或或signal例如：利用信號(hào)量實(shí)現(xiàn)互斥。例如：利用信號(hào)量實(shí)現(xiàn)互斥。第二章第二章 進(jìn)程管理進(jìn)程管理n 集中集中管理分散在進(jìn)程中的臨界段。管理分散在進(jìn)程中的臨界段。 1971年，年，Dijkstra提出，為每一臨界資源設(shè)置提出，為每一臨界資源設(shè)置一個(gè)一個(gè)“秘書秘書”進(jìn)程。訪問(wèn)該臨界資源的進(jìn)程都需先報(bào)告進(jìn)程。訪問(wèn)該臨界資源的進(jìn)程都需先報(bào)告“

28、秘書秘書”，由，由“秘書秘書”實(shí)現(xiàn)諸進(jìn)程的同步。實(shí)現(xiàn)諸進(jìn)程的同步。Hoare(1974)和和Hansen(1975)，發(fā)展為，發(fā)展為（Monitors）。）。n 把并發(fā)進(jìn)程間的操作，集中于相應(yīng)的管程中。把并發(fā)進(jìn)程間的操作，集中于相應(yīng)的管程中。 管程與管程與信號(hào)量機(jī)制功能等價(jià)，且更容易控制。信號(hào)量機(jī)制功能等價(jià)，且更容易控制。解決方法：解決方法：第二章第二章 進(jìn)程管理進(jìn)程管理一、管程的定義一、管程的定義（The definition of monitor）1 定義：定義： “2.5.1 管程的基本概念管程的基本概念The basic concepts of monitor 2 基本思想：基本思想：

29、把信號(hào)量及其操作原語(yǔ)封裝在一個(gè)對(duì)象內(nèi)部，即把信號(hào)量及其操作原語(yǔ)封裝在一個(gè)對(duì)象內(nèi)部，即將共享資源以及針對(duì)共享資源的所有操作集中在一個(gè)模塊中。將共享資源以及針對(duì)共享資源的所有操作集中在一個(gè)模塊中?？梢院瘮?shù)庫(kù)的形式實(shí)現(xiàn)。一個(gè)管程就是一個(gè)基本程序單位，可可以函數(shù)庫(kù)的形式實(shí)現(xiàn)。一個(gè)管程就是一個(gè)基本程序單位，可以單獨(dú)編譯。以單獨(dú)編譯。第二章第二章 進(jìn)程管理進(jìn)程管理 1) 管程名稱；管程名稱； 2) 局部于管程的共享變局部于管程的共享變量說(shuō)明量說(shuō)明(臨界資源描述臨界資源描述)； 3) 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程（即對(duì)臨界作的一組過(guò)程（即對(duì)臨界資源進(jìn)行操作的部分資源進(jìn)行操作的部分)； 4

30、) 對(duì)局部于管程的數(shù)據(jù)對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。設(shè)置初始值的語(yǔ)句。二、二、 管程的組成管程的組成（The Composition of Monitor）第二章第二章 進(jìn)程管理進(jìn)程管理type monitor-name=monitor variable declarations procedure entry P1(); beginend; procedure entry Pn(); beginend; begin initialization code end 第二章第二章 進(jìn)程管理進(jìn)程管理 1 1）局部于局部于管程的管程的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)僅能被僅能被局部于局部于管程的管程的過(guò)程過(guò)程

31、訪問(wèn)訪問(wèn)；反之，局部于管程的過(guò)程也僅能訪問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。；反之，局部于管程的過(guò)程也僅能訪問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。 2 2）一個(gè)進(jìn)程通過(guò)）一個(gè)進(jìn)程通過(guò)調(diào)用管程內(nèi)調(diào)用管程內(nèi)的一個(gè)的一個(gè)過(guò)程過(guò)程進(jìn)入管程，因此進(jìn)入管程，因此管程有很好的封裝性。管程有很好的封裝性。 3 3）為了保證共享變量的數(shù)據(jù)一致性，任一時(shí)刻管程中只）為了保證共享變量的數(shù)據(jù)一致性，任一時(shí)刻管程中只能有能有一個(gè)活躍的進(jìn)程一個(gè)活躍的進(jìn)程。其他調(diào)用該管程的進(jìn)程都被掛起，等。其他調(diào)用該管程的進(jìn)程都被掛起，等待管程變?yōu)榭捎?，即：管程能有效?shí)現(xiàn)進(jìn)程互斥訪問(wèn)資源。待管程變?yōu)榭捎?，即：管程能有效?shí)現(xiàn)進(jìn)程互斥訪問(wèn)資源。 三、管程的特性三、管程的特性（

32、 The peculiarity of monitor）第二章第二章 進(jìn)程管理進(jìn)程管理 當(dāng)一個(gè)已進(jìn)入管程的進(jìn)程等待時(shí)，釋放管程的互斥使當(dāng)一個(gè)已進(jìn)入管程的進(jìn)程等待時(shí)，釋放管程的互斥使用權(quán)；當(dāng)已進(jìn)入管程的一個(gè)進(jìn)程（用權(quán)；當(dāng)已進(jìn)入管程的一個(gè)進(jìn)程（P）喚醒另一個(gè)進(jìn)程）喚醒另一個(gè)進(jìn)程(Q)時(shí)，兩者必須有一個(gè)退出或停止使用管程。時(shí)，兩者必須有一個(gè)退出或停止使用管程。處理方法有三種：處理方法有三種：等待，繼續(xù)，直到等待或退出。等待，繼續(xù)，直到等待或退出。等待，繼續(xù)，直到退出或等待。等待，繼續(xù)，直到退出或等待。規(guī)定規(guī)定P的喚醒操作為管程中最后一個(gè)可執(zhí)行的操作。的喚醒操作為管程中最后一個(gè)可執(zhí)行的操作。Hoare

33、采用采用Hansen建議建議說(shuō)說(shuō) 明明第二章第二章 進(jìn)程管理進(jìn)程管理圖圖2 21111管管程程示示意意圖圖EntranceQueue ofEnteringProcessesMonitior Waiting Area Condition c1C1.wait. . . .condition cn. . . .Cn.waitUrgent Queuecsignal ExitM0NITOR Local DataCondition VariablesProcedure 1Procedure kInitialization Code第二章第二章 進(jìn)程管理進(jìn)程管理四、管程實(shí)現(xiàn)互斥和同步四、管程實(shí)現(xiàn)互斥和同步1

34、 互斥互斥 管程的第三個(gè)特性，使他們能有效的完成互斥。進(jìn)入管程管程的第三個(gè)特性，使他們能有效的完成互斥。進(jìn)入管程的互斥由編譯器負(fù)責(zé)，寫管程的人無(wú)需關(guān)心。的互斥由編譯器負(fù)責(zé)，寫管程的人無(wú)需關(guān)心。2 同步同步 管程實(shí)現(xiàn)同步，需設(shè)置：管程實(shí)現(xiàn)同步，需設(shè)置：l 條件變量條件變量x，表示等待原因。，表示等待原因。l 利用利用wait和和signal操作表示因等待原因出現(xiàn)而等待、操作表示因等待原因出現(xiàn)而等待、喚醒一個(gè)某原因而等待的進(jìn)程。喚醒一個(gè)某原因而等待的進(jìn)程。第二章第二章 進(jìn)程管理進(jìn)程管理& 設(shè)設(shè)var x:condition，則可有，則可有 x.wait因等待因等待x而阻塞，直至其他進(jìn)程執(zhí)行

35、而阻塞，直至其他進(jìn)程執(zhí)行x.signal。 x.signal喚醒一個(gè)因等待喚醒一個(gè)因等待x而阻塞的進(jìn)程。而阻塞的進(jìn)程。 如果如果x等待隊(duì)列中無(wú)進(jìn)程阻塞，該操作不產(chǎn)生任何作用。（與等待隊(duì)列中無(wú)進(jìn)程阻塞，該操作不產(chǎn)生任何作用。（與信號(hào)量的信號(hào)量的signal不同）不同）& 如：因共享資源忙而進(jìn)程等待，條件變量可定義為：如：因共享資源忙而進(jìn)程等待，條件變量可定義為：nonbusy：condiction。 則則wait為：為：nonbusy.wait，signal 為：為：nonbusy.signal條件變量和相關(guān)操作條件變量和相關(guān)操作第二章第二章 進(jìn)程管理進(jìn)程管理 首先建立管程名為首先建立管

36、程名為PC，并定義其包含的兩個(gè)過(guò)程：，并定義其包含的兩個(gè)過(guò)程：1）put(item)為生產(chǎn)者放消息過(guò)程。為生產(chǎn)者放消息過(guò)程。count表示已有的消息數(shù)表示已有的消息數(shù)目。目。countn，表緩沖池已滿。生產(chǎn)者需等待。，表緩沖池已滿。生產(chǎn)者需等待。2）get(item)為消費(fèi)者取消息過(guò)程。為消費(fèi)者取消息過(guò)程。 count0，表緩沖池已空，表緩沖池已空，消費(fèi)者等待。消費(fèi)者等待。PC管程的描述為：管程的描述為：Type PC=monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull,notempty:condition;

37、 2.5.2 利用管程解決生產(chǎn)者利用管程解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題procedure entry put(item) begin if countn then notfull.wait bufferin:=nextp in:=(in+1) mod n count:=count+1 if notempty.quene then notempty.signal endprocedure entry get(item) begin if count0 then notempty.wait nextc:=bufferout out:=(out+1) mod n count:=count-1 if

38、notfull.queue then notfull.signal endbegin in:=out:=0; count:=0; end第二章第二章 進(jìn)程管理進(jìn)程管理producer:begin repeat produce an item in nextp PC.put(nextp) until falseend consumer:begin repeat PC.get(item) consume the item in nextc until falseend第二章第二章 進(jìn)程管理進(jìn)程管理練練 習(xí)習(xí) 1n設(shè)某計(jì)算機(jī)有兩個(gè)設(shè)某計(jì)算機(jī)有兩個(gè)I/OI/O通道：分別掛一臺(tái)輸入機(jī)和一臺(tái)通道：分別掛一

39、臺(tái)輸入機(jī)和一臺(tái)打印機(jī)?？ㄆ瑱C(jī)上有一疊數(shù)據(jù)卡片，現(xiàn)在要把這些數(shù)打印機(jī)。卡片機(jī)上有一疊數(shù)據(jù)卡片，現(xiàn)在要把這些數(shù)據(jù)逐一輸入到緩沖區(qū)據(jù)逐一輸入到緩沖區(qū)B1B1，然后再?gòu)?fù)制到緩沖區(qū)，然后再?gòu)?fù)制到緩沖區(qū)B2B2，并，并在打印機(jī)上打印出來(lái)。在打印機(jī)上打印出來(lái)。n問(wèn)：系統(tǒng)可設(shè)哪些進(jìn)程來(lái)完成這個(gè)任務(wù)？用問(wèn)：系統(tǒng)可設(shè)哪些進(jìn)程來(lái)完成這個(gè)任務(wù)？用P.VP.V原語(yǔ)寫原語(yǔ)寫這些進(jìn)程的同步算法。這些進(jìn)程的同步算法。 第二章第二章 進(jìn)程管理進(jìn)程管理& 系統(tǒng)可設(shè)系統(tǒng)可設(shè)3 3個(gè)進(jìn)程：輸入進(jìn)程個(gè)進(jìn)程：輸入進(jìn)程R R、復(fù)制進(jìn)程、復(fù)制進(jìn)程C C、打印進(jìn)程、打印進(jìn)程P P；& 這些進(jìn)程之間的相互制約關(guān)系：這些進(jìn)程之間的

40、相互制約關(guān)系： R R受受C C的約束；的約束；C C受受R R、P P的約束；的約束；P P受受C C的約束。的約束。 & 信號(hào)量設(shè)置信號(hào)量設(shè)置 B1fullB1full：緩沖區(qū)：緩沖區(qū)B1B1滿，初值滿，初值0 0； B1emptyB1empty：緩沖區(qū)：緩沖區(qū)B1B1空，初值空，初值=1=1； B2fullB2full：緩沖區(qū)：緩沖區(qū)B2B2滿，初值滿，初值=0=0； B2emptyB2empty：緩沖區(qū)：緩沖區(qū)B2B2空，初值空，初值=1=1。 & 同步算法如下：同步算法如下：第二章第二章 進(jìn)程管理進(jìn)程管理R進(jìn)程進(jìn)程P(B1empty)；輸入信息到輸入信息到B1;V(B

41、1full)；C進(jìn)程進(jìn)程P(B1full)；從從B1中取出信息中取出信息;V(B1empty)；P(B2empty)；加工信息加工信息結(jié)果送入結(jié)果送入B2;V(B2full)；P進(jìn)程進(jìn)程P(B2full)；從從B2取出信息打印取出信息打印;V(B2empty)；第二章第二章 進(jìn)程管理進(jìn)程管理練練 習(xí)習(xí) 2n a,b 兩點(diǎn)間是一段東西向的單行車道，現(xiàn)要設(shè)計(jì)一個(gè)自兩點(diǎn)間是一段東西向的單行車道，現(xiàn)要設(shè)計(jì)一個(gè)自動(dòng)管理系統(tǒng)，管理規(guī)則如下：動(dòng)管理系統(tǒng)，管理規(guī)則如下：n當(dāng)當(dāng)ab間有車行駛時(shí)，同向車可以同時(shí)駛?cè)腴g有車行駛時(shí)，同向車可以同時(shí)駛?cè)隺b段，但段，但反向車必須在反向車必須在ab段外等待；段外等待；n當(dāng)

42、當(dāng)ab間無(wú)車時(shí)，間無(wú)車時(shí)，a（或（或b）的車輛可以進(jìn)入）的車輛可以進(jìn)入ab段，但段，但不能從不能從a，b點(diǎn)同時(shí)駛?cè)耄稽c(diǎn)同時(shí)駛?cè)?；n 請(qǐng)用請(qǐng)用wait,signal工具對(duì)工具對(duì)ab段實(shí)現(xiàn)正確管理。段實(shí)現(xiàn)正確管理。ab第二章第二章 進(jìn)程管理進(jìn)程管理r 互斥：雙方互斥進(jìn)入單行道；互斥：雙方互斥進(jìn)入單行道；互斥信號(hào)量互斥信號(hào)量r 而同方向的車可同時(shí)進(jìn)入，故每個(gè)方向等待進(jìn)入車道的而同方向的車可同時(shí)進(jìn)入，故每個(gè)方向等待進(jìn)入車道的第一輛車需爭(zhēng)奪進(jìn)入權(quán)，一旦爭(zhēng)得進(jìn)入權(quán)，同方向的車第一輛車需爭(zhēng)奪進(jìn)入權(quán)，一旦爭(zhēng)得進(jìn)入權(quán)，同方向的車隨意進(jìn)入，否則需等對(duì)方的車都駛出后才能進(jìn)入。為此，隨意進(jìn)入，否則需等對(duì)方的車都駛出后

43、才能進(jìn)入。為此，雙方均應(yīng)設(shè)置雙方均應(yīng)設(shè)置計(jì)數(shù)器計(jì)數(shù)器記錄該方向是否有車輛在行駛。斥記錄該方向是否有車輛在行駛。斥進(jìn)入的，進(jìn)入的，r 保證計(jì)數(shù)器互斥使用的保證計(jì)數(shù)器互斥使用的互斥信號(hào)量互斥信號(hào)量。var mutex, ab,ba：Semaphore： 1,1,1第二章第二章 進(jìn)程管理進(jìn)程管理Pab：Wait(ab) Ca+ If Ca=1 then wait(mutex);Signal(ab) enter; wait(ab)Ca- -; if Ca=0 then signal(mutex)；signal(ab);Pba:wait(ba)； Cb+; If Cb=1 then wait(mutex

44、)；signal(ba)； enter;wait(ba)； Cb-; if Cb=0 then signal(mutex)signal(ba);第二章第二章 進(jìn)程管理進(jìn)程管理練習(xí)練習(xí)3 圖書館問(wèn)題圖書館問(wèn)題l 圖書館有圖書館有100個(gè)座位，有一張登記表，要求：個(gè)座位，有一張登記表，要求： 閱讀者進(jìn)入時(shí)登記，取得座位號(hào)；閱讀者進(jìn)入時(shí)登記，取得座位號(hào)； 出來(lái)時(shí)，注銷；出來(lái)時(shí)，注銷； 登記表同時(shí)只能由一個(gè)人使用；登記表同時(shí)只能由一個(gè)人使用；l 用用P、V原語(yǔ)描述原語(yǔ)描述一個(gè)讀者一個(gè)讀者的使用過(guò)程。的使用過(guò)程。第二章第二章 進(jìn)程管理進(jìn)程管理&一個(gè)讀者有三種操作，一個(gè)讀者有三種操作，進(jìn)入進(jìn)入、閱

45、讀、閱讀、退出退出$ 其中，進(jìn)入和退出操作要其中，進(jìn)入和退出操作要互斥互斥使用登記卡，因此，使用登記卡，因此，登記卡作為臨界資源。登記卡作為臨界資源。$ 進(jìn)入進(jìn)入要申請(qǐng)座位，若座位已滿，否則不能進(jìn)入；要申請(qǐng)座位，若座位已滿，否則不能進(jìn)入；$ 退出退出要釋放座位。要釋放座位。& 有兩個(gè)進(jìn)程（進(jìn)入和退出），設(shè)兩個(gè)信號(hào)量：有兩個(gè)進(jìn)程（進(jìn)入和退出），設(shè)兩個(gè)信號(hào)量：$進(jìn)入私有信號(hào)量進(jìn)入私有信號(hào)量SN，表示座位數(shù)，初值為，表示座位數(shù)，初值為100；$互斥信號(hào)量互斥信號(hào)量mutex，初值為初值為1 。第二章第二章 進(jìn)程管理進(jìn)程管理Reader(int i)BeginEnter()；閱讀閱讀;Oute

46、r()EndEnter() Begin P(SN)； P(mutex)； 登記；登記； V(mutex)； End Outer() Begin P(mutex); 注銷；注銷； V(mutex); V(SN); End 第二章第二章 進(jìn)程管理進(jìn)程管理練練 習(xí)習(xí) 4n 三個(gè)進(jìn)程三個(gè)進(jìn)程R、W1、W2共享一個(gè)緩沖區(qū)共享一個(gè)緩沖區(qū)Buf。進(jìn)程。進(jìn)程R讀入數(shù)據(jù)到讀入數(shù)據(jù)到Buf中；中；若緩沖區(qū)中的數(shù)為奇數(shù)，則進(jìn)程若緩沖區(qū)中的數(shù)為奇數(shù)，則進(jìn)程W1將其取出顯示；若緩沖區(qū)中的數(shù)將其取出顯示；若緩沖區(qū)中的數(shù)為偶數(shù)，則進(jìn)程為偶數(shù)，則進(jìn)程W2將其取出顯示。對(duì)它們有如下的限制條件：將其取出顯示。對(duì)它們有如下的限制條

47、件：n 1）緩沖區(qū)中每次只能存放一個(gè)數(shù)；）緩沖區(qū)中每次只能存放一個(gè)數(shù)；n 2）僅當(dāng)緩沖區(qū)中沒有數(shù)，或）僅當(dāng)緩沖區(qū)中沒有數(shù)，或W1或或W2將數(shù)取走后，進(jìn)程將數(shù)取走后，進(jìn)程R才可才可以將新讀入的數(shù)放到緩沖區(qū)中；以將新讀入的數(shù)放到緩沖區(qū)中；n 3）進(jìn)程）進(jìn)程W1或或W2對(duì)每次存入緩沖區(qū)中的數(shù)只能顯示一次，且對(duì)每次存入緩沖區(qū)中的數(shù)只能顯示一次，且W1和和W2都不能從空的緩沖區(qū)中取數(shù)。都不能從空的緩沖區(qū)中取數(shù)。n假定開始時(shí)，緩沖區(qū)為空。利用記錄型信號(hào)量及假定開始時(shí)，緩沖區(qū)為空。利用記錄型信號(hào)量及wait、signal操作寫操作寫出三個(gè)并發(fā)進(jìn)程正確工作程序。出三個(gè)并發(fā)進(jìn)程正確工作程序。第二章第二章 進(jìn)程管

48、理進(jìn)程管理var s,s1,s2:semaphore:=1,0,0begin parbegin PR:begin repeat 從輸入設(shè)備讀到一個(gè)數(shù)從輸入設(shè)備讀到一個(gè)數(shù)B; wait(s); 放入放入; if B=奇數(shù)奇數(shù) then signal(s1); else signal(s2); until false; end; PW2:begin repeat wait(s2); y:=B; signal(s); 打印打印y； until false; end;parendPW1:begin repeat wait(s1); x:=B; signal(s); 打印打印x； until false

49、; end;第二章第二章 進(jìn)程管理進(jìn)程管理蘋果桔子問(wèn)題蘋果桔子問(wèn)題 桌上有一只盤子，每次只能放入一只水桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果果；爸爸專向盤子中放蘋果(apple)(apple)，媽媽，媽媽專向盤子中放桔子專向盤子中放桔子(orange)(orange)，一個(gè)兒子專，一個(gè)兒子專等吃盤子中的桔子，一個(gè)女兒專等吃盤子等吃盤子中的桔子，一個(gè)女兒專等吃盤子里的蘋果。里的蘋果。第二章第二章 進(jìn)程管理進(jìn)程管理nsp:semaphore； /* 盤子里可以放幾個(gè)水果盤子里可以放幾個(gè)水果 */nsg1:semaphore； /* 盤子里有桔子盤子里有桔子 */nsg2:sem

50、aphore； /* 盤子里有蘋果盤子里有蘋果 */信號(hào)量初值信號(hào)量初值n sp := 1; /* 盤子里允許放一個(gè)水果盤子里允許放一個(gè)水果*/n sg1 := 0; /* 盤子里沒有桔子盤子里沒有桔子 */n sg2 := 0; /* 盤子里沒有蘋果盤子里沒有蘋果*/第二章第二章 進(jìn)程管理進(jìn)程管理cobegincobeginprocess fatherprocess father beginbegin repeat repeat 削一個(gè)蘋果削一個(gè)蘋果；P(sp);P(sp);把蘋果放入把蘋果放入plateplate；V(sg2);V(sg2); until false; until fals

51、e;end;end;process motherprocess mother beginbegin repeat repeat 剝一個(gè)桔子剝一個(gè)桔子；P(sp);P(sp);把桔子放入把桔子放入plateplate；V(sg1);V(sg1); until false; until false;end;end;process sonprocess son beginbegin repeat repeat P(sg1); P(sg1);從從plateplate中取桔子；中取桔子；V(sp);V(sp);吃桔子；吃桔子； until false;until false;end;end;proces

52、s daughterprocess daughter beginbegin repeat repeat P(sg2); P(sg2); 從從plateplate中取蘋果；中取蘋果； V(sp);V(sp); 吃蘋果；吃蘋果； until false;until false;end;end;coendcoend第二章第二章 進(jìn)程管理進(jìn)程管理 void reader() while(1) wait(queue); wait(Rmutex); if(0 = readcount)wait(mutex); readcount = readcount + 1; signal(rdcntmutex); si

53、gnal(queue); read . wait(Rmutex); readcount = readcount - 1; if(0 = readcount)signal(mutex); signal(Rmutex); void writer() while(1) wait(Wmutex); if(0 =writecount)wait(queue); writecount = writecount + 1; signal(Wmutex); wait(mutex); write . signal(mutex); wait(Wmutex); writecount = writecount - 1;

54、if(0 = writecount)signal(queue); signal(Wmutex); semaphore mutex=1, Rmutex=1, Wmutex=1, queue=1;int readcount = 0, writecount = 0; 第二章第二章 進(jìn)程管理進(jìn)程管理 第二章第二章 進(jìn)程管理進(jìn)程管理while(1) wait(z); /用來(lái)保證寫者優(yōu)先用來(lái)保證寫者優(yōu)先 wait(rsem); /判斷有沒有寫進(jìn)程在臨界區(qū)，有則等待，否則拒判斷有沒有寫進(jìn)程在臨界區(qū)，有則等待，否則拒絕新的寫進(jìn)程進(jìn)來(lái)絕新的寫進(jìn)程進(jìn)來(lái) wait(x); /開始對(duì)開始對(duì)readcount的互斥訪問(wèn)

55、的互斥訪問(wèn) readcount+; /更新讀進(jìn)程數(shù)量更新讀進(jìn)程數(shù)量 if (readcount=1) wait(wsem); /第一個(gè)讀進(jìn)程第一個(gè)讀進(jìn)程需要判斷是否有寫進(jìn)程在進(jìn)行寫操作，有的話需要等待，沒有的話不讓需要判斷是否有寫進(jìn)程在進(jìn)行寫操作，有的話需要等待，沒有的話不讓寫進(jìn)程進(jìn)行新寫操作寫進(jìn)程進(jìn)行新寫操作 signal(x); /結(jié)束對(duì)結(jié)束對(duì)readcount的互斥訪問(wèn)的互斥訪問(wèn) signal(rsem); /歸還鎖，讓寫進(jìn)程可以進(jìn)臨界區(qū)歸還鎖，讓寫進(jìn)程可以進(jìn)臨界區(qū) signal(z); Void reader () 第二章第二章 進(jìn)程管理進(jìn)程管理 doReading(); wait(x

56、); /開始對(duì)開始對(duì)readcount的互斥訪問(wèn)的互斥訪問(wèn) readcount-; /更新讀進(jìn)程數(shù)量更新讀進(jìn)程數(shù)量 if (readcount=0) signal(wsem); /最后一個(gè)離開臨界區(qū)的讀進(jìn)程需最后一個(gè)離開臨界區(qū)的讀進(jìn)程需要?dú)w還鎖，讓寫進(jìn)程可以進(jìn)行寫操作要?dú)w還鎖，讓寫進(jìn)程可以進(jìn)行寫操作 signal(x); /結(jié)束對(duì)結(jié)束對(duì)readcount的互斥訪問(wèn)的互斥訪問(wèn) 第二章第二章 進(jìn)程管理進(jìn)程管理void writer() while(1) wait(y); /開始對(duì)開始對(duì)writecount的互斥訪問(wèn)的互斥訪問(wèn) writecount+; /更新寫進(jìn)程數(shù)量更新寫進(jìn)程數(shù)量 if (wri

57、tecount=1) wait(rsem); /第一個(gè)寫進(jìn)程需要判斷是否有讀進(jìn)第一個(gè)寫進(jìn)程需要判斷是否有讀進(jìn)程在臨界區(qū)，有的話需要等待，沒有的話不讓新的讀進(jìn)程進(jìn)來(lái)程在臨界區(qū)，有的話需要等待，沒有的話不讓新的讀進(jìn)程進(jìn)來(lái) signal(y); /結(jié)束對(duì)結(jié)束對(duì)writecount的互斥訪問(wèn)的互斥訪問(wèn) wait(wsem); /限制同一時(shí)刻只能有一個(gè)寫進(jìn)程進(jìn)行寫操作限制同一時(shí)刻只能有一個(gè)寫進(jìn)程進(jìn)行寫操作 doWriting(); 第二章第二章 進(jìn)程管理進(jìn)程管理 signal(wsem); /結(jié)束對(duì)寫操作的限制結(jié)束對(duì)寫操作的限制 wait(y); /開始對(duì)開始對(duì)writecount的互斥訪問(wèn)的互斥訪問(wèn)

58、writecount-; /更新寫進(jìn)程數(shù)量更新寫進(jìn)程數(shù)量 if (writecount=0) signal(rsem); /最后一個(gè)離開臨界區(qū)的寫進(jìn)程需要?dú)w最后一個(gè)離開臨界區(qū)的寫進(jìn)程需要?dú)w還鎖，讓讀進(jìn)程可以進(jìn)臨界區(qū)還鎖，讓讀進(jìn)程可以進(jìn)臨界區(qū) signal(y); /結(jié)束對(duì)結(jié)束對(duì)writecount的互斥訪問(wèn)的互斥訪問(wèn) 第二章第二章 進(jìn)程管理進(jìn)程管理2.6 進(jìn)程通信進(jìn)程通信Process Communication第二章第二章 進(jìn)程管理進(jìn)程管理The type of process communication第二章第二章 進(jìn)程管理進(jìn)程管理(Shared-Memory System)第二章第二章

59、進(jìn)程管理進(jìn)程管理 .發(fā)送原語(yǔ)發(fā)送原語(yǔ) .接收原語(yǔ)接收原語(yǔ)（Message Passing System)第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理1間接通信：間接通信： 建立一個(gè)通信參與者共享的邏輯實(shí)體建立一個(gè)通信參與者共享的邏輯實(shí)體信箱信箱，發(fā)送發(fā)送者向信箱發(fā)送消息；接收者到信箱取消息。者向信箱發(fā)送消息；接收者到信箱取消息。用于聯(lián)系不十分緊密的用于聯(lián)系不十分緊密的進(jìn)程之間。進(jìn)程之間。 間接通信方式間接通信方式（Indirect Communication way）優(yōu)點(diǎn)：優(yōu)點(diǎn)：信箱可實(shí)現(xiàn)信箱可實(shí)現(xiàn)“實(shí)時(shí)實(shí)時(shí)”或或“非實(shí)時(shí)非實(shí)時(shí)”通信。在讀通信。在

60、讀/寫時(shí)間上具有隨機(jī)寫時(shí)間上具有隨機(jī)性。性。 共享的邏輯實(shí)體可以是操作系統(tǒng)在核心空間提供的一組數(shù)據(jù)結(jié)構(gòu)，共享的邏輯實(shí)體可以是操作系統(tǒng)在核心空間提供的一組數(shù)據(jù)結(jié)構(gòu)，也可以磁盤上的文件為基礎(chǔ)，其特點(diǎn)是不只屬于通信中的任意一方，而也可以磁盤上的文件為基礎(chǔ)，其特點(diǎn)是不只屬于通信中的任意一方，而是一個(gè)中間實(shí)體。是一個(gè)中間實(shí)體。ABCDESendReceive第二章第二章 進(jìn)程管理進(jìn)程管理2信箱：信箱：包含有多個(gè)消息的隊(duì)列。系統(tǒng)為信箱通信提供若干包含有多個(gè)消息的隊(duì)列。系統(tǒng)為信箱通信提供若干條原語(yǔ)，實(shí)現(xiàn)對(duì)信箱的管理。條原語(yǔ)，實(shí)現(xiàn)對(duì)信箱的管理。1）信箱的創(chuàng)建和撤消）信箱的創(chuàng)建和撤消 進(jìn)程利用信箱創(chuàng)建原語(yǔ)建立一個(gè)新信箱。進(jìn)程利用信箱創(chuàng)建原語(yǔ)建立一個(gè)新信箱。信箱頭信箱頭