進程通常分為就緒、運行和阻塞三個工作狀態(tài)。三種狀態(tài)在某些條件下可以轉(zhuǎn)換，三者之間的轉(zhuǎn)換關(guān)系如下：

進程三個狀態(tài)之間的轉(zhuǎn)換就是靠PV操作來控制的。PV操作主要就是P操作、V操作和信號量。其中信號量起到了至關(guān)重要的作用。

信號量

信號量是最早出現(xiàn)的用來解決進程同步與互斥問題的機制。　

信號量（Saphore）由一個值和一個指針組成，指針指向等待該信號量的進程。信號量的值表示相應(yīng)資源的使用情況。信號量S>=0時，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請求分配一個資源，因此S的值減1；當S<0時，表示已經(jīng)沒有可用資源，S的絕對值表示當前等待該資源的進程數(shù)。請求者必須等待其他進程釋放該類資源，才能繼續(xù)運行。而執(zhí)行一個V操作意味著釋放一個資源，因此S的值加1；若S<0，表示有某些進程正在等待該資源，因此要喚醒一個等待狀態(tài)的進程，使之運行下去。

注意，信號量的值只能由PV操作來改變。

什么是信號量？信號量（semaphore）的數(shù)據(jù)結(jié)構(gòu)為一個值和一個指針，指針指向等待該信號量的下一個進程。信號量的值與相應(yīng)資源的使用情況有關(guān)。當它的值大于0時，表示當前可用資源的數(shù)量；當它的值小于0時，其絕對值表示等待使用該資源的進程個數(shù)。注意，信號量的值僅能由PV操作來改變。     一般來說，信號量S30時，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請求分配一個單位資源，因此S的值減1；當S<0時，表示已經(jīng)沒有可用資源，請求者必須等待別的進程釋放該類資源，它才能運行下去。而執(zhí)行一個V操作意味著釋放一個單位資源，因此S的值加1；若S￡0，表示有某些進程正在等待該資源，因此要喚醒一個等待狀態(tài)的進程，使之運行下去。

    利用信號量和PV操作實現(xiàn)進程互斥的一般模型是：進程P1              進程P2           ……          進程Pn……                  ……                           ……P（S）；              P（S）；                         P（S）；臨界區(qū)；             臨界區(qū)；                        臨界區(qū)；V（S）；              V（S）；                        V（S）；……                  ……            ……           ……

    其中信號量S用于互斥，初值為1。    使用PV操作實現(xiàn)進程互斥時應(yīng)該注意的是：    （1）每個程序中用戶實現(xiàn)互斥的P、V操作必須成對出現(xiàn)，先做P操作，進臨界區(qū)，后做V操作，出臨界區(qū)。若有多個分支，要認真檢查其成對性。    （2）P、V操作應(yīng)分別緊靠臨界區(qū)的頭尾部，臨界區(qū)的代碼應(yīng)盡可能短，不能有死循環(huán)。   （3）互斥信號量的初值一般為1。

    利用信號量和PV操作實現(xiàn)進程同步PV操作是典型的同步機制之一。用一個信號量與一個消息聯(lián)系起來，當信號量的值為0時，表示期望的消息尚未產(chǎn)生；當信號量的值非0時，表示期望的消息已經(jīng)存在。用PV操作實現(xiàn)進程同步時，調(diào)用P操作測試消息是否到達，調(diào)用V操作發(fā)送消息。    使用PV操作實現(xiàn)進程同步時應(yīng)該注意的是：

    （1）分析進程間的制約關(guān)系，確定信號量種類。在保持進程間有正確的同步關(guān)系情況下，哪個進程先執(zhí)行，哪些進程后執(zhí)行，彼此間通過什么資源（信號量）進行協(xié)調(diào)，從而明確要設(shè)置哪些信號量。    （2）信號量的初值與相應(yīng)資源的數(shù)量有關(guān)，也與P、V操作在程序代碼中出現(xiàn)的位置有關(guān)。    （3）同一信號量的P、V操作要成對出現(xiàn)，但它們分別在不同的進程代碼中。

【例1】生產(chǎn)者-消費者問題在多道程序環(huán)境下，進程同步是一個十分重要又令人感興趣的問題，而生產(chǎn)者-消費者問題是其中一個有代表性的進程同步問題。下面我們給出了各種情況下的生產(chǎn)者-消費者問題，深入地分析和透徹地理解這個例子，對于全面解決操作系統(tǒng)內(nèi)的同步、互斥問題將有很大幫助。

