Implement a program on Grid for the dining philosophers’ problem as follows. The

Question

Implement a program on Grid for the dining philosophers’ problem as follows. The program should use five Pthreads to simulate philosophers and declare an array of five semaphores to represent five forks.

Write the program without considering deadlock. Your program should create five Pthreads that run the same procedure as follows (Note: This is pseudo-code).

philosopher(int i){

    while (TRUE) {

    // Think

    // Eat

        printf(“Philosopher %d requests fork %d ”, i, i);

P(fork[i]);            /* Pick up left fork */

    printf(“Philosopher %D acquired fork %d ”, i, i);

    printf(“Philosopher %d requests fork %d ”, i, (i+1) mod 5);

          P(fork[(i+1) mod 5]); /* Pick up right fork */

            printf(“Philosopher %d acquired fork %d ”, i, (i+1) mod 5);

            eat();

            printf(“Philosopher %d releases fork %d ”, i, (i+1) mod 5);

          V(fork[(i+1) mod 5]);

          printf(“Philosopher %d releases fork %d ”, i, i);

        V(fork[i]);

    }

}

semaphore fork[5];

fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1;

fork(philosopher, 1, 0);

fork(philosopher, 1, 1);

fork(philosopher, 1, 2);

fork(philosopher, 1, 3);

fork(philosopher, 1, 4);

Make each philosopher print a message at every event (viz., request, allocation, release). The message should show the philosopher number and the relevant fork number, as shown in the above procedure.

Run the program and see whether it will run into deadlock.

philosopher(int i){

    while (TRUE) {

    // Think

    // Eat

        printf(“Philosopher %d requests fork %d ”, i, i);

P(fork[i]);            /* Pick up left fork */

    printf(“Philosopher %D acquired fork %d ”, i, i);

    printf(“Philosopher %d requests fork %d ”, i, (i+1) mod 5);

          P(fork[(i+1) mod 5]); /* Pick up right fork */

            printf(“Philosopher %d acquired fork %d ”, i, (i+1) mod 5);

            eat();

            printf(“Philosopher %d releases fork %d ”, i, (i+1) mod 5);

          V(fork[(i+1) mod 5]);

          printf(“Philosopher %d releases fork %d ”, i, i);

        V(fork[i]);

    }

}

Explanation / Answer

---- The arrays represent the philosophers and corresponding chopsticks for them.
Each element in the philosopher’s array corresponds to a thread and each element in the chopstick’s array corresponds to a mutex variable.
>>> Algorithm for thread (philosopher i) function:

Start.
Philosopher i is thinking.
Lock the left fork spoon.
Lock the right fork spoon.
Philosopher i is eating.
sleep
Release the left fork spoon.
Release the right fork spoon.
Philosopher i Finished eating.
Stop.

CODE USINGS THREADS ONLY

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<semaphore.h>
void *func(int n);
pthread_t philosopher[5];
pthread_mutex_t chopstick[5];
int main()
{
int i,k;
void *msg;
for(i=1;i<=5;i++)
{
k=pthread_mutex_init(&chopstick[i],NULL);
if(k==-1)
{
printf(“ Mutex initialization failed”);
exit(1);
}
}
for(i=1;i<=5;i++)
{
k=pthread_create(&philosopher[i],NULL,(void *)func,(int *)i);
if(k!=0)
{
printf(“ Thread creation error ”);
exit(1);
}
}
for(i=1;i<=5;i++)
{
k=pthread_join(philosopher[i],&msg);
if(k!=0)
{
printf(“ Thread join failed ”);
exit(1);
}
}
for(i=1;i<=5;i++)
{
k=pthread_mutex_destroy(&chopstick[i]);
if(k!=0)
{
printf(“ Mutex Destroyed ”);
exit(1);
}
}
return 0;
}

void *func(int n)
{
printf(“ Philosopher %d is thinking “,n);
pthread_mutex_lock(&chopstick[n]);//when philosopher 5 is eating he takes fork 1 and fork 5
pthread_mutex_lock(&chopstick[(n+1)%5]);
printf(“ Philosopher %d is eating “,n);
sleep(3);
pthread_mutex_unlock(&chopstick[n]);
pthread_mutex_unlock(&chopstick[(n+1)%5]);
printf(“ Philosopher %d Finished eating “,n);
}

CODE USINGS SEMAPHORES ONLY

#include<stdio.h>
#include<fcntl.h>
#include<semaphore.h>
#include<sys/wait.h>
#include<pthread.h>
#include<stdlib.h>
sem_t *sem[20];
int n;
int main()
{
pid_t cpid[5];
char semname[5];
int i,j=0;
n = 5;
for(i=0;i<n;i++)
{
sprintf(semname,”%d”,getpid()+i);
sem[i]=sem_open(semname,O_CREAT|O_EXCL,0666,1);
if(sem[i]==SEM_FAILED)
perror(“Unable to create semaphore”);
}

for(i=0;i<n;i++)
{
cpid[i]=fork();
if(cpid[i]==0)
break;
}

if(i==n)
{
int status;
for(i=0;i<n;i++)
waitpid(cpid[i],&status,WUNTRACED);
for(i=0;i<n;i++)
{
sem_close(sem[i]);
sprintf(semname,”%d”,getpid()+i);
sem_unlink(semname);
}
}
else
reader(i);
}
int reader(int val)
{
printf(“%d Thinking ”,val+1);
while(1)
{
sem_wait(sem[val%n]);if(!sem_trywait(sem[(val+1)%n]))
break;
else
sem_post(sem[val%n]);
}
printf(“%d Eating ”,val+1);
sleep(2);
sem_post(sem[val%n]);
sem_post(sem[(val+1)%n]);
printf(“%d Finished Eating ”,val+1);
}

EXPECTED OUTPUT

[root@localhost ~]$ gcc -o c dining.c -pthread
[root@localhost ~]$ ./c

Philosopher 1 is thinking
Philosopher 1 is eating
Philosopher 2 is thinking
Philosopher 3 is thinking
Philosopher 3 is eating
Philosopher 4 is thinking
Philosopher 5 is thinking
Philosopher 1 Finished eating
Philosopher 3 Finished eating
Philosopher 4 is eating
Philosopher 5 is eating
Philosopher 2 is eating
Philosopher 4 Finished eating
Philosopher 5 Finished eating
Philosopher 2 Finished eating

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.