基于顏色Petri網的生產者—消費者問題建模分析

周新宇

摘 ? 要：生產者—消費者問題是計算機領域一個經典的問題，經過多年的研究廣泛地應用于并行系統中?，F在已經利用多種技術實現了生產者—消費者問題的仿真，其中，利用Petri網對生產者—消費者問題仿真已經被證明是一種比較可行的仿真方案。文章對Petri網仿真生產者—消費者問題進行進一步優化，采用顏色Petri網對其進行仿真，并對優化后的模型與普通的模型進行了模擬運行。實驗結果表明：優化后的模型與普通的Petri網模型有相近的模擬結果，說明優化后的模型可以代替原有的模型進行生產者—消費者問題的模擬，降低了系統模型的復雜度。

關鍵詞：生產者—消費者;建模;仿真;顏色Petri網

生產者—消費者問題是進程同步的經典問題，經過多年的發展，已經應用于許多領域的同步問題建模分析，如在并行算法[1]、大量數據環境[2]、網管系統[3]等場景中，利用生產者—消費者模型解決相關的同步問題。由于生產者—消費者問題應用廣泛，對這個問題的仿真也有相當多的研究，如利用Java[4]語言、Linux[5]系統、COM[6]組件、C#[7]語言等對其進行的仿真研究。

Petri網是用來描述并發系統的一種形式化方法。Petri網是由Carl Adam Petri（德國）在20世紀60年代提出的，最初用來表示信息流模型，經過多年的發展，現在已經由簡單的、普通的Petri網發展到高級Petri網模型。生產者—消費者問題利用Petri網的建模研究已經實現了利用普通的Petri網對其建模及仿真[8-9]。本文采用顏色Petri網對生產者—消費者問題進行建模，比較了普通的Petri網建模與本方法的建模模型，通過實驗證明本方案降低了生產者—消費者問題建模的復雜性。

1 ? ?生產者—消費者問題

1.1 ?模型簡介

生產者—消費者問題是一種多線程同步問題的模型，一個典型的生產者—消費者模型如圖1所示。生產者與消費者在同一個系統中運行，生產者作為系統中的一個進程而存在，主要用來生產產品，當生產者生產完產品后，將生產的產品放入緩沖區中。消費者作為系統中運行的另一個進程而存在，主要的職能就是消耗生產者生產的產品，每次從緩沖區中取出一個產品，并消耗掉產品。緩沖區最初設置為空，代表暫時沒有產品;當生產者生產一個產品放入緩沖區時，緩沖區中產品計數加1，當消費者取出一個產品時，緩沖區中產品數減1。緩沖區是有限的，當緩沖區中產品數與緩沖區數目相等時，將不能繼續放入新的產品，緩沖區中的產品如果被消費者消耗完畢，消費者將不能再從緩沖區中取出產品。

1.2 ?系統運行方式

由生產者與消費者組成的系統運行方式分成兩個部分，一部分為生產者過程，一部分為消費者過程。

生產者生產產品流程如圖2所示。生產者生產進程啟動后，先檢查緩沖區是否滿，如果緩沖區滿了，則進程等待緩沖區有空間再向下運行;如果緩沖區不滿，則生產一個產品，然后將產品寫入緩沖區，占據一個緩沖區空間。

消費者消費產品流程如圖3所示。消費者進程啟動后，同樣先檢查緩沖區的內容，如果緩沖區中沒有產品，則等待緩沖區中有產品再繼續執行;當緩沖區不空的時候，讀取緩沖區中的產品，釋放一個緩沖區，然后消費掉一個產品。

緩沖區作為生產者和消費者進程的執行過程中的中介，制約著生產者跟消費者的行為，成為二者同步的基礎，緩沖區由于存在有限跟不能同時讀寫的特點，成為模型模擬的關鍵約束條件。

2 ? ?生產者消費者系統建模

2.1 ?顏色Petri網簡介

