《基于petri net分析并发控制》由会员分享，可在线阅读，更多相关《基于petri net分析并发控制（5页珍藏版）》请在金锄头文库上搜索。
1、基于 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 的 tok
2、en 都不超过 1，是有界的，这代表一种合理性。Figure 3：线程合并与进程终结值得一提的是，如果是一个进程 fork 出两个进程，这个图依然有效。在设计过程中，对并行过程建立 petri 网模型，比较容易验证所期望的性质。以下对几种同步控制方法和并行设计模式进行分析。2. 同步控制方法互斥锁Figure 4：临界资源访问T0 和 T1 两个操作访问了临界资源，为了保证互斥性，引入了 P5，同时又需要保证对方进入，需要在 T2 和 T3 释放 token。这个方案可以保证 P2 和 P4 不同时包含 token，或者说T0 和 T1 随机互斥发生。事实上，这个 P5 就是互斥锁的模型。在程
3、序中，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 网中不需要显式
4、地表达，因为每个变换都自动判断在 P 中的前提条件。 单入多出的变换：发送/广播信号，需要下一级变换等待 多入单出的变换：等待 多入多出的变换：视情况而定3. 并行设计模式最简单的并行行为是模块之间没有数据交互，基本不需要验证。下面讲述的是有数据交互并行行为生产者-消费者这种行为中，消费者是依赖于生产者的，有一种实现方案见 Figure 6。Figure 6：生产者-消费者设计 1T4 为生产过程，T2 为消费过程。两个过程的连接关系保证了先后次序。然而这种方式 P1和 P2 不满足有界性，比如可能有无限个 token 累积在 P1，在现实中表现为生产的产品未及时消费，产生库存溢出。此时要改变
5、设计，用 P2（消费完毕）作为生产的条件，可以保证 P 的有界性，见 Figure 7。系统实现的时候，P1 和 P2 解释为两个条件变量，生产者等待在 P2 上，执行完毕之后发信号给 P1；消费者等待在 P1 上，执行完毕之后发信号给 P2。系统启动时，发送信号给P2。值得注意的是，对于多个生产者- 消费者的情况，程序的结构不发生变化，只是条件变量的等待/唤醒条件发生变化。Figure 7：生产者-消费者设计 2流水线模式流水线是多级的生产者消费者模式老板-工人模式其实 Figure 1 就是这种模式，创建者为老板，被创建者为工人。4. 总结在 petri 网中可以准确地描述并发行为，并且可以根据 petri 网的性质推断现实系统的行为特征，提供自动化的模型检查与验证。
