For example, if the agent puts out tobacco and paper, the smoker with the matches should pick up both ingredients, make a cigarette, and then signal the agent. To explain the premise, the agent represents an operating system that allocates resources, and the smokers represent applications that need resources. The problem is to make sure that if resources are available that would allow one more applications to proceed, those applications should be woken up. Conversely, we want to avoid waking an application if it cannot proceed. Based on this premise, there are three versions of this problem that often

First, you are not allowed to modify the agent code. If the agent represents an operating system, it makes sense to assume that you dont want to modify it every time a new application comes along. The second restriction is that you cant use conditional statements or an array of semaphores. With these constraints, the problem cannot be solved, but as Parnas points out, the second restriction is pretty articial . With constraints like these, a lot of problems become unsolvable. The interesting version: This version keeps the rst restrictionyou cant change the agent codebut it drops the others.

The trivial version: In some textbooks, the problem species that the agent should signal the smoker that should go next, according to the ingredients that are available. This version of the problem is uninteresting because it makes the whole premise, the ingredients and the cigarettes, irrelevant. Also, as a practical matter, it is probably not a good idea to require the agent to know about the other threads and what they are waiting for. Finally, this version of the problem is just too easy. 101 1 2 3 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 102 Classical synchronization problems Naturally, we will focus on the interesting version. To complete the statement of the problem, we need to specify the agent code. The agent uses the following semaphores:

Agent semaphores agentSem = Semaphore (1) tobacco = Semaphore (0) paper = Semaphore (0) match = Semaphore (0) The agent is actually made up of three concurrent threads, Agent A, Agent B and Agent C. Each waits on agentSem; each time agentSem is signaled, one of the Agents wakes up and provides ingredients by signaling two semaphores. Agent A code agentSem . wait () tobacco . signal () paper . signal () Agent B code agentSem . wait () paper . signal () match . signal () Agent C code agentSem . wait () tobacco . signal () match . signal () This problem is hard because the natural solution does not work. It is tempting to write something like: Smoker with matches tobacco . wait () paper . wait () agentSem . signal () Smoker with tobacco paper . wait () match . wait () agentSem . signal () 1 2 3 4.5 Cigarette smokers problem Smoker with paper tobacco . wait () match . wait () agentSem . signal () Whats wrong with this solution? 103 104