资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
基于 petri 网分析并发控制刘云峰,2012 年 7 月 5 日1. 简介petri 网是用来分析并发行为的一种形式模型。举例来说,一个进程创建两个线程,然后等待它们结束,如下图:Figure 1:开始进程T2: 创建; T3: 合并;T1 和 T0 为各自线程的操作。P5 为起始控制点,其中的黑点儿为 token,表示拥有控制权。经过 T2 以后,P5 失去控制权,P0 与 P3 获得控制权,如下图。Figure 2:创建线程如此运行,最后 token 到达 P6,进程结束,见 Figure 3。注意 P4 和 P2 都有 token 时,T3才能激活。这个图里边,所有的 P 的 token 都不超过 1,是有界的,这代表一种合理性。Figure 3:线程合并与进程终结值得一提的是,如果是一个进程 fork 出两个进程,这个图依然有效。在设计过程中,对并行过程建立 petri 网模型,比较容易验证所期望的性质。以下对几种同步控制方法和并行设计模式进行分析。2. 同步控制方法互斥锁Figure 4:临界资源访问T0 和 T1 两个操作访问了临界资源,为了保证互斥性,引入了 P5,同时又需要保证对方进入,需要在 T2 和 T3 释放 token。这个方案可以保证 P2 和 P4 不同时包含 token,或者说T0 和 T1 随机互斥发生。事实上,这个 P5 就是互斥锁的模型。在程序中,P5 的出边实现为 T0 和 T1 之前的加锁操作,P5 的入边实现为 T2 和 T3 之后的解锁操作。此时 P5 中 token 的个数,解释为资源量。读写锁读写锁指的是读锁和写锁,除了读与读可并行以外,其它组合都只能互斥完成。这里用权重为 2 的变换 T4、T5 表示“ 写”操作。这个模型里,所有的 P 有界。而且除了 P2 和 P4可以同时有 token,其它组合只能是 P2,P4,P8,P9 单独有 token。此时 P5 的 2 出边实现为加写锁操作, 1 出边实现为加读锁操作,所有入边都实现为解锁操作。Figure 5:读写锁模型条件变量条件变量在 petri 网中不需要显式地表达,因为每个变换都自动判断在 P 中的前提条件。 单入多出的变换:发送/广播信号,需要下一级变换等待 多入单出的变换:等待 多入多出的变换:视情况而定3. 并行设计模式最简单的并行行为是模块之间没有数据交互,基本不需要验证。下面讲述的是有数据交互并行行为生产者-消费者这种行为中,消费者是依赖于生产者的,有一种实现方案见 Figure 6。Figure 6:生产者-消费者设计 1T4 为生产过程,T2 为消费过程。两个过程的连接关系保证了先后次序。然而这种方式 P1和 P2 不满足有界性,比如可能有无限个 token 累积在 P1,在现实中表现为生产的产品未及时消费,产生库存溢出。此时要改变设计,用 P2(消费完毕)作为生产的条件,可以保证 P 的有界性,见 Figure 7。系统实现的时候,P1 和 P2 解释为两个条件变量,生产者等待在 P2 上,执行完毕之后发信号给 P1;消费者等待在 P1 上,执行完毕之后发信号给 P2。系统启动时,发送信号给P2。值得注意的是,对于多个生产者- 消费者的情况,程序的结构不发生变化,只是条件变量的等待/唤醒条件发生变化。Figure 7:生产者-消费者设计 2流水线模式流水线是多级的生产者消费者模式老板-工人模式其实 Figure 1 就是这种模式,创建者为老板,被创建者为工人。4. 总结在 petri 网中可以准确地描述并发行为,并且可以根据 petri 网的性质推断现实系统的行为特征,提供自动化的模型检查与验证。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号