Software Transactional Memory

Table of Contents

This is a pair programming assignment. If you are on a team, this means that you and your partner should be doing the entirety of this assignment side-by-side, on a single computer, where one person is "driving" and the other is "navigating." Take turns every 15 minutes and use a timer to help you manage this.

Introduction

Software Transactional Memory (STM) is a mechanism for concurrency control in shared-memory programs, the idea for which originated in the database community. The basic concept is that critical sections of code in your program can be labeled as atomic blocks: 

atomic {
    int balance = account.getBalance();
    balance += 100;
    account.setBalance(balance);
}

Within atomic blocks, you can reason about your code as if the program were sequential. The language implementation ensures that atomic blocks execute atomically (all-or-nothing) and in isolation (without interference from other threads). Or, to be more precise, the execution behaves as if atomic blocks executed atomically and in isolation; in reality, atomic blocks in different threads may execute in parallel, but the program's behavior should be indistinguishable from an execution with no parallelism.

Terminology

A few pieces of terminology are standard:

  • A transaction is an attempted execution of atomic block at runtime.
  • When a transaction finishes executing its code, it attempts to commit. Committing a transaction makes its effects permanent.
  • The attempt to commit may fail if, for example, a memory location that the committing transaction read has been changed. In this case the transaction aborts instead of committing.
  • If a transaction aborts, the implementation should undo the side effects of the transaction (if any) and retry the transaction from the beginning.

In this project, we'll take a so-called "lazy" (as opposed to "eager") approach to STM. This means that updates to memory are kept in a thread-local buffer, and only made visible to other threads after the transaction has committed. (An eager approach updates memory locations directly during transaction execution and undoes its updates in the event the transaction aborts.) Implementing a lazy STM means that the most important and delicate part of your code will be the commit operation: this method must determine if it is safe to commit and, if so, update any modified memory locations.

Research challenges

The research community is pretty excited about transactional memory, though integrating into mainstream languages has been slow for a variety of reasons:

  1. Performance is lackluster because of all the overhead involved.
  2. Aborting means that all side effects of the transaction should be undone, which raises some tricky questions. What do you do about print statements, issued during a transaction, for example?

Nonetheless, STM is of great interest to language experts and efforts are being made to bring it to mainstream programming languages (e.g., this specification for adding transactions to C++). It appears to be only slowly being implemented, though gcc has done so. Furthermore, the language Clojure supports STM, and has been gaining some traction.

Implementing the STM

It's your job to implement a STM in Java. You'll be submitting this in multiple revisions, described at the end of this section. What follows first is a description of the entire STM implementation.

The beginnings of the library are in the folder carlstm. The class STM provides a static method execute, which takes a Callable object to run. This is our version of an atomic block; instead of using atomic { CODE }, we use a slightly more cumbersome syntax: 

