Dining Philosophers Problem Using Semaphores

1
1191

What is Dining Philosophers problem in C?

Suppose there are N philosophers meeting around a table, eating spaghetti and talking about philosophy. Now let us discuss the problem. There are only N forks available such that only one fork between each philosopher. Since there are only 5 philosophers and each one requires 2 forks to eat, we need to formulate an algorithm which ensures that utmost number of philosophers can eat spaghetti at once.

The next question is why we are detailing problems in this manner? Sometimes when it comes to computers, some of the analogous situations often demands solutions in a creative fashion. This is somewhat like an abstract problem in a novel dimension.

In this problem, the condition is each philosopher has to think and eat alternately. Assume that there is an infinite supply of spaghetti and eating is by no means limited by the quantity of food left. When available, each philosopher can pick up the adjacent fork. But he can eat only if the right and left forks are available.

Dining Philosophers Problem using Semaphores

 PROBLEM DEFINITION

To implement Dining Philosophers Problem using Threads and Semaphores

ALGORITHM

  1. Define the number of philosophers
  2. Declare one thread per philosopher
  3. Declare one semaphore (represent chopsticks) per philosopher
  4. When a philosopher is hungry
    1. See if chopsticks on both sides are free
    2.  Acquire both chopsticks or
    3.  eat
    4. restore the chopsticks
    5. If chopsticks aren’t free
  5. Wait till they are available

PROGRAM DEVELOPMENT

# include<stdio.h>

# include<pthread.h>

# include<stdlib.h>

# include<unistd.h>

# include<ctype.h>

# include<sys/types.h>

# include<sys/wait.h>

# include<semaphore.h>

# include<sys/sem.h>

sem_t chopstick[100];

int n;

void *thread_func(int no)

{

int i,iteration=5;

for(i=0;i<iteration;++i)

{

sem_wait(&chopstick[no]);

sem_wait(&chopstick[(no+1)%n]);

printf(“\nPhilosopher %d –> Begin eating”,no);

sleep(1);

printf(“\nPhilosopher %d –> Finish eating\n”,no);

sem_post(&chopstick[no]);

sem_post(&chopstick[(no+1)%n]);

}

pthread_exit(NULL);

}

int main()

{

int i,res;

pthread_t a_thread[100];

printf(“\nEnter the number of philosopher :”);

scanf(“%d”,&n);

for(i=0;i<n;++i)

{

res=sem_init(&chopstick[i],0,0);

if(res==-1)

{

perror(“semaphore initialization failed”);

exit(1);

}

}

for(i=0;i<n;++i)

{

res=pthread_create(&a_thread[i],NULL,thread_func,(int*) i);

if(res!=0)

{

perror(“semaphore creation failed”);

exit(1);

}

sem_post(&chopstick[i]);

}

for(i=0;i<n;++i)

{

res=pthread_join(a_thread[i],NULL);

if(res!=0)

{

perror(“semaphore join failed”);

exit(1);

}

}

printf(“\n \n thread join succesfull\n”);

for(i=0;i<n;++i)

{

res=sem_destroy(&chopstick[i]);

if(res==-1)

{

perror(“semaphore destruction failed”);

exit(1);

}

}

exit(0);

}

OUTPUT

$ gcc dining_sem.c -o dining_sem_op -lpthread

$ ./dining_sem_op

 

Next let us check out another method to solve the problem.

Dining Philosophers Problem using MUTEX

 PROBLEM DEFINITION

To implement Dining Philosophers Problem using Threads and mutex

ALGORITHM

  1. Define the number of philosophers
  2. Declare one thread per philosopher
  3. Declare one mutex(represent chopsticks) per philosopher
  4. When a philosopher is hungry
    1. See if chopsticks on both sides are free
    2.  acquire chopsticks
    3.  eat
    4. restore the chopsticks
    5. If chopsticks aren’t free
  5. wait till they’re available

PROGRAM DEVELOPMENT

# include<stdio.h>

# include<pthread.h>

# include<stdlib.h>

# include<unistd.h>

# include<ctype.h>

# include<sys/types.h>

# include<sys/wait.h>

# include<semaphore.h>

# define philosopher 5

pthread_mutex_t chopstick[philosopher]

int main()

{

int i,res;

pthread_t a_thread[philosopher];

void *thread_func(int n)

for(i=0;i<philosopher;++i)

{

res=pthread_mutex_init(&chopstick[i],NULL);

if(res==-1)

{

perror(“mutex initialization failed”);

exit(1);

}

}

for(i=0;i<philosopher;++i)

{

res=pthread_create(&a_thread[i],NULL,thread_func,(int)i);

if(res!=0)

{

perror(“mutex creation failed”)

exit(1);

}

}

for(i=0;i<philosopher;++i)

{

res=pthread_join(a_thread[i],NULL);

if(res!=0)

{

perror(“mutex join failed”);

exit(1);

}

}

printf(“thread join successful\n”);

for(i=0;i<philosopher;++i)

{

res=pthread_mutex_destroy(&chopstick[i]);

if(res==-1)

{

perror(“mutex destruction failed”)

exit(1);

}

}

exit(0);

}

void *thread_func(int n)

{

int i,iteration=5;

for(i=0;i<iteration;++i)

{

sleep(1);

pthread_mutex_lock(&chopstick[n]);

pthread_mutex_lock(&chopstick[n+1)%philosopher]);

printf(“\nBegin eating :%d”,N);

sleep(1);

printf(“\nFinish eating”%d”,n);

pthread_mutex_unlock(&chopstick[n]);

pthread_mutex_unlock(&chopstick[n+1)%philosopher]);

}

pthread_exit(NULL);

}

OUTPUT

$ gcc dining_sem.c -o dining_sem_op -lpthread

$ ./dining_sem_op

[root@localhost ~]$ gcc-I/usr/npt1 dint.c~]pthread

Begin eating :0

Begin eating :2

Finish eating:0

Finish eating:2

Begin eating :4

Begin eating :1

Finish eating:4

Finish eating:1

Begin eating :3

Begin eating :0

Finish eating:3

Finish eating:0

Begin eating :2

Finish eating:3

Begin eating :4

Finish eating:2

Finish eating:4

Begin eating :1

Begin eating :3

Finish eating:1

Finish eating:3

Begin eating :0

Begin eating :2

Finish eating:0

Finish eating:2

Begin eating :2

Begin eating :4

Finish eating:4

Finish eating:1

Begin eating :3

Begin eating :0

Finish eating:3

Finish eating:0

Begin eating :2

Begin eating :4

Finish eating:2

Finish eating:4

Begin eating :1

Begin eating :3

Finish eating:1

Finish eating:3

Begin eating :0

Begin eating :2

Finish eating:0

Finish eating:2

Begin eating :4

Begin eating :1

Finish eating:4

Finish eating:1

Begin eating :3

Finish eating:3

Thread join successful

1 COMMENT

LEAVE A REPLY