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

Programme

Here is a list of readings:

Deferred Update systems:
1. DSTM, WSTM and contention management (3.4.1-3.4.4) [Oleg]
2. Improvements on DSTM and WSTM (3.4.4-3.4.9) [Denis]

Direct Update systems:
3. McRT-STM and compiler optimizations (3.5.2-3.5.3) [Roma]
4. Bartok STM and compiler optimizations (3.5.4) [Lena]
Skipping: Autolocker

Language-oriented STMs:
5. HSTM for Concurent Haskell and AutoCaml (3.6.3-3.6.4) [Ilya]
Skipping: discussion of exceptions thrown from atomics, real-time Java stuff

HTM
Precursors
6. Optimistic synchronisation in hardware (4.3.2-4.3.5) [Leonid]
7. Lock elision (4.3.6-4.3.7) [Nastasia]
Skipping: IBM 801
HTM designs
8. Bounded/Large HTMs (4.4) [Kostya]
9. Unbounded HTMs (4.5)
10. Hybrid HTM-STMs (4.6)

Reading 4. Word granularity STM

March 14, 2008

Harris and Fraser’s 2003 OOPSLA paper was the first to describe a practical STM system integrated into a programming language. They implemented WSTM word-granularity STM) in the ResearchVM from Sun Labs.
WSTM benefits

• WSTM did not require a programmer to declare the memory locations accessed within a transaction.
• WSTM was integrated into a modern, object-oriented language ( Java) by extending the language with the atomic operation. Strangely enough, WSTM did not exploit the object-oriented nature of Java and could support procedural languages as well.

Strong or Weak Isolation	Weak
Transaction Granularity	Word
Direct or Deferred Update	Deferred (update in place)
Concurrency Control	Optimistic
Synchronization	Obstruction free
Conflict Detection	Late
Inconsistent Reads	Inconsistency toleration
Conflict Resolution	Helping or aborting
Nested Transaction	Flattened
Exceptions	Terminate

WSTM extended Java with a new statement:

atomic (condition) { 
   statements; 
} 

A modified JIT ( Just-In-Time, i.e., run-time) compiler translated this statement into

bool done = false; 
   while (!done) { 
            STMStart(); 
            try { 
                if (condition) { 
                    statements; 
                    done = STMCommit(); 
                } else { 
                    STMWait(); 
                } 
            } catch (Exception t) { 
              done = STMCommit(); 
              if (done) { 
                  throw t; 
              } 
            } 
   } 

Note: an exception within the atomic region’s predicate or body causes the transaction to commit. Subsequent systems more typically treated an exception as an error that aborts a transaction.
The code produced by the compiler relies on five primitive operations provided by the

void   STMStart() 
void   STMAbort() 
bool   STMCommit() 
bool   STMValidate() 
void   STMWait()

In addition, all references to object fields from statements within an atomic region are replaced by calls to an appropriate library operation:

STMWord STMRead(Addr a) 
void STMWrite(Addr a, STMWord w) 

Restrictions: Because the JVM’s JIT compiler performs this translation, only references from Java bytecodes, not those in native methods, are translated to access these auxiliary structures. A few native methods were hand translated and included in a WSTM library, but a call on most native methods (including those that perform IO operations) from a transaction would cause a run-time error.

enum TransactionStatus { ACTIVE, COMMITTED, ABORTED, ASLEEP }; 
class TransactionEntry { 
     public Addr loc; 
     public STMWord oldValue; 
     public STMWord oldVersion; 
     public STMWord newValue; 
     public STMWord newVersion; 
} 
class TransactionDescriptor { 
     public TransactionStatus status = ACTIVE; 
     int nestingDepth = 0; 
     public Set entries; 
} 

The status field records the transaction status. A transaction starts in state ACTIVE and makes a transition into one of the three other states. The nestingDepth field records the number of (flattened) transactions sharing this descriptor.
The entries field holds a TransactionEntry record for each location the transaction
reads or writes. The compiler redirects memory reads and writes to the appropriate descriptor. A TransactionEntry records a location’s original value (before the transaction’s first access) and its current value. For a location only read, the two values are identical. A transaction increments the version number when it modifies the location. The system uses the version number to detect conflicts.

OwnershipRec records the version number of the memory location, produced by the most recent committed transaction that updated the location. Second, when a transaction is in the process of committing, an OwnershipRec records the transaction that has acquired exclusive ownership of the location. Each ownership record holds either a version number or a pointer to the transaction that owns the location:

class OwnershipRec { 
     union { 
         public STMWord version; 
         public TransactionDescriptor* trans; 
     } val; 
     public bool HoldsVersion() { return (val.version & 0x1) != 0; } 
} 

