Dining Philosophers program

Sam · #1 12-Feb-2004, 10:19

I'm face a problem when doing this program.Can any one giving me some instruction??

There are N philosophers seated at a circular table, sharing chopsticks, so that no two adjacent philosophers may eat at the same time. Each philosopher is modeled by a process executing the following code:

CPP / C++ / C Code:

void philosopher(int i)
{
while(1){
think();
get_hungry_and_try_to_eat(i);
};
}

I need do write the routine get_hungry_and_try_to_eat() and think().And the routine must obtain a chopstick from the left and right side.Once it has both chopsticks, it should eat() and then release them. Since the philosophers are concurrent threads/process, any access they make to common data must be appropriately protected. This program also need too avoid busy-waiting.

I think a few days,but still can't get the concept.Any one can help me......Thanks very very much.....

Need help poor person.

dsmith · #2 12-Feb-2004, 10:35

Hi Sam. I know that you may disagree, but what a cool problem!

I am thinking a doubly-linked list representing the philosophers is the way that I would go, then to access the adjacent philosophers would simply be a call to prev and next. An array would work as well, but not as dynamic and without the end looping to create the "circle"

A couple of questions come to mind:

How many sets of chopsticks are there?
Do you have to get one from the left and one from the right to eat?
What is supposed to happen when a philosopher thinks?

Anyway, I would love to see this when you get it done. If you are struggling, you should try to set up your structures, etc. and post some code if you are struggling with it so that the people here can help with the specific problems.

BTW - You can post highlighted c code by using [C] and [/C]. I editted your post to do this.

Sam · #3 13-Feb-2004, 09:37

Thank Dsmith

Refer to your question, let said now we hv 5 people then we only hv 5 chopsticks,in both left and right.Not 5 set.That mean N people then got N Chopsticks.

You right,they have to get one from the left and one from the right to eat.But each time,only one ppl can eat, other ppl hv to wait after it finish eating and pass the chopsticks again to other ppl.

Think() is actually the philosopher can do anything.LIke maybe they eating, hungry , waiting their turn to eat or etc.

However thank for you adviser,if you got any idea,you are welcome to tell me.10

dsmith · #4 13-Feb-2004, 10:15

Hi Sam. I think I understand a bit better now. Each philosopher has a chopstick, but he can not use it to eat. He has to obtain the chopsticks from his neighbor. And according to the original post, philosophers seated next to each other can not eat at the same time.

I still like the doubly-linked array because it is dynamic. You can decide how many philosophers you have at run time and it would be easy to add more as you go on. But the way that you have written your philosopher function makes it appear that you are going to use an array, which will work.

I would define a philosopher by a structure like:

CPP / C++ / C Code:

struct phil{
   int chopstick;
   int eating;
}group[N];

Each of these is a flag. Each philosopher should be initialized to have a chopstick (ie chopstick = 1) and to not be eating (ie eating = 0).

Then to find out if a philosopher can eat would be something like:

CPP / C++ / C Code:

if( (group[i-1].chopstick) && (!group[i-1].eating) )
  if( (group[i+1].chopstick) && (!group[i-1].eating) ){
     group[i].eating = 1;
     group[i-1].chopstick = 0;
     group[i+1].chopstick = 0;
   }

Then when he is done eating

CPP / C++ / C Code:

group[i].eating = 0;
group[i+1].chopstick = 1;
group[i-1].chopstick = 1;

You would have to check your bounds in the above examples. So maybe you could track N (number of philosophers starting at 0) as a global and then in your try_to_eat function, start it with

CPP / C++ / C Code:

int left;
int right;

left = i -1;
if(left<0)
   left = N;
right = i+1;
if(right>N)
  right = 0;

