SOFTWARE TRANSACTIONAL MEMORY

As we learn from the literature, flexibility in choosing synchronizati on operations greatly simplifies the task of designing highly concurre nt programs. Unfortunately, existing hardware is inflexible and is at best on the level of a Lond-Linked/Store-Conditional operation on a si ngle word. Building on the hardware based transactional synchronizatio n methodology of Herlihy and Moss, we offer software transactional mem ory (STM), a novel software method for supporting flexible transaction al programming of synchronization operations. STM is non-blocking, and can be implemented on existing machines using only a Load-Linked/Stor e-Conditional operation. We use STM to provide a general highly concur rent method for translating sequential object implementations to non-b locking ones based on implementing a k-word compare & swap STM-transac tion. Empirical evidence collected on simulated multiprocessor archite ctures shows that our method always outperforms the non-blocking trans lation methods in the style of Barnes, and outperforms Herlihy's trans lation method for sufficiently large numbers of processors. The key to the efficiency of our software-transactional approach is that unlike Barnes style methods, it is not based on a costly ''recursive helping' ' policy.