目錄

• 1 進(jìn)程同步背景
• 2 臨界區(qū)
• • 2.1 進(jìn)程的互斥
• 3 信號(hào)量
• 4 哲學(xué)家問(wèn)題
• 5 生產(chǎn)者消費(fèi)者問(wèn)題
• 6 讀寫問(wèn)題
• 7 P，V操作總結(jié)

1 進(jìn)程同步背景

對(duì)于之前所提到的生產(chǎn)者消費(fèi)者問(wèn)題，采用共享內(nèi)存解決生產(chǎn)者消費(fèi)者問(wèn)題時(shí)，N個(gè)緩沖區(qū)最多只能用N-1個(gè)，那么為什么有一個(gè)是用不了的呢？這是因?yàn)樵谂袛嗑彌_區(qū)空或滿時(shí)，用取余計(jì)算實(shí)現(xiàn)的，之所以犧牲一個(gè)位置是為了讓緩沖區(qū)空和緩沖區(qū)滿兩種狀態(tài)有兩種不同的表達(dá)式，若是換一種方法，設(shè)置一個(gè)計(jì)數(shù)變量 count ，count 的值表示當(dāng)前緩沖區(qū)已經(jīng)使用的容量，count=0表示緩沖區(qū)空，count=BUFFER_SIZE表示緩沖區(qū)滿（BUFFER_SIZE為緩沖區(qū)大小），這樣就解決了犧牲一個(gè)緩沖區(qū)容量的問(wèn)題，如下圖：

下面是實(shí)現(xiàn)生產(chǎn)者添加商品的偽代碼，若不能理解該過(guò)程可以查閱數(shù)據(jù)結(jié)構(gòu)中循環(huán)隊(duì)列的內(nèi)容：

// 生產(chǎn)者調(diào)用的方法 public void enter(Object item) {// 緩沖區(qū)已經(jīng)滿無(wú)法繼續(xù)添加while (count == BUFFER_SIZE) ; // 添加一個(gè)商品到緩沖區(qū)buffer[in] = item;in = (in + 1) % BUFFER_SIZE;count++; // 計(jì)數(shù)加一 }

下面是實(shí)現(xiàn)消費(fèi)者消費(fèi)商品的偽代碼：

// 消費(fèi)者調(diào)動(dòng)的方法 public Object remove() {Object item;// 當(dāng)前緩沖區(qū)沒(méi)有商品，無(wú)法消費(fèi)while (count == 0) ; // 從緩沖區(qū)移除一個(gè)商品item = buffer[out];out = (out + 1) % BUFFER_SIZE;count--; // 商品總數(shù)減一return item; }

上述思想看起來(lái)是沒(méi)有問(wèn)題的，但是在實(shí)現(xiàn)過(guò)程中會(huì)出現(xiàn)問(wèn)題，問(wèn)題就出在 count 的自增和自減操作，由于count++和count--屬于高級(jí)指令，所以在機(jī)器執(zhí)行過(guò)程中是分為三個(gè)步驟的，中間還有一步轉(zhuǎn)交給寄存器的操作，如下圖：

所以當(dāng)一條指令分解成三個(gè)指令時(shí)，多個(gè)程序并發(fā)時(shí)就會(huì)出現(xiàn)問(wèn)題，現(xiàn)假設(shè)count=5，若生產(chǎn)一個(gè)商品，再消費(fèi)一個(gè)商品，最后count的值還是等于5，可在并發(fā)執(zhí)行時(shí)就不一定會(huì)這樣，見(jiàn)下面的例子（注：以下例子只是情況的一種，在并發(fā)執(zhí)行時(shí)會(huì)有非常多的不確定性），最終count的值等于4：

