From c1d151f5c09b718b521c858c223cd4243927f0c0 Mon Sep 17 00:00:00 2001 From: EuAndreh Date: Wed, 22 Jan 2025 12:34:24 -0300 Subject: WIP: Turn cmd/santa-example into functional test --- cmd/santa-example/main.go | 174 ---------------------------------- deps.mk | 9 ++ tests/functional/santa-claus/main.go | 1 + tests/functional/santa-claus/stm.go | 175 +++++++++++++++++++++++++++++++++++ 4 files changed, 185 insertions(+), 174 deletions(-) delete mode 100644 cmd/santa-example/main.go create mode 120000 tests/functional/santa-claus/main.go create mode 100644 tests/functional/santa-claus/stm.go diff --git a/cmd/santa-example/main.go b/cmd/santa-example/main.go deleted file mode 100644 index 76c0fbc..0000000 --- a/cmd/santa-example/main.go +++ /dev/null @@ -1,174 +0,0 @@ -// 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/anacrolix/stm" -) - -type gate struct { - capacity int - remaining *stm.Var[int] -} - -func (g gate) pass() { - stm.Atomically(stm.VoidOperation(func(tx *stm.Tx) { - rem := g.remaining.Get(tx) - // wait until gate can hold us - tx.Assert(rem > 0) - g.remaining.Set(tx, rem-1) - })) -} - -func (g gate) operate() { - // open gate, reseting capacity - stm.AtomicSet(g.remaining, g.capacity) - // wait for gate to be full - stm.Atomically(stm.VoidOperation(func(tx *stm.Tx) { - rem := g.remaining.Get(tx) - 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[int] - gate1, gate2 *stm.Var[gate] -} - -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(stm.VoidOperation(func(tx *stm.Tx) { - rem := g.remaining.Get(tx) - // wait until the group can hold us - tx.Assert(rem > 0) - g.remaining.Set(tx, rem-1) - // return the group's gates - g1 = g.gate1.Get(tx) - g2 = g.gate2.Get(tx) - })) - return -} - -func (g *group) await(tx *stm.Tx) (gate, gate) { - // wait for group to be empty - rem := g.remaining.Get(tx) - tx.Assert(rem == 0) - // get the group's gates - g1 := g.gate1.Get(tx) - g2 := g.gate2.Get(tx) - // reset group - g.remaining.Set(tx, g.capacity) - g.gate1.Set(tx, newGate(g.capacity)) - g.gate2.Set(tx, 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) stm.Operation[struct{}] { - return stm.VoidOperation(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) -} diff --git a/deps.mk b/deps.mk index cdfb946..21591c7 100644 --- a/deps.mk +++ b/deps.mk @@ -1,13 +1,17 @@ libs.go = \ src/stm.go \ + tests/functional/santa-claus/stm.go \ tests/stm.go \ mains.go = \ + tests/functional/santa-claus/main.go \ tests/main.go \ functional-tests/lib.go = \ + tests/functional/santa-claus/stm.go \ functional-tests/main.go = \ + tests/functional/santa-claus/main.go \ fuzz-targets/lib.go = \ @@ -18,8 +22,13 @@ benchmarks/lib.go = \ benchmarks/main.go = \ src/stm.a: src/stm.go +tests/functional/santa-claus/main.a: tests/functional/santa-claus/main.go +tests/functional/santa-claus/stm.a: tests/functional/santa-claus/stm.go tests/main.a: tests/main.go tests/stm.a: tests/stm.go +tests/functional/santa-claus/main.bin: tests/functional/santa-claus/main.a tests/main.bin: tests/main.a +tests/functional/santa-claus/main.bin-check: tests/functional/santa-claus/main.bin tests/main.bin-check: tests/main.bin +tests/functional/santa-claus/main.a: tests/functional/santa-claus/$(NAME).a tests/main.a: tests/$(NAME).a diff --git a/tests/functional/santa-claus/main.go b/tests/functional/santa-claus/main.go new file mode 120000 index 0000000..f67563d --- /dev/null +++ b/tests/functional/santa-claus/main.go @@ -0,0 +1 @@ +../../main.go \ No newline at end of file diff --git a/tests/functional/santa-claus/stm.go b/tests/functional/santa-claus/stm.go new file mode 100644 index 0000000..babdbaa --- /dev/null +++ b/tests/functional/santa-claus/stm.go @@ -0,0 +1,175 @@ +// 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 stm + +import ( + "fmt" + "math/rand" + "time" +) + +type gate struct { + capacity int + remaining *Var[int] +} + +func (g gate) pass() { + Atomically(VoidOperation(func(tx *Tx) { + rem := g.remaining.Get(tx) + // wait until gate can hold us + tx.Assert(rem > 0) + g.remaining.Set(tx, rem-1) + })) +} + +func (g gate) operate() { + // open gate, reseting capacity + AtomicSet(g.remaining, g.capacity) + // wait for gate to be full + Atomically(VoidOperation(func(tx *Tx) { + rem := g.remaining.Get(tx) + tx.Assert(rem == 0) + })) +} + +func newGate(capacity int) gate { + return gate{ + capacity: capacity, + remaining: NewVar(0), // gate starts out closed + } +} + +type group struct { + capacity int + remaining *Var[int] + gate1, gate2 *Var[gate] +} + +func newGroup(capacity int) *group { + return &group{ + capacity: capacity, + remaining: NewVar(capacity), // group starts out with full capacity + gate1: NewVar(newGate(capacity)), + gate2: NewVar(newGate(capacity)), + } +} + +func (g *group) join() (g1, g2 gate) { + Atomically(VoidOperation(func(tx *Tx) { + rem := g.remaining.Get(tx) + // wait until the group can hold us + tx.Assert(rem > 0) + g.remaining.Set(tx, rem-1) + // return the group's gates + g1 = g.gate1.Get(tx) + g2 = g.gate2.Get(tx) + })) + return +} + +func (g *group) await(tx *Tx) (gate, gate) { + // wait for group to be empty + rem := g.remaining.Get(tx) + tx.Assert(rem == 0) + // get the group's gates + g1 := g.gate1.Get(tx) + g2 := g.gate2.Get(tx) + // reset group + g.remaining.Set(tx, g.capacity) + g.gate1.Set(tx, newGate(g.capacity)) + g.gate2.Set(tx, 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) Operation[struct{}] { + return VoidOperation(func(tx *Tx) { + s.gate1, s.gate2 = g.await(tx) + s.task = task + }) +} + +func spawnSanta(elves, reindeer *group) { + for { + fmt.Println("-------------") + var s selection + Atomically(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 MainTest() { + return + 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) +} -- cgit v1.2.3