ABSTRACT
Many of the challenges in building shared-memory data structures stem from needing to update several memory locations at once-e.g., updating four pointers to insert an item into a doubly linked list. Transactional memory (TM) provides a mechanism for grouping together this kind of series of operations, with the effect that either all of them appear to execute, or none of them does. As with database transactions, TM lets the programmer focus on the changes that need to be made to data, rather than dealing with the low-level details of exactly which locks to acquire, or how to prevent deadlock. In this chapter, we look at how TM can be used by a programmer, at the ways it can
be implemented in hardware (HTM) and software (STM), and at how higher-level constructs can be built over it in a programming language. As a running example,
FIGURE 11.1: A double-ended queue built over a doubly linked list with sentinel nodes.
