golang

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.

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.