离散事件仿真

离散事件仿真基本原理 赵问道 浙江大学信息与通信工程研究所 目 录 一、离散事件仿真的基本概念 .................................................................................................. 3 1. 基于事件的（event-based）离散事件仿真 ................................................................. 3 2. 基于活动的（activity-based）离散事件仿真 .............................................................. 3 3. 基于进程的（process-based）离散事件仿真 .............................................................. 3 4. 三阶段（ three-phase）离散事件仿真 ........................................................................ 3 二、离散事件仿真系统的组成 .................................................................................................. 4 1. 时钟（Clock） ............................................................................................................... 4 2. 事件列表（Events List） ............................................................................................... 4 3. 随机数发生器（Random-Number Generators） .......................................................... 5 4. 统计（Statistics） .......................................................................................................... 5 5. 结束条件（ Ending Condition） .................................................................................. 5 三、仿真引擎逻辑（Simulation Engine Logic） ..................................................................... 5 1. 开始（Start） ................................................................................................................. 5 2. 循环（“Do loop” or “While loop”） ............................................................................. 6 3. 结束（End） .................................................................................................................. 6 离散事件仿真基本原理 一、离散事件仿真的基本概念 在离散事件仿真中，系统的操作通过按时间顺序排列的一组事件序列来表示。每个事件 发生在某一时刻，表示系统的状态改变。例如， 如果仿真电梯，那么事件可以是“6层的 按钮按下了”，随之系统状态改成“电梯移动”，并且最后到达状态“电梯位于 6层”i。 学习如何建立离散时间仿真的一个普通例子是仿真一个队列（queue），如顾客到达银 行接受出纳员的服务，这里的系统实体是“顾客队列”（CUSTOMER-QUEUE）和“出纳 员”（TELLERS）。系统事件是“顾客到达”（CUSTOMER-ARRIVAL）和“顾客离开” （CUSTOMER-DEPARTURE）（事件“出纳员开始服务”（TELLER-BEGINS-SERVICE ） 可以是到达和离开事件逻辑的组成部分) 。可以由这些事件改变的系统状态有“队列中的顾 客数量”（NUMBER-OF-CUSTOMERS-IN-THE-QUEUE (是一个从 0到 n的整数) ）和“出 纳员状态”（ TELLER-STATUS (忙或空闲)）。 为了仿真系统随机性需要的随机变量 （random variables）是“顾客到达间隔时间”（CUSTOMER-INTERARRIVAL-TIME）和 “出纳员服务时间”（TELLER-SERVICE-TIME）。 目前已经提出的实现离散时间仿真的基本方法有基于事件的（event-based）、基于活动 的（activity-based）、基于进程的（process-based）和三阶段（ three-phase，Pidd1998）等 方法。三阶段方法在很多商业化仿真软件包中得到了应用，但从用户角度看，所采用的仿真 方法的细节一般是被隐藏掉的。 1. 基于事件的（event-based）离散事件仿真 2. 基于活动的（activity-based）离散事件仿真 3. 基于进程的（process-based）离散事件仿真 4. 三阶段（ three-phase）离散事件仿真 二、离散事件仿真系统的组成 除了系统状态变量和系统事件发生逻辑外，离散事件仿真还包括以下组成部分： 1. 时钟（Clock） 仿真系统必须要保持对当前仿真时间的跟踪。在离散事件仿真中，与实时仿真（real time simulations）不同，时间是跳跃的（ time ‘hops’ ），因为事件是瞬时发生的– 随着仿真 的进展，时钟跳跃到下一事件的开始时间。 2. 事件列表（Events List） 仿真系统至少要维护一个仿真事件列表，这个列表有时称为挂起事件集（ pending event set ），因为这个列表列出了所有因为先前执行的仿真事件而挂起但仍需仿真的事件。一个 事件用事件发生的时刻和类型来描述，事件类型标识用于仿真事件的代码，一般事件代码都 是参数化的，事件描述中还包含表示事件代码的参数。 因为事件是瞬时发生的，具有一定事件跨度的动作(activities )则用事件序列（sequences of events）来仿真 t。有些仿真系统框架允许事件时间用间隔时间来表示，间隔时间用事件 的开始时刻和结束时刻表示。 基于瞬时事件的单线程仿真引擎只有一个当前事件。相反，支持基于间隔事件模型的多 线程仿真引擎可以有多个当前事件。 在这两种情况中，都存在事件间同步这个重要问题。 挂起事件集（ pending event set）通常用按事件时间分类的优先队列来表示（ priority queue）。，那就是说，不管事件加入事件集的顺序怎样，他们都是严格按时间顺序移除。 几个通用优先权队列算法证明对离散时间仿真是有效的[3] ，最著名的是分裂树算法（splay tree）。更新的算法包括skip lists 和calendar queues.[4] 通常事件随着仿真的进行而进行动态地调度。如上述银行例子，如果顾客队列 CUSTOMER_QUEUE 是空的且营业员 TELLER 是空闲的，在时间 t的事件 CUSTOMER- ARRIVAL会创建在时间 t+s发生的事件 ，其中 s 是由服务时间 SERVICE-TIME分布产生 的一随机数 。 3. 随机数发生器（Random-Number Generators） 根据系统模型，仿真系统需要产生各种类型的随机变量（random variables ）。这由一 个或多个伪随机数发生器（Pseudorandom number generators）产生。采用伪随机数，而不是 实际的随机数，是为了保证仿真系统在重复运行中具有完全一致的行为。 在离散事件仿真中有关随机数的一个问题是事件时间的稳定状态分布事先可能是不知道 的。因此，放入挂起事件集（pending event set）的初始事件集（ the initial set of events） 没 有代表稳定状态分布的达到时间（ arrival times ）。一般采用引导仿真模型的方法来解决这 一问题，让放入挂起事件集的事件去调度其他事件，随着仿真的进行，事件时间分布就会达 到稳态分布，这种方法称为引导仿真模型（ bootstrapping the simulation model）。从运行模 型中收集统计数据时，要么丢弃达到稳定状态之前的数据，要么让仿真运行足够长的时间以 便稳态数据可以消除引导过程的影响。 (This use of the term bootstrapping can be contrasted with its use in both statistics and computing.) 4. 统计（Statistics） 仿真系统通常会 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 系统的统计数据，用以表示感兴趣的一些统计量。在上述银行例子 中，一个感兴趣的统计量是平均服务时间。 5. 结束条件（ Ending Condition） 因为事件是自举的，理论上来说离散事件仿真系统可以永远运行下去。因此，仿真系统 设计者必须决定仿真什么时候结束。典型的选择是“在事件 t”（ “at time t” ）或者“在处 理 n个事件后”（ “after processing n number of events”）或者，更一般地，“当统计量 X达 到值 x时”（ “when statistical measure X reaches the value x”）。 三、仿真引擎逻辑（Simulation Engine Logic） 离散事件仿真系统主循环结构如下： 1. 开始（Start） • 初始化结束条件（Ending Condition）为 FALSE。 • 初始化系统状态变量。 • 初始化时钟（Clock） （通常从仿真时刻 0开始) 。 • 调度（Schedule）以初始化事件 (例如，将初始事件缴入事件列表（Events List）)。 2. 循环（“Do loop” or “While loop”） While (结束条件（Ending Condition ）为 FALSE) then do： • 将时钟设置成下一事件发生时刻。 • 执行下一事件，并将其从事件列表（Events List）中移除。 • 更新统计数据。 3. 结束（End） • 产生统计 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 。 一、离散事件仿真的基本概念 1. 基于事件的（event-based）离散事件仿真 2. 基于活动的（activity-based）离散事件仿真 3. 基于进程的（process-based）离散事件仿真 4. 三阶段（ three-phase）离散事件仿真 二、离散事件仿真系统的组成 1. 时钟（Clock） 2. 事件列表（Events List） 3. 随机数发生器（Random-Number Generators） 4. 统计（Statistics） 5. 结束条件（ Ending Condition） 三、仿真引擎逻辑（Simulation Engine Logic） 1. 开始（Start） 2. 循环（“Do loop” or “While loop”） 3. 结束（End）