Computer Laboratory

Systems Research Group – NetOS

Practical lock-free data structures

Student projects

Some of our recent research on lock-free programming has been looking at how to provide concurrency control primitives that are easy to use (i.e. hopefully more natural constructs for mainstream programmers than things like the mutexes, condition variables and semaphores covered in Part 1B CS&A).

One promising approach is to automate the difficult aspects of the programming and to allow the programmer to use a higher level syntax. For example, to transfer a value between two hash tables they could write:

        atomic {
          Object val = h1.remove(key);
          h2.insert (key, val);

We have an initial implementation of this built of a Software Transactional Memory (STM). Essentially, the STM provides read-word and write-word operations and a way of grouping them together into atomic transactions. Our paper at OOPSLA 2003 has more details. In many cases this system performs better than a simple implementation using the synchronized keyword.

There are a number of possible student projects that could build on this work:

  • Our current implementation has focused on the STM; the rest is a mess of unreleasable code. In particular, the compiler support for mapping atomic onto a series of STM operations would benefit from being thought out more clearly and implemented more carefully.
  • As part of his PhD work, Keir Fraser has developed an alternative STM with a different object based interface. It would be interesting to explore whether this can also be used to implement a construct such as atomic.

    Both of these projects would involve design work followed by modification to the javac source-to-bytecode compiler. Please contact Tim Harris if you are interested in either, of if you have your own suggestions in this area.