第三章進程管理(3)

1、1操作系統(tǒng)原理操作系統(tǒng)原理Principles of Operating System第三章第三章進進 程程 管管 理理(3)3.6 進程同步進程同步n3.6.1 同步的概念同步的概念n3.6.2 私用信號量私用信號量n3.6.3 用用P,V原語操作實現同步原語操作實現同步n3.6.4 生產者生產者-消費者問題消費者問題3.6.1 同步的概念同步的概念n例子例子: 計算進程和打印進程共同使用同一緩計算進程和打印進程共同使用同一緩沖區(qū)沖區(qū)Buf。教材。教材P593.6.1 同步的概念同步的概念n直接制約：直接制約：一組在異步環(huán)境下的并發(fā)進程，一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結果互為對方的執(zhí)

2、行條件各自的執(zhí)行結果互為對方的執(zhí)行條件，從而，從而限制各進程的執(zhí)行速度的過程稱為并發(fā)進程限制各進程的執(zhí)行速度的過程稱為并發(fā)進程間的直接制約，簡稱間的直接制約，簡稱直接制約直接制約。n異步環(huán)境：異步環(huán)境：主要指主要指各并發(fā)進程各并發(fā)進程的的執(zhí)行起始時執(zhí)行起始時間的隨機性間的隨機性和和執(zhí)行速度的獨立性執(zhí)行速度的獨立性。3.6.1 同步的概念同步的概念n同步：同步：把異步環(huán)境下的一組并發(fā)進程，把異步環(huán)境下的一組并發(fā)進程，因直因直接制約接制約而而互相發(fā)送消息互相發(fā)送消息而進行而進行互相合作、互互相合作、互相等待相等待，使得各進程按一定的速度執(zhí)行的過，使得各進程按一定的速度執(zhí)行的過程稱為程稱為進程間的同