The function FindOwnershipRec(a) maps memory address a to its associated OwnershipRec. The function CASOwnershipRec(a, old, new) performs a compare-and-swap operation on the OwnershipRec for memory address a, replacing it with value new, if the existing entry is equal to old.

void STMStart() { 
   if (ActiveTrans == null || ActiveTrans.status != TransactionStatus.ACTIVE) { 
        ActiveTrans = new TransactionDescriptor(); 
        ActiveTrans.status = TransactionStatus.ACTIVE; 
   } 
   AtomicAdd(ActiveTrans.nestingDepth, 1); 
} 

void STMAbort() { 
   ActiveTrans.status = TransactionStatus.ABORTED; 
   ActiveTrans.entries = null; 
   AtomicAdd(ActiveTrans.nestingDepth, -1); 
} 

struct ValVersion { 
   public STMWord val; 
   public STMWord version; 
} 

STMWord STMRead(Addr a) { 
   TransactionEntry* te = ActiveTrans.entries.Find(a); 
   if (null == te) { 
   // No entry in transaction descriptor. Create new entry (get value from memory) 
   // and add it to descriptor. 
      ValVersion vv = MemRead(a); 
      te = new TransactionEntry(a, vv.val, vv.version, vv.val, vv.version); 
      ActiveTrans.entries.Add(a, te); 
      return vv.val; 
   } else { 
   // Entry already exists in descriptor, so return its (possibly updated) value. 
      return te.newValue; 
   } 
}

void STMWrite(Addr a, STMWord w) { 
    STMRead(a); // Create entry if necessary. 
    TransactionEntry te = ActiveTrans.entries.Find(a); 
    te.newValue = w; 
    te.newVersion += 2; // Version numbers are odd numbers. 
} 

The function MemRead returns the value of a memory location, along with its version number:

• If no other transaction accessed the location and started committing, then the current value resides in the memory location and its ownership record contains the version number.
• If another transaction accessed the location and committed, the value is in the transaction’s newValue field and the version in the newVersion field.
• If another transaction accessed the location and has started, but not finished committing, the value is stored in the transaction’s oldValue field and the version in its oldVersion

STMCommit first acquires the ownership records for all locations accessed by the transaction. If successful, STMCommit changes the transaction’s state to COMMITTED, copies the modified values to memory, and releases the ownership records.
These three steps appear logically atomic to concurrent transactions because the committing transaction’s status changes atomically (and irrevocably) from ACTIVE to COMMITTED using an atomic read-modify-write operation. Once this change occurs, MemRead will return the updated value, even before the transaction copies value back to memory.

void STMCommit() { 
     // Only outermost nested transaction can commit. 
     if (AtomicAdd(ActiveTrans.nestingDepth, -1) != 0) { return; } 
     // A nested transaction already aborted this transaction. 
     if (ActiveTrans.status == TransactionStatus.ABORTED) { return; } 
       // Acquire ownership of all locations accessed by transaction. 
      int i; 
      for (i = 0; i < ActiveTrans.entries.Size(); i++) { 
           TransactionEntry* te = ActiveTrans.entries[i]; 
           switch (acquire(te)) { 
               case TRUE: { continue; } 
               case FALSE: { 
                       ActiveTrans.status = TransactionStatus.ABORTED; 
                       goto releaseAndReturn; 
               } 
               case BUSY: { /* conflict resolution */ } 
           } 
      } 
       // Transaction commits. 
      ActiveTrans.status = TransactionStatus.COMMITTED; 
        //Copy modified values to memory. 
      for (i = 0; i < ActiveTrans.entries.Size(); i++) { 
           TransactionEntry te = ActiveTrans.entries[i]; 
           *((STMWord*)te.loc) = te.newValue; 
      } 
   releaseAndReturn: // Release the ownership records. 
           for (int j = 0; j < i; j++) { release(te); } 
   } 
   bool acquire(TransactionEntry* te) { 
           OwnershipRec orec = CASOwnershipRec(te.loc, te.oldVersion, 
                                        ActiveTrans); 
           if (orec.HoldsVersion()) 
               { return orec.val.version == te.oldVersion; } 
           else { 
               if (orec.val.trans == ActiveTrans) { return true; } 
               else { return BUSY; } 
      } 
   } 

void release(TransactionEntry* te) { 
   if (ActiveTrans.status == TransactionStatus.COMMITTED) { 
       CASOwnershipRec(te.loc, ActiveTrans, te.newVersion); 
   } else { 
       CASOwnershipRec(te.loc, ActiveTrans, te.oldVersion); 
   } 
} 

