Locks and condition variables go together.
synchronized (when used
properly) makes sure that a group of reads and writes isn’t interleaved
with the actions of another thread.
wait let threads
wait for a condition to become true.
atomic fills the same role as
retry is safer and more powerful. With
transactional waiting the STM automatically identifies the
that should lead to wakeup, so you don’t have to call
means that there is no chance of lost wakeup. It also means that you can
wait for any condition to become true, not just those that were
identified ahead of time.
Search with backtracking
To explain how
retry works (and why it’s called
retry), it is
helpful to think of optimistic concurrency control as a search with
backtracking. As an atomic block executes it is searching forward. At
each step, if the STM discovers that the current search can’t proceed
then it backs up (rolls back) and tries again. In this analogy the
transaction is attempting to find a path of
Ref reads that avoid the
Ref writes performed by other threads.
To make this more concrete, consider the following two atomic blocks
that each access a pair of
sum method returns their sum,
transfer method increments one and decrements the other.
transfer should not affect the value returned from
transfer(2) are run simultaneously and
sum is unlucky,
it might look like this
The first time that
sum tries to read
y, the STM detects that the
value previously read from
x is no longer correct. This means that the
transaction attempt (search) has reached a dead end and the system
should roll back (backtrack) and try again. On the second attempt to
compute the sum both of the reads are consistent and so the transaction
can commit (the search is successful).
When an atomic block calls
retry it is signalling that the current
search is a dead end, even though all of the reads and writes are
consistent. The STM will backtrack and then try again. If some of the
Ref-s read by the transaction have changed before the new attempt,
then the atomic block may take a different path that avoids the call to
retry. The condition that
retry waits for is implicitly embedded in
the control path of the atomic block.
For example, to wait until
x is greater than 10, just write
if (x() <= 10) retry. The code that updates
x doesn’t need to know
ahead of time what conditions are interesting to its users, which
decreases coupling. The awaited condition might include inputs from
Ref-s. For example, to wait until
z is non-zero
if (x() == 0 && y() == 0 && z() == 0) retry.
This sounds like busy-waiting, so what about efficiency? It would be
very wasteful to roll back and reexecute continuously. Fortunately,
there is no point in trying again until one of the accessed
changed, and the STM knows which
Ref-s were accessed. Internally
retry is implemented using blocking constructs, so there is no
retry has a return type of
Nothing, which indicates that
it does not return normally.
retry lets you tell the STM about a dead end in the backtracking
orAtomic1 lets you give multiple search paths.
lets you chain atomic blocks that are alternative solutions to the
search. If the first alternative calls
retry then the second will be
tried, if the second calls
retry then the third will be tried, and so
on. (Alternatives are only considered after an explicit dead end using
retry, not when the transaction’s reads are inconsistent.) You can
chain alternatives directly using
orAtomic, or you can pass a
collection of atomic blocks to
The following code waits until one of
z is non-zero,
subtracts one from the first of the list that is non-zero, and records
what was done in the
msg. The second block will only be
attempted if the first block calls
retry, and the third block will
only be attempted if the second block calls
retry. If all of the
retry then the thread is blocked until one of the
is changed, and then the chain of alternatives will be retried.
Composable timeouts are an innovative feature of ScalaSTM, so we’re especially interested in your constructive criticism.
There are several reasons why you might want
retry to time out.
Perhaps error logging or handling code should be invoked; perhaps the
waiting thread should shut down if it doesn’t receive any work for a
while; or perhaps you are using the STM to implement a higher-level
interface that includes timeouts in its specification.
There are two ways to limit the amount of time that
retry will wait.
If you would like to set a policy for all calls to
retry, you can use
TxnExecutor that will cause timed-out retries to throw an
InterruptedException. If timeout is not an exceptional behavior you
can supply a timeout when waiting by using the
which falls through if the timeout has expired.
Using a custom TxnExecutor
atomic keyword defined in the
object is actually just a method that returns a
apply(block) method on the returned instance is actually
responsible for actually executing the atomic block.
withRetryTimeout method that returns a new executor that will
apply the retry timeout to all of the atomic block it executes. You can
apply the retry timeout directly when you call atomic, you can capture
and reuse the new executor with a new name, or you can use
TxnExecutor.transformDefault to change the system-wide default
executor returned by
If timeouts are part of the normal behavior, it may be convenient to
handle the timeout without an exception.
retryFor(timeout) acts like
retry if the timeout has not yet expired, otherwise it returns
immediately. Note that
retry have different return
Nothing, respectively), because
retry always triggers rollback.
pool is a transactional pool, the following code waits
up to 100 milliseconds for a pooled instance to be available, after
which the pool size is increased.
Waiting for Views
If the condition you’re waiting only involves a single
Ref you can
also block using
Ref.View.await(pred). This method blocks until the
predicate becomes true, then returns.
Ref.View.tryAwait(duration)(pred) returns true if the predicate became
true within the specified duration, otherwise it returns false.
tryAwait are part of 0.3. In version 0.2 the
await was called
retryUntil, and there was no
orAtomicis referred to as
orElsein the other STMs that support it. We changed the name to avoid confusion with