轉(zhuǎn)自：http://www.cnblogs.com/whatbeg/p/4435286.html

現(xiàn)代操作系統(tǒng)采用多道程序設(shè)計(jì)機(jī)制，多個(gè)進(jìn)程可以并發(fā)執(zhí)行，CPU在進(jìn)程之間來回切換，共享某些資源，提高了資源的利用率，但這也使得處理并發(fā)執(zhí)行的多個(gè)進(jìn)程之間的沖突和相互制約關(guān)系成為了一道難題。如果對(duì)并發(fā)進(jìn)程的調(diào)度不當(dāng)，則可能會(huì)出現(xiàn)運(yùn)行結(jié)果與切換時(shí)間有關(guān)的情況，令結(jié)果不可再現(xiàn)，影響系統(tǒng)的效率和正確性，嚴(yán)重時(shí)還會(huì)使系統(tǒng)直接崩潰。就比如你只有一臺(tái)打印機(jī)，有兩個(gè)進(jìn)程都需要打印文件，如果直接讓他們簡(jiǎn)單地并發(fā)訪問打印機(jī)，那么你很可能什么都打印不出來或者打印的文件是...anyway，我們需要增加一些機(jī)制來控制并發(fā)進(jìn)程間的這種相互制約關(guān)系。

? ??進(jìn)程間通信的很多問題的根本原因是我們不知道進(jìn)程何時(shí)切換。

? ?概念

? ? 首先我們了解一下臨界資源與臨界區(qū)的概念：臨界資源就是一次只允許一個(gè)進(jìn)程訪問的資源，一個(gè)進(jìn)程在使用臨界資源的時(shí)候，另一個(gè)進(jìn)程是無法訪問的，操作系統(tǒng)也不能夠中途剝奪正在使用者的使用權(quán)利，正所謂“潑出去的女兒嫁出去的水”是也。即臨界資源是不可剝奪性資源。那么臨界區(qū)呢？所謂臨界區(qū)就是進(jìn)程中范文臨界資源的那段程序代碼，注意，是程序代碼，不是內(nèi)存資源了，這就是臨界資源與臨界區(qū)的區(qū)別。我們規(guī)定臨界區(qū)的使用原則（也即同步機(jī)制應(yīng)遵循的準(zhǔn)則）十六字訣：“空閑讓進(jìn)，忙則等待，有限等待，讓權(quán)等待”--strling。讓我們分別來解釋一下：

（1）空閑讓進(jìn)：臨界資源空閑時(shí)一定要讓進(jìn)程進(jìn)入，不發(fā)生“互斥禮讓”行為。

（2）忙則等待：臨界資源正在使用時(shí)外面的進(jìn)程等待。

（3）有限等待：進(jìn)程等待進(jìn)入臨界區(qū)的時(shí)間是有限的，不會(huì)發(fā)生“餓死”的情況。

（4）讓權(quán)等待：進(jìn)程等待進(jìn)入臨界區(qū)是應(yīng)該放棄CPU的使用。

??? 好了，我們進(jìn)入下一部分。

? ? 進(jìn)程間通常存在著兩種制約關(guān)系：直接制約關(guān)系和間接制約關(guān)系，就是我們通常所說的進(jìn)程的同步與互斥。顧名思義，一個(gè)是合作關(guān)系，一個(gè)是互斥關(guān)系。進(jìn)程互斥說白了就是“你用的時(shí)候別人都不能用，別人用的時(shí)候，你也不能去用”，是一種源于資源共享的間接制約關(guān)系。進(jìn)程同步指的是“我們大家利用一些共同的資源區(qū)，大家一起合作，完成某些事情，但是我在干某些小事的時(shí)候，可能要等到你做完另一些小事”，是一種源于相互合作的直接制約關(guān)系。兩者區(qū)別在于互斥的進(jìn)程間沒有必然的聯(lián)系，屬于競(jìng)爭(zhēng)者關(guān)系，誰競(jìng)爭(zhēng)到資源（的使用權(quán)），誰就使用它，直到使用完才歸還。就比如洗衣房的洗衣機(jī)這個(gè)資源，去洗衣的同學(xué)并不需要有必然聯(lián)系，你們可以互不認(rèn)識(shí)，但是誰競(jìng)爭(zhēng)到洗衣機(jī)的使用權(quán)，就可以使用，直到洗完走人。而同步的進(jìn)程間是有必然聯(lián)系的，即使競(jìng)爭(zhēng)到使用權(quán)，如果合作者沒有發(fā)出必要的信息，該進(jìn)程依然不能執(zhí)行。就比如排隊(duì)打水，即使排到你了，如果水箱沒水了，你就打不了水，說明你和水箱是有著必然聯(lián)系的，你得從它里面取水，你們是同步關(guān)系，你們合作完成“打水”這個(gè)過程。