STMValidate is a read-only operation that checks the ownership records for each location accessed by the current transaction, to ensure that they are still consistent with the version the transaction initially read:

bool STMValidate() { 
    for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
        TransactionEntry* te = ActiveTrans.entries[i]; 
        OwnershipRec orec = FindOwnershipRec(te.loc); 
        if (orec.val.version != te.oldVersion) { return false; } 
    } 
    return true; 
} 

STMWait can be used to implement a conditional critical region by suspending the transaction until its predicate should be reevaluated. It aborts the current transaction and waits until another transaction modifies a location accessed by the first transaction. It acquires ownership of the TransactionEntry accessed by the transaction, changes the transactions status to ASLEEP, and suspends the thread running the transaction. When another transaction updates one of these locations, it will conflict with the suspended transaction!!!
The conflict manager should allow the active transaction to complete execution and then resume the suspended transaction, which releases its ownership records and then retries the transaction:

void STMWait() { 
    int I; 
    for (i = 0; i < ActiveTrans.entries.Size(); i++) { 
          TransactionEntry* te = ActiveTrans.entries[i]; 
          switch (acquire(te)) { 
              case TRUE: { continue; } 
              case FALSE: { 
                   ActiveTrans.status = TransactionStatus.ABORTED; 
                   goto releaseAndReturn; 
              } 
              case BUSY: { /* conflict resolution */ } 
         } 
   } 
   // Transaction waits, unless in conflict with another transaction and 
   // needs to immediately re-execute. 
   ActiveTrans.status = TransactionStatus.ASLEEP; 
   SuspendThread(); 
   // Release the ownership records. 
   releaseAndReturn: 
       for (int j = 0; j < i; j++) { release(te); } 
} 

If two transactions share a location that neither one modifies, one transaction will be aborted, since the system does not distinguish read-only locations from modified locations.
This performance issue is easily corrected. STMWrite can set a flag isModified in a transaction entry to record a modification of the location. STMCommit should acquire ownership of modified locations and validate unmodified locations! This introduces a new transaction status READ_PHASE. The transaction remains in this state until it commits.

void STMCommit() { 
   for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
      TransactionEntry* te = ActiveTrans.entries[i]; 
      if (te.isModified) { 
         switch (acquire(te)) { 
            case TRUE: { continue; } 
            case FALSE: { 
               ActiveTrans.status = TansactionStatus.ABORTED; 
               goto releaseAndReturn; 
            } 
            case BUSY: { /* conflict resolution */ } 
         } 
      } 
   } 
   ActiveTrans.status = TransactionStatus.READ_PHASE; 
   for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
      TransactionEntry* te = ActiveTrans.entries[i]; 
      if (!te.isModified) { 
         ValVersion vv = MemRead(te.loc); 
         if (te.oldVersion != vv.version) { 
         // Another transaction updated this location. 
            ActiveTrans.status = TransactionStatus.ABORTED; 
            goto releaseAndReturn; 
         } 
      } 
   } 
   // Transaction commits. Write modified values to memory. 
   ActiveTrans.status = TransactionStatus.COMMITTED; 
   for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
       TransactionEntry te = ActiveTrans.entries[i]; 
       *((STMWord*)te.loc) = te.newValue; 
   } 
   // Release the ownership records. 
releaseAndReturn: 
       for (int j = 0; j < i; j++) { release(te); } 
}

Reading 3. Deferred STM

March 7, 2008

Deferred Update STM Herlihy, Luchangco, Moir, and Scherer, PODC 2003

DSTM Characteristics

• Obstruction freedom
• Explicit contention manager, which encapsulates the policy of resolving conflicts
• Can release object, by reducing transaction readset

DSTM

Strong or Weak Isolation	Weak
Transaction granularity	Object
Update	Deferred (cloned replacement)
Concurrency control	Optimistic
Synchronization	Obstruction free
Conflict detection	Early
Incostistent reads	Validation
Conflicts resolution	Explicit content manager
Nested transaction	Flattened

A programmer must explicitly invoke library functions to create a transaction and to access shared objects. Transactions run on threads of a new class. The programmer must introduce and properly manipulate a container for each object involved in a transaction.
Example of using DSTM:

