Online Labs

Dining Philosopher’s Problem

The 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 philosopher, and as such, each philosopher has one fork to his or her left and one fork to his or her right. As spaghetti is difficult to serve and eat with a single fork, it must be assumed that in order for a philosopher to eat, the philosopher must have two forks. In the case of the dining philosopher, the philosopher can only use the fork on his or her left or right.

Illustration of the dining philosophers problem

 

 

 

14

 
 

 

In some cases, the dining philosophers problem is explained using rice and chopsticks as opposed to spaghetti and forks, as it is generally easier to understand that two chopsticks are required, whereas one could arguably eat spaghetti using a single fork, or using a fork and a spoon. In either case, only one instrument (fork or chopstick) can be picked up at a time, and the philosopher must have two instruments in order to eat.

 

23

The philosophers never speak to each other, which creates a dangerous possibility of deadlock in which 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 ungranted 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 due to a timing issue. 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.

The lack of available forks is an analogy to the locking of shared resources in real computer programming, a situation known as concurrency. Locking a resource is a common technique to ensure the resource is accessed by only one program or chunk of code at a time. When the resource the program is interested in is already locked by another one, the program waits until it is unlocked. When several programs are involved in locking resources, deadlock might happen, depending on the circumstances. For example, one program needs two files to process. When two such programs lock one file each, both programs wait for the other one to unlock the other file, which will never happen.

 

Algorithm

 

* The algorithm for the process is……….

                                                1.Start.

                                                2.Initialise the thread variables as required.

                                                3.Create the threads representing philosophers.

                                                4.Wait until the threads finishes execution.

                                                5.Stop.

      The algorithm for the philosopher is as……….

                                                1.Start.

                                                2.Wait for the left fork/spoon.

                                                3.Wait for the right fork/spoon.

                                                4.Start eating.

                                                5 Release the left fork/spoon.

                                                6.Release the right fork/spoon.

                                                7.Stop.

 

Program

 

  /* Program to implement the solution to dinning philosophers’ problem.

 

   * This program uses five thread functions as five philosophers.

 

   * The spoons or forks are represented with five semaphore variables.

 

   * To use shared memory just include the code after the sem_wait() in each thread.

 

   * To compile use ‘cc diningphilosopher.c -lpthread’.

 

   * To run ‘./a.out’.

 

 

                                                //inculsion         

#include<stdio.h>

#include<pthread.h>

#include<semaphore.h>

                                                //macro definition

#define cls() printf(“33[H33[J”)

#define EATINGTIME 1

                                    //function prototype for the thread function.

void * philosopher1();

void * philosopher2();

void * philosopher3();

void * philosopher4();

void * philosopher5();

                                    //global decalration of semaphore variables.

sem_t sem15,sem12,sem23,sem34,sem45;

                                    //global variable to control the execution of main.

int end=0;

 

int main()

{

 char a[2];

 

 pthread_t t1,t2,t3,t4,t5;

 pthread_attr_t at1;

 

 pthread_attr_init(&at1);

 pthread_attr_setdetachstate(&at1,PTHREAD_CREATE_DETACHED);

 

 sem_init(&sem15,0,1);

 sem_init(&sem12,0,1);

 sem_init(&sem23,0,1);

 sem_init(&sem34,0,1);

 sem_init(&sem45,0,1);

 

 cls();

 printf(“\n\n\n\n\n\n”);

 printf(“_____________________________________________________________________________________”);

 

 printf(“\n\n\n\t\t\tDINNING PHILOSOPHER PROBLEM.”);

 printf(“\n\t\t\t____________________________”);

 

 printf(“\n\n\t\tNO. OF PHILOSOPHERS :5”);

printf(“\n\n\t\tNO. OF FORKS(SPOONS):5\n\n”); printf(“_____________________________________________________________________________________”);

 

 printf(“\n\n\n\t\tPRESS ENTER TO CONTINUE…………………”);

 fgets(a,2,stdin);

 

 cls();

 pthread_create(&t1,&at1,philosopher1,NULL);

 pthread_create(&t2,&at1,philosopher2,NULL);

 pthread_create(&t3,&at1,philosopher3,NULL);

 pthread_create(&t4,&at1,philosopher4,NULL);

 pthread_create(&t5,&at1,philosopher5,NULL);

 

 while(end!=5)

 {

 }

}

                        //definition of philosopher1.

void * philosopher1()

{

 int i=0;

 

 printf(“\n\t\tPHILOSOPHER-1 THINKING.\n”);

 

 while(i<EATINGTIME)

 {

  sleep(1);

                        //waiting to acquire the forks.

  sem_wait(&sem15);

  sem_wait(&sem12);

 

  printf(“\n\t\t\t* PHILOSOPHER-1 EATING.*\n”);

 

  sleep(1);

                        //releasing the forks

  sem_post(&sem15);

  sem_post(&sem12);

 

  printf(“\n\t\tPHILOSOPHER-1 THINKING.\n”);

 

  i++;

 }

 end++;

}

 

                        //philosopher2.

void * philosopher2()

{

 int i=0;

 

 printf(“\n\t\tPHILOSOPHER-2 THINKING.\n”);

 

 while(i<EATINGTIME)

 {

  sleep(1);

 

  sem_wait(&sem12);

  sem_wait(&sem23);

 

  printf(“\n\t\t\t* PHILOSOPHER-2 EATING.*\n”);

 

  sleep(1);

 

  sem_post(&sem12);

  sem_post(&sem23);

 

  printf(“\n\t\tPHILOSOPHER-2 THINKING.\n”);

 

  i++;

 }

 end++;

}

 

                                    //philosopher 3

void * philosopher3()

{

 int i=0;

 

 printf(“\n\t\tPHILOSOPHER-3 THINKING.\n”);

 

 while(i<EATINGTIME)

 {

  sleep(1);

 

  sem_wait(&sem23);

  sem_wait(&sem34);

 

  printf(“\n\t\t\t* PHILOSOPHER-3 EATING.*\n”);

 

  sleep(1);

 

  sem_post(&sem23);

  sem_post(&sem34);

 

  printf(“\n\t\tPHILOSOPHER-3 THINKING.\n”);

 

  i++;

 }

 end++;

}

                                                //philosopher 4.

void * philosopher4()

{

 int i=0;

 

 printf(“\n\t\tPHILOSOPHER-4 THINKING.\n”);

 

 while(i<EATINGTIME)

 {

  sleep(1);

 

  sem_wait(&sem34);

  sem_wait(&sem45);

 

  printf(“\n\t\t\t* PHILOSOPHER-4 EATING.*\n”);

 

  sleep(1);

 

  sem_post(&sem34);

  sem_post(&sem45);

 

  printf(“\n\t\tPHILOSOPHER-4 THINKING.\n”);

 

  i++;

 }

 end++;

}

                                                //philosopher 5.

void * philosopher5()

{

 int i=0;

 

 printf(“\n\t\tPHILOSOPHER-5 THINKING.\n”);

 

 while(i<EATINGTIME)

 {

  sleep(1);

 

  sem_wait(&sem45);

  sem_wait(&sem15);

  printf(“\n\t\t\t* PHILOSOPHER-5 EATING.*\n”);

  sleep(1);

 sem_post(&sem45);

 sem_post(&sem15);

 

  printf(“\n\t\tPHILOSOPHER-5 THINKING.\n”);

  i++;

 }

 end++;

}

 

Output

 33

 

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: