# Dining Philosophers Problem Using Semaphores

1
3794

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<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;

{

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]);

}

}

int main()

{

int i,res;

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)

{

if(res!=0)

{

perror(“semaphore creation failed”);

exit(1);

}

sem_post(&chopstick[i]);

}

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

{

if(res!=0)

{

perror(“semaphore join failed”);

exit(1);

}

}

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<stdlib.h>

# include<unistd.h>

# include<ctype.h>

# include<sys/types.h>

# include<sys/wait.h>

# include<semaphore.h>

# define philosopher 5

int main()

{

int i,res;

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

{

if(res==-1)

{

perror(“mutex initialization failed”);

exit(1);

}

}

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

{

if(res!=0)

{

perror(“mutex creation failed”)

exit(1);

}

}

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

{

if(res!=0)

{

perror(“mutex join failed”);

exit(1);

}

}

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

{

if(res==-1)

{

perror(“mutex destruction failed”)

exit(1);

}

}

exit(0);

}

{

int i,iteration=5;

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

{

sleep(1);

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

sleep(1);

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

}

}

OUTPUT

\$ gcc dining_sem.c -o dining_sem_op -lpthread

\$ ./dining_sem_op

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