Upgrade to Pro — share decks privately, control downloads, hide ads and more …

(Not Very) Practical Concurrent Design Patterns...

(Not Very) Practical Concurrent Design Patterns in Go

Moriyoshi Koizumi

November 25, 2018
Tweet

More Decks by Moriyoshi Koizumi

Other Decks in Programming

Transcript

  1. (Not Very) Practical Concurrent Design Patterns in Go Nov 25,

    2018 Moriyoshi Koizumi Open Collector, Inc.
  2. Agenda Synchronization Basics Synchronizing Access to Resources in Go Who

    am I: @moriyoshi at github.com / @moriyoshit at twitter.com. Early Go contributor. Reviewed the Japanese translation of "Concurrency in Go".
  3. Note on the term usage To generally discuss synchronization things

    at the same level of abstraction, here we use the term processes instead of goroutines. Note it does not refer to the more concrete concept like OS processes.
  4. Processes A process is a series of operations accompanied by

    zero or any number of control sequences, which may be cyclic. Op1 Op2 Op3 A process is to be started by another process (except for the very rst process).
  5. Resources Resource are what processes interact and have side e

    ects on (reading, writing etc.). A resource is usually a region of physical memory or an OS's in-kernel object exposed to the user-land as a handle (namely, a le descriptor). ` ` ` File File fd:3 fd:2 File File Memory Kernel Space
  6. Race Conditions Processes run concurrently, or maybe in parallel. What

    if more than one process operate on the same resource at the same time? Ends up leaving the resource in an inconsistent state. Time Overlap ?! A B C A B C Op. Op. Op.
  7. Locks A mechanism to keep multiple processes from operating on

    the same resource at once (once in a concurrent manner). The part of operation sequence of which a lock prevents concurrent execution is called a critical section. Critical sections racing for a resource will be serialized by applying the lock at the entry and leaving point of each critical section, thus those are mutually exclusive. Time A B C A B Op. Op. Op. C Blocked Locked Unlocked Locked Unlocked Locked Unlocked
  8. Locks (cont'd) A most primitive lock can be represented as

    an object that has a binary state, locked and unlocked, and allows only one process to get it locked, by blocking the execution of other contending processes. In Go, these properties are provided by sync.Mutex: var lock sync.Mutex // Waiter go func() { lock.Lock() fmt.Println("I waited too long!") lock.Unlock() }() // First set the lock to locked lock.Lock() // Sleep enough for the waiter to launch time.Sleep(time.Millisecond) // Signal the lock lock.Unlock() Run
  9. Counting Semaphore Is a synchronization primitive that has a counting

    variable which holds an integer value. de nes a set of operations: signal, which atomically increments the counting variable by n and awakes one of the waiters if it reaches zero. wait, which atomically decrements the counting variable by one and lets the operating process sleep until the counting variable becomes zero. A counting semaphore can be composed of two locks: A lock that ensures the atomicity of the operations. A lock that signals one of the waiters.
  10. Counting Semaphore (cont'd) package main import ( "fmt" "sync" "time"

    ) type CountingSemaphore struct { c int mu sync.Mutex s sync.Mutex } func (cs *CountingSemaphore) Signal() { cs.mu.Lock() cs.c++ if cs.c == 0 { cs.s.Unlock() } cs.mu.Unlock() } func (cs *CountingSemaphore) Wait() { cs.mu.Lock() if cs.c >= 0 { cs.c-- } c := cs.c
  11. cs.mu.Unlock() if c < 0 { cs.s.Lock() } } func

    main() { cs := CountingSemaphore{} go func() { i := 0 for { cs.Wait() fmt.Println("hey", i) i += 1 time.Sleep(time.Millisecond) } }() time.Sleep(time.Millisecond) for { cs.Signal() cs.Signal() cs.Signal() time.Sleep(time.Second) } } Run
  12. Producer-Consumer Problem Settings: There are processes of two ends of

    a communication, a producer and a consumer. The producer generates data and pass it to the consumer through a FIFO bu er. The consumer receives the generated data from the bu er. The length of the FIFO bu er is limited. Problem: How can we make producer wait for the space if the bu er is full, while making consumer wait for the availability of the data? Producer Consumer Producer Consumer (wait) (wait) FIFO is empty FIFO is full
  13. Producer-Consumer Problem (cont'd) Solution: Wikipedia: prepare two counting semaphores, one

    for signaling vacancy, having its counter initialized to the size of the bu er. one for signaling availability, having its counter initialized to zero. Go: Just use channels.
  14. Reader-Writer Problem Settings: There are many waiters that read the

    resource (readers) and a few waiters that modify it (writers). Readers don't actually need a lock to access to the resource, but need writers kept away from the resource during the read. A writer must be protected from other writes, too. Problem: If a single mutex is applied to both readers and writers for avoiding the race, it wouldn't perform well because writes tend to take longer than the read. How can we improve the performance?
  15. Reader-Writer Problem (cont'd) Solution: Wikipedia: split the lock into a

    reader lock and a writer lock for ner granularity of locks. The reader lock, accompanied by the variable that counts the readers, ensures the atomicity of the counting operation. The writer lock, used to signal the waiter. Go: Just use sync.RWMutex.
  16. Monitors and Condition Variables Monitor is a concept of synchronized

    operations against a resource, where condition variables are key synchronization constructs. Condition variables de ne a following set of operations: wait, which lets the process sleep until the condition variable is signaled. signal, which signals the condition variable to awake any single waiter. broadcast, which signals the condition variable to awake all the waiters. Proposed in a 1973 paper by Per Brinch Hansen, and formalized by Charles Antony Richard Hoare in 1974. Originally posed as an architecture for general resource management in OS.
  17. Monitors and Condition Variables (cont'd) Di erences from semaphores: signal

    operations aren't backlogged. If no waiters are present, they'll be simply ignored. No broadcast operation is de ned in semaphores. signal with the number of waiters can simulate it. Two Di erent Semantics: Mesa semantics: Adopted by Go, Java, C++, pthread ... many Hoare semantics: Only in textbooks?
  18. Monitors and Condition Variables (cont'd) In Go, wait and signal

    may be represented by a (bu ered) channel and select. c := make(chan struct{}) // -- waiter <-c // -- signaler select { case c <- struct{}{} default: }
  19. Monitors and Condition Variables (cont'd) In some cases, wait and

    broadcast may be represented by a channel and close(). c := make(chan struct{}) // -- waiter <-c // ... checking condition ... // -- signaler close(c) Note that the channel becomes unreusable after being signaled.
  20. Monitors and Condition Variables (cont'd) Use sync.Cond import "sync" mu

    := &sync.Mutex{} cond := sync.NewCond(mu) // -- waiter func() { L.Lock() defer L.Unlock() cond.Wait() // ... checking condition ... }() // -- signaler cond.Signal() cond.Broadcast()
  21. Monitors and Condition Variables (cont'd) An excerpt from src/sync/cond.go: //

    Wait atomically unlocks c.L and suspends execution // of the calling goroutine. After later resuming execution, // Wait locks c.L before returning. Unlike in other systems, // Wait cannot return unless awoken by Broadcast or Signal. // // Because c.L is not locked when Wait first resumes, the caller // typically cannot assume that the condition is true when // Wait returns. Instead, the caller should Wait in a loop: // // c.L.Lock() // for !condition() { // c.Wait() // } // ... make use of condition ... // c.L.Unlock() // func (c *Cond) Wait() { c.checker.check() t := runtime_notifyListAdd(&c.notify) c.L.Unlock() runtime_notifyListWait(&c.notify, t) c.L.Lock() }
  22. Ideas Use synchronization primitives / constructs Let goroutines restrain themselves

    from making concurrent access to the resource in automony. Use arbitrating goroutines Let goroutines delegate the operations to the arbitrator goroutine tied to the resource one-by-one. Like a client-server model in distributed computing. Arbitrator
  23. Example: access to a shared variable Using mutexes: package main

    import ( "fmt" "sync" ) type Foo struct { v1 int v2 string mu sync.Mutex } func (f *Foo) GetV1() int { f.mu.Lock() defer f.mu.Unlock() return f.v1 } func (f *Foo) SetV1(v int) { f.mu.Lock() defer f.mu.Unlock() f.v1 = v } func (f *Foo) GetV2() string { f.mu.Lock()
  24. defer f.mu.Unlock() return f.v2 } func (f *Foo) SetV2(v string)

    { f.mu.Lock() defer f.mu.Unlock() f.v2 = v } func main() { f := Foo{} f.SetV1(123) fmt.Println(f.GetV1()) f.SetV2("test") fmt.Println(f.GetV2()) } Run
  25. Example: access to a shared variable (cont'd) De ne a

    mutex in the struct that contains shared variables in question: type Foo struct { v1 int v2 string mu sync.Mutex } Surround the accessing function body with Lock() and Unlock(). func (f *Foo) GetV1() int { f.mu.Lock() defer f.mu.Unlock() return f.v1 } func (f *Foo) SetV1(v int) { f.mu.Lock() defer f.mu.Unlock() f.v1 = v }
  26. Example: access to a shared variable (cont'd) Using arbitrators: package

    main import ( "fmt" ) type Foo struct { v1 int v2 string finChan chan struct{} v1GetChan chan chan int v1SetChan chan int v2GetChan chan chan string v2SetChan chan string } func (f *Foo) GetV1() int { ch := make(chan int) f.v1GetChan <- ch return <-ch } func (f *Foo) SetV1(v int) { f.v1SetChan <- v } func (f *Foo) GetV2() string {
  27. ch := make(chan string) f.v2GetChan <- ch return <-ch }

    func (f *Foo) SetV2(v string) { f.v2SetChan <- v } func (f *Foo) Dispose() { close(f.finChan) } func NewFoo() *Foo { f := &Foo{ v1: 0, v2: "", finChan: make(chan struct{}), v1GetChan: make(chan chan int), v1SetChan: make(chan int), v2GetChan: make(chan chan string), v2SetChan: make(chan string), } go func() { outer: for { select { case <-f.finChan: break outer case c := <-f.v1GetChan: c <- f.v1 case v := <-f.v1SetChan:
  28. f.v1 = v case c := <-f.v2GetChan: c <- f.v2

    case v := <-f.v2SetChan: f.v2 = v } } }() return f } func main() { f := NewFoo() defer f.Dispose() f.SetV1(123) fmt.Println(f.GetV1()) f.SetV2("test") fmt.Println(f.GetV2()) } Run
  29. Example: access to a shared variable (cont'd) Prepare channels for

    each operation. type Foo struct { v1 int v2 string finChan chan struct{} v1GetChan chan chan int v1SetChan chan int v2GetChan chan chan string v2SetChan chan string } Launch a proxying goroutine in the factory function. func NewFoo() *Foo { f := &Foo{ v1: 0, v2: "", finChan: make(chan struct{}), v1GetChan: make(chan chan int), v1SetChan: make(chan int), v2GetChan: make(chan chan string), v2SetChan: make(chan string), } go func() { outer: for { select {
  30. case <-f.finChan: break outer case c := <-f.v1GetChan: c <-

    f.v1 case v := <-f.v1SetChan: f.v1 = v case c := <-f.v2GetChan: c <- f.v2 case v := <-f.v2SetChan: f.v2 = v } } }() return f }
  31. Example: access to a shared variable (cont'd) Wrap the send

    to each channel by accessor methods. func (f *Foo) GetV1() int { ch := make(chan int) f.v1GetChan <- ch return <-ch } func (f *Foo) SetV1(v int) { f.v1SetChan <- v } Creation of the shared data and disposal f := NewFoo() defer f.Dispose()
  32. Pros / Cons Synchronization constructs: Pros: Fast. No explicit launch

    of goroutine is needed. Clean-up is also unnecessary. Cons: Does not play well with context.Context or time.Timer. Cancellation is signaled through a channel. Technically, Go runtime is capable of polling channels and sync.Mutex's in a single select construct...
  33. Pros / Cons (cont.d) Arbitrators: Pros: Make it look more

    Go-like. Play well with other components that utilize channels to asynchronous communication. → If simply using synchronization constructs, a short-living goroutine might need to be launched at each rendevous point. Cons: Codes tend to be bloated. Explicit launch of goroutine is needed. Clean-up is necessary to avoid goroutine leaks.
  34. Conclusion Synchronization constructs are composed from more primitive constructs. Go's

    builtin inter-process communication construct is actually built from such building blocks. Higher-level constructs can emulate low-level constructs. In Go, there are a wide range of choices for synchronization. Learn the various patterns and the semantics behind them, and choose the approriate means.
  35. Thank you Nov 25, 2018 Tags: golang, sync, concurrency (#ZgotmplZ)

    Moriyoshi Koizumi Open Collector, Inc. [email protected] (mailto:[email protected]) http://www.mozo.jp/ (http://www.mozo.jp/) @moriyoshit (http://twitter.com/moriyoshit)