figure 2: the cxspinlock aPi and implementation. the cx_optimistic aPi attempts to execute a critical section by starting a transaction, and using xtest to spin until the lock is free. if the critical section attempts i/o, the hardware will retry the transaction, returning the NEED_ EXCL flag from the xbegin instruction. this will result in a call to the cx_exclusive aPi, which waits until the lock is free, and acquires the lock using the xcas instruction to atomically compare and swap the lock variable, and which invokes the contention manager to arbitrate any conflicts on the lock. the cx_end aPi exits a critical section, either by ending the current transaction, or releasing the lock.

cx_optimistic

Use transactions, restart on I/O attempt

void cx_optimistic(lock) {
status = xbegin;
if(status==NEED_EXCL) {
xend ;
if(gettxid)
xrestart(NEED_EXCL);
else
cx_exclusive(lock);
return; }
while(!xtest(lock, 1));

}

cx_exclusive

Acquire a lock, with contention manager

void cx_exclusive(lock) { while( 1) { while(*lock != 1);

if(xcas(lock, 1, 0)) break;

}

}

cx_end

Release a critical section

void cx_end(lock) { if(xgettxid) xend; else

*lock = 1;

}

cx_optimistic and cx_exclusive assures the maximum concurrency while maintaining safety.

4. 2. converting linux to txlixux-cX

While the TxLinux-SS conversion of the kernel replaces spinlocks in selected subsystems with bare transactions, TxLixux-CX replaces all spinlocks with cxspinlocks. The API addresses the limitations of transactions in an OS context, which not only made it possible to convert more locks, but made it possible to do it much more quickly: in contrast to the six developer years required to create TxLinux-SS, TxLixux-CX required a single developer-month.

5. htm a WaRe scheDulinG

This section describes how MetaTM allows the OS to communicate its scheduling priorities to the hardware conflict manger, so the TM hardware does not subvert OS scheduling priorities or policy.

5. 1. Priority and policy inversion

Locks can invert OS scheduling priority, resulting in a high-er-priority thread waiting for a lower-priority thread. Some OSes, like Solaris, have mechanisms to deal with priority inversion such as priority inheritance, where a waiting thread temporarily donates its priority to the thread holding the lock. Recent versions of RT (Real-Time) Linux implement priority inheritance as well. Priority inheritance is complicated, and while the technique can shorten the length of priority inversion, it cannot eliminate it. In addition, it requires conversion of busy-waiting primitives such as spinlocks into blocking primitives such as mutexes. Conversion to mutexes provides an upper bound on latency in the face of priority inversion, but it slows down response time overall and does not eliminate the problem.

Simple hardware contention management policies for TM can invert the OS scheduling priority. HTM researchers have focused on simple hardware contention management that is guaranteed free from deadlock and livelock, e.g., timestamp, where the oldest transaction wins. ²⁰ The timestamp policy

does not deadlock or livelock because timestamps are not refreshed during transactional restarts—a transaction will eventually become the oldest in the system, and it will succeed. But if a process with higher OS scheduler priority can start a transaction after a process with lower priority starts one and those transactions conflict, the timestamp policy will allow the lower priority process to continue if a violation occurs, and the higher priority process will be forced to restart.

Locks and transactions can invert not only scheduling priority, but scheduling policy as well. OSes that support soft real-time processes, like Linux, allow real-time threads to synchronize with non-real-time threads. Such synchronization can cause policy inversion where a real-time thread waits for a non-real-time thread. Policy inversion is more serious than priority inversion. Real-time processes are not just regular processes with higher priority, the OS scheduler treats them differently (e.g., if a real-time process exists, it will always be scheduled before a non-real-time process). Just as with priority inversion, many contention management policies bring the policy inversion of locks into the domain of transactions. A contention manager that respects OS scheduling policy can largely eliminate policy inversion.

The contention manager of an HTM system can nearly eradicate policy and priority inversion. The contention manager is invoked when the write-set of one transaction has a non-empty intersection with the union of the read- and write-set of another transaction. If the contention manager resolves this conflict in favor of the thread with higher OS scheduling priority, then transactions will not experience priority inversion.

5. 2. contention management using os priority To eliminate priority and policy inversion, MetaTM-provides an interface for the OS to communicate scheduling priority and policy to the hardware contention manager (a mechanism suggested by other researchers^{14, 22}). Meta TM implements a novel contention management policy called os_prio. The os_prio policy is a hybrid of contention management policies. The first prefers the transaction with the