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. Any other combination is safe.

This is a variation on the H₂O problem from last week. Threads have to wait for other threads to arrive at the rendezvous, with the caveat that different threads are allowed pass depending on the number that have already passed.

The “problematic” situation is when the total number of hackers and serfs that have already boarded the boat is three:

  • If two hackers and one serf have boarded, only serfs can board.
  • If there are three serfs, only serfs can board.
  • If there are three hackers, only hackers can board.
  • If there is one hacker and two serfs, only hackers can board.
  • In any other case, anyone can board

With this in mind, the solution is simple: have a goroutine producing hackers and another producing serfs, with each of them sending hackers or serfs on their respective channel. With this setup, another gorutine can read from both channels using select and keep tabs on how many of each type have boarded the boat. Once the total number is three, perform the checks above and stop reading on the appropriate channel.

Like this:

	select {
	case <-hackerCh:
	case <-serfCh:

	if hackers+serfs == 3 {
		switch {
		case hackers == 2 || serfs == 3:
			hackerCh = nil
		case hackers == 3 || serfs == 2:
			serfCh = nil

Just like in H₂O, this is based on Dave Cheney’s channel axioms, specifically “a receive from a nil channel blocks forever”.

This might look like an oversimplification of the original problem, but note that the core of the original problem is letting the correct threads advance. Even if I have illustrated the solution using goroutines producing either hackers or serfs, the same solution can be extended to many goroutines corresponding to one hacker or one serf, sending on the corresponding channel and waiting for a signal that they can proceed.

The full source is here.

Next week we are going to the amusement park!