The cigarette smokers

The “The Little Book of Semaphores”, introduces the “cigarette smokers problem”. The problem was originally presented by Suhas Patil in a technical MIT memo¹, as a problem that cannot be solved with semaphores. This is the original formulation:

Three smokers are sitting at a table. One of them has tobacco, another has cigarette papers, and the third one has matches – each one has a different ingredient required to make and smoke a cigarette but he may not give any ingredient to another. On the table in front of them, two of the three ingredients will be placed, and the smoker who has the necessary third ingredient should pick up the ingredients from the table, make the cigarette and smoke it. Since a new set of ingredients will not be placed on the table until this action is completed, the other smokers who cannot make and smoke a cigarette with the ingredients on the table must not interfere with the fellow who can.

The memo goes on to state that coordination among smokers is needed and states there’s “a restriction that the process which supplies the ingredients cannot be changed and that no conditional statements can be used.” The first restriction can be understood if you think of that “process” as the operating system: you are not going to tailor the OS to each program it runs. The second restriction is subject of debate. Patil’s motivation was arguing that Dijkstra’s semaphores are insufficient for solving certain kinds of problems, and that it was necessary to extend them.

Parnas argued² that Patil’s solution is inadequate and that the problem can be solved without conditional statements by resorting to arrays of semaphores. His solution relies on introducing intermediate threads that keep track of the available ingredients, and goes through some gymnastics to avoid using conditional statements. In Go terms, his solution assigns one channel to each smoker, and it sends a signal over that channel when the ingredients required by that smoker become available.

Looking at Patil’s formulation, you have three things (processes, threads, goroutines, …) that produce exactly two ingredients on demand, and there’s the middle process that triggers the ingredient production. On the other end, you have three things that consume exactly one of those combinations. In other words, there’s a 1:1 relationship between the producers and the consumers, and the actual restriction in the problem is that only one producer-consumer chain can be active at any given time.

The problem is trivially solved by connecting the producer with the consumer and discarding the “table” in the middle, which is in my opinion a more realistic scenario: there’s a producer for each of the ingredients and there are processes collecting them. As soon as the correct pair becomes available, this wakes up the matching process.

If you follow that design, this is where the issue with expressing this problem in terms of separate threads becomes more apparent. In the diagram below, if tobacco is produced first, and this is consumed by the “tobacco paper” collector, and then a match is produced, the system has to wait for either more tobacco or paper to be produced. Two ingredients have been produced, which allow the consumer with paper to advance, yet it cannot because the resource has been appropriated by another part of the system.

It should be evident that this is solved by fusing the three collectors into one, and having it decide where to send the resources. But this is exactly the thing that the problem statement forbids.

I’m going to propose a solution very similar to the one shown by Parnas, but expressed in a more Go-like way. It does not contain conditional statement in the spirit of the restriction imposed by Patil, but it’s heavy on conditionals by way of the select statement.

First, as suggested by Patil, there are three agents producing pairs of ingredients. The agent waits for a cigarette to be produced before providing the ingredients for the next one. Since there are three agents, this is used to select which one of them is going to go next at producing ingredients. Each produced ingredient is sent over its corresponding channel. select is used to avoid imposing an order on the sending process. In order to avoid having to write code for an agent that produces each ingredient pair, one of the channels is nil for each of the three agents (remember that a send to a nil channel blocks forever). Whenever an ingredient is sent, the corresponding channel is set to nil.

func (a *Agent) run() {
	for {
		<-a.CigaretteCh

		tobaccoCh := a.TobaccoCh
		paperCh := a.PaperCh
		matchCh := a.MatchCh

		for i := 2; i > 0; i-- {
			select {
			case tobaccoCh <- Tobacco{}:
				tobaccoCh = nil
			case paperCh <- Paper{}:
				paperCh = nil
			case matchCh <- Match{}:
				matchCh = nil
			}
		}
	}
}

Next there’s a “pusher”, which takes ingredients from the agent and pushes them to the smokers. In the same way as done by Parnas, the pusher keeps track of the destination smoker by way of having a bit field that describes whether or not the ingredients should be sent or if it should keep waiting for more. Because of the way the agent is constructed, it’s not necessary to set channels to nil after receiving an item from them, as we know it’s going to send exactly two of them.

func (p *Pusher) run() {
	smokers := []chan<- SmokerPackage{
		nil,               // 0
		nil,               // 1
		nil,               // 2
		p.SmokerMatchCh,   // 3
		nil,               // 4
		p.SmokerPaperCh,   // 5
		p.SmokerTobaccoCh, // 6
	}

	pkg := SmokerPackage{}

	t := 0

	for {
		select {
		case item := <-p.TobaccoCh:
			pkg.Tobacco = &item
			t |= 0x1
		case item := <-p.PaperCh:
			pkg.Paper = &item
			t |= 0x2
		case item := <-p.MatchCh:
			pkg.Match = &item
			t |= 0x4
		case smokers[t] <- pkg:
			t = 0
			pkg = SmokerPackage{}
		}
	}
}

And lastly, the smoker is trivial: receive a package with ingredients, build a cigarette, and send it over the channel. In this case, that channel is read by the agent to proceed with the next cycle.

func (s *Smoker) run() {
	for {
		pkg := <-s.PackageCh
		s.CigaretteCh <- Cigarette{}
	}
}

This is the final implementation:

The full code for the solution is here.

What might not be immediately evident is that while the diagram is meant to explain the structure of the communication across the different components, it also shows the structure of the program in terms of channels and goroutines. The structure of the code is much easier to understand than the equivalent using threads and semaphores.

Is this solution valid within the original constraints? I say yes. It’s valid in the same way that the Parnas solution is valid. The use of select does not violate the requirement that no conditionals are used. select in this case is effectively doing the same thing as the scheduler picking up a specific thread to allow it to run and acquire a semaphore. The division of labor among threads is different from the one Parnas uses, but the program flow is very similar. Patil’s restriction around conditionals refers to not having to peek at shared variables in order to take decisions. Ignoring the code in the Go runtime (which is effectively the same as Patil ignoring the code in the operating system), this implementation does not have conditionals in that sense. Unlike Parnas’, this solution does not rely on shared memory. The value used to decide which channel to use to send the information is entirely local to the pusher goroutine.

Next week: dining savages.

Footnotes

¹ Patil, Suhas S. (February 1971). Limitations and Capabilities of Dijkstra’s Semaphore Primitives for Coordination among Processes (Technical report). MIT, Project MAC, Computation Structures Group. Memo 57.

² Parnas, David L. (March 1975). On a solution to the cigarette smokers’ problem (without conditional statements). Communications of the ACM 18 (3): 181–183. doi:10.1145/​360680.360709.