? ? 那么先來討論如何實(shí)現(xiàn)進(jìn)程的互斥控制。有下列幾種方法：嚴(yán)格輪換（每個(gè)進(jìn)程每次都從頭執(zhí)行到尾，效率不高，可能等待很久），屏蔽中斷（剛剛進(jìn)入臨界區(qū)時(shí)就屏蔽中斷，剛要出臨界區(qū)就打開中斷），專用機(jī)器指令test_and_set,test_and_clear，加鎖，軟件方法，信號(hào)量機(jī)制。講一下加鎖和軟件方法，加鎖方法如下：設(shè)置一個(gè)鎖標(biāo)志K表示臨界資源的狀態(tài)，K=1表示臨界資源正在被使用，K=0表示沒有進(jìn)程在訪問臨界資源。如果一個(gè)進(jìn)程需要訪問臨界資源，那么先檢查鎖標(biāo)志K：

if K == 1, 循環(huán)檢測(cè)，直到K = 0else if K == 0，設(shè)置鎖標(biāo)志為1，進(jìn)入臨界區(qū)

離開臨界區(qū)時(shí)設(shè)置鎖標(biāo)志K為0. 軟件方法類似，如愛斯基摩人的小屋協(xié)議，愛斯基摩人的小屋很小，每次只能容納一個(gè)人進(jìn)入，小屋內(nèi)有一個(gè)黑板，上面標(biāo)志這能夠進(jìn)入臨界區(qū)的進(jìn)程。若進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)，則先進(jìn)入小屋檢查黑板標(biāo)志，如果是自己，那么離開小屋進(jìn)入臨界區(qū)，執(zhí)行完后進(jìn)入小屋修改黑板標(biāo)志為其他進(jìn)程，離開小屋。如果小屋黑板標(biāo)志不是自己，那么反復(fù)進(jìn)入小屋考察黑板標(biāo)志是不是自己。這兩種方法都實(shí)現(xiàn)了互斥訪問，但是都違反了四條原則之一：讓權(quán)等待，都需要不斷的循環(huán)重復(fù)檢測(cè)標(biāo)志，霸占了CPU資源，不是很好的方法。

? ? 到后來，荷蘭計(jì)算機(jī)科學(xué)家Dijkstra于1965年提出了解決進(jìn)程同步與互斥問題的信號(hào)量機(jī)制，收到了很好的效果，被一直沿用至今，廣泛應(yīng)用與單處理機(jī)和多處理機(jī)系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)中。信號(hào)量機(jī)制就是說兩個(gè)或者多個(gè)進(jìn)程通過他們都可以利用的一個(gè)或多個(gè)信號(hào)來實(shí)現(xiàn)準(zhǔn)確無誤不沖突的并發(fā)執(zhí)行。如果臨界資源不夠，就會(huì)有一個(gè)信號(hào)表示出來，如果進(jìn)程此時(shí)想訪問，那么就會(huì)阻塞到一個(gè)隊(duì)列中，等待調(diào)度。當(dāng)臨界資源使用完畢，一個(gè)進(jìn)程改變信號(hào)，并及時(shí)喚醒阻塞的進(jìn)程，這就實(shí)現(xiàn)了進(jìn)程間的同步和互斥問題。

? ? 信號(hào)量分為整型信號(hào)量，記錄型信號(hào)量，AND信號(hào)量以及信號(hào)量集。最初的信號(hào)量就是整型信號(hào)量，定義信號(hào)量為一個(gè)整型變量，僅能通過兩個(gè)原子操作P,V來訪問，所謂原子操作就是指一組相聯(lián)的操作要么不間斷地執(zhí)行，要么不執(zhí)行。這兩個(gè)操作又稱為wait和signal操作或者down和up操作。之所以叫P,V操作是因?yàn)镈ijkstra是荷蘭人，P指的是荷蘭語中的“proberen”，意為“測(cè)試”，而V指的是荷蘭語中的“verhogen”，意為“增加”。最初P,V操作被描述為：

