The Sleeping Barber Problem

Computer Science Level 2

Barber Billy has made a separate waiting room for his barber shop. In the haircut room, there is just one barber chair though.

Billy does the following every time he finishes cutting someone's hair:

  • He checks the waiting room through the CCTV camera.
    • If there is someone, he goes to the waiting room and calls them to the haircut room.
    • If the waiting room is empty, he just falls asleep in his chair.

Clients in his shop behave in the following way:

  • When a client enters the shop, they go to the haircut room and check whether the barber is sleeping.
    • If he is sleeping, the client wakes up the barber.
    • If he is cutting someone else's hair, they go to the waiting room and wait.

Could it ever be the case that Billy would be sleeping indefinitely even though a customer is waiting in the waiting room?

Yes, this is possible No, this never happens

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Jordan Ladyman
Apr 18, 2017

I do not often post solutions, so I'm not sure if my logic is correct here, but here it goes:

The outlined tasks seem to cover every possible scenario, except for one. To find it, we must first rationalize to where the hole in the tasks might be.

In order for the barber to be asleep, he must first see no one through the CCTV camera. However, if any sets foot into the shop, they will proceed to the room with the sleeping barber and thus follow the tasks to wake up the barber.

THEREFORE, we are looking for a scenario where there IS a customer already in the shop when the barber sees no one on the CCTV camera. Assuming that the camera provides a full and clear view of the entire waiting room, we must conclude that the customer is in a different room.

The only rooms that any of the tasks allow a customer to be in (unless there is an assumed public restroom that hopefully would not have a surveillance camera) are the waiting room and the barber's haircutting room.

So, if the customer were to check on the status of the barber and see that he is NOT asleep (rather, he is checking his camera), then the customer would proceed to go back to the waiting room to wait.

Unfortunately, the barber would then go to sleep until another customer came, so let's hope this barber gets frequent business!!

5 Helpful 0 Interesting 0 Brilliant 0 Confused

The problem I see with this solution is that it either assumes a blind spot that is not revealed in the original problem, that the walk from the waiting room to the cutting room is long enough to finish a haircut, or that the CCTV is in a room other than the cutting room.

All that the problem asserts is that there are 2 rooms and a CCTV, so the only way they can be connected is by a single doorway. As soon as rooms or hallways are added to the scenario there becomes a limitless number of variables that could be added.

I wanted to give the answer that you did, but I kept going back to the original set of variables and felt that those solutions required me to add variables that were not a part of the scenario.

Peter Leinweber - 4 years, 1 month ago

Glad you posted a solution. Yes, this is a valid scenario where the customer and the barber are fooled by the systems they devised.

Another scenario would be a time when 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. ( Wikipedia )

The nice thing here is that this problem is not as much of an adhoc problem as it sounds. This could represent synchronization between agents which depend on each other. For example, an operating system sending files to the printer to print.

Agnishom Chattopadhyay - 4 years, 1 month ago
Sam Salmons
May 3, 2017

The initial conditions are not specified. What does the first client do if the barber is not yet cutting someone's hair nor is sleeping? Perhaps the barber is setting up when the first client walks in and so the barber tells the first client to go and wait. Then, the barber gets tired and takes a nap.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...