The Sleeping Barber Problem

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?

×

Problem Loading...

Note Loading...

Set Loading...