基于顏色Petri網(wǎng)的生產(chǎn)者—消費(fèi)者問題建模分析

周新宇

摘 ? 要：生產(chǎn)者—消費(fèi)者問題是計(jì)算機(jī)領(lǐng)域一個(gè)經(jīng)典的問題，經(jīng)過多年的研究廣泛地應(yīng)用于并行系統(tǒng)中?，F(xiàn)在已經(jīng)利用多種技術(shù)實(shí)現(xiàn)了生產(chǎn)者—消費(fèi)者問題的仿真，其中，利用Petri網(wǎng)對(duì)生產(chǎn)者—消費(fèi)者問題仿真已經(jīng)被證明是一種比較可行的仿真方案。文章對(duì)Petri網(wǎng)仿真生產(chǎn)者—消費(fèi)者問題進(jìn)行進(jìn)一步優(yōu)化，采用顏色Petri網(wǎng)對(duì)其進(jìn)行仿真，并對(duì)優(yōu)化后的模型與普通的模型進(jìn)行了模擬運(yùn)行。實(shí)驗(yàn)結(jié)果表明：優(yōu)化后的模型與普通的Petri網(wǎng)模型有相近的模擬結(jié)果，說明優(yōu)化后的模型可以代替原有的模型進(jìn)行生產(chǎn)者—消費(fèi)者問題的模擬，降低了系統(tǒng)模型的復(fù)雜度。

關(guān)鍵詞：生產(chǎn)者—消費(fèi)者;建模;仿真;顏色Petri網(wǎng)

生產(chǎn)者—消費(fèi)者問題是進(jìn)程同步的經(jīng)典問題，經(jīng)過多年的發(fā)展，已經(jīng)應(yīng)用于許多領(lǐng)域的同步問題建模分析，如在并行算法[1]、大量數(shù)據(jù)環(huán)境[2]、網(wǎng)管系統(tǒng)[3]等場(chǎng)景中，利用生產(chǎn)者—消費(fèi)者模型解決相關(guān)的同步問題。由于生產(chǎn)者—消費(fèi)者問題應(yīng)用廣泛，對(duì)這個(gè)問題的仿真也有相當(dāng)多的研究，如利用Java[4]語(yǔ)言、Linux[5]系統(tǒng)、COM[6]組件、C#[7]語(yǔ)言等對(duì)其進(jìn)行的仿真研究。

Petri網(wǎng)是用來描述并發(fā)系統(tǒng)的一種形式化方法。Petri網(wǎng)是由Carl Adam Petri（德國(guó)）在20世紀(jì)60年代提出的，最初用來表示信息流模型，經(jīng)過多年的發(fā)展，現(xiàn)在已經(jīng)由簡(jiǎn)單的、普通的Petri網(wǎng)發(fā)展到高級(jí)Petri網(wǎng)模型。生產(chǎn)者—消費(fèi)者問題利用Petri網(wǎng)的建模研究已經(jīng)實(shí)現(xiàn)了利用普通的Petri網(wǎng)對(duì)其建模及仿真[8-9]。本文采用顏色Petri網(wǎng)對(duì)生產(chǎn)者—消費(fèi)者問題進(jìn)行建模，比較了普通的Petri網(wǎng)建模與本方法的建模模型，通過實(shí)驗(yàn)證明本方案降低了生產(chǎn)者—消費(fèi)者問題建模的復(fù)雜性。

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

1.1 ?模型簡(jiǎn)介

