时间：2022-11-12 22:30:01 | 来源：信息时代
时间：2022-11-12 22:30:01 来源：信息时代
实时数据库并发控制 : 实时数据库中事务集的各数据操作执行的排序,亦称数据操作调度。与传统数据库一样,实时数据库并发控制是防止并发执行的实时事务彼此相互干扰的一种功能,所不同的是其正确性准则或协议不一样。对实时数据库而言,放松可串行化是必要的,其理由一方面如实时事务正确性所述; 另一方面来自实时应用的数据往往是“短命”的,故可断定由并发事务所引入的不一致性不会在数据库中扩展太大,即数据库不会被广泛地“污染”,而对局部的不一致性可使用像“补偿事务”这样的技术来补救,使得能很快恢复到一致状态。因此,对于实时数据库,并发控制技术分为可串行化和放宽可串行化两种。
1.锁式并发控制
传统的锁式协议2PL对实时数据库是不够的,可能遇到的两个主要问题就是“优先级颠倒”(低优先阻塞高优先)和死锁。为此,人们开发了多种策略来解决这些问题,其典型的有:
(1)优先级继承: 当发生优先级颠倒时,让“占有者”TH获得(即继承)“请求者”TR的优先级,从而继续执行直到结束(提交或夭折)。它的问题是TR被阻塞的时间可能会任意长,因为这种继承性是传递的,潜在地存在对于TR的阻塞链。
(2)低优先级夭折:当发生优先级颠倒时,夭折低优先级的TH而让高优先级的TR执行。这种策略的问题是: ①对那些已执行很长时间而还需执行很短时间的TH,夭折的代价很大,且重启可能使TH超截止期; ②重启的TH又可能(因优先级被动态升高)夭折TR,这样就导致循环夭折。
(3)优先级顶:其思想是为每一个数据设置一个“优先级顶”,它为要存取该数据的所有事务的优先级最高者。一个事务要获得对一个数据的锁,它的优先级必须严格地高于当前由其他事务锁住的所有数据的最高优先级顶,否则它被阻塞。该策略假定在每一事务执行前就知道其要存取的数据,并且对每一数据维护一个要存取它的各事务的ID及其优先级的表。
(4)有序共享: 引入锁之间的第三种(除共享、排他外)“有序共享”关系。例如,若事务Ti已具有数据对象O的一个读锁RLT_((i))(O),现事务Tj请求加写锁WLT_((j))(O),则建立了一个“有序共享关系”,而后允许WLT_((j))(O)请求。为了保证可串行化,事务必须遵循有序共享规则: 若事务Tj获得一个对于Ti具有有序共享关系的锁,则对应的Tj操作必须在Ti的以后执行,且只有Ti结束(提交或夭折)后,Tj才能提交。
2. 时间戳排序并发控制
时间戳排序(timestamp ordering,TO)法的基本思想是:
(1)按系统时钟或计数器为每一事务Ti赋一时间戳ts(Ti)。所以,时间戳集是一全序集。
(2)若事务Ti请求的操作与Tj已在处理的一操作冲突,且ts(Ti)<ts(Tj),则Ti夭折。
(3)当一事务夭折时,它必须以一新(即更大)的时间戳重新开始。
3. “乐观”并发控制
“乐观”并发控制法(optimistic concurrency control,OPT)假定事务很难发生冲突,因此让其无阻碍地运行到全部操作完成,然后在提交时进行检验,看是否曾发生过冲突并违反了可串行化要求。若通过了检验则提交; 否则就夭折。为此将一事务Ti的执行分成三阶段: 读、验证、写。该策略的关键是如何验证事务,有两种类型的验证方法: ①向后验证: 针对已提交的事务验证; ②向前验证: 针对活跃(尚在运行)的事务验证,著名的OPTBC(OPTimistic Broadcasting Commit)就是其典型代表。还有一些变种策略,如OPT-WAIT-50(等待优先级比它高的冲突事务的50%)。
4. ε-可串行化并发控制
ε-可串行化并发控制策略的关键是控制不一致性的允许度,称为散度控制(divergence control,DC)。典型的DC方法有: ①两段锁散度控制(DC-2PL):扩展2PL的锁相容矩阵; ②时间戳排序散度控制(DC-TO):放宽按事务时间戳的大小来排序冲突操作的处理,并考虑其不一致性累计是否超限而决定冲突处理策略;③乐观散度控制法(DC-OPT):基于通常的OPT方法,为每一数据维护一锁表来控制不一致性。
在线咨询
