1、PV操作的例題    一、線程是進(jìn)程的一個(gè)組成部分，一個(gè)進(jìn)程可以有多個(gè)線程，而且至少有一個(gè)可執(zhí)行線程。進(jìn)程的多個(gè)線程都在進(jìn)程的地址空間內(nèi)活動(dòng)。資源是分給進(jìn)程的，而不是分給線程的，線程需要資源時(shí)，系統(tǒng)從進(jìn)程的資源配額中扣除并分配給它。處理機(jī)調(diào)度的基本單位是線程，線程之間競(jìng)爭(zhēng)處理機(jī)，真正在處理機(jī)上運(yùn)行的是線程。線程在執(zhí)行過(guò)程中，需要同步。    二、在計(jì)算機(jī)操作系統(tǒng)中，PV操作是進(jìn)程管理中的難點(diǎn)。首先應(yīng)弄清PV操作的含義：PV操作由P操作原語(yǔ)和V操作原語(yǔ)組成（原語(yǔ)是不可中斷的過(guò)程），對(duì)信號(hào)量進(jìn)行操作，具體定義如下：  

2、  P（S）：將信號(hào)量S的值減1，即S=S-1；           如果S>=0，則該進(jìn)程繼續(xù)執(zhí)行；否則該進(jìn)程置為等待狀態(tài)，排入等待隊(duì)列。    V（S）：將信號(hào)量S的值加1，即S=S+1；           如果S>0，則該進(jìn)程繼續(xù)執(zhí)行；否則釋放隊(duì)列中第一個(gè)等待信號(hào)量的進(jìn)程。PV操作的意義：我們用信號(hào)量及PV操作來(lái)實(shí)現(xiàn)進(jìn)程的同步和互斥。PV

3、操作屬于進(jìn)程的低級(jí)通信。什么是信號(hào)量？信號(hào)量（semaphore）的數(shù)據(jù)結(jié)構(gòu)為一個(gè)值和一個(gè)指針，指針指向等待該信號(hào)量的下一個(gè)進(jìn)程。信號(hào)量的值與相應(yīng)資源的使用情況有關(guān)。當(dāng)它的值大于0時(shí)，表示當(dāng)前可用資源的數(shù)量；當(dāng)它的值小于0時(shí)，其絕對(duì)值表示等待使用該資源的進(jìn)程個(gè)數(shù)。注意，信號(hào)量的值僅能由PV操作來(lái)改變。     一般來(lái)說(shuō)，信號(hào)量S>=0時(shí)，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請(qǐng)求分配一個(gè)單位資源，因此S的值減1；當(dāng)S<0時(shí)，表示已經(jīng)沒(méi)有可用資源，請(qǐng)求者必須等待別的進(jìn)程釋放該類資源，它才能運(yùn)行下去。而執(zhí)行一個(gè)V操作意味著釋放一個(gè)單位資源，因

4、此S的值加1；若S?0，表示有某些進(jìn)程正在等待該資源，因此要喚醒一個(gè)等待狀態(tài)的進(jìn)程，使之運(yùn)行下去。    利用信號(hào)量和PV操作實(shí)現(xiàn)進(jìn)程互斥的一般模型是：進(jìn)程P1              進(jìn)程P2                     進(jìn)程Pn&#

5、160;                                            P（S）；      &

6、#160;       P（S）；                         P（S）；臨界區(qū)；             臨界區(qū)；   

7、0;                    臨界區(qū)；V（S）；              V（S）；               

8、         V（S）；                                           

9、60; 其中信號(hào)量S用于互斥，初值為1。    使用PV操作實(shí)現(xiàn)進(jìn)程互斥時(shí)應(yīng)該注意的是：    （1）每個(gè)程序中用戶實(shí)現(xiàn)互斥的P、V操作必須成對(duì)出現(xiàn)，先做P操作，進(jìn)臨界區(qū)，后做V操作，出臨界區(qū)。若有多個(gè)分支，要認(rèn)真檢查其成對(duì)性。    （2）P、V操作應(yīng)分別緊靠臨界區(qū)的頭尾部，臨界區(qū)的代碼應(yīng)盡可能短，不能有死循環(huán)。   （3）互斥信號(hào)量的初值一般為1。    利用信號(hào)量和PV操作實(shí)現(xiàn)進(jìn)程同步PV操作是典型的同步機(jī)制之一。用一個(gè)信號(hào)量與一個(gè)消息聯(lián)系起來(lái)，當(dāng)信

