《实时数据库并发控制协议及其Petri网分析.pdf》由会员分享，可在线阅读，更多相关《实时数据库并发控制协议及其Petri网分析.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、C o m p u t e r E n g i n e e r i n g a n d A p p l i c a t i o n s计算机工程与应用 实时数据库并发控制协议及其 P e t r i 网分析 陈俊，朱艳丽，古乐声 C HEN J u n，Z HU Y a n-l i，GU Yu e s h e n g 河南科技学院 信息工程学院，河南 新乡 4 5 3 0 0 3 S c h o o l o f I n f o r ma t i o n En g i n e e ri n g，He n a n I n s t i t u t e o f S c i e n c e a n d
2、T e c h n o l o g y，Xi n x i a n g，He n a n 4 5 3 0 0 3，Ch i n a E ma i l：c j 6 2 6 h i s t e d u c n CI t EN J u n ZHU Ya n l i GU Yu e-s h e n g Ne w s p e c u l a t i v e c o n c u r r e n c y c o n t r o l p r o t o c o l a n d a n a l y s i s b a s e d o n P e n e t Co mp u t e r En g i n e e r
3、 i n g a n d Ap p l i c a t i o n s，2 0 0 9，4 5(2 1)：1 2 1-1 2 3 A b s t r a c t：A n e w S p e c u l a t i v e C o n c u r r e n c y C o n t r o l P r o t o c o l(N S C C)f o r r e a l-t i m e d a t a b a s e i s p r o p o s e d T h e p r o t o c o l i s b a s e d O i l t h e t r a d i t i o n a l S
4、 C C Ma n g r e s t a r t i n g s a r e a d v o i d e d，a n d t h e c o n c u rr e n c y o f t r a n s a c t i o n i s e n h a n c e d F i n a l l y，u s i n g t h e o r y o f P e t e n e t，i t p r o v e s t h a t t h e p r o t o c o l i s f e a s i b l e a n d e f f e c t i v e K e y wo r d s：r e a
5、l t i m e d a t a b a s e；c o n c u r r e n c y c o n t r o l；N e w S p e c u l a t i v e C o n c u r r e n c y C o n t r o l(N S C C)；P e t e n e t 摘要：该文提出一种适用于实时数据库的新可推测并发控制(N e w S p e c u l a t i v e C o n c u r r e n c y C o n t r o l，N S C C)协议。该协议在传统 的 S C C协议基础之上，进行一系列改进，避免了大量不必要的事务重启，提高了并发度
6、。最后，通过 P e t ri网理论验证其可行性和正 确 性。关键词：实时数据库；并发控制；新可推测并发控制(N S C C)；P e t r i 网 DO I：1 0 3 7 7 8 j i s s n 1 0 0 2 8 3 3 1 2 0 0 9 2 1 0 3 6 文章编号：1 0 0 2 8 3 3 1(2 0 0 9)2 1-0 1 2 1 0 3 文献标识码：A 中图分类：T P 3 1 1 1 3 1 对于实时数据库系统来说，事务执行的最大并发度是非常 重要的性能指标，特别是在系统资源充足时，高并发度可以提 高系统资源的利用率。在截止期内提交的事务所占的比率对实 时数据库系统来
7、说是决定性的性能指标。可推测并发控制l l1(S p e c u l a t i v e C o n c u r r e n c y C o n t r o l，S C C)特别适合实时数据库。一方面，S C C类似于 P C C，能尽可能早地 检测到潜在的有害冲突，启动一个替换调度，从而增加事务满 足时间限制的机会。另一方面，S C C类似于 O C C，它允许冲突 事务并发执行，因此避免了不必要的可能影响事务及时提交的 延迟。这样一来，它就减轻了 P C C的阻塞问题和 O C C的重启 问题，从而更好地满足事务截止期。基于此，提出一种适用于实时数据库的新可推测并发控制 协议(N e w
8、S p e c u l a t i v e C o n c u r r e n c y C o n t r o l，N S C C)。该协议在 传统的 S C C协议基础之上，进行一系列改进，避免了大量不必 要的事务重启，提高了并发度。最后，通过 P e t r i 网理论验证其 可行性和正确性。1 NS C C协议基本执行规则 1 1 初始化规则 设 是就绪事务，当它获得 C P U调度时，系统为它创建一 个乐观影子，并且根据事务 的优先级、截止期限和系统信 息，为其分配一个 n 值，它表示该事务可拥有的影子的最大数 目。初始化 S p e c N u m()为 0，R e a d S e
9、t()和 Wr i t e S e t()均为 作者简介：陈俊(1 9 7 9 一)，女，助教，研究领域：实时数据库，P e t r i 网理论。收稿 13期：2 0 0 9 0 5 0 4 修回 13期：2 0 0 9 0 6 2 2 空集。1 2 冲突规则嘲 在 的执行过程中，检测它与其他并发事务的冲突。假定 为与其冲突的事务集中的任意一个。可能的冲突类型以及解 决方法如下：(1)读规则 当 在执行读操作时，检测出它与 的写操作产生冲突，称为冲突事务 与 的读一 写冲突，记作 R e a d s e t()n Wr i t e S e t(F )。此时，如果事务 对应的影子数目未达到 n，
10、并且不存在 对应于 冲突的投机影子，则要在冲突检测点开始，为事务 建立一个投机的影子。该影子可以通过直接复制乐观影子 得到，且该影子被阻塞直到事务 成功提交。否则，由于缺少负责解决冲突的投机影子，此潜在的冲突 不得不被忽略。(2)写规则 当 在执行写操作时，检测出它与 的读操作产生冲突，称为冲突事务 与 的写一 读冲突，记作 w t e s e t()n R e a d S e t()咖。此时，如果事务 对应的影子数目未达到 n：C o m p u t e r E n g i n e e r i n g a n d A p p l i c a t i o n s 计算机工程与应用 若不存在对应
11、于 冲突的投机影子，则需要从先于 读 操作的某个点为事务 建立一个投机的影子，且该影子被阻 塞直到事务 成功提交；若存在对应于 冲突的投机影子，则先令 夭折再从 先于 读操作的某个点为事务 建立一个投机的影子，且该 影子被阻塞直到事务 成功提交。(3)当 在执行写操作时，检测出它与 的写操作产生冲 突，称为冲突事务 o 与 的写一 写冲突，记作 Wr i t。S。t()n wr i t e S e t()(b。根据 T h o m a s 的写规则，可以通过删除事务发出的过时写 操作来保证执行的可串行化。因此，在这种情况下，忽略冲突继 续执行。1 3阻塞 规则 若事务 预读取数据 X，而与事务
12、 的写操作发生冲突，则事务 必须等待 提交后，才能继续执行操作。因此称事务 被阻塞，记作(r，X)Wa i t F o r()。1 4 准提交规则 当事务 执行完所有的读、写操作时，便进入准提交阶 段。事务 进行准提交操作之后处于己提交状态，不会因为数 据访问冲突而被重启或者因为错失截止期而被抛弃，而且该事 务所做的修改对数据库是有效可读的，活动事务可以读取该事 务的私有缓存来得到该事务所做的修改。此时，判断与之冲突的事务中截止期早的所占比例，若小 于阀值，则进入全提交阶段。当截止期临近时，准提交事务也必 须进入全提交阶段。1 5 提交规则 如果乐观影子 进入全提交阶段，它的执行过程为：(1)
13、将 的投机影子全部作废并中断。(2)对于每一个与 冲突的事务，执行以下操作：如果 有一个对应于 冲突的投机影子 ，那么，将 的乐观影子 中断，将投机影子 提升为新乐观影子。同 时，对于 已经执行了冲突中读操作的投机影子也随之中断。如果 不存在对应于 冲突的投机影子，那么，将，的 乐观影子 中断，在投机影子中选择没有执行冲突中的读操 作且最新创建的影子，将其提升为新的乐观影子。2 NS C C协议的 P e t r i 网及其正确性证明 2 1 NS C C协议的 P e t r i 网 给定事务问的一个并发执行，如果它们访问同一个客体，的行为 和事务 r，的行为 存在冲突，当 和 都执行写 操
14、作，那么使用 T h o m a s 的 T WR规则就可以解决它们之间的 写一写冲突；执行读操作 执行写操作，或者 执行写操作 执行读操作，则使用 N S C C协议来解决冲突。在事务处理过程中的基本执行规则相同，因此两个实时事 务的行为特性和多个事务的类似，不失一般性。假定两个实时 事务 和，分别只完成一个操作并产生冲突，即，r：r()和：()。此时两冲突实时事务的P e t r i 网模型如图 1 所示，该 图描述如下：图 1 N S C C协议的 P e t r i 网 N S C C P N (1)N S C C协议解决冲突的方法是建立投机影子而非加 锁，因此不存在死锁问题。如果实时
15、事务 和 发生读一 写冲 突，两事务的乐观影子 和 继续并发执行，只需要读事务 建立与冲突对应的投机影子 并阻塞。(2)如果写事务 先提交，读事务乐观影子 夭折，同时 投机影子 变成新的乐观影子开始执行。(3)如果读事务 先提交，读事务投机影子 夭折，同时 写事务乐观影子 夭折并产生新的乐观影子开始执行。N S C C协议的 P e t r i 网 N S C C P N=(P，T，F，W，Mo)，其 中：P=-s。，S 一，S。，J(津睛见表 1)，=(S。，T 1)，(S。，)，(S ，T。)，(S ，)，(5 ，)，(S，T。)，(S ，)，(S ，)，(S ，)，(S ，T I。)，(
16、S，)，(S ，)，(S ，)，(S ，r，q)，(S ，T 6)，(S ，)，(S )，(S。，)，(T ，S )，(，S )，(，S )，(r，4，S )，(，S )，(，S )，(，S )，(，S )，(，S )，(T 1 o，S l 1)，(T l l，S】1)=l，1，l l 初始标记 眠 有两个，分别对应以下两种情况：写事务先提交 1 0 =(2，1，0，0，1，0，0，0，0，0，2，0)读事务先提交 慨(2，1，0，0，1，0，0，2，0，0，0，0)表 1 N S C C P N中各库所和变迁 库所 意义 变迁 意义 2 2 N S C C协议的正确性证明 N S C C协议
17、的 P e t r i网 N S C C P N有两个 初始标记 慨 陈 俊，朱艳丽，古乐声：实时数据库并发控制协议及其 P e t r i 网分析 和 分别对应两个不同的可达树 N S C C P N WT(如图 2)和 N S C C P N R T(如图 3)，其中的所有标记如图 2所示。表 2 N S C C P N中的标记 帆：(2，1，0，0，1，0，0，0，0，0，2，O)Mr=(1，0，1，0，1，0，0，0，0，0，2，O)肘F(1，1，0，0，0，1，0，0，0，0，2，0)M3=(1，0，0，1，1，0，0，0，0，0，t，0)M4=(0，0，1，0，0，1，0，0，0，
18、0，2，0)Ms=(1，1，0，0，0，0，0，0，0，1，2，0)M6=(1，0，0，0，1，0，0，0，0，0，1，I)=(0，0，0，1，0，I，0，0，0，0，1，O J Ms=(O，0，1，0，0，0，0，0，0，1，2，0)肘(1，1，0，0，0，1，0，0，0，0，1，0)Ml(0，0，0，0，0，1，0，0，0，0，1，1)M1=(0，0，0，1，0，0，0，0，0，1，1，0)肘l2=(0，0，1，0，0，0，1，0，0，0，1，0)Mu=(1，1，0，0，0，0，0，0，0，0，1，1)MI4=(0，0，0，0，0，0，0，0，0，1，1，1)Ml 5=(0，0，0，1，0
19、，0，1，0，0，0，0，0)M1(0，0，1，0，0，0，0，0，0，0，1，1)Ml 7=(0，0，0，0，0，0，1，0，0，0，0，1)肘lF(0，0，0，1，0，0，0，0，0，0，0，1)M1 F(0，0，0，0，0，0，0，0，0，0，0，2)肘(2，1，0，0，1，0，0，2，0，0，0，0)肘(1，0，1，0，1，0，0，2，0，0，0，0)Mz l：(1，1，0，0，0，1，0，2，0，0，0，O)朋(】，0，0，0，1，0，0，1，1，0，0，O)肘(0，0，1，0，0，1，0，2，0，0，0，0)肘(1，1，0，0，0，0，1，1，0，0，0，0)肘=(1，1，0，0，
20、0，0，0，2，0，1，0，0)M2 6：(1，0，0，1，1，0，0，1，0，0，0，0)肘=(0，0，0，0，0，1，0，1，1，0，0，0)(0，0，l，0，0，0，I，1，0，0，0，0 j M2 9=(0，0，1，0，0，0，0，2，0，1，0，0)埘(1，0，0，0，1，0，0，1，0，0，0，1)M3=(0，0，0，1，0，1，0，1，0，0，0，0)M3 2=(0，0，0，0，0，0，0，1，1，1，0，0)_If =(0，0，0，0，0，0，1，0，1，0，0，0)M3 4=(0，0，1，0，0，0，0，1，0，0，0，1)肘3 5：(0，0，0，0，0，1，0，1，0，0，
21、0，1)肘(0，0，0，1，0，0，0，1，0，1，0，0)肘(0，0，0，0，0，0，0，0，1，0，0，1)M3 8：(0，0，0，0，0，0，0，1，0，1，0，1)l q 图 2 NS C C P N在写事务先提交时的可达树 N S C C P N WT M l 图3 N S C C P N在读事务先提交时的可达树 N S C C P N R T 定理 N S C C协议是正确的。证明 利用可达树分析技术，可知 N S C C协议的 P e t r i 网 N S C C P N具有下列动态特性6 1：(1)N S C C P N中的任一状态都是初始可达的 N S C C P N的初始
22、标识 肘0=眠，眠 从上述可达树中可以 看出，由帆 开始的状态可达集 R()=，M)；帆 开始的状态可达集 R(Ma,)=慨，M1 ，M Mj，8)c因 此，R(Mo)()u ()=眠，l，肘3 8 。S C C P N 的状态集=，M，l。因此，对任一标记 MS，均有 Mi R(Mo)，即 N S C C-P N的任状态都是从Mo 可达的。也就是说，该 P e t r i 网中没有孤立的死标识或无用的标识，这意味着 N S C C协议在执行过程中不会出现无法跳出的状态 或无用的状态。(2)N S C C P N是有界的 在 N S C C P N的可达树 N S C C P N WT和 N
23、S C C P N R T中，任何位置上的令牌数从未超过 2。因此，N S C C P N是有界的并 且其上界为 2。P e t r i 网有界则表明 N S C C协议在任何情况下所 处的状态是确定的。(3)N S C C P N是 U活性的(L 1 一 l i v e)有界 N S C C P N的可达树 N S C C P N WT和 N S C C P N R T包 含了所有可能的标记。从可达树中不难看出，从 开始，VV t T(1，2，1 1)都可以被(眠)中的某个点火序列至 少点火一次，即所有的变迁都是 L l 活性的，因此，P e t r i 网 N S C C P N是 I J
24、 1 活性的。从 P e t r i 网某初态开始一定能够到达相应的终态6 1，这意味 着 N S C C协议从初始状态 眠 开始后无论出现什么情况都不会 死锁，即它们可以正确地结束事务。(4)N S C C P N具有完整性 N S C C P N是有界的，其可达树就是其可达集。从其可达树 可以看到，当写事务先提交时，N S C C P N的所有状态都是 可达的并且可以点火转移到终止状态 M。(O，0，0，0，0，0，0，0，0，0，0，2)；当渎事务先提交时，N S C C P N的所有状态都从 可达并且也可以点火转移到终止状态 因此，无论是写事务 先提交还是读事务先提交，N S C C协
25、议都能正确地维护系统一 致性。(5)N S C C P N具有前进性 无论从可达树 N S C C P N WT还是 N S C C P N R T都可以看 出，任意状态之间没有出现循环，因而任一点火都将系统从初 态逐步地推向相应的终态。相应地，算法在执行过程中不会出 现无意义的动作。因此，同时具备上述五个性质的 P e t r i 网所描述的 N S C C 协议是正确的。3 结束语 根据实时数据库系统的实时特性，提出了一种新可推测并 发控制协议。该协议有助于提高系统资源利用率，增强事务实 时性。对 N S C C协议进行了模拟实验，通过实验证明，N S C C协 议有助于提高实时数据库系统
26、事务处理效能。参考文献：1 B e s t a v r o s A，B r a o u d a k i s S A f a mi l y o f s p e c u l a t i v e c o n c u r r e n c y c o n t r o l a l g o ri t h ms T e c h n i c a l R e p o r t T R-9 2-0 1 7 1t t C o mp u t e r S c i e n c e De p a r t me n t，Bo s t o n Un i v e r s i t y，Bo s t o n，MA，1 9 9 2-0 7
27、 2 T a n i a r D，G o e l S C o n c u r r e n c y c o n t r o l i s s u e s i n g ri d d a t a b a s e s【J J F u t u r e Ge n e r a t i o n Co mp u t u r e S y s t e ms，2 oo 7，2 3：1 5 4 1 62 (下转 2 4 1 页)刘景芝，孙伟，张绍娟：汽包水位粒子群一 lid 优化控制 2 0 0 9，4 5(2 1)2 4 1 ll me s 图2 两个控翻系统动态响应曲线 t i me s 图3 蒸汽漉量扰动下响应曲线
28、(在 t-4 0 0 8 时 加入蒸汽漉量外扰动信号(S t e p 2=1)品质好于传统方法，不仅超调量减小，且其过渡时间也缩短了。从图 3、图 4的仿真结果可看出，运用粒子群算法整定的 l i d控制所具有的抗干扰性，无论是内扰动还是外扰动，系统 仍具有较好的调节品质。5 结论 该文以锅炉汽包水位为被控对象，采用串级三冲量给水控 制系统，运用粒子群算法对系统进行参数整定，并获得了最优 控制参数。M A T L A B 仿真结果表明，基于粒子群算法优化的给水控制 系统与用传统方法整定参数的串级 liD控制比较，系统响应的 超调减小，反应时间加快且鲁棒性好，效果有明显改善。并且由 于粒子群参数
29、整定方法可以方便地用计算机程序实现，因此可 以容易地获得理论最佳参数，从而大大减少给水控制系统参数 整定现场调试工作。t i mds 图4 给水扰动下_ I I 应曲线(在t-4 0 0 8 时加 入培水内扰动信(S t e p l=l t，I I)参考文献：【l】1孙伟 循环流化床锅炉过程控制 M】徐州：中国矿业大学出版社，2 O 0 2 一l 1：1 l 5 1 l 8 【2】K e n n e d y J，E h e r h a r t R P a r t i c l e 8 w a r l n o p t i m i z a t i o n C P r o e e e d i n g
30、s o f I EE E I n t e rna t io n al Co n f e r e nc e O I 1 Ne u r a l Ne t w o r k s，Pe r t h，Au s t r ali a。1 9 9 5：1 9 4 2-1 9 4 8 ”3】S h i Y，E b e r h a r t R C E m p i ri c a l咖d y o f p a r ti c l e 8 W S I T fl o p t i m i z a-t i o n C y P r o c e e d i ng o f C o n g r e s s o n E v o l u t
31、i o n a r y C o m p u t a t i o n P i s c a t-a wa y，N J：I E E E S e r v i c e C e n t e r。1 9 9 9：1 9 4 5 1 9 4 9 4 1 E b e tha r t R C S h i Y P a r ti c l e 8 w a r m o p ti mi z a ti o n d e v e l o p m e n t s a p-p l i c a t i o n s a n d r e s o u r c e s C f P r o c e e d i n g s o f t h e I
32、 E E E C o n g r e s s o n E v o l u ti o n a r y C o mp u t a t i o n P i s c a t a w a y，N J：I E E E Ser v i c e C e n t e r，2 0 o1：8 1 8 6 嘲 王东风 锅炉汽包水位系统的预测函数控制忉华北电力大学学报，2 0 o 3(3)：4 4 4 7 (上接 1 2 3页)【3】陈俊，李陶深 网格环境下实时数据库并发控制协议的研究 c y 2 5 届全国数据库学术会议(N D B c 2 0 o 8)，广西桂林，2 0 0 8 年 1 O 月 2 3日一 2 5日
33、 重庆：计算机科学，2 0 0 8，3 5(1 0 A)：1 5 5 1 5 8 4】B e s t a v r o s A，B r a o u d a k i s S V al u e-cog n i z a n t s p e c u l a t i v e c o n c u r r e n c y c o n t r o l C T r o c e e d i n g s o f t h e I n t e r n a t i o n a l C o n f e r e n c e o n Ve r y L a r g e Da t a Ba s e s Z u ric h S wi
34、t z e r l a n d 1 9 9 5 O 9 5】Wang Y o n g y a n，Wang Q i ang，Wang H o n g a n，e t且 1 D y n a m i cu s t-m e n t o f e x e c u t i o n o r d e r i n r e a l t i m e d a t a b a s e s C P r o c e e d i n g s o f the 1 8 t h I n t e rna ti o n al Pa r a l l e l and Di s t r i b u t e d Pr o c e s s i
35、n g S y mp o s l u m S a n ta F e。Ne w Me x i c o：I EEE Co mp u t e r S o c i e t y。2 0 04)4 6 1 吴哲辉 P e t r i 网导论【M】北京：机械工业出版社，2 0 0 6 (上接 2 2 5页)【7】R a d i o l o g l c a l S o c i e t y 0 f N o r t h A me ri c g-I e alt h c a r e I n f o r m a t i o n and Man a g e me n t S y s t e ms S o c i e t
36、y I HE t e c h n i c f r a mew o rk，Re s i o n 5 5，H I MS S RS N A R 2 0 0 3-1 1 8】8 I n t e g r a ti n g the H e al th c a r e E n t e r p ri s e I H E t e c h n i c al f l B l e w o rk v o l u me I in t e g r a ti o n p r o f d e s，R e s i o n 8 0 E B O L (2 0 0 7-0 8-3 0)h a p：www i h e n e t T e
37、 c h ni c al_F r a me w o r k i n d e x c f m#1 T【9】Ko ff D A，M D I n t r o d u c i n g i n t e g r a ti n g the h e al t h c a m e n t e r p ri s e-C a n a d a J C a n a d i an A s s o c i a ti o n o f R a d i o l 0 g i s tz J o u r n al，2 0 0 5，5 6 (4)：2 2 5 2 3 1 (上接 2 2 8 页)例的搜索精度、寻求决策规则的支持度和可信度
38、、集结算子的 优化与改进等，这些都是今后粗糙集理论在智能决策支持系统 中发展的新方向。参考文献：【l】朱兴东，范敏种改进的属性约简算法及其D E L P m实现硼 计算 机工程与应用，2 O O 7，4 3(2 1)：1 6 8 1 6 9 【2】P a w l a k Z，B ans z e r C D e p e n d e n c y o f a t t r i b u t e s i n i nfo r m a t i o n s y s t e r n s J B u l l e n t in o f t h e P o h s h A c a d e m y o f S c i e n c e s Ma the m a t i c s，1 9 8 5，3 3(9 1 0)【3】王珏，苗夺谦，周育键 R o u g h Set 理论与应用的综述叨 模式识别与 人工智能，1 9 9 4，9(4)：3 3 7-3 4 4 4】徐玖平，吴巍 多属性决策的理论与方法【M】清华大学出版杜。2 0 0 6