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. Spectators may leave. Once all immigrants check in, the judge can confirm the naturalization. After the confirmation, the immigrants pick up their certificates of U.S. Citizenship. The judge leaves at some point after the confirmation. Spectators may now enter as before. After immigrants get their certificates, they may leave.

The immigrants waiting in line are easy to represent using one goroutine per immigrant and a single channel for all of them to enter the court. The same goes for the spectators. The judge is represented using a goroutine and a channel dedicated to letting him enter. Since it’s necessary to control when the different actors leave, and more specifically, since it’s necessary to control when they are allowed to leave, there’s a channel dedicated to each kind of actor leaving as well. This cannot be done with a single “in” channel and a single “out” channel because of the restrictions of the problem:

  • Immigrants can enter as long as the judge is not in the court
  • Immigrants cannot leave until the judge has left
  • Spectators can enter as log as the judge is not in the court
  • Spectators can leave at any time
  • The judge can enter at any time
  • The judge can leave at any time

Let’s say there’s a single “in” channel. That’s enough to support immigrant and spectators entering the court as long as the judge is not in the building. That same channel can be used to allow the judge to enter. The problem is now identifying who entered (an immigrant, a spectator or the judge). That could be done with type asserts:

	switch p := <-courtEntrance; p.(type) {
	case Immigrant:
		// ...
	case Spectator:
		// ...
	case Judge:
		// ...
	}

This allows for “shutting the doors” when the judge comes in:

	case Judge:
		courtEntrance = nil
		// ...

Exiting on the other hand is a bit more complicated because there’s a difference between immigrants and spectators. This means that if conceptually there’s a single exit, in practice there are at least two. And since it’s necessary to differentiate the judge from the immigrants, it probably makes sense to have three exits:

	select {
	case <-immigrantOut:
		// ...
	case <-judgeOut:
		// ...
	case <-spectatorOut:
		// ...
	}

To satisfy the “check in” step, it’s possible to introduce another channel just for that, immigrants send a message and once the message comes through, they can await for confirmation. Meanwhile the judge waits for a message stating that all the immigrants have checked in, and once that is received, he can proceed with the confirmation. After they get the confirmation, they proceed to wait for their certificate and then leave.

I’m not 100% satisfied with this code just yet. For example, examine what happens if there’s a loop producing judges instead of just shutting down when the last immigrant exits. But in order to show the basic idea of how to solve the problem, I think this gets close enough.

Initially I had implemented the confirmation step as a broadcast operation: have a channel that all the immigrants wait on and close it when the judge confirms the immigrants. This has the advantage that it’s independent of the number of immigrants and maps well to the described situation: all the immigrants are standing in front of the judge, the judge confirms all of them at once and they proceed to pick up their certificate. Closing a channel does exactly that: it unblocks everyone at once. The problem with that solution is precisely setting things up for the next round of immigrants. In principle in can be done from the same loop that the court is running: once the court gets a signal from the judge that the confirmation happened (it can be a select on the confirmation channel), simply make a new channel. This is safe because there will be no new immigrants just yet. The problem is what if there’s an immigrants In principle in can be done from the same loop that the court is running: once the court gets a signal from the judge that the confirmation happened (it can be a select on the confirmation channel), simply make a new channel. The problem is what happens if an immigrants arrives late at the operation reading from the channel: if the channel is not made anew, it’s still ok, because it would try to read from a closed channel and return immediately. But changing the channel without knowing for sure that all immigrants are already blocking on that receive operation doesn’t work.

The general approach to the solution shoudl be familiar to readers of this blog series. The full source is here.

The next problem in the series is another dinner invitation, but no philosophers this time.