WELCOME TO TECHNOLOGY FOR ALL WEB SITE
Home Page Discussion Group Request Form About Us Search Topic Dining Philosophers

MAIN DIRECTORY

Home
About Us
Discussion
 FAQ
Software Info
Computer Jobs
 Request Form

Feedback

 

The Smart Dining Philosophers

Abstract

An operating system that provides service to users is called server. A process that gets service from server is called client. Most client and servers normally all run the same microkernel, with both the clients and servers running(Andrew S. Tanenbaum p.51). A server can offer services to multiple clients. When many clients are accessing information from one server they then share resource. When clients are trying to access to a single resource concurrently there could be an opportunity for a problem or a deadlock.

The problem is motivated by the complex issues of how to assign a resource to each clients, which they need in order to do their jobs. In other words, how to manage shared resource allocation, which leads us to dining philosopher scenarios.

Introduction

This article will discuss the following topics and findings in detail:

  • What are dining philosophers?
  • What is the problem with dining philosophers?
  • What are the possible solutions to dining philosophers problems?
  • What is our evaluation and conclusion to the dining philosopher problem?

What are dining philosophers?

 

Dining philosophers are five clients sitting around a circular table and there is a big bowl of spaghetti at the center of the table. There are five forks placed in between each philosopher. When one philosopher gets hungry, he/she then grabs the fork to his/her immediate left and immediate right and starts to chaw. Once he/she is full, the philosopher then places the forks back and goes into the usual thinking mode.

The above scenario of dining philosophers is the best scenario. The dining philosophers are often used to illustrate various problems that can occur when many synchronized threads are competing for limited resources. The basic idea behind dining philosopher scenario is that if a concurrent activity always does what seems best for itself or what seems to be the right thing for itself in a shared resources scenario, the result can be chaos.

The five philosophers lead a simple life: they spend their time thinking and/or eating. Of course, a philosopher who wishes to eat must first have in hand two forks, and the etiquette of the boarding house requires that the hungry philosopher pick up his forks in a seemly manner, one at a time. Indeed, rude behavior of any sort is frowned upon: there can be no grabbing of two forks at once, no passing of forks around the table, and no eating with fingers, and once a philosopher picks up a fork he/she must eat before putting the fork back down.

Several things are clear about this peculiar lifestyle. At any given moment, no more than two of the five philosophers may eat. The arrangement of the forks around the table insures that when one philosopher is eating, neither of the philosophers seated next to him can pick up enough forks to begin eating.

Naturally, the philosophers have their share of problems. If each of them picked up a single forks and refused to let it go, no one at the table would be able to eat. In the computer trade, this situation is called a "deadlock".

What is the problem with dining philosophers

But even after we set up the rules and manner to abide by in order to avoid deadlock, the philosophers face other problems. For example, how can the five forks be shared so that no one at the table is starved to death? More information about the philosophers themselves is required for a solution to this problem. Are the philosophers all the same size? Is their nutritional requirements the same or does it vary? How well do they perceive and express their own needs?

These problems with dining philosophers omit an important fact that a philosopher never talks to another philosopher. The typically projected scenario is that if all the philosophers grab their forks on the left simultaneously (which can happen by any chance) none of them will be able to grab from their right. And with their one-track(eat) mind-set they will forever keep waiting for the missing right fork to come back to the table. This will cause them to starve themselves to death.

What are the possible solutions to dining philosophers’ problem?

There is a proof that no deterministic distributed and symmetric deadlock-free solution exists for the Dining Philosophers Problem. This is due to the existence of an adversary scheduler that can continually prevent the philosophers in their attempts to reach agreement on who is to eat next, thereby leading to deadlock, that is, a situation where all five philosophers starve to death.

For example, under the influence of such an adversary scheduler, the philosophers could become hungry simultaneously and pick up their right fork again in synchrony. Because of the symmetry and the fact that each philosopher's behavior is strictly deterministic, they have no choice but to put down their forks and try again. The adversary scheduler can cause this scenario to reoccur without end resulting in deadlock.

The introduction of randomness into the behavior of philosophers breaks the above symmetry and provides a solution to the problem. The simple essential use of randomization is in whether a philosopher attempts to first obtain the left fork or the right.

We have assumed that the lengths of thinking and eating periods of the philosophers vary; this is simulated by using random delays. For this reason it is clear that although the deterministic protocol is not as efficient as the probabilistic one, it is working because the adversary scheduler does not force the philosophers to pick up their right fork simultaneously; in other words, the scheduler has the effect of making the philosophers behave asynchronously. In this way, despite the fact that it is possible for deadlock, it is unlikely.

In the philosophers' case, preventing deadlock is relatively easy. They must simply learn and live by certain rules and guidelines: "Never pick up one fork unless both your left and right forks are available" or "If you have one fork in hand and the other is not available, put the first fork back on the table and wait until the other fork is available".

By treating with care the business of picking up forks, the philosophers avoid deadlock. No one can allow himself to be distracted while picking up a fork or to hold on to one forks while there is no prospect of picking up another.

A solution to the Dining Philosophers Problem must be deadlock free (if at any time there is a hungry philosopher then eventually some philosophers will eat), and lockout free (every hungry philosopher eventually gets to eat).

In a perfect world, each philosopher will abide by the rule, but that occasionally case could cause permanent damage to a philosopher depending on the length of the starvation. We believe that if each philosopher is courteous of each other, then they will limit the length of time they are eating based on the need of the next philosopher.

Round

Phil1

Phil2

Phil3

Phil4

