The barbershop problem

The second problem in the “Less classical problems” chapter of the “The Little Book of Semaphores” is called “the barbershop problem”. It as originally proposed by Dijkstra as “the sleeping barber” program. The book presents the problem as follows:

A barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.

At first reading, this sounds like a job for a buffered channel, because it would be able to hold waiting n customers until the barber services them. That approach doesn’t work because when the n+1 customer shows up before the barber was put the first one on the chair, sending on that channel will block, instead of just fail, meaning it’s not possible to implement the “leaves the shop” behavior.

A better approach is to implement a Barbershop that provides a channel where clients can request service. If the client can be serviced, it’s put on the waitlist. Meanwhile the barber is either waiting for the next customer or cutting the hair of the current one. A possible implementation looks like this:

type Barbershop struct {
	WaitRoomSize int
	WaitingCh    chan bool
	BarbershopCh chan Customer
}

The BarbershopCh is where customers enter the barbershop and the WaitingCh is where customers are told if they on the wait list or not. The Barbershop runs the following loop:

for {
	c := <-b.BarbershopCh:
	switch {
	case len(barberCh) == b.WaitRoomSize:
		// tell the customer that we are full
		b.WaitingCh <- false

	default:
		// add customer to wait list
		barberCh <- c
		log.Printf("Customer %s waiting", c.Name)
		// tell the customer that they are waiting
		b.WaitingCh <- true
	}
}

There’s an “internal” channel between the wait room and the barber (barberCh). This channel is buffered with the capacity set to the wait room size. When a new customer arrives at the barbershop, the code receives it, checks if there channel is not full yet, and if that’s the case adds the new customer to that channel, which will wake up the barber goroutine in case it’s sleeping.

Again, notice that the channel where customers arrive (the “door” to the barbershop) is not buffered. Every customer arriving at the barbershop gets to talk to a “host”, which then tells them whether or not there’s room in the wait room.

The barber is this loop:

for {
	c := <-barberCh
	// cut hair here
	c.Done()
}

and the customers are conceptually this loop:

for {
	barbershop.BarbershopCh <- c
	<-barbershop.WaitingCh
}

This approach might seem is a bit artificial, because there’s a loop producing customers. It’s not that far fetched, though, as it could correspond to a webserver taking requests and dispatching it to some worker goroutine, until a limit is hit and instead of servicing the request it replies with 503 (“service unavailable”), which is asking the client to retry in the future.

An alternative view is that there’s some kind of rate limiting (think logging service), where multiple goroutines are sending requests and it’s ok if some of those requests are not serviced. Since there’s a single goroutine B reading BarbershopCh, only one of the sending goroutines C can proceed to the point where it’s waiting for the reply from B. So the fact that here I’ve shown a loop fabricating clients does not mean that this solution only works with such a setup.

I find this solution compares much favorably with the “standard” one based around mutexes and semaphores. I think it’s conceptually simpler to reason about, even if the two solutions are similar in spirit.

The full source, with minor modifications for presentation purposes, is here.

Next week: a variation of this same problem, Hilzer’s barbershop.