Software Transactional Memory

SoftwareTransactionalMemory, or STM, provides transactional access to regular memory. This is generally implemented as an optimistic approach to concurrency control. Unlike locking, STM is also composable, meaning that procedures using STM can call arbitrary other procedures using STM without risking deadlock. (Lock based concurrency is generally not composable.)

Among the significant benefits, STM allows complex atomic transactions across memory cells, often without waiting and generally successful in many environments. Absent the locking, PriorityInversion problems are reduced due to the ability to abort other transactions and complete a higher-priority one. In a networked or distributed environment, there is far less danger in the face of communications failure -- things generally won't grind to a halt, though failure recovery is still a bear, esp. on a network (requiring atomic multicast). The system also avoids the use of locks at the higher level abstraction: no locks are needed at all across cells, so nobody needs to remember to use them, and DeadLock is no longer an issue. (Of course, LiveLock may prove to be a problem when requesting a resource in intense demand.)

This does come at a cost -- a O(N) space and processing cost per cell of SharedMutableState? for N threads concurrently interacting with each cell, plus constant costs for the STM service (e.g. mutexes or monitors over the cells, tracking whom is interacting with each cell, who wants to commit, etc.) The constant overhead penalty to regular access often raises even non-concurrent and unit-transactional time and space costs to twice that of the faster coarse-grained semaphore solutions on local memory (which, in turn, can cost twice as much as single-threaded operations when protecting data at a fine granularity). Anyhow, the performance hits are sufficient arguments to avoid turning all MutableState into STM even among its avid afficionados, and to limit it, instead, to only SharedMutableState? and PersistentState?. (A local thread stack shouldn't require such largess).

There are also hidden benefits: STM integrates very naturally with TransparentPersistence, OrthogonalSecurity, and VersionControl at the cell-level. The action of starting transactions, as separate from the regular access, provides an opportune moment for one-time-checks, while the interaction log makes for good history information if the important bits are kept around. (This can be done for locks, too, since they have a clear beginning and end. However, the integration isn't nearly so natural because locks are fundamentally separate objects from the cells they are locking, and guaranteeing that users of lockable cells actually bothered to lock them can be difficult.)

External Links See:

See also: AtomicConsistentIsolatedDurable, TransactionalActorModel, SynchronizationStrategies


EditText of this page (last edited January 26, 2009) or FindPage with title or text search