离散事件系统仿真 课件 05A 仿真策略与事件调度、05B 活动扫描与进程交互

事件调度仿真策略与系统仿真概述离散事件系统仿真基础随机观测模拟输入数据建模仿真算法设计仿真结果分析一、仿真策略概述二、事件调度法三、关键问题四、总结本节内容事件、活动与进程三者间关系仿真算法是确定仿真钟推进策略的控制方法，是仿真控制的核心。进程事件1事件2事件n-1事件n活动1活动2活动m…………一、仿真策略概述①从临时实体和永久实体的角度看：临时实体与某永久实体的开始接触、最终离开该永久实体都是事件；临时实体从开始接触某永久实体到最终离开该永久实体就可以看作一个活动；临时实体从进入系统（至少有一个永久实体）到最终离开，整个过程就是进程；②从仿真钟角度：事件是对应时间点（时刻）的；活动和进程均是对应时间段的；进程是多个有序的活动组成的。一、仿真策略概述对应的仿真策略（算法）主要有三种：事件调度法是面向事件的，记录事件发生的过程，处理每个事件发生时系统状态变化的结果。活动扫描法是面向活动的，记录每个活动开始与终止的时间，从而记录了实体从一种状态变为另一种状态的过程。进程交互法是面向进程的。它记录着每个进程推进的过程。进程交互法采用交叉推进的方法，推进每个进程，最终完成全部进程的推进，即完成系统的全部运行过程。一、仿真策略概述事件调度法，英文EventScheduling，简记为ES，

活动扫描法，英文ActivityScanning，简记为AS；

进程交互法，英文ProcessInteraction，简记为PI；事件调度法针对时刻点逐个处理；活动扫描法和进程交互法则需要针对时间段逐个处理；基于上述三种策略的组合也是可以的，比如三段扫描法，英文为ThreePhase（简记为TP）；本节主要介绍事件调度法的基本算法思想。一、仿真策略概述事件调度法最早出现在1963年兰德公司的Markowitz等人推出的SIMSCRIPT语言的早期版本中。基本思想：它以事件为分析系统的基本单元，通过定义事件及每个事件发生对系统状态的影响，按时间顺序确定并执行每个事件发生时有关的逻辑关系并策划新的事件来驱动模型的运行。二、事件调度法算法例程main(){inti,j,k;scanf(“Thefirstnumberis:”,&i);scanf(“Thescondnumberis:”,&j);k=i+j;printf(“Thesumofthetwonumbersis:%d”,k);getch();}定义变量变量初始化（数据输入）结果输出数据处理二、事件调度法主程序输入仿真控制参数调用初始化子程序调用时间控制程序调用事件子程序调用输出子程序结束仿真结束？1、修改系统状态；2、修改统计计数器；3、产生将来事件加到事件表。是否①②③1、根据统计计数器进行统计分析；2、打印输出报告。报告产生器1、仿真钟初始化；2、系统状态初始化；3、事件表初始化；4、统计计数器初始化。初始化子程序1、操作事件表，确定下一最早发生事件；2、推进仿真钟。时间推进子程序②事件调度法的仿真钟采用变步长的推进方法。每推进一次仿真钟，对每一个事件发生所引起的系统状态变化进行处理和记录。事件调度法的基本部件包括事件表、时间控制程序和事件处理子程序。事件表按时间的顺序存放所发生的事件，以及这些事件的相关属性。时间控制程序根据事件发生的间隔推进仿真钟。事件处理子程序处理每种事件发生时系统状态所发生的变化。二、事件调度法基本算法：（1）初始化：需要初始化的对象包括成分状态、事件表、系统初始事件、统计计数器置0、仿真钟开始时间t0和结束时间tE等（2）t(s)＝min{t|CA}的事件记录（3）修改事件表（4）推进仿真钟TIME＝t(s)（5）执行事件子程序（6）仿真结束否（TIME≥tE）？否则转第（2）步，是则生成报告，仿真结束。二、事件调度法

二、事件调度法循环部分程序流程表示为：

While(TIME＜T

)则执行

case根据事件类型

i＝1执行1类事件