由以上的例子可知，對(duì)共享數(shù)據(jù)的并發(fā)訪問(wèn)可能導(dǎo)致數(shù)據(jù)的不一致性，要保持?jǐn)?shù)據(jù)的一致性，就需要一種保證并發(fā)進(jìn)程的正確執(zhí)行順序的機(jī)制，解決有界緩沖區(qū)問(wèn)題的共享內(nèi)存方法在類數(shù)據(jù)count 上存在競(jìng)爭(zhēng)條件。

競(jìng)爭(zhēng)條件：

• 若干個(gè)并發(fā)的進(jìn)程(線程)都可以訪問(wèn)和操縱同一個(gè)共享數(shù)據(jù)，從而執(zhí)行結(jié)果就取決于并發(fā)進(jìn)程對(duì)這個(gè)數(shù)據(jù)的訪問(wèn)次序；
• 為了保證數(shù)據(jù)的一致性，需要有同步機(jī)制來(lái)保證多個(gè)進(jìn)程對(duì)共享數(shù)據(jù)的互斥訪問(wèn)。

進(jìn)程的類型分為兩種，一種是獨(dú)立進(jìn)程，它獨(dú)立執(zhí)行，不受其他進(jìn)程的影響；另一種就是協(xié)作進(jìn)程，如剛剛所講的生產(chǎn)者和消費(fèi)者問(wèn)題，這兩個(gè)進(jìn)程就屬于協(xié)作進(jìn)程。進(jìn)程間資源訪問(wèn)沖突也分為兩種，一種是共享變量的修改沖突，如上面的count值，另一種則是操作順序沖突，比如某個(gè)作業(yè)A，需要作業(yè)B提供數(shù)據(jù)進(jìn)行計(jì)算，若B提供數(shù)據(jù)，那么A會(huì)受到影響。

進(jìn)程間的制約關(guān)系分為如下兩種：

• 間接制約：有些資源需要互斥使用，因此各進(jìn)程進(jìn)行競(jìng)爭(zhēng)，獨(dú)占分配到的部分或全部共享資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥；
• 直接制約：進(jìn)行協(xié)作，具體說(shuō)，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài).進(jìn)程的這種關(guān)系為進(jìn)程的同步。

由于多個(gè)進(jìn)程相互競(jìng)爭(zhēng)資源，若各個(gè)進(jìn)程互不相讓，此時(shí)就會(huì)發(fā)生死鎖想象。

2 臨界區(qū)

臨界資源即共享資源，對(duì)于臨界資源，多個(gè)進(jìn)程必須互斥的對(duì)它進(jìn)行訪問(wèn)，在進(jìn)程中某些代碼會(huì)訪問(wèn)到臨界資源，這段代碼就叫做臨界區(qū) (critical section)，即進(jìn)程中訪問(wèn)臨界資源的一段代碼，實(shí)現(xiàn)進(jìn)程對(duì)臨界資源的互斥訪問(wèn)就是讓各進(jìn)程互斥的進(jìn)入自己的臨界區(qū)，也就是說(shuō)當(dāng)某個(gè)進(jìn)程在臨界區(qū)中執(zhí)行時(shí)，其他進(jìn)程都不能訪問(wèn)自己臨界區(qū)，這樣就保證了某個(gè)時(shí)間內(nèi)只有一個(gè)進(jìn)程在臨界區(qū)內(nèi)使用臨界資源，這樣就實(shí)現(xiàn)了臨界資源的互斥訪問(wèn)。

臨界區(qū)的執(zhí)行在時(shí)間上是互斥的，進(jìn)程必須請(qǐng)求允許進(jìn)入臨界區(qū)，也就是說(shuō)當(dāng)某個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，比如進(jìn)行某種操作來(lái)判斷當(dāng)前臨界區(qū)是否有進(jìn)程在執(zhí)行，在具體實(shí)現(xiàn)時(shí)也是利用代碼來(lái)判斷的，整個(gè)進(jìn)程的訪問(wèn)過(guò)程分為以下三個(gè)區(qū)：

