The roller coaster problem

Section 5.7 of “The Little Book of Semaphores” presents the last of the “less classical” synchronization problems. It’s another problem presented in “Concurrent Programming”, called “the roller coaster problem” and attributed to J.S. Herman. It reads as follows:

Suppose there are n passenger threads and a car thread. The passengers repeatedly wait to take rides in the car, which can hold C passengers, where C < n. The car can go around the tracks only when it is full.

Like in previous cases, the problem here is that multiple goroutines have to queue up waiting for some service and then they need to be notified about the completion of a process. One solution would be to have all the n goroutines send on a channel and have them block receiving from a second channel. On the other end, a goroutine would be reading from the first channel and when the process completes it would send n signals to the second channel. This would be enough to fulfill the constraints in the statement above.

I would like to explore another approach here. Have the n goroutines send to a channel, have the “car” goroutine receive C times from the same channel. What the sending goroutines would send is information about themselves (for illustration purposes the name suffices) and a channel that the “car” can use to notify the goroutines that the ride is over.

The passengers would look something like this:

	for {
		queue <- p
		<-p.Ch
	}

where p is the information about the passenger and p.Ch is the channel that the car uses to talk back to that specific goroutine.

The car would look something like this:

	passengers := make([]Passenger, 0, CarCapacity)

	// Load passengers
	for capacity := CarCapacity; capacity > 0; capacity-- {
		p := <-queue
		passengers = append(passengers, p)
	}

	// the car is full, go for a ride
	time.Sleep(100 * time.Millisecond)

	// Unload passengers
	for i := 0; i < CarCapacity; i++ {
		passengers[i].Ch <- struct{}{}
	}

And that’s it. This is enough to build a system like the one the problem describes.

One interesting thing to note is that with this solution, a goroutine getting off the car can get back on it right away, starving other goroutines that might have been waiting longer. One simple way to solve this issue is to make the channel corresponding to the queue buffered. In that way the passengers build up an actual queue. In that way, the goroutines getting off the car cannot immediately get back on it as there are other goroutines already in the front of the queue.

The full source is here.

Next week it’s the start of the not-so-classical problems, and it starts by manipulating linked lists.