关于JVSTM无锁提交算法探究.docVIP

关于JVSTM无锁提交算法探究 　　摘要：软件事务存储（software Transaction Memory）思想提出的初衷是用来作为并发控制的一个无锁机制。由于早期的STM实施面临着效率的诸多限制，并且不久之后一种无阻塞的思想出现了，它能够有效解决效率问题，简化STM的实施，因此，现在大多数活跃的STM都是采用了阻塞的设计方法，利用锁机制来保证事务提交操作的原子性。该方法在实际应用中有着更加优越的性能表现，当然部分由于它更加简单。然而当我们将阻塞方法应用到多核系统中，特别当事务写操作频繁的时候，该方法将会暴露出可拓展方面的天生缺陷。 关键词：软件事务存储 多版本控制 无锁提交算法 中图分类号：TP332 文献标识码：A 文章编号：1007-9416（2013）12-0120-02 1 引言 近些年，关于事务存储和软件事务存储的相关学术研究层出不穷，研究者们根据自己定义的特征集提出了STM各种实现建议。其中，J.Cachopo和A.Rito-Silva在2006年提出了JVSTM[1]（Java Versioned Software TransactionalMemory），该STM设计特别之处在于重点关注只读事务的执行。在JVSTM中，只读事务拥有极少的开销花费，并且绝不会和别的事务存在冲突的情况。事实上，只读事务在JVSTM中是一种无等待的实现方式。在本文中，我们提出和讨论一个基于JVSTM的新的可拓展并且有效的事务提交算法，该算法能够维持只读事务的原有性能，同时允许写事务能够并行执行，也就是在写回阶段，让写事务可以独立于其他事务运行，先行来执行其验证步骤，否则等待提交事务。 2 JVSTM简介 JVSTM是一种基于字的STM，它能够有效支持事务使用多版本控制（MVCC）方法。每个事务内存使用一种称之为版本盒子[1]（Versioned Box）的数据结构去标记该内存上的使用过的值。一个VBox实例代表了事务在内存中的定义，它拥有一个实体，该实体由多个元素（版本盒子列表）组成，每个元素（VBoxBody）包含一个版本号、该版本的值和一个指向之前版本的引用。 2.1 基于锁的事务提交算法 在事务执行期间，JVSTM会记录每个事务的访问（不管是读操作还是写操作）在事务的本地日志中（分别记录在读集或者写集中）。事务提交的时候，如果事务的读集是有效的，那么它的写集就需要写回，从而生成了一个新版本的值，该值对于其他后来执行的事务来说是可得到的。 基于锁的提交算法使用了一个全局锁，它的作用是提供互斥机制[1]。当所有的写事务提交时，全局锁能够在读集验证与写集写回之间确保原子性。除此之外，唯一的全局计数器提供的版本号仅仅能够改变内部临界区的值。当提交操作更新了全局计数器它设置的点具有线性化。事务在该点改变之后，对于其他开始的事务来说是可见的，也就是当一个新的事务开始执行之后，它需要根据读到的版本号去确定对应的值。 2.2 无锁事务提交算法必要性 上一节我们讨论了，相对于事务在整个执行周期内来说，一个写事务在提交阶段对于临界区操作所花费的时间是短暂的。然而，JVSTM设计之初主要是为了支持读操作频繁的应用开发。考虑到以上因素，这就不难解释提交算法使用全局锁会有如此高效性能。尽管如此，我们任然有充足的理由去实施替代解决方案。 第一、写事务的执行比率会影响性能，如果锁不能拓展的话。不同的应用程序对于读写操作会有不同的需求。有时我们会在段时间内需要执行大量的写事务，这一点在多核应用程序中尤为突出。这样就将大大增加不止一个写事务同时提交的概率。尽管对于单核计算机来说并不是一个问题，但是对于多核计算机来说，将会是个现实问题。因此，在多核计算机中争用全局锁，将会显著降低性能。 第二、由于冲突的存在，在多处理系统中争用将会增加事务重新执行的可能性，从而降低整个系统的吞吐量。在大量事务并行的情况下，冲突可能性的增加还是比较容易理解。然而，当在少于N个处理器的情况下运行N个事务，这个情况就显得不那么显而易见了。 3 无锁事务提交算法 在本章中，我们重点描述一个新的事务提交算法，以取代存在于JVSTM中基于锁的实现。在概念上，该算法相对基于锁算法拥有相同的步骤：（1）读集验证；（2）写集写回；（3）事务完成。在下面各个小节中，我们将解释每个步骤是怎样实现的。 3.1 读集验证 在基于锁的事务提交算法中，验证可以明确检查在读集中每个取值的必威体育精装版版本是否是事务读取的版本（snapshot validation），也可以逐步进行所有事务写集的检查，检查它们的提交版本是否比它们之前开始的事务版本要更新（delta validation）。假设事务T以版本V1开始执行