计算机系统的分析与建模.ppt

库所/变迁系统 2）如果Σ中有一条有向边f=(t,s)，其权值为W(f)=3，如图1.13a)所示，为了消除该有向边上的权值，可以用图1.13b)的网结构来代替。 库所/变迁系统 3）如果Σ中有一条有向边f=(t,s)，其权值为W(f)=2，如图1.14a)所示，那么图1.14b)的Petri网结构可以实现与之相同的效能。 库所/变迁系统 当把Σ中每一个带容量限定的库所和每一条加权的有向边都进行相应的取代之后，P/T系统Σ就被改造成为一个原型Petri网 。它们之间满足关系 而且易知 1）对Σ运行过程中可能出现的每个标识M，Σ’的运行过程中都有一个可能出现的标识M’，使得对每个s∈S都有 加权Petri网 对于一个P/T系统，如果规定各个库所的容量都为无穷大，即取消库所集上的容量函数而保留有向边集上的权函数，就得到一种介于原型Petri网和P/T系统之间的网系统模型Σ＝（S,T;F,W,M）。称这种模型为加权Petri网。 加权Petri网的变迁规则为： 基本网系统 基本网系统是最简单的分布式系统模型。由于在EN系统中，对任意标识M和任意s∈S，M(s)的值只有两种可能： M(s)＝0或M(s)＝1，可把每个s∈S看作一个条件， M(s)＝1表示条件s成立， M(s)＝0表示条件s不成立。 相应的可以把每个t∈T看作一个事件，.t和t.分别称为事件t的前置条件集和后继条件集。事件t有发生权当且仅当它的每个前置条件都成立但每个后继条件都不成立。 事件t的发生使得它的每个前置条件消失而每个后继条件都变成成立。在EN系统中，习惯上用B表示条件集，用E表示事件集。 条件事件系统 条件事件系统是以一个完全情态集 作为其第四元组成的四元组，而不象基本网系统那样，第四元只是一个情态 ( 即 ) 。 完全情态集既包含了事件向前发生所产生的新情态，也包含了向后追索得到的各个情态。 在条件事件系统中，每个条件（B的元素）都有机会成真，也有机会成假，每个事件（ E的元素）都有机会发生。 条件事件系统 例1.5 图1.15给出的是一个基本网系统Σ1＝（B,E;F,c0）,其中c0＝{ b1, b2 }。试写出从c0向前发生各个事件和向后追索得到的完全情态集C。 完全情态集 并不是从每个基本网系统都可以得到对应的C/E系统。例如，在图1.15的基本网系统中，若把初始情态集改为c0’ = {b1 }，那么得到的完全情态集为 C’ = {{b1 },{b3 },{b5 }} 在∑’＝(B,E;F,C’)中，条件b2,b4,b6和b7没有机会成真。而事件e3,e5,e6和e7没有机会发生,所以∑’不是一个条件事件系统 并发与冲突 同其他网系统模型相比，Petri网的突出优点之一是它们特别便于描述并发和冲突。 并发的必要条件 并发是指事件之间因果上的无依赖性。按照网论的观点，事件（变迁）的发生只依赖于它们的外延，而与全局情况无关。在图1.15的基本网系统中，事件e2的外延是 事件e3的外延是 由于e2和e3的外延之间没有公共部分，所以它们是两个相互独立的事件。这是基本网系统中两个事件处于并发的必要条件。 顺序关系 考察e2和e4两个事件之间的关系。在情态c0＝{ b1,b2 }下e2有发生权。如果在发生，得到情态c1＝{ b2,b3 }，易知e4在c1有发生权。即，e4的发生权是通过e2（在c0 ）发生获得的。 e2和e4是一种顺序关系。 同步 假如从情态c0发生事件串e2e4，得到的情态为{b2,b5}。这时只有等待事件串e3e5发生后，事件e6才有发生权，反之，如果从c0发生事件串e3e5 ，得到情态{b1,b6}这时也要等待另一事件串e2e4发生后，事件e6才有发生权。可见，事件e6起到了使两个并发的事件串和同步的作用。 哲学家用餐问题 Dijkstra提出的哲学家用餐问题是资源共享系统的一个通俗的典型例子。 5个哲学家坐在一个圆桌旁，圆桌上摆满了中餐食品，每两个哲学家之间摆了一根筷子。一个哲学家要吃食品时，必须同时拿起他左边的和右边的筷子。这时坐在他旁边的两位哲学家就不可能有足够的筷子来吃食品，只能坐在那里思考问题。每位哲学家从“思考”状态进入“吃食品”状态的条件是在他左、右两边的两根筷子未被使用。下图是这个问题的一个Petri网模型。 哲学家用餐问题 上面给出的模型已对问题进行了一定的处理：规定只有当一个哲学家身边的左右两根筷子都未被占用时，他才能拿起筷子（而且同时拿起两根筷子）。这样可以避免每位哲学家都拿起一根筷子不放下，等待别人让步，而结果谁也吃不上。 持续性 可达标识图与可覆盖性树 1 2 变迁发送序列与