Reusable barriers

At the end of Let’s meet, I wrote: “The channel-based solution has one advantage going for it, though: try surrounding the body of the worker in a for loop.” This is what The Little Book of Semaphores calls a “reusable barrier” in section 3.6. It’s introduced with the following puzzle:

Rewrite the barrier solution so that after all the threads have passed through, the turnstile is locked again.

In other words, rewrite the previous solution so that once all goroutines pass, the next goroutine that arrives at the barrier doesn’t pass until all the other goroutines have arrived at the barrier again.

This can be achieved almost for free with the channel-based solution:

func worker(name string, ready, wait chan Signal) {
	for {
		fmt.Printf("%s%d\n", name, 1)
		ready <- Signal{}
		<-wait
		fmt.Printf("%s%d\n", name, 2)
	}
}

func helper(N int, ready, wait chan Signal) {
	for {
		for i := N; i > 0; i-- {
			<-ready
		}
		// All the goroutines are ready, signal all the waiting
		// goroutines
		for i := N; i > 0; i-- {
			wait <- Signal{}
		}
	}
}

The only problem with this solution is that it does exactly what it’s supposed to do, and nothing more. In particular, it won’t prevent the the loop in one goroutine from getting ahead of the loop in a different goroutine. Think of it like the following, where each entry is an instruction that executes and returns at that point in time:

In essence the problem is that we are making sure that the goroutines enter a critical section together, but we are not doing the same when they leave the critical section. This issue becomes important for example if the code is part of a scatter-gather pipeline.

Even if the problem is not the same as the one described in TLBOS, the solution presented in the book applies:

func worker(name string, b1, b2 Barrier) {
	for {
		fmt.Printf("%s%d\n", name, 1)
		b1.Join()
		fmt.Printf("%s%d\n", name, 2)
		b2.Join()
	}
}

where I have introduced Barrier as a type that takes care of the synchronization operations, like this:

type Barrier struct {
	ready chan Signal
	wait  chan Signal
}

func (b Barrier) Join() {
	b.ready <- Signal{}
	<-b.wait
}

func NewBarrier(N int) Barrier {
	ready := make(chan Signal)
	wait := make(chan Signal)

	go func() {
		for {
			for i := N; i > 0; i-- {
				<-ready
			}
			for i := N; i > 0; i-- {
				wait <- Signal{}
			}
		}
	}()

	return Barrier{
		ready: ready,
		wait:  wait,
	}
}

(complete code here)

Nice and simple!