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

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

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

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

4、(4)要求互斥要求互斥，設置，設置公用信號量公用信號量n mutex保證生產(chǎn)者進程和消費者進程之間的互斥保證生產(chǎn)者進程和消費者進程之間的互斥（初值為（初值為1）。）。 $第二章第二章 進程管理進程管理生產(chǎn)者消費者動畫演示（1）$第二章第二章 進程管理進程管理生產(chǎn)者消費者動畫演示（生產(chǎn)者消費者動畫演示（2）$第二章第二章 進程管理進程管理生產(chǎn)者消費者動畫演示（生產(chǎn)者消費者動畫演示（3）$第二章第二章 進程管理進程管理生產(chǎn)者消費者動畫演示（生產(chǎn)者消費者動畫演示（4）$第二章第二章 進程管理進程管理produce(data)；Begin wait(empty); wait(mutex); 送數(shù)據(jù)入緩

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

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

7、，n，0； buffer：array0，n-1 of item; in , out : integer：=0，0；$第二章第二章 進程管理進程管理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:=buf

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

9、roducer:begin 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$第二章第二章 進程管理進程管理二、哲學家進餐問題二、哲學家進餐問題（Dining Philosopher Problem）準備進餐準備進餐進進餐餐準備進餐準備進餐進餐進餐 五個哲學家，共用一張五個哲學家，共用一張圓桌，五支筷子

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