• 進(jìn)入?yún)^(qū) (entry section)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問(wèn)臨界區(qū)”標(biāo)志；
• 退出區(qū) (exit section)：用于將"正在訪問(wèn)臨界區(qū)"標(biāo)志清除；
• 剩余區(qū) (remainder section)：代碼中的其余部分。

臨界區(qū)互斥問(wèn)題的解決方案要滿足如下三個(gè)要求：

• 互斥：假定進(jìn)程 Pi 在其臨界區(qū)內(nèi)執(zhí)行，其他任何進(jìn)程將被排斥在自己的臨界區(qū)之外；
• 有空讓進(jìn)：臨界區(qū)雖沒(méi)有進(jìn)程執(zhí)行，但有些進(jìn)程需要進(jìn)入臨界區(qū)，不能無(wú)限期地延長(zhǎng)下一個(gè)要進(jìn)入臨界區(qū)進(jìn)程的等待時(shí)間；
• 有限等待：在 一個(gè)進(jìn)程提出進(jìn)入臨界區(qū)的請(qǐng)求和該請(qǐng)求得到答復(fù)的時(shí)間內(nèi)，其他進(jìn)程進(jìn)入臨界區(qū)的次數(shù)必須是有限的。

2.1 進(jìn)程的互斥

如何實(shí)現(xiàn)進(jìn)程間的互斥？這里舉一個(gè)現(xiàn)實(shí)中游樂(lè)園的滑滑梯例子，滑滑梯一次只能進(jìn)一個(gè)小朋友，當(dāng)有很多小朋友想要玩的時(shí)候，那么一個(gè)解決辦法是讓他們輪流來(lái)玩，另一個(gè)解決辦法是提出想玩滑滑梯申請(qǐng)。在解決進(jìn)程間的互斥問(wèn)題時(shí)，也是借助了這兩個(gè)思想，這里介紹兩種算法。

---

算法1：設(shè)立一個(gè)兩進(jìn)程公用的整型變量 turn ，用來(lái)描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)有兩個(gè)進(jìn)程Pi，Pj ， 如果 turn==i，那么進(jìn)程 Pi允許在其臨界區(qū)執(zhí)行，即采用輪流的方式，用turn表示當(dāng)前運(yùn)行哪個(gè)進(jìn)程進(jìn)入臨界區(qū)。

Pi進(jìn)入臨界區(qū)的偽代碼如下：

while (turn != i); // 判斷是否輪到 Pi critical section; // 執(zhí)行臨界區(qū) turn = j; // 執(zhí)行完臨界區(qū)就輪到下一個(gè) Pjremainder section; // 執(zhí)行剩余區(qū)

Pj進(jìn)入臨界區(qū)的偽代碼如下：

while (turn != j); // 判斷是否輪到 Pjcritical section; // 執(zhí)行臨界區(qū) turn = i; // 執(zhí)行完臨界區(qū)就輪到下一個(gè) Piremainder section; // 執(zhí)行剩余區(qū)

對(duì)于之前提到的臨界區(qū)互斥問(wèn)題的三個(gè)要求，該算法顯然是滿足第一個(gè)互斥要求的，實(shí)際上該算法是強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程的實(shí)際需要，若 Pi 執(zhí)行完臨界區(qū)，turn也轉(zhuǎn)交給了Pj，但此時(shí)Pj不需要使用臨界區(qū)，這時(shí)臨界區(qū)處于空閑狀態(tài)，但turn這時(shí)不屬于Pi，所以Pi依然無(wú)法執(zhí)行臨界區(qū)，容易造成資源利用不充分，所以不滿足第二個(gè)要求有空讓進(jìn)，也不滿足第三個(gè)要求有限等待。

---

算法2：由于算法1 只記住了哪個(gè)進(jìn)程能進(jìn)入臨界區(qū)，沒(méi)有保存進(jìn)程的狀態(tài)，設(shè)立一個(gè)標(biāo)志數(shù)組 flag[]，用來(lái)描述進(jìn)程是否準(zhǔn)備進(jìn)入臨界區(qū)，初值均為 FALSE，先申請(qǐng)后檢查 。可防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。

