根据1993版的《计算机百科全数》,Carl Adam Petri一个在德国波恩为Gesellschaft fuer Mathematik und Datenverarbeitung工作,我花了很长时间猜测为什么他的理论并没有引起当时学术和工商界的本来应得的注意。Petri网络早在19世纪70年代就已经深入的研究过,以我浅见,他们提供了一个分析和研究并发系统优秀的架构,对于Petri网络的最好的和更广泛的讨论在T.Murata的Petri Nets: Properties, Analysis and Applications论文中阐述,IEEE第77次(1989年4月)会议录的541-580。本节主要讲述Petri网络的最主要方面,在下一节我们可以看到怎么样在编写WIN32 API应用程序的时候使用他们。
Petri网络非常的通用,并不仅仅用来模拟多线程应用程序,例如:计算机硬件和工作过程也可以用Petri网络来描述。本文将限定Petri网络的讨论范围为多线程应用程序。
Petri网络是一个有向图,它的节点可以是位置,或转换,前者被画作一个圆,它粗略地描述一个线程的当前状态,后者被画作一个矩形,它粗略的描绘从一个状态到另一个状态变换的行为。边存在于位置和转换之间,也就是说两个状态或位置不能直接彼此互相连接,然而,两个到多个位置能够连接到同一个转换(对于模拟同步来说很重要),一个转换可以连接一到多个位置(模拟非确定的系统很重要)。
为了模拟一个应用程序的动态行为,个别的位置能够标住(在Petri网络中通常在圆圈中画一个黑点来表示)来表示线程当前执行代码处于对应的状态。有一个简单的激活原则:如果所有转换的导入位置(前驱或输入)被标记并且所有转换连接的位置(后继或输出)没有被标记,那么该转换被激活。如果一个转换能被激活,那么它可以删除所有前驱节点的位置标记并标记所有后继的位置。注意,通常架构的Petri网络具有相当的弹性:在自由的Petri网络中,每个位置都有描述一个位置同时至多可以描述多少个标记的能力,并且每个边都关联一个数字,该数字来表示当边被旋转的时候多少个标记被删除或插入到某个位置。本文我们仅仅讨论所谓的1-conservative 的Petri网络,这种Petri网络中每个位置的容量假定为1并且在边连接位置到转换的时候删除一个标记,连接转换到一个位置时增加一个标记。
在上面的优点枯燥的讨论之后,我们来看一个例子-怎么样将GOOFY转换成一个Petri网络。
图1,GOOFY的Petri的网络图
这个网络仅仅描述了两个线程都能访问的while循环部分。网络由10个位置组成,每个线程由四个位置组成,相应对应的有四个状态:
1. 等待两个关键段(p11或p21)
2. 都声明了各自的关键段,但正在等待另一个(p12,p22)
3. 都声明了两个关键段(p13,p23)
4. 释放了第二个声明的关键段,而不是第一个(p14,p24)
剩下的两个位置表示关键段1和关键段2。相对于线程状态的位置指示了线程执行的代码段,而关键段对应的位置标记暗示该关键段是自由的。
就像图2所示,当状态”es1”激活时,从p11到cs2的标记被删除同时一个标记被插入p12。
图2,一个转换被激活后的GOOFY网络图
----未完待续
----未完待续