3、步進程間的同步。n具有同步關系的一組并發(fā)進程稱為具有同步關系的一組并發(fā)進程稱為合作進程合作進程。3.6.1 同步的概念同步的概念n合作進程間互相發(fā)送的合作進程間互相發(fā)送的信號信號稱為稱為消息消息或或事件事件。wait(消息名）：進程等待合作進程發(fā)來消息名）：進程等待合作進程發(fā)來“消息名消息名”的消息。的消息。signal（消息名）：向合作進程發(fā)送（消息名）：向合作進程發(fā)送“消息名消息名”的消息。的消息。例例n利用過程利用過程wait和和signal描述上例中的計算進描述上例中的計算進程程PC和打印進程和打印進程PP的同步關系。的同步關系。n(1) 設消息名設消息名Bufempty表示表示Buf

4、空，消息名空，消息名Buffull表示表示Buf中裝滿了數據。中裝滿了數據。n(2) 初始化初始化Bufempty=true，Buffull=false 。解解PC：A: wait(Bufempty) /等等合作者等等合作者Pp發(fā)來發(fā)來Bufempty為空的消息為空的消息計算計算Buf 計算結果計算結果Bufempty falsesignal(Buffull) /向合作者向合作者Pp發(fā)送發(fā)送Buffull為滿的消息為滿的消息GotoA解解PP：B: wait(Buffull) /等等合作者等等合作者Pc發(fā)來發(fā)來Buffull為滿的消息為滿的消息打印打印Buf中的數據中的數據清除清除Buf中的數

5、據中的數據Buffull falsesignal(Bufempty) /向合作者向合作者Pc發(fā)送發(fā)送Bufempty為空的消息為空的消息GotoB3.6.2 私用信號量私用信號量n私用信號量：私用信號量：只與制約進程及被制約進程有只與制約進程及被制約進程有關的信號量。關的信號量。n公用信號量：公用信號量：與一組并發(fā)進程有關的信號量。與一組并發(fā)進程有關的信號量。n進程進程Pi的私用信號量的私用信號量Semi：是：是從制約進程發(fā)從制約進程發(fā)送來的送來的、進程進程Pi的執(zhí)行條件所需要的的執(zhí)行條件所需要的消息消息。3.6.3 用用P,V原語操作實現同步原語操作實現同步n解決步驟：解決步驟：n為各并發(fā)進

6、程設置私用信號量；為各并發(fā)進程設置私用信號量；n為私用信號量賦初值；為私用信號量賦初值；1.利用，原語和私用信號量規(guī)定各進程的執(zhí)利用，原語和私用信號量規(guī)定各進程的執(zhí)行順序。行順序。例例設進程設進程PA和和PB通過緩沖區(qū)隊列傳遞數據。通過緩沖區(qū)隊列傳遞數據。PA為發(fā)送進程，為發(fā)送進程，PB為接收進程。為接收進程。PA發(fā)送數據時調用發(fā)送過程發(fā)送數據時調用發(fā)送過程deposit(data)，PB接收數據時調用過程接收數據時調用過程remove(data)。且數據的發(fā)送和。且數據的發(fā)送和接收過程滿足如下條件：接收過程滿足如下條件： (1) 在在PA至少送一塊數據入一個緩沖區(qū)之前，至少送一塊數據入一個緩

7、沖區(qū)之前，PB不可能從緩沖區(qū)中不可能從緩沖區(qū)中取出數據（假定數據塊長等于緩沖區(qū)長度）；取出數據（假定數據塊長等于緩沖區(qū)長度）； (2) PA往緩沖隊列發(fā)送數據時，至少有一個緩沖區(qū)是空的；往緩沖隊列發(fā)送數據時，至少有一個緩沖區(qū)是空的； (3) 由由PA發(fā)送的數據塊在緩沖隊列中按先進先出（發(fā)送的數據塊在緩沖隊列中按先進先出（FIFO）方式排列。）方式排列。 描述發(fā)送過程描述發(fā)送過程deposit(data)和接收過程和接收過程remove(data)。分析分析nPa和和Pb要合作完成，這是一個同步問題，要合作完成，這是一個同步問題，要設置私用信號量。要設置私用信號量。n設設Pa（放，（放，depo

8、sit）的）的私用信號量私用信號量Bufempty，表示，表示空緩沖區(qū)的個數空緩沖區(qū)的個數，初值為，初值為n；n設設Pb（取，（取，remove）的）的私用信號量私用信號量Buffull，表示表示已用緩沖區(qū)的個數已用緩沖區(qū)的個數，初值為，初值為0。進程的操作流程進程的操作流程PA: deposit(data):是否有空緩沖區(qū)？無則等待。是否有空緩沖區(qū)？無則等待。按按FIFO方式選擇一個空緩沖區(qū)方式選擇一個空緩沖區(qū)Buf(x)Buf(x) dataBuf(x)置滿標記置滿標記設置緩沖區(qū)有數據的標志設置緩沖區(qū)有數據的標志PB:remove(data):是否有裝滿數據的緩沖區(qū)？無則等。是否有裝滿數據

9、的緩沖區(qū)？無則等。按按FIFO方式選擇一個裝滿數據的緩方式選擇一個裝滿數據的緩沖區(qū)沖區(qū)Buf(x)；data Buf(x)；Buf(x)置空標記；置空標記；設置緩沖區(qū)有空間的標志。設置緩沖區(qū)有空間的標志。解解PA: deposit(data):begin local xP(Bufempty)按按FIFO方式選擇一個空緩沖區(qū)方式選擇一個空緩沖區(qū)Buf(x)Buf(x) dataBuf(x)置滿標記置滿標記（Buffull）end解解PB: remove(data):Begin local x （Buffull）；）；按按FIFO方式選擇一個裝滿數據的緩沖區(qū)方式選擇一個裝滿數據的緩沖區(qū)Buf(x)

10、；data Buf(x)；Buf(x)置空標記；置空標記；（Bufempty）；）；end思思 考考n1、在該題中需要考慮互斥嗎？為什么？、在該題中需要考慮互斥嗎？為什么？n2、如果每次只允許一個進程對緩沖隊列進、如果每次只允許一個進程對緩沖隊列進行操作時怎么辦？行操作時怎么辦？問題問題2分析分析n如果每次只允許一個進程對緩沖隊列進行操如果每次只允許一個進程對緩沖隊列進行操作時，涉及到進程間的互斥，需要設置一個作時，涉及到進程間的互斥，需要設置一個公用信號量公用信號量mutex，初值為，初值為1，表示可用緩，表示可用緩沖區(qū)的個數。沖區(qū)的個數。3.6.3 用用P,V原語操作實現同步原語操作實現同

11、步n用用P,V原語操作實現同步應注意的問題：原語操作實現同步應注意的問題：n分析進程間的制約關系，確定信號量種類。在確保進程分析進程間的制約關系，確定信號量種類。在確保進程間有正確的同步關系的情況下，哪個進程先執(zhí)行，哪些間有正確的同步關系的情況下，哪個進程先執(zhí)行，哪些進程后執(zhí)行，彼此之間通過什么資源（信號量）進行協進程后執(zhí)行，彼此之間通過什么資源（信號量）進行協調，從而明確設置哪些信號量。調，從而明確設置哪些信號量。n信號量的初值與相應資源的數量有關，也與信號量的初值與相應資源的數量有關，也與P、V操作操作在程序代碼中出現的位置有關。在程序代碼中出現的位置有關。1.同一信號量的同一信號量的P、

12、V操作要成對出現，但它們分別在不操作要成對出現，但它們分別在不同的進程代碼中。同的進程代碼中。例例 子子設公共汽車上有一位司機和一位售票員，它們的活設公共汽車上有一位司機和一位售票員，它們的活動如下，請分析司機與售票員之間的關系，如何動如下，請分析司機與售票員之間的關系，如何用用PV操作實現。操作實現。 司機：司機： 售票員：售票員：啟動車輛啟動車輛正常行車正常行車到站停車到站停車售票售票開車門開車門關車門關車門解解同步關系分析同步關系分析n為了安全起見，顯然要求：為了安全起見，顯然要求：關車門后才能啟關車門后才能啟動車輛；到站停車后才能開車門動車輛；到站停車后才能開車門。所以司機。所以司機和

13、售票員在到站停車、開門、關門、啟動車和售票員在到站停車、開門、關門、啟動車輛這幾個活動之間存在著同步關系。輛這幾個活動之間存在著同步關系。進程的操作流程進程的操作流程是否關門？是否關門？啟動車輛啟動車輛正常行駛正常行駛到站停車到站停車設車停標志設車停標志售票售票是否停車？是否停車？開車門開車門關車門關車門設門關標志設門關標志司機司機進程進程售票員進程：售票員售票員進程進程解解算法算法n由于司機與售票員之間要互通消息，由于司機與售票員之間要互通消息，司機司機進程進程設置一個設置一個私有信號量私有信號量run，用于判斷司，用于判斷司機機能否進行工作能否進行工作，初值為初值為1。售票員進程售票員進程

14、設設置一個置一個私有信號量私有信號量stop，用于判斷，用于判斷是否停是否停車車，售票員，售票員是否能夠開車門是否能夠開車門，初值為初值為0。解解算法算法n同步算法描述如下：同步算法描述如下：P（run）啟動車輛啟動車輛正常行駛正常行駛到站停車到站停車V（stop）售票售票P（stop）開車門開車門關車門關車門V（run）司機司機進程進程售票員進程：售票員售票員進程進程解解算法算法n程序中程序中PV操作出現的順序與信號量的初值設操作出現的順序與信號量的初值設置有關，以本題為例，算法描述如下時，置有關，以本題為例，算法描述如下時， run、stop的初值應為？的初值應為？售票售票P（stop）開

15、車門開車門關車門關車門V（run）售票員售票員進程：進程：正常行駛正常行駛到站停車到站停車 V（stop） P（run）啟動車輛啟動車輛司機司機進程進程例子例子n桌上有一空盤，允許存放一只水果。爸爸可桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時一次只能放一只水果供吃者取規(guī)定當盤空時一次只能放一只水果供吃者取用，請用用，請用P、V原語實現爸爸、兒子、女兒三原語實現爸爸、兒子、女兒三個并發(fā)進程的關系。個并發(fā)進程的關系。分析分析n爸爸、兒子、女

16、兒共用一個盤子，盤中一次只能放爸爸、兒子、女兒共用一個盤子，盤中一次只能放一個水果。當盤子為空時，爸爸可將一個水果放入一個水果。當盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待；若放入果盤中的是蘋果，則允許女女兒必須等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。爸爸與兒子、爸爸與女兒之兒吃，兒子必須等待。爸爸與兒子、爸爸與女兒之間存在同步關系。間存在同步關系。n提示：提示：設置一個信號量表示可否向盤中放水果，一設置一個信號量表示可否向盤中放水果，一個信號量表示可否取桔子，一個信號量表示可否取個信號量

17、表示可否取桔子，一個信號量表示可否取蘋果。蘋果。解解n設置三個信號量設置三個信號量S、So、Sa，信號量，信號量S表示表示盤子是否為空，其初值為盤子是否為空，其初值為1；信號量；信號量So表示表示盤中是否有桔子，其初值為盤中是否有桔子，其初值為0；信號量；信號量Sa表表示盤中是否有蘋果，其初值為示盤中是否有蘋果，其初值為0。同步描述。同步描述如下：如下：解解int S1;int Sa0;int So0; main() begin father(); /*父親進程父親進程*/ son(); /*兒子進程兒子進程*/ daughter(); /*女兒進程女兒進程*/ end father() wh

18、ile(1) P(S); 將水果放入盤中將水果放入盤中; if（放入的是桔子）（放入的是桔子）V(So); else V(Sa); son() while(1) P(So); 從盤中取出桔子從盤中取出桔子; V(S); 吃桔子吃桔子; daughter() while(1) P(Sa); 從盤中取出蘋果從盤中取出蘋果; V(S); 吃蘋果吃蘋果; 3.6.4 生產者/消費者問題n生產者消費者問題是一種同步問題的抽生產者消費者問題是一種同步問題的抽象描述。計算機系統(tǒng)中的每個進程都可象描述。計算機系統(tǒng)中的每個進程都可以消費（使用）或生產（釋放）某類資以消費（使用）或生產（釋放）某類資源。這些資源可

19、以是硬件資源，也可以源。這些資源可以是硬件資源，也可以是軟件資源。是軟件資源。n當某一進程使用某一資源時，可以看作當某一進程使用某一資源時，可以看作是消費，稱該進程為是消費，稱該進程為消費者消費者。而當某一。而當某一進程釋放某一資源時，它就相當于進程釋放某一資源時，它就相當于生產生產者者。問題描述把一個長度為的有界緩沖區(qū)（把一個長度為的有界緩沖區(qū)（n0)與一群生產者進程與一群生產者進程1，2，m和一群消費者進程和一群消費者進程1，2，k聯系起聯系起來（如圖來（如圖3.15所示）。所示）。設生產者進程和消費者進程是互相等效的，其中，各生產者進設生產者進程和消費者進程是互相等效的，其中，各生產者進