Pi進(jìn)入臨界區(qū)的偽代碼如下：

flag[i] = TURE; // Pi 申請(qǐng)執(zhí)行臨界區(qū) while (flag[j]); // 判斷 Pj 是不是在執(zhí)行臨界區(qū)或它也想執(zhí)行臨界區(qū)critical section; flag[i] = FALSE; // Pi 執(zhí)行完臨界區(qū)，撤銷之前的申請(qǐng)remainder section;

Pj進(jìn)入臨界區(qū)的偽代碼如下：

flag[j] = TURE; // Pj 申請(qǐng)執(zhí)行臨界區(qū) while (flag[i]); // 判斷 Pi 是不是在執(zhí)行臨界區(qū)或它也想執(zhí)行臨界區(qū)critical section; flag[j] = FALSE; // Pj 執(zhí)行完臨界區(qū)，撤銷之前的申請(qǐng)remainder section;

該算法顯然滿足互斥要求，因?yàn)槊看螆?zhí)行臨界區(qū)前都會(huì)判斷對(duì)方是否在執(zhí)行臨界區(qū)或是否也想進(jìn)入臨界區(qū)；設(shè)想某個(gè)時(shí)刻 Pi 和 Pj 都申請(qǐng)執(zhí)行臨界區(qū)，這樣會(huì)導(dǎo)致雙方誰(shuí)也不能執(zhí)行臨界區(qū)，所以不滿足有空讓進(jìn)的要求，算法2對(duì)比算法1的優(yōu)點(diǎn)是不用交替進(jìn)入，可連續(xù)使用，不用等待對(duì)方，缺點(diǎn)就是兩進(jìn)程可能都進(jìn)入不了臨界區(qū)。

---

算法3：在算法2的基礎(chǔ)上進(jìn)一步改進(jìn)，同樣是要先申請(qǐng)執(zhí)行臨界區(qū)，但要把turn改為對(duì)方，然后再進(jìn)行檢查若當(dāng)前對(duì)方在執(zhí)行臨界區(qū)或?qū)Ψ较胍獔?zhí)行臨界區(qū)且turn也是對(duì)方，那么就要等待對(duì)方執(zhí)行完。

Pi進(jìn)入臨界區(qū)的偽代碼如下：

flag[i] = TURE; // Pi 申請(qǐng)執(zhí)行臨界區(qū) turn = j; // 讓 Pj 下次執(zhí)行 while (flag[j] && turn = j); // 判斷 Pj 是不是在執(zhí)行臨界區(qū)或它也想執(zhí)行臨界區(qū)且當(dāng)且turn為它critical section; flag[i] = FALSE; // Pi 執(zhí)行完臨界區(qū)，撤銷之前的申請(qǐng)remainder section;

Pj進(jìn)入臨界區(qū)的偽代碼如下：

flag[j] = TURE; // Pj 申請(qǐng)執(zhí)行臨界區(qū) turn = i; // 讓 Pi 下次執(zhí)行 while (flag[i] && turn = i); // 判斷 Pi 是不是在執(zhí)行臨界區(qū)或它也想執(zhí)行臨界區(qū)且當(dāng)且turn為它critical section; flag[j] = FALSE; // Pj 執(zhí)行完臨界區(qū)，撤銷之前的申請(qǐng)remainder section;

算法3解決了算法1和算法2的缺點(diǎn)，同時(shí)算法3具有先到先入，后到等待的特點(diǎn)。

3 信號(hào)量

