Sleeping barber problem | Hacker News Reader

Sleeping barber problem

en.wikipedia.org

119 pointsSami_Lehtinen27 comments

This is a poor analogy because most barber shops have line-of-sight between the barbers and waiting room. The "both asleep" issue will never arise in the real world, and thus, the analogy doesn't help explain the problem.

Slightly better analogy of a similar but not exactly identical problem, which no doubt people have actually experienced unintentionally: you and a friend go to a store, decide to split up and buy different things. You go to where the X is, he goes to where the Y is.

You tell your friend "come meet me near the X when you're done, and if I'm done I'll find you at the Y". He tells you "come meet me near the Y when you're done", and if I'm done I'll find you at the X."

I'd say it's more of a colorful description than an analogy. Consider the classic dining philosophers problem for a crazier example. Who eats with both hands, using different forks, and sharing forks with your neighbor? And yet being able to visualize it like that helps a lot.

The dining philosophers have chopsticks in all the formulations I've seen. Wikipedia disagrees with me, FWIW.

Is this some kind of contest in missing the point?

This whole thread is.

Wasn't this the whole reason DARPA created the internet in the first place?

Clearly, you've never worked with philosophers.

What makes a philosopher other than love of wisdom? And in your estimation are they missing the point of other philosophers, or of non-philosophers? If the latter, what's a non-philosopher?

Chopsticks makes more sense, certainly. Although still, who shares chopsticks (much less trades individual chopsticks with other diners)?! I doubt this dinner ever actually happened. :P

Philosophers do, obviously.

Interesting, never heard that variant before.

In my OS class in college, my professor actually took the time in the lecture to criticize the textbook for describing it with forks and spaghetti rather than the less ludicrous rice and chopsticks. OTOH, when the computer science club at my school had an event where you could go to literally act out the problem with others, they used double-ended forks (I think two forks taped together) to mitigate germ spreading.

But a pair of chopsticks is meant to be held in one hand, and picking up food with one chopstick per hand is clumsy at best (since the sticks are at opposing angles rather than near-parallel).

How about knives and meat, where the non-dominant hand’s knife is used in place of a fork? That would definitely require having one utensil in each hand. Seems a bit crude-mannered for erudite philosophers, though...

The point is that chopsticks are interchangeable resources, unlike forks and knives, and you usually need two of them to eat, unlike forks.

The story makes sense for me if you assume that the dining philosophers aren't going to use one chopstick per hand, but they have to pick up one to the left and one to the right before they can put two in one hand.

This is a facile complaint - the analogy isn't meant to illustrate something about barbers, it's meant to illustrate things about interprocess communication.

You might as well say "actually life is not like a box of chocolates, because it cannot be purchased at candy shops and doesn't melt when you leave it on your dashboard".

Yes, any analogy will break down if you chase it to the fringes, but in this case, the central core of the analogy doesn't work. That makes it a bad analogy - you may as well just explain what's going on directly. Or spend the trivial effort to make a better one.

Surely "sleeping barber" sounds like a much more attractive problem to work on than "sleeping dentist".

The point of the analogy is to assign the described traits to the discussed concept, instead of putting the concept in the world of the analogy.

Analogies are about quick understanding, not about being real. Apparently you understood it, so it is a good example to use. Adding a virtual hallway with closed walls and doors between waiting area and working area is not a big deal.

If it's possible for the barber to finish and check the waiting room before the new customer traverses back to the waiting room from checking the barber, it means that the barber shop is poorly architected, and needs to be reimplemented (preferably with the latest JS framework).

And then write a pretentious Medium blog post how that (single-threaded “concurrent”) JS framework solves all concurrency/parallelism problems of the world by using async/await.

> For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no one there (the customer not having arrived yet), he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber.

This is the critical part of the analogy, and is why it breaks down. It's such an artificial contrivance to suggest that both the barber and the customer moving to the waiting room won't notice each other - yes, you can come up with theoretical ways to do it, but that's requiring contortions in order to explain what is supposed to be the main point of the analogy.

(it's already a stretch that the barber can't see the waiting clients, as per degenerate's comment above)

Totally agree. My initial reaction to this problem was that it could be solved with a thread-safe queue (usually already implemented in the chosen language).

Well there would have been no such thing already implemented in a standard library back in 1965 ;) And it's still a useful exercise for exactly why you need a thread-safe blocking queue, and probably shouldn't just roll your own if you don't know what you're doing.

> And it's still a useful exercise for exactly why you need a thread-safe blocking queue

Is it? A thread-safe blocking queue sounds like one of those take-a-number systems you find in some shops. But it would be very common to instead rely on the standard waiting-customer algorithm, in which, after waiting for some period of time, the customer gets frustrated and rings the bell at the counter. Take-a-number systems are vanishingly rare by comparison. Why do you need the queue?

Nobody has to take a number for a queue to form. Imagine people camping in front of apple stores for the new iPhone. Nobody is taking numbers yet the first to arrive also is the first customer that gets an iPhone.

I don't know why I picked such a complicated example.

Did you ever go to the grocery store and had to wait for the people in front of you? That's also queue and yet nobody is taking numbers.

I may just be misunderstanding, but if you were to represent a queue of people waiting in line as a data structure, wouldn't they each have a number, like their index in an array, etc? How is that different than a take-a-number system?

Queues are inherently ordered, right? The take-a-number system is still a queue, it just replaces physical ordering with a paper that shows your place in line.

Reply on news.ycombinator.com