tlgbos

In section 5.5 of “The Little Book of Semaphores” the following is called “building H₂O”: There are two kinds of threads, oxygen and hydrogen. In order to assemble these threads into water molecules, we have to create a barrier that makes each thread wait until a complete molecule is ready to proceed. As each thread passes the barrier, it should invoke bond. You must guarantee that all the threads from one molecule invoke bond before any of the threads from the next molecule do.

“The Little Book of Semaphores” presents the following as the “Santa Claus problem”, and attributes it to William Stallings: Stand Claus sleeps in his shop at the North Pole and can only be awakened by either (1) all nine reindeer being back from their vacation in the South Pacific, or (2) some of the elves having difficulty making toys; to allow Santa to get some sleep, the elves can only wake him when three of them have problems.

Last time I wrote about the “Barbershop problem” from the “The Little Book of Semaphores”. Ian Dawes pointed out that the solution I presented can be further simplified: instead of having a gorotine dedicated to arbitrating the waitroom, make the channel buffered, and use the following pattern to avoid blocking: select { case waitroom <- customer: // ... default: // ... } Ian is spot on. Like I pointed out in my reply, when I was working on the problem, I was trying to not ignore the original requirements and by focusing too much on that, I got my blinders on and missed the simpler and even easier to understand solution.

The second problem in the “Less classical problems” chapter of the “The Little Book of Semaphores” is called “the barbershop problem”. It as originally proposed by Dijkstra as “the sleeping barber” program. The book presents the problem as follows: A barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep.

In chapter 5 (“Less classical problems”), the “The Little Book of Semaphores”, starts by presenting the “dining saves problem”, introduced by Gregory Andrews in the book “Concurrent Programming: Principles and Practice.” A tribe of savages eats communal dinners from a large pot that can hold M servings of stewed missionary. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the pot is empty, the savage wakes up the cook and then waits until the cook has refilled the pot.

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.

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.