The senate bus problem

The next problem in “The Little Book of Semaphores” is called “the senate bus problem” and reads as follows:

Riders come to a bus stop and wait for a bus. When the bus arrives, all the waiting riders invoke boardBus, but anyone who arrives while the bus is boarding has to wait for the next bus. The capacity of the bus is 50 people; if there are more than 50 people waiting, some will have to wait for the next bus.

When all the waiting riders have boarded, the bus can invoke depart. If the bus arrives when there are no riders, it should depart immediately.

Puzzle: Write synchronization code that enforces all of these constraints.

The trick in this problem is preventing passengers from trying to board the bus after the bus has arrived. It’s very easy to handle if you build a queue of passengers inside a “bus station”. This bus station would accept passengers and start boarding as soon as the bus arrives. Handling the special constraints in this problem becomes trivial:

func (s *BusStation) Run() {
	var riders []*Passenger

	for {
		select {
		case p := <-s.gate:
			riders = append(riders, p)

		case bus := <-s.bus:
			// Bus arrived
			n := min(bus.capacity, len(riders))
			bus.Board(riders[:n])
			riders = riders[n:]
		}
	}
}

A channel is used to get passengers and collect them in a slice. Another channel is used to “receive” the bus when it arrives. When the bus arrives, the passengers start boarding, taking into account the capacity of the bus and the number of passengers in the boarding station. While this is happening, no passengers are getting thru the gate, satisfying the “no boarding after bus arrived” condition.

The Board method of the bus is trivial:

func (b *Bus) Board(passengers []*Passenger) {
	for _, p := range passengers {
		p.SignalBoard()
	}
}

It simply signals each of the passengers that it has boarded. SignalBoard is also trivial:

func (p *Passenger) SignalBoard() {
	close(p.sem)
}

A passenger is running this code:

	p := NewPassenger(fmt.Sprintf("Passenger %d", i))
	station.Enter(p)
	p.WaitBoard()

Basically it enters the station and waits until it’s signaled that it has boarded. WaitBoard looks like this:

func (p *Passenger) WaitBoard() {
	<-p.sem
}

WaitBoard will block until something returns from the channel, or when the channel is closed, which is what SignalBoard does.

station.Enter looks like this:

func (s *BusStation) Enter(p *Passenger) {
	s.gate <- p
}

It simply sends a pointer to the Passenger over the gate channel, which the bus station receives and adds to the riders slice.

This is simpler than the solution presented in the book: the only explicit signaling that happens is in the WaitBoard/SignalBoard methods, and this is happening in the “correct” direction, where the bus is telling the passenger that it has boarded.

The full source (with minor modifications for presentation) is here.

Next week we go to court.