10、號(hào)量的值為0時(shí)，表示期望的消息尚未產(chǎn)生；當(dāng)信號(hào)量的值非0時(shí)，表示期望的消息已經(jīng)存在。用PV操作實(shí)現(xiàn)進(jìn)程同步時(shí)，調(diào)用P操作測(cè)試消息是否到達(dá)，調(diào)用V操作發(fā)送消息。    使用PV操作實(shí)現(xiàn)進(jìn)程同步時(shí)應(yīng)該注意的是：    （1）分析進(jìn)程間的制約關(guān)系，確定信號(hào)量種類。在保持進(jìn)程間有正確的同步關(guān)系情況下，哪個(gè)進(jìn)程先執(zhí)行，哪些進(jìn)程后執(zhí)行，彼此間通過(guò)什么資源（信號(hào)量）進(jìn)行協(xié)調(diào)，從而明確要設(shè)置哪些信號(hào)量。    （2）信號(hào)量的初值與相應(yīng)資源的數(shù)量有關(guān)，也與P、V操作在程序代碼中出現(xiàn)的位置有關(guān)。  

11、60; （3）同一信號(hào)量的P、V操作要成對(duì)出現(xiàn)，但它們分別在不同的進(jìn)程代碼中。 例題一：過(guò)橋問(wèn)題   解：設(shè)信號(hào)量初值S=1           汽車進(jìn)程Pi(i=1,2,3,)           到達(dá)橋頭           P(s)  

12、;         橋行駛           到達(dá)橋另一端           V(s)例題二若有一售票廳只能容納300人，當(dāng)少于300人時(shí)，可以進(jìn)入。否則，需在外等候，若將每一個(gè)購(gòu)票者作為一個(gè)進(jìn)程，請(qǐng)用P、V操作編程。        解

13、：信號(hào)量初值S=300                購(gòu)票者進(jìn)程Pi(i=1,2,3,)                P(s)              &#

14、160; 進(jìn)入售票廳                購(gòu)票                退出售票廳                V(s) 

15、                           例題三有一只鐵籠子，每次只能放入一只動(dòng)物，獵手向籠中放入老虎，農(nóng)民向籠中放入豬，動(dòng)物園等待取籠中的老虎，飯店等待取籠中的豬，試用P、V操作寫出能同步執(zhí)行的程序。解：兩個(gè)生產(chǎn)者和兩個(gè)消費(fèi)者共享了一個(gè)僅能存放一件產(chǎn)品的緩沖器，生產(chǎn)者各自生產(chǎn)不同的產(chǎn)品，消費(fèi)者各自取自己需要的產(chǎn)品，

16、P、V操作編程為：獵手進(jìn)程    農(nóng)民進(jìn)程    動(dòng)物園進(jìn)程      飯店進(jìn)程   P(s)        P(s)        P(s1)          P(s2)   放入虎   

17、;  放入豬       買老虎         買豬   V(s1)       V(s2)       V(s)           V(s)其中S初值=1，S1=S2=0 例題四桌上有一只盤子，

18、每次只能放入一個(gè)水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，女兒專等吃盤中的蘋果，兒子專等吃盤中的桔子。用P、V操作寫出它們能正確同步的程序。（同例六詳解）解：信號(hào)量初值S1=0，S2=0，S=1 爸爸進(jìn)程   媽媽進(jìn)程   女兒進(jìn)程  兒子進(jìn)程  repeat         repeat          repeat   

19、;       repeat     P(s)          P(s)          P(s1)           P(s2)     放蘋果  &#

20、160;   放桔子        取蘋果           取桔子     V(s1)         V(s2)        V(s)      

21、60;      V(s)  until false    until false  until false  until false例題五 設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2如下，S1和S2初值均為0，求：P1，P2并發(fā)執(zhí)行結(jié)束后，x,y,z分別是多少？           進(jìn)程P1        

22、;          進(jìn)程P2           y:=1;                      x:=1;       

23、    y:=y+2;                  x:=x+1;           V(s1);                &

24、#160;   P(s1);           z:=y+1;                  x:=x+y;           P(s2);     &

