软件开发自动化作业.doc

太原理工大学硕士研究生 《软件开发自动化》习题 研究生姓名 石淑萍 学 号 专 业 计算机应用技术 学 院 计算机与软件学院 任 课 教 师 段富 指 导 教 师 牛之贤 日 期 2012年03月18日 第三章习题 3.1简述位置/迁移Petri网的迁移使能条件和迁移引发规则。 答：位置/状态Petri网，在含有令牌的Petri网中，依据迁移的使能（Enable）条件，可以使得使能的迁移引发（Fire），迁移的引发会依据依法规则实现令牌的移动。不变变化着的令牌重新分布就描述了系统的动态行为演化。 迁移的使能条件 对于Petri网PN=（P,T,F,K,W,M），如果且，则称t在M下使能，记为。 迁移的引发规则 对于Petri网PN=（P,T,F,K,W,M），任何在M下使能的迁移t将会引发，迁移t的引发使得位置中令牌重新分布，从而将标识M变成新标识，并称为M的后继标识，并记为。对于,可通过下式计算： 3.2简述Petri网模型中的顺序关系、并发关系、冲突关系以及混惑关系。 答：Petri网具有丰富的结构描述能力，Petri网模型有顺序关系、并发关系、冲突关系以及混惑关系。 顺序关系：设M为Petri网PN的一个标识，若存在t1,t2使得且，，亦即，在M标识下，t1使能，而t2不使能，且t1的引发会使t2使能，即t2的使能以t1的引发为条件，则称t1和t2在M下有顺序关系。 并发关系：设M为Petri网PN的一个标识，若存在t1,t2使得和，并满足，且，则称t1和t2在M下并发。就是说在标识下，t1和t2都使能，且它们当中任一个迁移的引发都不会使另一个迁移不使能。 冲突关系：设M为Petri网PN的一个标识，若存在t1和t2使得和，并满足，且，则称t1和t2在M下冲突。就是说M标识下，t1和t2都使能，但它们当中任一个迁移引发都会使另一个迁移不使能。 混惑关系：某些情形下，一个Petri网中可能同时存在着并发和冲突，而且并发迁移的引发会引起冲突的消失或出现。有些情况下，并发和冲突混合在一起产生的困惑，使人无法从终态判断是否有冲突发生过，所以将这种情况称为“混惑”。 3.3从描述并发和冲突的能力角度看，有哪些特殊Petri网？分别叙述它们的特点。 答：从描述并发和冲突的能力角度看，特殊Petri网可以分为：状态机、标记图、自由选择网、扩展自由选择网和非对称自由选择网。 状态机（SM）：在Petri网中，如果每一个迁移恰好只有一个输入位置和一个输出位置，即：，则称该Petri网为状态机。它可以描述并发，但不能描述冲突。 标记图（MG）：在Petri网中，如果每一个位置恰好只有一个输入迁移和一个输出迁移，即：，则称该Petri网为标记图。标记图中不会出现冲突。 自由选择网（FC）：在Petri网中，如果每一个位置的输出弧，或者是该位置的惟一输出弧，或者是某一迁移的惟一输入弧，即：或者，则称该Petri网为自由选择网。它允许并发和冲突同时存在。自由选择网中如果一个位置同时是多个迁移的输入（冲突），则它是所有这些迁移的惟一输入。因此，所有这些迁移或者同时有效，或者任何一个都没有发生权，这就能自由选择其中一个迁移的引发，而其他位置的令牌不会影响这些迁移的引发选择。 扩展的自由选择网（EFC）：在Petri网中，如果满足，则称该Petri网为扩展的自由选择网。它允许并发和冲突混合在一起出现（即混惑）。扩展自由选择网可改造成自由选择网。 非对称的自由选择网（AC）：在Petri网中，如果满足或者，则称该Petri网为非对称自由选择网。它可以描述非对称混惑，但不能描述对称混惑。 3.4阐述Petri网的各种行为性质和结构性质。 答：Petri网具有两类性质：与初始标识有关的（行为性质）和与初始标识无关的（结构性质）。 行为性质有：可达性、有界性和安全性、活性、可逆性、可覆盖性、持续性、同步距离、公平性。 可达性：是研究任何系统动态行为的基础，按照迁移引发规则，使能迁移的引发将改变令牌的分布（产生新的标识）。对于初始标识M0，如果存在一系列迁移t1、t2、…、tn的引发使得M0转换为Mn，则称标识Mn是从M0可达的，记为，其中，或简记为，称为迁移的引发序列。 有界性和安全性：在PN=(N,M0)中，若存在一个非负整数k，使得M0的任一可达标识的每个位置中的标识数都不超过k，即，对，都有，则称位置p为k有界。如果PN中每一位置都是k有界。则称PN为k有界。位置p为1有界，则称位置p是安全的。如果PN中每一个位置都是安全的，则称PN是安全的。 活性：是与系统中与死锁相关的一个性质。在PN=(N,M0)中，若存在使得迁移t使能，则t是