Petri網是一種由庫所、變遷以及連接庫所與變遷的弧組成的網狀結構，庫所代表資源或某種狀態，變遷代表資源的變動或狀態的改變。顏色Petri網是一種高級Petri網，是普通Petri網的擴展網。顏色Petri網在普通Petri網的基礎上增加了顏色集，顏色集分為簡單顏色集和復雜顏色集，顏色集的加入簡化了Petri網。

2.2 ?模型建立

生產者—消費者Petri網模型如圖4所示，變遷produce表示生產者的生產過程，變遷consume表示消費者的消費過程，變遷put in buffer和remove from buffer表示生產者與消費者之間的消費關系，庫所buf表示緩沖區，庫所pro1表示生產者，Pro2表示生產者生產產品，con1表示消費者，con2表示消費者等待。由圖4可以得知，生產者和消費者在緩沖區完成產品的交換。

生產者—消費者顏色Petri網模型如圖5所示，變遷pro/con表示生產者的生產過程和消費者的消費過程，變遷put in buffer和remove from buffer表示生產者與消費者之間的消費關系，庫所buf表示緩沖區，庫所pro/con表示生產者和消費者，produce表示生產者生產產品，consume表示消費者等待，生產者和消費者的產品的交換依然在緩沖區中完成。

3 ? ?模型分析

依據上文建立的模型，分別對兩種模型進行仿真模擬，比較仿真數據如圖6所示。仿真選取系統運行100次、200次、300次、400次、500次幾個節點，利用監視器監視代表buffer庫所中token的數據總數，也就是生產者生產過的產品總數，通過圖6數據對比可以看出，隨著模擬運行次數的增加，buffer中的產品數在兩種模型中趨于一致，因此可以說明，利用顏色Petri網對模型進行優化后，仿真的數據并沒有發生變化，說明兩個模型表達的事件相同，但是顏色Petri網簡化了模型的設計。

4 ? ?結語

本文對生產者—消費者問題進行了分析，分別用普通的Petri網及高級Petri網中的顏色Petri網建立了生產者—消費者仿真模型，并進行了仿真實驗，實驗結果表明，基于顏色Petri網的建模跟普通的Petri網建立的模型有相同的表達能力，并且降低了建模的復雜性，提升了建模的效率。

[參考文獻]

[1]魯向前，謝垂益，霍英.隨機性生產者消費者問題并行算法及仿真應用[J].計算機應用與軟件，2018（5）：291-296.

[2]陳勇.大數據量多進程環境下生產者消費者模式實現研究[J].電腦編程技巧與維護，2015（24）：66-67.

[3]張晶，鄭有才.網管消息通信中生產者消費者模式的應用與實現[J].電子科技，2007（7）：69-71.

[4]陳益.利用Java多線程并發機制解決生產者—消費者問題[J].智能計算機與應用，2010（1）：147-149.

[5]李梅.生產者—消費者的Linux多線程實現[J].價值工程，2012（30）：221-222.

[6]高升，馮亞麗，林冬梅.基于COM的生產者—消費者問題的解法[J].微型機與應用，2001（4）：6-8.

[7]江珊珊，全蕾.基于C#的生產者和消費者的線程同步研究[J].電腦知識與技術，2008（35）：2163-2164.

[8]張秀娟.生產者—消費者系統的建模與行為分析方法研究[J].微電子學與計算機，2004（5）：97-100.

[9]圖雅，青松.基于Petri網的計算機軟件系統建模[J].電腦知識與技術，2017（31）：222-223.

Abstract：Producer-consumer problem is a classical problem in computer field， which has been studied for many years and widely applied in parallel system. A variety of technologies have been used to realize the simulation of producer-consumer problem. Petri net simulation of producer-consumer problem has been proved to be a more feasible simulation scheme. In this paper， the Petri net simulation of producer-consumer problem was further optimized， and the colored Petri net was used to simulate it， and the optimized model was simulated with the ordinary model. The experimental results show that the optimized model has similar simulation results with the ordinary Petri net model， which indicates that the optimized model can replace the original model to simulate producer-consumer problems and reduce the complexity of the system model.

Key words：producer-consumer; model; simulation; colored Petri net