（1）一個生產(chǎn)者，一個消費者，公用一個緩沖區(qū)。定義兩個同步信號量：empty——表示緩沖區(qū)是否為空，初值為1。   full——表示緩沖區(qū)中是否為滿，初值為0。生產(chǎn)者進程while(TRUE){生產(chǎn)一個產(chǎn)品;     P(empty);     產(chǎn)品送往Buffer;     V(full);}消費者進程while(True){P(full);   從Buffer取出一個產(chǎn)品;   V(empty);   消費該產(chǎn)品;   }（2）一個生產(chǎn)者，一個消費者，公用n個環(huán)形緩沖區(qū)。定義兩個同步信號量：empty——表示緩沖區(qū)是否為空，初值為n。full——表示緩沖區(qū)中是否為滿，初值為0。

    設(shè)緩沖區(qū)的編號為1～n-1，定義兩個指針in和out，分別是生產(chǎn)者進程和消費者進程使用的指，指向下一個可用的緩沖區(qū)。生產(chǎn)者進程while(TRUE){     生產(chǎn)一個產(chǎn)品;     P(empty);     產(chǎn)品送往buffer（in）；     in=(in+1)mod n；     V(full);}消費者進程while(TRUE){ P(full);   從buffer（out）中取出產(chǎn)品；   out=(out+1)mod n；   V(empty);   消費該產(chǎn)品;   }（3）一組生產(chǎn)者，一組消費者，公用n個環(huán)形緩沖區(qū)    在這個問題中，不僅生產(chǎn)者與消費者之間要同步，而且各個生產(chǎn)者之間、各個消費者之間還必須互斥地訪問緩沖區(qū)。定義四個信號量：empty——表示緩沖區(qū)是否為空，初值為n。full——表示緩沖區(qū)中是否為滿，初值為0。mutex1——生產(chǎn)者之間的互斥信號量，初值為1。mutex2——消費者之間的互斥信號量，初值為1。

    設(shè)緩沖區(qū)的編號為1～n-1，定義兩個指針in和out，分別是生產(chǎn)者進程和消費者進程使用的指針，指向下一個可用的緩沖區(qū)。生產(chǎn)者進程while(TRUE){     生產(chǎn)一個產(chǎn)品;     P(empty);     P(mutex1)；     產(chǎn)品送往buffer（in）；     in=(in+1)mod n；     V(mutex1);     V(full);}消費者進程while(TRUE){ P(full)   P(mutex2)；   從buffer（out）中取出產(chǎn)品；   out=(out+1)mod n；   V（mutex2）；   V(empty);   消費該產(chǎn)品;   }  需要注意的是無論在生產(chǎn)者進程中還是在消費者進程中，兩個P操作的次序不能顛倒。應(yīng)先執(zhí)行同步信號量的P操作，然后再執(zhí)行互斥信號量的P操作，否則可能造成進程死鎖。

【例2】桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。

