离散事件系统仿真策略.doc

第十三章离散事件系统仿真策略离散事件系统仿真策略：介绍三种仿真策略，即事件调度法、活动扫描、进程交互法 主要术语：(1 )成分(Component):相应于系统中的实体，用于构造模型中的各个部分，可分为两大类： 主动成分(Active-type Component):可以主动产生活动的成分如排队系统中的顾客，它的到达将产生排队活动或服务活动被动成分(Pasive-type Component)：本身不能激发活动，只有在主动成分作用下才产生状态变化 (2 )描述变量：成分状态、属性的描述3)成分间的相互关系：描述成分之间相互影响的规则在一个模型中，主动成分对被动成分可能产生作用，而主动成分之间也可能产生作用C={ /. 2,…,』成分集合"是第i个成分分量()Ca={/. 2,…,加}主动成分子集“是第丿个主动成分分量⑴ CP={/. 2,…,/} 被动成分子集必是第k个被动成分分量(1)一个模型中， n=m+lS 所有成分的状态变量，值域为 P={Pb P2,…,Pn} 参数(属性)集合成分的状态下一发生变化的时刻，值域为成分在状态变量值为S时的条件是否满足，=true,表示满足，=false表示不满足。

TIME模型仿真钟的值，值域为13.1 事件调度法(Event Scheduling)事件调度法基本思想：用事件的观点来分析真实系统，通过定义事件及每个事件发生引起系统状态的变 化，按时间顺序确定并执行每个事件发生时有关的逻辑关系所有事件均放在事件表中模型中设有一个时间控制成分，该成分从事件表中选择具有最早发生时间的事件，并将仿真钟修改到该事件发生的时间，再调用与该事件相应的事件处理模块，该事件处理完后返回时 间控制成分这样，事件的选择与处理不断地进行，直到仿真终止的条件或程序事件产生为止策略的非形式描述：成分集合：主动成分集，被动成分集描述变量：描述每一主动成分的变量，的状态值域，下一变化时刻的时间变量描述每一被动成分的变量，的状态，值域(被动成分的状态变化只有在主动成分作用下才能发生，其发生时间由主动成分来确定，因而不需要时间变量) 描述所有成分的属性的变量：参数集合P={Pb P2, Pr}成分间的相互关系每个主动成分的影响受主在作用下其状态变化的描述，称为事件处理流程;各成分处理的优先级，即同时发生时的处理顺序(解结规则)注意，在事件调度法中，一般主动成分也同时具有被动成分属性，以便接受其它主动成分的作用。

事件调度法算法如下：执行初始化操作，包括： 置初始时间t=to,结束时间 事件表初始化，置系统初始事件 成分状态初始化(*第i类事件处理程序对成分的状态变化进行建模,而且要进行统计计算)上2执行第2类事件处理程序/=m执行第m类事件处理程序操作事件表，包括取出具有事件记录修改事件表推进仿真钟TIMEn⑸ While(TIME<=)则执行Case根据事件类型i/=1执行第1类事件处理程序*endcase取出具有事件记录**(**若具有事件记录有若干个，则按解结规则处理 )置仿真时间TIMEK(s)endwhile***(***该算法中未包括仿真结束后对结果的分析等内 容)13. 2 活动扫描法(Activity Scanning)事件调度法中仿真钟的推进仅仅依据准则，而该事件发生的任何条件的测试必须在该事件处理程序内 部去处理如果条件满足，该事件发生，否则，则推迟或取消该事件发生从本质上来说，事件调度法是一种“预定事件发生时间”的策略这样，仿真模型中必须预定系统中下最先发生的事件该策略对于活动持续时间确定性较强(可以是服从某种分布的随机变量)的系统是比较方便的当事件的发生不仅与时间有关，而且与其它条件有关，即只有满足某些条件时才会发生。

在这种情况下 ,事件调度法策略的弱点则表现出来了，由于这类系统的活动持续时间的不确定性，因而无法预定活动的开 始或终止时间活动扫描法的基本思想是：用活动的观点建模系统由成分组成，而成分包含着活动，这些活动的发 生必须满足某些条件；每一个主动成分均有一个相应的活动子例程；仿真过程中，活动的发生时间也做为条件之一，而且是较之其它条件具有更高的优先权设表示成分在系统状态S下的条件是否满足(=疗如则表示满足，=false则表示不满足)，表示成分的状 态下一发生变化的时刻，活动扫描法每一步要对系统中所有主动成分进行扫描，当：(i)仿真钟当前值TIME,且(ii)Mw时，执行该成分的活动子例程所有主动成分扫描一遍后，则又按同样顺序继续进行扫描，直到仿真结束显然，活动扫描法由于包括了对事件发生时间的扫描，因而它也具有事件调度法的功能实现措施：1・设置系统仿真钟TIME与成分仿真钟系统仿真钟表示系统的仿真进程的推进时间，而成分仿真钟则记录该成分的活动发生时刻，两者的关系可能有三种情况:(i) >TIME表示该活动在将来某一时刻可能发生；(ii) =TIME表示该活动如果条件满足则应立即发生；(iii)

2.设置条件处理模块该模块用于测定的值及系统仿真钟与成分仿真钟之间的关系，记 FUTURE(S)={ TIME}, PRESENT(S)={ =TIME), PAST(S)={

13. 3 进程交互法(Process Interactive)进程交互法采用进程（Process）描述系统，它将模型中的主动成分所发生的事件及活动按时间顺序进行 组合，从而形成进程表，一个成分一旦进入进程，只要条件满足，它将完成该进程的全部活动系统仿真钟的控制程序采用两张事件表，其一是当前事件表（CEL： Current Events List},它包含了从当前时间点开始有资格执行的事件的事件记录，但是该事件是否发生的条件（如果有的话）尚未判断，其二 是将来事件表（FEL： Future Events List},它包含在将来某个仿真时刻发生的事件的事件记录每一个事 件记录中包括该事件的若干属性，其中必有一个属性，说明该事件在进程中所处位置的指针当仿真钟推进时，满足TIME的所有事件记录从FEL移到CEL中，然后对CEL中的每个事件记录进 行扫描，对于从CEL中取出的每一个事件记录，首先判断它属于哪一个进程以及它在该进程中的位置该 事件是否发生则决定于发生条件是否为真若二Tme，则发生包含该事件的活动，只要条件允许，该进程要尽 可能多地连续推进，直到结束；如果=False或仿真钟要求停止，则退出该进程，然后对CEL的下一事件记录进行处理。

