离散系统仿真策略

应用任何一种仿真进程的推进方法都应考虑如何选择“下一事件”,以便执行相应的程序模块来修改系统状态,进行各种统计计算。从事件、活动、进程三个层次来组织事件即构成了处理离散事件模型的三种典型处理方法:事件调度法、活动扫描法、进程交互法。

1.事件调度法(Event Scheduling)

按这种方法建立模型时,所有事件均放于事件表中,模型中设有一个时间控制成分,该成分从事件表中选择具有最早发生时间的事件,并将仿真中的时间变量,即仿真钟修改到该事件发生的时间,再调用与该事件相应的事件处理模块,该事件处理完毕后返回时间控制成分。这样,事件的选择与处理不断地进行,直到仿真终止的程序事件发生为止。在这种方法中,任何条件的测试,均在相应的事件模块中进行,这显然是一种面向时间的仿真方法。

其非形式描述算法如下:

执行初始化操作,包括:

置初始时间t=t₀,结束时间t_∞=t_e

事件表初始化,置系统初始事件

成分状态初始化:S=((S_a1,t_a1),…,(S_am,t_am),…,(S_an,t_an))

操作事件表,包括:

取出具有t(s)=min(t_a|a∈C_a)事件记录

修改事件表

推进仿真钟TIME=t(s)

while(TIMEkengdielt;=t_∞)则执行

Case根据事件类型i

i=1执行第1类事件处理程序

i=2执行第2类事件处理程序

…

i=m执行第m类事件处理程序

endcase

取出具有t(s)=min(t_a|a∈C_a)事件记录

置仿真时间TIME=t(s)

endwhile

2.活动扫描法(Activity Scanning)

在这类仿真中,系统由部件组成,而部件包含着活动,该活动是否发生,视规定的条件是否满足而定,因而有一专门模块来确定激活条件。若条件满足,则激活相应部件的活动模块。时间控制程序较其他条件具有更高的优先级,即在判断激活条件时首先判断该活动发生的时间是否满足,然后再判断其他条件。若所有条件都满足,则执行该部件的活动子程序,然后再对其他部件进行扫描,对所有部件扫描一遍后,又按同样顺序进行循环扫描,直到仿真终止。

设(S)表示成分a在系统状态S下的条件是否满足((S)=true表示满足,(S)=false表示不满足),t_a表示成分a的状态下发生变化的时刻。活动扫描法每一步要对系统中所有主动成分进行扫描,当t_a≤仿真钟当前值TIME,且(S)=true时,执行该成分a的活动子例程。所有主动成分扫描一遍后,又按同样顺序继续进行扫描,直到仿真结束。由于活动扫描法包括了对事件发生时间的扫描,因而也具有事件调度法的功能。

其非形式描述算法如下:

执行初始化操作,包括:

置初始时间t=t₀,结束时间t_∞=t_e

设置主动成分的仿真钟t_a(i)(i=1,2,…,m)

成分状态初始化:S=((S_a1,t_a1),…,(S_am,t_am),…,(S_an,t_an))

设置系统仿真钟TIME=t₀

while(TIMEkengdielt;t_∞),则执行扫描

for j=最高优先数到最低优先数

将优先数为j的成分置成i

if(t_a(i)kengdielt;TIME且D_a(S)=true)

执行活动子例程i

退出,重新开始扫描

endfor

TIME=min{t_a|a∈FUTURE(S)}事件记录

Endwhile

3.进程交互法(Process Interactive)

离散事件系统仿真建模的第三种方法是进程交互法。一个进程包含若干个有序事件及有序活动。采用进程交互法建模更接近于实际系统,从用户的观点来看这种策略更易于使用,因而得到迅速的发展,但这种策略的软件实现比事件调度法及活动扫描法要复杂得多。

进程交互法采用进程(process)描述系统,它将模型中的主动成分所发生的事件及活动按时间顺序进行组合,从而形成进程表,一个成分一旦进入进程,它将完成该进程的全部活动。

软件实现时,系统仿真钟的控制程序采用两张事件表:其一是当前事件表CEL,它包含了从当前时间点开始有资格执行的事件的记录,但是该事件是否发生的条件(如果有的话)尚未判断;其二是将来事件表FEL,它包含在将来某个仿真时刻发生的事件记录。每一个事件记录中包括该事件的若干属性,其中必有一个属性说明该事件在进程中所处位置的指针。

