Department of Computer Science
University of Rochester
Our libraries are described in terms of common TM terminology. Two of the most important concepts are the write-acquisition/versioning implementation, and the transactional memory model. We describe these briefly here.
Before making updates to locations, a transaction must acquire write privileges to that location. In a blocking implementation, this is equivalent to saying transaction must lock the location for writing. A non-blocking implementation is likely to have a more complicated concept of write-acquisition.
A transaction may either lock the location as soon as it wants to write, called encounter-time or eager locking, or it may lock the locations at the last minute, called commit-time or lazy locking, just before it commits.
Both locking protocols must provide for deadlock avoidance, typically through a contention manager and rollback.
While write acquisition dictates when a blocking transaction will attempt to lock a location that it would like to write. Write versioning describes what the transaction does with the data that it would like to write.
In-place, or eager, versioning says that the transaction will make the update directly to the corresponding address, given that it has successfully locked the location. This requires that the transaction record the original value of the location, in case it aborts in the future. This record is stored as part of an undo log, so eager versioning is sometimes referred to as undo logging. The primary benefit of eager versioning is that transactional reads that occur after a write to a location can find the correct value at the expected address. Eager versioning requires eager acquisition, for obvious reasons.
Buffered, or lazy, versioning stores writes in a private write-log structure. On successful commit the writes in the write-log are "re-done" to their actual location. For this reason, implementations with lazy versioning are sometimes referred to as redo log implementations. The primary advantage of lazy versioning is its support for lazy acquire. A further benefit of lazy versioning is support for the Java memory model without strong isolation. The primary disadvantage is that every read needs to check the write set to see if the local transaction has an outstanding write to that location.
Our work has shown that lazy-acquisition/lazy-versioning is usually the
preferred
implementation. See our
paper on contention management
at PPOPP 2009 for more
details. For our word-based implementations
that support different combinations, use the -Vav flag on
the benchmark command line to select which one you want.
-Vee eager acquire/eager versioning-Vel eager acquire/lazy versioning-Vll lazy acquire/lazy versioning
Transactional memory models describe what a transaction means at a
fundamental level. We'll assume that a transaction is encoded in the
source as a properly nested atomic block structure. This is
equivalent to correctly
paired BEGIN
and END
transaction macros.
The different RSTM libraries support different transactional memory models, as listed in their descriptions. We briefly describe the major ones here. See Menon et al. for a more detailed discussion of SLA, ALA, and ELA and our paper on selective strict serializability from OPODIS 2008 for more information on SSS and SFS.
From Menon et al., SLA says that a transaction should act as if it acquires and releases a single, global, reentrant lock. This has particularly important implications for Java, where the behavior of programs with data races is defined.
Again from Menon et al., ALA is a relaxation of SLA that says that 1) each unique location is protected by its own lock, and 2) a transaction behaves as if it acquires all of the read locks that it needs at the time that it begins, and the write locks as it runs, before the first time it writes a location.
Again from Menon et al., ELA is a relaxation of ALA that says that a transaction acquires a lock on a location immediately prior to reading or writing it. This allows for race-free publication only.
From our paper on transactional memory models at OPODIS 2008, SSS says that the programmer must annotate transactions as acquiring if they privatize data, and releasing if they publish data.
From our paper on transactional memory models at OPODIS 2008, SFS relaxes SSS to support only publication via transactions that write.