Go: Monitor Pattern

Vincent Blanchon
Aug 10, 2019 · 4 min read
Image for post
Image for post
Illustration created for “A Journey With Go”, made from the original Go Gopher, created by Renee French.

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:

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:

Image for post
Image for post

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.

A Journey With Go

A Journey With Go Language Programming

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store