if( (group[left].chopstick) && (!group[left].eating) )
  if( (group[right].chopstick) && (!group[left].eating) ){
   ....

Hope this helps. I would appreciate you posting back with this when you get it done. I would like to see how it ends up...

WaltP · #5 13-Feb-2004, 13:43

I just realized that the following code:

CPP / C++ / C Code:

left = i -1;
if (left < 0)
    left = N-1;
right = i+1;
if (right >= N)
    right = 0;

can be shortened to:

CPP / C++ / C Code:

left  = (i+N-1) % N;
right = (j+N+1) % N;

to alleviate the expense of the if's! After 20 years of programming, you'd think I would have realized this before!

Also, note a couple of corrections in the original code.

dsmith · #6 13-Feb-2004, 14:56

That is a great math trick Walt! I tested it because I didn't quite follow the logic. I would never had got that in a million years. If you told me to write that as a one liner I would have written:

CPP / C++ / C Code:

left = (i==0)?N-1:i-1;
right = (i==(N-1))?0:i+1;

Yours is much cleaner. I am going to have to remember that one!

Sam · #7 17-Feb-2004, 05:41

Thank dsmith and WaltP, i hv finish the part of the program. But still encounter a problem, so any one of you can help me to solve it??
Thanky.Following is the code of the program, still got some bug inside :

CPP / C++ / C Code:

#include <stdio.h>
#include <math.h>

/* program diningphilosophers; */

/* Global Structures  */
typedef struct{
   int chopstick;
   int eating;
} PHIL;

void think ();
void eat ();
void wait (PHIL group[], int i);
void signal (PHIL group[], int i);
void get_hungry_and_try_to_eat (int i);
void philosopher (int number);

void think () {
	printf ("I'm hungry, I want to eat...\n\n");
}

void eat () {
	printf ("Yummy, yummy...\n\n");
}

void wait (PHIL group[], int i) {
	int left;
	int right;

	left = i - 1;
	right = i + 1;

	if (left < 0)
		left = i;

	else if (right > i)
		right = 0;

	if ((group[left].chopstick) && (!group[left].eating)) {
		if ((group[right].chopstick) && (!group[left].eating)) {
			group[i].eating = 1;			// philosopher is eating
			group[left].chopstick = 0;		// release left chopstick
			group[right].chopstick = 0;		// release right chopstick
		}
	}
}

void signal (PHIL group[], int i) {
	group[i].eating = 0;
	group[i+1].chopstick = 1;
	group[i-1].chopstick = 1;
}

void get_hungry_and_try_to_eat (int i) {

	PHIL philAry [N];

	wait (philAry [i], i);
	wait (philAry [(i+1) mod i], i);

	eat ();

	signal (philAry [(i+1) mod i], i);
	signal (philAry [i], i);
}

void philosopher (int number) {
	while (1) {
		think ();
		get_hungry_and_try_to_eat (number);
	}
}

void main () {
	int total, count;

	printf ("How many philosophers are eating?\n\n>>  ");
	scanf ("%d", &total);

	for (count = 0; count < total; count++) {
	}
	printf ("\n %d philosopher(s) entered dining room...\n\n");
	philosopher (total);
}

dsmith · #8 17-Feb-2004, 09:18

Hi Sam. I haven't gone through the entire logic yet, but there are a few things that are holding it from compiling:

Here you use a Constant N, but it is never defined. N needs to be your total value. Either you can pass this (probably best) or set it to a global.
CPP / C++ / C Code:
PHIL philAry [N];
Here you pass a single element of the array, when your function wants the entire array.
CPP / C++ / C Code:
wait (philAry [i], i); //Passing only one element of the array. void wait (PHIL group[], int i) //Looking for the entire array.
Also, try to name this function something other than wait as this is a standard library function.
Modulus division in C is done using %
CPP / C++ / C Code:
signal (philAry [(i+1) mod i], i);
If you want to do it as shown above, place a #define at the top of your program
CPP / C++ / C Code:
#define mod %

Your function signal has the same problem as wait

CPP / C++ / C Code:

signal (philAry [i], i);                   //Passing single element of array
void signal (PHIL group[], int i) {   //Wants the whole array.

It appears that you want to pass the entire array. Your call should be:

CPP / C++ / C Code:

signal(philAry, i);

Try to get this to compile and see what you come up with. I don't know if I 100% follow your logic yet. Get your code to compile and repost it. If it doesn't function like you expect, I will take a closer look.

Sam · #9 18-Feb-2004, 20:21

Dear dSmith,

Hello. Below is my developed program but got some problems. Can you help me to solve them?

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 100

/* Global Structures  */
typedef struct{
   int chopstick;
   int eating;
} PHIL;

PHIL philAry [N];
PHIL philWait [N];

void think (int i);
void eat (int i);
void waitLeft (int i);
void waitRight (int i);
void check (int i);
void finish (int i);
void get_hungry_and_try_to_eat (int philoNo, int totalPhilo);
void philosopher (int amount);
void running(int waitTime);

void think (int i) {
	printf ("\nPhilosopher no. %d is hungry...\n", i);
}

void eat (int i) {
	printf ("\nPhilosopher no. %d is eating...\n", i);
	running (rand());
}

void finish (int i) {
	printf ("\nPhilosopher no. %d stops eating ", i);
	printf ("and releases chopsticks...\n");

	philAry[i].eating = 0;			// Philosopher stops eating
	philAry[i+1].chopstick = 1;		// Right philosopher takes back chopstick
	philAry[i-1].chopstick = 1;		// Left philosopher takes back chopstick
}

void waitLeft (int i) {
	printf ("\nLeft chopstick is not available, so ");
	printf ("philosopher no. %d has to wait...\n", i);

	philWait[i + 1].chopstick = 0;
}

void waitRight (int i) {
	printf ("\nRight chopstick is not available, so ");
	printf ("philosopher no. %d has to wait...\n", i);

	philWait[i].chopstick = 0;
}

void check (int i) {
	for (int count = 0; count < i; count ++) {
		if (!philWait[count].chopstick && philAry[count].chopstick) {
			printf ("\nPhilosopher no. %d gets both chopsticks.", i-1);
			eat (i-1);
			finish (i-1);
			philWait[count].chopstick = 1;
		}
	}
}

void get_hungry_and_try_to_eat (int philoNo, int totalPhilo) {

	int left;
	int right;

	left = philoNo - 1;
	right = philoNo + 1;

	if (left < 0)
		left = totalPhilo;

	else if (right > totalPhilo)
		right = 0;

	if ((philAry[left].chopstick) && (!philAry[left].eating)) {
		printf ("\nPhilosopher no. %d gets left chopstick...", philoNo);
		philAry[left].chopstick = 0;

		if ((philAry[right].chopstick) && (!philAry[left].eating)){
			printf ("\nPhilosopher no. %d gets right chopstick...", philoNo);

			philAry[right].chopstick = 0;
			philAry[philoNo].eating = 1;		// philosopher is eating

			eat (philoNo);			
			finish (philoNo);

			philAry[left].chopstick = 1;		// Left philosopher takes back chopstick
			philAry[right].chopstick = 1;		// Right philosopher takes back chopstick
		}

		else {
			waitRight (philoNo);
			philAry[philoNo].eating = 0;
		}
	}

	else {
		waitLeft (philoNo);
		philAry[philoNo].eating = 0;
	}
}

void philosopher (int amount) {

	int randPhilo;

	int count = amount;

	while (count > 0) {
		running (rand());
		randPhilo = rand() % amount;
		think (randPhilo);
		check (amount);
		get_hungry_and_try_to_eat (randPhilo, amount);
		count--;
	}

	check (amount);
	printf ("\n");
}

void running(int waitTime)
{
	clock_t Goal;
	Goal=CLOCKS_PER_SEC*waitTime/1000+clock();
	while(Goal>clock());
}

void main () {
	int total, count;

	printf ("How many philosophers are eating?\n\n>>  ");
	scanf ("%d", &total);

	if (total != 0) {
		for (count = 0; count < total; count++){
			philAry[count].chopstick = 1;
			philWait[count].chopstick = 1;
			philAry[count].eating = 0;
		}

		philosopher (total);
	}

	else {
		printf ("There is no any philosopher eating.\n\n");
	}	
}

Actually this problem I need to use semaphore and threads to solve it but i didn't. I just use random time to control the process. And everytime when I run this program, for example I key in 2 or 4 philosophers, don't know why the first philosopher who will eat loses his right chopstick. But if I key in other values like 5 or 6, it won't come out such problem. While key in other larger values, it will say some of the philosophers' chopsticks are not available at the run time but actually they are supposed be available. Can you help me find out why? I think it is the rand() problem, is it?

Besides since I must define the N value, so I define 100. But when the program starts, I let the user keys in the number of philosophers who will eat together. Does it make sense? Can I do like such way?

Anyway, I'm appreciate for your help!! Thanks a lot!! May you have a nice day! Bye!

dsmith · #10 19-Feb-2004, 08:46

Quote:

Originally Posted by Sam

Actually this problem I need to use semaphore and threads to solve it but i didn't. I just use random time to control the process.

If this is for an assignment, you probably should look into using semaphores. I found a pretty good lecture on semaphores/threads with samples here. It is going to change the dynamic and structure of your program almost completely.

Quote:

Besides since I must define the N value, so I define 100. But when the program starts, I let the user keys in the number of philosophers who will eat together. Does it make sense? Can I do like such way?

I would use dynamic memory allocation for this instead of arrays. So define your philarray as a pointer and then allocate it after you ask for the number of philosophers. And then access it with a pointer.

CPP / C++ / C Code:

PHIL*  philAry;                             //Variable definition
...
philAry = malloc(sizeof(philAray) * total);    //Memory Allocation
...
(philAry+count)->eating = 0;        //Data access

If this *HAS* to be done with semaphores you should really read up on the post above and do some of your own testing. If you want to work with what you have, let me know and I will take a look at some of the other errors you are getting.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 08:44
Type casts ?	kai85	C++ Forum	12	23-Jun-2005 13:04
[TUTORIAL] Calling an external program in C (Linux)	dsmith	C Programming Language	4	22-Apr-2005 14:30
fltk-2.0 cvs	Plumb	FLTK Forum	20	13-Nov-2004 08:10
Need help with a C program (Long)	McFury	C Programming Language	3	29-Apr-2004 21:06

Dining Philosophers program

Thank Dsmith

ahaaaaa!

Program with bug(s)... Need help!!