display | more...

Like the dining philosophers problem the sleeping barber problem is a classical IPC problem. Both show which problems can occur in a multitasking multi user environment, when several tasks try to use the same resources. In contrast to the dining philosophers, which is rather abstract (though still very interesting), the sleeping barber problem has a more realistic background.

The problem
We have a barber shop with n seats and one barber. If no customer is in the shop, the barber falls asleep. If customer arrives three situations can happen:

• no other customers in the shop, barber sleeps. The customer has to wake the barber, and gets a haircut.
• <= n customers in the shop (free seats), barber works. The customer sits down on one of the free chairs, and has to wait for his turn.
• n+1 customers in the shop. All the seats are taken. The customer has to leave the shop.

What's the practical background?
You can think of the customers as programs, which want to print. The barber shop is the printing spooler with a finite number of slots for printing job (realistic, as memory is limited). The barber is a thread of the barber shop. If it has nothing to do it sleeps. If printing jobs arrive it is woken up, and works until all slots are free.

So what's the problem?
Actually there are three problems. The first is mutual exclusion. A customer has to prevent other customers entering the customer shop at the same time (as both would take the same seat or try to get a haircut at the same time). The second problem is to see if the barber is sleeping or not and the third is whether or not there are free seats in the barber shops.

Solution

Problem 1: just a semaphore which the customer down's, when entering the shop and up's when he's registered as a customer

Problem 2: This is achieved using two semaphores. The customer up's the customer semaphore, when entering the shop, and the barber down's it, when he arrives in the morning and after finishing a haircut. He sleeps if no customers are in the shop, and a customer entering the shop and upping the semaphore wakes him. The same thing happens the other way. The customer down's the barber semaphore. If no barber sleeps, he has to sleep until a barber tries to sleep, by upping the barbers semaphore.

Problem 3: is pretty simple. Just one integer variable counting the customers is used. If this variable is smaller than the number of seats, the customer tries to wake the barber. If the barber is not asleep, the customer sits down and begins to sleep.

Log in or register to write something here or to contact authors.