摘 要：本文研究的是操作系統(tǒng)中進(jìn)程同步和互斥的三大經(jīng)典問(wèn)題之一的生產(chǎn)者和消費(fèi)者問(wèn)題，通過(guò)信號(hào)量的機(jī)制，對(duì)多種辦法解決該問(wèn)題中可能會(huì)出現(xiàn)的多種情況。

關(guān)鍵詞：緩沖區(qū)；信號(hào)量；Java

1 信號(hào)量機(jī)制

生產(chǎn)者——消費(fèi)者問(wèn)題（Procedure——Consumer）是相互合作的進(jìn)程關(guān)系的一種抽象，既包含了同步又包含了互斥。同步指的是進(jìn)程之間的一種協(xié)調(diào)行為，互斥，指的是對(duì)于臨界區(qū)的使用在某個(gè)時(shí)刻只允許僅被一個(gè)進(jìn)程使用。

為了解決進(jìn)程的同步和互斥，荷蘭學(xué)著Dijkstra于1965年提出了一種卓有成效的信號(hào)量機(jī)制[1]。在長(zhǎng)期的應(yīng)用中，信號(hào)量機(jī)制經(jīng)歷了三個(gè)階段的發(fā)展，⒈整型信號(hào)量⒉記錄型信號(hào)量⒊“信號(hào)量集”機(jī)制。

1.1 整型信號(hào)量

定義一個(gè)整型變量S，表示資源的數(shù)目，僅能通過(guò)P（Wait（S），申請(qǐng)資源），V（Signal（S），釋放資源）操作來(lái)訪問(wèn)。具體定義如下：

P（S）：①將信號(hào)量S的值減1，即S=S-1；

②如果S<=0，該進(jìn)程置為等待狀態(tài)，排入等待隊(duì)列。

V（S）：①將信號(hào)量S的值加1，即S=S+1；

②如果S>0，則該進(jìn)程繼續(xù)執(zhí)行；否則釋放隊(duì)列中第一個(gè)等待信號(hào)量的進(jìn)程。

1.2 記錄型信號(hào)量

整型信號(hào)量存在一個(gè)缺點(diǎn)，當(dāng)S<=0時(shí)，就要不斷地去測(cè)試。進(jìn)程就會(huì)處于“忙等”狀態(tài)，不符合“讓權(quán)等待”。記錄型信號(hào)量解決了多個(gè)進(jìn)行訪問(wèn)同意臨界資源的情況。其數(shù)據(jù)結(jié)構(gòu)如下：

typedef semaphore=record

count：=integer；

queue：list of queue；

end

其中，count為信號(hào)量的個(gè)數(shù)。queue為阻塞隊(duì)列的進(jìn)程數(shù)目。

1.3 AND信號(hào)量

如果出現(xiàn)多個(gè)臨界資源時(shí)，就需要用AND信號(hào)量，指的是一個(gè)進(jìn)程一次性地申請(qǐng)運(yùn)行所需要的所有的資源，使用完后一次性地釋放資源。在這里需要設(shè)置兩個(gè)互斥的信號(hào)量實(shí)現(xiàn)對(duì)兩個(gè)資源的互斥使用，Dmutex，Emutex。

即：Swait（S1，S2，S3，……Sn），Ssignal（S1，S2，S3，……Sn）。

1.4 信號(hào)量集

在該種信號(hào)量機(jī)制中，是在AND信號(hào)量機(jī)制的基礎(chǔ)上，增加了一個(gè)下限，當(dāng)資源數(shù)量低于某一下限時(shí)即不予以分配資源。

Swait（S1，t1，d1，……S2，tn，dn）

Ssignal（S1，d1，……，Sn，dn）

其中，S為信號(hào)量，d為需求值，t為下限值。

2 Procedure——Consumer

生產(chǎn)者——消費(fèi)者問(wèn)題涉及到生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程?？梢园言撨^(guò)程理解為生產(chǎn)者生產(chǎn)產(chǎn)品，消費(fèi)者消費(fèi)這些產(chǎn)品。在兩者之間設(shè)置了存放產(chǎn)品的緩沖池。生產(chǎn)者把產(chǎn)品放入一個(gè)緩沖區(qū)，消費(fèi)者從一個(gè)緩沖區(qū)取走產(chǎn)品去消費(fèi)。這個(gè)問(wèn)題中，需要注意：⒈生產(chǎn)者和消費(fèi)者必須是互斥的，即當(dāng)生產(chǎn)者往緩沖區(qū)投放產(chǎn)品時(shí)，消費(fèi)者不能去取，其他生產(chǎn)者也不能往里面放數(shù)據(jù)。⒉生產(chǎn)者和消費(fèi)者是同步的，即生產(chǎn)者不能向滿緩沖區(qū)投放產(chǎn)品，消費(fèi)者也不能在空緩沖區(qū)取數(shù)據(jù)。Procedure流程圖如下：