生產(chǎn)者—消費(fèi)者問題是一種多線程同步問題的模型，一個(gè)典型的生產(chǎn)者—消費(fèi)者模型如圖1所示。生產(chǎn)者與消費(fèi)者在同一個(gè)系統(tǒng)中運(yùn)行，生產(chǎn)者作為系統(tǒng)中的一個(gè)進(jìn)程而存在，主要用來生產(chǎn)產(chǎn)品，當(dāng)生產(chǎn)者生產(chǎn)完產(chǎn)品后，將生產(chǎn)的產(chǎn)品放入緩沖區(qū)中。消費(fèi)者作為系統(tǒng)中運(yùn)行的另一個(gè)進(jìn)程而存在，主要的職能就是消耗生產(chǎn)者生產(chǎn)的產(chǎn)品，每次從緩沖區(qū)中取出一個(gè)產(chǎn)品，并消耗掉產(chǎn)品。緩沖區(qū)最初設(shè)置為空，代表暫時(shí)沒有產(chǎn)品;當(dāng)生產(chǎn)者生產(chǎn)一個(gè)產(chǎn)品放入緩沖區(qū)時(shí)，緩沖區(qū)中產(chǎn)品計(jì)數(shù)加1，當(dāng)消費(fèi)者取出一個(gè)產(chǎn)品時(shí)，緩沖區(qū)中產(chǎn)品數(shù)減1。緩沖區(qū)是有限的，當(dāng)緩沖區(qū)中產(chǎn)品數(shù)與緩沖區(qū)數(shù)目相等時(shí)，將不能繼續(xù)放入新的產(chǎn)品，緩沖區(qū)中的產(chǎn)品如果被消費(fèi)者消耗完畢，消費(fèi)者將不能再?gòu)木彌_區(qū)中取出產(chǎn)品。

1.2 ?系統(tǒng)運(yùn)行方式

由生產(chǎn)者與消費(fèi)者組成的系統(tǒng)運(yùn)行方式分成兩個(gè)部分，一部分為生產(chǎn)者過程，一部分為消費(fèi)者過程。

生產(chǎn)者生產(chǎn)產(chǎn)品流程如圖2所示。生產(chǎn)者生產(chǎn)進(jìn)程啟動(dòng)后，先檢查緩沖區(qū)是否滿，如果緩沖區(qū)滿了，則進(jìn)程等待緩沖區(qū)有空間再向下運(yùn)行;如果緩沖區(qū)不滿，則生產(chǎn)一個(gè)產(chǎn)品，然后將產(chǎn)品寫入緩沖區(qū)，占據(jù)一個(gè)緩沖區(qū)空間。

消費(fèi)者消費(fèi)產(chǎn)品流程如圖3所示。消費(fèi)者進(jìn)程啟動(dòng)后，同樣先檢查緩沖區(qū)的內(nèi)容，如果緩沖區(qū)中沒有產(chǎn)品，則等待緩沖區(qū)中有產(chǎn)品再繼續(xù)執(zhí)行;當(dāng)緩沖區(qū)不空的時(shí)候，讀取緩沖區(qū)中的產(chǎn)品，釋放一個(gè)緩沖區(qū)，然后消費(fèi)掉一個(gè)產(chǎn)品。

緩沖區(qū)作為生產(chǎn)者和消費(fèi)者進(jìn)程的執(zhí)行過程中的中介，制約著生產(chǎn)者跟消費(fèi)者的行為，成為二者同步的基礎(chǔ)，緩沖區(qū)由于存在有限跟不能同時(shí)讀寫的特點(diǎn)，成為模型模擬的關(guān)鍵約束條件。

2 ? ?生產(chǎn)者消費(fèi)者系統(tǒng)建模

2.1 ?顏色Petri網(wǎng)簡(jiǎn)介

Petri網(wǎng)是一種由庫(kù)所、變遷以及連接庫(kù)所與變遷的弧組成的網(wǎng)狀結(jié)構(gòu)，庫(kù)所代表資源或某種狀態(tài)，變遷代表資源的變動(dòng)或狀態(tài)的改變。顏色Petri網(wǎng)是一種高級(jí)Petri網(wǎng)，是普通Petri網(wǎng)的擴(kuò)展網(wǎng)。顏色Petri網(wǎng)在普通Petri網(wǎng)的基礎(chǔ)上增加了顏色集，顏色集分為簡(jiǎn)單顏色集和復(fù)雜顏色集，顏色集的加入簡(jiǎn)化了Petri網(wǎng)。

2.2 ?模型建立

生產(chǎn)者—消費(fèi)者Petri網(wǎng)模型如圖4所示，變遷produce表示生產(chǎn)者的生產(chǎn)過程，變遷consume表示消費(fèi)者的消費(fèi)過程，變遷put in buffer和remove from buffer表示生產(chǎn)者與消費(fèi)者之間的消費(fèi)關(guān)系，庫(kù)所buf表示緩沖區(qū)，庫(kù)所pro1表示生產(chǎn)者，Pro2表示生產(chǎn)者生產(chǎn)產(chǎn)品，con1表示消費(fèi)者，con2表示消費(fèi)者等待。由圖4可以得知，生產(chǎn)者和消費(fèi)者在緩沖區(qū)完成產(chǎn)品的交換。