分析 在本題中，爸爸、兒子、女兒共用一個盤子，盤中一次只能放一個水果。當盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實際上是生產(chǎn)者-消費者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費者也有兩類，每類消費者只消費其中固定的一類產(chǎn)品。

    解：在本題中，應(yīng)設(shè)置三個信號量S、So、Sa，信號量S表示盤子是否為空，其初值為l；信號量So表示盤中是否有桔子，其初值為0；信號量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：int S＝1;int Sa＝0;int So＝0;      main()      {        cobegin            father();      /*父親進程*/            son();        /*兒子進程*/            daughter();    /*女兒進程*/        coend    ｝    father()    {        while(1)          {            P(S);            將水果放入盤中;            if（放入的是桔子）V(So);            else  V(Sa);           }     }    son()    {        while(1)          {             P(So);             從盤中取出桔子;             V(S);             吃桔子;            ｝    }    daughter()    {         while(1)            {              P(Sa);              從盤中取出蘋果;              V(S);              吃蘋果;            ｝｝ 思考題：

四個進程A、B、C、D都要讀一個共享文件F，系統(tǒng)允許多個進程同時讀文件F。但限制是進程A和進程C不能同時讀文件F，進程B和進程D也不能同時讀文件F。為了使這四個進程并發(fā)執(zhí)行時能按系統(tǒng)要求使用文件，現(xiàn)用PV操作進行管理，請回答下面的問題：    （1）應(yīng)定義的信號量及初值：                    。    （2）在下列的程序中填上適當?shù)腜、V操作，以保證它們能正確并發(fā)工作：     A()                B()                  C()                 D()      {                 {                    {                  {      [1];                [3];                  [5];                 [7];      read F;             read F;                read F;              read F;     [2];                [4];                  [6];                 [8];      }                  }                    }                  } 

    思考題解答：（1）定義二個信號量S1、S2，初值均為1，即：S1=1，S2=1。其中進程A和C使用信號量S1，進程B和D使用信號量S2。（2）從[1]到[8]分別為：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

具體PV原語對信號量的操作可以分為三種情況：

1）              把信號量視為一個加鎖標志位，實現(xiàn)對一個共享變量的互斥訪問。

實現(xiàn)過程：

P(mutex);           // mutex的初始值為1

訪問該共享數(shù)據(jù);

V(mutex);

非臨界區(qū)

2）              把信號量視為是某種類型的共享資源的剩余個數(shù)，實現(xiàn)對一類共享資源的訪問。

實現(xiàn)過程：

P(resource);          // resource的初始值為該資源的個數(shù)N

使用該資源；

V(resource);

非臨界區(qū)

3）              把信號量作為進程間的同步工具

實現(xiàn)過程：

臨界區(qū)C1；    P(S);

V(S);           臨界區(qū)C2；

下面用幾個例子來具體說明：

例1：某超市門口為顧客準備了100輛手推車，每位顧客在進去買東西時取一輛推車，在買完東西結(jié)完帳以后再把推車還回去。試用P、V操作正確實現(xiàn)顧客進程的同步互斥關(guān)系。

分析：把手推車視為某種資源，每個顧客為一個要互斥訪問該資源的進程。因此這個例子為PV原語的第二種應(yīng)用類型。

解：semaphore  S_CartNum;   // 空閑的手推車數(shù)量， 初值為100

void  consumer(void)           // 顧客進程{        P(S_CartNum);

        買東西；

        結(jié)帳；

        V(S_CartNum); }

例2：桌子上有一個水果盤，每一次可以往里面放入一個水果。爸爸專向盤子中放蘋果，兒子專等吃盤子中的蘋果。把爸爸、兒子看作二個進程，試用P、V操作使這四個進程能正確地并發(fā)執(zhí)行。

分析：爸爸和兒子兩個進程相互制約，爸爸進程執(zhí)行完即往盤中放入蘋果后，兒子進程才能執(zhí)行即吃蘋果。因此該問題為進程間的同步問題。

解：semaphore  S_PlateNum;  // 盤子容量，初值為1

semaphore  S_AppleNum;   // 蘋果數(shù)量，初值為0

void  father( )                // 父親進程{

    while(1)

    {        P(S_PlateNum);

        往盤子中放入一個蘋果；

        V(S_AppleNum);

    } }

void  son( )   // 兒子進程{

    while(1)

    {        P(S_AppleNum);

        從盤中取出蘋果；

        V(S_PlateNum);

        吃蘋果；

    } }

另附用PV原語解決進程同步與互斥問題的例子:

經(jīng)典ipC問題如：生產(chǎn)者－消費者，讀者－寫者，哲學家就餐，睡著的理發(fā)師等可參考相關(guān)教材。

一、兩個進程PA、PB通過兩個FIFO（先進先出）緩沖區(qū)隊列連接（如圖）

    PA從Q2取消息，處理后往Q1發(fā)消息，PB從Q1取消息，處理后往Q2發(fā)消息，每個緩沖區(qū)長度等于傳送消息長度. Q1隊列長度為n，Q2隊列長度為m. 假設(shè)開始時Q1中裝滿了消息，試用P、V操作解決上述進程間通訊問題。

解：// Q1隊列當中的空閑緩沖區(qū)個數(shù)，初值為0semaphore  S_BuffNum_Q1;  

// Q2隊列當中的空閑緩沖區(qū)個數(shù)，初值為m semaphore  S_BuffNum_Q2;    

// Q1隊列當中的消息數(shù)量，初值為n semaphore  S_MessageNum_Q1;

// Q2隊列當中的消息數(shù)量，初值為0 semaphore  S_MessageNum_Q2;

void  PA( ){

        while(1)

        {                P(S_MessageNum_Q2);

                從Q2當中取出一條消息；

                V(S_BuffNum_Q2);

                處理消息；

                生成新的消息；

                P(S_BuffNum_Q1);

                把該消息發(fā)送到Q1當中；

                V(S_MessageNum_Q1);

        } }

void  PB( ){

        while(1)

        {                P(S_MessageNum_Q1);

                從Q1當中取出一條消息；

                V(S_BuffNum_Q1);

                處理消息；

                生成新的消息；

                P(S_BuffNum_Q2);

                把該消息發(fā)送到Q2當中；

                V(S_MessageNum_Q2);

        } }

