The “The Little Book of Semaphores”, introduces the “cigarette smokers problem”. The problem was originally presented by Suhas Patil in a technical MIT memo¹, as a problem that cannot be solved with semaphores. This is the original formulation: Three smokers are sitting at a table. One of them has tobacco, another has cigarette papers, and the third one has matches – each one has a different ingredient required to make and smoke a cigarette but he may not give any ingredient to another.

Ever since starting the series, I’ve been looking forward to this particular post. The Wikipedia entry describes the problem as follows: Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher.

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.

I skipped over “Chapter 2: Semaphores” because it doesn’t contain exercises. Nevertheless, looking back at it, I think it’s worth paying it a visit with Go in mind. The Little Book of Semaphores offers the following properties as a definition for a semaphore: When you create the semaphore, you can initialize its value to any integer, but after that the only operations you are allowed to perform are increment (increase by one) and decrement (decrease by one).

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?