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]
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.
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.
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.
sync.Cond structure hold a structure responsible for the ticket numbers:
This is where we find the
notify variables we have seen previously. This structure also holds a linked list of the waiting goroutines, via
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.