当CEL中的所有记录处理完毕后，结束对CEL的扫描，继续推进仿真钟，即把将来事件表 中的最早发生的事件记录移到CEL中，直到仿真结束•=J执行初始化操作，包括 确定该成分的下一事件衬设置开始时间t=to,结束时间 （为确定该进程的下一事件，必须对現⑸求值,设置初始化事件，并置于FEL中将FEL中有关事件记录置于CEL中成分状态初始化：设置系统仿真钟TIME=/0While （TIME<=）,则执行1. CEL扫描While （CEL中最后一个记录未处理完）则While （=true且当前成分未处理完）则执行该成分的活动*（*一个进程可能有若干个活动，每一个活动有相应的活动子例程来处理该成分在此活动发生时的状态变化及对其它成分的作用）以便决定下一活动是否发生如果条件不满足，则 该进程退出，并记下断点，置于FEL中endwhileendwhile2.推进仿真钟ZATIME<=）则将FEL中TIME时刻发生的事件记录移 至!J CEL中end旷endwhileTIME=FEL中安排的最早时间进程交互法既可预定事件，又可对条件求值，因而它兼有事件调度法及活动扫描法两者的优点13.5三种仿真策略的比较1・系统描述所有策略均提供主动成分及被动成分，每种成分均能接受其它成分的作用。

在事件调度法中，只有主动 型成分才能施加作用，而在其它两种策略中，主动型成分与被动型成分均可施加作用在事件调度法中，系统的动态特性表现为主动成分不断产生事件，而在活动扫描法中则表现为主动成分 产生活动；在进程交互法中则是通过成分在其进程中一步一步地推进来描述2・建模要点在事件调度法中，用户要对所定义的全部事件进行建模，条件的测试只能在事件处理子例程中进行活动扫描法设置了一个条件子例程专用于条件测试，还设置一个活动扫描模块，该模块对所有定义的活 动进行建模进程交互则将一个进程分成若干步，每一步包括条件测试及执行活动两部分3・仿真钟的推进在事件调度法中，主动成分的下一事件发生时间保存在事件表中，定时模块不断地从事件表中取岀具有 最早发生时间的事件记录，并将仿真钟推进到该事件发生时间，并转向该事件处理子例程执行活动扫描法除了设置了系统仿真钟之外，每一个主动型成分还没有成分仿真钟定时模块选择那些大于 当前系统仿真钟的值且是所有成分仿真钟最小的那个成分仿真钟，然后将系统仿真钟推进到该时刻，并开始 对活动扫描进程交互法采用将来事件表及前事件表当前事件表中的进程扫描完后，从将来事件表中取出具有最早发生时间的事件记录置于当前事件表中，仿真钟推进到该事件发生时间。

一旦某个进程被执行，则要求尽可 能多地走下去，但并不改变系统仿真钟；如果该进程并未完成，则将其断点记录下来，即将中断时间及事件 类型放到将来事件表中，如果当前事件表中有一项或几项的发生时间小于当前系统仿真钟的值，则说明在以 前的扫描中，发生该事件的条件未得到满足，本次应再次进行扫描4.评述事件调度法：建模灵活，可应用范围广泛，但一般要求用户用通用的高级语言编写事件处理子例程，建 模工作量大活动扫描法：对于各成分相关性很强的系统来说模型执行效率高但是，建模时，除了要对各成分的活 动进行建模外，仿真执行程序结构比较复杂，其流程控制要十分小心进程交互法：建模最为直观，其模型表示接近实际系统，特别适用于活动可以预测，顺序比较确定的系 统，但是其流程控制复杂，建模灵活性不如事件调度法13.6离散事件系统仿真语言1 GPSS： GPSS语言推出最早，釆用进程交互法GPSS特点：模型可采用一组标准的程序块(block)来表示其。