??有一個(gè)倉(cāng)庫(kù)，可以存放 A 和 B 兩種產(chǎn)品，倉(cāng)庫(kù)的存儲(chǔ)空間足夠大，但要求: (1)一次只能存入一種產(chǎn)品(A 或 B); (2)-N < (A 產(chǎn)品數(shù)量-B 產(chǎn)品數(shù)量) < M。 其中，N 和 M 是正整數(shù)。試用“存放 A”和“存放 B”以及 P、V 操作描述產(chǎn)品 A 與 產(chǎn)品 B 的入庫(kù)過(guò)程。

Semaphore Sa = M - 1;
Semaphore Sb = N - 1;
//代表還能存入的數(shù)量

Semaphore mutex = 1;

process_A() {
    while(1){
        P(Sa); //取一個(gè)A產(chǎn)品準(zhǔn)備入庫(kù)
        P(mutex);
        A產(chǎn)品入庫(kù);
        // A產(chǎn)品入庫(kù)后還能存入A產(chǎn)品數(shù)量-1
        V(mutex);
        V(Sb); //還能存入B產(chǎn)品數(shù)量+1
    }
}

process_B() {
    while(1){
        P(Sb); //取一個(gè)B產(chǎn)品準(zhǔn)備入庫(kù)
        P(mutex);
        B產(chǎn)品入庫(kù);
        // B產(chǎn)品入庫(kù)后還能存入B產(chǎn)品數(shù)量-1
        V(mutex);
        V(Sa); //還能存入A產(chǎn)品數(shù)量+1
    }
}

??桌子上有一只盤(pán)子，最多可容納兩個(gè)水果，每次只能放入或取出一個(gè)水果。爸爸專向盤(pán)子放蘋(píng)果（ apple），媽媽專向盤(pán)子中放桔子（ orange）；兩個(gè)兒子專等吃盤(pán)子中的桔子，兩個(gè)女兒專等吃盤(pán)子中的蘋(píng)果。請(qǐng)用 P、 V 操作來(lái)實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。

Semaphore mutex = 1;      //互斥信號(hào)量, 其初值為1
Semaphore empty = 2;       //記錄允許向盤(pán)子中放入水果的個(gè)數(shù)，初值為2
Semaphore orange = 0;      //盤(pán)子中已放入的蘋(píng)果的個(gè)數(shù)，初值為0
Semaphore apple = 0;      //盤(pán)子中已放入的桔子的個(gè)數(shù)，初值為0
main()
{
Cobegin
{
　　 father                    //父親進(jìn)程
    {
　　　　while (true)
       {
　　　　　　　　   P(empty);           //減少盤(pán)中可放入的水果數(shù)
                P(mutex);           //申請(qǐng)向盤(pán)中取、放水果
                向盤(pán)中放蘋(píng)果;
                V(mutex);           //允許向盤(pán)中取、放水果
                V(apple);           //遞增盤(pán)中的蘋(píng)果數(shù)
        }
     }
    mother                    //母親進(jìn)程
    {
　　　　while (true)
       {
　　　　　　　　　 P(empty);           //減少盤(pán)中可放入的水果數(shù)
                P(mutex);           //申請(qǐng)向盤(pán)中取、放水果
                向盤(pán)中放桔子;
                V(mutex);           //允許向盤(pán)中取、放水果
                V(orange);          //遞增盤(pán)中的桔子數(shù)
        }
    }
    daughteri（i=1,2）      //兩女兒進(jìn)程
    {
　　　　while (true)
       {
　　　　　　      P(apple);           //減少盤(pán)中蘋(píng)果數(shù)
                P(mutex);           //申請(qǐng)向盤(pán)中取、放水果
                取盤(pán)中蘋(píng)果;
                V(mutex);           //允許向盤(pán)中取、放水果
                V(empty);           //遞增盤(pán)中可放入的水果數(shù)
        }
     }
    sonj（j=1,2）           //兩兒子進(jìn)程
    {
　　　　while (true)
       {
　　　　　　　　  P(orange);          //減少盤(pán)中桔子數(shù)
                P(mutex);           //申請(qǐng)向盤(pán)中取、放水果
                取盤(pán)中桔子;
                V(mutex);           ／/允許向盤(pán)中取、放水果
                V(empty);           //遞增盤(pán)中可放入的水果數(shù)
        }
     }
   }
    Coend
}

