Hilzer's barbershop

Last time I wrote about the “Barbershop problem” from the “The Little Book of Semaphores”. Ian Dawes pointed out that the solution I presented can be further simplified: instead of having a gorotine dedicated to arbitrating the waitroom, make the channel buffered, and use the following pattern to avoid blocking:

	select {
	case waitroom <- customer:
		// ...
	default:
		// ...
	}

Ian is spot on. Like I pointed out in my reply, when I was working on the problem, I was trying to not ignore the original requirements and by focusing too much on that, I got my blinders on and missed the simpler and even easier to understand solution. Thanks again!

Hilzer’s variation is the following:

Our barbershop has three chairs, three barbers, and a waiting area that can accommodate four customers on a sofa and that has standing room for additional customers. Fire codes limit the total number of customers in the shop to 20.

A customer will not enter the shop if it is filled to capacity with other customers. Once inside, the customer takes a seat on the sofa or stands if the sofa is filled. When a barber is free, the customer that has been on the sofa the longest is served and, if there are any standing customers, the one that has been in the shop the longest takes a seat on the sofa. When a customer’s haircut is finished, any barber can accept payment, but because there is only one cash register, payment is accepted for one customer at a time. The barbers divide their time among cutting hair, accepting payment, and sleeping in their chair waiting for a customer.

It’s very similar to the original problem, with the difference that there are multiple barbers. You can think of the proposition as a queue, where some number of workers prepare inputs, another set transforms the inputs (the sofa) and yet another number of workers produce outputs (the barbers). In order to control the resource usage, there’s a limit on the amount of queued work that can be consumed.

In the solution I propose, there’s a barbershop holds information about the capacity and limits, as well as presenting an interface to control the queue.

type Barbershop struct {
	Capacity int
	SofaSize int
	Chairs   int

	BarbershopCh chan Customer
	PaymentCh    chan Payment
}

the barbershop also provides a way to control the run of the program and create the auxiliary components:

func (b Barbershop) Run() {
	sofa := make(Sofa, b.SofaSize)
	go sofa.Run(b.BarbershopCh)

	for i := b.Chairs; i > 0; i-- {
		barber := Barber{Name: fmt.Sprintf("%d", i)}
		go barber.Run(sofa, b.PaymentCh)
	}

	time.Sleep(5 * time.Second)
}

The sofa is simply a buffered channel, and its Run method allows the program to take a customer from the first staging area:

func (s Sofa) Run(shop chan Customer) {
	for {
		c := <-shop
		s <- c
		log.Printf("Customer %s sitting on sofa", c.Name)
	}
}

Since the shop channel is buffered, it’s accumulating customers until the buffer is full. This function, running as a goroutine, is taking customers out of that channel and passing it to another buffered channel, the sofa.

Here there’s what I consider a minor bug with respect to the original specification: since the sofa channel is also buffered, and the capacity is lower than the shop channel, it is possible that a customer is taken from the staging area and there’s no room in the sofa for it. If another customer tries to enter the shop at that point it will be possible to have one more customer in the system than what’s allowed. The fix for that is to lower the channel’s capacity by one. But this leads to the other side of the same bug: customers might be rejected when there are only 19 in barbershop. In the way the system is set up, what’s more likely to happen is that there’s going to be N customers buffered in the shop channel, 1 customer in between, and M customers buffered in the sofa channel.

The rest of the solution is pretty straightforward:

func (c Customer) Run(b Barbershop) {
	if c.EnterShop(b.BarbershopCh) == false {
		return
	}
	c.GetHaircut()
	c.Pay(b.PaymentCh)
	c.ExitShop()
}

The customer tries to enter the shop, going away if it’s full. It waits for a haircut and pays when it gets it. And when I say that it waits for a haircut, it actually waits for that:

func (c Customer) GetHaircut() {
	<-c.HaircutCh
	log.Printf("Customer %s got haircut", c.Name)
}

the haircut channel is specific to the customer, to make it possible for the barber to tell the correct customer that he’s finished cutting the hair. The payment, by the specification, goes to any barber, so there’s a single channel read by the three barbers whenever they get a chance to do so:

func (b Barber) Run(sofa Sofa, payment chan Payment) {
	for {
		log.Printf("Barber %s sleepling", b.Name)

		c := <-sofa
		log.Printf("Customer %s sitting on barber %s's chair", c.Name, b.Name)
		time.Sleep((time.Duration)(250) * time.Millisecond)
		c.HaircutCh <- Haircut{}

		p := <-payment
		log.Printf("Barber %s got payment from customer %s", b.Name, p.c.Name)
	}
}

Initially I had implemented this differently:

func (b Barber) Run(sofa Sofa, payment chan Payment) {
	for {
		log.Printf("Barber %s sleepling", b.Name)

		select {
		case c := <-sofa:
			// ...
			c.HaircutCh <- Haircut{}

		case p := <-payment:
			log.Printf("Barber %s got payment from customer %s", b.Name, p.c.Name)
		}
	}
}

I changed this because it makes possible for the barber to drain the sofa channel (and indirectly the access to the shop) without ever receiving payments, leading to a situation where the barbershop becomes more and more crowded. With the other implementation, the barber simply takes one customer from the sofa, cuts hair and waits for payment, making it impossible to overcrowd the shop.

The way to fix the deficiencies is to actually have a goroutine counting the customers going in and out of the barbershop, and stop letting customers in if the barbershop is full:

func (b Barbershop) Run() {
	total := 0
	in := b.in
	select {
	case c := <-in:
		total++
		if total == b.Capacity {
			in = nil
		}
		b.waitarea <- c
	case c := <- out:
		total--
		in = b.in
	}
}

The full source is here.

Next week it’s Christmas in March!

PS: I was a little late with this post because I wasn’t entirely satisfied with the implementation I had, and I let it rest for a couple of days.