20、程使用的過程程使用的過程deposit(data)和各消費者使用的過程和各消費者使用的過程remove(data)可描述如下：可描述如下：首先，上述生產者首先，上述生產者-消費者問題是一個同步問題。即生產者和消費者問題是一個同步問題。即生產者和消費者之間滿足如下條件：消費者之間滿足如下條件：(1) 消費者想接收數據時，有界緩沖區(qū)中至少有一個單元是滿消費者想接收數據時，有界緩沖區(qū)中至少有一個單元是滿的；的；(2) 生產者想發(fā)送數據時，有界緩沖區(qū)中至少有一個單元是空生產者想發(fā)送數據時，有界緩沖區(qū)中至少有一個單元是空的。的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產者進程和各另外，由于有界緩沖區(qū)是

21、臨界資源，因此，各生產者進程和各消費者進程之間必須互斥執(zhí)行。消費者進程之間必須互斥執(zhí)行。圖圖3.15 生產者生產者-消費者問題消費者問題1問題分析n為解決生產者消費者問題，應該設兩個同步信為解決生產者消費者問題，應該設兩個同步信號量，一個說明號量，一個說明空緩沖區(qū)的數目空緩沖區(qū)的數目，用，用avail表示，表示，初值為有界緩沖區(qū)的大小初值為有界緩沖區(qū)的大小N，另一個說明，另一個說明已用緩已用緩沖區(qū)的數目沖區(qū)的數目，用，用full表示，初值為表示，初值為。n由于在此問題中有由于在此問題中有M個生產者和個生產者和N個消費者，它個消費者，它們在執(zhí)行生產活動和消費活動中要對有界緩沖們在執(zhí)行生產活動和消

