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 critical region.

hardware tm concepts in metatm.

Primitive Definition
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
return.
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.,
access to a particular data structure.
transaction encodes information about the current transaction,
status word including reason for most recent restart. returned from
xbegin.

2. 2. synchronization with transactions

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 contention management.

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. ²⁴ Advanced issues in contention management include asymmetric conflicts, in which one of

the conflicting accesses is performed by a thread outside a transaction.

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 transactions.

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