25、#160;               V(s2)           y:=z+y;                  z:=x+z;解：因?yàn)镻1、P2是并發(fā)進(jìn)程，所以P1和P2調(diào)度順序不

26、確定。假設(shè)P1先執(zhí)行，當(dāng)P1執(zhí)行到P(s2)時(shí)，s2=-1，P1阻塞，此時(shí)y=3,z=4;當(dāng)調(diào)度程序調(diào)度到P2時(shí)，由于進(jìn)程P1巳執(zhí)行到了V(s1),P2在執(zhí)行P(s1)時(shí)，不阻塞而繼續(xù)執(zhí)行，當(dāng)執(zhí)行到V(s2)時(shí)，將P1喚醒，然后執(zhí)行到最后一個(gè)語(yǔ)句，此時(shí)x=5,z=9;當(dāng)P1再次被喚醒、調(diào)度時(shí)，繼續(xù)執(zhí)行P1的最后一處語(yǔ)句，此時(shí)y=12.所以最后結(jié)果是：x=5,y=12,z=9.如果P2先執(zhí)行，結(jié)果同上 【例題五】生產(chǎn)者-消費(fèi)者問(wèn)題在多道程序環(huán)境下，進(jìn)程同步是一個(gè)十分重要又令人感興趣的問(wèn)題，而生產(chǎn)者-消費(fèi)者問(wèn)題是其中一個(gè)有代表性的進(jìn)程同步問(wèn)題。下面我們給出了各種情況下的生產(chǎn)者-消費(fèi)者問(wèn)題

27、，深入地分析和透徹地理解這個(gè)例子，對(duì)于全面解決操作系統(tǒng)內(nèi)的同步、互斥問(wèn)題將有很大幫助。（1）一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，公用一個(gè)緩沖區(qū)。定義兩個(gè)同步信號(hào)量：empty表示緩沖區(qū)是否為空，初值為1。   full表示緩沖區(qū)中是否為滿，初值為0。生產(chǎn)者進(jìn)程while(TRUE)生產(chǎn)一個(gè)產(chǎn)品;     P(empty);     產(chǎn)品送往Buffer;     V(full);消費(fèi)者進(jìn)程while(True)P(full);   從Buffer取

28、出一個(gè)產(chǎn)品;   V(empty);   消費(fèi)該產(chǎn)品;   （2）一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，公用n個(gè)環(huán)形緩沖區(qū)。定義兩個(gè)同步信號(hào)量：empty表示緩沖區(qū)是否為空，初值為n。full表示緩沖區(qū)中是否為滿，初值為0。    設(shè)緩沖區(qū)的編號(hào)為1n-1，定義兩個(gè)指針in和out，分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指，指向下一個(gè)可用的緩沖區(qū)。生產(chǎn)者進(jìn)程while(TRUE)     生產(chǎn)一個(gè)產(chǎn)品;     P(empty); &

29、#160;   產(chǎn)品送往buffer（in）；     in=(in+1)mod n；     V(full);消費(fèi)者進(jìn)程while(TRUE) P(full);   從buffer（out）中取出產(chǎn)品；   out=(out+1)mod n；   V(empty);   消費(fèi)該產(chǎn)品;   （3）一組生產(chǎn)者，一組消費(fèi)者，公用n個(gè)環(huán)形緩沖區(qū)    在這個(gè)問(wèn)題中

30、，不僅生產(chǎn)者與消費(fèi)者之間要同步，而且各個(gè)生產(chǎn)者之間、各個(gè)消費(fèi)者之間還必須互斥地訪問(wèn)緩沖區(qū)。定義四個(gè)信號(hào)量：empty表示緩沖區(qū)是否為空，初值為n。full表示緩沖區(qū)中是否為滿，初值為0。mutex1生產(chǎn)者之間的互斥信號(hào)量，初值為1。mutex2消費(fèi)者之間的互斥信號(hào)量，初值為1。    設(shè)緩沖區(qū)的編號(hào)為1n-1，定義兩個(gè)指針in和out，分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指針，指向下一個(gè)可用的緩沖區(qū)。生產(chǎn)者進(jìn)程while(TRUE)     生產(chǎn)一個(gè)產(chǎn)品;     P(empty);&#

