第三章進(jìn)程管理(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、表示可否取桔子，一個(gè)信號量表示可否取蘋果。蘋果。解解n設(shè)置三個(gè)信號量設(shè)置三個(gè)信號量S、So、Sa，信號量，信號量S表示表示盤子是否為空，其初值為盤子是否為空，其初值為1；信號量；信號量So表示表示盤中是否有桔子，其初值為盤中是否有桔子，其初值為0；信號量；信號量Sa表表示盤中是否有蘋果，其初值為示盤中是否有蘋果，其初值為0。同步描述。同步描述如下：如下：解解int S1;int Sa0;int So0; main() begin father(); /*父親進(jìn)程父親進(jìn)程*/ son(); /*兒子進(jìn)程兒子進(jìn)程*/ daughter(); /*女兒進(jìn)程女兒進(jìn)程*/ 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 生產(chǎn)者/消費(fèi)者問題n生產(chǎn)者消費(fèi)者問題是一種同步問題的抽生產(chǎn)者消費(fèi)者問題是一種同步問題的抽象描述。計(jì)算機(jī)系統(tǒng)中的每個(gè)進(jìn)程都可象描述。計(jì)算機(jī)系統(tǒng)中的每個(gè)進(jìn)程都可以消費(fèi)（使用）或生產(chǎn)（釋放）某類資以消費(fèi)（使用）或生產(chǎn)（釋放）某類資源。這些資源可

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

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

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

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

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

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

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

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

27、，初值這個(gè)臨界資源的互斥訪問，初值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某寺廟，有小和尚、老和尚若干廟內(nèi)有一某寺廟，有小和尚、老和尚若干廟內(nèi)有一水缸，由小和尚提水入缸，供老和尚飲水缸，由小和尚提水入缸，供老和尚飲用水缸可容納用水缸可容納 30 桶水，每次入水、取水桶水，每次入水

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

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

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

31、phore buckets=5; / 表示有多少只空桶可表示有多少只空桶可用，初始時(shí)有用，初始時(shí)有 5 只桶可用只桶可用 semaphore mutex_well=1; / 用于實(shí)現(xiàn)對井的用于實(shí)現(xiàn)對井的互斥操作互斥操作 semaphore mutex_bigjar=1; / 用于實(shí)現(xiàn)對缸的用于實(shí)現(xiàn)對缸的互斥操作互斥操作 解解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有一個(gè)閱覽室，共有有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為入時(shí)必須先在一張登記表上登記，該表為每一座位列一表目，

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

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

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

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

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

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