Talk:Sleeping barber problem

Making sense

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)

The whole picture

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.

Semaphore

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 (talk • contribs) .

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

Code changes

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?

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?

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)

Shop layout

I'm a bit baffled by For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While they're on their way, the barber finishes their current haircut and goes to check the waiting room. Since there is no one there (the customer not having arrived yet)... - what layout is being imagined here for this to make sense, where the barber overtakes the customer on their way to the waiting room? Are we meant to imagine two adjacent rooms for cutting and waiting, with a long corridor that the customer must traverse between them, and a separate, shorter corridor (or even a door or window) which only the barber can use?

I can't find any description of the setup in sources that matches this, only examples like "A sleepy town contains a small barber shop having two doors and a few chairs. Customers enter through one door and leave through the other door." where it's all framed as being one room. Is this "customer not having arrived yet" aspect original research? --Lord Belbury (talk) 16:37, 4 December 2019 (UTC)

Wrong exemple?

I think that the last synchronization problem example is wrong:

"In another situation, two customers may arrive at the same time when there happens to be a single seat in the waiting room. They observe that the barber is cutting hair, go to the waiting room, and both attempt to occupy the single chair."

Following the described situation, the waiting room may have many chairs and not just one, so this can't be correct.