二、《操作系統(tǒng)》課程的期末考試即將舉行，假設(shè)把學生和監(jiān)考老師都看作進程，學生有N人，教師1人。考場門口每次只能進出一個人，進考場的原則是先來先進。當N個學生都進入了考場后，教師才能發(fā)卷子。學生交卷后即可離開考場，而教師要等收上來全部卷子并封裝卷子后才能離開考場。

(1)問共需設(shè)置幾個進程?

(2)請用P、V操作解決上述問題中的同步和互斥關(guān)系。

解：semaphore  S_Door;          // 能否進出門，初值1

semaphore  S_StudentReady;    // 學生是否到齊，初值為0

semaphore  S_ExamBegin;   // 開始考試，初值為0

semaphore  S_ExamOver;    // 考試結(jié)束，初值為0

int  nStudentNum = 0;          // 學生數(shù)目

semaphore  S_Mutex1         //互斥信號量，初值為1

int  nPaperNum = 0;       // 已交的卷子數(shù)目

semaphore  S_Mutex2         //互斥信號量，初值為1

void  student( ){

        P(S_Door);

        進門；        V(S_Door);

        P(S_Mutex1)；

        nStudentNum ++;         // 增加學生的個數(shù)

        if(nStudentNum == N)  V(S_StudentReady);

        V(S_Mutex1);

        P(S_ExamBegin);         // 等老師宣布考試開始

        考試中…

        交卷；

P(S_Mutex2)；

        nPaperNum ++;      // 增加試卷的份數(shù)

        if(nPaperNum == N)  V(S_ExamOver);

        V(S_Mutex2);

        P(S_Door);

        出門；

        V(S_Door);

}

void  teacher( ){

        P(S_Door);

        進門；        V(S_Door);

        P(S_StudentReady)；//等待最后一個學生來喚醒

        發(fā)卷子;

        for(i = 1; i <= N; i++)    V(S_ExamBegin);

        P(S_ExamOver);         // 等待考試結(jié)束

        封裝試卷；

        P(S_Door);

        出門；        V(S_Door);

}