当仿真钟推进时,满足t_a≤TIME的所有事件记录从FEL移到CEL中,然后对CEL中的每个事件记录进行扫描,对于从CEL中取出的每一个事件记录,首先判断它属于哪一个进程以及它在该进程中的位置。该事件是否发生则决定于发生条件是否为真。若D_ai(S)=true,则发生包含该事件的活动,只要条件允许,该进程要尽可能地连续推进,直到结束;如果D_ai(S)=false或仿真钟要求停止,则退出该进程,然后对CEL的下一事件记录进行处理。当CEL中的所有记录处理完毕后,结束对CEL的扫描,继续推进仿真钟,即把将来事件表中的最早发生的事件记录移到CEL中,直到仿真结束。这种策略可用以下算法来描述:

执行初始化操作,包括:

置初始时间t=t₀,结束时间t_∞=t_e

设置初始化事件,并置于FEL中

将FEL中有关事件记录置于CEL中

成分状态初始化:S=((S_a1,t_a1),…,(S_am,t_am),…,(S_an,t_an))

设置系统仿真钟TIME=t

while(TIMEkengdielt;t_∞),则执行

①CEL扫描

while(CEL中最后一个记录未处理完)则

while(D_ai(S)=true有关成分未处理完)则

执行该成分的活动

确定该成分的下一事件

endwhile

endwhile

②推进仿真钟

TIME=FEL中安排的最早时间

if(TIMEkengdielt;=t_∞)则

将FEL中所在TIME时刻发生的事件记录移到CEL中

endif

endwhile

4.三种仿真策略比较

(1)系统描述

所有策略均提供主动成分及被动成分,每种成分均能接受其他成分的作用。在事件调度法中,只有主动型成分C_A才能施加作用,而在其他两种策略中,主动型成分C_A与被动型成分C_P均可施加作用。

在事件调度法中,系统的动态特性表现为主动成分不断产生事件;在活动扫描法中则表现为主动成分产生活动;在进程交互法中则是通过成分在其进程中一步一步地推进来描述。

(2)建模要点

在事件调度法中,用户要对所定义的全部事件进行建模,条件的测试只能在事件处理子例程中进行。

活动扫描法设置了一个条件子例程专用于条件测试,还设置一个活动扫描模块,该模块对所有定义的活动进行建模。

进程交互则将一个进程分成若干步,每一步包括条件测试及执行活动两部分。

(3)仿真钟的推进

在事件调度法中,主动成分的下一事件发生时间保存在事件表中,定时模块不断地从事件表中取出具有最早发生时间的事件记录,将仿真钟推进到该事件发生时间,并转向该事件处理子例程执行。

活动扫描法除了设置了系统仿真钟之外,每一个主动型成分还设有成分仿真钟。定时模块选择那些大于当前系统仿真钟的值且是所有成分仿真钟最小的那个成分仿真钟,然后将系统仿真钟推进到该时刻,并开始对活动扫描。

进程交互法采用将来事件表及当前事件表。当前事件表中的进程扫描完后,从将来事件表中取出具有最早发生时间的事件记录置于当前事件表中,仿真钟推进到该事件发生时间。一旦某个进程被执行,则要求尽可能多地走下去,但并不改变系统仿真钟。如果该进程并未完成,则将其断点记录下来,即将中断时间及事件类型放到将来事件表中,如果当前事件表中有一项或几项的发生时间小于当前系统仿真钟的值,则说明在以前的扫描中,发生该事件的条件未得到满足,应再次进行扫描。

(4)执行控制

事件调度法由定时模块按下一最早发生时间选择事件记录,并转向该事件处理子例程执行。如果下一最早发生事件多于一个,首先按事件的优先数来选择,对具有相同优先数的多个同时事件,解结规则由用户在建模时规定。

活动扫描法按递减优先数的顺序对全部活动扫描,只有满足D_ai(S)=true且t_a≤TIME的活动才能被执行,对相同优先数的活动,解结规则由用户建模时加以规定。

进程交互法按递减优先数的顺序对当前事件表的全部记录进行扫描,根据该事件在其进程中的指针进行条件判断,当D_ai(S)=true时则执行该进程(据指针指示的位置),且只要条件满足,该进程一直执行下去,直到该进程结束;否则要记下断点,修改指针,并把该断点发生的将来时间登记在将来事件表中。当一个进程扫描完后,接着对下一优先数的成分进行扫描,直到扫描完毕。

概括地说,事件调度法建模灵活,可应用范围广泛,但一般要求用户采用通用的高级语言编写事件处理子例程,建模工作量大。活动扫描法对于各成分相关性很强的系统来说模型执行效率高,但是建模时要对各成分的活动进行建模,程序结构比较复杂,流程控制不易。进程交互法是建模最为直观的策略,其模型表示接近实际系统,特别适用于活动可以预测、顺序比较确定的系统,但是其流程控制复杂,建模灵活性不如事件调度法。