i＝2执行2类事件

………i＝m执行m类事件

endcase

取出具有t(s)＝min{t|CA}的事件记录置仿真时间TIME＝t(s)endwhile1、变量定义初始化之前还有一件事，叫做变量定义；在仿真平台操作时，拖放对象设置其属性就是在定义变量。在运行前平台需要将其进行梳理分类，通常可以概括成主动成分、被动成分，确定它们的状态、变化范围（值域）以及参数等；在仿真步骤的“系统调研”里提到的结构关系、工艺关系、处理优先级、解结规则等都会在开始运行前得到判断确认，仿真模型才能运行起来。三、关键问题2、系统成分通常我们可以把主动成分的概念与临时实体对应起来，英文单词Active，比如机器加工系统中的工件，自动化立体仓库中的料箱；被动成分可与永久实体对应起来，英文单词Passive，比如前面两个例子中的机器加工系统、自动化立体仓库等。通常主动成分可以主动产生事件，被动成分在主动成分作用下产生状态变化，所以事件调度法中常用主动成分施加作用。三、关键问题3、动态变量通常在程序开始前定义的变量都是静态的。随着仿真规模越来越大，静态变量需要定义很多，虽然有些变量用一次就一直不用了，但仍然会占用内存，影响内存高效利用，降低仿真效率。为了解决这个问题，算法中会用到动态变量的概念，在我们这里的事件表处理中很适用，前面有些执行过的事件就不再使用内存了，腾给后面要执行的事件。三、关键问题后续用动画展示三、关键问题事件调度法仿真策略与事件调度法基本算法变量定义流程图结果输出仿真策略三个要素系统成分循环部分时段变量/初始化四、总结动态变量时刻三种策略事件活动、进程从临时实体与永久实体相互关系理解关键问题（1）试从临时实体与永久实体的作用关系角度来阐述三种仿真策略；（2）试着参照类程序语言，编写简单的事件调度法程序。（3）与事件调度法相比，另两种仿真策略可能的异同在哪里？复习思考题：进程交互活动扫描与系统仿真概述离散事件系统仿真基础随机观测模拟输入数据建模仿真算法设计仿真结果分析一、活动扫描法二、进程交互法三、仿真策略比较四、总结本节内容这个方法最早出现于1962年Buxton和Laski发布的CSL语言中。基本思想：它是以活动为分析系统的基本单元，认为仿真系统在运行的每一个时刻都由若干活动构成，每一个活动对应一个活动处理模块，来处理与活动相关的事件。活动扫描法建立在设立系统仿真钟、成分仿真钟和条件测试模块的基础上的。一、活动扫描法成分仿真钟，也称时间元，即各个实体的局部时钟，将活动（或进程）的执行时间也单独管理起来，同样使用TIME表示系统（全局）仿真钟。每一个实体都带有标志自身时钟值的时间元，时间元的取值由所属实体的下一确定时间刷新。关于时钟元的标识方法，有绝对时间法和相对时间法两种，假设时间扫描算法用time_cell[i]表示第i个活动的时间元，则下一个TIME值的确定方法肯定不同。一、活动扫描法绝对时间法：将时间元的时钟值设定在相应实体的确定事件发生时刻上fori=1tomif(time_cell[i]>TIME)thenif(time_cell[i]<MIN)

thenMIN=time_cell[i]endifendifendforTIME=MIN相对时间法：将时间元的时钟值设定在相应实体确切发生的时间间隔上fori=1tomif

(time_cell[i]>0)thenif

