過(guò)橋問(wèn)題

一條河上架設(shè)了由N個(gè)橋墩組成的一座橋。若一個(gè)橋墩只能站一個(gè)人川蒙，過(guò)河的人只能沿著橋向前走而不能向后退蚜厉。過(guò)河時(shí)，只要對(duì)岸無(wú)人過(guò)畜眨，就可以過(guò)昼牛。但不允許河對(duì)岸的兩個(gè)人同時(shí)過(guò)，以防止出現(xiàn)死鎖康聂。請(qǐng)給出兩個(gè)方向的人順利過(guò)河的同步算法匾嘱。

不妨將兩個(gè)方向稱為正方和反方。為了考慮這個(gè)問(wèn)題：

1. 首先要想第一個(gè)過(guò)橋人的情況早抠，如果正反雙方都要過(guò)橋霎烙，那么第一個(gè)上橋的那個(gè)人就獲得對(duì)橋的控制權(quán)，從而使另一方必須等待蕊连。
2. 其次悬垃，假定正方人在過(guò)橋，因?yàn)橹挥蠳個(gè)橋墩甘苍，每個(gè)橋墩只能站一個(gè)人尝蠕，所以在正方過(guò)橋時(shí)只能控制在N個(gè)人之內(nèi)。
3. 最后载庭，最后一個(gè)離橋的人要釋放對(duì)橋的控制權(quán)看彼。

值得注意的是廊佩，第一個(gè)上橋的人（占有橋）不一定是最后一個(gè)離橋的人（釋放橋），這個(gè)問(wèn)題暗含的一個(gè)思想是靖榕，等待過(guò)橋的任何一個(gè)人都可能是第一個(gè)上橋的人标锄，正在過(guò)橋的這些人中任何一個(gè)都可能是最后一個(gè)離橋的人。

為此茁计，必須解決以下4個(gè)問(wèn)題：

• 如何確定是第一個(gè)上橋的人和最后一個(gè)離橋的人料皇？
• 如何獲得和釋放對(duì)橋的控制權(quán)？
• 誰(shuí)來(lái)獲得星压、釋放對(duì)橋的控制權(quán)践剂，為什么？
• 如何控制在N個(gè)人之內(nèi)娜膘？

關(guān)于這四個(gè)問(wèn)題的解答是：

• 為了確定第一個(gè)上橋的和最后一個(gè)離橋的人逊脯，可以設(shè)置一個(gè)計(jì)數(shù)器counter=0，只要上橋一個(gè)人就令其加一竣贪、只要下橋一個(gè)人就令其減一男窟，這樣，如果counter等于1就說(shuō)明這是第一個(gè)上橋的人贾富，如果counter等于0說(shuō)明這是最后一個(gè)離橋的人忱叭。因?yàn)檫^(guò)橋的人都要操作這個(gè)counter赐纱，從而counter也就變成了一個(gè)臨界資源，要給它設(shè)置一個(gè)信號(hào)量semCounter=1（同時(shí)只能有一個(gè)人來(lái)操作變量counter），否則就有可能出現(xiàn)counter的值錯(cuò)亂情況殖氏。

• 因?yàn)檎措p方都要過(guò)同一個(gè)橋奔穿，所以橋是一個(gè)臨界資源独柑，從而要設(shè)一個(gè)信號(hào)量semBridge=1盈厘，獲得對(duì)橋的控制權(quán)就是要P(semBridge)，而釋放對(duì)橋的控制權(quán)就是V(semBridge)盗胀。

• 那么誰(shuí)來(lái)獲得艘蹋、誰(shuí)來(lái)釋放對(duì)橋的控制權(quán)呢？也許你會(huì)考慮票灰，每一個(gè)上橋的人都執(zhí)行P(semBridge)來(lái)獲得上橋資格女阀，每一個(gè)離橋的人都執(zhí)行V(semBridge)來(lái)釋放資源。事實(shí)上這是錯(cuò)誤的也是不必要的屑迂。這是因?yàn)椋?/p>

  • 每一方過(guò)橋的人數(shù)事先是不固定的（盡管不能超過(guò)N浸策，但是并不強(qiáng)制規(guī)定一定要是N個(gè)人），所以如果按照這種PV設(shè)計(jì)思路惹盼，semBridge的初始值是無(wú)法設(shè)置的
  • 如果semBridge初始值設(shè)置為N庸汗，就有可能出現(xiàn)2種情況：
    • 正方上橋的人不足N人，他們執(zhí)行P原語(yǔ)后semBridge仍然非負(fù)手报，這樣反方的人執(zhí)行P原語(yǔ)后也上了橋蚯舱，兩方人員就會(huì)相對(duì)而發(fā)生死鎖改化，這是題目不允許的；
    • 又或者正方上橋的人恰好為N個(gè)人枉昏，執(zhí)行N次P原語(yǔ)后semBridge為0陈肛，這樣反方的人執(zhí)行P原語(yǔ)后進(jìn)入等待狀態(tài)，似乎是安全的凶掰。但是存在一個(gè)致命的失誤：每一個(gè)離橋的人都要執(zhí)行V原語(yǔ)來(lái)釋放。這樣蜈亩，一旦正方的人至少有一人下橋懦窘，反方的人就有可能獲得上橋資格，但時(shí)此時(shí)正方的人尚未全部下橋稚配，因此也會(huì)出現(xiàn)死鎖情況畅涂。

  正確的策略應(yīng)該是：第一個(gè)上橋的人執(zhí)行P(semBridge)，最后一個(gè)離橋的人執(zhí)行V(semBridge)道川。這樣就能保證一旦正方的人上橋午衰，除非最后一個(gè)人也下橋，否則反方人員必須等待冒萄。這也是為什么semBridge的初始值是1的原因臊岸。
  ????換句話說(shuō)，正方向第一個(gè)人執(zhí)行P原語(yǔ)后尊流，第二個(gè)人帅戒、第三個(gè)人……都不必執(zhí)行P原語(yǔ)而直接上橋（if語(yǔ)句實(shí)現(xiàn)）。
  ????而反方向要上橋時(shí)崖技，必然有第一個(gè)上橋人逻住，這個(gè)上橋人必須先對(duì)反方的counter的信號(hào)量semCounter執(zhí)行P原語(yǔ)，之后因?yàn)闄z測(cè)到counter為1后才會(huì)對(duì)semBridge執(zhí)行P原語(yǔ)迎献，此后進(jìn)入等待瞎访，注意因?yàn)檫M(jìn)入等待狀態(tài)，信號(hào)量semCounter根本沒(méi)有被釋放吁恍！扒秸，從而反方向的第二個(gè)人、第三個(gè)人……依次對(duì)semCounter（而不是semBridge）執(zhí)行P原語(yǔ)進(jìn)入等待冀瓦，根本沒(méi)有上橋機(jī)會(huì)鸦采。

• 過(guò)橋的人數(shù)如何控制在N個(gè)人以內(nèi)呢？設(shè)置一個(gè)控制人數(shù)的信號(hào)量semMax=N再適合不過(guò)咕幻。這個(gè)信號(hào)量可以作為正方雙方的共用信號(hào)量渔伯，因?yàn)閷?duì)它的操作是在獲取到橋的控制權(quán)（P(semBridge)）之后，所以不會(huì)發(fā)生沖突肄程。
  注意到在之前已經(jīng)定義了一個(gè)記錄人數(shù)的變量counter锣吼，為什么不使用counter來(lái)統(tǒng)計(jì)人數(shù)呢选浑？因?yàn)槿绻呀?jīng)有N個(gè)人在過(guò)橋，那么正方等待過(guò)橋的人就必須等待玄叠。信號(hào)量的PV操作有令其等待的功能古徒，而單純的變量則沒(méi)有，盡管可以對(duì)其進(jìn)行數(shù)值比較來(lái)查看是否超過(guò)人數(shù)上限读恃。

執(zhí)行代碼如下：

//設(shè)置計(jì)數(shù)變量
counterA=0,counterB=0; //正反雙方的計(jì)數(shù)變量
//設(shè)置信號(hào)量
semaphore 
    semCounterA=1, semCounterB=1,
    semBridge=1,
    semMax=N
//正方向上橋的過(guò)程
void directA(int i)
{
    //判斷是否是第一個(gè)上橋人隧膘，若是則鎖住橋
    P(semCounterA);
        counterA++;
        if(counterA==1)
            P(semBridge);
    V(semCounterA);

    //控制人數(shù)不超過(guò)N
    P(semMax);
        上橋，過(guò)橋寺惫，下橋;
    V(semMax);

    //離橋時(shí)減去人數(shù)疹吃，若是最后一個(gè)離橋則釋放橋
    P(semCounterA);
        counterA--;
        if(counterA==0)
            V(semBridge);
    V(counterA);
}

//反方向與正方向同理
void directB(int i){
    /*....*/
}