生產(chǎn)者—消費(fèi)者顏色Petri網(wǎng)模型如圖5所示，變遷pro/con表示生產(chǎn)者的生產(chǎn)過程和消費(fèi)者的消費(fèi)過程，變遷put in buffer和remove from buffer表示生產(chǎn)者與消費(fèi)者之間的消費(fèi)關(guān)系，庫(kù)所buf表示緩沖區(qū)，庫(kù)所pro/con表示生產(chǎn)者和消費(fèi)者，produce表示生產(chǎn)者生產(chǎn)產(chǎn)品，consume表示消費(fèi)者等待，生產(chǎn)者和消費(fèi)者的產(chǎn)品的交換依然在緩沖區(qū)中完成。

3 ? ?模型分析

依據(jù)上文建立的模型，分別對(duì)兩種模型進(jìn)行仿真模擬，比較仿真數(shù)據(jù)如圖6所示。仿真選取系統(tǒng)運(yùn)行100次、200次、300次、400次、500次幾個(gè)節(jié)點(diǎn)，利用監(jiān)視器監(jiān)視代表buffer庫(kù)所中token的數(shù)據(jù)總數(shù)，也就是生產(chǎn)者生產(chǎn)過的產(chǎn)品總數(shù)，通過圖6數(shù)據(jù)對(duì)比可以看出，隨著模擬運(yùn)行次數(shù)的增加，buffer中的產(chǎn)品數(shù)在兩種模型中趨于一致，因此可以說明，利用顏色Petri網(wǎng)對(duì)模型進(jìn)行優(yōu)化后，仿真的數(shù)據(jù)并沒有發(fā)生變化，說明兩個(gè)模型表達(dá)的事件相同，但是顏色Petri網(wǎng)簡(jiǎn)化了模型的設(shè)計(jì)。

4 ? ?結(jié)語(yǔ)

本文對(duì)生產(chǎn)者—消費(fèi)者問題進(jìn)行了分析，分別用普通的Petri網(wǎng)及高級(jí)Petri網(wǎng)中的顏色Petri網(wǎng)建立了生產(chǎn)者—消費(fèi)者仿真模型，并進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，基于顏色Petri網(wǎng)的建模跟普通的Petri網(wǎng)建立的模型有相同的表達(dá)能力，并且降低了建模的復(fù)雜性，提升了建模的效率。

[參考文獻(xiàn)]

[1]魯向前，謝垂益，霍英.隨機(jī)性生產(chǎn)者消費(fèi)者問題并行算法及仿真應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2018（5）：291-296.

[2]陳勇.大數(shù)據(jù)量多進(jìn)程環(huán)境下生產(chǎn)者消費(fèi)者模式實(shí)現(xiàn)研究[J].電腦編程技巧與維護(hù)，2015（24）：66-67.

[3]張晶，鄭有才.網(wǎng)管消息通信中生產(chǎn)者消費(fèi)者模式的應(yīng)用與實(shí)現(xiàn)[J].電子科技，2007（7）：69-71.

[4]陳益.利用Java多線程并發(fā)機(jī)制解決生產(chǎn)者—消費(fèi)者問題[J].智能計(jì)算機(jī)與應(yīng)用，2010（1）：147-149.

[5]李梅.生產(chǎn)者—消費(fèi)者的Linux多線程實(shí)現(xiàn)[J].價(jià)值工程，2012（30）：221-222.

[6]高升，馮亞麗，林冬梅.基于COM的生產(chǎn)者—消費(fèi)者問題的解法[J].微型機(jī)與應(yīng)用，2001（4）：6-8.

[7]江珊珊，全蕾.基于C#的生產(chǎn)者和消費(fèi)者的線程同步研究[J].電腦知識(shí)與技術(shù)，2008（35）：2163-2164.

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

[9]圖雅，青松.基于Petri網(wǎng)的計(jì)算機(jī)軟件系統(tǒng)建模[J].電腦知識(shí)與技術(shù)，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