T result = STM.execute(() -> {
    // Your code here
    return something;
}

It ends up being very convenient to have transactions return a value, so the code within STM.execute() returns a value of type T. Note that we are making use of a Java 8 lambda expression here. If you have not come across lambda expressions in Java before, you may find this Java magazine article or this official Java tutorial useful, though long-winded.

Transactional objects

We'll avoid some of the challenges described in the introduction by not providing true atomicity and isolation, as we would expect from a "real" STM. We will instead support atomicity and isolation only for limited types of operations. Specifically, transactions can read and write special transactional objects, which are objects from the class TxObject. If you implement your STM correctly, all reads and writes of TxObjects within a transaction should happen atomically and in isolation.

As an example, look at the file SimpleTransaction.java in examples. This program creates a shared TxObject x and executes two transactions, each of which increments x five times each. (Note that we're cheating a bit here by putting println statements in the transactions; these won't/can't be undone.)

TxObjects are defined in TxObject.java, much of which has been left for you to implement. They support two operations: read() and write(). Both of these operations must be called from within a transaction; any other calls should result in a NoActiveTxException.

The value field of each TxObject should be protected by a lock. This will be important during transaction commit.

Lazy buffering

So, how should you actually implement the STM? The technique you should use is called lazy buffering. In lazy buffering, each transaction maintains a private data structure recording which TxObjects it has read and/or written during its current execution attempt. Specifically, for each TxObject touched by the transaction, you should track the object's "old" value (the value seen the first time the TxObject was accessed) and the object's "new" value (the value most recently written to the object by the transaction, or the old value if no writes have occurred).

You should store each transaction's updates in an object of type TxManager. You'll need to add the appropriate data structure(s) to this file. When a transaction calls read() or write() on a TxObject, those methods should delegate to the current transaction's TxManager instead of directly reading or writing the value field of the TxObject class.

Note that the TxObject value field should only be accessed in three cases:

  • when the TxObject is created
  • the first time a transaction calls read() or write() on the TxObject
  • during transaction commit.

You'll have to deal with a few tricky details in writing the TxManager class:

  • One difficulty is how to find a transaction's TxManager onject. Java provides a convenient way of storing thread-local data. Look at the documentation for java.lang.ThreadLocal for more information. You should be able to use this functionality to retrieve the current thread's TxManager from wherever you need it.
  • You're going to do a lot of battle with Java generics to get everything to line up right. Feel free to work through Oracle's tutorial on generics if you would find that helpful. One annoying detail is that Java's generics can't really express the idea of "I want a list of pairs of objects in which both objects have the same type, but different pairs may have different types." You'll have to use the "unknown" type ? (e.g., TxObject<?>) and/or "raw" types (e.g., TxObject). This means you'll have warnings about unsafe casts in your code. So be it. You're allowed to add @SuppressWarning annotations to get rid of them if you need to.

Executing a transaction

When a program executes a transaction using STM.execute(), the following steps should take place:

  1. Find the current thread's TxManager and call its start() method. This should toggle a flag in the TxManager indicating a transaction is active. If a transaction is already active, TxManager.start() should throw a AlreadyActiveTxException. (See bonus work for more on nested transactions.)
  2. Call the transaction's call() method to execute the atomic block.
  3. If call() throws an AbortedTxException, call TxManager.abort() to clean up any transactional state and go back to step 1 to retry the transaction.
  4. Call TxManager.commit() in order to attempt to commit the transaction. (More later on what exactly happens during commit().)
  5. If commit() returns true, the transaction is complete! Return the transaction's result.
  6. If commit() returns false, the attempt to commit failed and the transaction has aborted. In this case, commit() should have taken care of calling abort(). Go back to step 1 to retry the transaction.

Committing a transaction

The commit() operation is the most important part of our STM. As stated earlier, every transaction maintains a private buffer containing the old and new values for every TxObject read or written by the transaction. commit() tries to make the transaction's updates permanent. Since transactions must behave as if they executed atomically and in isolation, commit() must ensure that all of the TxObjects have their expected ("old") value. (We could probably ignore the "old" value for TxObjects that were written before being read, but that is unusual and not worth adding a special case for.)

Of course, it is crucial that no other thread change the value of a TxObject after commit() compares the TxObject's current value to the old value but before commit() updates the TxObject with the new value. Therefore, commit() should acquire locks for all of the TxObjects read or written by the transaction, and it should not release those locks until it has updated the value of every TxObject written by the transaction.. This ensures that the updates appear to happen "all at once" to other threads.

One tricky detail here is that acquiring multiple locks at the same time introduces the possibility of deadlock, which is not acceptable. There are multiple approaches to solving this problem. Here's my recommendation: try to acquire the lock for each TxObject, and if the lock is already held by another transaction, pessimistically choose to abort the transaction. You can use the trylock method of the java.util.concurrent.locks.Lock class to try to acquire a lock without blocking.

Performance optimizations

You are required to implement the following performance optimizations.

Read/write locks: Using regular locks for protecting TxObjects means that we cannot effectively exploit read parallelism. Therefore, you should use read/write locks instead of normal locks. Think carefully about where read locks can be used, as this will improve performance rather than using write locks.

Exponential backoff: Consider the case in which you try to acquire a read lock during call(). If the call to lock() blocks, that means some other thread is holding a write lock on that TxObject and will likely change its value. Therefore in this case, it makes sense to preemptively abort and retry the transaction. Use tryLock() to attempt to acquire the read lock; if tryLock() fails, throw an AbortedTxException and catch it in STM.execute().

It is usually not the best choice to retry the transaction immediately, since the other thread will still be holding the write lock for a while afterwards and the thread will fail again. Therefore you should implement exponential backoff: delay for a short period before retrying the transaction, and double the length of the delay every time the transaction fails again. Even delaying by a nanosecond should save you time wasted running and re-running doomed transactions. You should only delay if the transaction aborted due to a failed call to tryLock() in call() or commit().

STM Submissions

Breaking this project up into multiple pieces is challenging because so much of it is interdependent. You'll be submitting drafts that may not be entirely functional, but will demonstrate that you are making adequate progress.

Submission 1: Lazy buffering

For this submission, lazy buffering should be implemented as described above. You should have appropriate code written for TxObject, TxManager, and/or other classes as necessary to get the lazy buffering aspect of this assignment implemented. You should add either tests or debugging output (print statements and the like) to demonstrate that the methods you have written here are working. Submit a very short writeup describing what we should be looking for in order to see that you have lazy buffering implemented and working, even though my tests may be failing.

Submission 2: Executing and committing a transaction

You should have code that will execute and commit a transaction, though at this stage it may still be buggy. Nonetheless, it should be clear that you have all the essential pieces in place. Submit a very short writeup describing where we should look in your code to observe that you have the framework essentially implemented.

Submission 3: Executing and committing a transaction working and optimized

This is a repeat of the previous step, where your code should now be working. The SimpleTransactionTest should now be passing on multiple runs. That said, this test isn't sufficient, and we will run more intensive tests.

Applying your work to a hash table

This is where you finally apply your STM system to an actual data structure in order to make it parallel. The file SimpleHashSet.java gives a simple implementation of a separate chaining hash table. This implementation is not thread-safe.

Submission 4: STM Hash Table

In a class titled STMHashSet, modify SimpleHashSet to implement a version of the hash set using the STM transactional constructs. Each method that needs it should now use a single atomic block. Note that every reference that is neither read-only nor thread-local should be represented with a TxObject. You shouldn't be directly using any locks.

(Java has a built in thread-safe hash table. You should not use it for purpose of this assignment.)

Submission 5: Comparison approaches and writeup

For this last piece, you should completely ignore all the work you've done on STM, and implement two more versions of a hash table that instead use locking. Your work should again be based on the non-thread-safe SimpleHashSet that I provided.

  • Create a version called CoarseHashSet that uses a single lock for the entire set. Threads should acquire this lock for each method.
  • Create a version called FineHashSet that uses a lock per array index.

Submit a short writeup (a paragraph or two is fine) comparing the relative advantages of each of the three approaches.

Bonus Work

If you've finished the project, you can try these extensions out as a bonus:

  1. Nested transactions: Modify your implementation to allow nesting of transactions. This will require modifying the start(), commit() and abort() methods of TxManager. The updates of inner transactions should not become visible until the outermost transaction commits. Aborting an inner transaction should abort the entire transaction. Include in your submission a test case that demonstrates nested transactions.
  2. Print buffering: Add a print(String) method to STM. Calling this method allows "safe" printing inside a transaction; the printed Strings are buffered until the transaction commits, then printed to the screen. Include in your submission a test case that demonstrates print buffering.

Submission Details

Push all your code to your GitHub repository. You'll be doing this in steps, so use comments that look like "Submission 1 complete", "Submission 2 complete", etc, to let us know when you've submitted a complete version. If you decide to resubmit because you made a fix after submitting, use a comment like "Submission 1 resubmitted". If you resubmit yet again, use a comment like "Submission 1 resubmitted 2". And so on. As always, make sure your code is properly documented.

You should include a single file credits.txt that contains the following information:

  • Your name and your partner's name (if applicable).
  • A list of people, books, websites or other sources you used in the course of completing this project. Include anyone or anything except your partner, me, and the course materials. In particular, if you had more than a passing interaction with another student, or if you used code from a website as a starting point, list that information.

Please make sure your submission, other than the credits.txt file above, is anonymous. In particular, your name(s) should not appear in your write-up or in any of your Java code.