注意這個(gè)設(shè)計(jì)的一個(gè)極限情況是，假設(shè)正方向的人開(kāi)始過(guò)橋西雀，并且過(guò)橋的人有無(wú)窮個(gè)人萨驶，那么反方向的人永遠(yuǎn)也無(wú)法獲得過(guò)橋機(jī)會(huì)。因?yàn)椴淮嬖谧詈笠粋€(gè)人來(lái)釋放橋艇肴。
過(guò)橋問(wèn)題的一個(gè)變種——第二類讀寫(xiě)者問(wèn)題將會(huì)對(duì)此加以限制腔呜。

讀寫(xiě)者問(wèn)題（第一類）

某數(shù)據(jù)庫(kù)有一個(gè)寫(xiě)進(jìn)程、多個(gè)讀進(jìn)程再悼，它們之間讀核畴、寫(xiě)操作的互斥要求是：寫(xiě)進(jìn)程運(yùn)行時(shí)，其他讀冲九、寫(xiě)進(jìn)程不能對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作膛檀。讀進(jìn)程之間不互斥，可以同時(shí)讀數(shù)據(jù)庫(kù)娘侍。請(qǐng)用信號(hào)量及PV操作描述這一組進(jìn)程的工作過(guò)程咖刃。

分析此題的約束條件：

1. 讀者之間不發(fā)生互斥
2. 寫(xiě)者與讀者（甚至是其他寫(xiě)者）之間發(fā)生互斥
3. 數(shù)據(jù)庫(kù)是一個(gè)臨界資源區(qū)

多個(gè)讀者之間可以共存，所以第一個(gè)讀者會(huì)與寫(xiě)者競(jìng)爭(zhēng)資源憾筏，一旦讀者進(jìn)入臨界資源區(qū)嚎杨，它就會(huì)“鎖”住這個(gè)資源，寫(xiě)者進(jìn)入等待氧腰，而其他讀者可以進(jìn)入枫浙。最后一個(gè)讀者退出臨界資源區(qū)時(shí)釋放資源。
為了識(shí)別第一個(gè)讀者和最后一個(gè)讀者古拴，設(shè)置計(jì)數(shù)變量readerCounter=0箩帚，計(jì)數(shù)變量保護(hù)信號(hào)量semReaderCounter=1。數(shù)據(jù)庫(kù)資源區(qū)公有信號(hào)量semDB=1黄痪。
由于讀者的個(gè)數(shù)不受限制紧帕，所以沒(méi)有必要設(shè)置semMax。
由此寫(xiě)出的偽代碼是：

//讀者技術(shù)變量
readerCounter=0;

//信號(hào)量
semaphore
    semReaderCounter=1,
    semDB=1;

//寫(xiě)者進(jìn)程
writer(){
    P(semDB)
        寫(xiě)操作
    V(semDB)
}

//讀者進(jìn)程
reader(){
    //判定是否是第一個(gè)讀者，如果是則競(jìng)爭(zhēng)
    P(semReaderCounter)
        semReaderCounter++;
        if(semReaderCounter==1)
            P(semDB)
    V(semReaderCounter)
    
    執(zhí)行讀操作
    
    //判定是否是最后一個(gè)離開(kāi)數(shù)據(jù)庫(kù)的讀者是嗜，若是愈案，則釋放資源
    P(semReaderCounter)
        semReaderCounter--;
        if(semReaderCounter==0)
            V(semDB)
    V(semReaderCounter)
}

注意到，此時(shí)也存在一個(gè)隱患：一旦讀者進(jìn)程爭(zhēng)取到數(shù)據(jù)庫(kù)鹅搪，并且此后有源源不斷的讀者進(jìn)程也進(jìn)入數(shù)據(jù)庫(kù)站绪，且讀取時(shí)間很長(zhǎng)，數(shù)據(jù)庫(kù)資源得不到釋放丽柿，那么寫(xiě)者進(jìn)程就有可能長(zhǎng)時(shí)間被阻塞而發(fā)生“饑餓現(xiàn)象”恢准。為此，考慮第二類的讀寫(xiě)者問(wèn)題甫题。

讀寫(xiě)者問(wèn)題（第二類）

將只讀數(shù)據(jù)的進(jìn)程稱為“讀者”進(jìn)程馁筐，而寫(xiě)或修改數(shù)據(jù)的進(jìn)程稱為“寫(xiě)者”進(jìn)程。允許多個(gè)“讀者”同時(shí)讀數(shù)據(jù)幔睬，但不允許“寫(xiě)者”與其他“讀者”或“寫(xiě)者”同時(shí)訪問(wèn)數(shù)據(jù)眯漩。另外芹扭，要保證：一旦有“寫(xiě)者”等待時(shí)麻顶，新到達(dá)的“讀者”必須等待，直到該“寫(xiě)者”完成數(shù)據(jù)訪問(wèn)為止舱卡。試用P辅肾、V 操作正確實(shí)現(xiàn)“讀者”與“寫(xiě)者”的同步。

這個(gè)問(wèn)題的約束條件在第一類讀寫(xiě)者問(wèn)題的基礎(chǔ)上增加了一條：

• 一旦有“寫(xiě)者”等待時(shí)轮锥，新到達(dá)的“讀者”必須等待矫钓，直到該“寫(xiě)者”完成數(shù)據(jù)訪問(wèn)為止。

這是基于“寫(xiě)者優(yōu)先”的策略舍杜。寫(xiě)者優(yōu)先是因?yàn)樾履龋?dāng)共享數(shù)據(jù)區(qū)被讀者占用時(shí)，緊鄰的讀者可能會(huì)立刻進(jìn)入既绩，并且長(zhǎng)時(shí)間讀取概龄，而寫(xiě)者相當(dāng)長(zhǎng)的時(shí)間被阻塞無(wú)法進(jìn)入數(shù)據(jù)區(qū)，從而造成“寫(xiě)者饑餓”饲握。

這個(gè)問(wèn)題是過(guò)橋問(wèn)題的一個(gè)變種私杜。若將讀者、寫(xiě)者分別看作是兩方過(guò)橋的人救欧，而將共享數(shù)據(jù)區(qū)看作是一座橋（可以通過(guò)任意數(shù)目的人衰粹，即過(guò)橋問(wèn)題中的N=+∞）。由此可以轉(zhuǎn)述為如下描述：

讀者笆怠、寫(xiě)者分別在橋兩邊準(zhǔn)備過(guò)橋铝耻。過(guò)橋的人只能沿著橋向前走而不能向后退。對(duì)于讀者而言蹬刷，只要對(duì)岸沒(méi)有寫(xiě)者田篇，就可以通過(guò)任意數(shù)目的人替废，但是一旦對(duì)岸有寫(xiě)者準(zhǔn)備過(guò)橋，準(zhǔn)備過(guò)橋的讀者將等待寫(xiě)者過(guò)橋后才能過(guò)橋泊柬。對(duì)于讀者而言椎镣，如果橋上有任何人（讀者或?qū)懻撸急仨毜人麄冞^(guò)了橋后兽赁，自己才能過(guò)橋状答。

大體的代碼框架沒(méi)有變化。變量和信號(hào)量需要：

• 橋（共享數(shù)據(jù)區(qū)）的互斥信號(hào)量：semDataMutex=1
• 讀者刀崖、寫(xiě)者的計(jì)數(shù)變量：readerCounter=0, writerCounter=0
• 計(jì)數(shù)變量保護(hù)信號(hào)量：semReaderCounter=1, semWriterCounter=1

由于對(duì)于讀者而言不限制過(guò)橋人數(shù)惊科，因此沒(méi)有必要設(shè)置semMax信號(hào)量。

在過(guò)橋問(wèn)題中亮钦，讀者的步驟分為三個(gè)部分：

//第一部分：準(zhǔn)備上橋
if(是第一個(gè)上橋的讀者){
    試圖獲取過(guò)橋的權(quán)力
    if(沒(méi)有成功)  進(jìn)入等待隊(duì)列
}

//第二部分：過(guò)橋
過(guò)橋

//第三部分：準(zhǔn)備下橋
if(是最后一個(gè)下橋的讀者){
    釋放橋資源
}       

可以看出馆截，只要有一個(gè)讀者上了橋，并且橋上還有讀者蜂莉，后續(xù)讀者都可以上橋蜡娶。為了保證“一旦對(duì)岸有寫(xiě)者準(zhǔn)備過(guò)橋，準(zhǔn)備過(guò)橋的讀者將等待寫(xiě)者過(guò)橋后才能過(guò)橋”映穗，必須對(duì)這種行為加以限制：
????考慮存在某個(gè)信號(hào)量窖张，它指示是否有寫(xiě)者準(zhǔn)備過(guò)河，每個(gè)讀者上橋之間都要檢測(cè)這個(gè)信號(hào)量蚁滋，如果發(fā)生寫(xiě)者準(zhǔn)備過(guò)橋的情況宿接，它就要進(jìn)入等待隊(duì)列。顯然辕录，對(duì)這個(gè)信號(hào)量的檢測(cè)操作必須在準(zhǔn)備上橋進(jìn)行:

