第十一章petri网

1、petri 网251 .第 - 251 - 页第11章petri 网本章研究 petri 网及其在操作系统中的应用。11.1包(bag) 一个包 (bag)是某个定义域上的元素集合，但是包不像集合， 它允许元素的多次出现。一个元素或者是一个集合中的元素，或者不是一个集合中的元素。在包理论中，一个元素可以在一个包中0 次(不在包中 )，或一次，两次，或任意规定次数。例 1。考虑在域 a,b,c,d 上的下列包：b1=a,b,c b4 = a,a,a b2 = a b5 =a,a,a,b,b,c,d,d b3 = a,b,c,c b6 = a,b,c,c 某些包是集合，例如，b1和 b2,，和集合

2、一样，元素的次序是不重要的。所以b3和 b6是相同包（有序包是序列）。11.1.1包的元素关系定义 1 一个元素 x 在一个包 b 中的出现次数为#(x, b) 。对所有的 x 和 b#(x, b) 0。若#(x, b)0，则元素 x 是包 b 的一个成员， 标志为 xb。类似地， 若#(x, b)=0，则元素x 不是包 b 的一个成员， xb。我们定义空包 为没有元素的包。11.1.2包的运算在包上定义四个运算。对两个包a 和 b 定义 : 包联合ab #(x, ab )=max(#(x,a),#(x,b) 包交ab #(x, ab )=min (#(x,a),#(x,b) 包和a+b #(

3、x,a+b)= #(x,a)+#(x,b) 包差a-b #(x,a-b)= #(x,a)-#(x, ab ) 包的联合，交，及和满足交换律和结合律。此外，成立下列包含关系：ab a ab a-b a a+b 包 a 的基数（ cardinality ）|a|是包中元素出现总数：|a| = xax),(#联合与和之间的差别显然是| ab |a| + |b| |a+b| = |a| + |b| 11.1.3包的包含和相等如果一个包a 的每个元素也是包b 的元素，并且至少有那么多次，即包a 是包 b 的子包，标志为a b。a b 当且仅当对所有x 满足#(x, a) #(x, b) 。如果对所有x，

4、#(x, a) = #(x, b) ，则两个包相等a=b 。由上述定义，我们可以立即得到a = b 当且仅当a b 且 b a。对所有包 b，成立 b 。- 252 - petri 网第 - 252 - 页a = b 蕴涵 |a| = |b|。a b 蕴涵 |a|b|。如果 a b 且 a b，则称包 a 被严格地包含在包b 中。记为 a b。注意， a b 蕴涵 |a| |b|，但不能得到 #(x, a) 0 do begin if odd(y1) then begin y3 := y3 y2; y1 := y1 1; end y2 := y2 y2; y1 := y1 2; end; ou

5、tput(y3); end. 注意，框图不规定要做的计算，仅规定程序的结构。上述表格表明一个解释如何能应用到的框图的动作。一个驻在位置中的标号意味着程序计数器准备执行下一条指令，除去前于判断的位置之外每个位置有唯一的输出转移，而在前于判断的位置有两个输出转移，分别对应于判断谓词的结果真和假。转移显然和程序的动作相联，即计算和判断。如果我们希望解释petri 网，我们必须对每个转移提供一个解释。petri 网259 .第 - 259 - 页图 12 11.3.3并行现在我们可以用几种方法引入并行或并发。考虑两个并发进程的情况，每个进程可以由一个petri 网表示。因此，简单地把这两个进程的相应的petri 网联合组成的petri 网，可以表示两个进程的并发执行。组合的 petri 网的初始作标志有两个标志，分别在表示进程初始程序计数器的位置中。这引进了一个并行。另一种途径是考虑在一个计算机系统中如何正式地将并行引进到一个进程中。最简单的一种方法是dennis 和 van horn1966 提出的 fork 和 join 操作。在位置i 执行一个 fork 操作导致当前进程在位置i+1 继续，并且创建一个新的进程