Dining Philosophers Problem

Dining Philosophers Problem

There are n number of philosophers meeting around a table, eating spaghetti and talking about philosophy. There are only n forks are available and each philosopher needs 2 forks to eat. Only one fork is available between each philosopher. Now we have design algorithm that ensures maximum number of philosophers can eat at once and none starves as long as each philosopher eventually stop eating.

 

           38 (1).jpg

 

N = 5 ;  /* total number of philosophers */

Right (i) = (i + 1) mod n ;

Left (i) = ((i = = n) ? 0 : (i + 1))

Philosopher_state[] = {thinking, hungry, eating}

Semaphore mutex = 1 ;

Semaphore S[n] ;  /*one per philosopher, all 0 initially*/

Philosopher (int process)

{

while(true)

{

Think () ;

Get_forks (process) ;

Eat () ;

Put_forks (process) ;

}

}

Test (int i)

{

If (state[i] = hungry)&&(state[left(i)] != eating)&&(state[right(i) != eating])

{

State[i] = eating ;

V(S[i]) ;

}

}

Get_forks(int i)

{

P(mutex) ;

State[i] = hungry ;

Test [i] ;

V (mutex) ;

P(S[i])

}

Put_forks(int i)

{

P(mutex) ;

State [i] = thinking ;

Test (left(i)) ;

Test (right(i)) ;

V (mutex) ;

}

Another approach :

               

N = 5 ;  /* total number of philosophers */

Right (i) = (i + 1) mod n ;

Left (i) = ((i = = n) ? 0 : (i + 1))

Philosopher_state[] = {thinking, hungry, eating}

Semaphore mutex = 1 ;

Semaphore S[n] ;  /*one per philosopher, all 0 initially*/

Philosopher (int process)

{

while(true)

{

Think () ;

Get_forks (process) ;

Eat () ;

Put_forks (process) ;

}

}

Get_forks(int i)

{

State[i] = hungry ;

While (state[i] = =hungry)

{

P(mutex) ;

If (state[i] = =hungry && state[left(i)] != eating && state[right(i)] != eating)

{

State[i] = eating ;

V[S(i)] ;

}

V(mutex) ;

P[S(i)];

}

}

Put_forks(int i)

{

P(mutex) ;

State[i] = thinking ;

If (state[left(i)] = = hungry)

V(S[left(i)]) ;

If (state[right(i)] = = hungry)

V(S[right(i)]) ;

V(mutex) ;

}

 

This avoids starvation and deadlock problems.

 

Contributor's Info

Created:
0Comment