??有一個(gè)理發(fā)師，一把理發(fā)椅和 N 把供等候理發(fā)的顧客坐的椅子。如果沒(méi)有顧客，則理發(fā)師便在理發(fā)師椅子上睡覺(jué)；當(dāng)一個(gè)顧客到來(lái)時(shí)，必須喚醒理發(fā)師進(jìn)行理發(fā)；如果理發(fā)師正在理發(fā)時(shí)又有顧客來(lái)到，則如果有空椅子可坐，他就坐下來(lái)等，如果沒(méi)有空椅子，他就離開(kāi)。為理發(fā)師和顧客各編一段程序（偽代碼）描述他們的行為，要求不能帶有競(jìng)爭(zhēng)條件。

Semaphore mutex = 1;    //互斥信號(hào)量，初值為1.
Semaphore  Wait = 0;     //等待服務(wù)的顧客數(shù)
Semaphore  barbers= 0;    //等待顧客的理發(fā)師數(shù)
Int custNum = 0;    //等待的顧客(還沒(méi)理發(fā)的)

Costumer()
{
　　while(true)
　　{
        P(mutex);            //申請(qǐng)理發(fā)
        if(custNum>0)
　　　　　{
            if(custNum<N)   //若等待人數(shù)小于N
　　　　　　　{
                V(mutex);     //釋放進(jìn)程等待
                CustNum++；     //增加等待人數(shù)
            }
　　　　　　　else            //若等待人數(shù)超過(guò)N
　　　　　　　　{
                V(mutex);   //釋放進(jìn)程等待
                離開(kāi)；
             }
　　　　　}
　　　　else                //若目前無(wú)人等待
　　　　{
            V(mutex);        //釋放進(jìn)程等待
            V(barbers)；     //如果必要的話，喚醒理發(fā)師
            理發(fā)；
            離開(kāi)；
            P(mutex);        //要求進(jìn)程等待
            custNum--；        //顧客人數(shù)減1
            V(mutex);       //釋放進(jìn)程等待
            V(wait);        //等待人數(shù)減1
　　　　}
　　}
}

Barber()
{
　　while(true)
　　{
        P(mutex);            //要求進(jìn)程等待
        if(custNum ==0)    //目前無(wú)顧客
　　　　 {
            V(mutex);        //釋放進(jìn)程等待
            P(barbers);        //理發(fā)師睡覺(jué)
　　     }
　　　　else
　　　　{
            V(mutex);        //釋放進(jìn)程等待
            理發(fā);
　　　　}
　　}
}

??吸煙者問(wèn)題。三個(gè)吸煙者在一間房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙，第三個(gè)有自己的火柴。供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西（隨機(jī)地）在桌面上，然后喚醒另一個(gè)吸煙者。試為吸煙者和供應(yīng)者編寫(xiě)程序解決問(wèn)題。

Semaphore S = 1;                //供應(yīng)者
Semaphore S1,S2,S3;                //三個(gè)吸煙者
S1 = S2 = S3 = 0;
bool flag1,flag2,fiag3;            //三種吸煙原料
fiag1=flag2=flag3=true;

Apply()                            //供應(yīng)者
{
　　While(true)
　　{
          P(S);
　　   　　 取兩樣香煙原料放桌上，由flagi標(biāo)記；
　　　     if (flag2 && flag3) //供紙和火柴
　　　　　　{
　　　        V(S1);          //喚醒吸煙者一
　　　       }
　　       else if(flag1 && fiag3) //供煙草和火柴
　　　　　　{
　　　        V(S2);                //喚醒吸煙者二
　　　       }
　　   　　else                      //供煙草和紙
　　　　　　{
　　　        V(S3);                //喚醒吸煙者三
           }
　　　}
}

Smoker1()                         //吸煙者一
{
　　　While(true)
　　 {
　　　    P(S1);
　　　    取原料；
　　　    做香煙；
　　　    V(S);                    //喚醒供應(yīng)者
　　　    吸香煙；
　　　}
}

smoker2()                        //吸煙者二
{
　　　While(true)
　　　{
　　　    P(S2);
　　　    取原料；
　　　    做香煙；
　　　    V(S);                    //喚醒供應(yīng)者
　　　    吸香煙;
　　　}
}

Smoker3()                        //吸煙者三
{
　　　While(true)
{
　　　    P(S3);
　　     取原料；
　　     做香煙；
　　　    V(S);                    //喚醒供應(yīng)者
　　　   吸香煙;
　　　}
}

