The sushi bar problem

The next chapter in the the little Go book of semaphores series introduces the “not remotely classical problems” and the first one is called “the sushi bar problem”.

Imagine a sushi bar with 5 seats. If you arrive while there is an empty seat, you can take a seat immediately. But if you arrive when all 5 seats are full, that means that all of them are dining together, and you will have to wait for the entire party to leave before you sit down.

This is another problem about limiting the number of concurrent threads that have access to a specific resource. In this case the resource becomes unavailable when a certain number of threads are using it, and it only becomes available again when all those threads release it.

As with previous problems, in Go this can be modelled as a goroutine enforcing the constraints:

	for {
		select {
		case c := <-in:
			n++
			if n == 5 {
				in = nil
			}
			c.Sit(r)
		case <-r.out:
			n--
			if n == 0 {
				in = r.in
			}
		}
	}

The two channels in the select are created when the Restaurant is created:

type Restaurant struct {
	in  chan *Customer
	out chan *Customer
}

func NewRestaurant() *Restaurant {
	return &Restaurant{
		in:  make(chan *Customer),
		out: make(chan *Customer),
	}
}

Initially clients come in thru the in channel and this happens until the max count is reached. At that point, the variable used to reference the in channel is set to nil. The out channel is always available and it’s used by clients to tell the restaurant that they are leaving. When all have left, the in variable is set back to the incoming channel. This is enough to implement the constraints as specified.

It’s interesting to compare with the semaphore-based solution, where, in order to enforce the constraint that all the customers have to leave before others can enter, one solution is to have the departing customers to update the count of seated customers. Unlike the solution presented here, it’s necessary for customers to do some of the bookkeeping necessary to enforce constraints.

The full source (with minor modifications for presentation and filling in the details for the customers) is here.

Next week, adults provide supervision for children at the kindergarten.