22、費活動中要對有界緩沖區(qū)進行操作。區(qū)進行操作。有界緩沖區(qū)是一個臨界資源有界緩沖區(qū)是一個臨界資源，必，必須須互斥使用互斥使用，需要設置一個，需要設置一個互斥信號量互斥信號量mutex，其初值為其初值為。進程的操作流程進程的操作流程n生產者進程：生產者進程：deposit(data):判斷緩沖區(qū)是否有空間？判斷緩沖區(qū)是否有空間？判斷緩沖區(qū)是否可操作？判斷緩沖區(qū)是否可操作？送數據入緩沖區(qū)某單元送數據入緩沖區(qū)某單元設緩沖區(qū)有數據的標志。設緩沖區(qū)有數據的標志。設緩沖區(qū)可操作的標志。設緩沖區(qū)可操作的標志。n消費者進程：消費者進程： remove(data):判斷緩沖區(qū)是否有數據？判斷緩沖區(qū)是否有數據？判斷緩

23、沖區(qū)是否可操作？判斷緩沖區(qū)是否可操作？取緩沖區(qū)中某單元數據取緩沖區(qū)中某單元數據設緩沖區(qū)有空間的標志。設緩沖區(qū)有空間的標志。設緩沖區(qū)可操作的標志。設緩沖區(qū)可操作的標志。問題解問題解n生產者進程：生產者進程： deposit(data):begin（avail）（mutex）送數據入緩沖區(qū)某單元送數據入緩沖區(qū)某單元（full）（mutex）end問題解問題解n消費者進程：消費者進程： remove(data):begin（full）（mutex）取緩沖區(qū)中某單元數據取緩沖區(qū)中某單元數據（avail）（mutex）end思思 考考n上例中生產者進程、消費者進程中的兩個上例中生產者進程、消費者進程中的