if(有寫(xiě)者準(zhǔn)備過(guò)河){
    進(jìn)入等待序列
}else{
    //第一部分：準(zhǔn)備上橋
}

//第二部分：過(guò)橋

//第三部分：準(zhǔn)備下橋    

對(duì)于寫(xiě)者：

• 如果他是第一個(gè)準(zhǔn)備上橋的人睦霎，那么他要發(fā)出某個(gè)信號(hào)告知對(duì)岸那些準(zhǔn)備過(guò)橋的讀者他要準(zhǔn)備過(guò)河，請(qǐng)讀者等待走诞。
• 根據(jù)寫(xiě)者優(yōu)先副女，如果有很多個(gè)寫(xiě)者準(zhǔn)備過(guò)橋，這個(gè)信號(hào)只有等最后一個(gè)寫(xiě)者過(guò)完橋后才能撤銷(xiāo)速梗，在此期間肮塞，等待的讀者還是在等待。
• 因?yàn)閷?xiě)者必須等橋上正在過(guò)河的任何人（無(wú)論是寫(xiě)者還是讀者）都過(guò)了他才能過(guò)橋（互斥）姻锁，所以它要競(jìng)爭(zhēng)過(guò)橋

因此它的步驟分為5個(gè)部分

//第一部分：發(fā)出信號(hào)
if(若是第一個(gè)上橋的寫(xiě)者){
    發(fā)出準(zhǔn)備過(guò)河信號(hào)
}

//第二部分：準(zhǔn)備過(guò)橋
試圖過(guò)橋（競(jìng)爭(zhēng)橋資源）
if(沒(méi)有成功)  //橋上還有人
    進(jìn)入等待隊(duì)列  //等待他們都通過(guò)橋

//第三部分：過(guò)橋
過(guò)橋

//第四部分：準(zhǔn)備下橋
釋放橋資源  //保證橋上最多只有一個(gè)寫(xiě)者枕赵，并且只有寫(xiě)者全部通過(guò)讀者才能繼續(xù)過(guò)
if(是最后一個(gè)下橋的寫(xiě)者){
    撤銷(xiāo)寫(xiě)者過(guò)河信號(hào)，等待中的讀者可以準(zhǔn)備過(guò)橋
}       

綜上所述位隶，這個(gè)“準(zhǔn)備過(guò)河的信號(hào)”可以設(shè)為semWRMutex=1

//變量
readerCounter=0, writerCounter=0 //計(jì)數(shù)變量
//信號(hào)量
semaphore
    semDataMutex=1 //共享資源互斥
    semReaderCounter=1, semWriterCounter=1  //計(jì)數(shù)變量保護(hù)
    semWRMutex=1 //有寫(xiě)者準(zhǔn)備過(guò)河

//讀者：
reader(){
    //探測(cè)是否有寫(xiě)者準(zhǔn)備進(jìn)入拷窜，這里不要把P理解為wait，
    //在這里需要有一個(gè)掛入等待隊(duì)列的功能，P是合適的
    P(semWRMutex)  
        //如果沒(méi)有寫(xiě)者準(zhǔn)備進(jìn)入篮昧，則semWRMutex=1赋荆，
        //P(semWRMutex) 后semWRMutex為0，然后這個(gè)讀者進(jìn)入       

        P(semReaderCounter)
            readerCounter++;
            if(readerCounter==1)
                P(semsemDataMutex)
        V(semReaderCounter)

     //在下面的語(yǔ)句中又立刻將semWRMutex設(shè)為1
    V(semWRMutex)

    //執(zhí)行讀操作
    /*................*/


    //準(zhǔn)備退出
    P(semReaderCounter)
        readerCounter--;
        if(readerCounter==0)
            V(semsemDataMutex)
    V(semReaderCounter)
}


//寫(xiě)者
writer(){
    P(semWriterCounter)
        WriterCounter++;
        if(WriterCounter==1)
            //第一個(gè)準(zhǔn)備進(jìn)入的寫(xiě)者發(fā)出準(zhǔn)備進(jìn)入信號(hào)
            //這個(gè)信號(hào)直到最后一個(gè)寫(xiě)者結(jié)束后才撤銷(xiāo)
            //注意這里的“發(fā)出”并不是signal（V原語(yǔ)）
            P(semWRMutex)
    V(semWriterCounter)

    //由于互斥懊昨，必須競(jìng)爭(zhēng)
    P(semsemDataMutex)
    //執(zhí)行寫(xiě)操作
    //退出
    V(semsemDataMutex)
    
    //探測(cè)是否是最后一個(gè)寫(xiě)者
    P(semWriterCounter)
        WriterCounter--;
        if(WriterCounter==0)
            //最后一個(gè)寫(xiě)者結(jié)束后撤銷(xiāo)信號(hào)窄潭，通知相關(guān)等待讀者進(jìn)入
            V(semWRMutex)
    V(semWriterCounter)
}

倉(cāng)庫(kù)問(wèn)題

有一個(gè)倉(cāng)庫(kù)，可以存放A 和B 兩種產(chǎn)品酵颁，但要求：
（1）每次只能存入一種產(chǎn)品（A 或B）嫉你；
（2）-N＜A 產(chǎn)品數(shù)量－B 產(chǎn)品數(shù)量＜M。其中躏惋，N 和M 是正整數(shù)幽污。
試用同步算法描述產(chǎn)品A 與產(chǎn)品B 的入庫(kù)過(guò)程。

對(duì)于不等式-N＜A 產(chǎn)品數(shù)量－B 產(chǎn)品數(shù)量＜M可以拆分為兩個(gè)不等式：B-A<N且A-B<M簿姨。也就是說(shuō)距误，B的數(shù)量至多只能比A多N-1個(gè)，且A的數(shù)量至多只能比B多M-1個(gè)扁位。
顯然准潭，倉(cāng)庫(kù)是一個(gè)臨界資源，所以需要設(shè)置一個(gè)互斥信號(hào)量semRepository=1贤牛。

然而如何保證A惋鹅、B的數(shù)量滿足約束條件呢则酝？考慮到殉簸，如果A、B之間的數(shù)量差一旦超過(guò)約束范圍沽讹，比如某時(shí)刻A-B=M-1了般卑，那么接下來(lái)A就不能再放入了，這個(gè)時(shí)候A必須進(jìn)入等待隊(duì)列等待爽雄。所以很容易想到使用信號(hào)量來(lái)保證約束條件蝠检。
分別為A、B設(shè)置約束信號(hào)量semEnableA挚瘟，semEnableB叹谁，分別表示A、B還可以存入的數(shù)量乘盖，那么它們的初值是多少呢焰檩？或者說(shuō)，這兩個(gè)信號(hào)量該如何使用订框？

考慮在任意時(shí)刻析苫，倉(cāng)庫(kù)中A、B的數(shù)量都在約束范圍內(nèi)，假定現(xiàn)在要放入一個(gè)A衩侥，必須檢測(cè)這個(gè)A能否放入国旷，即執(zhí)行P(semEnableA)操作，如果判定不能放入茫死，則A進(jìn)入等待隊(duì)列跪但；另外，如果判定能放入峦萎，那么A放入后特漩，B還可存入數(shù)量也要加一個(gè)（semEnableB++），這樣雙方數(shù)量差才能不超過(guò)界限骨杂，這就要求要執(zhí)行V(semEnableB)涂身。對(duì)于B而言也是同理。也就是：semEnableA在A進(jìn)程中被P搓蚪，但是卻是在B進(jìn)程中被V蛤售。

設(shè)semEnableA初值為K。在初始時(shí)刻妒潭，倉(cāng)庫(kù)是空的悴能。考慮一個(gè)極端情況雳灾，就是只放入A而不放B漠酿，從而不斷執(zhí)行P(semEnableA)操作，semEnable不斷自減谎亩，由于B的數(shù)量始終是0炒嘲，所以這個(gè)過(guò)程直到A的數(shù)量為M-1后停止，此時(shí)semEnableA=K-(M-1)匈庭。之后再放入A時(shí)執(zhí)行P(semEnableA)將導(dǎo)致A被掛起等待夫凸，這蘊(yùn)含了semEnableA=0，也就是K=M-1阱持，所以semEnableA的初始值為M-1夭拌。對(duì)于B而言，同理可得semEnableB的初始值為N-1衷咽。

由此寫(xiě)出如下為偽代碼：

semaphore
    semRepository=1,
    semEnableA=M-1, semEnableB=N-1

//放入A
putA(){
    取A產(chǎn)品
    P(semEnableA) //檢測(cè)能否放入A
        P(semRepository) //若能鸽扁，則鎖住倉(cāng)庫(kù)
              放入A
        V(semRepository)
    V(semEnableB) //將B可放入的數(shù)量加一個(gè)
}

