Nested Transactional Variables

Printer-friendly version
Info
Advisors: 
Prerequisites: 

You should choose this topic if:

  • you are interested in programming languages, their design and implementation;
  • you are heavily interested in concurrency and parallelism;
  • you have followed or are planning to follow the course "Multicore Programming";
  • previous experience with Clojure or Scala is a plus.
Context: 

Multi-core processors have become ubiquitous, so programs need concurrency to exploit the hardware efficiently. However, programming with concurrency is notoriously difficult. Mutable state that is shared between threads should be protected to prevent race conditions. Locks are one mechanism to achieve this protection, but they are very error-prone and difficult to compose. Forgetting to acquire a lock can lead to race conditions; acquiring locks in the incorrect order leads to deadlocks. Software Transactional Memory is an alternative technique, in which memory operations are protected using atomic transactions. STM is implemented using optimistic synchronization, freeing the programmer from having to specify which memory locations to lock. Moreover, STM is free from deadlocks.

STM encapsulates shared memory locations in "transactional variables" (TVar), and allows these to be accessed in transactions delimited by "atomic" blocks. For example, in Haskell a user's bank account might be represented as:

checking :: TVar Int
checking = newTVar 100 -- create a checking account containing €100
withdraw account amount = atomically $ do
    old <- (readTVar from)
    writeTVar account (old - amount)
withdraw checking 50   -- withdraw €50

Now imagine we have a database consisting of many users:

data User = User { name :: String, checking :: Int, savings :: Int }
accounts :: [User]

To make this data transactional, we can choose several levels of granularity:

accounts :: TVar [User]
accounts :: [TVar User]
accounts :: [(TVar String, TVar Int, TVar Int)]

or even:

accounts :: TVar [TVar (TVar String, TVar Int, TVar Int)]

Depending on the level of granularity, the amount of concurrency varies (many TVars allow more concurrency), the number of conflicts will vary (one global TVar leads to more contention), and the difficulty of writing code varies (finer-grained concurrency leads to more complex code).

The proposal of this thesis is to investigate whether it is possible to simplify this for the programmer, by introducing "nested transactional variables". It should then be possible to write:

accounts :: NTVar [User]

This nested TVar should allow high concurrency while being easy to use.

Goal & Research Activities: 

The goal of this thesis is to investigate how to represent nested transactional variables, to develop an implementation (in Clojure, Scala, or Haskell), and to evaluate it using several example programs.

In a first phase, you will implement several example programs that use transactional variables containing complex data structures. This will allow you to investigate which problems and usage patterns occur in a typical application. You will examine the trade-offs between using transactional variables at coarser-grained or finer-grained levels. You will also write pseudo-code to demonstrate how these programs could be written using nested TVars.

In a next phase, you will develop a prototype implementation of nested TVars. This could be on top of an existing implementation of STM, for instance the implementation in Clojure using macros seen in the "Multi-core Programming" class. It is possible you will need to provide your own implementations of some collection classes for this purpose (e.g. TransactionalMap, TransactionalList...).

Finally, you should be able to run the "pseudo-code" of the first phase using your new implementation. You can then evaluate how easy it is to write such programs, and what the implications are on performance.

References: 

General info:

Papers on STM:

  • Harris, T., Marlow, S., Peyton Jones, S., & Herlihy, M. (2005). Composable memory transactions. In Proceedings of the tenth ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP ’05), p. 48–60.
  • Peyton Jones, S. (2007). Beautiful concurrency. In Beautiful Code. O’Reilly.
  • Shavit, N., & Touitou, D. (1997). Software transactional memory. Distributed Computing, 10(2), 99–116.