24、兩個V操作是否可以交換位置，操作是否可以交換位置，P操作呢？為什么？操作呢？為什么？讀者讀者/寫者問題寫者問題 有兩組并發(fā)進程有兩組并發(fā)進程: : 讀者和寫者讀者和寫者, ,共享一組數據區(qū)共享一組數據區(qū) 要求：要求： 允許多個讀者同時執(zhí)行讀操作允許多個讀者同時執(zhí)行讀操作 不允許讀者、寫者同時操作不允許讀者、寫者同時操作 不允許多個寫者同時操作不允許多個寫者同時操作讀者優(yōu)先讀者優(yōu)先如果讀者來：如果讀者來：1 1）無讀者、寫者，新讀者可以讀）無讀者、寫者，新讀者可以讀2 2）有寫者等，但有其它讀者正在讀，則新讀者有寫者等，但有其它讀者正在讀，則新讀者也可以讀也可以讀3 3）有寫者寫，新讀者等）有寫

25、者寫，新讀者等如果寫者來：如果寫者來：1 1）無讀者，新寫者可以寫）無讀者，新寫者可以寫2 2）有讀者，新寫者等待）有讀者，新寫者等待3 3）有其它寫者，新寫者等待）有其它寫者，新寫者等待讀者優(yōu)先的解法讀者優(yōu)先的解法n設公用信號量設公用信號量w，用于讀者和寫者、寫者和寫者之間的互斥，用于讀者和寫者、寫者和寫者之間的互斥，初值初值w=1。n只要有一個讀者進程在讀，便不允許讀者進程去寫，所以要只要有一個讀者進程在讀，便不允許讀者進程去寫，所以要設一個設一個全局變量全局變量readcount，表示正在讀的讀者數目，初值，表示正在讀的讀者數目，初值readcount =0；僅當僅當readcount=

