概要

第一节：介绍一般原则和概念：事件调度/时间推进算法，3个常用视角：事件调度、进程交互、活动扫描。 第二节：列表处理的一些概念

相关概念

系统 system 为完成目标随时间推移而交互作用的实体的集合
模型 model 系统的抽象表示
系统状态 system state 描述系统所需的变量集
实体 entity 需精确表示的系统对象或组件 （一台服务器、一位顾客、一台机器）
属性 attribute 实体的特性 （排队顾客的优先级）
列表 list (队列中按照先来先服务原则或优先级顺序排队的顾客) 也被称为集合、队列或链
事件 event 改变系统状态，瞬间发生的事情 （一位新顾客的到来）
事件通知 当前或者未来发生的事件的记录，以及执行该事件所需的相关数据，至少有事件类型和事件时间
未来事件列表 记录未来事件的通知列表，根据事件发生时间顺序排序，也称为未来时间列表
活动 具有一定长度的时间段，当他开始时就知道他的持续时长
延迟 无法确定长度的时间段，结束后才可以知道它的持续长度
（后进先出的排队时间，由于顾客到达的随机性，无法确定当前顾客的排队时长）
仿真时钟 表示仿真时间的变量

活动时间通常指服务时间，到达间隔，人为设定的处理时间 （无条件等待）

  • 确定型：恰好5分钟
  • 统计型：从集合{2， 5， 7}等概率抽取
  • 基于系统变量，实体属性的函数：运输船的装载时间是以吨位和每小时装载率为变量的函数

为了跟踪活动和它的预期时间，活动开始时会创建一个事件通知，包含这个活动的事件（结束）时间

例如，如果当前仿真时钟已推进到第100分钟，此时一个时长5分钟的检验活动刚刚开始，则一个事件通知将被创建，它包含了事件类型（检查结束事件）和事件时间（100 + 5）

延迟时间不能人为预先确定，需要根据系统条件来确定 （有条件等待）

一位顾客在等待队列中的延迟（排队时间）可能却决于之前顾客数和服务时间，也与服务台和设备有关

  • 延迟相关的事件即不以事件通知表示

image.png
TIM截图20200807083843.png
image.png

事件调度/时间推进

:::info 每一次事件推进都会，都会将该事件从未来事件列表中移除，并加入新触发的事件，重新排序 ::: image.png
仿真过程中FEL（未来事件列表）的长度和内容不断变化，FEL主要操作有

  1. 移除即将发生的事件
  2. 像列表中添加新事件
  3. 偶尔取消个别事件

image.png
未来事件生成

  • 例1：时刻0的系统快照是由初始时间和所谓外生事件定义的

image.png

  • 例2：未来事件生成也可以由排队系统仿真中服务完成事件引起

image.png

  • 例3：机器发生故障时交替发生的运作和宕机情况

image.png
每个仿真都必须有一个终止事件，这里称之为E，决定了仿真模型将运行多久，一般有2种方法终止仿真过程

  1. 在时刻0，指定一个在未来时刻T。发生的仿真终止事件。因此，在开始仿真之前，仿真运行的时间长度[0，T]是已知的。例如，T=40小时的车间生产仿真。
  2. 运行长度T是由仿真模型本身确定的。通常情况下，T是某一特定事件发生的时刻。例如，T可能是某个服务中心第100个服务完成事件的时间，也可以是某个复杂系统出现故障的时间，也可以是在军事战役仿真中，我方脱离战斗或将敌人全部歼灭的时间（以首先发生的那个时间为准），也可以是分销中心完成当天所有订单的过程中最后一个货柜发运的时间。
  • 实际上，T很可能是人们进行仿真时所研究的一个重要统计量。

全局视角

事件调度全局视角

关注事件以及事件对系统状态的影响

进程交互全局视角

关注系统进程，即一个实体的生命周期，（其中的事件和活动会占用有限的资源）

在更精确的术语中，进程是一个按时间排序的事件、活动和延迟的列表，并且包括对资源的需求，过程定义了流经系统的实体的生命周期。图3-4展示的是一个“顾客进程”的例子。在图中，我们看到两个顾客进程之间的交互情况：直到前一个顾客的“服务完成事件”发生，顾客n+1才结束等待。通常情况下，许多进程并存于同一个模型之中，并且进程之间的交互可能相当复杂。

image.png

  • 当遇到延迟时，系统会自动将事件置入FEL,将实体放入列表。

    此时会出现当其他进程运行的时候，某个进程被暂时中止运行的情况

活动扫描全局视角

在活动扫描法中， 每次仿真时钟推进时，模型会检查各项活动的开始条件，如果条件得到满足，那么相应的活动就会开始。活动扫描法的支持者认为该方法概念简单，因此可以使用模块化方式建模，更易于维护和理解，也便于其他分析人员将来对其进行修改。然而，这些支持者也承认，该方法需要重复扫描才能确定一个活动是否可以开始，这会导致计算机运行变慢。因此，纯粹的活动扫描法已被“三相法”（three-phase approach)所替代（三相法的概念更加复杂）。它使活动扫描法具有了一些事件调度的功能，支持可变的时间推进步幅，从而避免了不必要的扫描，同时保留了活动扫描法的主要优点。

在三相法中，事件被认为是持续时间为零的活动。如果按照这个定义，那么活动就可以分为两类，姑且称之为B型活动和C型活动：

  • B型活动 必然发生的活动，包括所有首要事件和无条件的活动。
  • C型活动 有条件的活动或事件。

B型活动和事件可以提前排程，就像在事件调度法中那样，它支持可变的时间推进步幅。FEL中只包含B型事件。在每一次时间推进完成之时，也就是说，本次时间推进所涉及的全部B型事件都结束之后，才能进行条件扫描，决定是否有满足条件的C型活动可以开始。总而言之，在三相法中，仿真就是重复执行以下三个阶段的内容，直至完成：

  1. 阶段1 从FEL中移除即将发生事件，推进时钟至该事件时间。从FEL中移除在同一时刻发生的所有其他事件。
  2. 阶段2 执行所有从FEL中移除的B型事件。（这可以释放一些资源，或改变系统状态。）
  3. 阶段3 扫描触发每个C型活动的条件，激活满足条件的C型活动；重复扫描，直到没有额外的C型活动可以开始，并且不再有事件发生时停止。

总结

事件调度法和进程交互法都使用了可变时间推进步幅（variable time advance)，也就是说，当所有事件和系统状态都在同一个时刻产生或改变，则仿真时钟直接推进到FEL中下一个将要发生的事件时间。相反，活动扫描法使用一个固定的时间增量和基于规则的方法，以此来决定这些活动可以在仿真时间的哪一个时间点开始。