tlgbos

The “Faneuil Hall” problem comes next in line in “The Little Book of Semaphores” and deals with taking the Oath of Citizenship in the city of Boston: There are three kinds of threads: immigrants, spectators, and a one judge. Immigrants must wait in line, check in, and then sit down. At some point, the judge enters the building. When the judge is in the building, no one may enter, and the immigrants may not leave.

The next problem in “The Little Book of Semaphores” is called “the senate bus problem” and reads as follows: Riders come to a bus stop and wait for a bus. When the bus arrives, all the waiting riders invoke boardBus, but anyone who arrives while the bus is boarding has to wait for the next bus. The capacity of the bus is 50 people; if there are more than 50 people waiting, some will have to wait for the next bus.

The author of “The Little Book of Semaphores” wrote this week’s problem inspired by real life events at Colby College. The problem’s statement is the following: The following synchronization constraints apply to students and the Dean of Students: Any number of students can be in a room at the same time. The Dean of Students can only enter a room if there are no students in the room (to conduct a search) or if there are more than 50 students in the room (to break up the party).

Next problem in line in the the little Go book of semaphores series is about caring for children. It comes from the book “Operating Systems and Middleware: Supporting Controlled Interaction” by Max Hailperin (problem 4.6). It reads as follows: State licensing rules require a child-care center to have no more than three infants present for each adult To put it in a different way: there’s a room where both adults and children are found.

The next chapter in the the little Go book of semaphores series introduces the “not remotely classical problems” and the first one is called “the sushi bar problem”. Imagine a sushi bar with 5 seats. If you arrive while there is an empty seat, you can take a seat immediately. But if you arrive when all 5 seats are full, that means that all of them are dining together, and you will have to wait for the entire party to leave before you sit down.

After that short intermission in reactive programming, it’s back to the little Go book of semaphores series with “the Modus Hall problem”. I didn’t understand the reference in the footnote and after some googling, it turns out that “Modus Hall” is the nickname given to a set of temporary student residence buildings at the Olin College of Engineering where the author of the problem, Nathan Karst, was a student. The problem reads as follows:

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.