可以用臨界區(qū)解決互斥問(wèn)題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，之前所提到的輪流和申請(qǐng)都是基于兩個(gè)進(jìn)程的臨界區(qū)模型所提出來(lái)的，當(dāng)進(jìn)程數(shù)目過(guò)多的時(shí)候，顯然要引入新的機(jī)制來(lái)解決互斥問(wèn)題，操作系統(tǒng)可從進(jìn)程管理者的角度來(lái)處理互斥的問(wèn)題，信號(hào)量 (Semaphore) 就是操作系統(tǒng)提供的管理公有資源的有效手段。

信號(hào)量是在1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語(yǔ)的test (proberen)、increment (verhogen)），是一種卓有成效的進(jìn)程同步機(jī)制。用于保證多個(gè)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)關(guān)系的相應(yīng)機(jī)制稱為進(jìn)程同步機(jī)制。

信號(hào)量是一個(gè)整型變量，代表信號(hào)量代表可用資源實(shí)體的數(shù)量。除了初始化之外，僅能通過(guò)兩個(gè)不可分割的原子操作訪問(wèn)，即P(S)和V(S)，簡(jiǎn)稱為P，V操作。

原子操作：指的是操作系統(tǒng)內(nèi)最小的操作單位，它的執(zhí)行時(shí)不可中斷的。

由于S代表當(dāng)前可用資源的數(shù)量，當(dāng) S <= 0時(shí)，會(huì)一直等待資源，所以存在忙等現(xiàn)象，又稱自旋鎖，此時(shí)CPU的利用率是不高的，偽代碼如下：

P(S); // 申請(qǐng)資源while (S <= 0); // 當(dāng)前沒(méi)有可用資源就要一直等待 S--; // 若有資源，就要總資源數(shù)減一 V(S); // 使用完資源要釋放資源 S++; // 釋放資源

為了解決忙等現(xiàn)象，引入了一種不需要忙等的方案，它將 S-- 操作提前了，先減再判斷 S 的值，若判斷的 S < 0，就讓進(jìn)程進(jìn)入阻塞狀態(tài)（通常是設(shè)置一個(gè)阻塞進(jìn)程隊(duì)列），在釋放資源時(shí)，若 S >= 0，則要喚醒阻塞的進(jìn)程，偽代碼如下：

P(S); // 申請(qǐng)資源S--; // 總資源數(shù)減一if (S < 0) {block; // 若當(dāng)前無(wú)可用資源，則將該進(jìn)程阻塞} V(S); // 使用完資源要釋放資源S++; // 釋放資源if (S >= 0) {wakeup; // 若當(dāng)前有可用資源，則將之前阻塞的進(jìn)程喚醒}

---

S是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量：

• P(S)：表示申請(qǐng)一個(gè)資源；
• V(S)：表示釋放一個(gè)資源。

一般來(lái)說(shuō)初始化指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)，在信號(hào)量經(jīng)典定義下，信號(hào)量S的值不可能為負(fù)，后面的定義下可能為負(fù)，因?yàn)楹竺娴亩x是先做 S--：

• S≥0 表示可供并發(fā)進(jìn)程使用的資源數(shù)；
• S<0 其絕對(duì)值就是正在等待進(jìn)入臨界區(qū)的進(jìn)程數(shù)。

---

在用信號(hào)量解決問(wèn)題的時(shí)候，首先要分清楚這個(gè)問(wèn)題是個(gè)同步問(wèn)題，還是一個(gè)互斥問(wèn)題，若是一個(gè)互斥問(wèn)題，那么就要找到互斥的臨界資源是什么，并把臨界資源抽象成信號(hào)量，然后給信號(hào)量賦初值并給出正確的P，V操作。

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

問(wèn)題描述：（由Dijkstra首先提出并解決）5個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子（注意是5支而不是5雙），每?jī)蓚€(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)進(jìn)餐，問(wèn)題模型如下圖：

先考慮該問(wèn)題是一個(gè)同步問(wèn)題還是一個(gè)互斥問(wèn)題，顯然它是一個(gè)互斥問(wèn)題，那么它的臨界資源就是筷子，把臨界資源抽象成信號(hào)量為 Semaphore chopStick[] = new Semaphore[5];，即一個(gè)容量為5的數(shù)組。

