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.

Intro

This is a blog for experimental Transactional Memory seminar at Math-Mech SPbSU.
We meet every Friday at 9:30 at 3502.
The idea is to read J.R. Larus, R.Rajwar Transactional Memory and underlying papers along the way.
(Mitya has an electronic version, Ilya Sergey has a paper copy)

We'll post schedule and announcements here, as well as some sort of lecture notes.