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