哲學(xué)家思考和進(jìn)餐的過(guò)程如下面的偽代碼：

Repeat思考；取chopStick[i]; // 一根筷子取chopStick[(i+1) mod 5]； // 取旁邊一根筷子進(jìn)餐；放chopStick[i]; // 放回筷子放chopStick[(i+1) mod 5]； // 放回筷子 Until false;

用信號(hào)量表示的偽代碼如下：

while (true) {// 取左邊的筷子chopStick[i].P();// 取右邊的筷子chopStick[(i + 1) % 5].P();// 進(jìn)餐// 放回左邊的筷子chopStick[i].V();// 放回右邊的筷子chopStick[(i + 1) % 5].V();// 思考 }

用信號(hào)量實(shí)現(xiàn)保證了互斥，但是這種實(shí)現(xiàn)下可能會(huì)出現(xiàn)死鎖，當(dāng)五個(gè)哲學(xué)家每人拿起了他左邊的筷子，則桌子上筷子全部被拿完了，而沒(méi)有一個(gè)哲學(xué)家湊齊了兩支筷子，解決這個(gè)死鎖的方法有如下幾種：

• 最多允許四個(gè)哲學(xué)家同時(shí)就坐，此時(shí)至少有一個(gè)哲學(xué)家能夠同時(shí)拿起兩支筷子；
• 同時(shí)拿起兩根筷子，若某個(gè)哲學(xué)家要進(jìn)餐時(shí)，要求他同時(shí)拿起一雙，若不能同時(shí)拿起兩支，就不能進(jìn)餐；
• 非對(duì)稱解決，處于奇數(shù)位置的哲學(xué)家限制他只能拿左邊的筷子， 處于偶數(shù)位置的哲學(xué)家限制他只能拿右邊的筷子，這樣無(wú)論如何都會(huì)有一個(gè)哲學(xué)家能同時(shí)拿起兩支筷子。

5 生產(chǎn)者消費(fèi)者問(wèn)題

問(wèn)題描述：若干進(jìn)程通過(guò)有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進(jìn)程不斷寫入，而"消費(fèi)者"進(jìn)程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作，問(wèn)題模型如下圖：

由于進(jìn)程之間是共享了臨界資源，所以他們之間肯定是互斥關(guān)系，所以要設(shè)置臨界區(qū)保證進(jìn)程間互斥訪問(wèn)，由于生產(chǎn)者生產(chǎn)商品給消費(fèi)者使用，他們之間也存在著同步關(guān)系。

緩沖區(qū)的大小是固定為N，當(dāng)緩沖區(qū)滿的時(shí)候，生產(chǎn)者是不能再生產(chǎn)商品的，當(dāng)緩沖區(qū)為空的時(shí)候消費(fèi)者是不能消費(fèi)商品的，我們可以抽象以下變量：

• full：表示緩沖區(qū)滿的數(shù)量，也就是可用商品的個(gè)數(shù)，它的初值為 0；
• empty：表示緩沖區(qū)空的數(shù)量，也就是還可以生產(chǎn)多少商品的個(gè)數(shù)，它的初值為 N；
• mutex：用于訪問(wèn)緩沖區(qū)的互斥，初值是 1。

每生產(chǎn)一個(gè)商品就要進(jìn)行 full++ 操作，每消費(fèi)一個(gè)商品就要進(jìn)行 empty++ 操作，full 和 empty 滿足關(guān)系式 full + empty = N。對(duì)于生產(chǎn)者來(lái)說(shuō)它一開(kāi)始要生產(chǎn)商品放到緩沖區(qū)里面，而緩沖區(qū)是互斥的，生產(chǎn)的時(shí)候還要看緩沖區(qū)里面是否還有空位，有空位才能夠生產(chǎn)，所以對(duì)應(yīng)的有兩對(duì)P，V操作，一對(duì)是關(guān)于互斥信號(hào)量 mutex的操作，一對(duì)是關(guān)于資源信號(hào)量 empty 的操作。在實(shí)現(xiàn)的時(shí)候要注意每個(gè)進(jìn)程中各個(gè)P操作的次序是非常重要的。應(yīng)先檢查資源數(shù)目，再檢查是否互斥，否則可能出現(xiàn)死鎖。

對(duì)于生產(chǎn)者操作的偽代碼如下；

P(empty); // 申請(qǐng)空位 empty-- P(mutex); // 申請(qǐng)占用緩沖區(qū)// 生產(chǎn)一個(gè)商品放入緩沖區(qū) V(mutex); // 釋放占用的緩沖區(qū) V(full); // 添加商品 full++

對(duì)于消費(fèi)者操作的偽代碼如下：

P(full); // 申請(qǐng)消費(fèi)一個(gè)商品 full-- P(mutex); // 申請(qǐng)占用緩沖區(qū)// 消費(fèi)緩沖區(qū)中的一個(gè)商品 V(mutex); // 釋放占用的緩沖區(qū) V(empty); // 增加一個(gè)空位 empty++

用信號(hào)量表示生產(chǎn)者的偽代碼如下：

public void enter(Object item) {empty.P(); // 申請(qǐng)緩沖區(qū)中的一個(gè)空位mutex.P(); // 申請(qǐng)占用緩沖區(qū)// 添加一個(gè)商品到緩沖區(qū)buffer[in] = item;in = (in + 1) % BUFFER_SIZE;mutex.V(); // 釋放占用緩沖區(qū)full.V(); // 增加一個(gè)商品 }

用信號(hào)量表示消費(fèi)者的偽代碼如下：

public Object remove() {full.P(); // 申請(qǐng)消費(fèi)一個(gè)商品mutex.P(); // 申請(qǐng)占用緩沖區(qū)// 從緩沖區(qū)消費(fèi)一個(gè)商品Object item = buffer[out];out = (out + 1) % BUFFER_SIZE;mutex.V(); // 釋放占用的緩沖區(qū)empty.V(); // 增加一個(gè)空位return item; }

6 讀寫問(wèn)題

問(wèn)題描述：對(duì)共享資源的讀寫操作，任一時(shí)刻“寫者”最多只允許一個(gè)，而“讀者”則允許多個(gè)。

讀寫問(wèn)題存在以下三種關(guān)系：

• 讀者和寫者：互斥關(guān)系，寫者在寫的時(shí)候讀者不可以讀，讀者在讀的時(shí)候?qū)懻卟豢梢詫?#xff1b;
• 寫者和寫者：互斥關(guān)系，同一時(shí)刻只能有一個(gè)寫者進(jìn)行寫操作；
• 讀者和讀者：沒(méi)有限制，多個(gè)讀者可以同時(shí)讀。

那么可以從兩個(gè)方面來(lái)考慮這個(gè)問(wèn)題，即有讀者來(lái)會(huì)怎么樣和有寫者來(lái)會(huì)怎么樣，當(dāng)有讀者來(lái)的時(shí)候：

• 如果當(dāng)前系統(tǒng)中沒(méi)有讀者也沒(méi)用寫者，那么新來(lái)的讀者可以直接讀，一旦這個(gè)讀者開(kāi)始讀的時(shí)候，后面來(lái)的讀者都可以讀，但是后來(lái)的寫者是不可以寫的；
• 當(dāng)一個(gè)讀者到來(lái)的時(shí)候，發(fā)現(xiàn)有一個(gè)寫者正在等待，因?yàn)橹耙呀?jīng)到來(lái)了讀者并且現(xiàn)在在讀，那么這個(gè)時(shí)候來(lái)的讀者便可以直接讀；
• 當(dāng)一個(gè)讀者到來(lái)的時(shí)候，發(fā)現(xiàn)有一個(gè)寫者正在寫，那么該讀者就不能讀，并且后面來(lái)的讀者都要等待，除非這個(gè)寫者寫完。