P(S): while (S≤0) {do nothing};S=S-1;V(S): S=S+1;

但是這樣明顯違反了“讓權(quán)等待的原則”，后來發(fā)展為記錄型信號(hào)量，記錄型信號(hào)量的數(shù)據(jù)結(jié)構(gòu)是一個(gè)兩元組，包含信號(hào)量的值value和關(guān)于此信號(hào)量的阻塞隊(duì)列Q，value具有非負(fù)初值，一般反映了資源的數(shù)量，只能由P,V操作改變其值。（還有另一種定義，信號(hào)量由value和P組成，value為信號(hào)量的值，P為指向PCB隊(duì)列的指針）。

記錄型信號(hào)量的P,V操作原語為：

P(S): S.value = S.value-1;if(S.value < 0)block(S,Q);V(S): S.value = S.value + 1;if(S.value <= 0)wakeup(S,Q);

? ??我們來詳細(xì)解釋一下這兩個(gè)操作的含義：

? ? 首先，P操作，首先將S.value減1，表示該進(jìn)程需要一個(gè)臨界資源，如果S.value<0，那么說明原來的S.value <= 0，即已經(jīng)沒有資源可用了，于是將進(jìn)程阻塞到與信號(hào)量S相關(guān)的阻塞隊(duì)列中去，如果S.value<0,那么|S.value|其實(shí)就表示阻塞隊(duì)列的長(zhǎng)度，即等待使用資源的進(jìn)程數(shù)量。然后，V操作：首先S.value加1，表示釋放一個(gè)資源，如果S.value <= 0，那么說明原來的S.value < 0，阻塞隊(duì)列中是由進(jìn)程的，于是喚醒該隊(duì)列中的一個(gè)進(jìn)程。那么，為什么S.value > 0時(shí)不喚醒進(jìn)程呢，很簡(jiǎn)單，因?yàn)樽枞?duì)列中沒有進(jìn)程了。

? ? P操作相當(dāng)于“等待一個(gè)信號(hào)”，而V操作相當(dāng)于“發(fā)送一個(gè)信號(hào)”，在實(shí)現(xiàn)同步過程中，V操作相當(dāng)于發(fā)送一個(gè)信號(hào)說合作者已經(jīng)完成了某項(xiàng)任務(wù)，在實(shí)現(xiàn)互斥過程中，V操作相當(dāng)于發(fā)送一個(gè)信號(hào)說臨界資源可用了。實(shí)際上，在實(shí)現(xiàn)互斥時(shí)，P,V操作相當(dāng)于申請(qǐng)資源和釋放資源。

? ? 我們將信號(hào)量初值設(shè)置為1時(shí)通常可實(shí)現(xiàn)互斥，因?yàn)樾盘?hào)量表示資源可用數(shù)目，互斥信號(hào)量保證只有一個(gè)進(jìn)程訪問臨界資源，相當(dāng)于只有一個(gè)訪問權(quán)可用。設(shè)置為0或者N時(shí)可以用來實(shí)現(xiàn)同步。我們后面將會(huì)在生產(chǎn)者-消費(fèi)者問題中看到這點(diǎn)。用P,V操作實(shí)現(xiàn)互斥類似于加鎖的實(shí)現(xiàn)，在臨界區(qū)之前加P操作，在臨界區(qū)之后加V操作，即可互斥控制進(jìn)程進(jìn)入臨界區(qū)，訪問臨界資源。記錄型信號(hào)量由于引入了阻塞機(jī)制，消除了不讓權(quán)等待的情況，提高了實(shí)現(xiàn)的效率。

? ??經(jīng)典問題

? ? 下面通過一些實(shí)例詳細(xì)講解如何使用信號(hào)量機(jī)制解決進(jìn)程同步與互斥問題。先說明一條規(guī)律，即：同步與互斥實(shí)現(xiàn)的P,V操作雖然都是成對(duì)出現(xiàn)，但是互斥的P,V操作出現(xiàn)在同一個(gè)進(jìn)程的程序里，而同步的P,V操作出現(xiàn)在不同進(jìn)程的程序中。

問題1：生產(chǎn)者-消費(fèi)者問題

? ? 經(jīng)典的同步互斥問題，也稱作“有界緩沖區(qū)問題”。具體表現(xiàn)為：

