“Petri 网展开从另一种数据表示减少重复交错:它显式保存事件和 token 实例的因果关系,让多个线性执行对应同一个无冲突配置。有限完整前缀依靠标识比较及合适的截断顺序,不能只因两个结点标…”
形式陈述
本页采用所引展开构造的模型条件:有限、所有弧权为一的 1-safe Petri 网,每个可达库所至多一个 token,且每个变迁的输入库所集和输出库所集都非空。其展开是一个通常无限的发生网,包含表示 token 实例的条件结点、表示变迁发生实例的事件结点,以及到原网库所和变迁的标签映射。
发生网的有向路径给出因果偏序。两个事件若竞争同一个输入条件,则直接冲突;冲突传播到其后继。事件集合
展开不把原网里的每个变迁只复制一次。同一变迁在不同因果历史或不同轮次发生时,会产生不同事件实例;正是这些副本让展开自身保持无环。
直觉
状态图把“先做甲后做乙”与“先做乙后做甲”画成两条路径;若二者使用独立资源,这只是同一次并发活动的两种排队方式。展开保留甲、乙没有因果先后的事实,用一个配置代表这些交错。
另一方面,共享输入资源的两项选择不能一起进入配置。因果无先后不自动等于可并发,还必须排除冲突。
例子与边界
两个独立任务只需两个事件
初态在
若再加入
循环为什么复制 token 实例
若网只有
每个
有限完整前缀凭什么截断
在上述有限非退化模型下,有界网虽然展开可无限,却能构造有限完整前缀。“完整”不只要求每个可达marking出现:对每个可达M,须有配置C满足
典型规则将事件e的局部配置(e及其全部因果前驱)与已保留的较小配置比较:若到达相同marking,且后者在合适的 adequate order 中更小,就将e标为cutoff。cutoff事件及其输出条件本身仍保留,只抑制其因果后代;直接删掉cutoff事件可能丢失刚才要求的动作扩展。
adequate order 须良基,细化严格包含,即
允许初始空配置参与比较的变体中,上面的单循环发生一次t后便回到相同marking;保留这次事件,再以空配置代表其未来即可截断。若严格采用原文只比较事件局部配置的版本,则下一次t才与第一次的局部配置比较并被截断;两者都保留执行t的扩展。一般并发网中,任意遇到相同标签就合并不够;比较的是配置到达的完整 marking,并须使用保证完整性的顺序条件。
推论与应用
展开适合分析可达 marking、死锁及因果冲突。其优势取决于并发结构:
偏序约简通常从状态探索中删去冗余交错;展开则显式构造事件及 token 的因果结构。二者目标相近,保存的数据对象和正确性证明不同。Mazurkiewicz 迹把独立动作交换归为同类,可帮助理解交错如何对应同一个配置。
本页没有声称任意无界网都能靠同样规则得到有限完整前缀。离开 1-safe 或有界范围时,需要额外的多重 token 处理和明确的终止条件。空输入、空输出变迁也需另定发生实例约定;例如没有输入也没有输出的空动作可重复触发,却不能不加说明地套用由输入条件集合唯一确定事件的构造。
参考资料
- [1] Javier Esparza, Stefan Römer and Walter Vogler, An Improvement of McMillan's Unfolding Algorithm, TACAS 1996,pp. 87–106:完整前缀与 adequate orders。
- [2] 论文公开稿,发生网、配置和 cutoff 的详细定义。