public bool insert(int v) {
List newList = new List(v);
TM0bject newNode = new TM0bject(newList);
TMThread thread = (TMThread)Thread.currentThread();
while (true) {
thread.beginTransaction();
bool result = true;
try {
   List prevList = (List)this.first. open(WRITE);
   List currList = (List)prevList.next. open(WRITE);
   while (eurrList.value <> v) {
       prevList = currList;
       currList = (List)currList.next. open(WRITE);
   }
   if (currList.value == v) { result = false; }
   else {
       result = true;
       newList.next = prevList.next;
       prevList.next = newNode;
   }
} catch (Denied d) {}
if (thread. commitTransaction()) {
   return result;
}
}

The TMThread class extends the Java Thread class:

class TMThread : Thread {
  void beginTransaction();
  bool commitTransaction();
  void abortTransaction();
}

Transaction references an object through a TMObject.The open operation prepares a TMObject to be manipulated by a transaction and exposes the underlying object to the code in the transaction. The actions that open performs depend on whether an object is open for reading or writing.

class TMObject {
  private class Locator {
    public Transaction trans;
    public Object oldVersion;
    public Object newVersion;
  }
  TMObject(Object obj);
  enum Mode { READ, WRITE };
  Object open(Mode mode);
}

The current version of an object is found through the object’s Locator.

• If the Locator does not contain a transaction, the current version is the original object (oldVersion).


• If the Locator points to some transaction, we check it`s status:
  
  
  
  1. COMMITTED. The current version is the one modified by the
     transaction (newVersion).
     
  
  
  2. ABORTED. The current version is the original object
     (oldVersion).
     
  
  
  3. ACTIVE. Conflict! The contention manager must resolve the
     conflict by aborting or delaying one of the transactions.
     Note: it`s only the place, where we ask the contention manager! All other conflicts mean inconsistency and we have no choise: we have to abort current transaction!
     
  
  
  
  

DSTM adds two levels of indirection to an object:

• READ - adds to current transaction read set pair (TMObject and currentVersion), then validate current transaction
  

// Record the TMObject and its current value (version) in transaction’s read table.
curTrans.recordRead(this, currentVersion(locInfo));
if (!curTrans.validate()) { throw new Denied(); }
return version;

• WRITE - create new Locator, get current version of TMObject, clone it and validate

// Create a new Locator pointing to a local copy of the object and install it.
Locator newLocInfo = new Locator();
newLocInfo.trans = curTras;
// Actually it is just a spin lock to ensure, that no one has modified current
object`s locator
do {
  Locator oldLocInfo = locInfo;
  // Note: We can get conflict in currentVersion
  newLocInfo.oldVersion = currentVersion(oldLocInfo);
  newLocInfo.newVersion = newLocInfo.oldVersion.clone();
} while (CAS(locInfo, oldLocInfo, newLocInfo) != oldLocInfo);
if (!trans.validate()) { throw new Denied(); }
return newLocInfo.newVersion;

Validating the transaction’s consistency relies on the read set. DSTM compares each object entry in a transaction’s read set against the current version of the object (obtained by following the TMObject reference). If the objects differ, the transaction should abort since it is in inconsistent state.

A transaction commits by validating its read set, and if that operation succeeds, by
changing its status from ACTIVE to COMMITTED.

Note: We don`t need modify objects in memory! This modification(ACTIVE -> COMMITED) makes all of the transaction’s modified objects into the current version of the respective objects!

Clarification: Invalidation Policies

I skimmed through the original paper by Michael Scott "Sequential Specification of Transactional Memory Semantics", which introduced classification of invalidation policies (lazy, eager W-R, mixed and eager), that was a stumbling block at our last reading.

Apparently our understanding of what was meant turns out to be correct: Scott introduces a notion of transactional memory history as essentially a sequence of events which include reading and writing memory and commiting and aborting transactions (each event is annotated with a transaction), that he says that predicate C(H,s,t) (where H is a history and s and t are transactions) is a conflict function if C(H,s,t) satisfies certain rules (mainly asserting that non-overlapping transactions do not conflict), and then he classifies conflict functions into lazy, eager W-R, mixed or eager depending on what kind of histories particular conflict function classifies as a conflict.

Garbage Collection vs. Transactional Memory

Dan Grossman's paper "The Trasactional Memory / Garbage Collection Analogy" argues that

Transactional Memory is to shared-memory concurrency

as
Garbage Collection is to memory management

Here is a summarizing list of similiarities:

GC Term	TM Term
memory management	concurrency
dangling pointers	races
space exhaustion	deadlock
regions	locks
garbage collection	transactional memory
reachability	memory conflicts
nursery data	thread-local data
weak pointers	open nesting
I/O of pointers	I/O in trasactions
tracing	deferred update
automatic reference counting	direct update
conservative collection	false memory conflicts
real-time collection	obstruction freedom
liveness analysis	escape analysis

Be careful though: the analogy is a bad guide for studying TM. I believe we should first understand all the nuances and problems of implementing TM in its own right, and only then can we think of connections to Garbage Collection.

Mitya has the full text for the article (I believe ACM copyright allows to make copies for classroom use)