1.兩個(gè)進(jìn)程對(duì)同一個(gè)內(nèi)存資源進(jìn)行操作，一個(gè)是生產(chǎn)者，一個(gè)是消費(fèi)者。

2.生產(chǎn)者往共享內(nèi)存資源填充數(shù)據(jù)，如果區(qū)域滿，則等待消費(fèi)者消費(fèi)數(shù)據(jù)。

3.消費(fèi)者從共享內(nèi)存資源取數(shù)據(jù)，如果區(qū)域空，則等待生產(chǎn)者填充數(shù)據(jù)。

4.生產(chǎn)者的填充數(shù)據(jù)行為和消費(fèi)者的消費(fèi)數(shù)據(jù)行為不可在同一時(shí)間發(fā)生。

? ? 生產(chǎn)者-消費(fèi)者之間的同步關(guān)系表現(xiàn)為緩沖區(qū)空，則消費(fèi)者需要等待生產(chǎn)者往里填充數(shù)據(jù)，緩沖區(qū)滿則生產(chǎn)者需要等待消費(fèi)者消費(fèi)。兩者共同完成數(shù)據(jù)的轉(zhuǎn)移或傳送。生產(chǎn)者-消費(fèi)者之間的互斥關(guān)系表現(xiàn)為生產(chǎn)者往緩沖區(qū)里填充數(shù)據(jù)的時(shí)候，消費(fèi)者無法進(jìn)行消費(fèi)，需要等待生產(chǎn)者完成工作，反之亦然。

既然了解了互斥與同步關(guān)系，那么我們就來設(shè)置信號(hào)量：

? ? 由于有互斥關(guān)系，所以我們應(yīng)該設(shè)置一個(gè)互斥量mutex控制兩者不能同時(shí)操作緩沖區(qū)。此外，為了控制同步關(guān)系，我們?cè)O(shè)置兩個(gè)信號(hào)量empty和full來表示緩沖區(qū)的空槽數(shù)目和滿槽數(shù)目，即有數(shù)據(jù)的緩沖區(qū)單元的個(gè)數(shù)。mutex初值為1，empty初值為n，即緩沖區(qū)容量，代表初始沒有任何數(shù)據(jù)，有n個(gè)空的單元，類似的，full初值為0.

? ? 下面進(jìn)行生產(chǎn)者-消費(fèi)者行為設(shè)計(jì)：

void Productor() {while(1) {//制造數(shù)據(jù)P(&empty);P(&mutex);//填充數(shù)據(jù)V(&mutex);V(&full);} }void Consumer() {while(1) {P(&full);P(&mutex);//消費(fèi)數(shù)據(jù)V(&mutex);V(&empty);} }

? ??這樣我們的分析也就完成了，http://www.cnblogs.com/whatbeg/p/4419979.html?這篇文章里有我用Windows API實(shí)現(xiàn)的用信號(hào)量實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問題。

? ? 下面，問題來了，我們的生產(chǎn)者和消費(fèi)者里面都有兩個(gè)P,兩個(gè)V操作，那么兩個(gè)P操作可否調(diào)換順序呢？V操作呢？想一想。

? ? 答案是P操作不可對(duì)換，V操作可以。為什么呢？想象一下這種情況，生產(chǎn)者執(zhí)行P(mutex)把互斥量鎖住，然后再P(empty),此時(shí)empty < 0，鎖住，無法繼續(xù)生產(chǎn)，等待消費(fèi)者消費(fèi)，消費(fèi)者倒是也想消費(fèi)，可是mutex被鎖住了啊，于是兩個(gè)人就等啊等，就成了等待戈多了。。但是V操作是可以隨意調(diào)換的，因?yàn)閂操作是解鎖和喚醒，不會(huì)因?yàn)樗i住什么。

問題2：讀者-寫者問題

第二個(gè)經(jīng)典問題是讀者-寫著問題，它為數(shù)據(jù)庫的訪問建立了一個(gè)模型。規(guī)則如下：

1.一個(gè)進(jìn)程在讀的時(shí)候，其他進(jìn)程也可以讀。

2.一個(gè)進(jìn)程在讀/寫的時(shí)候，其他進(jìn)程不能進(jìn)行寫/讀。

3.一個(gè)進(jìn)程在寫的時(shí)候，其他進(jìn)程不能寫。

