I’m making a pause in the “semaphores” series to visit a problem from exercism.io, namely react in Go. As the description says, the idea is to implement a basic reactive system in Go. Wikipedia defines “reactive programming” as “a programming paradigm oriented around data flows and the propagation of change. This means that it should be possible to express static or dynamic data flows with ease in the programming languages used, and that the underlying execution model will automatically propagate changes through the data flow.

The next problem in the “The Little Book of Semaphores” is called the “unisex bathroom problem”, by Allen Downey himself. The problem statement reads as follows: A friend of the author took a job at Xerox. She was working in a cubicle in the basement of a concrete monolith, and the nearest women’s bathroom was two floors up. She proposed to the Uberboss that they convert the men’s bathroom on her floor to a unisex bathroom, sort of like on Ally McBeal.

I pushed back the publication of this entry because I wasn’t so happy with the implementation I had. It’s a new chapter in the “The Little Book of Semaphores”: not so-classical problems. The first problem there is called “search-insert-delete” and it deals with linked lists. Three kinds of threads share access to a singly-linked list: searchers, inserters and deleters. Searchers merely examine the list; hence they can execute concurrently with each other.

Section 5.7 of “The Little Book of Semaphores” presents the last of the “less classical” synchronization problems. It’s another problem presented in “Concurrent Programming”, called “the roller coaster problem” and attributed to J.S. Herman. It reads as follows: Suppose there are n passenger threads and a car thread. The passengers repeatedly wait to take rides in the car, which can hold C passengers, where C < n. The car can go around the tracks only when it is full.

In section 5.6 of “The Little Book of Semaphores”, Allen Downey says this problem might have originally come from Anthony Joseph at U.C. Berkeley: Somewhere near Redmond, Washington there is a rowboat that is used by both Linux hackers and Microsoft employees (serfs) to cross a river. The ferry can hold exactly four people; it won’t leave the shore with more or fewer. To guarantee the safety of the passengers, it is not permissible to put one hacker in the boat with three serfs, or to put one serf with three hackers.

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.