Software Transactional Memory for Dynamic-sized Data Structures
Mark Moir
Sun Microsystems
We present a new, dynamic form of software transactional memory that
is simpler, more efficient, and more flexible than previous software
transactional memory implementations. In particular, it is well
suited to implementing dynamic-sized nonblocking data structures: for
example, we have used it to implement red-black trees. This
represents the most sophisticated nonblocking data structure
implemented to date. They key to the efficiency of our implementation
is the combination of a new progress condition called obstruction
freedom and modular contention management mechanisms.