golang

After a weeks-long hiatus around the end of last year, I’m back to the regular once-a-week schedule. The next stop in the “classical problems” chapter of “The Little Book of Semaphores” is called the “readers-writers” problem. The book describes it thusly: “any situation where a data structure, database, or file system is read and modified by concurrent threads. While the data structure is being written or modified it is often necessary to bar other threads from reading, in order to prevent a reader from interrupting a modification in progress and reading inconsistent or invalid data.

This is the first entry in the “Classical synchronization problems” chapter of “The Little Book of Semaphores”, the “producer-consumer problem”. The text describes the problem as a common pattern where some threads are producers and some threads are consumers. It imposes the follow two constraints on the system: While an item is being added to or removed from the buffer, the buffer is in an inconsistent state. Therefore, threads must have exclusive access to the buffer.

For $WORK reasons, I want an up-to-date Go cross compiler for OpenEmbedded. Taking a look at existing efforts I ended up forking dodgerblue’s repository in order to fix a couple of issues, most notably, the fact that in order to bootstrap 1.5, the recipe goes behind bitbake’s back and downloads 1.4 source. I was working with Fido’s core-image-minimal just to make sure that everything compiled ok in a cross-build environment (more on that later).

The first time I used Go to solve the particular puzzle I’d like to discuss in this post, I though I was doing something wrong because the solution is so concise. Secton 3.7 of the Little Book of Semaphores presents the following puzzle: Imagine that goroutines represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting.

At the end of Let’s meet, I wrote: “The channel-based solution has one advantage going for it, though: try surrounding the body of the worker in a for loop.” This is what The Little Book of Semaphores calls a “reusable barrier” in section 3.6. It’s introduced with the following puzzle: Rewrite the barrier solution so that after all the threads have passed through, the turnstile is locked again. In other words, rewrite the previous solution so that once all goroutines pass, the next goroutine that arrives at the barrier doesn’t pass until all the other goroutines have arrived at the barrier again.

Chapter 3 of The Little Book of Semaphores proposes the following puzzle: Generalize the signal pattern so that it works both ways. Thread A has to wait for Thread B and vice versa. If Thread A runs two statements a1 and a2, and Thread B runs two statements b1 and b2, the requirement is for a1 to execute before b2 and for b1 to execute before a2. In other words, the threads are to meet before executing their respective second statement.

In the introduction to The Little Book of Semaphores (TLBOS), the author presents the following puzzle (rephrased a little): Imagine that Alice and her friend Bob live in different cities, and one day, around dinner time, Alice starts to wonder who ate lunch first that day, she or Bob. Assuming that Bob is willing to follow simple instructions, is there any way Alice can guarantee that tomorrow she will eat lunch before Bob?

The Little Book of Semaphores, by professor Allen Downey, is a textbook that introduces the principles of synchronization for concurrent programming. It’s available under the GNU Free Documentation License. The book uses Python to illustrate the concepts, but I think Go is a much better fit for that purpose. Semaphores are rarely seen in Go as such. The sync package provides synchronization primitives, for example, mutual exclusion locks and condition variables, but notably it doesn’t provide a semaphore.