Talk:Cigarette smokers problem

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Mid rated as Mid-importance on the assessment scale

Contents

[edit] Solution

I've just updated the article with a solution to the problem that involves an array of semaphores (which explains why Patil didn't consider it a solution). But it seems utterly straightforward and trivial! So I don't understand why Parnas' paper[1] makes the problem statement and array-based solution sound so complicated, or why he's talking about "semaphore overflow" when all you need are binary semaphores. And why the restriction on conditional statements? Am I misunderstanding the problem — does it have extra constraints the article doesn't mention? --Quuxplusone 02:47, 25 February 2006 (UTC)

[edit] What is the PROBLEM

What is missing from the page is the definition - What is the PROBLEM? Should be a final paragraph under the section "Problem".

"Argument" starts with saying the problem is solvabale or non-solvable, but what does it mean to solve this problem? —Preceding unsigned comment added by 212.143.17.66 (talk • contribs)

As with other famous synchronization problems (Sleeping barber problem, Dining philosophers problem, Readers-writers problem), the "problem" is simply to simulate on a computer what has already been described in words. I've added a paragraph, but it's very much repeating what's already explained further down, in the "Argument" section, so maybe someone else can clean it up and remove the redundancy. --Quuxplusone 06:54, 21 March 2006 (UTC)

[edit] Silliness of problem

I fail to see how the problem with the original restrictions says anything at all about semaphores. Is it even possible to do the random selection stage without using either an array or conditional statements? -Ahruman 08:45, 18 October 2006 (UTC)

[edit] You sure about the code?

I tried to implement this simple code with semaphores and the semaphore for a specific smoker can get easily over the limit (assume the same smoker is chosen three times in a row) - with T semaphore set to 0 in the beginning everything works fine... —Preceding unsigned comment added by 87.105.14.3 (talk • contribs)

So, are you saying the code doesn't work, or are you saying "everything works fine"? Anyway, the pseudocode looks to me like a direct translation of the English description given in the intro. Are you remembering that of the three smokers, one of them is waiting on A[0], one on A[1], and one on A[2]? If you made them all wait on A[0], that would obviously be a problem. --Quuxplusone 07:02, 7 June 2007 (UTC)


I'm a newbie and I wasn't sure how to add another comment this thread (through 'edit' is ok?). Back to the issue - I meant that if the code was implemented as stated (especially with T semaphore with initial value of 1) you can easily get this semaphore out of bounds (and that, at least in c#, gives you a runtime error)
Imagine such situation - the 'table' thread starts (with semaphore T with value of 1) and chooses smoker 0, signals it(semaphore A[0] is 1), then executes wait(T) (this semaphore goes to 0) and starts another loop, at the same time smoker executes wait(A[0]) (A[0] goes back to 0), then signal(T) (T goes back to 1), and starts smoking (I assume it takes relatively long time, long enough to keep it occupied till the end of our simulation :)
The situation now: (beginning of 2nd 'table' loop) - A[0] is 0, T is 1, 'table' chooses once more smoker 0, signals it (A[0] is 1), does wait(T) (T goes to 0) and starts another loop (third one), now it chooses smoker 0 for the third time, signals it and here A[0] goes to 2 - which I think is a serious mistake - I might be of course wrong, I'm no expert.
Anyway, thanks for the reply, and let me know what you think of my a little bit too long post ;). Greets, Chodorowicz 13:53, 7 June 2007 (UTC)
(Yes, the "edit" link at the top of the section, or the "edit this page" tab at the top of the page, work for editing.)
If smoker 0 is smoking, then he will not pick up the second signal on A[0]. Therefore, A[0] will remain 1, and T will remain 0 (because smoker 0 has not signaled on T yet). Therefore, the 'table' will not pick up any signal from T; he'll remain waiting in wait(T). Only when smoker 0 finishes his first cigarette will he start rolling another, and only when he's rolled that one will he again signal(T), allowing the 'table' to wake up for the third loop. It is invariably true that if smoker 0 is smoking, and smoker 0 is being signaled, then the 'table' is asleep. Basically, you just missed one wait(T) in your scenario; you have three loops, but only two wait(T)s. --Quuxplusone 02:59, 8 June 2007 (UTC)
I think that my confusion is related to the terms "make a cigarette", and "smoke the cigarette". If I understood you correctly (T will remain 0 (because smoker 0 has not signaled on T yet) the smoker thread should not signal T until he finishes smoking, and in the code on the page we have signal(T) before "smoke the cigarette", If implement code in such a way that signal(T) goes before thisThread.sleep(); my scenario can go as I described it; Chodorowicz 11:47, 8 June 2007 (UTC)

I think an example will do a better job of explaining than more paragraphs from me. Notice that this is a token passing protocol; there is one semaphore for each "agent" in the system, and at any given time, at most one of those semaphores is high. An agent only acts when his semaphore is high (when he "has the token"); and when he's done acting, he "gives" the token to someone else by signaling their semaphore. --Quuxplusone 09:14, 9 June 2007 (UTC)

Event Table A[0] A[1] A[2]
Start 1 0 0 0
Table waits(T), succeeding immediately 0 0 0 0
Table signals(A[0]) 0 1 0 0
Table waits(T) 0 1 0 0
Smoker 0 finishes wait(A[0]) 0 0 0 0
Smoker 0 makes a cigarette 0 0 0 0
Smoker 0 signals(T) 1 0 0 0
Smoker 0 starts smoking 1 0 0 0
Table finishes wait() 0 0 0 0
Table signals(A[0]) 0 1 0 0
Table waits(T) 0 1 0 0
Smoker 0 keeps smoking 0 1 0 0
Smoker 0 finishes smoking 0 1 0 0
Table is still waiting 0 1 0 0
Smoker 0 waits(A[0]) 0 1 0 0
Smoker 0 finishes wait(A[0]) 0 0 0 0
Smoker 0 makes another cigarette 0 0 0 0
Table is still waiting 0 0 0 0
Smoker 0 signals(T) 1 0 0 0
...


I agree 100% with the table you sketched, but... (sorry for the constant “but's”, I hope they don't drive you crazy, I think this is the last one:).. in the sketch how program works that you provided you have
Event Table A[0] A[1] A[2]
Start 1 0 0 0
Table waits(T), succeeding immediately 0 0 0 0
Table signals(A[0]) 0 1 0 0
...
So clearly agent/table first executes wait(T) and after that signal(A[0], and in the code on the page these operations are clearly placed inversely (first signal(A[k]); then wait(T);) Chodorowicz 19:17, 9 June 2007 (UTC)

Ah. Well. :) I've fixed it now. Thanks! --Quuxplusone 03:35, 11 June 2007 (UTC)

Nice. Thanks for the clarifications and interesting discussion. Greets! That was my first input in the development of Wikipedia, I hope I can do more in the future :)Chodorowicz 14:35, 11 June 2007 (UTC)