Checkpoint synchronization: Difference between revisions
→{{header|Go}}: add simpler solutions
(Added Kotlin) |
(→{{header|Go}}: add simpler solutions) |
||
Line 671:
=={{header|Go}}==
'''Solution 1, WaitGroup'''
The type sync.WaitGroup in the standard library implements a sort of checkpoint synchronization. It allows one goroutine to wait for a number of other goroutines to indicate something, such as completing some work.
This first solution is a simple interpretation of the task, starting a goroutine (worker) for each part, letting the workers run concurrently, and waiting for them to all indicate completion. This is efficient and idiomatic in Go.
<lang go>package main
import (
"log"
"math/rand"
"sync"
"time"
)
func worker(part string) {
log.Println(part, "worker begins part")
time.Sleep(time.Duration(rand.Int63n(1e6)))
log.Println(part, "worker completes part")
wg.Done()
}
var (
partList = []string{"A", "B", "C", "D"}
nAssemblies = 3
wg sync.WaitGroup
)
func main() {
rand.Seed(time.Now().UnixNano())
for c := 1; c <= nAssemblies; c++ {
log.Println("begin assembly cycle", c)
wg.Add(len(partList))
for _, part := range partList {
go worker(part)
}
wg.Wait()
log.Println("assemble. cycle", c, "complete")
}
}</lang>
{{out}}
Sample run, with race detector option to show no race conditions detected.
<pre>
$ go run -race r1.go
2018/06/04 15:44:11 begin assembly cycle 1
2018/06/04 15:44:11 A worker begins part
2018/06/04 15:44:11 B worker begins part
2018/06/04 15:44:11 B worker completes part
2018/06/04 15:44:11 D worker begins part
2018/06/04 15:44:11 A worker completes part
2018/06/04 15:44:11 C worker begins part
2018/06/04 15:44:11 D worker completes part
2018/06/04 15:44:11 C worker completes part
2018/06/04 15:44:11 assemble. cycle 1 complete
2018/06/04 15:44:11 begin assembly cycle 2
2018/06/04 15:44:11 A worker begins part
2018/06/04 15:44:11 B worker begins part
2018/06/04 15:44:11 A worker completes part
2018/06/04 15:44:11 C worker begins part
2018/06/04 15:44:11 D worker begins part
2018/06/04 15:44:11 C worker completes part
2018/06/04 15:44:11 B worker completes part
2018/06/04 15:44:11 D worker completes part
2018/06/04 15:44:11 assemble. cycle 2 complete
2018/06/04 15:44:11 begin assembly cycle 3
2018/06/04 15:44:11 A worker begins part
2018/06/04 15:44:11 B worker begins part
2018/06/04 15:44:11 A worker completes part
2018/06/04 15:44:11 C worker begins part
2018/06/04 15:44:11 D worker begins part
2018/06/04 15:44:11 B worker completes part
2018/06/04 15:44:11 C worker completes part
2018/06/04 15:44:11 D worker completes part
2018/06/04 15:44:11 assemble. cycle 3 complete
$
</pre>
'''Solution 2, channels'''
Channels also synchronize, and in addition can send data. The solution shown here is very similar to the WaitGroup solution above but sends data on a channel to simulate a completed part. The channel operations provide synchronization and a WaitGroup is not needed.
<lang go>package main
import (
"log"
"math/rand"
"strings"
"time"
)
func worker(part string, completed chan string) {
log.Println(part, "worker begins part")
time.Sleep(time.Duration(rand.Int63n(1e6)))
p := strings.ToLower(part)
log.Println(part, "worker completed", p)
completed <- p
}
var (
partList = []string{"A", "B", "C", "D"}
nAssemblies = 3
)
func main() {
rand.Seed(time.Now().UnixNano())
completed := make([]chan string, len(partList))
for i := range completed {
completed[i] = make(chan string)
}
for c := 1; c <= nAssemblies; c++ {
log.Println("begin assembly cycle", c)
for i, part := range partList {
go worker(part, completed[i])
}
a := ""
for _, c := range completed {
a += <-c
}
log.Println(a, "assembled. cycle", c, "complete")
}
}</lang>
{{out}}
<pre>
$ go run -race r2.go
2018/06/04 15:56:33 begin assembly cycle 1
2018/06/04 15:56:33 A worker begins part
2018/06/04 15:56:33 B worker begins part
2018/06/04 15:56:33 A worker completed a
2018/06/04 15:56:33 D worker begins part
2018/06/04 15:56:33 C worker begins part
2018/06/04 15:56:33 B worker completed b
2018/06/04 15:56:33 C worker completed c
2018/06/04 15:56:33 D worker completed d
2018/06/04 15:56:33 abcd assembled. cycle 1 complete
2018/06/04 15:56:33 begin assembly cycle 2
2018/06/04 15:56:33 A worker begins part
2018/06/04 15:56:33 B worker begins part
2018/06/04 15:56:33 C worker begins part
2018/06/04 15:56:33 D worker begins part
2018/06/04 15:56:33 A worker completed a
2018/06/04 15:56:33 B worker completed b
2018/06/04 15:56:33 D worker completed d
2018/06/04 15:56:33 C worker completed c
2018/06/04 15:56:33 abcd assembled. cycle 2 complete
2018/06/04 15:56:33 begin assembly cycle 3
2018/06/04 15:56:33 A worker begins part
2018/06/04 15:56:33 B worker begins part
2018/06/04 15:56:33 C worker begins part
2018/06/04 15:56:33 D worker begins part
2018/06/04 15:56:33 B worker completed b
2018/06/04 15:56:33 A worker completed a
2018/06/04 15:56:33 D worker completed d
2018/06/04 15:56:33 C worker completed c
2018/06/04 15:56:33 abcd assembled. cycle 3 complete
$
</pre>
'''Solution 3, two-phase barrier'''
For those that might object to the way the two solutions above start new goroutines in each cycle, here is a technique sometimes called a two-phase barrier, where goroutines loop until being shutdown. In each loop there are two phases, one of making the part, and one of waiting for the completed parts to be assembled. This more literally satisfies the task but in fact is not idiomatic Go. Goroutines are cheap to start up and shut down in Go and the extra complexity of this two-phase barrier technique is
not justified.
<lang go>package main
import (
"log"
"math/rand"
"strings"
"sync"
"time"
)
func worker(part string, completed chan string) {
log.Println(part, "worker running")
for {
select {
case <-start:
log.Println(part, "worker begins part")
time.Sleep(time.Duration(rand.Int63n(1e6)))
p := strings.ToLower(part)
log.Println(part, "worker completed", p)
completed <- p
<-reset
wg.Done()
case <-done:
log.Println(part, "worker stopped")
wg.Done()
return
}
}
}
var (
partList = []string{"A", "B", "C", "D"}
nAssemblies = 3
start = make(chan int)
done = make(chan int)
reset chan int
wg sync.WaitGroup
)
func main() {
rand.Seed(time.Now().UnixNano())
completed := make([]chan string, len(partList))
for i, part := range partList {
completed[i] = make(chan string)
go worker(part, completed[i])
}
for c := 1; c <= nAssemblies; c++ {
log.Println("begin assembly cycle", c)
reset = make(chan int)
close(start)
a := ""
for _, c := range completed {
a += <-c
}
log.Println(a, "assembled. cycle", c, "complete")
wg.Add(len(partList))
start = make(chan int)
close(reset)
wg.Wait()
}
wg.Add(len(partList))
close(done)
wg.Wait()
}</lang>
{{out}}
<pre>
$ go run -race r3.go
2018/06/04 16:11:54 A worker running
2018/06/04 16:11:54 B worker running
2018/06/04 16:11:54 C worker running
2018/06/04 16:11:54 begin assembly cycle 1
2018/06/04 16:11:54 A worker begins part
2018/06/04 16:11:54 D worker running
2018/06/04 16:11:54 C worker begins part
2018/06/04 16:11:54 B worker begins part
2018/06/04 16:11:54 D worker begins part
2018/06/04 16:11:54 A worker completed a
2018/06/04 16:11:54 C worker completed c
2018/06/04 16:11:54 D worker completed d
2018/06/04 16:11:54 B worker completed b
2018/06/04 16:11:54 abcd assembled. cycle 1 complete
2018/06/04 16:11:54 begin assembly cycle 2
2018/06/04 16:11:54 C worker begins part
2018/06/04 16:11:54 D worker begins part
2018/06/04 16:11:54 B worker begins part
2018/06/04 16:11:54 A worker begins part
2018/06/04 16:11:54 D worker completed d
2018/06/04 16:11:54 A worker completed a
2018/06/04 16:11:54 B worker completed b
2018/06/04 16:11:54 C worker completed c
2018/06/04 16:11:54 abcd assembled. cycle 2 complete
2018/06/04 16:11:54 begin assembly cycle 3
2018/06/04 16:11:54 A worker begins part
2018/06/04 16:11:54 D worker begins part
2018/06/04 16:11:54 C worker begins part
2018/06/04 16:11:54 B worker begins part
2018/06/04 16:11:54 D worker completed d
2018/06/04 16:11:54 A worker completed a
2018/06/04 16:11:54 B worker completed b
2018/06/04 16:11:54 C worker completed c
2018/06/04 16:11:54 abcd assembled. cycle 3 complete
2018/06/04 16:11:54 D worker stopped
2018/06/04 16:11:54 B worker stopped
2018/06/04 16:11:54 C worker stopped
2018/06/04 16:11:54 A worker stopped
</pre>
'''Solution 4, workers joining and leaving'''
This solution shows workers joining and leaving, although it is a rather different interpretation of the task.
<lang go>package main
| |||