基于信號量機制的生產者消費者問題的分析

摘 要：本文研究的是操作系統中進程同步和互斥的三大經典問題之一的生產者和消費者問題，通過信號量的機制，對多種辦法解決該問題中可能會出現的多種情況。

關鍵詞：緩沖區；信號量；Java

1 信號量機制

生產者——消費者問題（Procedure——Consumer）是相互合作的進程關系的一種抽象，既包含了同步又包含了互斥。同步指的是進程之間的一種協調行為，互斥，指的是對于臨界區的使用在某個時刻只允許僅被一個進程使用。

為了解決進程的同步和互斥，荷蘭學著Dijkstra于1965年提出了一種卓有成效的信號量機制[1]。在長期的應用中，信號量機制經歷了三個階段的發展，⒈整型信號量⒉記錄型信號量⒊“信號量集”機制。

1.1 整型信號量

定義一個整型變量S，表示資源的數目，僅能通過P（Wait（S），申請資源），V（Signal（S），釋放資源）操作來訪問。具體定義如下：

P（S）：①將信號量S的值減1，即S=S-1；

②如果S<=0，該進程置為等待狀態，排入等待隊列。

V（S）：①將信號量S的值加1，即S=S+1；

②如果S>0，則該進程繼續執行；否則釋放隊列中第一個等待信號量的進程。

1.2 記錄型信號量

整型信號量存在一個缺點，當S<=0時，就要不斷地去測試。進程就會處于“忙等”狀態，不符合“讓權等待”。記錄型信號量解決了多個進行訪問同意臨界資源的情況。其數據結構如下：

typedef semaphore=record

count：=integer；

queue：list of queue；

end

其中，count為信號量的個數。queue為阻塞隊列的進程數目。

1.3 AND信號量

如果出現多個臨界資源時，就需要用AND信號量，指的是一個進程一次性地申請運行所需要的所有的資源，使用完后一次性地釋放資源。在這里需要設置兩個互斥的信號量實現對兩個資源的互斥使用，Dmutex，Emutex。

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

1.4 信號量集

在該種信號量機制中，是在AND信號量機制的基礎上，增加了一個下限，當資源數量低于某一下限時即不予以分配資源。

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

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

其中，S為信號量，d為需求值，t為下限值。

2 Procedure——Consumer

生產者——消費者問題涉及到生產者進程和消費者進程。可以把該過程理解為生產者生產產品，消費者消費這些產品。在兩者之間設置了存放產品的緩沖池。生產者把產品放入一個緩沖區，消費者從一個緩沖區取走產品去消費。這個問題中，需要注意：⒈生產者和消費者必須是互斥的，即當生產者往緩沖區投放產品時，消費者不能去取，其他生產者也不能往里面放數據。⒉生產者和消費者是同步的，即生產者不能向滿緩沖區投放產品，消費者也不能在空緩沖區取數據。Procedure流程圖如下：

2.1 一個生產者一個消費者，公用一個緩沖區

這個問題中不存在互斥的問題，因此只需定義兩個同步信號量，empty與full。Empty表示緩沖區是否為空，初值為1，full表示緩沖區是否為滿，初值為0。

2.2 一個生產者，一個消費者，公用n個環形緩沖區

這種情況下，生產者可以把產品放入其中一個緩沖區當中，只用當緩沖區放入產品，消費者才可以去消費，但是，這些緩沖區是可以循環使用，為了實現循環使用，我們采用了指針，要求生產者是按照一定的順序把生產的產品放入到緩沖區鏈中。

定義兩個同步信號量empty和full，Empty表示緩沖區是否為空，初值為n，full表示的是緩沖區是否為滿，初值為0。定義兩個指針生產者和消費者使用的指針，為input和iget，指向下一個能夠使用的緩沖區。

2.3 n個生產者，n個消費者，公用n個環形緩沖

生產者和消費者之間的是同步的，各個生產者之間，各個消費者之間是互斥的，對緩沖區的訪問應該是互斥的，為了解決這個問題，需要利記錄型信號量。定義三個變量，S為互斥信號量，初始化為1，n為資源信號量，表示已經存放產品的的緩沖區，初始化為0，e為資源信號量，表示空緩沖區的個數。

3 總結

⑴進程在申請資源的時候，如果資源信號量和互斥信號量同時存在，應該先申請資源信號量，后申請互斥信號量（表示查看下該緩沖區是否其他進程在使用）。

⑵同一進程中的P、V操作必須配對出現，同一個信號量的P、V操作可以不同時出現，但是可以在同一進程中嵌套使用。

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

[參考文獻]

[1]嚴兵.生產者消費者問題的分析和實現[J].西華大學學報（自然科學版），2006，25（2）：13-15.

[2]湯曉丹，梁紅兵，哲鳳屏，湯子瀛.計算機操作系統[M].西安電子科技大學出版社，2007.

[3]彭學軍，霸桂芳.生產者——消費者問題圖示分析兩則.許昌師專學報[J]，2006-3-30.

[4]李金忠，曾勁濤.生產者/消費者經典同步問題的深入探究.電腦編程技巧與維護[J].2008-01-03.

[5]張秀娟.生產者-消費者系統的建模與行為分析方法研究.微電子學與計算機，2004-06-20.

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

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