Go: Monitor pattern

Vincent Blanchon
Aug 10 · 4 min read

Go implements the monitor pattern thanks to the sync package and the sync.Cond structure. The monitor pattern allows our goroutines to wait for a specific condition while entering in a sleeping mode without blocking our execution or consuming resources.

Condition variable in action

Let’s start with an example of this pattern in order to see the advantages it could bring. I will use the example provided in the presentation by Bryan Mills :

The queue is a pretty simple structure composed by an internal array of items and sync.Cond structure. Then, we do two things:

  • Ten goroutines are launched and will try to consume X items in a row. If those items are not all available at once, the goroutine will wait to be woken up
  • The main goroutine will fill the queue up with one hundred items. For each item added, it will wake up one of the goroutines that is waiting for items.

Here is the output of this program:

 4: [31 32 33 34]
8: [10 11 12 13 14 15 16 17]
5: [35 36 37 38 39]
3: [ 7 8 9]
6: [40 41 42 43 44 45]
2: [18 19]
9: [46 47 48 49 50 51 52 53 54]
10: [21 22 23 24 25 26 27 28 29 30]
1: [20]
7: [ 0 1 2 3 4 5 6]

If you run this program many times, you will get different outputs. As we can see, the value acquired by each goroutine is a continuous series since it retrieves the value by batch. This point is important in order to understand the difference of the behavior with the channels.

sync.Cond vs Channels

Solving this problem with a single channel would not be easy since it would be pulled out one by one by the consumers.

To solve this issue with the channels, Bryan Mills wrote an equivalent solution (page 65) with a composition of two channels:

The result is similar:

1: [ 0]
10: [ 1 2 3 4 5 6 7 8 9 10]
5: [11 12 13 14 15]
8: [16 17 18 19 20 21 22 23]
6: [24 25 26 27 28 29]
3: [37 38 39]
7: [30 31 32 33 34 35 36]
9: [46 47 48 49 50 51 52 53 54]
2: [44 45]
4: [40 41 42 43]

In terms of readability and semantics, condition variables have maybe a small advantage here. However, it comes with constraints.

Caution

Let’s run a benchmark with 100 items as shown in the example:

WithCond-8  15.7µs ± 2%
WithChan-8 19.4µs ± 1%

Working with condition variables is a bit faster here. Let’s try with 10k items:

WithCond-8  2.84ms ± 1%
WithChan-8 917µs ± 1%

Working with channels is now much faster. This issue has explained by Bryan Mills in the “Starvation” section (page 45):

Suppose that we have one call to GetMany(3000), and one caller executing GetMany(3) in a tight loop. The two waiters will be about equally likely to wake up, but the GetMany(3) call will be able to consume three items, whereas GetMany(3000) won’t have enough ready. The queue will remain drained and the larger call will block forever.

The presentation also highlights other possible issues we could face while working with condition variables. If the pattern looks simple at first sight, we should be careful while using it. The example seen previously did show us how it could be more efficient to work with channels and to share by communicating.

Internal workflow

The internal implementation is quite simple and based on a ticket system. Here is a simple representation of the previous example:

Each goroutine that enters waiting mode will get assigned a ticket number from a variable wait which starts from 0. This represents the waiting queue.
Then, each call to Signal() will increment another counter named notify that represents the queue of the goroutines that needs to be notified or awakened.

Our sync.Cond structure hold a structure responsible for the ticket numbers:

This is where we find the wait and notify variables we have seen previously. This structure also holds a linked list of the waiting goroutines, via head and tail, where each goroutine keeps a reference to the acquired ticket number in its internal structure.

When the signal is received, Go iterates on the linked list until the ticket number assigned to the inspected goroutine matches with the number of the notify variable, the current ticket number to be awakened. Once the goroutine has been found, its state will change from the waiting mode to runnable mode and will now be handled in the Go scheduler.

If you would like to go deeper in the Go scheduler, I strongly suggest you read this tutorial about the Go scheduler by William Kennedy.

Vincent Blanchon

Written by

Gopher — Dubai

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade