Talk:Sleeping barber problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Does this page make sense to computer experts? I certainly don't understand it. :-) Jwrosenzweig 00:13, 28 Feb 2004 (UTC)

Not really, I only knew of the dining philosophers problem. This article (and similar pages found by Google) state the rules but not what the difficulty really is - in plain language. I searched and only found homework problems being stated, or programs that claimed to be successful implementations. So why are the locks important? What's the relevance of an unbounded queue? Someone that has actually analysed this needs to write some more text for us!  (-;  – Lee J Haywood 18:46, 15 May 2004 (UTC)
Is it any better now? Dori | Talk 05:37, May 16, 2004 (UTC)
Yes, much better. Personally I'd like to have a clear understanding of what happens when you don't implement a valid solution. For example, with the dining philosophers, it's clear that deadlock occurs when they all take, say, their left forks and then wait for the other – it is then easy to work out the solution for yourself. With this article, the solution is outlined well, but I don't think that it is immediately clear why it is correct to someone who is only vaguely familiar with semaphores. Thanks.  – Lee J Haywood 08:29, 16 May 2004 (UTC)
OK, how about now? :) We'll make an article out of this. Dori | Talk 15:41, May 16, 2004 (UTC)
Okay, I still have 2 points to make. First, the outline of the solution doesn't mention the use of a queue – so starvation would be an issue. Second, the solution says that a new customer can sit in the barber's chair when they arrive, if it is empty, ignoring those in the waiting room. So the solution seems to neglect how the barber actually chooses the next customer and how that customer gets from the waiting room to the chair. Of course, we don't want the whole solution here – it is a homework problem, after all (I'd implement it myself, but I'm very ill at the moment).  – Lee J Haywood 08:23, 17 May 2004 (UTC)
I have to check since it's been a while, but I believe the semaphores take care of the queues. Dori | Talk 15:08, May 17, 2004 (UTC)
Yes, starvation is an issue. The customers will have their hair cut in a random order, so one of them may wait indefinetely if customers arrive all the time. And yes, a customer that just arrived may get his hair cut ahead of others in the waiting room, if timing is right. The main purpose of this solution is to guarantee the synchronization between barber and customer. To prevent starvation you must enforce FIFO order on the customers, but this require aditional coding. Also, the problem does not state that the first one to arrive should be the first one to get a hair cut, but this is usually true. Italo Tasso 13:34, 8 June 2007 (UTC)

I don't get the whole picture - maybe I am not so smart :-}.

In my thinking, each customer enters, take a sit and call the barber to cut his hair. The barber remember who has called him (the "call" will wake him if necessary) and cut the hairs in this order. I fail to see any race conditions here... :-?. Can someone state the prerequisites of this problem more precisely to show what actions are atomic and what not? (As example, how could it be, that the barber wait *on* an customer while this customer wait *on* the barber?)

When you say that the barber remembers who has called him, you are already solving the problem using a queue. That is a possible solution. Every problem that can be solved with a message queue can be solved with semaphores/shared memory, and vice versa. The problem we want to solve happens when the barber is cutting someones hair and another customer arrives. The barber must finish cutting hair and the second customer must wait. The barber can't cut both hair at the same time, nor stop one in the middle. Barber and customer must be synchronized. Italo Tasso 14:03, 8 June 2007 (UTC)

Since the barber problem is rather illustrative (like the philosophy dinner), maybe replacing the words "semaphore" and "mutex" with illustrative examples could make me understand it?

So if I get it right, a mutex is some kind of a table bell. Each customer enter, sit down and press the bell which will make the bartender awake, right? (Since there is only one bell, they have to wait until the bell is "free").

The semaphore is not as easy for me to map to the barber problem. Currently I just think of the semaphore as the customer chairs, however I fail to see a concurrency problem here (as long as "sit down onto a free chair" is atomic). Maybe it is something different?

Mutex and semaphore are the same thing. Mutex or lock usually refers to a binary semaphore, whose value is only one or zero. An illustrative example on semaphores would be keys to a room. On the entrace there is a box with keys. If you want to enter, you must grab a key (P function). When you leave, you drop the key on the box (V function). If there are no keys in the box, you wait (P) until someone else drops a key (V). A mutex would be a box with only one key, so that you have only one person in the room at a time. Check out the page about semaphores here at the wikipedia. Italo Tasso 14:03, 8 June 2007 (UTC)

--Imi.

Are the semaphore inited to zero? maybe it would be helpfull to show their init in the pseodo code. —The preceding unsigned comment was added by 212.143.92.226 (talkcontribs) .

I just added the initialization values. Italo Tasso 14:03, 8 June 2007 (UTC)

I did some changes to the pseudo-code:

  • The initialization values for the semaphores were missing.
  • I replaced the acquire/release semaphore notation with the more conventional P and V. Acquire/release usually refer to locks or binary semaphores. The customers semaphore is not binary. It must assume values greater than 1 to work properly. It is not clear that releasing it several times will increase its value beyond 1.
  • In the customer thread, there was a loop that caused all customers to have their hair cut. This is not how it should be. If there are no free seats, the customer leaves without having his hair cut.

Italo Tasso 12:58, 8 June 2007 (UTC)

Mistakes?[edit]

Is it just me or the semaphore functions aren't right?

Taken from Semaphore article here on wikipedia :
P(Semaphore s) {

 wait until s > 0, then s := s-1;
 /* must be atomic once s > 0 is detected */

}

V(Semaphore s) {

 s := s+1;   /* must be atomic */

}

Well...isn't actually P which waits if nothing is available? The code says : V(Customers) //tries to acquire a customer - if none is available he goes to sleep

same here: V(accessSeats) //at this time he has been awakened - want to modify the number of available seats

or here : P(accessSeats) //don't need to lock the chairs anymore shouldn't we give the lock back (make it 1) ?

I think they should be swapped and it will be ok. Or maybe it's just me... 141.85.0.74 22:04, 14 November 2007 (UTC)

Deadlock?[edit]

I understand that some customers may not get their haircut if there is not any queue. But how it could possibly result in a deadlock? —Preceding unsigned comment added by 88.101.76.122 (talk) 03:06, 4 March 2008 (UTC)

I think that using semaphores is a mess compared to using queues:

barber.takeNextCustome() {

   queue.pop(); // wait on next customer to aarive if no one is waiting

}

customer.arrive() {

   queue.push( this ); // wait for barber to be free or awake him if he's waiting

}


I second the complants here. This is a lousy explanation. I think it boils down to not explaining how the barber might come to be waiting on a customer. DJ Clayworth (talk) 01:55, 11 February 2010 (UTC)