我們來分析他們的關(guān)系，首先，這個(gè)問題沒有明顯的同步關(guān)系，因?yàn)樵谶@個(gè)問題里，讀和寫并不要合作完成某些事情。但是是有互斥關(guān)系的，寫者和寫者，寫者和讀者是有互斥關(guān)系的，我們需要設(shè)置一個(gè)mutex來控制其訪問，但是單純一個(gè)信號(hào)量的話會(huì)出現(xiàn)讀者和讀者的互斥也出現(xiàn)了，因?yàn)槲覀兛赡苡卸鄠€(gè)讀者，所以我們?cè)O(shè)置一個(gè)變量ReadCount表示讀者的數(shù)量，好，這個(gè)時(shí)候，對(duì)于ReadCount又要實(shí)現(xiàn)多個(gè)讀者對(duì)他的互斥訪問，所以還要設(shè)置一個(gè)RC_mutex。這樣就好了。然后是行為設(shè)計(jì)：

void Reader() {while(1) {P(&RC_mutex);rc = rc + 1;if(rc == 1) P(&mutex); //如果是第一個(gè)讀者，那么限制寫者的訪問V(&RC_mutex);//讀數(shù)據(jù)P(&RC_mutex);rc = rc - 1;if(rc == 0) V(&mutex); //如果是最后一個(gè)讀者，那么釋放以供寫者或讀者訪問V(&RC_mutex);} }void Writer() {while(1) {P(&mutex);//寫數(shù)據(jù)V(&mutex);} }

其實(shí)，這個(gè)方法是有一定問題的，只要趁前面的讀者還沒讀完的時(shí)候新一個(gè)讀者進(jìn)來，這樣一直保持，那么寫者會(huì)一直得不到機(jī)會(huì)，導(dǎo)致餓死。有一種解決方法就是在一個(gè)寫者到達(dá)時(shí)，如果后面還有新的讀者進(jìn)來，那么先掛起那些讀者，先執(zhí)行寫者，但是這樣的話并發(fā)度和效率又會(huì)降到很低。有人提出了一種寫者優(yōu)先的解法，有點(diǎn)不好理解，這里給出實(shí)現(xiàn)：

//寫者優(yōu)先的讀者-寫者問題解法 Semaphore x = y = z = 1; //x控制ReadCount的互斥訪問，y控制WriteCount的互斥訪問 Semaphore rsem = wsem = 1; //rsem,wsem分別表示對(duì)讀和寫的互斥控制 int ReadCount = WriteCount = 0;void Reader() {P(z); //z保證寫跳過讀，做到寫優(yōu)先P(rsem); //控制對(duì)讀的訪問，如果有寫者，那么此處不成功P(x); //對(duì)RC的互斥控制ReadCount++; if(ReadCount == 1) P(wsem); //第一個(gè)讀者出現(xiàn)后，鎖住不讓寫 V(x);V(rsem); //釋放讀的訪問，以使其他讀者進(jìn)入 V(z);//讀數(shù)據(jù)... P(x);ReadCount--;if(ReadCount == 0) V(wsem); //如果是最后一個(gè)讀者，釋放對(duì)寫的信號(hào) V(x); }void Writer() {P(y);WriteCount++;if(WriteCount == 1) P(rsem);V(y);P(wsem);//寫數(shù)據(jù)... V(wsem);P(y);WriteCount--;if(WriteCount == 0) V(rsem);V(y); }

問題3：哲學(xué)家就餐問題

哲學(xué)家就餐問題描述如下：

有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐，哲學(xué)家們共用一張圓桌，分別坐在周圍的五張椅子上，在圓桌上有五個(gè)碗和五支筷子，平時(shí)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐，進(jìn)餐完畢，放下筷子又繼續(xù)思考。

約束條件
(1)只有拿到兩只筷子時(shí)，哲學(xué)家才能吃飯。
(2)如果筷子已被別人拿走，則必須等別人吃完之后才能拿到筷子。
(3)任一哲學(xué)家在自己未拿到兩只筷子吃飯前，不會(huì)放下手中拿到的筷子。
(4)用完之后將筷子返回原處

分析：筷子是臨界資源，每次只被一個(gè)哲學(xué)家拿到，這是互斥關(guān)系。如果筷子被拿走，那么需要等待，這是同步關(guān)系。

容易想到一種錯(cuò)誤的解法，所以設(shè)置一個(gè)信號(hào)量表示一只筷子，有5只筷子，所以設(shè)置5個(gè)信號(hào)量，哲學(xué)家每次饑餓時(shí)先試圖拿左邊的筷子，再試圖拿右邊的筷子，拿不到則等待，拿到了就進(jìn)餐，最后逐個(gè)放下筷子。這種情況可能會(huì)產(chǎn)生死鎖，因?yàn)槲覀儾恢肋M(jìn)程何時(shí)切換（這也是很多IPC問題的根本原因），如果5個(gè)哲學(xué)家同時(shí)饑餓，同時(shí)試圖拿起左邊的筷子，也很幸運(yùn)地都拿到了，那么他們拿右邊的筷子的時(shí)候都會(huì)拿不到，而根據(jù)第三個(gè)約束條件，都不會(huì)放下筷子，這就產(chǎn)生了死鎖。《現(xiàn)代操作系統(tǒng)》中記載的一種解法是僅當(dāng)一個(gè)哲學(xué)家左右的筷子都可用時(shí)，才拿起筷子，將“試圖獲取兩個(gè)筷子”作為臨界資源，用一個(gè)互斥量mutex實(shí)現(xiàn)對(duì)其的互斥控制，然后用n個(gè)變量記錄哲學(xué)家的狀態(tài)（饑餓，進(jìn)餐，思考<可有可無，因?yàn)槌饲皟烧咭酝庵粫?huì)思考>），然后用一個(gè)同步信號(hào)量數(shù)組，每個(gè)信號(hào)量對(duì)應(yīng)一個(gè)哲學(xué)家，來保證哲學(xué)家得不到自己所需筷子的時(shí)候阻塞。算法如下：