31、160;    P(mutex1)；     產(chǎn)品送往buffer（in）；     in=(in+1)mod n；     V(mutex1);     V(full);消費(fèi)者進(jìn)程while(TRUE) P(full)   P(mutex2)；   從buffer（out）中取出產(chǎn)品；   out=(out+1)mod n； 

32、  V（mutex2）；   V(empty);   消費(fèi)該產(chǎn)品;     需要注意的是無(wú)論在生產(chǎn)者進(jìn)程中還是在消費(fèi)者進(jìn)程中，兩個(gè)P操作的次序不能顛倒。應(yīng)先執(zhí)行同步信號(hào)量的P操作，然后再執(zhí)行互斥信號(hào)量的P操作，否則可能造成進(jìn)程死鎖?！纠}六】桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用P、V原語(yǔ)實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。分析在本題中，爸爸、兒子、女兒共用一個(gè)盤子，盤中一次只能放一個(gè)水果。

33、當(dāng)盤子為空時(shí)，爸爸可將一個(gè)水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實(shí)際上是生產(chǎn)者-消費(fèi)者問(wèn)題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費(fèi)者也有兩類，每類消費(fèi)者只消費(fèi)其中固定的一類產(chǎn)品。    解：在本題中，應(yīng)設(shè)置三個(gè)信號(hào)量S、So、Sa，信號(hào)量S表示盤子是否為空，其初值為l；信號(hào)量So表示盤中是否有桔子，其初值為0；信號(hào)量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：int S1;int Sa0;int So0;     

34、main()              cobegin            father();                 son();     

35、0;             daughter();           coend        father()            while(1)     &#

36、160;                P(S);            將水果放入盤中;            if（放入的是桔子）V(So);        

37、;    else  V(Sa);                    son()            while(1)              

38、0;        P(So);             從盤中取出桔子;             V(S);             吃桔子;  &

39、#160;                 daughter()             while(1)                     &

40、#160;    P(Sa);              從盤中取出蘋果;              V(S);              吃蘋果;  

41、0;          思考題：四個(gè)進(jìn)程A、B、C、D都要讀一個(gè)共享文件F，系統(tǒng)允許多個(gè)進(jìn)程同時(shí)讀文件F。但限制是進(jìn)程A和進(jìn)程C不能同時(shí)讀文件F，進(jìn)程B和進(jìn)程D也不能同時(shí)讀文件F。為了使這四個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)能按系統(tǒng)要求使用文件，現(xiàn)用PV操作進(jìn)行管理，請(qǐng)回答下面的問(wèn)題：    （1）應(yīng)定義的信號(hào)量及初值：              

42、0;     。    （2）在下列的程序中填上適當(dāng)?shù)腜、V操作，以保證它們能正確并發(fā)工作：     A()                B()                &

43、#160; C()                 D()                                 

44、60;                                 1;                3;   &

45、#160;              5;                 7;      read F;             read

46、 F;                read F;              read F;     2;              &#

47、160; 4;                  6;                 8;               

48、0;                                               思考題解答：（1）定義二個(gè)信號(hào)量S1、S2，初值均為1，即：S

49、1=1，S2=1。其中進(jìn)程A和C使用信號(hào)量S1，進(jìn)程B和D使用信號(hào)量S2。（2）從1到8分別為：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)習(xí)題1:有三個(gè)并發(fā)進(jìn)程使用同一個(gè)緩沖區(qū),進(jìn)程P1負(fù)責(zé)讀數(shù)據(jù)到緩沖區(qū),P2負(fù)責(zé)加工緩沖區(qū)中的數(shù)據(jù),進(jìn)程P3負(fù)責(zé)將緩沖區(qū)中加工后的數(shù)據(jù)輸出.在進(jìn)程P3沒(méi)有輸完之前,進(jìn)程P1不能讀入新的數(shù)據(jù)到緩沖區(qū)中.請(qǐng)用P、V操作編程.解：信號(hào)量初值：S1=0，S2=0，S3=0           進(jìn)程P1 

50、0;       進(jìn)程P2        進(jìn)程P3           讀數(shù)據(jù)到        P(S1)           P(S2)     &

51、#160;      緩沖區(qū)            加工           輸出            V(S1)             V(S2)           V(S3)            P(S3) 習(xí)題2：設(shè)有六個(gè)進(jìn)程P1、P2、P3、P4、P5、P6，它們并發(fā)執(zhí)行。由P1開(kāi)始執(zhí)行