當(dāng)寫者到來(lái)時(shí)：

• 若當(dāng)前沒(méi)有讀者，寫者可以直接寫；
• 若當(dāng)前有讀者，寫者便要等待讀者讀完；
• 若當(dāng)前正有寫者在寫，那么該寫者要等待。

總結(jié)來(lái)說(shuō)寫者是更任何人互斥的，讀讀是允許的，并且可以發(fā)現(xiàn)只有第一個(gè)和最后一個(gè)讀者是會(huì)影響寫者的，那么如何知道哪個(gè)讀者是第一個(gè)來(lái)的，哪個(gè)讀者是最后一個(gè)走的呢？我們的解決方法是設(shè)置一個(gè)變量來(lái)統(tǒng)計(jì)讀者的個(gè)數(shù)，初值可以設(shè)為 0，來(lái)一個(gè)讀者就加一，走一個(gè)讀者就減一，這里引入一個(gè)共享變量必然會(huì)成為臨界資源，對(duì)于這個(gè)臨界資源時(shí)肯定要對(duì)它進(jìn)行保護(hù)的，采用的采用信號(hào)量機(jī)制如下：

• 信號(hào)量Wmutex表示"允許寫"，初值是1；
• 公共變量Rcount表示“正在讀”的進(jìn)程數(shù)，初值是0；
• 信號(hào)量Rmutex為了保護(hù)臨界資源Rcount，它表示對(duì)Rcount的互斥操作，初值是1。

