关于Petri网中同步距离定义的研究.doc

合 肥 工 业 大 学 学 报 （自 然 科 学 版 ） 第 卷 第 期 年 月：关于 网中同步距离定义的研究王丽丽， 吴哲辉， 方贤文， 刘道浩（安徽理工大学 理学院，安徽 淮南 ；山东科技大学 信息科学与工程学院，山东 青岛 ）摘要：同步距离是描述 个事件间同步的一个重要的恒定性质，反映了 个变迁之间的独立程度。 它 对 系统的设计、分析和优化提供了很大的帮助。 文章研究了 网中的同步距离的定义，通过实例分析指出原有定义适用于含有有向回路的网系统。 随后将原有定义细化，引 入 公 平 性、亚 公 平 性、跨 来 定义新的同步距 离。新定义将处于非公平关系的变迁根据亚公平关 系 分 类 情 况 考 虑；对于处于公平关系的变迁根据 跨 分 种情况，讨论了同步距离的求解，并通过实例解决了原有定义存在的问题。关键词：网；同步距离定义；观察库所；跨中图分类号：文献标志码：文章编号：（） ， ， ， （，；，）： ， ， ， ：；网作为描述异 步 并发现象的系 统 模型 在许多领域 得 到 了 广 泛 应 用，尤 其 是 在 并 发 系统中更显示出 独 特 的 优 越 性。 在 许 多 系 统 设 计中，尤其 是 在 信息 中系统常 常会遇到信息之 间的同步 问 题，譬 如，必 须 考 虑 信 息 的 发 送、传递及接收 等 动 作 间 的 同 步，多 媒 体 系 统 中 媒 体流内的信 息 同 步 以 及 媒 体 流 间 的 信 息 同 步 等。同步论中用同步 距 离 的 概 念 对 各 种 实 际 系 统 中同步问题作统一的定 量 描述。 同 步 距 离 是 对 组事件间 同 步 程 度 的 定 量 描 述，也 是 刻 画 系 统收稿日期：；修回日期：基金项目：国家自然科学基金资助项目（；）；安徽省高校自然科学基金重点资助项目（）；安徽省自然 科学基金资助项目（）；安徽省软科学研究计划资助项目 （）和安徽理工大学青年教师科学研 究基金资助项目（）作者简介：王丽丽（），女，安徽怀宁人，安徽理工大学讲师；吴哲辉（），男，广东连州人，博士，山东科技大学教授，博士生导师；方贤文（），男，河南商丘人，博士，安徽理工大学教授，硕士生导师动态行为的 工 具，非 常 适 合 度 量 基 于 网 的源模型中最大定 向 信 号 的 规 模。 从 同 步 距 离 与 系统设计和分析 的 关 系 可 以 看 出，一 般 来 说，增 加同步距 离 意 味 着 放 宽 事 件 间 的 相 关 性，从 而 获得对系 统 较 大 的 控 制 权；减 少同步距离则是 进一步密 切 事 件 间 的 依 赖 关 系，从 而 使 环 境 可 以对它施 加 的 影 响 和 控 制 变 小 甚 至 消 失，所 以 同步距离 对 系 统 分 析、建模和 优化提供了一定 的帮助。（）；对 任 意 正 整 数 ，都 存 在 （）和 ： 满 足 （）（），则称 亚公平依赖于 。定义 （，；）为 一 个 网， 为 的关联矩阵。 若（）维 非 平 凡 的 非 负 整数向量 满足，则称 为 的一个可重复向量，称 （）为可重复向量 的支集。设 （，；）为 一 个 网， ，定义 ， ， 是网 的一组可重复向量。 如果任意基本概念（ ， ，）都 不 能 被 ， ， ， ，定义设 （，；， ）为 一 个 ， 非负整系数线性表出，而 的任意一个可重复向量都可被 ， ， ，非负整系 数 线 性网， 。 如果存在正整数，使得 ， 表出，则称 ， ， ， 为 的 本 原 可 重 复 向（ ）和 ： 都 有 （）（），且，则称 和 处 于公平关系，如果 中任意 个变迁均处于公平关系，则称 为公平 网。量 集，记 为 ，即 ， ， ，每个 （， ，）称为网 的一个本原可重复向量。为了统一，本文 均 采 用（，）作 为 变 迁 的同步距离记号，当讨论一个网系统 中各个变迁之间的同步距离时，一般假设 为一定义 ，设 （，；， ）为 一 个 正整 数，使 得 ： 都 有 （） （），则称在 中，变 迁 弱 公 平 依 赖于 。个恰当网系统，即， （ ）：。可见一个恰当网系统 必然是一级活的，所以本文假设所讨论的网系统均为恰当网系统。定义设 （，；， ）为 一 个 定义设）为 一 个 （ ， ； ，网， ，如果 ， （ ），都存 在 正 整 网， ， ， 和 的同步距离为：数，使 得 ： 都 有 （）烄 ， 和 不处于公平关系；（ ，） 烅烆（） （）： （） ， ，（），其他。， 定 理 设 （，；， ）为 一 个 ， ，其中， ，网，若存在 （ ）使得 和 在网中处于， ，。并发或冲突关系，则（ ，）。在文献中给出了观察库所作为观察窗口 来求解变迁之间同步距离的方法，为了了解网系统运行过程中 和 的同步情况，添加一个库所元素作为观察窗口， ， ， 中 可以盛放托肯，且容量为无限大，而且为了不影响原系统的动态行为， 中已放入足够多的托肯，则 引发一次，在 中放入一个托肯； 引发一次从 中移走一个托肯。 中拥有的托肯数最大差额为 和 之间的同步距离。图一个非公平的 网典型实例例网 和 分 别 如 图 和 图 所 示，首先讨论 中变迁 与其他变迁之间的同步距离，易知该网存在 个本原可重复向量，即 图一个非公平的 网王丽丽，等：关于 网 中同步距离定义的 研 究第 期通过分析可知，变迁 和 、 、 都不处于公平关系，故根据定义 有（ ，） （，）。 从物理意义上可知 和（，）之间 没有任何的同步关系，但对于任意的正整数 都 存在 变 迁 序 列 （ ） （ ） 使 得 ，即 单独可以发生的次数 是由前面 的循环序列发生的次数决定的，即当循环序列发 生 次后， 最多单独可以发生的次数也只能为。 故在某种程度上 和其他的变迁（，）存在某种依赖关系。按照定义 求得的（ ，） （，） 不能很精确地反映 个变迁之间的真正的依赖关 系。 和 不处于公平关系，按照定义 可以求 得（ ， ） 。 通 过 分 析 网 发 现， 和 之间确实不存在任何的关系，此时按照定义 得 到的同步距离值能够精确地反映这 个变迁之间 关系。分析上述的例子可以发现，当 个变 迁 之 间 不处于亚公平关 系 时 （如 中变迁 和 ），通 过定义 求出的同步距离能精确地反映这 个变 迁之间的关系，当 个变迁之间处于亚公平关系 时 （如 中变迁 和 ），通 过 定 义 求 出 的 同 步距离就不能十分精确地反映这 个变迁之间的 关系。图存在本原可重复向量的网系统对于图，若采用定义 的方法，可得（ ，）；若采用观察库所的方法可得（ ， ）。 通过分析发现，因为在网 中变迁 和 处 于结构上并发关系，又由定理 可知（ ， ），同时结合图形易知（ ， ）。 故此时利用 观察库所求出的同步距离值较精确。对于图，若采用定义 的方法可得： （ ，） ，（ ，） ，（ ，） ； 若采用观察库所的方法可得：（ ，） ，（ ，） ，（ ，） 。通过分析发现， 中 的 和 处 于 公 平 关 系且不 存在本原可重 复 向 量使得它们 为其支 集，同时 和 之间存在有向路，但它们在 初 始 状态下处 于 并 发 关 系，所 以（ ， ）；同 理 可以发现 和 与 和 同 样。 对 于 该 情 况 根据上述 的 结 果 得 出，采 用 定 义 和 采 用 观 察 库所求得 结 果 存 在 分 歧，可 知 采 用 观 察 库 所 求 得的结果更加精确。 中 和 处于公平关系且不存在本原可 重复向量使它们为其支集，同时它们之间存在有 向路，但在任何可达标识下均处于顺序关系，根据 上述的结果可得，采用定义 和观察求得的结果 是一致的。例网系统 、 和 分 别 如 图 、图 和图 所示，本文采用观察库所和定义 来讨论网系统 中 的 和 、网 系 统 中 的 和（，）以及网系统 中 和 的变迁之间 的同步距离。对于图 ，若 采 用 定 义 的 方 法 可 得（ ，）；若采用观察库所的方法，得到（ ， ）。 通过分析发现 和 处于公平关 系，且 网 系 统 存在唯一 一 个 本 原 可 重 复 向 量 使得 和 为其支集。 虽然此时 和 之间存在有向路，且在初始标识下 和 处于并发关 系，但是对于这种情况根据上述的结果得出，采用 种方法得到的同步距离是相等的。例 种不同结构的网系统如图 所示，本 文分别采用观察库所和定义 来讨论网中变迁之 间的同步距离。 利用观察库所可得：（ ，） ， （ ，） ，（，） ， （，） 。图 一个含结构并发的网系统图不存在本原可重复向量的网系统利用定义 可得：（ ，） ， （ ，） ，（，） ， （，） 。通过分析可以发现，当变迁之间存在冲突或 并发时，通过这 种方式求得的同步距离的值不 相等，但是当 个变迁之间处于顺序状态时，通过 这 种方式求得同步距离的值是相等的。量，这些覆盖 和 本原可重复向量的集合记为 。定理 设 （，；）为 一 个 可 重 复 网， 的本原可重复向量集合为 ，覆盖变迁和的 本 原 可 重 复 向 量 集 合 为 ，若（） （）， 满足，则 和（） （）处于公平关系。证明若 存 在 本 原 可 重 复 向 量 使 得（），（）（或 （），（），显然此时 和 不处于公平关系，故若存在本原可重复向量 使得（），则 （）（或 （），则 （），又由文献中的 定理可知，若 和 同属 的一个公平分 支 的 充分 必 要 条 件 是 ， ，且 满 足 （）（） （） （），易 知 定 理 结 论 成立。从定理 可知，若 个变迁处于公平关系，则 其本原可重复向量对应的分量必然成比例。约定 记 定 理 中 的 （） （）（）（），若，记 ，其中 为既约分数。图各种不同的网系统定义设 （，；， ）为 一 个 从例 和例 可以看出，当网系统中 个变迁处于公 平 关 系 且 处 于 冲 突 或 者 并 发 关 系 时， 通过定 义 求 出的 同步 距离有时不是十分精 确，但是当 个 变迁 处于公平 关系且它们之间 存在有向 路，同 时在 任意的可 达标识下均处于 顺序关系 时，通 过 定 义 求出 的同步距离是精 确的。网， ， ，如果 亚公平依赖于 ，且 亚公平依赖于 或 公平依赖于 ，则称 和 在中处于亚公 平 关 系 （）。 记，即 ，（） ， （ ，）（ ）（ ）（ ，）（ （ ，）， （ ）（ ）显然亚公平关系是一种对称关系，为了同单向的亚公平依赖关系相区分，分别用方括号和圆 括号来记它们。在网 中 若 个 变 迁 之 间 处 于 亚 公 平 关 系 时，从例 可以看出，它们之间存在潜在的依赖关 系，若用 来表示它们之间的同步距离，则很难看 出这 个变迁之间存在潜在的依赖关系。为了更加精确地描述亚公平关系的变迁之间同步距离定义定义设 （，；， ）为 一 个 网，。 若 ， ：（ ，） （ ，） ，则称 为 的一个 跨集。 若 为 的一 个 跨集，而且任意 都 不 是 的 一 个 跨集，则称 为 的一个 跨。从定义 可以看出，“跨”的概念和出现网中“切”的概念类似，但“跨”是针对一般 网，而“切”是针对出现网。定义 设 （，；）为 一 个 可 重 复 网， 的本 原 可重复向量集合为 ，若 都有 （）， （） 或 （）， （），那么称满足 （），（） 的 本 原 可重复向量 为覆盖变迁 和 本原可重复向的同步 距 离 值，本 文 引 入 了 一 个 无 界 量 （），（）表示一个可以任意增大的量，但这种增大受到变迁（事先）发生次数的影响。约定关于（）做如下规定：若在网 （，；）中， ， ， 亚 公 平 依 赖 于 ，公平依赖于 ，则（）中的 ；否则，则（）中的 。定义设 （，；， ）为 一 个 王丽丽，等：关于 网 中同步距离定义的 研 究第 期网，（）为可达标识集， ， ，则 和 的同步距离定义为：（）当 和 不处于公平关系时，有 （）， 或， 和 处于亚公平关系； ， 其他。（ ，）（）当 和 处于公平关系时，有（） （）： （） （） 烄， ， 若 和 不属于同一个 跨；（）： （），（）（） ： （）， （，） 烅若 和 不属于同一个 跨，（）（） ： （），但 （）使 并且 （其中若存在覆盖 和 本原可重复向量的集合 且 ，则（） ，（） ，否则（）（） ）；烆（） （）： （）， ，（），其他。， 定义 中（）的取值见约定，、 、 的取值见约定。中变迁之间的同步距离。对于例，在 中 变 迁 与其他的变迁处 于亚公平关系，而且 亚 公 平 依 赖 于 其 他 变 迁，同步距离求解算法所以 根 据 （）中 的 取 值 得 出 （ ，）（），。 其 物 理 意 义 为 变 迁 单 独 的发生次 数 受 到 变 迁 的 发 生 次 数 （无 限 的 正 整数）的限制，易知变迁 与 其 他 的 变 迁 存 在 一 定 的依赖关系。 在 中 由 于 变 迁 和 不 处 于 亚公平关系，所以（ ， ） ，其 物 理 意 义 为通过定义 求解任意 个变迁之间的同步距离的算法如下。算法 任意 个变迁之间的同步距离求解 算法。输入：一般 网（，；，）。输出：任意 个变迁 和 之间的同步距离值（ ，）。算法步骤： 和 不处于公平关系 和 处于亚公平关系 亚公平依赖于 ， 公平依赖于 ，（ ，）（）（ ，）（）（ ，） 和 属于同一个 跨 （ ，） （） （）： 不发生， 可以 发生任意多的 次 数 （，），易 知 和 不存在任何联系，没 有 任 何的同步。对于例，在图 中，由于变迁 和 处于公 平关系，但它们属于同一个 跨，所以有：（ ，）（ ）（ ）： ， （） （）， （）： （ ） 。 在图 中，变迁 和 处于公平关系且不属于同一个 跨，但 （ ）使 并且， （） （） （）：，所以有：， （） 和 不属于同一个 跨，但（）使 并且 （ ，）（） （） ： （）（） （） ： （） 和 处于其他关系 （ ，） （） （）： （） ， ，（）根据算法 和定义 来重新求解上述实例（ ，）（）（） ：， （） （ ）（） ： ， ， （） 。， 同理可得变迁和不属于（ ， ），同一个 跨，但是在任何 可 达 标 识 下 和 均处于顺序状态，所以有：， （ ，） （） （）：， （） ， ，（） 。在图 中，变迁 和 处于公平关系且不属于同一个 跨，但是 （ ）使 并 且 ，所以（ ，）。对于例 中，在 图 中 变 迁 和 处 于 公 平关系且 属 于 同 一 个 跨，故（ ， ），在 图中变迁 和 处于公平关系且不属于同一 个 跨，此时变迁 和 处于冲突关系，所以有 （ ，），同理可得，图中（ ，），在 图中（ ，）。参考 文 献 ， ， ，： 韩江洪，唐 璐，王跃飞，等基于 的 网络建模及性 能 分 析 合肥工业大学学报：自 然 科 学 版，（）： ， ， ，（）：同步距离与系统行为同步距离与系统行为之间的关系可描述为：（ ，） 时，表明 和 发生次数之差 为无穷大，没有任何的同步关系。（，）（）时，即 和 同步距离为有 限的正整数时，表明 和 以（， ）为距离互 相同步。（ ，） 时， 和 互 以 对 方 的 存 在 为 自身存在的条件，网论中把它们看作一个事件，即 。（，）时，