Threading in programming has a long history. A number of patterns have evolved over time, to help programmers share and control resources between threads. The Go Programming language implements a number of the classical patterns, Mutexes, Semaphores, and Condition Variables, as well as the well known Channels
This article will focus on one of the first pattern to arise, Semaphores.
As with most things in computer science semaphores are based on ideas that existed (and continue to exist) in other systems. Semaphores are a means of communicating over long distances. They’re flags that, when held in a certain way, convey information, letters, words, to people who can read them from far away.
Rail networks had cause to use this system. There was a need to quickly convey information between distant points. A section of rail that was required to be shared by trains running in both directions needed a way to tell trains when the section was being used and that they had to wait for their turn. A semaphore was then placed at each end of the critical section, with operators able to signal to the other end that a train was going to enter the critical section.
The rail network’s semaphore implementation is what we would call a binary semaphore, or a mutual exclusion lock. The semaphores have two states, locked or unlocked. An issue exists though, two trains could arrive at either end of the critical section simultaneously take possession of the semaphore lock for their respective end, then discover that the other end is already locked, more on this later.
Computer science adopted this pattern of using semaphores to ensure that multiple processes could share a restricted resource/piece of critical code. In 1965 Dijkstra’s paper (English translation) was published, although his team had been using the concept from 1962 or 1963.
The implementation of locking a resource in computers needs to get around the issue raised earlier, two or more processes trying to take possession of the lock at the same time. The software implementation utilises what is known as a busy, or spin lock, that is, the code will try to acquire possession of the lock, and if it fails it will loop and try again.
This is very inefficient as the process is using CPU for no reason other than the fact that it cannot get access to a resource that it wants. There is a hardware implementation, which is favoured, but is still a busy lock, and that is for the CPU to define a Test and Set Lock (TSL) extension/instruction that is atomic as far as the software is concerned.
In practice the TSL is still a spinlock, but operating at the hardware level ensures it uses fewer cycles to determine if it is able to obtain the lock. See AMD’s Architecture Programmer’s Manual Vol. 3 page 11 for an example.
There is another problem, though. When a process does not have possession of a lock, it cannot continue computation, so it will go to sleep. The sleeping process is usually then awoken when the lock is available, most implementations achieve this by sending the process a signal.
The solution of sending signals to the sleeping process has a race condition embedded in it, a process may ask if it can take possession of a lock, and be told no. At that instant the OS scheduler takes over, before the process can go to sleep, and reactivates a process that currently owns the lock.
The active process sees that the inactive process wants the lock, and sends a wake-up signal. When the scheduler reactivates the first process that was asking for the lock, that process is not yet asleep, it has only just asked if it can take possession of the lock, it receives the wake-up signal. But the process ignores the wake up signal as it is currently awake.
The process then sees that it cannot acquire the lock (from its query before the scheduler swapped processes), and goes to sleep. The process then sleeps forever, as other processes will see that it has already been signalled to wake-up and will not signal it again when they (re)acquire the lock.
This is known as the Producer-Consumer problem (or bounded buffers problem).
The solution to this problem was to store a net count of the sleep/wake-up signals sent to a process, thus letting it know if it should be awake or asleep when it is next scheduled. This is how semaphores were originally implemented, integers whose value went up when a wake-up signal was received, and went down when a sleep signal was received.
And this brings us to semaphores in Go. A semaphore in Go is a FIFO queue, where a process/thread/goroutine asks the semaphore for n tokens, tokens that will be used to gain access to the critical region or resource.
When a process’s token reaches the front of the queue, it can use the code/resource, returning the token when it exists. A Java semaphore behaves in a very similar manner, with one important exception. Java semaphores allow barging, that is, Java allows processes to jump ahead in the queue.
Reading all of this, you might be forgiven for thinking that there might be another way to implement the semaphore pattern in Go, using the channel structure. Bryan C. Mills, in his Gophercon 2018 talk: Rethinking Classical Concurrency Patterns agrees with you.
At the point in the video that’s been linked to Bryan talks about using channels as mutexes and single value semaphores. Channels are, after all, synchronised queues, so placing goroutines, or tokens that are owned by that goroutine, in a channel, allow the channel to be used as FIFO semaphores.
As Bryan says communicating the metadata is a legitimate use of channels, and (IMO) it’s easier to reason about than a semaphore.
Thus, when to use the semaphore pattern is, when you want to queue up processes that want access to a given resource that only one should be using at a given point in time. How you do that is best done (in Go at least) with channels. Have your process place tokens in the channel, requesting access, when that token reaches the front of the queue, give the channel ownership of the resource, to do with it as it wishes. When the process finishes, a new token is drawn from the channel.