computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none and doing so in an orderly manner. The barber and his customers represent aforementioned processes.
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 or her 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 he wakes him up and sits in the chair. If the barber is cutting hair then he goes to the waiting room. If there is a free chair in the waiting room he sits in it and waits his turn. If there is no free chair then the customer leaves. On a naive analysis the above description should ensure that the shop functions correctly, with the barber cutting 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, which 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 hasn't 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, observe that the barber is cutting hair and there is a single seat in the waiting room, and go to the waiting room. They will both then attempt to occupy the single chair.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in fundamental programming.
[edit] A solution
This article does not cite any references or sources.
Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (February 2010)
A possible solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and the third ensures mutual exclusion. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and if none of these are empty, leaves. Otherwise the customer takes a seat – thus reducing the number available (a critical section). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get their haircut one at a time.
This problem involves only one barber, and it is therefore also called the single sleeping barber problem. A multiple sleeping barbers problem is similar in the nature of implementation and pitfalls, but has the additional complexity of coordinating several barbers among the waiting customers.
Implementation
* The following pseudo-code guarantees synchronization between barber and customer and is deadlock free, but may lead to starvation of a customer. P and V are functions provided by the semaphores.
* You need (as mentioned above):
+ Semaphore Customers = 0
+ Semaphore Barber = 0
+ Semaphore accessSeats (mutex) = 1
+ int NumberOfFreeSeats = N //total number of seats
* The Barber (Thread/Process):
while(true) { //runs in an infinite loop
P(Customers) //tries to acquire a customer - if none is available he goes to sleep
P(accessSeats) //at this time he has been awakened - want to modify the number of available seats
NumberOfFreeSeats++ //one chair gets free
V(Barber) //the barber is ready to cut
V(accessSeats) //we don't need the lock on the chairs anymore
//here the barber is cutting hair
}
* The Customer (Thread/Process):
while(true) { //runs in an infinite loop
P(accessSeats) //tries to get access to the chairs
if ( NumberOfFreeSeats > 0 ) { //if there are any free seats
NumberOfFreeSeats-- //sitting down on a chair
V(Customers) //notify the barber, who's waiting that there is a customer
V(accessSeats) //don't need to lock the chairs anymore
P(Barber) //now it's this customer's turn, but wait if the barber is busy
//here the customer is having his hair cut
} else { //there are no free seats
//tough luck
V(accessSeats) //but don't forget to release the lock on the seats
//customer leaves without a haircut
}
}
Tuesday, March 2, 2010
The R-W problem
The R-W problem: is another classic problem for which design of synchronization and concurrency mechanisms can be tested. The producer/consumer is another such problem; the dining philosophers is another.
Definition
* There is a data area that is shared among a number of processes.
* Any number of readers may simultaneously write to the data area.
* Only one writer at a time may write to the data area.
* If a writer is writing to the data area, no reader may read it.
* If there is at least one reader reading the data area, no writer may write to it.
* Readers only read and writers only write
* A process that reads and writes to a data area must be considered a writer (consider producer or consumer)
Semaphore Solution: Readers have Priority
int readcount = 0;
semaphore wsem = 1; //
semaphore x = 1; //
void main(){
int p = fork();
if (readcount==1)
wait(wsem);
signal(x);
doReading();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal(x);
}
}
void writer(){
while(1){
wait(wsem)
doWriting();
signal(wsem)
}
}
if(p) reader; // assume multiple instances
else writer; // assume multiple instances
}
void reader(){
while(1){
wait(x);
readcount++;
Once readers have gained control, a flow of reader processes could starve the writer processes.
Rather have the case that when a write needs access, then hold up subsequent reading requests until after the writing is done.
Semaphore Solution: Writers have Priority
int readcount, writecount = 0;
semaphore rsem, wsem = 1; //
semaphore x,y,z = 1; //
void main(){
int p = fork();
if(p) reader; // assume multiple instances
else writer; // assume multiple instances
}
void reader(){
while(1){
wait(z);
wait(rsem);
wait(x);
readcount++;
if (readcount==1)
wait(wsem);
signal(x);
signal(rsem);
signal(z);
doReading();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal(x);
}
}
void writer(){
while(1){
wait(y);
writecount++;
if (writecount==1)
wait(rsem);
signal(y);
wait(wsem);
doWriting();
signal(wsem);
wait(y);
writecount--;
if (writecount==0)
signal(rsem);
signal(y);
}
}
Definition
* There is a data area that is shared among a number of processes.
* Any number of readers may simultaneously write to the data area.
* Only one writer at a time may write to the data area.
* If a writer is writing to the data area, no reader may read it.
* If there is at least one reader reading the data area, no writer may write to it.
* Readers only read and writers only write
* A process that reads and writes to a data area must be considered a writer (consider producer or consumer)
Semaphore Solution: Readers have Priority
int readcount = 0;
semaphore wsem = 1; //
semaphore x = 1; //
void main(){
int p = fork();
if (readcount==1)
wait(wsem);
signal(x);
doReading();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal(x);
}
}
void writer(){
while(1){
wait(wsem)
doWriting();
signal(wsem)
}
}
if(p) reader; // assume multiple instances
else writer; // assume multiple instances
}
void reader(){
while(1){
wait(x);
readcount++;
Once readers have gained control, a flow of reader processes could starve the writer processes.
Rather have the case that when a write needs access, then hold up subsequent reading requests until after the writing is done.
Semaphore Solution: Writers have Priority
int readcount, writecount = 0;
semaphore rsem, wsem = 1; //
semaphore x,y,z = 1; //
void main(){
int p = fork();
if(p) reader; // assume multiple instances
else writer; // assume multiple instances
}
void reader(){
while(1){
wait(z);
wait(rsem);
wait(x);
readcount++;
if (readcount==1)
wait(wsem);
signal(x);
signal(rsem);
signal(z);
doReading();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal(x);
}
}
void writer(){
while(1){
wait(y);
writecount++;
if (writecount==1)
wait(rsem);
signal(y);
wait(wsem);
doWriting();
signal(wsem);
wait(y);
writecount--;
if (writecount==0)
signal(rsem);
signal(y);
}
}
Producer-consumer problem
producer-consumer problem (also known as the bounded-buffer problem) is a classical example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer. The producer's job is to generate a piece of data, put it into the buffer and start again. At the same time the consumer is consuming the data (i.e. removing it from the buffer) one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.
The solution for the producer is to go to sleep if the buffer is full. The next time the consumer removes an item from the buffer, it wakes up the producer who starts to fill the buffer again. In the same way, the consumer goes to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer. The solution can be reached by means of inter-process communication, typically using semaphores. An inadequate solution could result in a deadlock where both processes are waiting to be awakened. The problem can also be generalized to have multiple producers and consumers.
Implementations
This solution has a race condition. To solve the problem, a careless programmer might come up with a solution shown below. In the solution two library routines are used, sleep and wakeup. When sleep is called, the caller is blocked until another process wakes it up by using the wakeup routine. itemCount is the number of items in the buffer.
int itemCount
procedure producer() {
while (true) {
item = produceItem()
if (itemCount == BUFFER_SIZE) {
sleep()
}
putItemIntoBuffer(item)
itemCount = itemCount + 1
if (itemCount == 1) {
wakeup(consumer)
}
}
}
procedure consumer() {
while (true) {
if (itemCount == 0) {
sleep()
}
item = removeItemFromBuffer()
itemCount = itemCount - 1
if (itemCount == BUFFER_SIZE - 1) {
wakeup(producer)
}
consumeItem(item)
}
}
The problem with this solution is that it contains a race condition that can lead into a deadlock. Consider the following scenario:
The consumer has just read the variable itemCount, noticed it's zero and is just about to move inside the if-block.
Just before calling sleep, the consumer is interrupted and the producer is resumed.
The producer creates an item, puts it into the buffer, and increases itemCount.
Because the buffer was empty prior to the last addition, the producer tries to wake up the consumer.
Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost. When the consumer resumes, it goes to sleep and will never be awakened again. This is because the consumer is only awakened by the producer when itemCount is equal to 1.
The producer will loop until the buffer is full, after which it will also go to sleep.
Since both processes will sleep forever, we have run into a deadlock. This solution therefore is unsatisfactory.
An alternative analysis is that if the programming language does not define the semantics of concurrent accesses to shared variables (in this case itemCount) without use of synchronization, then the solution is unsatisfactory for that reason, without needing to explicitly demonstrate a race condition.
[edit] Using semaphores
Semaphores solve the problem of lost wakeup calls. In the solution below we use two semaphores, fillCount and emptyCount, to solve the problem. fillCount is incremented and emptyCount decremented when a new item has been put into the buffer. If the producer tries to decrement emptyCount while its value is zero, the producer is put to sleep. The next time an item is consumed, emptyCount is incremented and the producer wakes up. The consumer works analogously.
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE
procedure producer() {
while (true) {
item = produceItem()
down(emptyCount)
putItemIntoBuffer(item)
up(fillCount)
}
}
procedure consumer() {
while (true) {
down(fillCount)
item = removeItemFromBuffer()
consumeItem(item)
}
}
The solution above works fine when there is only one producer and consumer. Unfortunately, with multiple producers or consumers this solution contains a serious race condition that could result in two or more processes reading or writing into the same slot at the same time. To understand how this is possible, imagine how the procedure putItemIntoBuffer() can be implemented. It could contain two actions, one determining the next available slot and the other writing into it. If the procedure can be executed concurrently by multiple producers, then the following scenario is possible:
up(emptyCount) Two producers decrement emptyCount
One of the producers determines the next empty slot in the buffer
Second producer determines the next empty slot and gets the same result as the first producer
Both producers write into the same slot
To overcome this problem, we need a way to make sure that only one producer is executing putItemIntoBuffer() at a time. In other words we need a way to execute a critical section with mutual exclusion. To accomplish this we use a binary semaphore called mutex. Since the value of a binary semaphore can be only either one or zero, only one process can be executing between down(mutex) and up(mutex). The solution for multiple producers and consumers is shown below.
semaphore mutex = 1
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE
procedure producer() {
while (true) {
item = produceItem()
down(emptyCount)
down(mutex)
putItemIntoBuffer(item)
up(mutex)
up(fillCount)
}
up(fillCount) //the consumer may not finish before the producer.
}
procedure consumer() {
while (true) {
down(fillCount)
down(mutex)
item = removeItemFromBuffer()
up(mutex)
up(emptyCount)
consumeItem(item)
}
}
Notice that the order in which different semaphores are incremented or decremented is essential: changing the order might result in a deadlock.
The solution for the producer is to go to sleep if the buffer is full. The next time the consumer removes an item from the buffer, it wakes up the producer who starts to fill the buffer again. In the same way, the consumer goes to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer. The solution can be reached by means of inter-process communication, typically using semaphores. An inadequate solution could result in a deadlock where both processes are waiting to be awakened. The problem can also be generalized to have multiple producers and consumers.
Implementations
This solution has a race condition. To solve the problem, a careless programmer might come up with a solution shown below. In the solution two library routines are used, sleep and wakeup. When sleep is called, the caller is blocked until another process wakes it up by using the wakeup routine. itemCount is the number of items in the buffer.
int itemCount
procedure producer() {
while (true) {
item = produceItem()
if (itemCount == BUFFER_SIZE) {
sleep()
}
putItemIntoBuffer(item)
itemCount = itemCount + 1
if (itemCount == 1) {
wakeup(consumer)
}
}
}
procedure consumer() {
while (true) {
if (itemCount == 0) {
sleep()
}
item = removeItemFromBuffer()
itemCount = itemCount - 1
if (itemCount == BUFFER_SIZE - 1) {
wakeup(producer)
}
consumeItem(item)
}
}
The problem with this solution is that it contains a race condition that can lead into a deadlock. Consider the following scenario:
The consumer has just read the variable itemCount, noticed it's zero and is just about to move inside the if-block.
Just before calling sleep, the consumer is interrupted and the producer is resumed.
The producer creates an item, puts it into the buffer, and increases itemCount.
Because the buffer was empty prior to the last addition, the producer tries to wake up the consumer.
Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost. When the consumer resumes, it goes to sleep and will never be awakened again. This is because the consumer is only awakened by the producer when itemCount is equal to 1.
The producer will loop until the buffer is full, after which it will also go to sleep.
Since both processes will sleep forever, we have run into a deadlock. This solution therefore is unsatisfactory.
An alternative analysis is that if the programming language does not define the semantics of concurrent accesses to shared variables (in this case itemCount) without use of synchronization, then the solution is unsatisfactory for that reason, without needing to explicitly demonstrate a race condition.
[edit] Using semaphores
Semaphores solve the problem of lost wakeup calls. In the solution below we use two semaphores, fillCount and emptyCount, to solve the problem. fillCount is incremented and emptyCount decremented when a new item has been put into the buffer. If the producer tries to decrement emptyCount while its value is zero, the producer is put to sleep. The next time an item is consumed, emptyCount is incremented and the producer wakes up. The consumer works analogously.
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE
procedure producer() {
while (true) {
item = produceItem()
down(emptyCount)
putItemIntoBuffer(item)
up(fillCount)
}
}
procedure consumer() {
while (true) {
down(fillCount)
item = removeItemFromBuffer()
consumeItem(item)
}
}
The solution above works fine when there is only one producer and consumer. Unfortunately, with multiple producers or consumers this solution contains a serious race condition that could result in two or more processes reading or writing into the same slot at the same time. To understand how this is possible, imagine how the procedure putItemIntoBuffer() can be implemented. It could contain two actions, one determining the next available slot and the other writing into it. If the procedure can be executed concurrently by multiple producers, then the following scenario is possible:
up(emptyCount) Two producers decrement emptyCount
One of the producers determines the next empty slot in the buffer
Second producer determines the next empty slot and gets the same result as the first producer
Both producers write into the same slot
To overcome this problem, we need a way to make sure that only one producer is executing putItemIntoBuffer() at a time. In other words we need a way to execute a critical section with mutual exclusion. To accomplish this we use a binary semaphore called mutex. Since the value of a binary semaphore can be only either one or zero, only one process can be executing between down(mutex) and up(mutex). The solution for multiple producers and consumers is shown below.
semaphore mutex = 1
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE
procedure producer() {
while (true) {
item = produceItem()
down(emptyCount)
down(mutex)
putItemIntoBuffer(item)
up(mutex)
up(fillCount)
}
up(fillCount) //the consumer may not finish before the producer.
}
procedure consumer() {
while (true) {
down(fillCount)
down(mutex)
item = removeItemFromBuffer()
up(mutex)
up(emptyCount)
consumeItem(item)
}
}
Notice that the order in which different semaphores are incremented or decremented is essential: changing the order might result in a deadlock.
Dining philosophers problem
In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. It is a classic multi-process synchronization problem.
In 1965, Edsger Dijkstra set an examination question on a synchronization problem where five computers competed for access to five shared tape drive peripherals. Soon afterwards the problem was retold by Tony Hoare as the dining philosophers problem.
This is a theoretical explanation of deadlock and resource starvation by assuming that each philosopher takes a different fork as a first priority and then looks for another.
Problem
The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things: eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right.
Illustration of the dining philosophers problem
The dining philosophers problem is sometimes explained using rice and chopsticks rather than spaghetti and forks, as it is more intuitively obvious that two chopsticks are required to begin eating.
The philosophers never speak to each other, which creates a dangerous possibility of deadlock when every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).
Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of unwarranted requests'. In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so forth, making a circular chain.
Starvation (and the pun was intended in the original problem description) might also occur independently of deadlock if a philosopher is unable to acquire both forks because of a timing problem. For example there might be a rule that the philosophers put down a fork after waiting five minutes for the other fork to become available and wait a further five minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up their left fork at the same time the philosophers will wait five minutes until they all put their forks down and then wait a further five minutes before they all pick them up again.
In general the dining philosophers problem is a generic and abstract problem used for explaining various issues which arise in problems which hold mutual exclusion as a core idea. The various kinds of failures these philosophers may experience are analogous to the difficulties that arise in real computer programming when multiple programs need exclusive access to shared resources. These issues are studied in the branch of Concurrent Programming. The original problems of Dijkstra were related to external devices like tape drives. However, the difficulties studied in the Dining Philosophers problem arise far more often when multiple processes access sets of data that are being updated. Systems that must deal with a large number of parallel processes, such as operating system kernels, use thousands of locks and synchronizations that require strict adherence to methods and protocols if such problems as deadlock, starvation, or data corruption are to be avoided.
[edit]Solutions
[edit]Waiter solution
A relatively simple solution is achieved by introducing a waiter at the table. Philosophers must ask his permission before taking up any forks. Because the waiter is aware of which forks are in use, he is able to arbitrate and prevent deadlock. When four of the forks are in use, the next philosopher to request one has to wait for the waiter's permission, which is not given until a fork has been released. The logic is kept simple by specifying that philosophers always seek to pick up their left hand fork before their right hand fork (or vice versa).
To illustrate how this works, consider the philosophers are labelled clockwise from A to E. If A and C are eating, four forks are in use. B sits between A and C so has neither fork available, whereas D and E have one unused fork between them. Suppose D wants to eat. Were he to take up the fifth fork, deadlock becomes likely. If instead he asks the waiter and is told to wait, we can be sure that next time two forks are released there will certainly be at least one philosopher who could successfully request a pair of forks. Therefore deadlock cannot happen.
[edit]Monitor solution
The example below shows a solution where the forks are not represented explicitly. Philosophers can eat if none of their neighbors are eating. This is comparable to a system where philosophers that cannot get the second fork must put down the first fork before they try again.
In the absence of locks associated with the forks, philosophers must ensure that the decision to begin eating is not based on stale information about the state of the neighbors. If philosopher B sees that A is not eating, then turns and looks at C, A could begin eating while B looks at C. This solution avoids this using a single mutual exclusion lock, not associated with the forks, but with the decision procedures that can change the states of the philosophers. This is ensured by the monitor. The procedures test, pickup and putdown are local to the monitor and share a mutual exclusion lock. Notice that processes calling WAITC(x) release the lock and wait on the variable x until another process calls SIGNALC(x) on the same variable. When the process that called WAITC resumes, it will have reacquired the lock.
Notice that this example does not tackle the starvation problem. For example, philosopher 2 can wait forever on condition variable can_eat[2] if the eating periods of philosophers 1 and 3 always overlap.
To also guarantee that no philosopher starves, one could keep track of the number of times a hungry philosopher cannot eat when his neighbors put down their forks. If this number exceeds some limit, the state of the philosopher could change to Starving, and the decision procedure to pick up forks could be augmented to require that none of the neighbors are starving.
A philosopher that cannot pick up forks because a neighbor is starving, is effectively waiting for the neighbor's neighbor to finish eating. This additional dependency reduces concurrency. Raising the threshold for transition to the Starving state reduces this effect.
[edit]Example Solution
Example Solution written in Pascal (using Monitor synchronization)
PROGRAM d_p;
CONST
DoomsDay = FALSE;
MONITOR dining_philosophers; // Start of monitor declaration
CONST
Eating = 0;
Hungry = 1;
Thinking = 2;
VAR
i : INTEGER; // init loop variable
state : ARRAY [0..4] OF INTEGER; // Eating, Hungry, Thinking
can_eat : ARRAY [0..4] OF CONDITION; // one for each Philosopher
// place for Hungry Ph to wait until chopsticks become available
PROCEDURE test(k : INTEGER);
BEGIN
IF (state[k] = Hungry)
AND (state[(k+4) MOD 5] <> Eating)
AND (state[(k+1) MOD 5] <> Eating) THEN
BEGIN
state[k] := eating;
SIGNALC(can_eat[k]); // End the wait if any
END;
END;
PROCEDURE pickup(i: INTEGER);
BEGIN
state[i] := Hungry;
WRITELN('philosopher ',i,' hungry');
test(i); // are my neighbors eating?
IF state[i] <> Eating THEN
WAITC(can_eat[i]); // wait until they finish eating
WRITELN('philosopher ',i,' eating');
END;
PROCEDURE putdown(i : INTEGER);
BEGIN
state[i] := Thinking;
WRITELN('philosopher ',i,' thinking');
test( (i+4) MOD 5); // give left neighbor chance to eat
test( (i+1) MOD 5); // give right neighbor chance to eat
END;
BEGIN // initialize monitor
FOR i := 0 TO 4 DO state[i] := Thinking;
END; // end of monitor definition
PROCEDURE philosopher(i : INTEGER);
BEGIN
REPEAT
pickup(i); // pick up chopsticks
putdown(i); // put down chopsticks
UNTIL DoomsDay;
END;
BEGIN // main program
COBEGIN // start all five processes at once
philosopher(0); philosopher(1); philosopher(2);
philosopher(3); philosopher(4);
COEND;
END
In 1965, Edsger Dijkstra set an examination question on a synchronization problem where five computers competed for access to five shared tape drive peripherals. Soon afterwards the problem was retold by Tony Hoare as the dining philosophers problem.
This is a theoretical explanation of deadlock and resource starvation by assuming that each philosopher takes a different fork as a first priority and then looks for another.
Problem
The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things: eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right.
Illustration of the dining philosophers problem
The dining philosophers problem is sometimes explained using rice and chopsticks rather than spaghetti and forks, as it is more intuitively obvious that two chopsticks are required to begin eating.
The philosophers never speak to each other, which creates a dangerous possibility of deadlock when every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).
Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of unwarranted requests'. In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so forth, making a circular chain.
Starvation (and the pun was intended in the original problem description) might also occur independently of deadlock if a philosopher is unable to acquire both forks because of a timing problem. For example there might be a rule that the philosophers put down a fork after waiting five minutes for the other fork to become available and wait a further five minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up their left fork at the same time the philosophers will wait five minutes until they all put their forks down and then wait a further five minutes before they all pick them up again.
In general the dining philosophers problem is a generic and abstract problem used for explaining various issues which arise in problems which hold mutual exclusion as a core idea. The various kinds of failures these philosophers may experience are analogous to the difficulties that arise in real computer programming when multiple programs need exclusive access to shared resources. These issues are studied in the branch of Concurrent Programming. The original problems of Dijkstra were related to external devices like tape drives. However, the difficulties studied in the Dining Philosophers problem arise far more often when multiple processes access sets of data that are being updated. Systems that must deal with a large number of parallel processes, such as operating system kernels, use thousands of locks and synchronizations that require strict adherence to methods and protocols if such problems as deadlock, starvation, or data corruption are to be avoided.
[edit]Solutions
[edit]Waiter solution
A relatively simple solution is achieved by introducing a waiter at the table. Philosophers must ask his permission before taking up any forks. Because the waiter is aware of which forks are in use, he is able to arbitrate and prevent deadlock. When four of the forks are in use, the next philosopher to request one has to wait for the waiter's permission, which is not given until a fork has been released. The logic is kept simple by specifying that philosophers always seek to pick up their left hand fork before their right hand fork (or vice versa).
To illustrate how this works, consider the philosophers are labelled clockwise from A to E. If A and C are eating, four forks are in use. B sits between A and C so has neither fork available, whereas D and E have one unused fork between them. Suppose D wants to eat. Were he to take up the fifth fork, deadlock becomes likely. If instead he asks the waiter and is told to wait, we can be sure that next time two forks are released there will certainly be at least one philosopher who could successfully request a pair of forks. Therefore deadlock cannot happen.
[edit]Monitor solution
The example below shows a solution where the forks are not represented explicitly. Philosophers can eat if none of their neighbors are eating. This is comparable to a system where philosophers that cannot get the second fork must put down the first fork before they try again.
In the absence of locks associated with the forks, philosophers must ensure that the decision to begin eating is not based on stale information about the state of the neighbors. If philosopher B sees that A is not eating, then turns and looks at C, A could begin eating while B looks at C. This solution avoids this using a single mutual exclusion lock, not associated with the forks, but with the decision procedures that can change the states of the philosophers. This is ensured by the monitor. The procedures test, pickup and putdown are local to the monitor and share a mutual exclusion lock. Notice that processes calling WAITC(x) release the lock and wait on the variable x until another process calls SIGNALC(x) on the same variable. When the process that called WAITC resumes, it will have reacquired the lock.
Notice that this example does not tackle the starvation problem. For example, philosopher 2 can wait forever on condition variable can_eat[2] if the eating periods of philosophers 1 and 3 always overlap.
To also guarantee that no philosopher starves, one could keep track of the number of times a hungry philosopher cannot eat when his neighbors put down their forks. If this number exceeds some limit, the state of the philosopher could change to Starving, and the decision procedure to pick up forks could be augmented to require that none of the neighbors are starving.
A philosopher that cannot pick up forks because a neighbor is starving, is effectively waiting for the neighbor's neighbor to finish eating. This additional dependency reduces concurrency. Raising the threshold for transition to the Starving state reduces this effect.
[edit]Example Solution
Example Solution written in Pascal (using Monitor synchronization)
PROGRAM d_p;
CONST
DoomsDay = FALSE;
MONITOR dining_philosophers; // Start of monitor declaration
CONST
Eating = 0;
Hungry = 1;
Thinking = 2;
VAR
i : INTEGER; // init loop variable
state : ARRAY [0..4] OF INTEGER; // Eating, Hungry, Thinking
can_eat : ARRAY [0..4] OF CONDITION; // one for each Philosopher
// place for Hungry Ph to wait until chopsticks become available
PROCEDURE test(k : INTEGER);
BEGIN
IF (state[k] = Hungry)
AND (state[(k+4) MOD 5] <> Eating)
AND (state[(k+1) MOD 5] <> Eating) THEN
BEGIN
state[k] := eating;
SIGNALC(can_eat[k]); // End the wait if any
END;
END;
PROCEDURE pickup(i: INTEGER);
BEGIN
state[i] := Hungry;
WRITELN('philosopher ',i,' hungry');
test(i); // are my neighbors eating?
IF state[i] <> Eating THEN
WAITC(can_eat[i]); // wait until they finish eating
WRITELN('philosopher ',i,' eating');
END;
PROCEDURE putdown(i : INTEGER);
BEGIN
state[i] := Thinking;
WRITELN('philosopher ',i,' thinking');
test( (i+4) MOD 5); // give left neighbor chance to eat
test( (i+1) MOD 5); // give right neighbor chance to eat
END;
BEGIN // initialize monitor
FOR i := 0 TO 4 DO state[i] := Thinking;
END; // end of monitor definition
PROCEDURE philosopher(i : INTEGER);
BEGIN
REPEAT
pickup(i); // pick up chopsticks
putdown(i); // put down chopsticks
UNTIL DoomsDay;
END;
BEGIN // main program
COBEGIN // start all five processes at once
philosopher(0); philosopher(1); philosopher(2);
philosopher(3); philosopher(4);
COEND;
END
Subscribe to:
Posts (Atom)