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)

Reading 2. Taxonomy and Implementation

February 29th, 2008

Granularity

Object granularity/Word granularity

Direct/Deferred Update

Deferred update: transactions modify private copies of objects, and copy to public space on commit
Direct update: transactions modify objects in place, revert modifications on rollback.
In STM, direct update appears to be faster.

Concurrency control

Conflict:

• Occurs when transactions perform conflicting operation on memory location
  
• Is detected when TM system is aware of that conflict
  
• Is resolved when TM system takes action to ensure correctness (delays or aborts transaction)
  

These three events happen in that order, but at different times.
Pessimistic concurrency control: all three events happen at the same time.
Optimistic concurrency control: TM system postpones detection and resolution.

Progress Guarantees:

• Wait freedom: all threads contending over a set of objects make forward progress in finite steps
  
• Lock freedom: at least one thread contending over a set of objects make forward progress
  
• Obstruction freedom: thread makes progress in the absense of contention over shared objects

Conflict detection

A conflict can be:

1. Detected on open: when transaction declares its intent of accessing an object
   
2. Detected on validation: at some point during transaction execution
   
3. Detected on commit: extreme case of validation, just before transaction commits (essentially a must, unless all conflicts are detected on open)

Validation should happen either by value or by version number (latter avoids ABA problem)

Early conflict detection may terminate the transaction that may have commited.
(TB and TC conflict with TA over two different objects...)

Late conflict detection discards more computation.

How to detect conflicts: either read/write sets (objects accessed by transaction; can be private or public) or reader/writer sets (transactions accessing objects).

Invalidation Policies

See Michael Scott's paper for a formal discussion

• Lazy: TA and TB conflict if TA writes (an object), TB reads (the same object), and TA commits before TB
  
• Eager W-R: Lazy or TA writes, TB reads, but neither commit
  
• Mixed: Lazy or TA reads, TB reads and writes, neither commit
  
• Eager: Eager W-R or TB reads, TA writes, neither commits

Lazy < Eager W-R < Eager
Lazy < Mixed < Eager

Doing something about conflicts

Validation: check the read set
Invalidation: check the reader set
Inconsistency toleration: allow transaction to continue in inconsistent state and recover from consequences (validate on throwing exception, timeout non-terminating loops &c)

Particulary bad example:
Thread 1:

ListNode res;
atomic {
  res = lHead;
  if (lHead != null)
    lHead = lHead.next;
}
use res several times

Thread 2:

atomic {
  ListNode n = lHead;
  while (n != null) {
    n.val++;
    n = n.next;
  }
}

If read set is private (only visible to a thread that keeps it) and inconsistency is tolerated, it is possible that thread 1 will see modified value and then unmodified value of res.val

Reading 1. Basic Concepts and Design Space

February 22nd, 2008

Main Syntactic Construct

atomic {
  x.Bar();
  y = x.Baz(); // (1)
  y.Foo();
}

atomic {
  y = null; // (2)
}

TM system guarantees that code inside atomic blocks runs as if there are no other concurrent threads.
In the example, there is no data race between (1) and (2).
TM system should detect transaction memory conflicts and abort (and restart) one of the transactions.

Operational Semantics

Replace atomic with synchronized(MasterLock). The correct TM-system implementation should be equivalent.
Real-life system should do better!

TM is not a concurrent programming panacea:

bool flagA = false;
bool flagB = false;

// Th1:
atomic {
  while(!flagA);
  flagB = true;
}

// Th2
atomic {
  flagA = true;
  while(!flagB)
}

Th1 and Th2 deadlock! If we put smaller atomics, they will work.

Transaction Properties In TM System

TM-guaranteed properties:
Isolation - while transaction executes, no other transaction sees its changes, and vice versa.
Atomicity - transaction either does all changes it does to memory, or appears not to execute at all.
Not guaranteed:
Consistency - cannot be specified independently of a particular program

Exceptions

Exceptions thrown from inside atomic should commit transaction. Otherwise, complicated handling of exception object should be implemented.

Additional Features

retry - implementing conditional variables

atomic {
  if (buffer.IsEmpty()) retry;
  var value = buffer.GetFirst();
  ...
}

Will only work if sufficient progress guarantees are provided by TM system (wait freedom or lock freedom - see next lecture)

orElse

Weak Or Strong Isolation

Weak Isolation: transactions are only isolated from other transactions.
Strong Isolation: transactions are isolated from non-transactional code too (as if all memory accesses outide programmer-written atomics are surrounded in small atomics too)

Nested Transactions

Generally, when nested transaction commits, its changes are only seen by the parent transaction.

flattened nested transactions: aborting nested aborts its parent
closed nested transactions: abroting nested only aborts itself.

However, open nested transactions are useful.
open nested transactions: commit of nested open transaction is immediately seen by all.
Reduces conflicts (e.g. gensym())

Exceptions

Should commit transaction, otherewise non-trivial handling of exception object should be implemented.