Composable Memory Transactions is an effort to make Software transactional memory composable. In this case compositionality means that correct program parts can be composed into bigger correct program parts without any knowledge of the underlying implementation. Software transactional memory is kind of lock free algorithms. ...

Problem example

Suppose we've got proper (correct) list operations get and set, which work pretty well. But when we compose them together, for example increasing element. That may give us unpredicted result, such as reading element first (correct get) increasing it, in meantime somebody have written other value to list, and then setting it to improper value.

Definitions

• Software transactional memory or STM - basic concept of lock-free transaction-like synchronization
• compositionality - ability of combining (composing) correct program parts into bigger program parts without loose of correctness.

Software transactional memory is kind of lock free algorithms. ... Software transactional memory is kind of lock free algorithms. ...

Underlying idea

To add compositionality to STM we need the following operations: Software transactional memory is kind of lock free algorithms. ...

• atomic(x) - execute block x atomically,
• retry - when executed inside atomic block, clear transaction log and try from the beginning,eventually sleeping if there was no significant changes to monitored memory
• or_atomic(x,y) - perform operation x and, if it fails, revert the effects caused by it and try y where x and y are parts of program which do not perform any irreversible I/O operations.

An additional enhancement to this is support for running exceptions from inside atomic block.

Original implementation was written by Tim Harris, Simon Marlow, Simon Peyton Jones and Maurice Herlihy for Glasgow Haskell Compiler version 6.4 Simon Peyton Jones is a British computer scientist who does research on the implementation and applications of functional programming languages, particularly lazy functional languages. ... The Glasgow Haskell Compiler (or GHC) is an open source Native code Compiler for the functional programming language Haskell which was developed at the University of Glasgow. ...

Implementations

Composable Memory Transactions are based on idea expressed in ^[1]. They've implemented idea in Glasgow Haskell Compiler which is in standard distribution beginning from version 6.4. The Glasgow Haskell Compiler (or GHC) is an open source Native code Compiler for the functional programming language Haskell which was developed at the University of Glasgow. ...

External links

• ^  http://research.microsoft.com/Users/simonpj/papers/stm/ - Original paper
• http://libcmt.sourceforge.net/ - implementation of CMT in C programming language (alpha stage, no API-stability yet)