PPoPP 2008 - Safer Open-Nested Transactions Through Ownership

Safer Open-Nested Transactions Through Ownership (poster presentation)

Kunal Agrawal, I-Ting Angelina Lee and Jim Sukha

The 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2008)
Salt Lake City, Utah, February 20-23, 2008

Abstract

Researchers in transactional memory (TM) have proposed open nesting as a methodology for increasing the concurrency of a program. The idea is to ignore certain ``low-level'' memory operations of an open-nested transaction when detecting conflicts for its parent transaction, and instead perform abstract concurrency control for the ``high-level'' operation that nested transaction represents. To support this methodology, TM systems use an open-nested commit mechanism that commits all changes performed by an open-nested transaction directly to memory, thereby avoiding low-level conflicts. Unfortunately, because the TM runtime is unaware of the different levels of memory, an unconstrained use of open-nested commits can lead to anomalous program behavior.

In this paper, we describe a framework of \emph{ownership-aware} transactions which incorporates the notions of modules and memory that modules own into TM semantics. By constraining the sharing of data between \emph{transactional modules} (Xmodules) based on familiar notions of abstraction and by organizing Xmodules into levels, we show that ownership-aware TM has clean memory-level semantics that can provide provable guarantees of some form of abstract serializability.

More specifically, we propose a new \emph{ownership-aware commit mechanism}, a hybrid between an open-nested and closed-nested commit which commits a piece of data differently depending on whether the current Xmodule owns the data or not. Using the framework of transactional computations from our prior work, we describe the OAT model, an operational semantics for ownership-aware TM. We prove that the OAT model guarantees \emph{serializability by modules}, an adaptation of multilevel serializability from databases to TM. Finally, we prove that if transactions in the process of aborting obey restrictions on their memory footprint, the OAT model is free from \emph{semantic deadlock}.

START Conference Manager (V2.54.5)