Phil5

1

EAT

THINK

EAT

THINK

THINK

2

THINK

EAT

THINK

EAT

THINK

3

THINK

THINK

EAT

THINK

EAT

Round 1 Round 2 Round 3

Another solution will be to set up a mediator that each philosopher goes through to ask permission to use the forks. By setting up the mediator, we are addressing the possibility of one of the philosopher hogging to one fork for a long time while waiting for the another fork to be released. The mediator will allow the philosopher to take the fork only after both the forks are available. The mediator will also allow the philosopher to use the fork based on the critical need of it. The mediator will if for example, philosopher 1 is hungry and want to eat so badly. Then the mediator will let philosopher 1 eat and can also decide whether it is philosopher 3 or philosopher 4 that will eat with philosopher 1 based on immediate need and criticality of the philosophers. The mediator will be the judge on who needs to eat and how long has the philosopher been waiting for the forks to eat with. This will reduce the chance of dead lock and possible starvation.

 

The following is the headerfile of dining philosopher.

/* philtable.h -- Here are the calls we can make on the monitor

* representing the dining philosophers

*/

void * tableinit(void *(*)(int *)); /* argument is the function*/

/*representing the philosopher*/

void printstate(void);

void pickup(int k);

void putdown(int k);

The following is the function dining philosopher calls.

/* philtable.c */

#include <sys/types.h>

#include <pthread.h>

#define PHILNUM 5

typedef enum {thinking, hungry, eating} philstat;

typedef struct tablestruct {

pthread_t t[PHILNUM];

int self[PHILNUM];

pthread_mutex_t mutex;

pthread_cond_t condition[PHILNUM];

philstat status[PHILNUM];

} table;

table * tab;

void printstate(void){

/* Prints out state of philosophers as, say, TEHHE, meaning */

/* that philosopher 0 is thinking, philosophers 1 and 4 are eating,

and*/

/* philosophers 2 and 3 are hungry.*/

static char stat[] = "THE";

int i;

for (i=0; istatus)[i]);}

printf("\n");

}

int test (int i) {

if (

((tab->status)[i] == hungry) &&

((tab->status)[(i+1)% PHILNUM] != eating) &&

((tab->status)[(i-1+PHILNUM)% PHILNUM] != eating)) {

(tab->status)[i] = eating;

pthread_cond_signal(&((tab->condition)[i]));

return 1;

}

return 0;

}

void pickup(int k) {

pthread_mutex_lock(&(tab->mutex));

(tab->status)[k] = hungry;

printstate();

if (!test(k)) {

pthread_cond_wait(&((tab->condition)[k]), &(tab->mutex));}

printstate();

pthread_mutex_unlock(&(tab->mutex));

}

void putdown(int k) {

pthread_mutex_lock(&(tab->mutex));

(tab->status)[k] = thinking;

printstate();

test((k+1)%PHILNUM);

test((k-1+PHILNUM)%PHILNUM);

pthread_mutex_unlock(&(tab->mutex));

}

table * tableinit(void *(* philosopher)(void *)) {

int i;

tab = (table *) malloc (sizeof(table));

if(pthread_mutex_init(&(tab->mutex), NULL) != 0) {

perror("pthread_mutex_init");

exit(1);}

for (i=0; iself)[i] = i;

(tab->status)[i] = thinking;

if(pthread_cond_init(&((tab->condition)[i]), NULL)

!= 0) {

perror("pthread_cond_init");

exit(1);}

}

for (i=0; it)[i]),NULL,

philosopher, &((tab->self)[i]))!= 0) {

perror("pthread_create");

exit(1);}

}

return tab;

}This is the dining philosopher main file:

/* philmain.c */

#include <stdio.h>

#include "philtable.h"

void * philosopher(int * a);

int main(void) {

void * tab = tableinit(philosopher);

sleep(60); /* Wait a while then exit */

printf("WE ARE DONE\n");}

void * philosopher(int * who) {

/* For simplicity, all philosophers eat for the same amount */

/* of time and think for a time that is simply related */

/* to their position at the table. The parameter who identifies */

/* the philosopher: 0, 1, 2, .. */

while (1){

sleep((*who)+1);

pickup((*who));

sleep(1);

putdown((*who));}

return who;

}

Evaluation and Conclusion

All our attempts so far to solve the dining philosopher problem have one thing in common, all the philosophers share some mechanism to facilitate their synchronization. There is a shared process containing a single input statement, which services all the calls by philosophers wishing to eat . It is debatable, but we find the condition synchronization of the dining philosopher problem most naturally expressed as a problem that is bound to happen. This is because the solution makes no reference whatever to forks, but only to each philosopher's right to eat. Philosophers can always wait to see if both the forks are available before grabbing one, and soon after eating release the fork for the next hungry philosopher to eat next.

If all philosophers are smart and they abide by the rules, then it will be dead lock free and a perfect place for dining philosophers.

 
Reference:

Andrew S. Tannenbaum. "Distributed Operation System" 1995.

H.M. Deitel / P.J. Deitel "How To Program C++" 1994.

W. Richard Stevens "TCP/IP Illustrated, Volume 3: TCP for transactions, HTTP, NNTP, and the UNIX Domain Protocols" 1996

Back to Top


HOME |  DISCUSSION | ABOUT US  |  RESUME SUBMISSION  |  BOOK REVIEW  | Computer Jobs | Software Info | Tech-Support Directory for Computer Companies

Copyright © 1999 www.technologyforall.com. All rights reserved.
Revised: November 28, 2000