3
$\begingroup$

"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.
Improve this question
$\endgroup$
1
  • 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
    Commented Dec 6, 2016 at 10:24

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Dec 6, 2016 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
    Commented Dec 6, 2016 at 13:23
  • $\begingroup$ @ chi - Thanks a lot. So silly of me :( $\endgroup$
    – KGhatak
    Commented Dec 6, 2016 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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