寫者的操作偽代碼如下：

P(Wmutex); // 申請(qǐng)寫信號(hào)量write; // 寫 V(Wmutex); // 釋放寫信號(hào)量

讀者的操作相對(duì)復(fù)雜，其偽代碼如下：

P(Rmutex); // 申請(qǐng)對(duì) Rcount 的使用if (Rcount == 0) {// 當(dāng)前讀者是第一個(gè)讀者// 若允許他讀，則要不允許后來(lái)的讀者寫// 要將寫操作的信號(hào)量做 P 操作P(Wmutex);}++Rcount; // 讀者數(shù)加一，上下對(duì) Rmutex 的P，V操作實(shí)際上是為了保護(hù) Rcount V(Rmutex);…read; // 讀… P(Rmutex);--Rcount; // 讀完之后讀者數(shù)減一，上下對(duì) Rmutex 的P，V操作實(shí)際上是為了保護(hù) Rcountif (Rcount == 0) {// 當(dāng)前讀者是最后一個(gè)離開(kāi)的讀者// 此時(shí)應(yīng)該釋放寫操作，對(duì)寫操作做 V 操作V(Wmutex);} V(Rmutex);

7 P，V操作總結(jié)

信號(hào)量S為一個(gè)整型的變量，它描述的是當(dāng)前可用資源的數(shù)目，當(dāng) S > 0 時(shí)表示有S個(gè)資源可用，當(dāng) S = 0 時(shí)表示無(wú)資源可用，當(dāng) S < 0 則 $|S|$表示 S 等待隊(duì)列中的進(jìn)程個(gè)數(shù)，P(S) 表示申請(qǐng)一個(gè)資源，V(S) 表示釋放一個(gè)資源，信號(hào)量的初值應(yīng)該大于等于0。

P，V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作，且有以下規(guī)律：

• 當(dāng)為互斥操作時(shí)：它們處于同一進(jìn)程；
• 當(dāng)為同步操作時(shí)：它們不在同一進(jìn)程中出現(xiàn)。

對(duì)于前后相連的兩個(gè)P(S1)和P(S2) ，順序是至關(guān)重要的，同步P操作應(yīng)該放在互斥P操作前。

總結(jié)

以上是生活随笔為你收集整理的操作系统原理第六章：进程同步的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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