26、0， 讀者進程才需要執(zhí)行讀者進程才需要執(zhí)行P(w)操作。操作。n若若P(w)操作成功，讀者進程便可去讀，相應地做操作成功，讀者進程便可去讀，相應地做readcount +1操作操作。同理，。同理，僅當讀者進程完成時執(zhí)行了僅當讀者進程完成時執(zhí)行了Readcount-1操作后其值為操作后其值為0時，才須執(zhí)行時，才須執(zhí)行V(w)操作，以便讓寫者進程寫操作，以便讓寫者進程寫。n又因為又因為Readcount是一個可被多個讀者進程訪問的臨界資源是一個可被多個讀者進程訪問的臨界資源，因此，為它設置一個互斥信號量因此，為它設置一個互斥信號量mutex，用于對，用于對readcount 這個臨界資源的互斥訪問

27、，初值這個臨界資源的互斥訪問，初值mutex=1讀者：讀者： while (1) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 讀讀 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;寫者：寫者： while (1) P(w); 寫寫 V(w); ;例例 子子n某寺廟，有小和尚、老和尚若干廟內有一某寺廟，有小和尚、老和尚若干廟內有一水缸，由小和尚提水入缸，供老和尚飲水缸，由小和尚提水入缸，供老和尚飲用水缸可容納用水缸可容納 30 桶水，每次入水、取水桶水，每次入水

28、、取水僅為僅為1桶，不可同時進行。水取自同一井中，桶，不可同時進行。水取自同一井中，水井徑窄，每次只能容納一個水桶取水。設水井徑窄，每次只能容納一個水桶取水。設水桶個數為水桶個數為5個，試用信號量和個，試用信號量和 PV 操作給操作給出老和尚和小和尚的活動。出老和尚和小和尚的活動。 解解n小和尚提水，老和尚取水，他們之間是一種合作關系，涉小和尚提水，老和尚取水，他們之間是一種合作關系，涉及進程的及進程的同步同步；設置兩個私用信號量：；設置兩個私用信號量：empty為為小和尚小和尚進進程的程的私用信號量私用信號量，表示水缸中，表示水缸中還可以裝多少桶水還可以裝多少桶水，初值為，初值為30；ful

29、l為為老和尚老和尚進程的進程的私用信號量私用信號量，表示，表示水缸中有多少桶水缸中有多少桶水水，初值為，初值為0。n對水缸的操作中，每次入水、取水僅為對水缸的操作中，每次入水、取水僅為1桶，不可同時進行。桶，不可同時進行。水缸是共享資源水缸是共享資源。這涉及到進程的。這涉及到進程的互斥互斥。設置。設置公用信號量公用信號量mutex_bigjar，用于實現對水缸的互斥操作，初值為，用于實現對水缸的互斥操作，初值為1。n水取自同一井中，水井徑窄，每次只能容納一個水桶取水。水取自同一井中，水井徑窄，每次只能容納一個水桶取水。井也是共享的資源井也是共享的資源，涉及到進程的，涉及到進程的互斥互斥。設置公

