Talk:Cigarette smokers problem

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)

Parnas mentions this in his paper:

"In Patil's description of the problem the agent is considered to be an unchangeable part of the problem definition and is defined by the six processes shown below..."

This solution has the agent/arbiter pick the smoker to notify directly, and is a solution to a different problem altogether, as the agent has been changed.

The overflows he mentions are caused by increments on S[1], S[2], and S[4], which are used to encode conditional state in a semaphore array. As there are P-operations for S[3], S[5], and S[6] those semaphores are properly decremented, but S[1], S[2], and S[4] never are. The P-operation processes ensure that those semaphores are drained again, provided there is no starvation of the process that drains.

Personally I do not see why these have to be done in separate processes, as S[6], S[5], and S[3] define which values of S[1], S[2], and S[4] have been incremented. So the process P(S[6]) could perform P(S[4]) P(S[2]), the process P(S[5]) could perform P(S[4]) P(S[1]) and the process P(S[3]) could perform P(S[2]) P(S[1]) without needing the drain process (rendering the argument that starvation could lead to an overflow moot).

What I do not understand is what Parnas means when he talks about his correspondence with Courtier about reducing processes and introducing S[0], is there anyone who can clarify that?

Ronald Huizer, 11 February 2011 —Preceding unsigned comment added by 216.189.164.158 (talk) 05:15, 11 February 2011 (UTC)

What is the PROBLEM

This article is completely useless the way it stands at present. The "problem formulation" is missing! Even my first-year BSc students can write better articles than this - at least they understand that the problem must be well defined.... — Preceding unsigned comment added by 85.224.154.124 (talk) 12:35, 24 December 2012 (UTC) 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)

The problem is still missing, or at least not clearly formulated. I assume the problem is somewhere along the lines that the other two smokers can't smoke as fast as they would want to because they need to wait for the matchman to stop blocking the table? —Preceding unsigned comment added by 82.197.252.119 (talk) 20:41, 24 March 2009 (UTC)

I agree that the problem itself is not well articulated in this article, previous user quuxplusone mentions the dining philosophers problem, but that problem is well articulated in that they need 2 forks to eat but if everyone picks up one and waits, nobody can eat. 99.255.142.67 (talk) —Preceding undated comment added 04:00, 23 April 2011 (UTC).

One year after the last edit, the PROBLEM itself is still not clear. Can someone with more knowledge than I have add this? Erwin (talk) 15:15, 6 June 2012 (UTC)

Something is missing. Please state the PROBLEM explicitly! — Preceding unsigned comment added by 185.25.95.132 (talk) 14:27, 5 April 2015 (UTC)

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)

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)

Lung cancer???

Is there any source for the "smokers get lung cancer" line? This was added by a non-logged-in user, and I don't know if it even really makes sense... Darkxsun (talk) 04:07, 16 April 2009 (UTC)

Lung Cancer can be one of the solution to get out of the deadlock. One smoker would die and his infinite resource would be available for rest of the two. —Preceding unsigned comment added by 220.225.34.13 (talk) 12:36, 27 January 2010 (UTC)

Or would completely disappear -- each smoker could have their resources locked away in a safe that none of the others had the key for. In which case the problem would persist. Even if not, it would require two smokers to die to "solve" the problem. —Preceding unsigned comment added by 80.167.145.223 (talk) 18:48, 18 February 2010 (UTC)

please

I don't understand this. Please have editors make this article more accessible to lay readers. In particular, I don't understand what the actual problem is, since it seems that every smoker is probably going to be able to smoke a lot. —Preceding unsigned comment added by 74.242.207.79 (talk) 09:28, 3 March 2011 (UTC)

I agree. After reading this article, the user has no idea of what the actual problem is. It doesn't state that what it does state is a problem.--Prehistoricmanthe2nd (talk) 01:37, 19 March 2013 (UTC)

Historic Quote "What the Fuck does this even mean?" please have somebody write an introduction that explains what the Legendary /imaginary? problem is and how it might arise. To do that, they might also want to fully elucidate the Patel parameters. Somebody is being lazy, or lyin' or none of the admittedly intelligent folk actually have a goddamn clue what the meaning of an Encyclopedia is. They are treating the subject as though they are chatting amongst themselves in a chat room.

It is better than nothing, if you are well versed in a few areas, but a hunch persists that for somebody with understanding, by putting some effort into it it could be elucidated in a way approacheable by a layperson.

The article still doesn't say what is the problem? I thought maybe I was having difficulty with reading comprehension, but I come here and see many others with the same question.129.219.155.89 (talk) 19:28, 30 December 2013 (UTC)

June 2015 cleanup

This edit on 02:43, February 25, 2006 by Quuxplusone reformulated the problem statement in a way that fundamentally changes the problem, as well as introducing an unsourced solution that fails to meet the problem constraints. I've attempted to restore the original problem using sources available online, hopefully making it clearer what the problem actually is. — Miles 07:10, 30 June 2015 (UTC)

They

"The smoker who has the third supply should remove the two items from the table, using them (along with their own supply) to make a cigarette, which they smoke for a while."

Is the supply that of the third smoker? Who smokes the cigarette, the third smoker or all three? Of course, English is not my native language, but cannot it be that something is wrong with the sentence? Эйхер (talk) 18:35, 12 November 2016 (UTC)

Problem Update 2022

I made some minor changes to make it clear that the problem has fundamental restrictions. I've also made it clear that these restrictions have been questioned/criticized.

Prior to this the problem section did not even mention the restrictions. Ggpur (talk) 13:23, 20 February 2022 (UTC)