CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

XJava: Java Support for Transactions Everywhere

C. Scott Ananian, Bradley C. Kuszmaul, Charles E. Leiserson, Gideon Stupp & Jim Sukha

Introduction

The most basic problem inherent in the coordination of concurrent tasks is the enforcing of atomicity so that the partial results of one task do not inadvertently corrupt another task. Atomicity is typically enforced through locking protocols, but these protocols can introduce other complications, such as deadlock, unless restrictive methodologies in their use are adopted.

The Transactions Everywhere project in the Supercomputing Technologies Group (Supertech) focuses on using transactional memory (originally proposed by Herlihy and Moss [1]) as a tool for simplifying concurrent programming. Adopting the view that transactions should be the rule rather than the exception, we construct novel mechanisms for transaction support in Java by borrowing ideas from nonpreemptive multitasking systems.

Nonpreemptive Multitasking Systems

Twenty years ago nonpreemptive multitasking operating systems were in many cases the default choice (Windows 3.1, Mac OS). Although this was mostly due to their simple architecture, it also turned out that writing multi-process programs for this environment is relatively simple. The reason is that in such an environment once a process gets hold of the CPU it can run for as long as it needs, up until it explicitly yields to other processes, so synchronization is almost never an issue. Such systems, however, had many disadvantages, most notably, a long loop in a single process could freeze the entire machine. It became notoriously difficult to figure out where and when to yield, particularly when writing library routines called by other programs. As a result, user responsiveness degraded greatly as more and more processes were executed concurrently. In fact, user-perceived responsiveness has been one of the main motivations for preemptive multi-threading in the single CPU desktop.

Goals

Our goal is to try and bring the programming simplicity of nonpreemptive systems to modern software development, without compromising the advantages of the preemptive operating-system environment. We use the transactional memory synchronization primitives to create causal ordering among transaction blocks (the code fragment between two yield operations). That is, if there is some memory address that is accessed both while in transaction block A and while in transaction block B then either A fully executes before B or vise versa, even if they are executed by different threads. In practice, the runtime executes each transaction block within a separate memory transaction, and if a collision happens then at least one of the transactions is rolled back and automatically retried. Totally independent transaction blocks, however, execute in a truly concurrent way. Thus, not only process and OS separation is kept, but the programming complexity of a single multi threaded application is reduced, since blocking occurs only when necessary. For example, a server application that spawns many independent threads to support multiple independent clients need not worry about their interaction with each other.

Progress

A fundamental design decision we made was that every plain Java program that executes correctly in a single thread must execute correctly using multiple threads in XJava. We made this choice because typically programmers start by thinking about code in a serial way and add concurrency only afterwords. The basic XJava model is that by default there is a single transaction in each thread. If two or more threads share a resource their execution would be serialized with respect to each other. Two independent threads, however, would execute concurrently just as they would in a standard Java runtime. Note that all the transaction rollbacks and retries are automatically executed by the runtime in a way transparent to the programmer, thus creating the illusion of a nonpreemptive environment.

To add concurrency, XJava supports the yield keyword which breaks the context of a single transaction block into several parts. In the following code, for example, each iteration of the loop would be executed in the context of a different transaction.

class Worker implements Runnable {
  Stack s=nil;

  Worker(Stack s) {
    this.s=s;
  }

  void run() { 
    for(int i=0;i<10;i++) {
      int  j = (int)(Math.random() * 100);
      s.push(j);
      System.out.println(s.pop());
      yield;  // <---  yield in run() breaks the transaction.
  }
}

While simply using yield was sufficient twenty years ago, current object-oriented practices require better control over the concurrent execution. Much of our current work is focused on finding the correct abstractions that will enable us to seamlessly integrate nonpreemptive concepts with object oriented programming.

Future Work

We are still finalizing the the linguistic aspects of XJava. In particular, a crucial step is to find loophole mechanisms that would allow the independent execution of transactions within transactions (nested independent transactions) for debugging purposes, for example. Furthermore the interplay between the compiler, the (X)Java runtime, the operating system and the hardware must be further explored if we want to achieve a realistic model for this new programming paradigm. Finally, support tools such as data race detectors [2] and multi threaded profilers should be developed to create a full, modern development environment.

Research Support:

This research is supported in part by the Singapore-MIT Alliance and by NSF Grants ACI-0324974, CNS-0305606 and by the Fulbright foundation.

References:

[1] M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the Twentieth Annual International Symposium on Computer Architecture, 1993.

[2] Kai Huang. Data-Race Detection in Transactions-Everywhere Parallel Programming. Master's Thesis . Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology June, 2003

[3] C. Scott Ananian, Krste Asanovi'c, Bradley C. Kuszmaul, Charles E. Leiserson, and Sean Lie. Unbounded Transactional Memory. Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA'05). CSAIL, Massachusetts Institute of Technology June, 2005.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)