"The Little Book of Semaphores" (2nd Ed. by Allen B. Downey, section 4.5.1) as well as Wiki (link) mentioned that a trivial solution (as shown below) to the 'Cigarette smokers problem' will cause a deadlock. Somehow I couldn't wrap my head around it. Pls help me undersatnd how deadlock can occur for the below solution. P.S. We assumed agent code cannot be modified and We're free to use semaphores and other variables as needed

Code sample (from the book):

     Agent A                 Agent B          Agent C
1 agentSem.wait()     agentSem.wait()      agentSem.wait()
2 tobacco.signal()    paper.signal()       tobacco.signal()
3 paper.signal()      match.signal()       match.signal()

     Smoker I           Smoker II               Smoker III
1 tobacco.wait()       paper.wait()           tobacco.wait()
2 paper.wait()         match.wait()           match.wait()
3 agentSem.signal()    agentSem.signal()      agentSem.signal()

    Assume semaphores 'tobacco', 'paper', and 'match' are  initialized with
    zero, and 'agentSem' is initialized with one.
  • 1
    $\begingroup$ I think the idea of the deadlock is that smokers remove items one by one and not pairs. So if you need a and b and there is a and c on the table you take a and wait forever for b. $\endgroup$ – Eugene Dec 6 '16 at 10:24

Agent A consumes agentSem, and produces tobacco and paper.

That might make Smoker I smoke but he is late: Smoker II already took the paper and Smoker III took tobacco.

Now, all the smokers are stuck, and the agents as well.

  • $\begingroup$ @ chi - This is the reasoning made in the book. But as the problem states that the agent would repeat the process of supplying the ingredients, I wonder, wouldn’t the subsequent supply of either {paper, match} or {tobacco, match} or even {tobacco, paper} guarantee that at least one of the smokers progresses. $\endgroup$ – KGhatak Dec 6 '16 at 11:08
  • 1
    $\begingroup$ @BuckCherry I guess that the book is trying to say that the agents repeat their whole code. Rerunning Agent I would wait on the semAgent semaphore again, and that is still zero since no one was able to smoke. Hence, deadlock. $\endgroup$ – chi Dec 6 '16 at 13:23
  • $\begingroup$ @ chi - Thanks a lot. So silly of me :( $\endgroup$ – KGhatak Dec 6 '16 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.