离散事件系统仿真策略

1离散事件系统仿真策略离散事件系统仿真策略：介绍三种仿真策略，即事件调度法、活动扫描、进程交互法。主要术语：（１）成分（Component）：相应于系统中的实体，用于构造模型中的各个部分，可分为两大类：主动成分（Active-typeComponent）：可以主动产生活动的成分如排队系统中的顾客，它的到达将产生排队活动或服务活动。被动成分（Pasive-typeComponent）：本身不能激发活动，只有在主动成分作用下才产生状态变化。（２）描述变量：成分状态、属性的描述。（３）成分间的相互关系：描述成分之间相互影响的规则。在一个模型中，主动成分对被动成分可能产生作用，而主动成分之间也可能产生作用。C＝{1.2,…,n}成分集合,i是第i个成分分量(ni1)。2CA={1.2,…,m}主动成分子集,j是第j个主动成分分量(1nmmj,)。CP={1.2,…,l}被动成分子集,k是第k个被动成分分量(1klln,)。一个模型中，n=m+lS所有成分的状态变量,值域为S。P={p1,p2,…,pn}参数(属性)集合。t成分的状态下一发生变化的时刻,值域为}{),(0R)S(D成分在状态变量值为S时的条件是否满足,)S(D=true，表示满足，)S(D=false表示不满足。TIME模型仿真钟的值，值域为}{),(0R。事件调度法(EventScheduling)事件调度法基本思想：用事件的观点来分析真实系统，通过定义事件及每个事件发生引起系统状态的变化，按时间顺序确定并执行每个事件发生时有关的逻辑关系。3所有事件均放在事件表中。模型中设有一个时间控制成分，该成分从事件表中选择具有最早发生时间的事件，并将仿真钟修改到该事件发生的时间，再调用与该事件相应的事件处理模块，该事件处理完后返回时间控制成分。这样，事件的选择与处理不断地进行，直到仿真终止的条件或程序事件产生为止。策略的非形式描述：成分集合},,{CnA21：主动成分集},,{CmA21，被动成分集},,{CnmmP21描述变量：描述每一主动成分AC的变量，的状态s值域S，s下一变化时刻的时间变量t描述每一被动成分PC的变量，的状态s，值域S(被动成分的状态变化只有在主动成分作用下才能发生,其发生时间由主动成分来确定,因而不需要时间变量。)描述所有成分的属性的变量：参数集合P={p1,p2,…,pr}成分间的相互关系4每个主动成分AC的影响受主在作用下其状态变化的描述,称为事件处理流程;各成分处理的优先级,即同时发生时的处理顺序(解结规则)。注意,在事件调度法中,一般主动成分也同时具有被动成分属性,以便接受其它主动成分的作用。事件调度法算法如下:执行初始化操作,包括:置初始时间t=t0,结束时间tte事件表初始化,置系统初始事件成分状态初始化)s,s),t,s(),t,s((Snmmm111操作事件表,包括取出具有}Ctmin{)s(tA事件记录修改事件表推进仿真钟TIME=t(s)While(TIME=t)则执行Case根据事件类型ii=1执行第1类事件处理程序*（*第i类事件处理程序对成分的状态变化进行建模，而且要进行统计计算）i=2执行第2类事件处理程序…i=m执行第m类事件处理程序2endcase取出具有}Ctmin{)s(tA事件记录**（**若具有}Ctmin{)s(tA事件记录有若干个，则按解结规则处理）置仿真时间TIME=t(s)endwhile***（***该算法中未包括仿真结束后对结果的分析等内容）活动扫描法(ActivityScanning)事件调度法中仿真钟的推进仅仅依据}Ctmin{)s(tA准则，而该事件发生的任何条件的测试必须在该事件处理程序内部去处理。如果条件满足，该事件发生，否则，则推迟或取消该事件发生。从本质上来说，事件调度法是一种“预定事件发生时间”的策略。这样，仿真模型中必须预定系统中下一最先发生的事件。该策略对于活动持续时间确定性较强（可以是服从某种分布的随机变量）的系统是比较方便的。当事件的发生不仅与时间有关，而且与其它条件有关，即只有满足某些条件时才会发生。在这种情况下，事件调度法策略的弱点则表现出来了，由于这类系统的活动持续时间的不确定性，因而无法预定活动的开2始或终止时间。活动扫描法的基本思想是：用活动的观点建模。系统由成分组成，而成分包含着活动，这些活动的发生必须满足某些条件；每一个主动成分均有一个相应的活动子例程；仿真过程中，活动的发生时间也做为条件之一，而且是较之其它条件具有更高的优先权。设)S(D表示成分在系统状态S下的条件是否满足()S(D=true则表示满足，)S(D=false则表示不满足)，t表示成分的状态下一发生变化的时刻，活动扫描法每一步要对系统中所有主动成分进行扫描，当：(i)t仿真钟当前值TIME，且(ii))S(D=true时,执行该成分的活动子例程。所有主动成分扫描一遍后，则又按同样顺序继续进行扫描，直到仿真结束。显然，活动扫描法由于包括了对事件发生时间的扫描，因而它也具有事件调度法的功能。实现措施：3１．设置系统仿真钟TIME与成分仿真钟t系统仿真钟表示系统的仿真进程的推进时间，而成分仿真钟则记录该成分的活动发生时刻，两者的关系可能有三种情况：(i)tTIME表示该活动在将来某一时刻可能发生;(ii)t=TIME表示该活动如果条件满足则应立即发生;(iii)tTIME表示该活动按预定时间早应发生,但因条件未满足,到目前为止实际上仍未发生,当前是否发生,则只要判断其发生的条件。2.设置条件处理模块该模块用于测定)S(D的值及系统仿真钟与成分仿真钟之间的关系,记FUTURE(S)={tTIME}，PRESENT(S)={t=TIME}，PAST(S)={tTIME}该模块将满足下列条件:(i)PRESENT(S)PAST(S)，且(ii))S(D=true的成分置于可激活（4ACTIVATABLE）的成分集合中，即ACTIVATABLE(S)=true)S(D)S(PAST)S(PRESENT此时，系统仿真钟不推进，仅仅处理成分活动，包括修改成分仿真钟。如果可激活的成分集合为空，则将系统仿真钟推进到下一最早发生的活动生成时刻，即TIME=min(tFUTURE(S))算法描述：执行初始化操作,包括:置初始时间t=t0，结束时间ett设置主动成分的仿真钟t(i)(i=1,2,…,m)成分状态初始化：)s,s),t,s(),t,s((Snmmm111设置系统仿真钟TIME=t0While(TIMEt)，则执行扫描forj=最高优先数到最低优先数将优先数为j的成分置成i2If(t(i)TIME且)S(Di=true)执行活动子例程i退出，重新开始扫描endifendforTIME=min(tFUTURE(S))endwhile核心是建立活动子例程模型。包括此活动发生引起的状态变化（自身的），对其它成分的状态产生的作用等等，而条件处理模块则是这种策略实现的本质，它相应于事件调度法中的定时模块。进程交互法（ProcessInteractive）进程交互法采用进程（Process）描述系统，它将模型中的主动成分所发生的事件及活动按时间顺序进行组合，从而形成进程表，一个成分一旦进入进程，只要条件满足，它将完成该进程的全部活动。系统仿真钟的控制程序采用两张事件表，其一是当前事件表（CEL：CurrentEventsList），它包含了从当前时间点开始有资格执行的事件的事件记录，但是该事件是否发生的条件（如果有的话）尚未判断，其二是将来事件表（FEL：FutureEventsList），它包含在将来某个仿真时刻发生的事件的事件记录。每一个事2件记录中包括该事件的若干属性，其中必有一个属性，说明该事件在进程中所处位置的指针。当仿真钟推进时，满足tTIME的所有事件记录从FEL移到CEL中，然后对CEL中的每个事件记录进行扫描，对于从CEL中取出的每一个事件记录，首先判断它属于哪一个进程以及它在该进程中的位置。该事件是否发生则决定于发生条件是否为真。若)S(Di=True,则发生包含该事件的活动，只要条件允许,该进程要尽可能多地连续推进，直到结束；如果)S(Di=False或仿真钟要求停止，则退出该进程，然后对CEL的下一事件记录进行处理。当ＣＥＬ中的所有记录处理完毕后，结束对ＣＥＬ的扫描，继续推进仿真钟，即把将来事件表中的最早发生的事件记录移到ＣＥＬ中，直到仿真结束。算法描述：执行初始化操作，包括设置开始时间t=t0，结束时间t设置初始化事件，并置于FEL中将FEL中有关事件记录置于CEL中成分状态初始化：)s,s),t,s(),t,s((Snmmm111设置系统仿真钟TIME=t02While(TIME=t)，则执行1.CEL扫描While(CEL中最后一个记录未处理完)则While()S(Di=true且当前成分未处理完)则执行该成分的活动*（*一个进程可能有若干个活动，每一个活动有相应的活动子例程来处理该成分在此活动发生时的状态变化及对其它成分的作用）确定该成分的下一事件**（为确定该进程的下一事件，必须对Dai(S)求值，以便决定下一活动是否发生。如果条件不满足，则该进程退出，并记下断点，置于FEL中。）endwhileendwhile2.推进仿真钟TIME=FEL中安排的最早时间If(TIME=t)则将FEL中TIME时刻发生的事件记录移到CEL中endifendwhile进程交互法既可预定事件，又可对条件求值，因而它兼有事件调度法及活动扫描法两者的优点。2113.5三种仿真策略的比较１．系统描述所有策略均提供主动成分及被动成分，每种成分均能接受其它成分的作用。在事件调度法中，只有主动型成分AC才能施加作用，而在其它两种策略中，主动型成分AC与被动型成分PC均可施加作用。在事件调度法中，系统的动态特性表现为主动成分不断产生事件，而在活动扫描法中则表现为主动成分产生活动；在进程交互法中则是通过成分在其进程中一步一步地推进来描述。２．建模要点在事件调度法中，用户要对所定义的全部事件进行建模，条件的测试只能在事件处理子例程中进行。活动扫描法设置了一个条件子例程专用于条件测试，还设置一个活动扫描模块，该模块对所有定义的活动进行建模。进程交互则将一个进程分成若干步，每一步包括条件测试及执行活动两部分。３．仿真钟的推进2在事件调度法中，主动成分的下一事件发生时间保存在事件表中，定时模块不断地从事件表中取出具有最早发生时间的事件记录，并将仿真钟推进到该事件发生时间，并转向该事件处理子例程执行。活动扫描法除了设置了系统仿真钟之外，每一个主动型成分还没有成分仿真钟。定时模块选择那些大于当前系统仿真钟的值且是所有成分仿真钟最小的那个成分仿真钟，然后将系统仿真钟推进到该时刻，并开始对活动扫描。进程交互法采用将来事件表及前事件表。当前事件表中的进程扫描完后，从将来事件表中取出具有最早发生时间的事件记录置于当前事件表中，仿真钟推进到该事件发生时间。一旦某个进程被执行，则要求尽可能多地走下去，但并不改变系统仿真钟；如果该进程并未完成，则将其断点记录下来，即将中断时间及事件类型放到将来事件表中，如果当前事件表中有一项或几项的发生时间小于当前系统仿真钟的值，则说明在以前的扫描中，发生该事件的条件未得到满足，本次应再次进行扫描。4.评述事件调度法：建模灵活，可应用范围广泛，但一般要求用户用通用的高级语言编写事件处理子例程，建3模工作量大。活动扫描法：对于各成分相关性很强的系统来说模型执行效率高。但是，建模时，除了要对各成分的活动进行建模外，仿真执行程序结构比较复杂，其流程控制要十分小心。