STM (Software Transactional Memory) is a concurrency control mechanism for managing access to shared memory. In the traditional threaded model of concurrent programming, when we share data among threads, we keep it consistent using locks. A lock is an object which signals ownership of some resource, and which has one really important property; it references at most one process, and when you want to look at it and update it, nothing can intervene between the read and write. On simple systems, reasoning in terms of threads and locks is relatively simple. But as soon as the system grows in complexity, it becomes really complicated to understand and debug hundreds of threads updating several shared variables. A typical issue is a deadlock; when two threads wait on each other to acquire a resource they are locking.
There are several methods that try to make it easier to do coordination between multiple tasks such as enforcing ordering, semaphores, and monitors.
STM tries to resolve the problem of accessing shared memory introducing a well-known semantic: transactions. In the same way as database engines protect their data, with STM we can protect data against concurrent access.
STM enforces the organization of code into transactions. A transaction makes the code run in atomic isolation. The data used by the transactional code remains consistent irrespective of whether the transaction finishes normally or abruptly. The transactional code modifies the data while other tasks do not see the modification until the transaction is committed.
Groovy has support for Software Transactional Memory through the GPars library. To enable the STM API it is necessary to add a dependency to the Multiverse library. Multiverse is a Java-based Software Transactional Memory implementation for the JVM.
This recipe will show how a number of threads can incorrectly update a global variable (a simple counter) and how to fix the problem using STM.
In order to use STM with GPars, we need to add a dependency to the Gradle build script shown in the introduction of this chapter.
compile('org.multiverse:multiverse-beta:0.7-RC-1') { transitive = false }
At the time of writing, the GPars API 1.0 are still using a beta version of Multiverse.
The following steps will introduce us to the world of STM with the help of GPars and Multiverse.
package org.groovy.cookbook.stm import static org.multiverse.api.StmUtils.newIntRef import groovyx.gpars.actor.* import groovyx.gpars.stm.GParsStm import org.multiverse.api.references.IntRef class StmValueIncreaser { int value = 0 IntRef stmValue = newIntRef(0) ... }
StmValueIncreaser
class:// Message final class Increase { } final class ValueAccessActor extends DynamicDispatchActor { void onMessage(Increase message) { value++ // unsafe increment GParsStm.atomic { stmValue.increment() // safe increment } } }
def actors = [:] Random random = new Random() int max = 20 Map start() { // init actors (1..20).each { actors.put(it,new ValueAccessActor().start()) } // spawn actors and increase counter (1..100).each { actors.get(rnd(1,20)) << new Increase() } ( actors.values()*.stop() )*.join() int stmProtected = 0 GParsStm.atomic { stmProtected = stmValue.get() } ['withStm': stmProtected, 'noStm': value] }
// return random number from range def rnd = { from, to ->random.nextInt(to - from + 1) + from }
@Test void testFrequency() { def stm = new StmValueIncreaser() def results = stm.start() assert results.get('withStm') == 100 assert results.get('noStm') != 100 }
So, what is happening in this class? The start
method initializes twenty stateless ValueAccessActor
actors and puts them into a Map
. The key of the Map is the number of the actor (1, 2, 3,...20). These actors only accept one type of message, the very anemic Increase
.
After the actor initialization, the code loops one hundred times, and for each iteration it sends a Increase
message to one of the actors in the actor pool. Note that each message is sent to a randomly chosen actor:
actors.get(rnd(1,20))
The reason for the random message sending, is that we want to reproduce several threads accessing the same variable concurrently. Using a single actor would defy the purpose of this exercise, as actors process messages through a mailbox, sequentially, one after the other. Accessing the actor in a round-robin fashion would also decrease the chances of a race condition on the variable.
Upon message reception, the actor does two simple operations; it increases the two variables by one unit, defined in the body of the class.
The first variable is, well, just a variable which gets hammered by the actors. Each message increments the variable by one unit. The second variable is an STM
variable. The variable can only be updated atomically, in the context of a globally defined STM transaction.
The actor increase the variables in two different ways:
value++ GParsStm.atomic { stmValue.increment() }
The value
variable gets incremented without any lock. Several actors running on different threads will read and write the variable at the same time.
The GParsStm.atomic
static method runs the closure inside a transaction, and the value of stmValue
gets updated atomically.
Each actor sees its "own copy" of the variable and the increase operation is executed and committed by each actor running on its own thread. This guarantees that, when we finally access the stmValue
after the 100 messages have been fired, the value of the variable is actually 100. On the contrary, the value
variable's value changes at every test run. It fluctuates between 14 and 35, depending on a number of factors, such as number of cores and speed of the hardware.
The unit test can be used to verify that the STM "protected" variable is always set to 100 while the other variable is always smaller than 100.
STM is a very powerful tool in the hands of the "concurrent developer". It is important to understand that this power doesn't come cheap. A simple increment of an Integer
variable does indeed provoke many more CPU cycles than the couples required to update a variable in Java. If we run javap -c
over the Java bytecode produced by the compilation of the StmValueIncreaser
class, we will see a very long Java bytecode list of instructions. Removing the STM references, the bytecode shrinks dramatically. This shows that the Multiverse STM implementation used by GPars is not lightweight. Nevertheless it's a very efficient paradigm to reason about and implement heavily concurrent systems. In this recipe, we addressed a relatively simple problem that could also have been solved using the JDK's AtomicInteger
. However Multiverse supports many more data types and data structures: take a look at the documentation and Javadoc for a deeper understanding of what the framework has to offer.