In chapter 5 (“Less classical problems”), the “The Little Book of Semaphores”, starts by presenting the “dining saves problem”, introduced by Gregory Andrews in the book “Concurrent Programming: Principles and Practice.”

A tribe of savages eats communal dinners from a large pot that can hold M servings of stewed missionary. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the pot is empty, the savage wakes up the cook and then waits until the cook has refilled the pot.

For the simple case of the cook handling out meals to the diners this is trivially solved with a channel and a goroutine:

func cook(ch chan Serving) {
	for {
		ch <- Serving{}
	}
}

There are some constraints that require a different solution:

  • The pot holds M servings
  • When the pot becomes empty, it’s the savage that wakes up the cook

This means the cook can wait for a signal and refill the pot when it arrives. For the savage to detect that the pot is empty, one could use an integer with a mutex around it. When the integer becomes zero, that savage sends the signal and waits for a “pot full” signal in return.

The cook would look something like this:

func cook(potEmpty, potFull chan struct{}) {
	for {
		<- potEmpty
		// prepare missionary
		potFull <- struct{}{}
	}
}

The savage might look like this:

func (s Savage) eat() {
	s.m.Lock()
	if *s.pot == 0 {
		s.potEmpty <- struct{}{}
		<- s.potFull
		*s.pot = M
	}
	*s.pot = *s.pot - 1
	s.m.Unlock()
	// eat
}

This falls right into “communicate by sharing memory”, because one savage is communicating to the next how many servings are left.

I look at the problem statement and I feel that it’s artificial. I’d be happier with a “Pot” actor that sends out servings upon request, and requests for more food when it runs low. Like this:

func (p Pot) serve() {
	for {
		if p.servings == 0 {
			p.potEmpty <- struct{}{}
			<- p.potFull
			p.servings += M
		}
		p.Serving <- Serving{}
		p.servings--
	}
}

with this implementation both the savage and the cook become trivial, and this can actually model a situation where there are consumers (the savages) and there’s one producer (the cook), and we would like to drive production from a third location (the pot, in this example). This removes intimate knowledge about the cook from the savages and makes the whole thing relatively simple to reason about.