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!