(time_cell[i]<MIN)thenMIN=time_cell[i]endifendifendforTIME=TIME+MIN一、活动扫描法下一个TIME值的扫描算法活动的时间元表示有两种，即绝对时间法和相对时间法。二者差别：在于判断条件和最后系统仿真钟的设置表达式上。前者的时钟值为所属实体的事件发生时刻，后者的时钟值设定在时间间隔上。以绝对时间法为例，最后得到的都是绝对时间值，由此可基于绝对时间值来进行比较。一、活动扫描法绝对时间值与系统时间TIME比较，有三种可能：（1）活动时间元小于TIME：意味着这个活动已经开始执行了，但因为要持续一段时间，它有可能还没执行完，为此使用了变量Da(S)来判断，如果Da(S)=true表示已执行完，放在“可激活成分”集合中；一、活动扫描法（2）活动时间元大于TIME：意味着这个活动等待执行，不放入“可激活成分”集合中，后续算法中会通过循环在这些活动中把当前最早要发生的活动找出来，记入MIN变量，循环结束后，让系统时间推进到这个时刻。一、活动扫描法（3）活动时间元等于TIME：将该活动置于可激活成分集合中，其对应的Da(S)置为true，后续调用该活动对应的子程序，改变系统状态，包括安排后续活动的发生时间等。基于二者的相互关系，可以将活动分成PAST(S)、PRESENT(S)和FUTURE(S)三个集合，在可激活成分集合中活动a都是满足属于前面两个集合且Da(S)为true两个条件的。一、活动扫描法

一、活动扫描法

一、活动扫描法

一、活动扫描法类程序描述：一、活动扫描法输出结果仿真结束？

结束开始

置于可激活成分集合中执行活动子程序ii=1i=i+1i>n？NYNYNY程序结构图算法思想：针对临时实体的生命周期而建立，需要处理临时实体从进入系统到离开系统整个过程中所有事件，包括确定事件和条件事件；它同样需要成分仿真钟，此时的成分仿真钟，对应的是由多个有序事件构成的进程，而活动扫描法对应的是活动；如果把活动扫描法是列角度的成分，那么进程交互法是行角度的成分。二、进程交互法参照活动扫描法的内容可知，成分仿真钟ta与系统仿真钟TIME同样存在三种关系，这三种关系对应着两个不同的事件集合。由于事件对应时间点，所以过去已发生的事件可以不管了，需要管现在和将来要发生的事件。（1）当ta>TIME时事件放入FutureEventList(FEL)；（2）当ta≤TIME时事件放入CurrentEventList(CEL)；二、进程交互法需要说明的是：有些事件从时间上它可以发生了，但其他条件不足还没发生，这类事件也要放入CEL中。此时要记录断点，在后面条件满足时加以执行。由此在逐个循环CEL中每个成分事件时，首先判断该事件的条件Da(S)是否为true。如果是则执行该事件，修改系统状态、统计计数器，包括把新增事件放入FEL中。当然初始化时所有事件都在FEL中。二、进程交互法算法步骤：（1）初始化；（2）在CEL中扫描，测试某成分事件条件是否满足。

如果满足则推进成分仿真钟并执行该事件，直到完毕或无法继续设置断点；如果不满足继续测试下一个成分事件；（3）在FEL中找下一个最早发生的事件，推进系统仿真钟；二、进程交互法算法步骤：（4）将FEL中满足ta≤TIME的事件移入CEL，转向第（2）步；

值得注意的是，当某个成分事件满足条件执行后，还要继续确定这个成分的下一个事件。若又满足条件则继续执行，直到完毕或无法继续设置断点。二、进程交互法

二、进程交互法类程序描述二、进程交互法输出结果仿真结束？初始化结束开始

执行该成分确定该成分的下一事件CEL中有记录？YYNYNN程序结构图

从成分推进的角度（1）活动扫描法：所有成分是步步为营、齐头并进；（2）进程交互法：各个成分交替推进，结束事件也参差不齐，与思维逻辑相符，但其断点的设置和处理很重要，特别是系统复杂时。三、仿真策略比较从循环核心的角度（1）活动扫描法中，有多少活动在建立仿真模型编译时已经确定下来，于是采用for循环放在while循环内来实现；（2）进程交互法的CEL中，有多少记录是随着系统运行不断变化的，只有采用while循环嵌套while循环的方式来实现，循环的次数通过结束条件来控制。三、仿真策略比较三、仿真策略比较事件调度法ES活动扫描法AS进程交互法PI系统描述主动成分施加作用主动成分和被动成分均可施加作用主动成分和被动成分均可施加作用建模要点对事件建模，事件子程序对活动建模，条件子程序进程分