2.1 一個(gè)生產(chǎn)者一個(gè)消費(fèi)者，公用一個(gè)緩沖區(qū)

這個(gè)問(wèn)題中不存在互斥的問(wèn)題，因此只需定義兩個(gè)同步信號(hào)量，empty與full。Empty表示緩沖區(qū)是否為空，初值為1，full表示緩沖區(qū)是否為滿，初值為0。

2.2 一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，公用n個(gè)環(huán)形緩沖區(qū)

這種情況下，生產(chǎn)者可以把產(chǎn)品放入其中一個(gè)緩沖區(qū)當(dāng)中，只用當(dāng)緩沖區(qū)放入產(chǎn)品，消費(fèi)者才可以去消費(fèi)，但是，這些緩沖區(qū)是可以循環(huán)使用，為了實(shí)現(xiàn)循環(huán)使用，我們采用了指針，要求生產(chǎn)者是按照一定的順序把生產(chǎn)的產(chǎn)品放入到緩沖區(qū)鏈中。

定義兩個(gè)同步信號(hào)量empty和full，Empty表示緩沖區(qū)是否為空，初值為n，full表示的是緩沖區(qū)是否為滿，初值為0。定義兩個(gè)指針生產(chǎn)者和消費(fèi)者使用的指針，為input和iget，指向下一個(gè)能夠使用的緩沖區(qū)。

2.3 n個(gè)生產(chǎn)者，n個(gè)消費(fèi)者，公用n個(gè)環(huán)形緩沖

生產(chǎn)者和消費(fèi)者之間的是同步的，各個(gè)生產(chǎn)者之間，各個(gè)消費(fèi)者之間是互斥的，對(duì)緩沖區(qū)的訪問(wèn)應(yīng)該是互斥的，為了解決這個(gè)問(wèn)題，需要利記錄型信號(hào)量。定義三個(gè)變量，S為互斥信號(hào)量，初始化為1，n為資源信號(hào)量，表示已經(jīng)存放產(chǎn)品的的緩沖區(qū)，初始化為0，e為資源信號(hào)量，表示空緩沖區(qū)的個(gè)數(shù)。

3 總結(jié)

⑴進(jìn)程在申請(qǐng)資源的時(shí)候，如果資源信號(hào)量和互斥信號(hào)量同時(shí)存在，應(yīng)該先申請(qǐng)資源信號(hào)量，后申請(qǐng)互斥信號(hào)量（表示查看下該緩沖區(qū)是否其他進(jìn)程在使用）。

⑵同一進(jìn)程中的P、V操作必須配對(duì)出現(xiàn)，同一個(gè)信號(hào)量的P、V操作可以不同時(shí)出現(xiàn)，但是可以在同一進(jìn)程中嵌套使用。

⑶申請(qǐng)資源必須在釋放資源之前，即先需要Wait，再Signal。

[參考文獻(xiàn)]

[1]嚴(yán)兵.生產(chǎn)者消費(fèi)者問(wèn)題的分析和實(shí)現(xiàn)[J].西華大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，25（2）：13-15.

[2]湯曉丹，梁紅兵，哲鳳屏，湯子瀛.計(jì)算機(jī)操作系統(tǒng)[M].西安電子科技大學(xué)出版社，2007.

[3]彭學(xué)軍，霸桂芳.生產(chǎn)者——消費(fèi)者問(wèn)題圖示分析兩則.許昌師專學(xué)報(bào)[J]，2006-3-30.

[4]李金忠，曾勁濤.生產(chǎn)者/消費(fèi)者經(jīng)典同步問(wèn)題的深入探究.電腦編程技巧與維護(hù)[J].2008-01-03.

[5]張秀娟.生產(chǎn)者-消費(fèi)者系統(tǒng)的建模與行為分析方法研究.微電子學(xué)與計(jì)算機(jī)，2004-06-20.

基金項(xiàng)目：2013年福建省教育廳科技研究項(xiàng)目（JB13280）。

作者簡(jiǎn)介：李盼盼（1984-），女，碩士，助教；趙浩（1982-），男，碩士，助教。