陈彦舟 冯朝辉

中国人民公安大学信息安全系 北京 102600

0 引言

数据库管理系统(DBMS)的一个主要功能是进行数据控制，其中并发控制又是数据控制当中的一个重要内容。并发控制要解决的问题就是串行化调度与死锁检测，进而破坏死锁，使系统得以继续运行。通常使用各种协议来对并发事务对数据库的访问进行控制。目前最常用的封锁协议是2PL协议。但是满足2PL协议的调度却有可能会带来死锁和活锁问题。

Petri网是一种能很好地描述和分析验证系统动态性能的工具。研究人员们很自然地用Petri网去描述和学习并发控制系统。如在FMS中，Petri网得到很好的应用。文献[1]通过建立并发事务共享数据资源的普通Petri网模型，探讨了可串行化调度与死锁检测问题，但是当系统涉及的事务与数据资源较多时，所构造的Petri网模型过于复杂，出现状态“爆炸”现象。

1 并发事务带封锁机制的增广有色Petri网模型

本文讨论的数据库系统有n个并发事务Ti(1 ≤i≤n)和m个共享资源Dj(1 ≤j≤m)。各事务对共享资源的加锁情况用矩阵Ln×m表示元素lij定义如下：

定义1：抑制弧/容许弧

（1）FI⊆ (P×T)为抑制弧集，F∏⊆ (P×T)为容许弧集，且FI∩F∏=φ，(FI∪F∏) ∩F=φ；

（2）W: (FI∪F∏) → {0}。

定义2：设PI(P∏)表示与抑制弧(容许弧)关联的库所之集合，t在M下可使能发生，当且仅当：

若M[t＞，则t在M下可以使能发生M[t＞M′，则M′的定义是：

2 建立ECPN_LM模型

定义 3：一个描述并发事务竞争共享资源的带封锁机制的扩展有色Petri网是一个九元组：

ECPN_LM=(P，T；F，FI，F∏，C，I-，I+，M。)

其中：P是库所的有限集合；T是变迁的有限集合；F=PT∪TP是普通有向弧的有限集合；FI是抑制弧集合；F∏是容许弧集合；……