Software transactional memory for dynamic-sized data structures

We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-~eedom. Obstruction-freedom is weaker than lock-freedom; as a re-sult, it admits substantially simpler and more efficient im-plementations. A novel feature of our obstruction-free STM implementation is its use of modular contention managers to ensure progress in practice. We illustrate the utility of our dynamic STM with a straightforward implementation f an obstruction-free red-black tree, thereby demonstrating a so-phisticated non-blocking dynamic data structure that would be difficult to implement by other means. We also present the results of simple preliminary performance experiments that demonstrate hat an "early release " feature of our STM is useful for reducing contention, and that our STM lends itself to the effective use of modular contention managers. 1