一种基于目录的软件事务性内存实现算法

A Lightweight Directory Based Algorithm for STM

软件事务性内存(STM)提供同步手段,让多线程程序高效并发执行.STM算法中一般包含记录所访问的共享数据、缓冲投机修改的数据以及处理事务冲突.STM中的主要开销在于维护共享数据访问记录和一致性验证.维护共享数据访问记录主要目的是便于进行验证.冲突检测(conflict detection)判断两个事务能否同时提交,而验证(validation)确保每个线程看到的数据状态是一致的.给出了关于STM一个简单模型,证明在STM中对共享数据的修改是线性的.提出的LDSTM算法通过在目录中维护版本信息,可以在读取各个共享对象时快速确定事务的内存视图是否处于一致状态,可以极大减少冲突检测和验证的开销.该算法可以实现早期发现写-写冲突,减少无效计算.在单线程情况下该算法开销很小.实验数据表明,LDSTM简单高效,冲突检测和验证开销减少明显.

Software transactional memory （STM） systems use lightweight, in-memory software transactions to address concurrency in multi-threaded applications, ensuring safety at all times. The implementation of STM needs to track concurrent accesses, buffer speculative updates, and manage conflicts. Two principal sources of overhead is bookkeeping and validation. Bookkeeping serves largely to implement conflict detection. Conflict detection is the problem of determining when two transactions cannot both be safely committed. Validation is the related problem of ensuring that a transaction never views inconsistent data. A model is given that shows all modifications to shared data by a STM are linearizable. Based on the model, a new lightweight algorithm named LDSTM is presented here that version information of shared data is kept in a directory buffer which can be used to verify whether the view observed by a transaction is consistent at each data item access quickly. The new algorithm detect write-write conflicts early since at most one of the conflicting transactions can ever commit, it can greatly reduce the cost of conflict detection and validation and avoid extra read-data-bookkeeping. In single-threaded mode, the overhead of LDSTM is much less than other STM except buffer-update overhead. Experimental results show that LDSTM is simple, and can substantially reduce the cost of conflict detection and validation.