事件模型
把事件抽象为偏序集中的元素,用转移映射和线性扩展描述它与扫描模型的交互;坐标、类型、载荷只是表示层。标签 数学 / 事件 / 偏序 / 线性扩展 / 扫描线 / 模型
定义
固定状态空间 与有限全序时间轴 。一个事件模型由
组成,其中:
- 是有限事件集;
- 是 上的偏序,表示事件之间的先后约束;
- 把事件作用到状态上;
- 是线性扩展,把事件排到时间轴。
此时 。事件 的作用是转移 ,。若 ,则 一般表示 时刻的若干个操作构成的集合。
表示层
坐标、类型、载荷不是事件模型的必要部分。若给定坐标映射 ,则事件点就是 ;它通过“坐标先后 + 同一坐标上的优先级”诱导 。类型与载荷只用于定义 。
因此,同一个事件集 与偏序 可以有多种坐标表示;每种表示与一个线性扩展 一起给出一个事件模型 。按 、时间或右端点排序,都是选择不同线性扩展的方式。
常见误解
- 认为事件就是修改操作:事件是 中的元素, 才是它对应的转移。
- 认为事件必须带坐标:坐标只是诱导事件顺序的一种表示;抽象事件只需要偏序位置。
- 认为事件必须带类型和载荷:它们只是定义 的数据。
- 认为查询必须是事件:查询也可以在切点读取;若把查询建成事件,需要扩展接口以携带输出。
- 认为同一坐标的事件不需要排序:仍需用优先级或编号得到线性扩展。
- 认为事件模型只属于扫描线:它描述一般的离散事件调度;扫描线只是选取线性扩展的一种方式。