【毕业学位论文】（Word原稿）Petri网系统的可达性研究-计算机软件及理论

分类号 密级 编号 中国科学院研究生院 硕士学位论文 系统的可达性研究 指导教师 杨 路 研究员 中国科学院成都计算机应用研究所 申请学位级别 硕 士 学科专业名称 计算机软件及理论 论文提交日期 论文答辩日期 培养单位 中国科学院成都计算机应用研究所 学位授予单位 中国科学院研究生院 答辩委员会主席 I 摘 要 . . 言 . 一章 背景知识 . 1 历史与发展 . 1 研究方法及应用 . 1 的直观理解 . 2 的形式化描述 . 2 第二章 与代数系统的关系 . 6 模型映射到代数系统 . 6 基于 的 系统性质分析 . 8 号计算软件介绍 14 . 12 计算代数方法的局限性 . 14 第三章 能量优化模型 . 15 系统映射到线性空间 . 15 弱可达性及其分析 . 17 能量优化模型建立和分析 . 20 第四章 可达性的神经网络解法 . 24 神经网络介绍 15 . 24 络模型 . 26 能 量优化模型的神经网络解法 . 30 算法的实现 . 32 第五章 综合分析方法 . 34 几种方法的综合比较 . 34 综合分析方法描述 . 34 综合分析方法总结 . 36 第六章 应用实例分析 . 38 结尾 问题与展望 . 48 致 谢 . 49 附 录 . 50 系统的可达性研究 作者：吴文渊 专业方向：计算机软件及理论 导师：杨路研 究员 摘 要 本文对 系统的可达性问题做了综合性的阐述和分析， 提出了利用能量优化方法来解决可达性问题，并在此基础上结合计算代数方法和神经计算模型对可达性问题做了进一步的研究。作者的主要工作在以下四个方面： 1. 给出了 到线性空间的映射规则及其可达性的等价性定理； 2. 建立了能量优化模型 , 将可达性判断化为优化问题； 3. 用神经网络来求解能量优化模型； 4. 最后综合了计算代数方法和能量优化模型的优点给出一个基于计算代数和神经计算的方法。本文的 特点就在于提出了一种利用基于硬件的大规模并行的神经计算来代替基于软件的串行的数字计算的可达性判断解决方案。 在前言中，着重阐述了可达性问题的研究意义，主要困难和目前使用的五类研究方法，在做了简单的评价后，引出我们的研究目的和研究成果。在第一章，简要回顾了 模型的背景知识和研究的历史与发展状况，研究方法和应用范围等背景知识。之后，又介绍了 模型以及相关知识，将该领域的知识框架做了大体说明。 在第二章，主要介绍了计算代数方法。先描述了将 模型映射到代数系统的基本思想， 模 型的行为特征对应的代数表示，将可达性问题归结为代数问题。接着讲解了必要的计算代数方面的基础知识，主要讲解了计算代数方法的核心工具 ，以及计算 的著名数学软件 使用方法和 软件包。最后，分析了计算代数方法的局限性。 从第三章开始大部分是作者的工作，在第三章中主要给出了利用能量优化模型及其可达性的等价性定理来解决可达性问题。先说明了该方法思想的出发点和形成过程，之后在该模型下自然诱导出弱可达性概念及其性质。提出利用整数规划方法来处理弱可达性条件，并介绍了相关 的数学软件。最后描述了能量优化模型建立的过程和方法。 第四章是针对第三章的能量优化模型提出神经网络的模型计算方案。首先，叙述了神经网络的基础知识，神经计算的特点和应用。之后介绍了神经网络的一种全连接模型 经网络，及 络在能量优化模型的应用。接着对 络求解能量优化模型的能量函数和相关参数做了计算和分析。最后对神经计算的软件硬件实现做了简单的说明。 五章总结了前几章叙述的各类方法，对其优缺点进行分析比较后提出了综合分析方法，给出了综合分析方法的算法流程。在第六章，以 停等协议的 后，本文结尾对 在附录中给出了用 写的利用 络求解能量优化模型的算法程序。 关键词： 模型；可达性； ；能量优化模型； 经网络；弱可达性；综合分析方法； f u ( a of by by an of of be by a is In of a of in at In as is of of is in is to of of on of a to is of of is to of In we to to of V of of by is In we a by in A is in to is by is to of By an an 言 自从 1962 年 他的博士论文 1中提出 模型以来，该模型就成为理论计算机科学包括自动机模型和形式语言理论的一个分支。在分析并行系统的状态行为的技术中， 模型具有自然，直观，简单易懂等特点。它是一种形式化模型描述方法，在并行模型分析，协议的验证，自动控制等方面有广泛的应用。可达性分析是系统的状态，行为分析的基础。可达性就是研究系统可能达到的状态和状态间的关系，而连接状态和状态的纽带就是变迁。可达性也是研究系统最基本的行为，其他行为特征比如：可逆 性 、有界性、活性、可覆盖性、 公平性 等 ，都可归结为可达性的研究。但是，随着系统规模的扩大，状态空间的组合爆炸使可达性分析非常困难。利用 模型进行系统分析的复杂度呈指数倍提高，明显阻碍了该方法在实时系统中的应用。各种相关的处理方法被提出，但各有优缺点。 可达性的研究最基本方法就是穷举法，构造可达树，遍历所有的过程和状态，是最彻底也是最低效的方法 ,该方法对于规模较小的问题是有效的，但对于复杂的系统该方法就无能为力了。因为可达性的研究面临的主要困难就是组合爆炸，当问题规模变大，可能的状态数呈几何级数增加 ，解决问题所需的时间空间也呈几何级数增加。这就阻碍了实时并行系统的分析。 目前提出的解决方法主要还有以下几种：转化为代数问题再利用 作判断的方法 2(在第二章我们将着重介绍计算代数的方法 )；转化为矩阵计算问题利用不变量求解线性方程的方法 (与第三章介绍的能量优化方法的出发点一致 )；通过进程代数将问题分而治之的方法 3；还有基于布尔函数计算和二叉决策图压缩状态空间的方法 4。下面先介绍一下后两种方法。 基于进程代数的分而治之的分析方法： 组合爆炸可以通过利用分而治之的方法来加以控制，一般称 为组合分析方法(主要思想是分析一个大系统的各个部分，再将各个部分按层次合成起来。传统的可达性分析方法不能将系统分解，而进程代数和进程计算方法可将一个大系统分解为等价的子系统。 进程代数是关于通信并发系统的代数理论的统称。 20 世纪 70 年代后期，英国学者 别提出了通信系统演算 和通信顺序进程 ，开创了用代数方法研究通信并发系统的先河。之后 ， 出的 等等，这些代数理论都使用通信，而不是共享存储，作为进程间相互作用的基本手段，表现出面向分布式系统的特征。在语法上，进程代数用一组算子作为进程的构件。算子的语义通常用结 化操作语义方法定义，这样进程就可以看成是带标号的变迁系统。进程代数的一个显著特征是把并发性归结为非确定性，将并发执行的进程行为看成是各单个进程行为的所有可能的交错合成。进程代数研究的核心问题是进程的等价性，即在什么意义下两个进程的行为相同。但问题在于，在分解时可能将一个大系统分为子系统的同时， 产生过多的进程图和进程图节点 3。 基于布尔函数计算和二叉决策图压缩状态空间的方法： 主要思想是用布尔函数来表示 的结构和行为，将 的变迁转化为布尔函数的计算。 转化为布尔代数是很自然的， T,S;F,K,W,假定 K=1, 令 T，就可以表示 系统所有的状态空间，而可达标识集必是 , , ， 映射函数 M ： 如果，如果，01 可达状态空间由该集合的特征函数来表示，只要是属于可达状态空间的点，通过特征函数计算，输出为 1，反之亦然。所以无论状态空间的大小，一个特征函数与可达标识集是一一对应的。特征函数： B 2 ,既是 果，如果01 比如： ),)(,)(,(747232 ， 4765317365421 )( 所以，求可达状态集就可以通过循环计算特征函数来得到。 算法： 0 t o= t,o - 0) 中 : 是状态点集对应的特征函数， t, 含义是将变迁 t 作用于布尔函数 是计算 应的可达状态集中能实施 迁 t 所得到的所有新可达状态集所对应的特征函数。 算法中所有的运算都是布尔运算，而布尔运算的实现可通过二叉决策图(相应运算实现，并且可以证明每种运算都是多项式时间完成，在此不再做介绍，相关文献请见 910。 该方法的优点在于求出特征函数后可快速判断某个状态是否可达。但该方法的问题在于： 1. 在运算过程中使用的二叉决策图峰值远远大于最后结果的个数 2. 求出的特征函数只是一个无结构的集合，不能给出标识间的结 构关系，不能构造变迁过程，也无法讨论系统的可逆性。 这些方法都有自己的适用范围和优缺点。我们提出的方法是基于计算代数和神经计算的方法：综合了计算代数方法和矩阵计算方法，建立 了能量优化模型，并用神经网络来实现算法，其特点就在于提出了一种可利用基于硬件的大规模并行的神经计算代替了基于软件的串行的数字计算。 在第一章简要介绍了 的背景知识，第二章介绍了计算代数的方法和相关知识。后四章给出了作者的主要工作。附录中给出上述算法的 序。 第一章 背景知识 1 第一章 背景知识 历史与发展 的概念最早在 1962 年 博士论文中提出来 1。网论从一开始就以物理为基础，当时的理论计算机科学包括自动 机模型和形式语言理论，其概念构架不适合描述物理系统，它缺少重要的并发概念。 是一个状态变迁模型，可用来描述系统中各异步成分之间的关系，同时允许同时发生多个状态变迁，也是一个并发模型。当时的计划是要用一种兼容物理和计算机科学两者的语言和概念构架来形式化描述制约通信进程的所有“自然法则” 11。 1970至 1975 年， 计算结构研究小组积极参与 的相关研究，在 1975 年7 月在 行第一次 和相关方法的研讨会。从 1980 年召开第一次 年一次的国际研讨会连续不断， 理论和应用的研究成果也不断涌现，到 1987 年已有 2074 篇重要的相关论文发表12。 随着研究的不断深入， 理论也在不断地充实和完善，其抽象和描述能力也不断的朝着横向纵向发展。它的纵向扩展表现为：从基本的条件 /事件 (C/E)网，位置变迁 (P/T)网，发展到谓词 /变迁网和着色网等高级网。它的横向扩展表现为：从无参数的网，发展到时间 和随机 。 研究方法及应用 模型就是一个基于图的数学形式化描述模型，用来分析离散的 并发系统，或者说 模型用来描述非同步的因果和非因果行为，包括并行和不确定选择。 理论研究的主要内容是系统模型的行为特征，包括：可逆性(有界性 (活性 (可达性 (可覆盖性 ( 公平性 ( 。 以研究模型的组织结构和动态行为为目标，着眼于系统中可能发生的各种状态变化及变化之间的关系。 模型的主要分析方法依赖于对 诸如 关联矩阵 、 可达树 、 状态方程 、 位置 不 变量、变迁不变量 等的研究与分析。 在 研究与应用的发展历史中，它的应用范围已经远远超出了计算机科学的领域，成为研究离散事件动态系统的一种有用工具。如今， 模型在众多方面得以应用。两个成功的应用领域是性能评价和通信协议，其他很有前景的应用领域包括分布式软件系统，分布式数据库系统，并发并行计算，柔性制造系统，多处理机系统，逻辑推理，办公自动化系统，形式语言，神经元网络和决策模型等。以 协议工程形式化方法 为例： 协议的验证是基于对 模型分析而进行的。概括地讲，协议工程形式化方法是要为协议 设计的整个阶段提供规范化的指导，这包括描述 (验证 (实现 (测试 (几个主要阶段，每一阶段都有相应的方法和技术 。通过位置 /变迁（ P/T）网 模型 就可以 很好的描述并 分析 整个系统 。 系统的可达性研究 2 的直观理解 用 描述的系统有一个共同的特征：系统的动态行为表现为资源 (物质资源和信息资源 )的流动。在提供 (式描述之前，通过分布系统几个基本行为模型描述的例子，先对 作一个直观的说明。 一个 的结构元素包括：位置 (变迁 (、弧 (位置用于描述可能的系统局部状态，例如：计算机和通信系统的对列、缓冲、资源等。变迁用于描述修改系统状态的事件，例如：计算机和通信系统的信息处理、发送、资源的存取等。弧通过其指向来规定局部状态和事件之间的关系：它们引述事件能够发生的局部状态；由事件所引发的局部状态的转换。 在 模型中，标记包含在位置中，它们在位置中的动态的变化表示系统的不同状态。如果一个位置描述一个条件，它能包含或不 包含一个标记，当一个标记表现在这个位置中，条件为真；否则为假。如果一个位置定义一个状态，在这个位置中的标记个数用于规定这个状态。例如：在计算机和通信系统中，标记可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。 一个 模型的动态行为是由它的实施规则规定的，当使用等于 1 的弧权时，如果一个变迁的所有输入位置 (这些位置连接到这个变迁，弧的方向是从位置到变迁 )至少包含一个标记，那么这个变迁可能实施 (相关联的事件发生 )。对这种情况，这个变迁称为可实施的。一个可实施的变迁导致从它所有的输入位置中清除 一个标记，在它的每一个输出位置 (这些位置连接到这个变迁，弧的方向从标迁到位置 )中产生一个标记。当使用大于 1 的弧权时，在变迁的每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可以实施；这个变迁的实施 将清除在该变迁的每一个输入位置的相应的标记个数，并在变迁的每一个输出位置产生相应的标记个数。变迁的实施是一个原子操作，清除输入位置的标记和在输出位置产生标记是一个不可分割的完整操作。 的形式化描述 本节的目的是把上一节的概念形式化。 一网及其图形表示 定义 1元组 N=(S, T ; F) 称为有向网的充要条件是： 1. S T= (二元性 )； 2. S T (网非空 ); 3. F S T T S; 4. ) ) = S T ; 其中 ) =x| y : (x,y) F， ) =y| x : (x,y) F S 和 T 分别称为 N 的位置集和变迁集， F 为流关系 (位置集和变迁集是有向网的基本成分，流关系是从它们构造出来的。位置和变迁是两类不同的元素，所以 S T= ，而 S T 表示网中至少有一个元素。每一个位置第一章 背景知识 3 表示一种资源，变迁是资源的流动，由流关系规定，所以变迁只能与位置有直接关系： F S T T S。 ) ) = S T 表示不存在不参加任何变迁的资源和不引起资源流动的变迁。 二网系统定义 有向网是系统的结构框架，活动是框架上的是系统中流动的资源。网系统必须需指明资源的初始分布，规定框架上的活动规则，即位置的容量和变迁与资源之间的数量关系。 记 : N=1,2,3, , 0 N, ： + ,对于有向网 N=(S, T； F)。 定义 1 K: SN 称为 N 的容量函数（ 2对于给定的容量函 数 k M: S 为 N 的一个标识（ 条件是： s S M(s) K(s) 3 W： FN 称为 N 上的权函数，对 (x,y) F W(x,y)=W(x,y) 称为 (x,y)上的权。权函数规定每个变迁发生一次引起的资源量上的变化，显然对任何 (x,y) F，有 0。 3如果 t T 在标识 M 下是可实施的，那么 t 可以实施并产生一个新的后继标识 M ,M 可由下列方程给出： s S: M(s)=M(s) W(s,t) W(t,s)。 4系统标识 M 经过 t 的实施得到新的 标识 M ，可以表示成 MtM或者 MM 。 定义 1实施序列 令 =(S,T； F, K,W, 一个 P/ =的一个有限实施序列 i,1 i n:i ;的长度 =n ， 变迁实施序列。 定义 1可达标识 令 =(S, T； F, K,W, 一个有限的 P/识 M 是由 达的当且仅当存在 一个变迁实施序列，使得 实施得到 M，亦即， M。 系统的可达性研究 4 三网系统分类 C、 A、 使用的系统模型实际上是 K=和 W=1 的网系统， 70 年代 A、 是 网系统的容量函数 1 K=1, W=1 这时每个 S 元只有“有 “无 种状态，可理解为只有“真”和“不真” 两种状态的布尔变量。网论中把这种 s 元称为条件，与条件关联的变迁称为事件。这种由条件和事件构成的网系统称为 条件 /事件网 )。 2 K= , W=1 这是传统上称为 称为 P/ 3 K， W 为任意函数 这种系统通常称为 P/面将着重介绍 四可达标识集 许多应用问题都关心系统可能的状态，可达标识集是解决这类问题的关键。可达标识集 是 任何可能发生序列所能进入的全部状态的集合。 可达性的分析对于协议验证十分必要，因为用 模拟协议的正确性的许多问题都可转化为可达性问题。 P/ 定义 1可达 标识集 P/=(S,T,F,K,W, 可达标识集 满足下列条件的最小集合： 1. 2. 若有 M t T,使 MtM,则 M 由以上定义可得： 定理 1 则存在序列 =t 得 i: 0 。反之已然。 定义 1可达树 首先定义一记号：对于所有 n N， n 1M ,即 s S， 1M (s)= M(s) W(s,t) W(t,s)。 M 的计算可区分为两种情况： 1) 从 r到 果存在标注 M 的结点 z y 且 s S： 1M (s)第一章 背景知识 5 M (s)，那么 M (s)= 其他如果)()(),( 11 2) 其它情况， M = 1M 。 一个 P/的是它所有的元素都是有界的，很自然它的可达树也是有界的。 定义 2可达图 令 =（ S, T； F, K,W, 一个有限的 P/的可达图是由标识 (标记值可能由表示 )为结点的图，其弧线由 达图有下列算法构成。 算法 2：可达图构成 1两个可达树的结点是等价的当且仅当它们有相同的标注 M。 2可达图的结点是它的可达树结点的等价类。从结点 的弧线标注为 t，当且仅当存在 y Y 且存在 z Z，使得在可达树中从 y到 t。 可达图是可达树中相同结点的相重叠。 五 系统模型的行为特征 1. 若对于所有的 M 存在正整数 k， 使得对所有 s S， M(s) k，就说是有界 P/T 系统，或 。 模型的有界性是指网中任何 位置 的标记数是有界的，无界的 模型表示相应的协议层上有无限多的标记数，这样的协议显然是很不公平的。 k=1 时也称为安全系统。 k 为界系统也称 2 t T，若对任一可达标识 M 均有从 M 可达的 ,存在标识 M M，使得 M t，就说变迁 t 是活的。若所有 t T 都是 活的，就说系统是活的。 具有活性表明该协议是无死锁的。 有些系统的界有时不易或无法确定，但可以证明其存在性，这时也可以笼统的说该系统是有界的。定义中的 M为从 M 出发有限步可到达的标识集，也就是以 M 为初始标识时的可达标识集。 M t是 有发生权。 有潜在的发生权，即有限步即可获得的发生权。 3. 模型的可覆盖性 ： 在一个 P/T 系统中，标识 M 称为可覆盖的， 当且仅当系统可达集中存在标识 M，使得对系统中任一 位置 P， M(P) M(P)成立。 4 模型的可 逆 性 ： 在一个 P/T 系统中 ， 若对于所有的 M 都有从 M 可达到 如果 M， MtM，我们可以得到， 从 M 可达到 M。 六 模型的主要分析方法 定义 2关联矩阵和不变量 令 =(S,T;F,K,W,一个有限的 P/ S=s1, ,T=t1, , 1矩阵 C=1 i n， 1 j m)是的关联矩阵 当且仅当 W( W( 2一个 n 元整数列向量 x 叫作的一个 且仅当 x=0，其中 的转置矩阵。 3一个 一个 且仅当 C y=0。 系统的可达性研究 6 假定 即的第 i 元素表示变迁 0 到 M 转换过程中的实施次数，则有 : M=C 于是有下面定理 : 定理 1 一个 是的一个 且仅当 0中 初始标识， M 证明：“ ” 因为 一个 以有 ；又有 M 所以 M=C，即 T 以 0 T 0 M T 0 T 有 0 T ; 由 M 的任意性可知 。 同样有下面的定理。 定理 1 一个 m 维向量 X 0是的一个 且仅当 存在的一个标识 M 初始标识）和一个变迁实施序列从 M 回到 M，亦即，MM，的实施计数向量等于 X。 第二章 与代数系统的关系 模型映射到代数系统 除了用关联矩阵，各种向量的方法来表示 系统的状态和系统变化的过程以外，还有其他的数学描述方法来刻划和定量分析 系统的性 质。 1995年 提出利用代数系统来描述 系统的性质。下面将介绍 系统的多项式的描述方法。 一映射的直观描述 1系统状态映射成多元多项式环上的单项式。 系统位置 i 的 方次 系统状态 M 一个单项式 a 2变迁条件映