?

還有一種解法是讓奇數(shù)號(hào)與偶數(shù)號(hào)的哲學(xué)家拿筷子的先后順序不同，以破壞環(huán)路等待條件。還可以只允許4個(gè)哲學(xué)家同時(shí)進(jìn)餐（4個(gè)人都拿起一只筷子的時(shí)候，第5個(gè)人不能再拿筷子，這樣就會(huì)空出一只筷子）

?

? ??例題分析

? ? 至此，我們已經(jīng)可以總結(jié)出一點(diǎn)用信號(hào)量解決同步互斥問題的基本規(guī)律和一般步驟：

? ? （1）分析各進(jìn)程間的制約關(guān)系，從而得出同步與互斥關(guān)系

? ? （2）根據(jù)（1）中的分析，設(shè)置信號(hào)量

? ? （3）編寫偽代碼，實(shí)施P,V操作

? ??同步：多個(gè)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，相互等待消息

? ? ?互斥：對(duì)臨界資源的使用

?

? ? 要注意的是，雖然P,V操作在每一個(gè)進(jìn)程中都是成對(duì)出現(xiàn)的，但不一定是針對(duì)一個(gè)信號(hào)量。互斥信號(hào)量的P,V操作總是出現(xiàn)在一個(gè)進(jìn)程中的臨界區(qū)的前后，而同步信號(hào)量的P,V操作總是出現(xiàn)在具有同步關(guān)系的兩個(gè)進(jìn)程中，需要等待消息的一方執(zhí)行P操作，發(fā)出消息的一方執(zhí)行V操作。

? ??下面通過諸多例題來熟悉，掌握及訓(xùn)練用信號(hào)量解決同步與互斥問題的一般方法。

?

問題4：放水果問題

桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個(gè)蘋果，媽媽可向盤中放一個(gè)桔子。

兒子專等吃盤中的桔子，女兒專等吃蘋果。

試用P、V操作實(shí)現(xiàn)爸爸、媽媽、兒子、女兒四個(gè)并發(fā)進(jìn)程的同步。

分析：臨界資源是盤子，放的時(shí)候不能取，取的時(shí)候不能放，取的時(shí)候不能再取。同步關(guān)系：爸爸、媽媽與盤子為空，兒子與盤中有桔，女兒與盤中有蘋果。

所以設(shè)置一個(gè)mutex互斥信號(hào)量來控制對(duì)盤子的訪問，用empty，orange，apple分別代表以上同步關(guān)系。程序如下：

