We plan to implement a library providing software transactional memory support in the Rust programming language (on AMD64, but without TSX support).
Transactional memory (TM) is a concurrency control mechanism for managing access to shared memory in multithreaded programs. We talked about a hardware implementation of TM in class, and we plan to work on a software implementation. This means transactional memory without reliance on hardware support, making it possible for programs that want to use TM to run on multiple machines with different hardware specs.
In a program using TM, each thread may request modifications to (potentially) shared resources without regard for what other threads might be doing (even to the same shared memory). When and how read/write or write/write conflicts are resolved depends on the conflict resolution policy adopted. Contrast this with the traditional locking mechanism, which restricts access to a common resource to only a single thread at a time.
Arguably, STM should provide superior performance to traditional locking, as it should allow concurrent execution of threads competing for shared resources to a greater extent. Moreover, it removes the need for the programmer to explicity manage the synchronization between the different threads, allowing them to work at a higher level of abstraction. Manual lock management often leads to problems such as deadlock and livelock that the programmer has to worry about — liberating a programmer from such concerns can be a boon to both correctness and productivity. Hence, we aim to show (our implementation of) STM a viable alternative to traditional locking by comparing the performance of parallel programs written both ways.
For this project, we will have to develop an entire working STM library in Rust, a language that neither of us is very familiar with.
Additionally, difficult issues come up when implementing TM. For instance, if effectful operations (such as I/O) are performed within a transaction, problems arise if the transaction fails and has to be retried. Furthermore, implementing a correct concurrency mechanism is itself a challenging undertaking with many subtleties. For instance, STM has to ensure progress in program execution, which entails detecting and resolving certain conflicts. Another consideration is dealing with exceptions that can arise due to a thread performing unsafe memory operations. On top of all this, interaction with non-transactional code has to be handled in a consistent manner.
Beyond correctness, there is also the concern of efficiency. STM incurs significant overhead as a result of (in a possible implementation) having to maintain logs of data reads/writes for each thread.
We’ll have to familiarise ourselves with Rust, probably by going through the Rust book.
We’re considering one of either NOrec or TL2 for our implementation.
We intend to try for an optimistic STM implementation that, in the good case, is at least competitive with the performance of programs written without STM.
With extra time, we might try for a pessimistic implementation of STM as well, and compare and contrast the two.
At the demo, we will show graphs comparing our STM implementation against locking programs and other implementations. If we write really cool interactive testing programs, we’ll also demo those.
We plan to target AMD64 without TSX or other hardware transactional memory features. We chose AMD64 because of ease of access to development hardware. We’re going with the no hardware support option because