30、用信號量。設置公用信號量mutex_well，用于實現對井的互斥操作，初值為，用于實現對井的互斥操作，初值為1。n所有的和尚都要用桶來提水或取水，所有的和尚都要用桶來提水或取水，水桶是共享資源水桶是共享資源，涉，涉及進程的及進程的互斥互斥。設置。設置公用信號量公用信號量bucket，表示，表示空桶的個數空桶的個數，初值為初值為5。解解semaphore empty=30; / 表示缸中目前還能裝表示缸中目前還能裝多少桶水，初始時還能裝多少桶水，初始時還能裝 30 桶水桶水 semaphore full=0; / 表示缸中有多少桶水，初始表示缸中有多少桶水，初始時缸中沒有水時缸中沒有水 sema

31、phore buckets=5; / 表示有多少只空桶可表示有多少只空桶可用，初始時有用，初始時有 5 只桶可用只桶可用 semaphore mutex_well=1; / 用于實現對井的用于實現對井的互斥操作互斥操作 semaphore mutex_bigjar=1; / 用于實現對缸的用于實現對缸的互斥操作互斥操作 解解young_monk(): while(ture) P(empty); P(buckets);get a bucket ； go to the well; P(mutex_well); get water; V(mutex_well); go to the temple;

32、P(mutex_bigjar); pure the water into the bigjar; V(mutex_bigjar); V(buckets); V(full); old_monk() : while(ture) P(full); P(buckets); get a bucket; P(mutex_bigjar); get water; V(mutex_bigjar); V(buckets); V(empty); 例例 子子n有一個閱覽室，共有有一個閱覽室，共有100個座位，讀者進個座位，讀者進入時必須先在一張登記表上登記，該表為入時必須先在一張登記表上登記，該表為每一座位列一表目，

33、包括座號和讀者姓名每一座位列一表目，包括座號和讀者姓名等，讀者離開時要消掉登記的信息，試問：等，讀者離開時要消掉登記的信息，試問：n為描述讀者的動作，應編寫幾個程序，設置幾為描述讀者的動作，應編寫幾個程序，設置幾個進程？個進程？1.試用試用PV操作描述讀者進程之間的關系。操作描述讀者進程之間的關系。 解解n讀者的動作有兩個：一是讀者的動作有兩個：一是填表填表進入閱覽室進入閱覽室，這時要，這時要考慮閱覽室里是否有座位；一是讀者閱讀完畢，考慮閱覽室里是否有座位；一是讀者閱讀完畢，離離開閱覽室開閱覽室清除表清除表，這時的操作要考慮閱覽室里是否，這時的操作要考慮閱覽室里是否有讀者。讀者在閱覽室讀書時，

34、由于沒有引起資源有讀者。讀者在閱覽室讀書時，由于沒有引起資源的變動，不算動作變化。的變動，不算動作變化。 n算法的信號量有三個：算法的信號量有三個：seats表示閱覽室是否表示閱覽室是否有座位（初值為有座位（初值為100，代表閱覽室的空座位數）；，代表閱覽室的空座位數）；readers表示閱覽室里的讀者數，初值為表示閱覽室里的讀者數，初值為0；設置公用信號量設置公用信號量mutex ，表示被共享的，表示被共享的登記表登記表這這一一臨界資源臨界資源，初值為，初值為1，用來防止兩個以上讀者進，用來防止兩個以上讀者進程同時查表。程同時查表。 解解讀者進入閱覽室的動作描述讀者進入閱覽室的動作描述get

