Abstract
Software transactional memory (STM) has evolved as an alternative for traditional lock-based process synchronization. It promises greater degree of concurrency and faster execution. This paper proposes a simple, lightweight, and yet efficient implementation of OFTM. The major contribution of the paper is in proposing a new STM algorithm that uses simple data structure. This does not require any contention manager toward ensuring progress condition, atomicity, and serializability of transactions besides maintaining data consistency. Experimental simulation on random data set establishes the merit of the proposed solution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Herlihy, M., Moss, J.E.B.: Transactional memory: architectural support for lockfree data structures. In: Proceedings of 20th Annual International Symposium on Computer Architecture, ISCA ’93, pp. 289–300, May 1993
Shavit, N., Touitou, D.: Software transactional memory. In: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 204–213. ACM August 1995
Marathe, V.J., Scott, M.L.: A Qualitative Survey of Modern Software Transactional Memory Systems. Technical Report Nr. TR 839. University of Rochester, Computer Science Department (2004)
Herlihy, M.: Wait-free synchronization. TOPLAS: ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1997)
Fraser, K.: Practical lock freedom. PhD Dissertation, Cambridge University Computer Laboratory (2003)
Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, pp. 522–529 (2003)
Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for dynamic-sized data structures. In: 22nd Annual ACM Symposium on Principles of Distributed Computing, pp. 92–101, July 2003
Scherer III, W.N., Scott, M.L.: Advanced contention management for dynamic software transactional memory. In: 24th Annual ACM Symposium on Principles of Distributed Computing, PODC ’05, pp. 240–248 (2005)
Maranthe, V.J., Scherer III, W.N., Scott, M.L.: Adaptive software transactional memory. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp. 354–368, May 2005
Tabba, F., Wang, C., Goodman, J.R., Moir, M.: NZTM: non-blocking zero-indirection transactional memory. In: Proceedings of the 21st ACM Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 204–213 (2009)
Ghosh, A., Chaki, N.: Design of a new OFTM algorithm towards abort-free execution. In: 9th International Conference, ICDCIT 2013, pp. 255–266, Bhubaneswar, India, 5–8 Feb 2013
Harris, T., Larus, J., Rajwar, R.: Transactional Memory, 2nd edn., pp. 101–145. Morgan & Claypool, (2010)
Perelman, D., Fan, R., Keidar, I.: On maintaining multiple versions in STM. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pp. 16–25 (2010)
Attiya, H., Hillel, E.: Single-version STMs can be multi-version permissive. In: Proceedings of the 12th International Conference on Distributed Computing and Networking, ICDCN’11, pp. 83–94, Bangalore, India (2011)
http://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node40.html (2014)
Knuth, D.E.: The art of computer programming. Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley, Reading (1997). ISBN 0-201-89684-2
Guerraoui, R., Kapałka, M.: On obstruction-free transactions. In: Proceedings of the 29th Annual Symposium on Parallelism in Algorithms and Architectures, pp. 304–313 (2008)
Guerraoui, R., Kapalka, M.: The semantics of progress in lock-based transactional memory. In: POPL ’09, pp. 404–415 (2009)
Guerraoui, R., Henzinger, T.A., Singh, V.: Permissiveness in transactional memories: In: Proceedings of the 22nd International Symposium on Distributed Computing (2008)
Crain, T., Imbs, D., Raynal, M.: Read invisibility, virtual world consistency and probabilistic permissiveness are compatible. In: Algorithms and Architectures for Parallel Processing, pp. 244–257. Springer, Berlin (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer India
About this chapter
Cite this chapter
Saha, A., Chatterjee, A., Pal, N., Ghosh, A., Chaki, N. (2015). A Lightweight Implementation of Obstruction-Free Software Transactional Memory. In: Chaki, R., Saeed, K., Choudhury, S., Chaki, N. (eds) Applied Computation and Security Systems. Advances in Intelligent Systems and Computing, vol 305. Springer, New Delhi. https://doi.org/10.1007/978-81-322-1988-0_5
Download citation
DOI: https://doi.org/10.1007/978-81-322-1988-0_5
Published:
Publisher Name: Springer, New Delhi
Print ISBN: 978-81-322-1987-3
Online ISBN: 978-81-322-1988-0
eBook Packages: EngineeringEngineering (R0)