11、re 所有信號量初值為所有信號量初值為1， :=1, 1, 1, 1, 1;$第二章第二章 進程管理進程管理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哲學家進餐活動可描述為：哲學家進餐活動可描述為： Think； wait(chopsticki)； wait(chopsticki+1 mod 5)； eat ； signal(chopsticki； signal(

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

13、子；偶數(shù)號人先拿）規(guī)定奇數(shù)號人先拿左筷子，后拿右筷子；偶數(shù)號人先拿右筷子，后拿左筷子。五個哲學家都先競爭奇數(shù)號筷子，獲右筷子，后拿左筷子。五個哲學家都先競爭奇數(shù)號筷子，獲得后再競爭偶數(shù)號筷子。最后總有一個哲學家能獲得兩只筷得后再競爭偶數(shù)號筷子。最后總有一個哲學家能獲得兩只筷子。子。$第二章第二章 進程管理進程管理0123401234r 4）用）用AND信號量機制信號量機制可獲得最簡潔解法?？色@得最簡潔解法。$第二章第二章 進程管理進程管理$第二章第二章 進程管理進程管理AND信號量實現(xiàn)哲學家就餐描述信號量實現(xiàn)哲學家就餐描述var chopstick:array 0,4 of semaphore

14、:=(1,1,1,1,1);process i repeat think; eat; until false; 哲學家問題對于多個競爭進程互斥地訪問有限資源哲學家問題對于多個競爭進程互斥地訪問有限資源( (如如I/OI/O設備設備) )這一類問題的建模十分有用。這一類問題的建模十分有用。 $第二章第二章 進程管理進程管理 一個數(shù)據(jù)對象被多個進程共享。其中有些進程要求讀，另一個數(shù)據(jù)對象被多個進程共享。其中有些進程要求讀，另一些進程要求寫或修改。要求讀的進程稱為一些進程要求寫或修改。要求讀的進程稱為“reader進程進程”；其它的稱為其它的稱為“writer進程進程”。允許多個允許多個reader

15、進程同時執(zhí)行；不進程同時執(zhí)行；不允許一個允許一個writer進程和其它進程和其它reader進程或進程或writer進程同時訪問進程同時訪問共享對象。共享對象。l a、多個、多個reader可同時訪問這組共享數(shù)據(jù)可同時訪問這組共享數(shù)據(jù)并發(fā)并發(fā)；l b、多個、多個writer不可同時訪問這組共享數(shù)據(jù)不可同時訪問這組共享數(shù)據(jù)互斥；互斥；l c、reader與與writer不可同時訪問這組共享數(shù)據(jù)不可同時訪問這組共享數(shù)據(jù)互斥互斥 它為數(shù)據(jù)庫訪問建立了一個模型。它為數(shù)據(jù)庫訪問建立了一個模型。 三、讀者三、讀者-寫者問題寫者問題（Reader/Writer ProblemReader/Writer Pr

16、oblem）$第二章第二章 進程管理進程管理r1r2rnwRreadcount信號量設置信號量設置 Wmutex：W/R和和W/W的互斥。的互斥。 Rmutex：讀者對讀者對readcount的互斥操作。的互斥操作?？刂谱兞吭O置：控制變量設置：Readcount 記錄讀的個數(shù)。記錄讀的個數(shù)。$第二章第二章 進程管理進程管理申請申請Rmutex若若readcount=0申請申請Wmutexreadcount+1 讀操作讀操作釋放釋放Rmutex申請申請Rmutexreadcount1若若readcount=0釋放釋放Wmutex釋放釋放Rmutexvar rmutex,wmutex:semaph

17、ore:=1,1 readcount:integer:=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 讀者寫者問題描述讀者寫

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

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

20、: begin repeat 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 信號量集機制解決讀者寫者問題信號量集機制解決讀者寫者問題$第二章第二章 進程管理進程管理四、打瞌睡的理發(fā)師問題四、打瞌睡的理發(fā)師問題 理發(fā)店里有一位理發(fā)師，一把理理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和發(fā)

21、椅和N N把供等候理發(fā)的顧客坐的把供等候理發(fā)的顧客坐的椅子椅子； 理發(fā)師為理發(fā)椅上的顧客理發(fā)，理發(fā)師為理發(fā)椅上的顧客理發(fā)，沒有顧客就在理發(fā)椅上睡覺；沒有顧客就在理發(fā)椅上睡覺； 第一個顧客到來第一個顧客到來，他必須先喚醒，他必須先喚醒理發(fā)師理發(fā)師； 如如果顧客來時理發(fā)師正在果顧客來時理發(fā)師正在忙忙，若若有空椅子有空椅子，則則坐下來等；否則離開坐下來等；否則離開。$第二章第二章 進程管理進程管理說說 明：明：理發(fā)師和每位顧客都分別是一個進程。理發(fā)師和每位顧客都分別是一個進程。r 理發(fā)師：理發(fā)師：看是否有顧客，若沒有，在理發(fā)椅上睡覺；否則，看是否有顧客，若沒有，在理發(fā)椅上睡覺；否則，為等待最久的顧客

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

23、理# define CHAIRS 5 /*為等待的顧客準備的椅子數(shù)為等待的顧客準備的椅子數(shù)*/semaphore customers=0; /*等待服務的顧客數(shù)等待服務的顧客數(shù)*/ semaphore barbers=0; /*等待顧客的理發(fā)師數(shù)等待顧客的理發(fā)師數(shù)*/ semaphore mutex=1; /*用于互斥用于互斥*/ int waiting=0; /*等待的顧客等待的顧客(還沒理發(fā)的還沒理發(fā)的)*/ 三個信號量三個信號量nCustomers：用來記錄等候理發(fā)的顧客數(shù)用來記錄等候理發(fā)的顧客數(shù)(不包括正在理不包括正在理發(fā)的顧客發(fā)的顧客)，初值為，初值為0；nBarbers：等候顧客的

24、理發(fā)師數(shù)，初值為等候顧客的理發(fā)師數(shù)，初值為0；nMutex：用于對用于對waiting 變量的互斥。變量的互斥。信號量設置和變量定義信號量設置和變量定義$第二章第二章 進程管理進程管理Void customers(void) wait(mutex); /*互斥進入臨界區(qū)互斥進入臨界區(qū)*/ If(waiting0 S0 表示有表示有S S個資源可用個資源可用S=0 S=0 表示無資源可用表示無資源可用S0 S0 則則| S | S |表示表示S S等待隊列中的進程個數(shù)等待隊列中的進程個數(shù)P(S): P(S): 表示申請一個資源表示申請一個資源 V(S)V(S)： 表示釋放一個資源。表示釋放一個資

25、源。信號量的初值應該大于等于信號量的初值應該大于等于0 01 信號量的物理含義：信號量的物理含義：$第二章第二章 進程管理進程管理l 當為當為互斥操作互斥操作時，它們同處于時，它們同處于同一進程同一進程; ;l 當為當為同步操作同步操作時，則時，則不在同一進程不在同一進程中出現(xiàn)中出現(xiàn); ;l 如果如果P(S1)P(S1)和和P(S2)P(S2)兩個操作在一起，那么兩個操作在一起，那么P P操作的順操作的順序至關重要序至關重要, ,一個同步一個同步P P操作與一個互斥操作與一個互斥P P操作在一起操作在一起時時同步同步P P操作在互斥操作在互斥P P操作前操作前；l 而兩個而兩個V V操作的順序

26、無關緊要。操作的順序無關緊要。2 P.V操作必須成對出現(xiàn)操作必須成對出現(xiàn):$第二章第二章 進程管理進程管理優(yōu)點：優(yōu)點： 簡單，而且表達能力強簡單，而且表達能力強（用（用P.V操作可解決任何同步互斥操作可解決任何同步互斥問題）。問題）。缺點：缺點： 不夠安全；不夠安全；P.V操作使用不當會出現(xiàn)死鎖；遇到復雜同步操作使用不當會出現(xiàn)死鎖；遇到復雜同步互斥問題時實現(xiàn)復雜?；コ鈫栴}時實現(xiàn)復雜。3 P.V操作的優(yōu)缺點操作的優(yōu)缺點$第二章第二章 進程管理進程管理2.5 管程機制 Monitor Mechanism 信號量機制為互斥、同步問題的解決提供了有效靈活的工信號量機制為互斥、同步問題的解決提供了有效靈

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

28、告進程。訪問該臨界資源的進程都需先報告“秘秘書書”，由，由“秘書秘書”實現(xiàn)諸進程的同步。實現(xiàn)諸進程的同步。Hoare(1974)和和Hansen(1975)，發(fā)展為，發(fā)展為（Monitors）。）。 把并發(fā)進程間的操作，集中于相應的管程中。把并發(fā)進程間的操作，集中于相應的管程中。 管程與管程與信號量機制功能等價，且更容易控制。信號量機制功能等價，且更容易控制。解決方法：解決方法：$第二章第二章 進程管理進程管理一、管程的定義一、管程的定義（The definition of monitor）1 定義：定義： “2.5.1 管程的基本概念管程的基本概念The basic concepts of

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

30、源進行操作的部分資源進行操作的部分)； 4) 對局部于管程的數(shù)據(jù)對局部于管程的數(shù)據(jù)設置初始值的語句。設置初始值的語句。二、二、 管程的組成管程的組成（The Composition of Monitor）$第二章第二章 進程管理進程管理type monitor-name=monitor variable declarations procedure entry P1(); beginend; procedure entry Pn(); beginend; begin initialization code end $第二章第二章 進程管理進程管理 1 1）局部于局部于管程的管程的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)

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

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