?? 面包師問(wèn)題。面包師有很多面包和蛋糕，由 n 個(gè)銷(xiāo)售人員銷(xiāo)售。每個(gè)顧客進(jìn)店后先取一個(gè)號(hào)，并且等著叫號(hào)。當(dāng)一個(gè)銷(xiāo)售人員空閑下來(lái)，就叫下一個(gè)號(hào)。請(qǐng)分別編寫(xiě)銷(xiāo)售人員和顧客進(jìn)程的程序。

Semaphore buyer= 0;                //顧客人數(shù)
Semaphore seller = n;            //銷(xiāo)售人員數(shù)
Semaphore mutex_s = 1;            //用于銷(xiāo)售人員的互斥信號(hào)量
Semaphore mutex_b = 1;            //用于顧客的互斥信號(hào)量
int count_s = 0;                //記錄取號(hào)的值
int count_b = 0;                //記錄叫號(hào)的值

void Buy()                    //顧客進(jìn)程
{
    進(jìn)店；
   P(mutex_b);          //取號(hào)
   count_b++;
　　 V(mutex_b);
　　 V(buyer);
　　P(seller);            //等待叫號(hào)
   買(mǎi)面包；
   離開(kāi)
}

void Sell()
{
   while(true)
   {
        P(buyer);
        P(mutex_s);   //叫號(hào)
        count_s++;
        叫編號(hào)為count_s的顧客；
        V(mutex_s);
        V(seller)；
   }
}

?? 桌上有一空盤(pán)，運(yùn)行存放一只水果，爸爸可向盤(pán)中放蘋(píng)果，也可放桔子，兒子專等吃盤(pán)中的桔子，女兒專等吃盤(pán)中的蘋(píng)果。規(guī)定當(dāng)盤(pán)中空時(shí)一次只能放一個(gè)水果供吃者取用，用 P,V 原語(yǔ)實(shí)現(xiàn)爸爸兒子和女兒 3 個(gè)并發(fā)進(jìn)程的同步。

    Semaphore S = 1;      //S 表示盤(pán)子是否為空；
Semaphore Sa = 0;        //Sa 表示盤(pán)中是否有蘋(píng)果；
Semaphore Sb = 0;    //Sb 表示盤(pán)中是否有桔子；

Father()            //父親進(jìn)程
{
    while(TRUE)
　　{
        P(S);
        將水果放入盤(pán)中;
        if (放入的是桔子)
            V(Sb);
        else
            V(Sa);
    }
}

Son()                  //兒子進(jìn)程
{
    while(TRUE)
　　{
        P(Sb);
        從盤(pán)中取出桔子；
        V(S);
　　　　  吃桔子;
    }
}

Daughter()            //女兒進(jìn)程
{
    while(TRUE)
　　{
        P(Sa);
        從盤(pán)中取出蘋(píng)果；
        V(S);
        吃蘋(píng)果;
    }
}

?? 寫(xiě)者優(yōu)先的讀者－－寫(xiě)者問(wèn)題。讀者-寫(xiě)者問(wèn)題為數(shù)據(jù)庫(kù)訪問(wèn)建立了一個(gè)模型。例如,一個(gè)系統(tǒng),其中有許多競(jìng)爭(zhēng)的進(jìn)程試圖讀寫(xiě)其中的數(shù)據(jù),多個(gè)進(jìn)程同時(shí)讀是可以接受的,但如果一個(gè)進(jìn)程正在更新數(shù)據(jù)庫(kù),則所有的其他進(jìn)程都不能訪問(wèn)數(shù)據(jù)庫(kù)，即使讀操作也不行。寫(xiě)者優(yōu)先是指當(dāng)一個(gè)寫(xiě)者到達(dá)時(shí)，將阻止其后面的讀者進(jìn)入數(shù)據(jù)庫(kù)，直到其離開(kāi)為止。

    Semaphore Mut1, Mut2, Wmutex, Fmutex;          //互斥信號(hào)量
int Rcount, Wcount;                          //讀寫(xiě)者人數(shù)
Mut1 = Mut2 = WMutex = Fmutex = 1;
Rcount = Wcount = 0;

Writer()                            //寫(xiě)者進(jìn)程
{
　　　While(true)
　　　{
　　　    P(Mut1);
　　　    Wcount=Wcount+1；
　　　    If (Wcount==1)
　　　　　{
　　　        P(Fmutex);     //如有讀者，寫(xiě)者阻塞在此處
　　　    }
　　　    V(Mut1);
　　　    P(WMutex);
　　　    寫(xiě)；
　　　    V(Wmutex);
　　　    P(Mut1);
　　　    Wcount=Wcount-1;
　　　    If (Wcount==0)
　　　　  {
　　　        V(Fmutex);
　　　    }
　　　    V(Mut1);
　　　}
}

