Operating System Concepts

Download 252.5 Kb.
Size252.5 Kb.
The Dining Philosopher’s Problem

From “Operating System Concepts”, by Silberschatz, 5th edition.

Used in Class Lecture – 10/12/03

Sleeping Barber Problem

From “Modern Operating Systems”, by A. Tanenbaum, p. 62

Used in class Lecture
This is an analysis a greatly simplified “barbershop problem”. The barbershop consists of a waiting room with only two chairs, one barber chair, and one barber. If a customer arrives and there is an empty chair (in waiting room), he sits down, and waits for his turn for a haircut. If the waiting room is full, the customer simple leaves. If there are no customers, the barber sleeps. If a customer arrives, he “notifies” (not the Java notify!) the barber and waits. On being notified, the barber wakes up if sleeping, if not sleeping, the barber keeps cutting. Note that a barber is “notified” when a customer signals on the customers semaphore. The following semaphore definitions and pseudocode describe the interaction between customers and he barber.
The barb-ctrl semaphore has the following interpretation:

if barber is not sleeping, then barb-ctrl  0, and magnitude of barb-ctrl is number of customers waiting.

In particular, if barber is not sleeping and barb-ctrl = 0, then barber is cutting hair with no one waiting.

If barber is sleeping, then barb-ctrl = 0 (not cutting & no customers waiting).

.barb-ctrl may be summarized as follows:


barber sleeping

barber not sleeping


not cutting hair & no one waiting

cutting hair & no one waiting

< 0 (negative)

cannot happen

cutting hair & customers waiting

Customers block on this barb-ctrl if the barber is busy

The customer semaphore represents the number of people in the waiting room when the barber is cutting hair, and is –1 when the barber is sleeping. The barber “sleeps” by blocking on the customers semaphore.
semaphore customers = 0; /* # of customers waiting for service, if barber awake */

/* barber sleeps by blocking on this semaphore */

semaphore barb-ctrl = 0; /* see above for description */

semaphore mutex = 1; /* to control mutual exclusion of critical section */

int waiting = 0; /* shared variable = number of customers waiting */
void barber() { /* barber process */

while (1) {

wait(customers); /* go to sleep (clock) if # of customers is 0 */

wait (mutex); /* acquire access to critical section */

--waiting; /* decrement count of waiting customers */

signal(barb-ctrl); /* invite a customer to get in the barber chair */

signal(mutex); /* release the mutex */

cut_hair(); /* cut hair – will take a variable amount of time */



void customer() { /* customer process */

wait(mutex); /* acquire access to critical section */

if (waiting < 2) { /* if here are free chairs, enter & sit down */

++waiting;; /* increment count of waiting customers */

signal(customers); /* notify barber – wake him up if sleeping */

signal(mutex); /* release the mutex */

wait(barb-ctrl); /* wait for the barber */

get_haircut(); /* get into barber chair and get a haircut */


else signal(mutex); /* shop full, release mutex and leave */

Share with your friends:

The database is protected by copyright ©dentisty.org 2019
send message

    Main page