only in particular situations, such as when a particular critical region only reads a data structure. While lock variations
can reduce the performance problems of locks, they do not
reduce complexity, and in fact increase complexity as developers and code maintainers must continue to reason about
whether a particular lock variation is still safe in a particular
hardware tm concepts in metatm.
xbegin instruction to begin a transaction.
xend instruction to commit a transaction.
xretry instruction to restart a transaction.
xgettxid instruction to get the current transaction identifier, which is
0 if there is no currently active transaction.
xpush instruction to save transaction state and suspend current
transaction. used on receiving an interrupt.
xpop instruction to restore previously saved transaction state
and continue xpushed transaction. used on an interrupt
xtest if the value of the variable equals the argument, enter the
variable into the transaction read-set (if a transaction ex-
ists) and return true. otherwise, return false, and do not
enter the variable in the read-set.
A compare and swap instruction that subjects non-transactional threads to contention manager policy.
Conflict one transactional thread writes an address that is read or
written by another transactional thread.
Asymmetric A non-transactional thread reads (writes) an address
conflict written (read or written) by a transactional thread. (Also
known as a violation of strong isolation.)
Contention multiple threads attempt to acquire the same resource, e.g.,
2. 2. synchronization with transactions
access to a particular data structure.
transaction encodes information about the current transaction,
status word including reason for most recent restart. returned from
HTM is a replacement for synchronization primitives such
as spinlocks and sequence locks. Transactions are simpler
to reason about than locks. They improve performance by
eliminating lock variables and the coherence cache misses
associated with them, and they improve scalability by allowing concurrent execution of threads that do not attempt to
update the same data.
Transactions compose a thread executing a transaction
can call into a module that starts another transaction. The xcas
second transaction nests inside the first. In contrast, most
lock implementations do not compose. If one function takes
a lock and then calls another function which eventually tries
to take the same lock, the thread will deadlock. Research on
transaction nesting semantics is an active area, 13, 15, 16 but flat
nesting, in which all nested transactions are subsumed by
the outermost transaction, is easy to implement. MetaTM
uses flat nesting, but all patterns of transaction nesting are
free from deadlock and livelock.
HTM designs share a few key high level features: primitives for managing transactions, mechanisms for detecting
conflicts between transactions, called conflict detection, and
mechanisms for handling conflicts when they occur, or
The table here provides an HTM glossary, defining important concepts, and listing the primitives Meta TM adds to the
x86 ISA. The machine instructions not shown in italics are
those which are generic to any HTM design. Those shown in
italics are specific to Meta TM. The xbegin and xend instructions start and end transactions, respectively. Starting a transaction causes the hardware to enforce isolation for reads and
writes to memory until the transaction commits; the updates
become visible to the rest of the system on commit. The xretry
instruction provides a mechanism for explicit restart.
The set of memory locations read and written during a
transaction are called its read-set and write-set, respectively.
A conflict occurs between two transactions when there is a
non-empty intersection between the write-set of one transaction and the union of the read- and write-sets of another
transaction. Informally, a conflict occurs if two transactions
access the same location and at least one of those accesses
is a write-set.
When two transactions conflict, one of those transactions will proceed, while the other will be selected to discard
its changes and restart execution at xbegin: implementation
of a policy to choose the losing transaction is the responsibility of a contention manager. In Meta TM, the contention
manager is implemented in hardware. The policies underlying contention management decisions can have a first-order
impact on performance. 24 Advanced issues in contention
management include asymmetric conflicts, in which one of
the conflicting accesses is performed by a thread outside a
3. htm anD oPeRatinG s Ystems
This section discusses motivation for using TM for synchronization in an operation system, and considers the most
common approach to changing lock-based programs to use
3. 1. Why use htm in an operating system?
Modern operating systems use all available hardware processors in parallel, multiplexing the finite resources of the
hardware among many user processes concurrently. The OS
delegates critical tasks such as servicing network connections or swapping out unused pages to independent kernel
threads that are scheduled intermittently. A process is one
or more kernel threads, and each kernel threads is scheduled directly by the OS scheduler.
The result of aggressive parallelization of OS work is substantial sharing of kernel data structures across multiple
threads within the kernel itself. Tasks that appear unrelated
can create complex synchronization in the OS. Consider, for
example, the code in Figure 1, which is a simplification of
the Linux file system’s dparent_notify function. This
function is invoked to update the parent directory’s modify
time when a file is accessed, updated, or deleted. If two separate user processes write to different files in the same directory concurrently, two kernel threads can call this function