On the Cost of Concurrency in Transactional Memory
Authors:
Preprint
Abstract
The crux of software transactional memory (STM) is to combine an easy-to-use programming interface with an efficient utilization of the concurrent computing abilities provided by modern machines. But does this combination come with an inherent cost? We evaluate the cost of concurrency by measuring the amount of expensive synchronization that must be employed in an STM implementation that ensures positive concurrency, i.e., allows for concurrent transaction processing in some executions. We consider two popular progress conditions: progressiveness and permissiveness. For permissive STMs, we evaluate the number of expensive synchronization patterns that must appear in an execution of a read-only transaction. For progressive STMs, we measure the amount of data that must be "protected" in an uncontended execution of an update transaction. For both progress conditions, our result imply that the amount of expensive synchronization needed to implement a transaction is proportional to the size of the transaction's data set.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Read Invisibility, Virtual World Consistency and Probabilistic Permissiveness are CompatibleLecture Notes in Computer Science, 2011
- Single-Version STMs Can Be Multi-version Permissive (Extended Abstract)Lecture Notes in Computer Science, 2011
- The semantics of progress in lock-based transactional memoryACM SIGPLAN Notices, 2009
- On the correctness of transactional memory2008
- Permissiveness in Transactional Memories2008
- Shared memory consistency models: a tutorialComputer, 1996
- The performance of spin lock alternatives for shared-memory multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1990
- Defining livenessInformation Processing Letters, 1985
- The serializability of concurrent database updatesJournal of the ACM, 1979
- A new solution of Dijkstra's concurrent programming problemCommunications of the ACM, 1974