July 13–16, 2003 | Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III
The paper introduces a new form of dynamic software transactional memory (DSTM) designed to support dynamic-sized data structures. The authors propose a non-blocking implementation that ensures *obstruction-freedom*, a weaker form of progress compared to lock-freedom, allowing simpler and more efficient implementations. A key feature is the use of modular contention managers to ensure progress, which can be implemented and "plugged in" without affecting transaction code or correctness. The utility of DSTM is demonstrated through the implementation of an obstruction-free red-black tree, a sophisticated non-blocking data structure. Preliminary performance experiments show that an "early release" feature reduces contention and that modular contention managers are effective in managing progress. The paper also discusses the design and implementation details of DSTM, including the handling of synchronization conflicts, validation, and committing transactions. The authors conclude by highlighting the potential for further research in contention manager design and the benefits of DSTM in implementing complex data structures.The paper introduces a new form of dynamic software transactional memory (DSTM) designed to support dynamic-sized data structures. The authors propose a non-blocking implementation that ensures *obstruction-freedom*, a weaker form of progress compared to lock-freedom, allowing simpler and more efficient implementations. A key feature is the use of modular contention managers to ensure progress, which can be implemented and "plugged in" without affecting transaction code or correctness. The utility of DSTM is demonstrated through the implementation of an obstruction-free red-black tree, a sophisticated non-blocking data structure. Preliminary performance experiments show that an "early release" feature reduces contention and that modular contention managers are effective in managing progress. The paper also discusses the design and implementation details of DSTM, including the handling of synchronization conflicts, validation, and committing transactions. The authors conclude by highlighting the potential for further research in contention manager design and the benefits of DSTM in implementing complex data structures.