//放入B
putB(){
    取B產(chǎn)品
    P(semEnableB) //檢測(cè)能否放入B
        P(semRepository) //若能，則鎖住倉(cāng)庫(kù)
              放入B
        V(semRepository)
    V(semEnableA) //將A可放入的數(shù)量加一個(gè)
}

多任務(wù)同步問(wèn)題（狀態(tài)合并和拓?fù)渑判颍?/h3>

設(shè)有如下5個(gè)任務(wù)镶骗，每個(gè)節(jié)點(diǎn)代表一個(gè)任務(wù)桶现。對(duì)每一個(gè)任務(wù)而言，只有其所有前驅(qū)任務(wù)都被執(zhí)行完畢卖词，該任務(wù)才能開(kāi)始執(zhí)行巩那，請(qǐng)使用P吏夯、V原語(yǔ)實(shí)現(xiàn)。

這是一個(gè)典型的進(jìn)程同步問(wèn)題即横。一種普適的做法是為每一個(gè)箭頭標(biāo)明一個(gè)使用信號(hào)量噪生，由于此處有7個(gè)箭頭，于是存在7個(gè)私用信號(hào)量东囚，它們的初始值都是0跺嗽。

對(duì)于某個(gè)任務(wù)T_i，它的框架是：

Ti {
    對(duì)Ti的入度信號(hào)量執(zhí)行P原語(yǔ)
    執(zhí)行Ti
    對(duì)Ti的出度信號(hào)量執(zhí)行V原語(yǔ)
}

例如對(duì)于T₁有：

T1{
    do T1    //由于T1沒(méi)有前驅(qū)任務(wù)页藻，所以不必執(zhí)行P原語(yǔ)
    V(S12)
    V(S13)
}

對(duì)于T2有：

T1{
    P(S12)
    do T2  
    V(S24)
}

對(duì)于T6

T6{
    P(S46)
    P(S56)
    do T6    //由于T6沒(méi)有后繼任務(wù)桨嫁，所以不必執(zhí)行V原語(yǔ)
}

但是實(shí)際上，可以通過(guò)合并箭頭的方式來(lái)減少信號(hào)量的數(shù)目份帐×О桑考慮下面兩種情況：

1. 一對(duì)多情況
   
   
   即存在n個(gè)進(jìn)程P_ik（k=1,2,...,n），它們的前驅(qū)進(jìn)程是P₁废境。事實(shí)上可以將這n個(gè)箭頭合并為一個(gè)箭頭畜挨，從而只用設(shè)置一個(gè)信號(hào)量S_1i=0：
   
   
   對(duì)于P₁而言，它的程序框架是：

   P1{
       /*...前驅(qū)事務(wù)代碼*/
       V(S1i)
       V(S1i)
       ...... //執(zhí)行n次V(S1i)
       V(S1i)
   }
   

   而對(duì)P_ik而言噩凹，它的代碼框架是：

   Pik{
       P(S1i)
       /*...后繼事務(wù)代碼*/
   }
   

   對(duì)于其解釋是這樣的：假定在極短的時(shí)間內(nèi)進(jìn)程P₁和P_ik（k=1,2,...,n）進(jìn)程同時(shí)執(zhí)行了巴元。那么由于信號(hào)量S_1i初始值為0，且P(S_1i)被執(zhí)行n次驮宴，從而S_1i=-n并且P_ik（k=1,2,...,n）均被掛入等待對(duì)隊(duì)列進(jìn)行等待逮刨。然后，等到P₁執(zhí)行完它的前驅(qū)事務(wù)代碼后堵泽，依次執(zhí)行n次V(S_1i)修己，每次執(zhí)行一次就會(huì)使得等待隊(duì)列中的一個(gè)進(jìn)程P_ik進(jìn)入就緒隊(duì)列準(zhǔn)備執(zhí)行。由于這n個(gè)后繼進(jìn)程不在同一條鏈上落恼，所以它們可以并發(fā)執(zhí)行箩退，同時(shí)也滿足了同步關(guān)系离熏。
2. 多對(duì)一情況
   
   
   對(duì)于這種情況佳谦，我們?nèi)匀豢梢詫⒓^進(jìn)行合并，并專設(shè)一個(gè)信號(hào)量S_i1=0來(lái)表示同步關(guān)系
   
   
   對(duì)于P₁而言滋戳，它的程序框架是：

   P1{
       P(S1i)
       P(S1i)
       ...... //執(zhí)行n次P(Si1)
       P(S1i)
       /*...后繼事務(wù)代碼*/
   }
   

   而對(duì)P_ik而言钻蔑，它的代碼框架是：

   Pik{
       /*...前驅(qū)事務(wù)代碼*/
       V(Si1)
   }
   

   對(duì)于這種情況的解釋是：當(dāng)進(jìn)程P₁執(zhí)行第一句P(S_i1)時(shí)，由于信號(hào)量S_i1初值為0奸鸯，從而P₁進(jìn)入等待隊(duì)列咪笑，此時(shí)S_i1=-1。然后娄涩，任意一個(gè)前驅(qū)進(jìn)程P_ik執(zhí)行完畢后執(zhí)行V(S_i1)窗怒，使得S_i1=0映跟，并且P₁又進(jìn)入就緒隊(duì)列準(zhǔn)備執(zhí)行。P₁執(zhí)行完第二個(gè)P(S_i1)后扬虚，S_i1又等于-1且其自身又進(jìn)入等待隊(duì)列被阻塞努隙，直到下一個(gè)前驅(qū)進(jìn)程P_ik'執(zhí)行完畢后執(zhí)行V(S_i1)使其繼續(xù)運(yùn)行……如此循環(huán)往復(fù)，直到所有的這n個(gè)前驅(qū)進(jìn)程P_ik都執(zhí)行完畢辜昵，進(jìn)程P₁才能執(zhí)行它的后繼事務(wù)代碼荸镊，由此完成同步功能。

那么如何進(jìn)行合并呢堪置？第k節(jié)點(diǎn)的所有入邊都標(biāo)上semIn(k)的標(biāo)記躬存，所有出邊都標(biāo)上semOut(k)標(biāo)記。設(shè)第k個(gè)結(jié)點(diǎn)有numIn個(gè)入邊舀锨，有numOut個(gè)出邊岭洲，則其算法為：

T(k){
    P(semIn(k)) × numIn //表示依次執(zhí)行P(semIn(k))共numIn次
    do work
    V(semOut(k)) × numOut //表示依次執(zhí)行V(semIn(k))共numOut次
}

對(duì)于本題的圖：

它的信號(hào)量可以縮減為4個(gè)：

所以代碼如下：

semaphore
    S1,S2,S3,S4;
S1=S2=S3=S4=0;

T1{
    do work
    V(S1) × 2
}
T2{       
    P(S1)    
    do work 
    V(S3)
}
T3{       
    P(S1)    
    do work 
    V(S2)
}
T4{
    P(S3) × 2
    do work
    V(S4)
}
T5{
    P(S2)
    do work 
    V(S3)
    V(S4)
}
T6{
    P(S4) × 2
    do work
}

其執(zhí)行過(guò)程表如下，可見(jiàn)是保持了同步關(guān)系坎匿，并且信號(hào)量只需要四個(gè)而不是七個(gè)：

吃水果問(wèn)題（簡(jiǎn)單）

桌子上有一只盤(pán)子钦椭，盤(pán)子中只能放一只水果。爸爸專向盤(pán)子中放蘋(píng)果碑诉，媽媽專向盤(pán)子中放橘子彪腔，一個(gè)兒子專等吃盤(pán)子中的橘子，一個(gè)女兒專等吃盤(pán)子中的蘋(píng)果进栽。用PV 操作實(shí)現(xiàn)他們之間的同步機(jī)制德挣。

由于不能同時(shí)放蘋(píng)果和橘子，所以盤(pán)子是一個(gè)臨界資源快毛，而父親母親就是互斥關(guān)系格嗅。如果盤(pán)子中沒(méi)有水果時(shí)，兒子女兒是不能取水果的唠帝，所以父親母親和女兒兒子之間是同步關(guān)系屯掖。所以，思路如下：

• 父親母親對(duì)盤(pán)子信號(hào)量操作绍坝，獲得放水果的許可
• 父親（母親）放了水果后勤讽，發(fā)出私用信號(hào)量來(lái)通知女兒（兒子）取水果
• 女兒（兒子）取完水果后通知父親（母親）放水果，并釋放盤(pán)子資源

由于這個(gè)盤(pán)子中只能放一個(gè)水果妹懒，所以父親與女兒蔚万、母親與兒子之間各只需一個(gè)私用信號(hào)量。

