As a simple example, we’ll build a doubly-linked list that can be safely used by multiple threads or actors. We’ll teach our list how to be a blocking queue, and then we’ll add the ability to select the next available element from several queues.
If you use
sbt, add the following dependency to your project
build.sbt and run
sbt update. Maven2 configuration and manual
download links are here.
Use Ref for shared variables
In our mutable linked list, we need thread-safety for each node’s next
and prev pointers. In general, if it is possible that one thread might
write a variable at the same time that another thread is accessing it
(reading or writing), then the STM needs to be involved by using a
Ref is a single mutable cell; there are also transactional
TSet) that are replacements for
To make the code simpler we make the list circular, with an extra header node. On creation, the header’s next and prev point to itself. The next and prev pointers are always non-null.
Wrap your code in atomic
x is a
x() gets the value stored in
x() = v sets it to the value
Ref-s can only be read and written inside an atomic block. This is
checked at compile time by requiring that an implicit
InTxn value be
available. Atomic blocks are functions that take an
so this requirement can be satisfied by marking the parameter as
Compose atomic operations
Atomic blocks nest, so you can build compound operations from simple ones.
Optimize single-operation transactions
Ref.single returns an instance of
Ref.View, which acts just like the
Ref except that it can also be accessed outside an atomic
block. Each method on
Ref.View acts like a single-operation
transaction, hence the name.
Ref.View provides several methods that
perform both a read and a write, such as
transform. If an atomic block only accesses a single
Ref, it might
be more concise and more efficient to use a
Wait for conditions to change
retry keyword when an atomic block can’t complete on its
current input state. Calling
retry inside an atomic block will cause
it to roll back, wait for one of its inputs to change, and then retry
execution. This is roughly analogous to a call to
wait where ScalaSTM
automatically generates the matching
notifyAll. As part of its
implementation of optimistic concurrency the STM keeps track of an
atomic block’s read set, the set of
Ref-s that have been read during
the transaction. This means that the STM can efficiently block the
current thread until another thread has written to an element of its
read set, at which time the atomic block can be retried. This makes it
trivial to wait for complex conditions, and eliminates lost wakeups.
To demonstrate, we’ll add a function to our list that waits until the list is non-empty, then removes and returns the first element.
Wait for multiple events
Another way to proceed after an atomic block ends in
retry is to
provide an alternative. You can chain atomic blocks using
the lower alternatives will be tried if the upper ones call
This lets you compose functions that block using
retry, or to convert
to and from blocking behavior.
For example, we can use the blocking version of
construct one that returns an
Option, by providing an alternative.
It is also easy to switch from a function that returns a failure code to
one that blocks. The following
select method waits until one of its
inputs is non-empty, then removes an element from that list.
Be careful about rollback
ScalaSTM might need to try an atomic block more than once before
optimistic concurrency can succeed. Any call into the STM might
potentially discover the failure and trigger the rollback and retry.
Ref variables that have a lifetime longer than the atomic
block won’t be rolled back, and so they should be avoided. Local
variables used only inside or only outside the atomic block are fine,
badToString is incorrect because it uses a mutable
StringBuilder both outside and inside its atomic block. The return
value will definitely mention all of the elements of the list, but it
might include some of them two or more times.
toString is correct
because it uses a new
StringBuilder for each atomic attempt.
Look at the source
This list example is part of the source on GitHub: ConcurrentIntList.scala