33、喚醒操作為管程中最后一個可執(zhí)行的操作。Hoare采用采用Hansen建議建議說說 明明$第二章第二章 進程管理進程管理圖圖2 21111管管程程示示意意圖圖EntranceQueue ofEnteringProcessesMonitior Waiting Area Condition c1C1.wait. . . .condition cn. . . .Cn.waitUrgent Queuecsignal ExitM0NITOR Local DataCondition VariablesProcedure 1Procedure kInitialization Code$第二章第二章 進程管理進

34、程管理四、管程實現(xiàn)互斥和同步四、管程實現(xiàn)互斥和同步1 互斥互斥 管程的第三個特性，使他們能有效的完成互斥。進入管程管程的第三個特性，使他們能有效的完成互斥。進入管程的互斥由編譯器負責，寫管程的人無需關心。的互斥由編譯器負責，寫管程的人無需關心。2 同步同步 管程實現(xiàn)同步，需設置：管程實現(xiàn)同步，需設置：l 條件變量條件變量x，表示等待原因。，表示等待原因。l 利用利用wait和和signal操作表示因等待原因出現(xiàn)而等待、操作表示因等待原因出現(xiàn)而等待、喚醒一個某原因而等待的進程。喚醒一個某原因而等待的進程。$第二章第二章 進程管理進程管理& 設設var x:condition，則可有，則可有 x.