這個(gè)題的核心思想在于其同步過(guò)程實(shí)現(xiàn)：父親與女兒是同步的肖方，父親鎖住的盤(pán)子只有女兒才能釋放猜憎。母親與兒子是同步的，母親鎖住的盤(pán)子只有兒子才能釋放辩越。而盤(pán)子的互斥信號(hào)量又是公用的欺旧。
這就保證了：父親放了水果后辞友，除非女兒進(jìn)程拿了水果并釋放盤(pán)子痴柔，否則其他進(jìn)程都要等待糯耍。即父親母親獲取不到盤(pán)子而等待革为，兒子因?yàn)楸P(pán)中沒(méi)有橘子的信號(hào)（母親沒(méi)有更改semOrange仍然是0）而陷入等待。

semaphore
    semPlate=1 //盤(pán)子的互斥信號(hào)量
    semApple=0, semOrange=0 //注意同步進(jìn)程的信號(hào)量初始值是0

//父親放蘋(píng)果
putApple(){
    //獲得盤(pán)子荒揣，它的釋放是在取蘋(píng)果進(jìn)程中進(jìn)行的
    //P(semPlate) 后篷角，除非女兒進(jìn)程去了蘋(píng)果釋放盤(pán)子
    //否則父親。母親系任、兒子三個(gè)進(jìn)程都取不到盤(pán)子
    P(semPlate) 
        放蘋(píng)果
        V(semApple) //通知女兒吃蘋(píng)果恳蹲，由于semApple初始值0嘉蕾，V原語(yǔ)后變?yōu)?
                    //此后霜旧，當(dāng)女兒還沒(méi)有取到蘋(píng)果并釋放盤(pán)子時(shí)掷倔，下一輪放蘋(píng)果
                    //操作會(huì)在P(semPlate)這一步被掛起等待
}

//女兒取蘋(píng)果
getApple(){
    //接收到取蘋(píng)果信號(hào)。該操作使得semApple從1又變?yōu)?
    //從而如果父親未放蘋(píng)果，semApple始終是0睡蟋，則在下一輪取蘋(píng)果操作時(shí)
    //在這一步被掛起等待
    P(semApple) 
        取蘋(píng)果
        V(semPlate) //釋放盤(pán)子資源
}

//取橘子和拿橘子進(jìn)程如法炮制
putOrange(){
    /*.......*/
}

getOrange(){
    /*.......*/
}

吃水果問(wèn)題（生產(chǎn)者-消費(fèi)者）

桌子上有一只盤(pán)子傍菇，盤(pán)子中最多放N個(gè)水果。爸爸專向盤(pán)子中放蘋(píng)果鲤屡，媽媽專向盤(pán)子中放橘子显拜，且每次只能放一個(gè)。兒子女兒每次可以拿一個(gè)水果來(lái)吃见芹。用PV 操作實(shí)現(xiàn)他們之間的同步機(jī)制惯吕。

這是上個(gè)吃水果問(wèn)題的一個(gè)變種混埠。它的變化是：

1. 盤(pán)子（緩沖區(qū)）的容量是N
2. 生產(chǎn)者生產(chǎn)的東西消費(fèi)者都可以使用，女兒可以吃蘋(píng)果橘子衬吆，兒子也可以。

在上個(gè)簡(jiǎn)單的吃水果問(wèn)題中，父親鎖住盤(pán)子后放了蘋(píng)果拇勃，當(dāng)且僅當(dāng)它的同步進(jìn)程——女兒進(jìn)程取完蘋(píng)果后釋放盤(pán)子資源四苇，否則其他所有進(jìn)程都會(huì)進(jìn)入等待。這就保證了父親女兒同步進(jìn)行方咆。

而在這個(gè)問(wèn)題中月腋，盤(pán)子可放的水果不止一個(gè)，生產(chǎn)者進(jìn)程鎖住盤(pán)子后放了水果峻呛，但是不應(yīng)該在消費(fèi)者進(jìn)程釋放盤(pán)子罗售，否則生產(chǎn)者放一個(gè)水果辜窑，當(dāng)且僅當(dāng)消費(fèi)者拿走后才能放下一個(gè)水果钩述，這樣盤(pán)子任意時(shí)刻至多只能有一個(gè)水果，這顯然是不合理的穆碎。無(wú)論是生產(chǎn)者還是消費(fèi)者牙勘，在對(duì)盤(pán)子操作之前一個(gè)鎖住盤(pán)子，而在操作完成后要自己釋放盤(pán)子佑钾。

盤(pán)子設(shè)置一個(gè)互斥信號(hào)量semPlate=1牍戚，由于盤(pán)子最多可以放N個(gè)水果眯搭，所以信號(hào)量要增設(shè)兩個(gè)：目前可以取多少個(gè)水果semEnableGet，以及目前有多少個(gè)空位可以放水果semEnablePut恭金。初始時(shí)，有N個(gè)位置可以放水果褂策，而有0個(gè)水果可以取横腿，所以初始值semEnableGet=0，semEnablePut=N斤寂。
對(duì)這兩個(gè)信號(hào)量的操作是這樣的：

1. 生產(chǎn)者檢測(cè)是否可以放水果（P(semEnablePut)）耿焊。如果可以就放（semEnablePut也就減少一個(gè)空位），否則要等待空位遍搞。
2. 得到放置許可后罗侯，生產(chǎn)者要鎖住盤(pán)子（P(semPlate)）
3. 然后放水果
4. 生產(chǎn)者釋放盤(pán)子（V(semPlate)），并且通知可以取水果了（V(semEnableGet)后semEnableGet自增1溪猿，表示多一個(gè)水果可裙辰堋）

1. 消費(fèi)者檢測(cè)是否有水果可以取（P(semEnableGet)）诊县。如果可以就冉才（semEnableGet也就減少一個(gè)水果），否則要等待水果翎冲。
2. 得到放置許可后垂睬，消費(fèi)者要鎖住盤(pán)子（P(semPlate)）
3. 然后取水果
4. 消費(fèi)者釋放盤(pán)子（V(semPlate)），并且通知可以放水果了（V(semEnablePut)后semEnablePut自增1，表示多一個(gè)空位可以放水果）

注意驹饺，V原語(yǔ)次序可以任意钳枕，但是P原語(yǔ)順序不能亂，否則可能會(huì)引發(fā)死鎖赏壹。

哲學(xué)家問(wèn)題：

假設(shè)有五位哲學(xué)家圍坐在一張圓形餐桌旁鱼炒，做以下兩件事情之一：吃飯，或者思考蝌借。吃東西的時(shí)候昔瞧，他們就停止思考，思考的時(shí)候也停止吃東西菩佑。餐桌中間有一大碗意大利面自晰，每?jī)蓚€(gè)哲學(xué)家之間有一只筷子，哲學(xué)家必須用兩只筷子吃東西稍坯。他們只能使用自己左右手邊的那兩只筷子酬荞。條件是：
1. 只有拿到左右兩只筷子才吃飯
2. 如果筷子在別人手上，必須等他人吃完后才能拿筷子
3. 在未拿到兩只筷子吃飯前瞧哟，絕對(duì)不會(huì)放下自己手中的筷子

描述一個(gè)保證不會(huì)有兩個(gè)相鄰的人同時(shí)要求吃飯的通信算法是簡(jiǎn)單的：

semaphore 
    chopstick[0]~chopstick[4]=1    //5根筷子的互斥信號(hào)量
philosopher(i){  //第i個(gè)哲學(xué)家進(jìn)程
    P(chopstick[i]); //拿左邊的筷子
        P(chopstick[i+4 mod 5])  //拿右邊的筷子混巧，注意mod的使用
            吃飯
        V(chopstick[i+4 mod 5])  //放下右邊的筷子
    V(chopstick[i]); //放下左邊的筷子
}

盡管這個(gè)算法是簡(jiǎn)單的，但是它有一個(gè)潛在的隱患：可能會(huì)引發(fā)死鎖勤揩。假設(shè)5個(gè)哲學(xué)家同時(shí)拿起左手邊的筷子咧党，但是都沒(méi)有右邊的筷子，且根據(jù)題意陨亡，他們都不會(huì)放下自己的筷子傍衡，從而沒(méi)有人能吃飯。

為了避免死鎖数苫，改進(jìn)上述算法聪舒。因?yàn)樗腥硕家饶米约鹤笫诌叺目曜樱@樣可能每個(gè)人手中都恰好有一根筷子虐急，這是引發(fā)死鎖的關(guān)鍵箱残。
自然想到，如果兩個(gè)相鄰的哲學(xué)家都首先取第一根筷子既可避免止吁。讓偶數(shù)編號(hào)的哲學(xué)家先拿左手邊的筷子（第i個(gè)哲學(xué)家拿第i個(gè)筷子）而讓奇數(shù)編號(hào)的哲學(xué)家拿右手邊的筷子（第i個(gè)哲學(xué)家拿第 (i+4)mod5 個(gè)筷子）：

先拿的筷子

這樣被辑，任何一個(gè)哲學(xué)家拿到一根筷子時(shí)，就會(huì)阻止他相鄰的哲學(xué)家拿到該筷子敬惦，這名哲學(xué)家從而只能等待：

semaphore 
    chopstick[0]~chopstick[4]=1    //5根筷子的互斥信號(hào)量
