A Lightweight Directory Based Algorithm for STM

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.