A TimeStamp Based Multi-version STM Algorithm
A TimeStamp Based Multi-version STM Algorithm
复制标题
基于时间戳的多版本STM算法
DOI：
10.1007/978-3-642-45249-9_14
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
K. Vidyasankar
中科院分区：
文献类型：
--
作者：
Priyanka Kumar;Sathya Peri;K. Vidyasankar
软件事务存储系统STM是共享存储系统中并发控制的一个很有前途的选择。多版本STM系统为每个t对象维护多个版本。存储多个版本的优点是，它有助于成功执行更多数量的读取操作。多版本许可mv-permissiveness是多版本STM的一个进度条件，它声明只读事务永远不会中止。最近提出了一个STM系统，它只维护一个版本，但mv允许。这就提出了一个自然的问题：多版本STM可以实现多大的并发性。我们发现，在多版本的STM比单版本的系统中，更少的事务被中止。我们还表明，任何STM系统，是允许的w.r.t不透明必须保持至少尽可能多的版本的数量活的交易。这一结果的一个直接含义是，没有单一版本的STM可以允许w.r.t不透明度。
本文提出了一个基于时间戳的多版本STM系统，该系统满足不透明性，易于实现。我们正式证明了所提出的STM系统的正确性。虽然文献中已经提出了许多多版本STM系统满足不透明性，但据我们所知，它们中没有一个被正式证明是不透明的。我们还提出了垃圾收集过程，删除不需要的版本的事务对象。我们表明，与垃圾收集的版本数量保持的数量是有限的活交易的数量。
Software Transactional Memory Systems STM are a promising alternative for concurrency control in shared memory systems. Multiversion STM systems maintain multiple versions for each t-object. The advantage of storing multiple versions is that it facilitates successful execution of higher number of read operations than otherwise. Multi-Version permissiveness mv-permissiveness is a progress condition for multi-version STMs that states that a read-only transaction never aborts. Recently a STM system was proposed that maintains only a single version but is mv-permissive. This raises a natural question: how much concurrency can be achieved by multi-version STM. We show that fewer transactions are aborted in multi-version STMs than single-version systems. We also show that any STM system that is permissive w.r.t opacity must maintain at least as many versions as the number of live transactions. A direct implication of this result is that no single-version STM can be permissive w.r.t opacity.
In this paper we present a time-stamp based multiversion STM system that satisfies opacity and is easy to implement. We formally prove the correctness of the proposed STM system. Although many multi-version STM systems have been proposed in literature that satisfy opacity, to the best of our knowledge none of them has been formally proved to be opaque. We also present garbage collection procedure which deletes unwanted versions of the transaction objects. We show that with garbage collection the number of versions maintained is bounded by number of live transactions.