Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Regarding Dining Philosophers Problem (http://www.go4expert.com/forums/regarding-dining-philosophers-t9368/)

joeserhal 16Mar2008 07:52

Regarding Dining Philosophers Problem
 
Hi there,
I'm trying to implement the Dining Philosophers problem, using a virtual distributed system, in which a host creates a number of virtual sites and communication means between them (message passing).
Hence, every site created should be thought of a "philosopher", and each will try to pick the forks (if available).
I have already implemented the whole Virtual Distributed System, and communications means, I am able to create the sites. But I need a way to allow the created "philosophers" to execute a the same time, trying to pick the forks...i.e, I don't want it to happen in sequential way (loop iteration, one after the other), it needs to be like some kind of a race, the one who gets there first can pick up the fork...Do you know what i mean??

Anybody has any ideas??
Thanks.

joeserhal 23Mar2008 11:13

Re: Regarding Dining Philosophers Problem
 
I have finally written the code to solve the Dining philosopher problem using a virtual distributed system with message passing (as a mean of communication between each created site). However, when i run the program, it hangs.
Anybody can help me out with it?

The following is the code in which sites are created and the dining philosopher problem is handled using semaphores. I can successfully create sites ( I have tested it) so i know the problem comes from the Philo() function.
Code:

#include <stdio.h>
#include <time.h>
#include "vds.h"
#include "comm.h"
#include "queue.c"
#include <stdlib.h>
#include <unistd.h>

#define MEALS 10
#define EATING 0
#define THINKING 1
#define HUNGRY 2
#define THINK_TIME 4
#define EAT_TIME 4
#define N_PHIL 5

int chopstick[5] = {1};
int mutex = 1;
Queue block_mutex;
Queue block_chopstick[5];

void test();
void Philo();
void think(int ph_id);
void eat(int ph_id,int meal);
void put_forks(int ph_id);
void get_forks(int ph_id);
int Request(int chopstick,int philosopher);
void Release (int chopstick,int philosopher);
void sem_wait(int chopstick_num, char* type);
void sem_signal(int chopstick_num, char* type);


int main(argc, argv)
int argc;
char *argv[];
{
        int  sid;


        /*
        *
        * Site Initialization
        *
        *
        */
        setbuf( stdout, NULL ); /* no output buffering */

        if (argc != 4) {
                fprintf(stderr, "Usage: %s <SID> <NS HOST> <NS PORT>\n", argv[0]);
                exit(ERROR);
        }

        if (SiteSetup(atoi(argv[1]), argv[2], atoi(argv[3])) == ERROR) {
                fprintf(stderr, "SiteInit(%d) failed.\n", atoi(argv[1]));
                exit(ERROR);
        }

        printf("I am site %d. I am up and running\n", atoi(argv[1]));


        Philo();        /* This is a simple test routine. You should comment it out */

        /*
        *
        * Lab 2 Protocol
        *
        * Philo_Init()
        * while ( 1 ) {       
        *  Philosophers simulation code
        *
          * }
        *
        */



        /*
        *
        * Site Termination
        *
        *
        */
        SiteExit();
}


void Philo()
{
    char *MSG = (char *)malloc(MAX_MSG_LEN);
    int i, sender;
    char delims[] = " "; 
    char *result = NULL; 
     
    block_mutex = CreateQueue(5);
   
    for(i=0;i<5;i++)
        block_chopstick[i] = CreateQueue(2);
   
    srand(MySID);
    if(MySID>=1 && MySID<=5)
    {
      while(1)
      {
              for (i=0;i<MEALS;i++)
              {
                think(MySID);
                get_forks(MySID);
                eat(MySID,i);
                put_forks(MySID);
              }
              printf("Philosopher %d's thread has exited\n",MySID);
        }   
    }
    else
    if(MySID == 6)  //if I am the site responsable for synchronization
    {
      //Do the work for the semaphores, increments and decrements
      Receive(MSG, &sender);
      result = strtok( MSG, delims );
      if(strcmp(result,"Wait")==0)  //check if the message received corresponds to a sem_wait
      {
        result = strtok( NULL, delims );
        if(strcmp(result,"chopstick")==0) //check if the semaphore needed to be handled is "chopstick"
        {
            result = strtok( NULL, delims );
            for(i=0;i<5;i++)
            {
                if(i == atoi(result))
                {
                  chopstick[i]--;
                  if(chopstick[i]<0)
                    Enqueue(sender,block_chopstick[i]);//BLOCK the philosopher, put on waiting queue of this chopstick
                  else
                      Send("OK", sender);
                  }
            }
        }
        else
        if(strcmp(result,"mutex")==0) //check if the semaphore needed to be handled is "mutex"
        {
                  mutex--;
                  if(mutex<0)
                    Enqueue(sender,block_mutex);//BLOCK the philosopher, put on waiting queue -> mutex[sender]=0
                  else
                      Send("OK", sender);
        }
      } //end of sew-wait handling
      else 
      if(strcmp(result,"Signal")==0)  //check if the message received corresponds to a sem_signal
      {
        result = strtok( NULL, delims );
        if(strcmp(result,"chopstick")==0) //check if the semaphore needed to be handled is "chopstick"
        {
            result = strtok( NULL, delims );
            for(i=0;i<5;i++)
            {
                if(i == atoi(result))
                {
                  chopstick[i]++;
                  if(chopstick[i]<=0)
                    Dequeue(block_chopstick[i]);//NBLOCK philosopher waiting on this chopstick from the blocking queue of this chopstick
                  Send("OK", sender);
                  }
            }
        }
        else
        if(strcmp(result,"mutex")==0) //check if the semaphore needed to be handled is "mutex"
        {
                  mutex++;
                  if(mutex<=0)
                    Dequeue(block_mutex);//NBLOCK philosopher waiting on mutex from the blocking queue of mutex
                  Send("OK", sender);
        }
      }  //end of sem_signal handling         
   
   
    }//end of job for site responsable for synchronization
   
}
 
 
 
int Request(int chopstick,int philosopher)
{
        return 1;
}

void Release (int chopstick,int philosopher)
{
}
 
void sem_wait(int chopstick_num, char* type)
{
    char *MSG = (char *)malloc(MAX_MSG_LEN);
    char* string;
    int i,sender=6;
    if (strcmp(type,"chopstick")==0) //if dealing with semaphore "chopstick"
    {
          for(i=0;i<N_PHIL;i++)
          {
            if(i==chopstick_num)
            {
                sprintf(string, "Wait %s %d", type, i);
                Send(string, 6);
            }
          }
    }
    else
    if(strcmp(type,"mutex")==0)  //if dealing with semaphore mutex
    {
                sprintf(string, "Wait mutex"); 
                Send(string, 6);
    } 
    Receive(MSG, &sender);
}


void sem_signal(int chopstick_num, char* type)
{
    char *MSG = (char *)malloc(MAX_MSG_LEN);
    char* string;
    int i,sender=6;
    if (strcmp(type,"chopstick")==0) //if dealing with semaphore "chopstick"
    {
          for(i=0;i<N_PHIL;i++)
          {
            if(i==chopstick_num)
            {
                sprintf(string, "Signal %s %d", type, i);
                Send(string, 6);
            }
          }
    }
    else
    if(strcmp(type,"mutex")==0)  //if dealing with semaphore mutex
    {
                sprintf(string, "Signal mutex"); 
                Send(string, 6);
    } 
    Receive(MSG, &sender);
}


     
void think(int ph_id)
{
  int wait_time;
  wait_time=rand()%THINK_TIME+1;
  printf("\tPhilosopher %d is thinking for %d seconds.\n",ph_id,wait_time);
  sleep(wait_time);
}


void get_forks(int ph_id)
{
  int left=0,right=0;
  while(!left){
          sem_wait(-1,"mutex");
        left=Request(ph_id-1,ph_id);
        sem_signal(-1,"mutex");
        if (!left)
          sleep(1);
  }
  sem_wait(ph_id-1,"chopstick");
  while(!right){
        sem_wait(-1,"mutex");
        right=Request((ph_id)%N_PHIL,ph_id);
        sem_signal(-1,"mutex");
        if (!right)
        {
          sleep(1);
        }
  }
  sem_wait((ph_id)%N_PHIL,"chopstick");
}


void eat(int ph_id,int meal)
{
  int wait_time;
  wait_time=rand()%EAT_TIME+1;
  printf("\tPhilosopher %d is eating meal %d for %d seconds.\n",ph_id,meal+1,wait_time);
  sleep(wait_time);
}


void put_forks(int ph_id)
{
  int i;
  sem_wait(-1,"mutex");
  Release(ph_id-1,ph_id);
  Release((ph_id)%N_PHIL,ph_id);
  sem_signal(ph_id-1,"chopstick");
  sem_signal((ph_id)%N_PHIL,"chopstick");
  sem_signal(-1,"mutex");
}



void test()
{
        /*
        * To test: read, understand, then issue the command:
          * vds <filename>, where <filename> is in local dir and
        * contains:
        *
        * ------ start file
        * 3
        * 1 sand
        * 2 sand
        * 3 sand
        * <your vds bin path>
        * ------ end file
        *
        */

    char *MSG = (char *)malloc(MAX_MSG_LEN);
        int sender;

        sleep(3);
        if (MySID==3)  {
                sleep(3);
                Send("Hi, I am 3 sending you my greetings\n\0", 2);
        }
        else if (MySID==2) {
                Send("Hi, I am 2 sending you my greetings\n\0", 3);
        }

        if(MySID==3 || MySID==2) {
                Receive(MSG, &sender);
                printf("Site %d: Received this msg fm site %d: %s\n", MySID, sender, MSG);
        }
       
}


The output it produces is:
http://img186.imageshack.us/img186/8...tputxm7.th.jpg

it doesnt seem to execute the getforks(),eat(), putforks() functions....

lead.smart34 25Mar2008 15:22

Re: Regarding Dining Philosophers Problem
 
can you please tell what exactly you need


All times are GMT +5.5. The time now is 05:58.