David Dice's Weblog

Understanding Tradeoffs in Software Transactional Memory

Understanding Tradeoffs in Software Transactional Memory by Nir Shavit and myself was accepted in CGO-2007. The paper describes the TL1 (Transactional Locking) mechanism. The slides presented at the conference are available as well. (We first described TL1 at Transact'06 in Ottawa). TL1's successor, TL2, authored by mself, Nir Shavit and Ori Shalev, was published in DISC'06.

Briefly, STMs such as TL1 periodically revalidate the read-set during a transaction. This is necessary as a transaction might have read a set of values that are inconsistent and then, based on that inconsistent data, enter an infinite loop, generate traps, or otherwise misbehave. We refer to such a transaction as a zombie: it's observed inconsistent state and could never successfully commit, but it's still running. We could avoid zombie transactions by revalidating the entire read-set after each transactional load. That's sufficient to avoid zombies, but the cost is quadratic with the size of the read-set. Instead, TL1 admits zombies (transiently) and validates periodically. The period of zombie execution is bounded. But the TL1 runtime environment must also provide zombie containment to gracefully tolerate the misbehavior of zombie transactions.

Another way to avoid zombies is to use so-called visible readers. Conceptually each transactional variable maps to a read-write lock. The first time a transaction reads from a location it acquires the read-lock. And of course transactional writes acquire the lock for writing. Visible readers avoid zombie execution but at the cost of considerable read-write coherency traffic on the read-write locks.

TL2 does not admit zombies execution, potentially making it more suitable for C or C++ unmanaged runtime environments. And it manages to avoid zombies with validation costs only proportional to the read-set size and without visible readers.

Posted at 10:34AM Feb 26, 2007 by David Dice in General  |  Comments[3]