Reading 5. Improvements on DSTM and WSTM

Contention policies

1. Aggressive. The acquiring transaction terminates any conflicting transaction
2. Polite. The acquiring transaction uses exponential backoff to delay for a fixed number of exponentially growing intervals before aborting the other transaction. After each interval, the transaction checks if the other transaction has finished with the object.
3. Timestamp. This manager aborts any transaction that started execution after the acquiring transaction.
4. Published Timestamp. This manager follows the timestamp policy, but also aborts older transactions that appear inactive.
5. Greedy. This manager aborts the transaction that has executed the least amount of time
6. Kindergarten. This manager maintains a “hit list” of transactions to which a given transaction previously deferred. If the transaction holding the object is on the list, the acquiring transaction immediately terminates it. If it is not on the list, the acquiring transaction adds it to the list and then backs off for a fixed interval before aborting itself. This policy ensures that two transactions sharing an object take turns aborting (hence the name).
7. Karma. This manager uses a count of the number of objects that a transaction has opened (cumulative, across all of its aborts and reexecutions) as a priority. An acquiring transaction immediately aborts another transaction with lower priority. If the acquiring transaction’s priority is lower, it backs off and tries to reacquire the object N times, where N is the difference in priorities, before aborting the other transaction.
8. Eruption. This manager is similar to Karma, except that it adds the blocked transaction’s priority to the active transaction’s priority; to help reduce the possibility that a third transaction will subsequently abort the active transaction.
9. Polka. This is a combination of the Polite and Karma policies. The key change to Karma is to use exponential backoff for the N intervals.
   

SXM
SXM is a deferred, object-based STM system implemented as a library for C# code. It is
similar in operation to DSTM system, although implemented in .NET.

Strong or Weak Isolation	Weak
Transaction Granularity	Object
Direct or Deferred Update	Deferred (cloned replacement)
Concurrency Control	Optimistic
Synchronization	Nonblocking (obstruction free)
Conflict Detection	Early
Inconsistent Reads	Inconsistency toleration
Conflict Resolution	Explicit contention manager
Nested Transaction	Closed
Exceptions

Key features:

• polymorphic contention management, which is a framework for managing conflicts between transactions
• run-time code generation to produce some of the boilerplate code

Each transaction selects a contention manager from a collection of managers that implement a
diverse set of policies. All policies are classified based on the cost of the state that they maintain

Rank	Policy Class	Policy	State
1		Aggressive, Polite	–
2	Ad hoc	Greedy, Killblocked	Transaction start time
3	Local	Timestamp	Transaction start time, variable
4		Kindergarten	List of transactions
5	Historical	Karma, Polka, Eruption	List of objects

A higher–numbered policy is more expensive to compute than a lower–ranked one; but it
is not necessarily more predictive of future behavior. Ranking identifies policies that are comparable to each other.
SXM assumes that two transactions with policies from different policy classes were not intended to conflict, so neither transaction’s policy is preferable and uses the Greedy policy.
If the two transactions’ policies belong in the same class, SXM applies the conflict policy from the transaction that wants to acquire the object.

ASTM
Adaptive STM(ASTM) is a deferred, object-based STM system by Marathe, Scherer, and Scott that explored several performance improvements to the basic design of DSTM system

Strong or Weak Isolation	Weak
Transaction Granularity	Object
Direct or Deferred Update	Deferred (cloned replacement)
Concurrency Control	Optimistic
Synchronization	Nonblocking (obstruction free)
Conflict Detection	Early or late (selectable)
Inconsistent Reads	Validation
Conflict Resolution	Explicit contention manager
Nested Transaction
Exceptions

Key features:

• ASTM eliminated a memory indirection in accessing fields in an object open for reading
• adaptive system to change its conflict resolution policy from early to late detection

An object opened for update has the same representation as in DSTM, with two levels of indirection between the TMObject and the object’s fields
An object opened for reading by a transaction has a single level of indirection, so the TMObject points directly to the object’s fields

Late and early conflict detection
With late conflict detection, a transaction does not acquire ownership of an object that it is modifying. Instead, it modifies a cloned copy of the object and defers conflict detection until the transaction commits, which reduces the interval in which an object is locked and avoids some unnecessary transaction aborts. When the transaction commits, it may find that the object modified or may find another transaction in the process of committing changes to the object. The first case causes the transaction to abort, while the second one invokes a contention manager to resolve the conflict

Late and early conflict detection have comparable overhead for most benchmarks, but early detection is easier to implement. Late acquire performs better for a long running transaction that reads a large number of objects and updates only a few, because this policy allows concurrent readers and writers.

ASTM implements an adaptive policy that recognizes a transaction that modifies few objects but reads many objects . ASTM then switches the thread executing the transaction from early to late detection for subsequent transactions. If a transaction falls below the thresholds, it reverts to early detection

Ananian and Rinard

Strong or Weak Isolation	Strong
Transaction Granularity	Object
Direct or Deferred Update	Deferred (in-place)
Concurrency Control	Optimistic
Synchronization	Nonblocking
Conflict Detection	Early
Inconsistent Reads	Invalidation
Conflict Resolution	Abort conflicting transaction
Nested Transaction	Flatten
Exceptions	Terminate or abort

Key features:

• strong isolation
• written in PROMELA, so it can be directly verified with the SPIN model checker

Each Java object is extended by two fields. The first, named versions, is a linked list containing a version record for each transaction that modified a field in the object. A version record identifies the transaction and records the updated value of each modified field. The second field, named readers, is a list of transactions that read a field in the object.