Semaphore mutex = 1; Semaphore empty = 1, orange = apple = 0;mother:while(1) {P(empty);P(mutex);//放入桔子 V(mutex)V(orange);}father:while(1) {P(empty);P(mutex);//放入蘋果 V(mutex)V(apple);}son:while(1) {P(orange)P(mutex)//取桔子 V(mutex);V(empty);}daughter:while(1) {P(apple)P(mutex)//取蘋果 V(mutex);V(empty);}

?

問題5：讀文件問題

四個(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)用P、V操作進(jìn)行管理。

分析：互斥關(guān)系：A和C讀文件時(shí)互斥，B和D讀文件時(shí)互斥，沒有同步關(guān)系。

所以設(shè)置兩個(gè)互斥信號(hào)量：AC_mutex,BD_mutex即可。偽代碼如下：

Semaphore AC_mutex = BD_mutex = 1;A:while(1) {P(AC_mutex);//read F V(AC_mutex);} B:while(1) {P(BD_mutex);//read F V(BD_mutex);} C:while(1) {P(AC_mutex);//read F V(AC_mutex);} D:while(1) {P(BD_mutex);//read F V(BD_mutex);}

?

問題6：閱覽室問題 / 圖書館問題

有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名。讀者離開時(shí)要消掉登記信號(hào)?
，閱覽室中共有100個(gè)座位。用PV操作控制這個(gè)過程。

分析：

由于每個(gè)讀者都會(huì)進(jìn)行一樣的操作：登記->進(jìn)入->閱讀->撤銷登記->離開，所以建立一個(gè)讀者模型即可。

臨界資源有：座位，登記表

讀者間有座位和登記表的互斥關(guān)系，所以設(shè)信號(hào)量empty表示空座位的數(shù)量，初始為100，mutex表示對(duì)登記表的互斥訪問，初始為1。

P,V操作如下：

Semaphore mutex = 1, empty = 100; Reader()： While(true) {P(empty) //申請(qǐng)空座位P(mutex) //申請(qǐng)登記表//登記 V(mutex) //釋放登記表//進(jìn)入閱讀P(mutex) //申請(qǐng)登記表//撤銷登記V(mutex) //釋放登記表V(empty) //釋放座位 }

?

問題7：單行道問題

一段雙向行駛的公路，由于山體滑坡，一小段路的一般車道被阻隔，該段每次只能容納一輛車通過，一個(gè)方向的多個(gè)車輛可以緊接著通過，試用P,V操作控制此過程。

分析：

臨界資源為一半被阻隔的一小段區(qū)域，所以需要Go_mutex,Come_mutex來控制每個(gè)方向車輛通過該路段，以及實(shí)現(xiàn)兩個(gè)方向的同步關(guān)系，同步關(guān)系即為：當(dāng)某方向已有車輛在通行時(shí)，另一方向的車輛必須等待，反之亦然。類似于讀者-寫者問題，車輛從兩邊通過相當(dāng)于兩個(gè)讀者，我們?cè)O(shè)立兩個(gè)計(jì)數(shù)器A和B分別代表兩個(gè)方向的汽車數(shù)量，還要設(shè)置兩個(gè)信號(hào)量A_mutex和B_mutex來實(shí)現(xiàn)對(duì)計(jì)數(shù)器的互斥訪問，因?yàn)樯襟w滑坡處只允許一輛車通過，所以還需設(shè)置一個(gè)互斥量mutex保證相同方向的車輛依次通過該處。

于是程序如下（PV操作包含其中）：

#include <Windows.h> #include <stdio.h> #define N 100 #define TRUE 1 typedef int Semaphore; Semaphore A = 0, B = 0; HANDLE Go_mutex,Come_mutex; HANDLE A_mutex,B_mutex; HANDLE mutex;void down(HANDLE handle) {WaitForSingleObject(handle, INFINITE); }void up(HANDLE handle) {ReleaseSemaphore(handle, 1, NULL); }DWORD WINAPI Come(LPVOID v) {while(TRUE) {down(Come_mutex);down(A_mutex);A = A+1;if(A == 1) {down(Go_mutex);printf(" <<<=====開始自東向西\n");}up(A_mutex);up(Come_mutex);down(mutex);//自東向西通過該路段printf(" <<<=====第%s輛車\n",(char *)v);printf(" END <<<=====第%s輛車\n",(char *)v);up(mutex);down(A_mutex);A = A-1;if(A == 0) {up(Go_mutex);printf(" 自東向西的所有車輛行駛完畢\n");}up(A_mutex);Sleep(2000);}return 1; }DWORD WINAPI Go(LPVOID v) {while(TRUE) {down(Go_mutex);down(B_mutex);B = B+1;if(B == 1) {down(Come_mutex);printf("開始自西向東====>\n");}up(B_mutex);up(Go_mutex);down(mutex);//自西向東通過該路段printf("第%s輛車=====>>>\n",(char *)v);printf("第%s輛車=====>>> END\n",(char *)v);up(mutex);down(B_mutex);B = B-1;if(B == 0) {up(Come_mutex);printf("自西向東的所有車輛行駛完畢\n");}up(B_mutex);Sleep(2000);}return 1; }int main() {DWORD Tid;char AThread[12][10];char BThread[12][10];mutex = CreateSemaphore(NULL, 1, 1, NULL);A_mutex = CreateSemaphore(NULL, 1, 1, NULL);B_mutex = CreateSemaphore(NULL, 1, 1, NULL);Go_mutex = CreateSemaphore(NULL, 1, 1, NULL);Come_mutex = CreateSemaphore(NULL, 1, 1, NULL);for(int i=0;i<4;i++) {AThread[i][0] = i+1+'0';AThread[i][1] = '\0';CreateThread(NULL,0,Come,AThread[i],0,&Tid);}for(int i=4;i<8;i++) {BThread[i][0] = i+1+'0';BThread[i][1] = '\0';CreateThread(NULL,0,Go,BThread[i],0,&Tid);}Sleep(20000);return 0; }

運(yùn)行結(jié)果：

?

從其中可以看出，車輛正常交替順序通過該路段。數(shù)字重復(fù)出現(xiàn)是因?yàn)榫€程被重復(fù)地調(diào)度執(zhí)行。