Reader()                            //讀者進(jìn)程
{
　　　While(true)
　　　{
　　　    P(Mut2);
　　　    Rcount=Rcount+1;
　　　    If (Rcount==1)
　　　　　 {
　　　        P(Fmutex);
　　　    }
　　　    V(Mut2);
　　　    讀；
　　　    P(Mut2);
　　　    Rcount=Rcount-1;
　　　    If (Rcount==0)
　　　　  {
　　　         V(Fmutex);
　　　    }
　　　    V(Mut2);
　　　}
}

?? 在天津大學(xué)與南開(kāi)大學(xué)之間有一條彎曲的小路，這條路上每次每個(gè)方向上只允許一輛自行車(chē)通過(guò)。但其中有一個(gè)小的安全島 M，同時(shí)允許兩輛自行車(chē)停留，可供兩輛自行車(chē)已從兩端進(jìn)入小路的情況下錯(cuò)車(chē)使用。如圖所示。

file

下面的算法可以使來(lái)往的自行車(chē)均可順利通過(guò)。其中使用了 4 個(gè)信號(hào)量， T 代表天大路口資源， S 代表南開(kāi)路口資源， L 代表從天大到安全島一段路的資源， K 代表從南開(kāi)到安全島一段路的資源。程序如下，請(qǐng)?jiān)诳瞻孜恢锰幪顚?xiě)適當(dāng)?shù)?PV 操作語(yǔ)句，每處空白可能包含若干個(gè) PV 操作語(yǔ)句。

begin
    t:=1;s:=1;l:=1;k:=1;
    cobegin
    從天大到南開(kāi)的進(jìn)程
        begin
            ______(1)______
           通過(guò) L 路段;
           進(jìn)入安全島 M；
           ______(2)______
           通過(guò) K 路段
           ______(3)______
        end
   從南開(kāi)到天大的進(jìn)程
       begin
          略，與“從天大到南開(kāi)的進(jìn)程”相反。
       end
    coend
end

??解答：

??(1) P(t); P(l);

??(2) V(l); P(k);

??(3) V(k); V(t);

??三個(gè)進(jìn)程 P1、 P2、 P3 互斥使用一個(gè)包含 N(N>0)個(gè)單元的緩沖區(qū)。 P1 每次用 produce()生成一個(gè)正整數(shù)并用 put()送入緩沖區(qū)某一空單元中;P2 每次用 getodd()從該緩沖區(qū)中取出一個(gè)奇數(shù)并用 countodd()統(tǒng)計(jì)奇數(shù)個(gè)數(shù);P3 每次用 geteven()從該緩沖區(qū)中取出一個(gè)偶數(shù)并用 counteven()統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng),并說(shuō)明所定義信號(hào)量的含義。要求用偽代碼描述。

P1()
{
　　　While(true)
　　　{
　　　    X = produce();      //生成一個(gè)數(shù)
　　　 　 P(empty);     //是否有空單元格
　　　    P(mutex);    //進(jìn)入臨界區(qū)
　　　    Put();
　　　    if(X%2 == 0)
　　　         V(s2);   //如果是偶數(shù)，向P3發(fā)出信號(hào)
　　　    else
　　　          V(s1);   //如果是奇數(shù)，向P2發(fā)出信號(hào)
　　　    V(mutex);         //離開(kāi)臨界區(qū)，釋放互斥信號(hào)量
　　　}
}

P2()
{
　　　While(true)
　　　{
　　　    P(s1);     //收到P1發(fā)送來(lái)的信號(hào)，已產(chǎn)生奇數(shù)
　　　 　 P(mutex);         //進(jìn)入臨界區(qū)
　　　    getodd();
　　　    countodd():=countodd()+1;
　　　    V(mutex);
　　　    V(empty);         //離開(kāi)臨界區(qū)，釋放互斥信號(hào)量
　　　}
}

P3()
{
　　　While(true)
　　　{
　　　 　 P(s2)        //收到P1發(fā)送來(lái)的信號(hào)，已產(chǎn)生偶數(shù)
　　　   P(mutex);         //進(jìn)入臨界區(qū)
　　　   geteven();
　　　   counteven():=counteven()+1;
　　　   V(mutex);
　　　   V(empty);         //離開(kāi)臨界區(qū)，釋放互斥信號(hào)量
　　　}
}