Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Copy of The sleeping barber problem

Operating System Project
by

Iry Cociug

on 17 January 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of The sleeping barber problem

The Problem
The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his hair. If there are no other customers waiting, he returns to his chair and sleeps in it.
Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves. Based on a naive analysis, the above description should ensure that the shop functions correctly, with the barber cutting the hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice, there are a number of problems that can occur that are illustrative of general scheduling problems.


The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair, etc.) all take an unknown amount of time. 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. In another example, two customers may arrive at the same time when there happens to be a single seat in the waiting room. They observe that the barber is cutting hair, go to the waiting room, and both attempt to occupy the single chair.


Relationship with the Producer – Consumer Problem
The sleeping barber problem and the producer – consumer problem are somehow similar.
The producer – consumer problem uses a common shared memory area, where the producer
stores data and the consumer takes the data.

The first issue appears when the producer wants to store some data in the memory area and this area is full and the second one when the consumer wants to read data from the memory area and this is empty.
The solution for the first issue is to suspend the producer until the consumer takes at least one piece of data from the shared memory area and the solution for the second issue is to suspend the consumer until the producer stores new data in the memory area.
Actually, in the sleeping barber shop problem the role of the producer is played by the clients, the role of the consumer is played by the barber and the memory area is equivalent to the number of chairs in the waiting room.
When the waiting room is full, the clients are forced to leave the barbershop so process of adding new data in the memory area is suspended( just as in the producer-consumer case).
If the waiting room is empty, the barber would lie on the barber chair, doing nothing, taking a nap so the process of taking data from the memory area is suspended.

The Solution
An incorrect approach to this problem may lead to some issues like:
 The barber could wait forever for a client and in the same time a client could wait forever for the barber
 The clients may not respect their arrival order and this could lead to the fact that some of them
will never have the opportunity to sit on the barber's chair although they were waiting.

The problem analysis:

 mutual exclusion(mutex): a client has to prevent another client to enter at the same time in the barbershop due to the fact that both of them will sit on the same chair and the barber would cut their hair at the same time
 checking the state of the barber(sleep or awake)
 checking the number of empty seats in the waiting room

Implementation
This solution will use three semaphores:
 clients: contains the number of clients that are in the waiting room
 barbers: the number of barbers (0 or 1 ) who are idle, waiting for clients
 mutex: which is used for mutual exclusion

It also uses a variable “wait” which counts the number of clients waiting, in fact it is a copy of clients and it is necessary because we cannot read the current value of a semaphore.

Constant and Global Variables

#define Chairs 5 /* number of chairs in the waiting room */
typedef int semaphore;
semaphore clients=0; /* number of clients waiting for service */
semaphore barber=0; /* number of barbers waiting for clients */
semaphore mutex=1; /* for mutual exclusion */
int wait=0; /* clients are waiting(not being cut) */

Remarks:
There is no loop in the client's procedure because every client cuts his hair only once; in the barber's procedure there is a loop that ables the barber to take the next client
The solution is from the book of A.S. Tanenbaum, Modern Operating Systems

Barber's procedure

void barber(void)
{
while(TRUE)
{
down(&Clients); /* go to sleep if number of clients is 0 */
down(&mutex); /* acquire access to 'waiting' */
wait=wait-1; /* decrement count of waiting customers*/
up(&barbers); /* one barber is now ready to cut hair*/
up(&mutex); /*release 'wait'*/
cut_hair(); /*cut hair (outside critical region)*/
}
}

Client's procedure

void client(void)
{
down(&mutex); /*enter critical region*/
if(wait<Chairs){ /*if there are no free chairs, leave*/
wait=wait+1; /*increment count of waiting customers*/
up(&customers); /*wake up barber if necessary */
up(&mutex); /*release access to 'wait'*/
down(&barbers); /*go to sleep if number of free barbers is 0*/
get_haircut(); /*be seated and be serviced*/
}else{
up(&mutex); /*shop is full; do not wait*/
}
}

The problem can be generalized by considering more than one barber (multiple sleeping barbers problem).
A possible solution can use nine semaphores for binary or general usage:
 capacity: total number of chairs in the waiting room;
 wait: number of waiting clients;
 barbers: number of barbers;
 hair_cutting: ensure us that a barber is performing only a task at once;
 ready, done: specifies if there is a client ready or a client that is already hair cutted ;
 payment: specifies if a payment is about to be done;
 bill: specifies the end of the payment;
 leave: specifies when the client leaves the barber's chair;

Semaphores

typedef int semaphore;
semaphore capacity=12;
semaphore wait=3;
semaphore barbers=3;
semaphore hair_cutting=3;
semaphore ready=0, done=0;
semaphore leave=0;
semaphore payment=0, bill=0;

Client's procedure

void client(void) {

down(&capacity);
enter_barbershop();
down(&wait);
wait_in_line();
down(&barbers);
leave_chair();
up(&wait);
prepare_haircut();
up(&ready);
down(&done);
finish_haircut();
down(&leave);
pay();
up(&payment);
down(&bill);
exit_barbershop();
up(&capacity);
}

Barber's procedure

void barber(void) {
while (true) {
down(&ready);
down(&hair_cutting);
haircut();
up(&hair_cutting);
down(&leave);
up(barbers);
}
}

Cashier's procedure

void casier(void) {
while (TRUE) {
down(&payment);
down(&hair_cutting);
accept_payment();
up(&hair_cutting);
up(&bill);
}
}

Real life applications:
-call-center;
-printers;
-the institution's ticket mechanism;

Tanenbaun A.S., “Modern Operating System”, 2nd Edition
Fortis F., “Sisteme de operare”, Editura Eubeea, 2005
References

The Sleeping Barber Problem
Ovidiu Staniloiu
Adrian Secheres
Norberth Stancu
Full transcript