A novel aspect of this system is the use of a sentinel (signalling a conflicting access) value in a memory location to redirect read and write operations to the transactional data structures.

NT-read:
if it encounters sentinel, it aborts the transaction modifying the object containing the value, restores the field’s value from the most recently committed transaction’s record, clears versions list and re-reads location

NT-write aborts all transactions reading and writing the object and directly updates the field in the object. Readers and version lists are cleared. If the program is actually writing the sentinel value, the write instruction is treated as a short transaction to make difference with real sentinel

T-read first ensures that its transaction descriptor is on the object’s reader list. It aborts all uncommitted transactions that modified the object. After this, the transaction can read the field in the object and directly use any values other than the sentinel. The sentinel value, on the other hand, requires a search of the version records to find one with the same version and the updated value of the field. After this we can clear versions list.

A T-write aborts all other uncommitted transactions that read or wrote the object. It also creates, if none previously existed, a version object for the transaction. The next step is to copy the unmodified value in the field to all version records, including those of the committed transactions, so that the field can be restored if the transaction is rolled back. If the versions list does not contain a committed transaction, one must be created to hold this value. Finally, the new value can be written to the running transaction’s version record and the object field set to the sentinel value

This STM system aggressively resolves conflicting references to an object. A read aborts transactions in the process of modifying the object and a write aborts all transactions that accessed the object. In essence, the system implements a multireader, single-writer lock on an object.

RSTM

Strong or Weak Isolation	Weak
Transaction Granularity	Object
Direct or Deferred Update	Deferred (cloned replacement)
Concurrency Control	Optimistic
Synchronization	Nonblocking (obstruction-free)
Conflict Detection	Early or late (selectable)
Inconsistent Reads	Bounded invalidation
Conflict Resolution	Conflict manager
Nested Transaction	Flatten
Exceptions

Key features:

• RSTM only uses a single level of indirection to an object, instead of the two levels used
  by previous systems such as DSTM
• RSTM avoids dynamically allocating many of its data structures and contains its own memory collector, so it can work with nongarbage collected languages such as C++
• RSTM uses invalidation to avoid inconsistent reads. It employs a new heuristic for
  tracking an object’s readers

In RSTM, every transactional object is accessed through an ObjectHeader, which points directly to the current version of the object. RSTM uses the low-order bit of the NewData field in this object as a flag

The TransactionDescriptor referenced through an object’s header determines the transaction’s state. If the transaction commits, then NewDataObject is the current version of the object. If the transaction aborts, then OldDataObject is the current version. If the transaction is active, no other transaction can read or write the object without aborting the transaction.

A transaction opens an object before accessing it:

1. If opening the object for update, the transaction must first acquire the object with the following actions:
   (a) Read the object’s NewData pointer and make sure no other transaction owns it. If it is owned, invoke the contention manager.
   (b) Allocate the NewDataObject and copy values from the object’s current version.
   (c) Initialize the Owner and OldData pointers in the new object.
   (d) Use a CAS to atomically swap the pointer read in step (a) with a pointer to the newly allocated copy.
   (e) Add the object to transaction’s private write list.
   (f ) Iterate through the object’s visible reader list, aborting all transactions it contains.
2. If opening the object for reading and space is available in the object’s visible readerlist, add the transaction to this list. If the list is full, add the object to the transaction’s private read list.
3. Check the status word in the transaction’s descriptor, to make sure another transaction has not aborted it.
4. Incrementally validate all objects on the transaction’s private read list.

Introducing visible reader list should have resulted in performance boost, because it reduces the cost of validation. But benchmarks show that visible readers are actually more costly, because of the extra cache traffic caused by updating the visible read table in each object

TL
Dice and Shavit described an STM system called transactional locking (TL), which combined deferred update with blocking synchronization

Strong or Weak Isolation	Weak
Transaction Granularity	Object, word or region
Direct or Deferred Update	Deferred (in-place)
Concurrency Control	Optimistic
Synchronization	Blocking
Conflict Detection	Early or late (selectable)
Inconsistent Reads	Inconsistency toleration
Conflict Resolution	Delay and abort
Nested Transaction	Flatten
Exceptions

Key features:

• uses blocking to acquire an object

Each object is associated with a lock. A lock is either locked, and pointing to the transaction holding exclusive access, or unlocked, and recording the object’s version, which is incremented when a transaction updates the object.

A transaction maintains a read set and a write set. An entry in the read set contains the address of the object and the version number of the lock associated with the object. An entry in the write set contains the address of the object, the address of its lock, and the updated value of the object.

When the transaction executes a write, it first looks for the object’s entry in its write set. If
it is not present, the transaction creates an entry for the object. The write modifies the entry in the write set, not the actual object. The transaction does not acquire the lock.

A memory load first checks the write set, to determine if the transaction previously updated the object. If so, it uses the updated value from the write set. If the object is not in the set, the transaction adds the referenced object to the read set and attempts to read the actual object. If another transaction locked the object, the reading transaction can either delay and retry or abort itself.

When a transaction commits, it first acquires locks for all objects in its write set. A transaction will only wait a bounded amount of time for a lock to be released to avoid deadlock. After acquiring locks for the objects it modified, the transaction validates its read set. If successful, the transaction can complete by copying updated values into the objects, releasing the locks, and freeing its data structures.

Performance measurements on simple benchmarks showed that TL performed better than other STM systems, such as Harris and Fraser’s nonblocking WSTM system