?

問題8：理發(fā)師問題

理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子 如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。 一個(gè)顧客到來時(shí)，它必?
須叫醒理發(fā)師 如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開。用PV操作管理該過程。

分析：

法1：首先設(shè)置一個(gè)count表示等待的人數(shù)（包括理發(fā)椅上的那個(gè)人），初值為0，以供后來者判斷是否應(yīng)該離開。同時(shí)對(duì)count的訪問要保證互斥，所以設(shè)置mutex信號(hào)量來保證互斥，初值為1。

臨界資源：凳子，理發(fā)椅。 分別設(shè)置waitchair,barchair信號(hào)量，初值分別為n和1，表示臨界資源數(shù)量。

同步關(guān)系：顧客和理發(fā)師之間有同步關(guān)系，用ready和done信號(hào)量來表示，初值均為0，ready表示顧客有沒有準(zhǔn)備好，done表示理發(fā)師是否完成一次理發(fā)。

注意：并非每一個(gè)進(jìn)程都需要while(1)無限循環(huán)，比如此例，顧客剪完一次頭發(fā)就走了，不可能馬上再來剪，而以前的生產(chǎn)者-消費(fèi)者不同，他們都是可以不斷生產(chǎn)消費(fèi)的。

寫出P,V操作如下：

Semaphore waitchair = n; Semaphore barchair = 1; Semaphore ready = done = 0; int count = 0; Semaphore mutex = 1;barber:while(1) {P(ready);理發(fā)V(done);}consumer:P(mutex);if(count <= n) {count = count + 1;V(mutex);}else {V(mutex);離開}P(waitchair);P(barchair);V(waitchair); //離開等待椅去理發(fā)椅需要釋放等待椅!V(ready); //準(zhǔn)備好了P(done); //等待理發(fā)完成 V(barchair);P(mutex);count = count - 1;V(mutex);離開

?

法2：將凳子和理發(fā)椅看做同一種資源，因?yàn)橹灰戆l(fā)椅空就一定會(huì)有人湊上去，所以相當(dāng)于每個(gè)位置都是理發(fā)椅，理發(fā)師只需要去每個(gè)有人的座位理發(fā)即可。

還是設(shè)置count表示正在理發(fā)店中的人數(shù)，以便決定后來者是否離開。

同步關(guān)系仍用ready和done來表示。

算法：

Semaphore ready = done = 0; int count = 0; Semaphore mutex = 1;barber:while(1) {P(ready);理發(fā)V(done);}consumer:P(mutex);if(count <= n) {count = count + 1;V(mutex);}else {V(mutex);離開}V(ready); //準(zhǔn)備好了P(done); //等待理發(fā)完成P(mutex); //也可由理發(fā)師來做count-1的操作count = count - 1;V(mutex);離開

總結(jié)

以上是生活随笔為你收集整理的用信号量解决进程的同步与互斥的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。