Synchronization queues in Golang

how to use channels to write idiomatic code in Go

Michał Łowicki
Mar 12, 2018 · 6 min read

Problem

Let’s suppose we’re running an IT company employing programmers and testers. To give people a chance to get to know each other and relax a bit we’ve bought a ping-pong table and established following rules:

  • exactly two people can play at the same time,
  • next pair can start their game only when previous one finished so it’s not allowed to switch one player,
  • testers can only work with programmers and vice versa (never two testers or two programmers together). If programmer or tester wants play then needs to wait for tester or programmer respectively to establish a valid pair.

We’ll mimic testing, coding and playing ping-pong by time.sleep:

Such program emits stream of messages like this:

But to play ping-pong in accordance with the rules our stream of messages can consists only of such 4-lines long sequences (in any order and repeated arbitrary number of times):

So first either tester or programmer approaches the table. Afterwards partner joins (programmer or tester accordingly). While leaving the game they can do it in any order. This is why we’ve 4 valid sequences.

Below are two solutions. 1st one is based on mutexes and 2nd one uses separate worker which coordinates the whole process making sure everything happens according to the policy.

Solution #1

Both solutions are using data structure which queues programmers and testers before approaching the table. When there is at least one valid pair available (Dev + QA) then one pair is allowed to play ping-pong.

Package queue is defined as follows:

Queue has mutex which serves two purposes:

  • synchronizes access to shared counters (numT and numP)
  • acts as a token held by playing employees which blocks others from joing the table

Programmers and testers are waiting for ping-pong parter using unbuffered channels:

or

Reading from one of these channels will block goroutine if there is no opponent available.

Let’s analyze StartT which is executed by testers:

If numP is greater than 0 (there is at least one programmer waiting for the game) then number of waiting programmers is decreased by one and one of waiting programmer will be allowed to join the table (q.queueP <- 1). What is interesting here is during this path mutex won’t be released so it’ll serve as a token giving exclusive access to ping-pong table.

If there is no waiting programmers then numT (number of waiting testers) is increased and goroutine blocks on <-q.queueT.

StartP is basically the same but executed by programmers.

During the play, mutex will be locked so it needs to be released by either programmer or tester. To release mutex only when both parties finished the game a barrier doneP is used:

If programmer is still playing and tester finished then tester will block on <-q.doneP. As soon as programmer reaches q.doneP <- 1 then barrier will open and mutex will be released to allow these employees to go back to work.

If tester is still playing then programmer will block on q.doneP <- 1. When tester is done then it reads from barrier <-q.doneP which will unblock programmer and mutex will be released to free the table.

What is interesting here is that mutex is always released by tester even when either tester or programmer might locked it. It’s also part of reason why this solution might not be so obvious at first glance…

Solution #2

We’ve a central coordinator running inside separate goroutine which orchestrate the whole process. Scheduler gets information about new employee who wants to relax or if someone is done with ping-pong via msg channel. While receiving any message state of the scheduler is updated:

  • number of waiting Devs or QAs is increased
  • information about playing employees is updated

After receiving any of defined messages, scheduler will check if it’s allowed to start a game by another pair:

if q.waitP > 0 && q.waitT > 0 && !q.playP && !q.playT {

If so the state is updated accordingly and one tester and one programmer are unblocked.

Instead of using mutexes (as in solution#1) to manage access to shared data, we’ve now a separate goroutine which talks with outside world over the channel. This gives us more idiomatic Go program.

Don’t communicate by sharing memory, share memory by communicating.

Resources


If you’ve found alternative solution you would like to share then please comment beneath.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

golangspec

A series dedicated to deeply understand Go’s specification…

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

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