philosopher(i){  //第i個(gè)哲學(xué)家進(jìn)程
    if(i是偶數(shù))
        P(chopstick[i]); //拿左邊的筷子
            P(chopstick[i+4 mod 5])  //拿右邊的筷子盼理，注意mod的使用
                吃飯
            V(chopstick[i+4 mod 5])  //放下右邊的筷子
        V(chopstick[i]); //放下左邊的筷子
    else
        P(chopstick[i+4 mod 5]); //拿右邊的筷子
            P(chopstick[i])  //拿左邊的筷子
                吃飯
            V(chopstick[i+4 mod 5])  //放下右邊的筷子
        V(chopstick[i]); //放下左邊的筷子
}

讀卡機(jī)問(wèn)題

讀卡機(jī)上讀卡片。這一項(xiàng)工作由三個(gè)進(jìn)程get俄删，copy和put以及兩個(gè)緩沖區(qū)buffer1和 buffer2 完成宏怔。進(jìn)程get的功能是把一張卡片上的信息從讀卡機(jī)上讀進(jìn)buffer1奏路；進(jìn)程copy的功能是把buffer1中的信息復(fù)制到buffer2；進(jìn)程put的功能是取出buffer2中的信息并從行式打印機(jī)上打印輸出臊诊。

這是一個(gè)同步問(wèn)題鸽粉。有一個(gè)錯(cuò)誤的解法是這樣的：

因?yàn)間et和copy、copy和put之間都是同步關(guān)系抓艳。如果buffer1中g(shù)et沒(méi)有放入數(shù)據(jù)触机，copy是取不到數(shù)據(jù)的，只能等待玷或。對(duì)于buffer2也同理儡首。所以：

//錯(cuò)誤做法： ERROR SOLUTION
semaphore
    enable1=0,enable2=0; //兩個(gè)緩沖區(qū)是否可以放入數(shù)據(jù)
get{
    放入數(shù)據(jù);
    V(enable1)
}
copy{
    P(enable1)
        取數(shù)據(jù)
        放入buffer2
        V(enable2)
}
put{
    P(enable2)
    取數(shù)據(jù)
}

乍一看似乎是合理有效的：一開(kāi)始都沒(méi)有數(shù)據(jù)，enable1和enable2都是0偏友，copy在運(yùn)行 P(enable1)時(shí)會(huì)進(jìn)入等待蔬胯，put在運(yùn)行P(enable2)也會(huì)進(jìn)入等待。直到get放入數(shù)據(jù)并執(zhí)行 V(enable1)時(shí)约谈，copy才被激活笔宿，然后copy執(zhí)行 V(enable2)時(shí)，put才被激活取數(shù)據(jù)棱诱。此后get不再放入數(shù)據(jù)，copy和put繼續(xù)等待涝动，如此往復(fù)迈勋。

但是這里有一個(gè)重大隱患，那就是沒(méi)有考慮到兩個(gè)緩沖區(qū)是臨界資源沒(méi)有被保護(hù)醋粟。你可能會(huì)想靡菇，get和copy是同步關(guān)系而 不是互斥關(guān)系 ，如果get不通知copy來(lái)去數(shù)據(jù)米愿，那么copy就會(huì)在P(enable1)這一步時(shí)陷入等待厦凤，根本不會(huì)訪問(wèn)buffer1，似乎臨界資源不產(chǎn)生沖突育苟。

但是恰恰忽略的一點(diǎn)是较鼓，copy在取數(shù)據(jù)時(shí)，因?yàn)閎uffer1沒(méi)有被保護(hù)而使得copy也在往里面填充數(shù)據(jù)违柏。這就會(huì)引發(fā)臟數(shù)據(jù)博烂。所以盡管時(shí)同步，也要對(duì)臨界資源進(jìn)行互斥：

semaphore
    enable1=0,enable2=0, //兩個(gè)緩沖區(qū)是否可以放入數(shù)據(jù)
    bufMutex1=1,bufMutex2=1; //兩個(gè)緩沖區(qū)的互斥信號(hào)量
get{
    P(bufMutex1)
        放入數(shù)據(jù);
    V(bufMutex1)

    V(enable1)
}
copy{
    P(enable1)
        P(bufMutex1)
            取數(shù)據(jù)
        V(bufMutex1)

        P(bufMutex2)
            放入buffer2
        V(bufMutex2)

        V(enable2)
}
put{
    P(enable2)
    
    P(bufMutex2)
        取數(shù)據(jù)
    V(bufMutex2)
}

這樣在copy取buffer1中數(shù)據(jù)時(shí)漱竖，get需要等待而不能放入數(shù)據(jù)禽篱。

注意到，enable1這個(gè)信號(hào)量在這里僅表示能否裝入馍惹，所以只適合表示緩沖區(qū)僅能放置一份數(shù)據(jù)的情況躺率。
但是假如是一個(gè)緩沖隊(duì)列玛界，里面可以放置N份數(shù)據(jù)，那么只使用enable1就明顯不夠了悼吱，為此需要設(shè)置兩個(gè)信號(hào)量：

• 當(dāng)前還能放多少數(shù)據(jù)：enablePutData=N（相當(dāng)于empty）
• 當(dāng)前有多少份數(shù)據(jù)可以冉抛小：enableGetData=0（相當(dāng)于full）

enablePutData初始值是N，表示剛開(kāi)始可以放N份數(shù)據(jù)舆绎；enableGetData初始值是0鲤脏，表示剛開(kāi)始沒(méi)有數(shù)據(jù)可以取：

• 每放一份數(shù)據(jù)后吕朵，執(zhí)行P(enablePutData)來(lái)使enablePutData自減1猎醇，表示少一個(gè)單元可放數(shù)據(jù)，如果enablePutData等于0努溃，表示沒(méi)有單元可以放數(shù)據(jù)硫嘶，則生產(chǎn)者需要等待。
  放完數(shù)據(jù)后梧税，需要執(zhí)行V(enableGetData)來(lái)使enableGetData自增1沦疾，表示緩沖區(qū)多一個(gè)數(shù)據(jù)可取，就是剛剛放入的那一份第队。
• 每取一份數(shù)據(jù)后哮塞，執(zhí)行P(enableGetData)來(lái)使enableGetData自減1，表示少一個(gè)數(shù)據(jù)可取凳谦，就是剛剛?cè)×说哪且环菀涑绻鹐nableGetData等于0，表示沒(méi)有數(shù)據(jù)可取尸执，則消費(fèi)者需要等待家凯。
  取完數(shù)據(jù)后，需要執(zhí)行V(enablePutData)來(lái)使enablePutData自增1如失，表示緩沖區(qū)多一個(gè)空位可以放數(shù)據(jù)绊诲。

所以拓展后可以寫(xiě)為：

semaphore
    enablePutData1=N,enablePutData2=N,
    enableGetData1=0,enableGetData2=0,
    bufMutex1=1,bufMutex2=1; //兩個(gè)緩沖區(qū)的互斥信號(hào)量
get{
    //先測(cè)試能否放數(shù)據(jù)再互斥臨界區(qū)，P原語(yǔ)順序錯(cuò)亂可能會(huì)引發(fā)死鎖
    P(enablePutData1)
        P(bufMutex1)
            放入數(shù)據(jù);
        V(bufMutex1)
    V(enableGetData1)
}
copy{
    P(enableGetData1) //測(cè)試buffer1能不能取數(shù)據(jù)
        P(bufMutex1)
            取數(shù)據(jù)
        V(bufMutex1)
    V(enablePutData1)

    //測(cè)試buffer2能不能放數(shù)據(jù)
    P(enablePutData2)
        P(bufMutex2)
            放入buffer2
        V(bufMutex2)
     V(enableGetData2)
}
put{
    //測(cè)試buffer2能不能取數(shù)據(jù)
    P(enableGetData2)
        P(bufMutex2)
            取數(shù)據(jù)
        V(bufMutex2)
     V(enablePutData2)
}

如果N=1就是本題的情況褪贵，測(cè)試enable信號(hào)量可以減少為1個(gè)掂之。

游覽車(chē)問(wèn)題

已知風(fēng)景區(qū)內(nèi)的轎車(chē)總量為M輛，游客總數(shù)為N竭鞍，約定：
（1）每輛轎車(chē)限乘一位游客板惑；
（2）如果有空閑的轎車(chē)，應(yīng)當(dāng)允許想游覽的游客乘坐偎快；
（3）無(wú)空閑轎車(chē)時(shí)冯乘，游客只能排隊(duì)等待；
（4）若沒(méi)有想游覽的游客晒夹，空閑的轎車(chē)也要等待裆馒。

顯然存在一個(gè)轎車(chē)進(jìn)程Car()和游客進(jìn)程Passager()姊氓。題目中的M、N在這里并不是想要告訴你車(chē)數(shù)和人數(shù)喷好，而是想告訴你車(chē)輛數(shù)目和游客數(shù)目是固定的翔横。這里的“固定”指游客游覽完可以繼續(xù)游覽，轎車(chē)游覽完可以繼續(xù)拉客梗搅。所以禾唁，本題的相關(guān)信號(hào)量的值和M、N都沒(méi)有關(guān)系无切！荡短。

