实时系统的DDSPN建模与VHDL描述和仿真
摘 要：离散时间确定与随机Petri网(DDSPN)是一种优良的实时系统建模与分析工具。本文研究了基于VHDL的DDSPN描述及仿真方法，分析了VHDL在实时系统建模中的特点与优势，并用一个典型实例验证了该方法的有效性。
关键词：DDSPN；VHDL；实时系统
引言
使用Petri网对系统进行建模和评估已经得到了广泛的研究。通常的做法是使用连续时间马尔可夫随机Petri网对系统进行建模，其中使用较广的是广义随机Petri网(GSPN)。但是，GSPN规定变迁的激发时间只能为0或服从指数分布，而许多在实时应用中的时间行为必须使用确定时间或随机时间来描述，因此GSPN不适合对这些行为建模。
本文使用离散时间确定与随机Petri网(Discrete Time Deterministic and Stochastic Petri Net，DDSPN)对实时系统进行建模和分析。与GSPN相比，DDSPN允许变迁的激发时间为确定时间或服从通常的概率分布(不限定为指数分布)，这一特性克服了使用连续时间随机Petri网分析实时系统的主要困难，为实时系统建模提供了一条可行的途径。
由于DDSPN中变迁激发时间为确定时间和多种离散随机变量，因而不再与马尔可夫链同构，数学解析方法不再适用，计算机仿真成为解算其性能指标的通用方法。如果使用软件编程语言来描述Petri网，虽然会具有很大的灵活性，成熟的语言工具也比较多，但是软件编程语言通常都不能很好反映Petri网的异步并发特性，这就等于丢弃了Petri网的最大优点。由于VHDL语言本身具有描述并发和同步的能力，因此本文使用VHDL语言来描述DDSPN。
图1 两个处理器的DDSPN模型
图2 仿真结果
离散时间确定与随机Petri网
广义随机Petri网定义：一个GSPN是一个六元组(P，T；F，W，M0，l)，其中：
(1)P∩T=f,P和T是两类不同的元素；
(2)P={p1,p2,p3,…,pm}是有限位置的集合；
(3)T={t1,t2,t3,…,tn}是有限变迁的集合；
(4)(P×T)∪(T×P)是弧的集合,弧关系仅存在于位置和变迁两类元素之间；
(5)W：F→N+是弧权函数，N+={1,2,3,…}；
(6)M0：P→N是初始标识，N={0,1,2,3,…}；
(7)F中允许有禁止弧，禁止弧仅存在于从位置到变迁的弧，禁止弧所连接的位置的原可实施条件变为不可实施(disenable)条件，原不可实施条件变为可实施条件，且在相连变迁实施时，没有标记从相连的位置移出；
(8)变迁集T划分为两个子集：T=Tt∪Ti，Tt∩Ti=f，时间(timed)变迁集Tt={t1，t2，…，tk}，瞬时(immediate)变迁集Ti={tk+1，…，tn}，与时间变迁集相关联的平均变迁实施速率集合l={l1，l2，…，lk}；
(9)在一个标识M下为多个可实施的瞬时变迁定义一个随机开关，确定它们之间的实施速率选择。
广义随机Petri网是随机Petri网的一种扩充，主要表现在：将变迁分为两类，一类为瞬时变迁，与随机开关相关联并且实施延时为零；另一类为时间变迁，与指数随机分布的实施延时相关联。在图形上，确定时间变迁用黑体长方块表示，指数时间变迁用空白长方块表示。
DDSPN是由Robert Zijal等人提出的一种离散非马尔可夫随机Petri网。它是对GSPN的一种扩充，它将时间离散化，系统只在采样点进行观察，使能变迁在采样点激发。允许时间变迁的实施延时既可以是常数，也可以是离散随机变量。DDSPN允许的离散随机变量分布有：几何分布(几何分布是一种离散无记忆分布，与连续时间的指数分布相对应)、均匀分布等。瞬时变迁是确定时延变迁的特殊情况。
使用VHDL语言描述
DDSPN
在VHDL语言中，wait和after语句可被用来对电路的时延进行建模与仿真。wait语句用于进程(包括过程)中，格式为：wait for时间表达式。当执行到wait语句时，运行程序将被挂起，直到超过这一时间后，进程自动恢复执行。VHDL中使用after语句实现器件的传输延时和惯性延时。
DDSPN具有元素较少且结构规整的特点，因此可以使用VHDL中的结构化进程语句Process结合after语句来描述；而Process模块本身具有的并行特性又能很好地反映Petri网的特点。需要用VHDL描述的DDSPN元素包括位置、变迁以及与变迁相关联的激发时间变量。
位置
根据DDSPN中位置元素的特点，可采用多进程结构描述位置元素，进程内部顺序执行，进程之间并发执行。多进程结构是并行执行进程的网络，多个进程并发执行，因此，根据DDSPN系统的拓扑结构，可将各进程映射为各位置状态，从而描述出各位置间的异步并发关系。各进程之间通过全局信号进行通信。进程模块中使用信号Pn表示位置pn中的标识数，当与位置相关的输入或输出变迁发生后，要根据系统时钟对信号Pn加1或减1。具体描述如下：
--位置p1
process(reset,clk)
begin
if(reset='0')then
p1<=0;
--初始化位置p1中的标识
elsif(clk'event and clk='1')then
if (p2=1 and p3=1) then
--变迁t1激发条件
p1<=p1+1 after 变迁激发时间;
--位置p1中的标识数改变
end if;
end if;
end process;
变迁
表1 DDSPN模型位置与变迁
变迁通过进程中的一系列判断表达式来实现。对变迁输入位置集中的每个位置信号Pm进行判断，当激发条件满足则变迁激发，变迁输出位置集中的每个位置信号量Pn增加。例如上例中位置p1有一个输入变迁t1，t1有两个输入位置和一个输出位置，分别为p2、p3和p1。进程中判断表达式(p2=1 and p3=1)的值，当为真时位置p1中的标识数加1。
激发时间
变迁激发时间通过VHDL中after语句实现。DDSPN中与变迁相联系的激发时间可以是确定值也可以是离散随机变量，需要编写随机数生成模块。(0,1)均匀分布随机数是最基本的随机数，通过对它进行适当的变换，就可以得到任意分布的其他随机变量，因此随机数模块的核心为一个(0,1)均匀分布随机数发生器。本文中采用线性同余法产生伪随机序列，使用线性同余法必须事先提供三个参数：l、m、m，其递推公式为：
xi+1=(lxi+m)(mod m)
式中，i=1,2...，l≠0，符号(mod m)表示对lxi+m取以m为模的余数，这里l称为乘子，m为增量，m为模。在上式中，若给定初值x0(称为种子)，就可迭代算出均匀随机数序列x1、x2…，将它们除以m，即可得到(0，1)区间均匀分布的随机数xi。该算法的VHDL程序如下：
--随机数产生
procedure GenRnd(r: inout real; seed: in Integer := 13) is
constant RN_M : Integer := 714025;
constant RN_IA: Integer := 1366;
constant RN_IC: Integer := 150889;
begin
r := (RN_IA * r + RN_IC) mod RN_M;
r := REAL(r) / REAL(RN_M);
end GenRnd;
基于VHDL的DDSPN仿真
VHDL语言有许多成熟的仿真工具，现在广泛使用的是ModelTech公司的ModelSim。在使用ModelSim仿真时，将基于VHDL的DDSPN模块作为黑盒子加入仿真工程，并使用测试台文件产生系统激励。下面以一个例子来说明仿真过程。
图1显示了一个简单的实时系统的DDSPN模型，该系统由两个处理器1、2组成，两个处理器的处理任务时间分别为5和7；实时任务的到达间隔时间服从{3，4，5，6，7}上的离散均匀分布。处理器的工作状态分为工作态和空闲态，工作态表示处理器正在处理实时任务，空闲态表示处理器在等待实时任务的到达。假定处理器的准备时间为0，任务到达后处理器立即开始工作，处理器1的优先级高于处理器2，在处理器1、2均处于工作态时到达的实时任务无法处理，表1给出了该系统DDSPN模型的说明。
模型中包含了9个位置和6个变迁，其中t0为时间参数服从{3，4，5，6，7}上离散均匀分布的随机时间变迁，T1、T5、T6为瞬时变迁，T3、T7为确定时间变迁，时间参数分别为5和7，通过禁止弧实现处理器1的优先级高于处理器2。
根据该模型编制VHDL程序，并在ModelSim中经编译、仿真，得到仿真波形如图2所示。仿真结果表明：在到达的100个实时任务中，处理器1处理了68个，处理器2处理了28个，有4个实时任务无法处理，因此该系统无法满足该实时任务的需求，必须提高处理器处理速度或增加处理器数目。从仿真结果可以看出该模型较好地反映了该系统的处理能力，为设计实际系统提供了有价值的参考。
结语
本文讨论了使用随机Petri网对实时系统进行建模和仿真的问题。针对连续时间马尔可夫SPN描述实时系统存在的问题，提出一种用非马尔可夫Petri网DDSPN对实时系统进行建模与仿真分析的实现方案。详细讨论了用VHDL语言对DDSPN进行描述的方法，并在EDA仿真工具ModelSim中对系统进行了仿真。最后，通过一个实例验证了该方法的正确性，收到了良好效果。■
参考文献
1 R·大卫,H·奥兰著. 黄建文，赵不贿译. 佩特利网和逻辑控制器图形表示工具(GRAFCET)[M]. 北京：机械工业出版社, 1996