Class notes for CSC 2/458, 5 March ff., 2008 Transactional Memory Background Herlihy and Moss, ISCA'93 Shavit & Touitou, PODC'95 (one of several important theory papers from that era) Harris & Fraser, OOPSLA'03 Herlihy, Luchangco, Moir, and Scherer, PODC'03 Rajwar & Goodman, MICRO'01, ASPLOS'02 Martinez & Torrellas, ASPLOS'02 Problems with locks preemption, page faults, thread failure forget to lock; forget to release deadlock, priority inversion lack of composability * complexity/concurrency tradeoff TM addresses (most or all of) these with higher-level abstraction. Borrowed from DB community. Implementations assumed to employ speculation. HW v. SW all things equal, HW is faster, but HW policies are hard to change SW policies can be more complex, more dynamic legacy machines need SW hybrids best effort acceleration Representative SW implementations eager, undo, R-W locking, object-based (Ennals, McRT) keep time-sorted write log, undo in reverse order eager, NB, cloning, incrementally validating, object-based, obstruction-free, vis or invis readers (DSTM) lazy, redo, time-based, stripe (or object) based, read-post-validating (TL2) abort if location has been modified since transaction started (can be relaxed to perform full validation and update of start time instead) lazy, redo, non-locking, commit-serializing (RingSTM) low and high watermarks in (conceptually unbounded) list remember high as of start time; double-check on read; validate if nec. keep read and write filters commit by enqueuing write filter --------------------- Dimensions to the design space (incomplete list) blocking/nonblocking (lock-free v. obstruction-free) eager/lazy redo/undo/cloning visible readers/invisible readers/partially-visible readers/read locks contention management polite, aggressive, "responder wins", timestamp, karma, polka, highlander, reincarnation (current timestamp), ... can force lock-freedom (Guerrouai et al.) object-based/stripe-based validation underappreciated by some early systems; implement with incremental open-time checks post-read time-based checks (ala TL2) sandboxing heuristics to avoid incremental validation conflict counter (Lev & Moir): maintain reader counts, and skip validation if no one has committed writes to an object with active readers commit counter (Spear et al.): skip validation if no one has committed writes TL2-style timestamps (Dice & Shavit): continue if THIS OBJECT has not been modified since my transaction began (so I'm valid as of my start time) ============================ Semantic challenges "single lock semantics" ? (much of discussion here drawn from [Menon et al.], TRANSACT'08) problem: most STM implementations can produce behavior in the presence of races that locks can't produce. example: // data == 42, ready == false, val == 0 atomic { tmp = data data = 1 atomic { ready = true } if (ready) val = tmp } With traditional critical sections, val can never end up being 42. With most current STMs it can, if threads interleave as shown. [ Recall that memory models typically require a global "happens-before" among special synchronization ops, and between special ops and ordinary ops in the same thread. In release consistency, the special ops are acquire and release instructions. In the Java MM, they are synchronized block enter/release and volatile load/store. A race is a pair of conflicting accesses not ordered by happens-before. ] The program above has a race between txnal and non-txnal code, so maybe we just say "don't do that"? But consider: // data == 42, ready == false, val == 0 data = 1 atomic { atomic { if (ready) ready = true val = data } } Here there is no race in the source code, but the compiler may _introduce_ a race by speculatively hoisting the read of data out of the conditional. With traditional memory models, the compiler has to introduce a WBW fence in thread 1 to prevent the race. What is the analagous solution for transactions? This is the PUBLICATION PROBLEM. It can be solved by providing STRONG ISOLATION (aka strong atomicity), but that requires HW support or unacceptable overhead on nontransactional accesses. The symmetric PRIVATIZATION PROBLEM deals with non-txnal access _after_ txnal access. Example: atomic { atomic { if (visible) visible = false if (p != null) } if (p != null) p = p->next p = p->next < abort > Here thread 2 may suffer a memory violation if the code interleaves as shown and it doesn't realize fast enough that the commit in thread 1 is going to force it to abort. This is the DOOMED TRANSACTION manifestation of the privatization problem. Similarly: atomic { if (visible) if (p != null) p = p->next < commit > atomic { visible = false } if (p != null) < clean up > p = p->next } If thread 2 is using a redo log, thread 1 may not see the update of p in time, and may suffer a memory violation. This is the DELAYED CLEANUP manifestation of the privatization problem. An attractive alternative to strong isolation is to say that race-free programs display global lock atomicity (GLA), and are publication and privatization safe. Publication-safe means the implementation respects happens-before between a non-txnal access and a subsequent txnal access. Privatization-safe means the implementation respects happens-before between a txnal access and a subsequent non-txnal access. Two questions arise (1) What sorts of behavior are permitted for racy programs? Java limits (and defines) the possibilities; C has "catch fire" semantics (realistically: "thin-air" values). (2) Must publicizing and privatizing transactions be explicitly identified by the programmer? If so, the implementation of non-labeled txns might be cheaper, at least for "catch fire" languages. Menon et al. propose three progressive relaxations of GLA: DLA (disjoint) -- as if every location had a separate lock, acquired presciently at beginning of txn ALA (asymmetric) -- like DLA, but read locks can be acquired lazily ELA (encounter-time) -- like ALA, but write locks can be acquired lazily For race-free programs, DLA and ALA provide the same semantics as GLA. For racy programs, they introduce new possible (but well-defined) behaviors. ELA provides the same semantics as GLA only if the compiler refrains from speculative hoisting. Which of these we should have (if "catch fire" isn't ok) is still an open question, as is how to implement them efficiently. --------------------------- irreversible operations for correctness (e.g. read-after-prompt interactive I/O) for speed (avoid instrumentation in inevitable txn) implement via global read/write lock no concurrency global write lock allows concurrent readers, but inev. txn must acquire have to instrument inev. reads to wait for concurrent writers to abort GWL + fence avoids inev. read instrumentation transactional "drain" irreversible txn as "writer" other writers as "readers" inevitable read locks allows concurrent writers, but forces read instrumentation inevitable read Bloom filter cheaper way to allow concurrent writers commit order == serialization order == cleanup order (RingSTM) nesting subsumption closed how to tell what level you conflict with? open admits circularity x == y == 0 A B atomic { atomic { open atomic { open atomic { x = 1 y = 1 } } u = y v = x } } u == v == 1 // neither outer txn came first exceptions error v. non-local return additional compiler challenges track "transactional state" of references clone subroutines based on states of parameters elide operations validation memory fences on relaxed order machines instrumentation on provably non-escaping values track irreversible operations require programmer to label? what's the default: reversible or irreversible? if the former, what do you do about legacy libraries? if the latter, you have to label a LOT