Building H₂O

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 Go solution (at least my Go solution) to this problem is trivial: have goroutines produce oxygen and goroutines produce hydrogen. The trick here is that the goroutine assembling the molecules has to read from any of the goroutines producing the atoms. The program has to stop reading from the goroutine that has provided all the atoms it has to provide for a single molecule until one is assembled. In other words, if an oxygen atom shows up, don’t read any more oxygen atoms until you have the hydrogen atoms.

There are two ways of soving this problem: stop reading in the assembly goroutine or stop producing in the atom-creating goroutines.

The first approach is simple:

	select {
	case <-och:
		// Got an O, don't need more
		o++
		och = nil
	case <-hch:
		// Got an H
		if h++; h == 2 {
			// have enough H
			hch = nil
		}
	}

and then the rest of the logic goes something like:

	if o == 1 && h == 2 {
		// build molecule
		// ...

		// reset channels
		och = b.och
		hch = b.hch
	}

This is again based on Dave Cheney’s Channel Axioms, specifically “a receive from a nil channel blocks forever”.

With this approach there’s one producer of oxygen, that looks like this:

	for {
		ch <- Oxygen{}
	}

and one producer of hydrogen, that looks exactly the same:

	for {
		ch <- Hydrogen{}
	}

The other approach is to block on the producer side.

The simplest way of doing this, is to produce the necessary atom and block while reading from a channel. This channel might have been provided initially to both the producers and the consumer. The consumer could send the correct number of signals (3 in this example) to unblock the producers. This looks messy to me.

Another approach is for the producer to send a channel and block reading from that channel. The consumer will simply close the channel it got from the producer when it has received all the atoms it needs. This uses another of the axioms: “a receive from a closed channel returns the zero value immediately”.

The consumer side looks something like this:

	select {
	case o = <-och:
	case h1 = <-h1ch:
	case h2 = <-h2ch:
	}

It simply receives the channels and stores them, and later, when it has all the atoms:

	close(o)
	close(h1)
	close(h2)

by closing the three channels it unblocks all the producers, which look like this:

	tmp := make(chan struct{})
	ch <- tmp
	<-tmp

Note how the consumer is reading hydrogen from two different channels. This is because in this pattern I’d rather the producer to not know how many atoms are needed, so it’s going to block after producing just one. This could be solved by receiving on the hydrogen channel, and immediately closing the received channel to unblock the producer and wait for another one. If you are really going with that, I think you are better off with the first pattern. This one is better when there’s less symmetry (for example, if there were three kinds of producers).

One nice property of the general approach, specially compared to the typical one based on semaphores, is that the producers do not know that the others exist. Their function is limited to producing the atoms they need to produce and nothing else. It also does not have that really odd asymmetry in the usual semaphore-based solution, where a mutex is acquired by one kind of producer and released by a different kind.

The full source is here.

Next week: crossing a river, hopefully not the Styx!