A sequential and MR-Lock Reimplemation of : Lock-free Transactions without Rollbacks for Linked Data Structures

Non-blocking transactional structures are now been there for quite a while now. With the transactional structure we want to achieve atomicity of multiple operation of a transaction and consistency of the structure after rollback. Older solutions like software transactional memory (STM) and transactional boost provide synchronization at an external layer over the structure itself. This introduces an overhead which is not necessarily required. Thus, it is a probable problem. To solve this issue, researchers provided with a solution which make structural changes in the existing data structure and make it transactional, lock-free. In this work we present a sequential re-implantation of a the above provided solution. We applied transactional transformation to a linked-list and made a sequential version of it. Next, we introduced multi-resource lock version of the same which will used locking to support multi- thread operation on the linked list. As anyone would expect, we get constant time graph for a sequential version of the transactional structure. But the case for locked based multi thread version is different. We get worse performance as compared to sequential version as we get the overhead of maintain a resource vector. As the number of threads increase the size of resource vector increase and thus contention increases. In future we plan to completely re-implement a lock free transactional linked data structure and yet again compare its result with the results from this paper.