35、in：while(TRUE) P (seats); /*沒有座位則離開沒有座位則離開*/ P（mutex）; /*進入臨界區(qū)（查表）進入臨界區(qū)（查表）*/ 填寫登記表填寫登記表; 進入閱覽室讀書進入閱覽室讀書; V（mutex）; /*離開臨界區(qū)離開臨界區(qū)*/ V（readers）; 解解讀者離開閱覽室的動作描述讀者離開閱覽室的動作描述getout：while(TRUE) P（readers） /*閱覽室是否有人讀書閱覽室是否有人讀書*/ P（mutex） /*進入臨界區(qū)進入臨界區(qū)*/ 消掉登記；消掉登記； 離開閱覽室；離開閱覽室； V（mutex） /*離開臨界區(qū)離開臨界區(qū)*/ V（seat

36、s） /*釋放一個座位資源釋放一個座位資源*/例例 子子n桌子上有一只盤子，桌子上有一只盤子，最多可容納兩個水果最多可容納兩個水果，每次只能放入或取出一個水果每次只能放入或取出一個水果，爸爸專向盤，爸爸專向盤子中放蘋果（子中放蘋果（apple），媽媽專向盤子中放），媽媽專向盤子中放橘子（橘子（orange），兩個兒子專等吃盤子中），兩個兒子專等吃盤子中的橘子，兩個女兒專等吃盤子中的蘋果，請的橘子，兩個女兒專等吃盤子中的蘋果，請用用P.V操作來實現爸爸、媽媽、兒子、女兒操作來實現爸爸、媽媽、兒子、女兒間的同步與互斥關系。間的同步與互斥關系。 解解n該題是生產者該題是生產者/消費者的變形，有兩對生

37、產消費者的變形，有兩對生產者和消費者，生產者需指明是給哪個消費者者和消費者，生產者需指明是給哪個消費者的產品，但消費者取走產品后無須特別通知的產品，但消費者取走產品后無須特別通知某個生產者，因為空出的緩沖區(qū)可由兩個生某個生產者，因為空出的緩沖區(qū)可由兩個生產者隨意爭奪。產者隨意爭奪。解解n盤子為互斥資源，可以放兩個水果，因此設生產者（爸爸、盤子為互斥資源，可以放兩個水果，因此設生產者（爸爸、媽媽）私用信號量媽媽）私用信號量empty，初值為，初值為2；設公用信號量；設公用信號量mutex，初值為初值為1，控制對盤子的互斥訪問；設置女兒進程的私用信號，控制對盤子的互斥訪問；設置女兒進程的私用信號量

38、量apple，表示盤子中的蘋果數，兒子進程的私用信號量，表示盤子中的蘋果數，兒子進程的私用信號量orange，表示盤中橘子個數，初值均為，表示盤中橘子個數，初值均為0。n爸爸放蘋果前先看看有無空間，若有，則放入蘋果，向女兒爸爸放蘋果前先看看有無空間，若有，則放入蘋果，向女兒發(fā)信號發(fā)信號V（apple）；媽媽放橘子前先看看盤子有無空間，若）；媽媽放橘子前先看看盤子有無空間，若有，放入橘子后向兒子發(fā)信號有，放入橘子后向兒子發(fā)信號V（orange）。）。n女兒先看看有無蘋果，若有，則取走蘋果后將盤子置空女兒先看看有無蘋果，若有，則取走蘋果后將盤子置空V（empty）；兒子先看看有沒有橘子，若有，則取走橘子后）；兒子先看看有沒有橘子，若有，則取走橘子后將盤子置空。將盤子置空。解解 爸爸、媽媽、兒子、女兒進程如下：爸爸、媽媽、兒子、女兒進程如下： 爸爸爸爸 媽媽媽媽 女兒女兒 兒子兒子L1：P（empty） L2：P（empty） L3：P（apple） L4：P（orange） P（mutex） P（mutex） P（mutex） P（mutex） 放蘋果放蘋果 放橘子放橘子 取蘋果取蘋果 取橘子取橘子 V（mutex） V（mut