這道題巧用了信號(hào)量和等待機(jī)制。首先用自然語(yǔ)言表述出這兩個(gè)進(jìn)程要干什么哆键。

對(duì)于轎車(chē)進(jìn)程Car()掘托，每當(dāng)它運(yùn)行時(shí)：

1. 可用轎車(chē)數(shù)目加1，通知（喚醒）等待的游客籍嘹。
2. 在游客進(jìn)程沒(méi)有發(fā)出發(fā)信號(hào)表明上車(chē)可以出發(fā)之前闪盔，轎車(chē)是在等待狀態(tài)。
3. 帶上乘客游覽辱士，在這一段時(shí)間內(nèi)泪掀，游客進(jìn)程什么也不做，從而處于等待狀態(tài)
4. 發(fā)出游覽完成信號(hào)识补，通知（喚醒）乘客下車(chē)
5. 在接收到游客下車(chē)完成信號(hào)之前族淮，一直等待游客下車(chē)。然后返回第一步凭涂。

對(duì)于游客進(jìn)程Passager()，每當(dāng)它運(yùn)行時(shí)：

1. 檢查是否有可用轎車(chē)（轎車(chē)有可用信號(hào)）贴妻，如果有則選定一個(gè)轎車(chē)切油，否則等待
2. 開(kāi)始上車(chē)，在這個(gè)過(guò)程中名惩，轎車(chē)進(jìn)程等待
3. 上車(chē)后澎胡，發(fā)出開(kāi)車(chē)信號(hào)，喚醒轎車(chē)進(jìn)程出發(fā)
4. 游覽過(guò)程中游客不需要做什么娩鹉，這就是處于等待狀態(tài)攻谁，需要轎車(chē)進(jìn)程發(fā)出游覽完成信號(hào)后，游客進(jìn)程才從等待狀態(tài)喚醒弯予，執(zhí)行下一步
5. 游客下車(chē)戚宦，在此過(guò)程中，轎車(chē)進(jìn)程等待
6. 下車(chē)完成后锈嫩，發(fā)出下車(chē)完成信號(hào)受楼，本次游覽結(jié)束垦搬，游客繼續(xù)返回第一步準(zhǔn)備游覽。

虛線代表等待狀態(tài)艳汽，圓角框代表運(yùn)行狀態(tài)

上述描述中可以學(xué)到如下技巧：

1. A進(jìn)程與B進(jìn)程交互運(yùn)行時(shí)猴贰，當(dāng)某個(gè)操作要在A進(jìn)程完成，此間B進(jìn)程陷入等待河狐，直到A進(jìn)程完成后發(fā)出信號(hào)激活B進(jìn)程米绕。為此，設(shè)置一個(gè)信號(hào)量semaphore=0馋艺，B中執(zhí)行P(semaphore)使得B等待栅干，而當(dāng)A完成操作后，執(zhí)行V(semaphore)來(lái)喚醒B進(jìn)程丈钙，因?yàn)锽進(jìn)程掛在semaphore的等待隊(duì)列中非驮。
2. 游客進(jìn)程通過(guò)對(duì)可用車(chē)數(shù)semEnableCar進(jìn)行P操作后，如果沒(méi)有可用的轎車(chē)雏赦，就掛入該信號(hào)量等待隊(duì)列中劫笙。而后無(wú)論來(lái)多少輛車(chē)，因?yàn)檐?chē)要聲明可用車(chē)數(shù)加1星岗，也就是執(zhí)行V操作填大，這就會(huì)喚醒semEnableCar等待隊(duì)列中的游客進(jìn)程，讓游客上車(chē)俏橘。
   反過(guò)來(lái)說(shuō)允华，如果轎車(chē)進(jìn)程執(zhí)行V操作后，如果沒(méi)有游客進(jìn)程寥掐，那么就不可能收到開(kāi)車(chē)信號(hào)靴寂，也就會(huì)陷入等待中。
   所以召耘，semEnableCar的初始值就是0百炬，而不是M或者N什么的。當(dāng)沒(méi)有一個(gè)車(chē)時(shí)污它，游客的P(semEnableCar)才能導(dǎo)致游客等待剖踊。

semaphore
    semEnableCar=0,   //可用車(chē)數(shù)目信號(hào)量
    semCanStart=0,    //可以開(kāi)車(chē)信號(hào)量
    semFinish=0,    //游覽完成信號(hào)量
    semHasTakenOff=0    //游客已經(jīng)下車(chē)信號(hào)量

Car(){
    V(semEnableCar)  //可用車(chē)+1，通知等待的游客
    P(semCanStart) //等待游客的“可以出發(fā)”信號(hào)
        開(kāi)始游覽衫贬，在這個(gè)過(guò)程中德澈，游客正在等待，也就是阻塞狀態(tài)
    V(semFinish)  //向游客進(jìn)程發(fā)出游覽完成信號(hào)
    P(semHasTakenOff)   //等待游客的“已經(jīng)下車(chē)”信號(hào)
    Car() //循環(huán)運(yùn)行
}

Passager(){
    P(semEnableCar)  //等待有可用車(chē)
        上車(chē)固惯，此時(shí)轎車(chē)等待
    V(semCanStart) //發(fā)出“可以出發(fā)”信號(hào)
    P(Finish)  //在收到轎車(chē)“游覽完成”信號(hào)之前梆造，進(jìn)入阻塞狀態(tài)，表示“正在游覽”
        游客開(kāi)始下車(chē)缝呕，此間轎車(chē)正在等待
    V(semHasTakenOff)   //游客“已經(jīng)下車(chē)”信號(hào)給轎車(chē)澳窑，激活轎車(chē)
    Passager() //循環(huán)運(yùn)行
}

理發(fā)問(wèn)題

有一個(gè)理發(fā)師斧散，一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子。如果沒(méi)有顧客摊聋，則理發(fā)師等待鸡捐；當(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)條件歇僧。

這是一個(gè)比較復(fù)雜的進(jìn)程同步問(wèn)題。需要設(shè)計(jì)兩個(gè)進(jìn)程：

• 顧客進(jìn)程Customer()
• 理發(fā)師進(jìn)程Barber()

需要注意到锋拖，在顧客與理發(fā)師發(fā)生同步交互之前诈悍，顧客需要先判斷是否需要等待（這個(gè)過(guò)程，理發(fā)師進(jìn)程不需要介入）兽埃。其邏輯如下：

等待過(guò)程

那么如何做呢尚揣？可以設(shè)置一個(gè)變量waitingNumbers涌矢，當(dāng)一個(gè)顧客來(lái)到時(shí)先判斷等待人數(shù)waitingNumbers是否超過(guò)可等待人數(shù)N，如果是則離開(kāi)（即顧客進(jìn)程結(jié)束）快骗，否則waitingNumbers++娜庇，顧客準(zhǔn)備等待。顯然方篮，所有顧客都要對(duì)waitingNumbers操作名秀，從而waitingNumbers也就成為一個(gè)臨界資源，為此要進(jìn)行保護(hù)藕溅，故而設(shè)置互斥量semWaitingNumbersMutex=1匕得，因?yàn)橥粫r(shí)間至多只能由一個(gè)顧客進(jìn)行操作。

現(xiàn)在如果顧客進(jìn)程還沒(méi)有退出巾表，那么他就要與理發(fā)師進(jìn)程發(fā)生交互汁掠。

進(jìn)程交互階段

注意，在這一階段有兩個(gè)關(guān)鍵的等待過(guò)程攒发。當(dāng)顧客尚未到來(lái)或者還沒(méi)有發(fā)出準(zhǔn)備理發(fā)的信號(hào)之前调塌，理發(fā)師是在等待的。另一方面惠猿，如果客戶沒(méi)有離開(kāi)羔砾，而理發(fā)師沒(méi)有對(duì)其發(fā)出可以理發(fā)信號(hào)時(shí)，客戶就需要等待偶妖，這個(gè)等待就是題目中“坐在等待區(qū)椅子上”的等待情況姜凄。

也就是說(shuō)，顧客發(fā)信號(hào)喚醒等待的理發(fā)師趾访，理發(fā)師發(fā)信號(hào)喚醒等待的顧客（★★★核心思想）

針對(duì)理發(fā)師的等待态秧，可以設(shè)置一個(gè)信號(hào)量semCustomers=0。理發(fā)師對(duì)其進(jìn)行P操作（wait）扼鞋，使得semCustomers為-1申鱼，從而理發(fā)師進(jìn)入等待。直到顧客對(duì)其進(jìn)行V（signal）操作云头，使得semCustomers為0捐友，重新喚醒理發(fā)師進(jìn)程。

