July 13-16, 2003 | Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III
This paper presents a new form of software transactional memory (STM) called Dynamic Software Transactional Memory (DSTM), designed to support dynamic-sized data structures. The authors propose a novel non-blocking implementation of DSTM based on obstruction-freedom, a weaker progress condition than lock-freedom. Obstruction-freedom allows for simpler and more efficient implementations, as it ensures that any thread that runs long enough will make progress, even if other threads are blocking it. A key feature of their implementation is the use of modular contention managers to ensure progress in practice. The authors demonstrate the utility of DSTM by implementing an obstruction-free red-black tree, a complex non-blocking data structure that would be difficult to implement using other methods. They also present preliminary performance experiments showing that an "early release" feature of their STM is useful for reducing contention, and that their STM is effective in using modular contention managers.
The paper describes the use of DSTM through simple examples, including an integer set implementation that supports insert, delete, and member operations. The authors also discuss how DSTM detects synchronization conflicts and how transactions commit and abort, emphasizing how the obstruction-free property simplifies the underlying algorithm. They describe how their implementation interfaces with contention managers, which are responsible for ensuring progress. The paper also presents some simple experiments with their prototype DSTM implementation, showing that DSTM can outperform traditional locking approaches in high-concurrency scenarios. The authors conclude that DSTM provides a simple open-ended mechanism for guaranteeing progress and prioritizing transactions, and that further research is needed to explore the full potential of contention managers in designing efficient non-blocking data structures.This paper presents a new form of software transactional memory (STM) called Dynamic Software Transactional Memory (DSTM), designed to support dynamic-sized data structures. The authors propose a novel non-blocking implementation of DSTM based on obstruction-freedom, a weaker progress condition than lock-freedom. Obstruction-freedom allows for simpler and more efficient implementations, as it ensures that any thread that runs long enough will make progress, even if other threads are blocking it. A key feature of their implementation is the use of modular contention managers to ensure progress in practice. The authors demonstrate the utility of DSTM by implementing an obstruction-free red-black tree, a complex non-blocking data structure that would be difficult to implement using other methods. They also present preliminary performance experiments showing that an "early release" feature of their STM is useful for reducing contention, and that their STM is effective in using modular contention managers.
The paper describes the use of DSTM through simple examples, including an integer set implementation that supports insert, delete, and member operations. The authors also discuss how DSTM detects synchronization conflicts and how transactions commit and abort, emphasizing how the obstruction-free property simplifies the underlying algorithm. They describe how their implementation interfaces with contention managers, which are responsible for ensuring progress. The paper also presents some simple experiments with their prototype DSTM implementation, showing that DSTM can outperform traditional locking approaches in high-concurrency scenarios. The authors conclude that DSTM provides a simple open-ended mechanism for guaranteeing progress and prioritizing transactions, and that further research is needed to explore the full potential of contention managers in designing efficient non-blocking data structures.