Master’s Thesis: Mergeable Objects in Software Transactions

August, 2015

The advent of multi-core systems has made concurrent programming wide-spread in order to utilize additional computing capacity. Classical lock-based synchronization often relies on the programmer’s expertise to avoid deadlock and livelocks. Transactional Memory (TM) provides an abstraction for concurrent access to multiple shared objects, similar to transactions in a database systems. TMs guarantee safe access to shared objects and provide features such as atomicity and isolation, without demanding explicit synchronization from the programmer.

Many TM models are based on serializability of transactions. If two transactions access the same shared object, and at least one of them modifies this object, a conflict is detected and one of the transaction has to be aborted and re-executed. In a highly concurrent application, high contention in shared memory may result in large numbers of aborts, which in turn results in lower performance.

Mergeable Transactional Memory (MTM) is an alternative to the serializable transactions. Under MTM, transactions operate concurrently on shared objects without introducing conflicts. All updates from a transaction become visible together. Instead of aborting and re-executing, transactions commit their changes which in case of conflicts are merged together. Mergeable transactions are realized using special data structures with merge functions which handle the conflict resolution according to the semantics of the abstract data type that is implemented. These data structures are referred to as Mergeable Objects. An efficient merge operation enables MTM to execute multiple updates in parallel to other threads and execute the merge inside the critical section.

The goal of master thesis is to

  • Implement TM library in Java to support Mergeable Objects
  • Evaluate the library for performance using existing benchmarks

Prerequisite

  • Knowledge in Java programming
  • Basics of concurrent programming

Contact