实时数据库系统之实时并发控制协议.doc

实时数据库系统之实时并发控制协议 2PL：Two-Phase Locking）协议，这个协议要求事务分为两个阶段提出加锁与解锁请求。传统数据库系统中的研究表明，在大部分操作环境中基于锁的协议性能优于乐观的协议[AGR87]。在实时数据库中事务按照截止期或者重要性被分配优先级，冲突解决机制偏向于具有较高优先级的事务。但是2PL并未考虑事务的优先级，当应用于优先级驱动的事务调度系统时，倾向于导致优先级反转与死锁问题，因此一些研究在2PL协议中引入了基于优先级的冲突解决机制以及优先级继承或者优先级顶机制。基于优先级的2PL变体协议主要包括：2PL-HP、2PL-WP、2PL-CPI、2PL-CR等等。 2PL-HP（2PL - High Priority）[ABB88，HAR90]，也称为2PL-PA（2PL - Priority Abort），采用偏向于高优先级事务的冲突解决方法，一旦检测到冲突就立即通过夭折低优先级的事务解决所有的数据冲突。而2PL-WP（2PL - Wait Promote）[ABB92，SHA90]，也称为2PL-PI（Priority Inheritance）[HUA92]，是通过阻塞锁请求事务来解决冲突，其中包含了一种优先级继承机制。针对2PL-HP所进行的实验结果[ABB89，HUA91b]表明基于优先级夭折方法的实时并发控制协议相对于基于优先级继承方法的协议性能显著要好。Stankovic等[STA91b]也发现2PL-HP在实时数据库环境中优于2PL-WP协议，并且认为基本的优先级继承并不适合于2PL协议中的冲突解决。Haritsa等[HAR92]认为2PL-WP减少了高优先级事务的阻塞时间，但是这种阻塞时间仍然不确定。并且，在较高的数据竞争条件下，2PL-WP可能导致系统中的大部分事务在同样的优先级上执行[LEE96]。 毫无疑问，重启接近完成的事务会导致CPU资源的浪费，因为重启要求被夭折事务的所有操作必须重做。而另一方面，阻塞可能导致较高优先级的事务错失截止期。因此，2PL-CPI（2PL - Conditional Priority Inheritance）[HUA91b,HAR92]是2PL-HP与2PL-WP的组合。在这种协议中，只有当冲突的低优先级事务接近完成时才采用优先级继承，否则这个低优先级事务被夭折。与2PL-CR非常类似的一个协议是2PL-CR（2PL - Conditional Restart），按照下面的方法决定是否夭折较低优先级的事务：如果较高优先级的事务的松弛时间大于其剩余执行时间，则较低优先级的事务继续执行，否则夭折。 在实时系统中，优先级顶协议（PCP：Priority Ceiling Protocol）[SHA90]能够限制优先级反转不超过单个关键段的执行时间，并且能够避免死锁。一些研究通过扩展优先级顶协议来调度处理实时事务的并发执行，最初L. Sha等[SHA91]使用读/写语义改进了PCP协议的性能，提出了RW-PCP（Read/Write Priority Ceiling Protocol）协议。为了进一步减少事务阻塞时间，K-W. Lam等在[LAM00]中引入了动态调整串行化顺序的思想增强了RW-PCP协议来处理硬实时事务。Tei-Wei Kuo等[KUO98]则采用两版本方法扩展了RW-PCP协议，重点是利用数据项的一致版本减少事务之间的写-读冲突。这些基于优先级顶的协议的主要优点在于能够提供单阻塞与无死锁特性，从而支持对硬实时事务进行可调度性分析。 王宏安等[电子学报2005]通过引入静态抢占等级的概念，基于EDF动态优先级事务调度系统，提出了一种新的并发控制协议MV-PL（Multi-Version two-phase locking based on Preemption Level）协议。协议中采用多版本机制，使得事务的串行化顺序不再由冲突的锁请求的顺序决定，而是能够根据事务的优先级进行动态地调整，因此能够最小化不必要的事务阻塞，增强高优先级事务的抢占能力。 2乐观的并发控制协议 基于锁的并发控制属于悲观的方法，总是假定事务冲突经常发生，而实际上锁只在最坏情形下才是必要的。乐观并发控制基于相反的假设，事务冲突很少发生，因此允许事务无阻碍地执行直到全部操作完成，然后在提交时进行验证，如果通过了检验就提交，否则夭折。如果系统中事务之间的数据竞争很弱，大部分事务能够通过验证并提交；而如果事务之间的竞争越激烈，越多的事务就将被夭折并重启，从而降低系统资源利用率[AGR87,BHG87,ELM95]。 OCC协议中，事务的执行分为三个阶段：读阶段（Read phase）、验证阶段（Validation phase）与写阶段（Write phase）。而为