35、wait因等待因等待x而阻塞，直至其他進程執(zhí)行而阻塞，直至其他進程執(zhí)行x.signal。 x.signal喚醒一個因等待喚醒一個因等待x而阻塞的進程。而阻塞的進程。 如果如果x等待隊列中無進程阻塞，該操作不產(chǎn)生任何作用。（與等待隊列中無進程阻塞，該操作不產(chǎn)生任何作用。（與信號量的信號量的signal不同）不同）& 如：因共享資源忙而進程等待，條件變量可定義為：如：因共享資源忙而進程等待，條件變量可定義為：nonbusy：condiction。 則則wait為：為：nonbusy.wait，signal 為：為：nonbusy.signal條件變量和相關操作條件變量和相關操作$第二章第二章 進程

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

37、,notempty:condition; 2.5.2 利用管程解決生產(chǎn)者利用管程解決生產(chǎ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

38、n count:=count-1 if notfull.queue then notfull.signal endbegin in:=out:=0; count:=0; end$第二章第二章 進程管理進程管理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$第二章第二章 進程管理進程管理練練 習習 1 設某計算機有兩個設某計算機有兩個I/OI/

39、O通道：分別掛一臺輸入機和一臺通道：分別掛一臺輸入機和一臺打印機?？ㄆ瑱C上有一疊數(shù)據(jù)卡片，現(xiàn)在要把這些數(shù)打印機。卡片機上有一疊數(shù)據(jù)卡片，現(xiàn)在要把這些數(shù)據(jù)逐一輸入到緩沖區(qū)據(jù)逐一輸入到緩沖區(qū)B1B1，然后再復制到緩沖區(qū)，然后再復制到緩沖區(qū)B2B2，并，并在打印機上打印出來。在打印機上打印出來。 問：系統(tǒng)可設哪些進程來完成這個任務？用問：系統(tǒng)可設哪些進程來完成這個任務？用P.VP.V原語寫原語寫這些進程的同步算法。這些進程的同步算法。 $第二章第二章 進程管理進程管理& 系統(tǒng)可設系統(tǒng)可設3 3個進程：輸入進程個進程：輸入進程R R、復制進程、復制進程C C、打印進程、打印進程P P；& 這些進程之間

40、的相互制約關系：這些進程之間的相互制約關系： R R受受C C的約束；的約束；C C受受R R、P P的約束；的約束；P P受受C C的約束。的約束。 & 信號量設置信號量設置 B1fullB1full：緩沖區(qū)：緩沖區(qū)B1B1滿，初值滿，初值0 0； B1emptyB1empty：緩沖區(qū)：緩沖區(qū)B1B1空，初值空，初值=1=1； B2fullB2full：緩沖區(qū)：緩沖區(qū)B2B2滿，初值滿，初值=0=0； B2emptyB2empty：緩沖區(qū)：緩沖區(qū)B2B2空，初值空，初值=1=1。 & 同步算法如下：同步算法如下：$第二章第二章 進程管理進程管理R進程進程P(B1empty)；輸入信息到輸入信

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

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

43、的車都駛出后才能進入。為此，雙方均應設置雙方均應設置計數(shù)器計數(shù)器記錄該方向是否有車輛在行駛。斥記錄該方向是否有車輛在行駛。斥進入的，進入的，r 保證計數(shù)器互斥使用的保證計數(shù)器互斥使用的互斥信號量互斥信號量。var mutex, ab,ba：Semaphore： 1,1,1$第二章第二章 進程管理進程管理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 wai

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

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

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

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

48、程管理var s,s1,s2:semaphore:=1,0,0begin parbegin PR:begin repeat 從輸入設備讀到一個數(shù)從輸入設備讀到一個數(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;$第二章第二章 進程管理進程管理蘋果桔子問題蘋果桔子問題 桌上有一只盤子，每次只能放入一只水桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果果；爸爸專向盤子中放蘋果(apple)(apple)，媽媽，媽媽專向盤子中放桔子專向盤子中放桔子(orange)(orange)，一個兒子專，一個兒子專等吃盤子中的桔子，一個女兒專等吃盤子等吃盤子中的桔子，一個女兒專等吃盤子里的蘋果。里的蘋果。$第二章第二章 進程管理進程管理sp:semaphore； /* 盤子里可以放幾個水果盤子里可以放幾個水果 */sg1:semaphore； /* 盤子里有桔子盤子里有桔子 */sg2:semaph

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

51、end;end;process motherprocess mother beginbegin repeat repeat 剝一個桔子剝一個桔子；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;process

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

53、nal(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; i

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

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

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

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

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

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

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