三、某商店有兩種食品A和B，最大數(shù)量均為m個。 該商店將A、B兩種食品搭配出售，每次各取一個。為避免食品變質(zhì)，遵循先到食品先出售的原則。有兩個食品公司分別不斷地供應(yīng)A、B兩種食品(每次一個)。為保證正常銷售，當某種食品的數(shù)量比另一種的數(shù)量超過k(k個時，暫停對數(shù)量大的食品進貨，補充數(shù)量少的食品。

(1) 問共需設(shè)置幾個進程?

(2) 用P、V操作解決上述問題中的同步互斥關(guān)系。

解：semaphore  S_BuffNum_A;  //A的緩沖區(qū)個數(shù), 初值m

semaphore  S_Num_A;          // A的個數(shù)，初值為0

semaphore  S_BuffNum_B;  //B的緩沖區(qū)個數(shù), 初值m

semaphore  S_Num_B;          // B的個數(shù)，初值為0

void  Shop( ){

        while(1)

        {                P(S_Num_A);

                P(S_Num_B)；

                分別取出A、B食品各一個;

                V(S_BuffNum_A);

                V(S_BuffNum_A);

                搭配地銷售這一對食品;

        } }

// “A食品加1，而B食品不變”這種情形允許出現(xiàn)的次數(shù)(許可證的數(shù)量)，其值等于//k-(A-B)，初值為k

semaphore  S_A_B;

// “B食品加1，而A食品不變”這種情形允許出現(xiàn)的次數(shù)(許可證的數(shù)量)，其值等于//k-(B-A)，初值為k

semaphore  S_B_A;

void  PRoducer_A ( ){

        while(1)

        {                生產(chǎn)一個A食品；

                P(S_BuffNum_A)；

                P(S_A_B);

                向商店提供一個A食品；

                V(S_Num_A);

                V(S_B_A);

        } }

void  Producer_B ( ){

        while(1)

        {                生產(chǎn)一個B食品；

                P(S_BuffNum_B)；

                P(S_B_A);

                向商店提供一個B食品；

                V(S_Num_B);

                V(S_A_B);

        } }

四：在一棟學生公寓里，只有一間浴室，而且這間浴室非常小，每一次只能容納一個人。公寓里既住著男生也住著女生，他們不得不分享這間浴室。因此，樓長制定了以下的浴室使用規(guī)則：（1）每一次只能有一個人在使用；（2）女生的優(yōu)先級要高于男生，即如果同時有男生和女生在等待使用浴室，則女生優(yōu)先；（3）對于相同性別的人來說，采用先來先使用的原則。

假設(shè)：

（1）當一個男生想要使用浴室時，他會去執(zhí)行一個函數(shù)boy_wants_to_use_bathroom，當他離開浴室時，也會去執(zhí)行另外一個函數(shù)boy_leaves_bathroom；

（2）當一個女生想要使用浴室時，會去執(zhí)行函數(shù)girl_wants_to_use_bathroom，當她離開時, 也會執(zhí)行函數(shù)girl_leaves_bathroom;

問題：請用信號量和P、V操作來實現(xiàn)這四個函數(shù)（初始狀態(tài)：浴室是空的）。

解：信號量的定義：

semaphore  S_mutex;     // 互斥信號量，初值均為1

semaphore  S_boys; // 男生等待隊列，初值為0

semaphore  S_girls;   // 女生等待隊列，初值為0

普通變量的定義：

int  boys_waiting = 0;     // 正在等待的男生數(shù)；

int  girls_waiting = 0; // 正在等待的女生數(shù)；

int  using = 0;      // 當前是否有人在使用浴室;

void  boy_wants_to_use_bathroom ( ){

        P(S_mutex);

        if((using == 0) && (girls_waiting == 0))

         {

                using  =  1;

                V(S_mutex);

         }

        else

         {

                boys_waiting ++;

                V(S_mutex);

                P(S_boys);

         }

}

void  boy_leaves_bathroom ( ){

        P(S_mutex);

        if(girls_waiting  >  0)  // 優(yōu)先喚醒女生

         {

                girls_waiting --;

                V(S_girls);

         }

        else  if(boys_waiting  >  0)

         {

                boys_waiting --;

                V(S_ boys);

         }

        else    using  =  0;         // 無人在等待

        V(S_mutex);

}

void  girl_wants_to_use_bathroom ( ){

        P(S_mutex);

        if(using == 0)

         {

                using  =  1;

                V(S_mutex);

         }

        else

         {

                girls_waiting ++;

                V(S_mutex);

                P(S_girls);

         }

}

void  girl_leaves_bathroom ( ){

        P(S_mutex);

        if(girls_waiting  >  0)  // 優(yōu)先喚醒女生

         {

                girls_waiting --;

                V(S_girls);

         }

        else  if(boys_waiting  >  0)

         {

                boys_waiting --;

                V(S_ boys);

         }

        else    using  =  0;         // 無人在等待

        V(S_mutex);

}

關(guān)于PV操作容易產(chǎn)生的一些疑問：

1，S大于0那就表示有臨界資源可供使用，為什么不喚醒進程？

S大于0的確表示有臨界資源可供使用，也就是說這個時候沒有進程被阻塞在這個資源上，所以不需要喚醒。

2，S小于0應(yīng)該是說沒有臨界資源可供使用，為什么還要喚醒進程？

V原語操作的本質(zhì)在于：一個進程使用完臨界資源后，釋放臨界資源，使S加1，以通知其它的進程，這個時候如果S<0，表明有進程阻塞在該類資源上，因此要從阻塞隊列里喚醒一個進程來“轉(zhuǎn)手”該類資源。比如，有兩個某類資源，四個進程A、B、C、D要用該類資源，最開始S=2，當A進入，S=1，當B進入S=0，表明該類資源剛好用完， 當C進入時S=-1，表明有一個進程被阻塞了，D進入，S=-2。當A用完該類資源時，進行V操作，S=-1，釋放該類資源，因為S<0，表明有進程阻塞在該類資源上，于是喚醒一個。

3，如果是互斥信號量的話，應(yīng)該設(shè)置信號量S=1，但是當有5個進程都訪問的話，最后在該信號量的鏈表里會有4個在等待，也是說S=-4，那么第一個進程執(zhí)行了V操作使S加1，釋放了資源，下一個應(yīng)該能夠執(zhí)行，但喚醒的這個進程在執(zhí)行P操作時因S<0，也還是執(zhí)行不了，這是怎么回事呢？

當一個進程阻塞了的時候，它已經(jīng)執(zhí)行過了P操作，并卡在臨界區(qū)那個地方。當喚醒它時就立即進入它自己的臨界區(qū)，并不需要執(zhí)行P操作了，當執(zhí)行完了臨界區(qū)的程序后，就執(zhí)行V操作。

4，S的絕對值表示等待的進程數(shù)，同時又表示臨界資源，這到底是怎么回事？

當信號量S小于0時，其絕對值表示系統(tǒng)中因請求該類資源而被阻塞的進程數(shù)目.S大于0時表示可用的臨界資源數(shù)。注意在不同情況下所表達的含義不一樣。當?shù)扔?時，表示剛好用完。