Documentation ¶
Overview ¶
Package stm provides Software Transactional Memory operations for Go. This is an alternative to the standard way of writing concurrent code (channels and mutexes). STM makes it easy to perform arbitrarily complex operations in an atomic fashion. One of its primary advantages over traditional locking is that STM transactions are composable, whereas locking functions are not -- the composition will either deadlock or release the lock between functions (making it non-atomic).
To begin, create an STM object that wraps the data you want to access concurrently.
x := stm.NewVar(3)
You can then use the Atomically method to atomically read and/or write the the data. This code atomically decrements x:
stm.Atomically(func(tx *stm.Tx) { cur := tx.Get(x).(int) tx.Set(x, cur-1) })
An important part of STM transactions is retrying. At any point during the transaction, you can call tx.Retry(), which will abort the transaction, but not cancel it entirely. The call to Atomically will block until another call to Atomically finishes, at which point the transaction will be rerun. Specifically, one of the values read by the transaction (via tx.Get) must be updated before the transaction will be rerun. As an example, this code will try to decrement x, but will block as long as x is zero:
stm.Atomically(func(tx *stm.Tx) { cur := tx.Get(x).(int) if cur == 0 { tx.Retry() } tx.Set(x, cur-1) })
Internally, tx.Retry simply calls panic(stm.Retry). Panicking with any other value will cancel the transaction; no values will be changed. However, it is the responsibility of the caller to catch such panics.
Multiple transactions can be composed using Select. If the first transaction calls Retry, the next transaction will be run, and so on. If all of the transactions call Retry, the call will block and the entire selection will be retried. For example, this code implements the "decrement-if-nonzero" transaction above, but for two values. It will first try to decrement x, then y, and block if both values are zero.
func dec(v *stm.Var) { return func(tx *stm.Tx) { cur := tx.Get(v).(int) if cur == 0 { tx.Retry() } tx.Set(v, cur-1) } } // Note that Select does not perform any work itself, but merely // returns a transaction function. stm.Atomically(stm.Select(dec(x), dec(y)))
An important caveat: transactions must be idempotent (they should have the same effect every time they are invoked). This is because a transaction may be retried several times before successfully completing, meaning its side effects may execute more than once. This will almost certainly cause incorrect behavior. One common way to get around this is to build up a list of impure operations inside the transaction, and then perform them after the transaction completes.
The stm API tries to mimic that of Haskell's Control.Concurrent.STM, but this is not entirely possible due to Go's type system; we are forced to use interface{} and type assertions. Furthermore, Haskell can enforce at compile time that STM variables are not modified outside the STM monad. This is not possible in Go, so be especially careful when using pointers in your STM code. Remember: modifying a pointer is a side effect!
Example ¶
// An implementation of the "Santa Claus problem" as defined in 'Beautiful // concurrency', found here: http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/beautiful.pdf // // The problem is given as: // // Santa repeatedly sleeps until wakened by either all of his nine reindeer, // back from their holidays, or by a group of three of his ten elves. If // awakened by the reindeer, he harnesses each of them to his sleigh, // delivers toys with them and finally unharnesses them (allowing them to // go off on holiday). If awakened by a group of elves, he shows each of the // group into his study, consults with them on toy R&D and finally shows // them each out (allowing them to go back to work). Santa should give // priority to the reindeer in the case that there is both a group of elves // and a group of reindeer waiting. // // Here we follow the solution given in the paper, described as such: // // Santa makes one "Group" for the elves and one for the reindeer. Each elf // (or reindeer) tries to join its Group. If it succeeds, it gets two // "Gates" in return. The first Gate allows Santa to control when the elf // can enter the study, and also lets Santa know when they are all inside. // Similarly, the second Gate controls the elves leaving the study. Santa, // for his part, waits for either of his two Groups to be ready, and then // uses that Group's Gates to marshal his helpers (elves or reindeer) // through their task. Thus the helpers spend their lives in an infinite // loop: try to join a group, move through the gates under Santa's control, // and then delay for a random interval before trying to join a group again. // // See the paper for more details regarding the solution's implementation. package main import ( "fmt" "math/rand" "time" "github.com/lukechampine/stm" ) type gate struct { capacity int remaining *stm.Var } func (g gate) pass() { stm.Atomically(func(tx *stm.Tx) { rem := tx.Get(g.remaining).(int) // wait until gate can hold us tx.Assert(rem > 0) tx.Set(g.remaining, rem-1) }) } func (g gate) operate() { // open gate, reseting capacity stm.AtomicSet(g.remaining, g.capacity) // wait for gate to be full stm.Atomically(func(tx *stm.Tx) { rem := tx.Get(g.remaining).(int) tx.Assert(rem == 0) }) } func newGate(capacity int) gate { return gate{ capacity: capacity, remaining: stm.NewVar(0), // gate starts out closed } } type group struct { capacity int remaining *stm.Var gate1, gate2 *stm.Var } func newGroup(capacity int) *group { return &group{ capacity: capacity, remaining: stm.NewVar(capacity), // group starts out with full capacity gate1: stm.NewVar(newGate(capacity)), gate2: stm.NewVar(newGate(capacity)), } } func (g *group) join() (g1, g2 gate) { stm.Atomically(func(tx *stm.Tx) { rem := tx.Get(g.remaining).(int) // wait until the group can hold us tx.Assert(rem > 0) tx.Set(g.remaining, rem-1) // return the group's gates g1 = tx.Get(g.gate1).(gate) g2 = tx.Get(g.gate2).(gate) }) return } func (g *group) await(tx *stm.Tx) (gate, gate) { // wait for group to be empty rem := tx.Get(g.remaining).(int) tx.Assert(rem == 0) // get the group's gates g1 := tx.Get(g.gate1).(gate) g2 := tx.Get(g.gate2).(gate) // reset group tx.Set(g.remaining, g.capacity) tx.Set(g.gate1, newGate(g.capacity)) tx.Set(g.gate2, newGate(g.capacity)) return g1, g2 } func spawnElf(g *group, id int) { for { in, out := g.join() in.pass() fmt.Printf("Elf %v meeting in the study\n", id) out.pass() // sleep for a random interval <5s time.Sleep(time.Duration(rand.Intn(5000)) * time.Millisecond) } } func spawnReindeer(g *group, id int) { for { in, out := g.join() in.pass() fmt.Printf("Reindeer %v delivering toys\n", id) out.pass() // sleep for a random interval <5s time.Sleep(time.Duration(rand.Intn(5000)) * time.Millisecond) } } type selection struct { task string gate1, gate2 gate } func chooseGroup(g *group, task string, s *selection) func(*stm.Tx) { return func(tx *stm.Tx) { s.gate1, s.gate2 = g.await(tx) s.task = task } } func spawnSanta(elves, reindeer *group) { for { fmt.Println("-------------") var s selection stm.Atomically(stm.Select( // prefer reindeer to elves chooseGroup(reindeer, "deliver toys", &s), chooseGroup(elves, "meet in my study", &s), )) fmt.Printf("Ho! Ho! Ho! Let's %s!\n", s.task) s.gate1.operate() // helpers do their work here... s.gate2.operate() } } func main() { elfGroup := newGroup(3) for i := 0; i < 10; i++ { go spawnElf(elfGroup, i) } reinGroup := newGroup(9) for i := 0; i < 9; i++ { go spawnReindeer(reinGroup, i) } // blocks forever spawnSanta(elfGroup, reinGroup) }
Output:
Index ¶
Examples ¶
Constants ¶
const Retry = "retry"
Retry is a sentinel value. When thrown via panic, it indicates that a transaction should be retried.
Variables ¶
This section is empty.
Functions ¶
func AtomicGet ¶
func AtomicGet(v *Var) interface{}
AtomicGet is a helper function that atomically reads a value.
func AtomicSet ¶
func AtomicSet(v *Var, val interface{})
AtomicSet is a helper function that atomically writes a value.
Types ¶
type Tx ¶
type Tx struct {
// contains filtered or unexported fields
}
A Tx represents an atomic transaction.
func (*Tx) Assert ¶
Assert is a helper function that retries a transaction if the condition is not satisfied.