基于颜色Petri网的生产者—消费者问题建模分析

周新宇

摘   要：生产者—消费者问题是计算机领域一个经典的问题，经过多年的研究广泛地应用于并行系统中。现在已经利用多种技术实现了生产者—消费者问题的仿真，其中，利用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