A Lock-based Protocol for Software Transactional Memory

The aim of a software transactional memory (STM) system is to facilitate the design of concurrent programs, i.e., programs made up of processes (or threads) that concurrently access shared objects. To that end, a STM system allows a programmer to write transactions accessing shared objects, without having to take care of the fact that these objects are concurrently accessed: the programmer is discharged from the delicate problem of concurrency management. Given a transaction, the STM system commits or aborts it. Ideally, it has to be efficient (this is measured by the number of transactions processed per time unit), while ensuring that as few transactions as possible are aborted. From a safety point of view (the one addressed in this paper), a STM system has to ensure that, whatever its fate (commit or abort), each transaction always operates on a consistent state. STM systems have recently received a great attention. Among the proposed solutions, lock-based systems and clock-based systems have been particularly investigated. This paper presents a new lock-based STM system designed from simple basic principles. Its main features are the following: it (1) does not require the shared memory to manage several versions of each object, (2) uses neither timestamps, nor version numbers, (3) aborts a transaction only when it conflicts (with some other live transaction), (4) never aborts a write only transaction, (5) employs only bounded control variables, and (6) has no centralized contention point