The pseudocode for the main operations executed by a typical STM is illustrated in figure 1. It shows two STM algorithms: one that performs full validation and one that uses a global version number (the additional statements marked with the gv# comment).

The advantage of STM for system programmers is that it offers flexibility in implementing different mechanisms and policies for these operations. For end users, the advantage of STM is that it offers an environment to transactionalize (i.e., port to TM) their applications without incurring extra hardware cost or waiting for such hardware to be developed.

On the other hand, STM entails nontrivial drawbacks with respect to performance and programming semantics:

Overheads. In general, STM results in higher sequential overheads than traditional shared-memory programming or HTM. This is the result of the software expansion of loads and stores to shared mutable locations inside transactions to tens of additional instructions that constitute the STM implementation (for example, the STM_READ code in figure 1). Depending on the transactional characteristics of a workload, these overheads can become a high hurdle for STM to achieve performance. The

FIGURE

1STM Operations

Pseudo-code for STM begin

STM_BEGIN() read global version number /* gv# */

Pseudo-code for STM read barrier
STM_READ(A)

if already written goto written path read metadata of A if metadata is locked goto conflict path log A and its metadata in the read set read value at A if STM_VALIDATE() goto conflict path return val

sequential overheads (that is, conflict-free overheads that are incurred regardless of the actions of other concurrent threads) must be overcome by the concurrency-enabling characteristics of transactional memory.

Semantics. To avoid incurring high STM overheads, nontransactional accesses (i.e., loads and stores occurring outside transactions) are typically not expanded. This has the effect of weakening—and hence complicating—the semantics of transactions, which may require the programmer to be more careful than when strong transactional semantics are supported. The following are some of the weakened guarantees that are usually associated with such STMs: • Weak atomicity. Typically, the STM runtime libraries cannot detect conflicts between transactions and nontransactional accesses. Thus, the semantics of atomicity are weakened to allow undetected conflicts with nontransactional accesses (referred to as weak atomicity²⁸), or equivalently put the burden on the programmer to guarantee that no such conflicts can possibly take place. • Privatization. Some STM designs prohibit the seamless privatization of memory locations (that is, the transition from being accessed transactionally to being accessed

Pseudo-code for STM validate

STM_VALIDATE()
read global version number /* gv# */
if global version number changed /* gv# */
for each read set entry
if metadata changed return FALSE
return TRUE

Pseudo-code for STM end

STM_END() lock metadata for write set if already locked goto conflict path if STM_VALIDATE() goto conflict path

/* Success guaranteed */ increment global version number /* gv# */ execute writes update/unlock metadata for write set