這就又引發(fā)一個(gè)問(wèn)題：如果第二個(gè)顧客溃槐、第三個(gè)……第K個(gè)顧客依次到來(lái)（且沒(méi)有離開(kāi)匣砖，K≤N），那么他們每個(gè)人都要進(jìn)行V(semCustomers)操作，因?yàn)榈谝粋€(gè)顧客操作后semCustomers等于0猴鲫，那么后續(xù)這K人的V操作將會(huì)使得semCustomers等于K对人，并且因?yàn)闆](méi)有等待進(jìn)程（針對(duì)信號(hào)量semCustomers的唯一可以等待的只有理發(fā)師進(jìn)程），所以這些顧客進(jìn)程將繼續(xù)后續(xù)操作拂共∥【V原語(yǔ)妙用】

在后續(xù)操作中必須使這些人陷入等待，設(shè)置一個(gè)信號(hào)量semBarber=0匣缘。所有人在V(semCustomers)后必須進(jìn)行P(semBarber)猖闪，即等待理發(fā)師發(fā)出可以理發(fā)通知，即等待理發(fā)師的V(semBarber)操作肌厨。第一個(gè)顧客在收到理發(fā)師通知進(jìn)行理發(fā)時(shí)培慌，semBarber又重新歸零，這樣后來(lái)的K個(gè)人對(duì)其P操作后使得semBarber等于-1柑爸、-2吵护、……、-K表鳍，這K個(gè)人也就進(jìn)入了等待馅而。

現(xiàn)在，論證上述過(guò)程的可持續(xù)性：當(dāng)?shù)谝晃活櫩碗x開(kāi)后譬圣，理發(fā)師進(jìn)程又重新進(jìn)行P(semCustomers)操作瓮恭，因?yàn)榇藭r(shí)semCustomers為K，所以理發(fā)師不會(huì)等待厘熟，而是繼續(xù)執(zhí)行屯蹦。理發(fā)師接下來(lái)執(zhí)行V(semBarber)喚醒顧客，由于semBarber為-K绳姨，K個(gè)人都掛在semBarber信號(hào)量的等待隊(duì)列中登澜，所以任選一個(gè)喚醒，進(jìn)行理發(fā)飘庄。由此可以循環(huán)執(zhí)行脑蠕。

int waitingNumbers=0;  //等待的顧客
semaphore
    semWaitingNumbersMutex=1,
    semBarber=0,
    semCustomers=0,
    semCut=0,  //可以開(kāi)始理發(fā)
    semFinish=0,  //理發(fā)完成

Customer(){
    P(semWaitingNumbersMutex)
        if(waitingNumbers>N)
            V(semWaitingNumbersMutex)  //此后，進(jìn)程結(jié)束跪削，表示離開(kāi)
        else{
            waitingNumbers++;
            V(semWaitingNumbersMutex);

            V(semCustomers);  //通知理發(fā)師有顧客
            P(semBarber)//等待理發(fā)師通知
            
            //接到了通知谴仙，就坐理發(fā)，注意等待座位要空出來(lái)
            P(semWaitingNumbersMutex)
                waitingNumbers--;
            V(semWaitingNumbersMutex)

            //告訴理發(fā)師可以開(kāi)始理發(fā)
            V(semCut)
            //等待理發(fā)完成信號(hào)
            P(semFinish)
        }
}

Barber(){
    P(semCustomers)  //等待顧客到來(lái)
    V(semBarbers)  //喚醒等待的顧客
    P(semCut)  //等待顧客可以開(kāi)始理發(fā)信號(hào)
        //理發(fā)
    V(semFinish)  //理發(fā)完成
}

實(shí)際上可以推廣為M個(gè)理發(fā)師理發(fā)碾盐，而執(zhí)行代碼并不發(fā)生變化狞甚。這是因?yàn)樵谙到y(tǒng)中運(yùn)行著M個(gè)Barber()進(jìn)程，它們剛開(kāi)始都執(zhí)行第一個(gè)P(semCustomers)語(yǔ)句而陷入等待廓旬，直到有顧客到來(lái)執(zhí)行V(semCustomers)而喚醒任意一個(gè)理發(fā)師理發(fā)。任意一個(gè)理完頭發(fā)的理發(fā)師發(fā)信號(hào)來(lái)喚醒下一個(gè)等待的顧客。

上機(jī)問(wèn)題

某高校計(jì)算機(jī)系開(kāi)設(shè)有網(wǎng)絡(luò)課并安排了上機(jī)實(shí)習(xí)孕豹，假設(shè)機(jī)房共有2m臺(tái)機(jī)器涩盾，有2n 名學(xué)生選該課，規(guī)定：
① 每?jī)蓚€(gè)學(xué)生組成一組励背，各占一臺(tái)機(jī)器春霍，協(xié)同完成上機(jī)實(shí)習(xí)；
② 只有一組的兩個(gè)學(xué)生到齊叶眉，并且此時(shí)機(jī)房有空閑機(jī)器時(shí)址儒，該組學(xué)生才能進(jìn)入機(jī)房；
③ 上機(jī)實(shí)習(xí)由一名教師檢查衅疙，檢查完畢莲趣，一組學(xué)生同時(shí)離開(kāi)機(jī)房。
試用P饱溢、V操作模擬上機(jī)實(shí)習(xí)過(guò)程喧伞。

在這里，除了學(xué)生進(jìn)程Student()和教師進(jìn)程Teacher()之外绩郎，還應(yīng)該有一個(gè)進(jìn)程潘鲫，用以實(shí)現(xiàn)第一個(gè)約束條件——即兩個(gè)學(xué)生到齊后才允許進(jìn)入，不妨將該進(jìn)程命名為Monitor()肋杖。顯然教師進(jìn)程不具有此功能溉仑，它只是用來(lái)完成第三約束條件，即“檢查”功能状植。

可以設(shè)置一個(gè)信號(hào)量semStudent=0浊竟，當(dāng)來(lái)一個(gè)學(xué)生時(shí)執(zhí)行V操作，通知Monitor浅萧，而Monitor執(zhí)行P操作來(lái)接收通知信號(hào)量逐沙。為了實(shí)現(xiàn)“兩個(gè)學(xué)生到齊才能進(jìn)去”，Monitor需要執(zhí)行兩次P(semStudent)洼畅，然后才發(fā)出兩次允許進(jìn)入信號(hào)——分別給兩個(gè)申請(qǐng)進(jìn)入的學(xué)生使用吩案。其核心的步驟是：

1. 初始，semStudent=0,
2. Monitor執(zhí)行第一個(gè)P(semStudent) => semStudent=-1帝簇，陷入等待
3. 第一個(gè)學(xué)生執(zhí)行V(semStudent) => semStudent=0徘郭，喚醒Monitor，該學(xué)生等待接收可進(jìn)入信號(hào)丧肴。
4. Monitor執(zhí)行第二個(gè)P(semStudent) => semStudent=-1残揉，陷入等待
5. 第二個(gè)學(xué)生執(zhí)行V(semStudent) => semStudent=0，喚醒Monitor芋浮，該學(xué)生等待接收可進(jìn)入信號(hào)抱环。
6. Monitor繼續(xù)執(zhí)行，分別執(zhí)行兩次V(semEnter) => 兩個(gè)等待的學(xué)生接收到信號(hào)，進(jìn)入镇草。

后面的步驟就很簡(jiǎn)單了眶痰，因?yàn)楸仨氂锌臻e的電腦，否則學(xué)生等待梯啤，因?yàn)殡娔X總數(shù)固定竖伯，所以可以設(shè)置一個(gè)電腦的信號(hào)量semComputer=2M。教師和學(xué)生進(jìn)程之間是互相同步的關(guān)系因宇。

BEGIN
    Semaphore： 
        semStudent=0, semComputer=2M ,semEnter=0, semFinish=0, semCheck=0;
COBEGIN
    Process Procedure  semStudent()
    begin
        V(semStudent);                  // 表示有學(xué)生到達(dá)
        P(semComputer);                 // 等待獲取一臺(tái)計(jì)算機(jī)
        P(semEnter);                        // 等待進(jìn)入許可
            DO it with partner();
        V(semFinish);                       // 實(shí)習(xí)完成
        P(semCheck);                        // 等待老師檢查
        V(semComputer):                 // 釋放計(jì)算機(jī)資源
    end

Process Procedure Teacher()
    begin
        P(semFinished);                 // 等待學(xué)生實(shí)習(xí)完成
        P(semFinished);                 // 等待另一學(xué)生實(shí)習(xí)完成
            check the work();
        V(semCheck);                        // 表示檢查完成
        V(semCheck);                        // 表示檢查完成
    end

Process Procedure Monitor()
    begin
        P(semStudent);                      // 等待學(xué)生到達(dá)
        P(semStudent);                  // 等待另一學(xué)生到達(dá)
        V(semEnter);                        // 允許學(xué)生進(jìn)入
        V(semEnter);                        // 允許學(xué)生進(jìn)入
    end
    
Coend
END