The Dining Philosophers Problem - classic process synchronization problem

This is part of homework 6 and due 11/6, at the beginning of class.

Five philsophers are seated around a circular table.  In the center is
a bowl of rice and the table is laid with five single chopsticks.
Each chopstick is shared by two philsophers.   The challenge is to write
code to synchronize the five philosophers so that each can think, eat, think,
eat forever.  To eat successfully, one has to pick up both chopsticks.
(see your textbook pages 211.)

For each of the proposed solutions below, determine whether it results
in success, violation of mutual exclusion, deadlock, or livelock
(also known as starvation).  
Deadlock means the processes are blocked and will never be able to
execute again.  Livelock means they are executing in a loop that they
can never get out of.  Success means full tummies and burning brains.
Violation of mutual exclusion means chopstick wars!

SOLUTION 1:  protect each chopstick separately

chopstick[0..4]: array of binary semaphore, initialized to 1;


repeat forever  {
	THINK;				THINK
	P(chopstick[i]);		check if left is free
        pick up left;			pick up left
        P(chopstick[i+1 mod 5]);	check if right is free
        pick up right;			pick up right
	EAT                             EAT
        put down left;			put down left
        V(chopstick[i]);		tell next in line left is free
        put down right;			put down right
        V(chopstick[i+1 mod 5]);        tell next in line right is free
}

-------------
SOLUTION 2:  check to see if both chopsticks are free, if so, pick up both.

mutex[0..4]: array of binary semaphore; all initialized to 1.

This is the code for philospher[i]:

repeat forever  {
	THINK;				THINK
	P(mutex[i]);			check if left is free
        P(mutex[i+1 mod 5]);		check if right is free
	pick up both chopsticks		pick up both chopsticks
	EAT				EAT
	put down both chopsticks	put down both chopsticks
        V(mutex[i]);			tell next in line left is free
        V(mutex[i+1 mod 5]);		tell next in line right is free
}

--------------
SOLUTION 3:  only allow four philsophers to sit at the table at a time.

table: counting semaphore, initialized to 4;
chopstick[0..4]: array of binary semaphore, all intialized to 1;

repeat forever  {
	THINK;				THINK
	P(table);			check if space at the table,
	sit down			sit down
	P(chopstick[i]);		check if left is free
        pick up left;			pick up left
        P(chopstick[i+1 mod 5]);	check if right is free
	pick up right;			pick up right
	EAT                             EAT
	put down left			put down left
        V(chopstick[i]);		tell next in line left is free
	put down right			put down right
        V(chopstick[i+1 mod 5]);        tell next in line right is free
        V(table);			tell next in line there is space
}

----------------

SOLUTION 4:  non-semaphore solution

chopstick[0..4]: array of Boolean, all intialized to 1;

repeat forever  {
   THINK;				 THINK
   repeat {				 repeat ....
      if (chopstick[i] == 1) {		    if left free,
          chopstick[i] = 0;                 pick up left.
          pick up left; 
      }
      if (chopstick[i+1] == 1)		    if right free,	
          chopstick[i+1] = 0;	            pick up right.
          pick up right;
      }
      else {
          chopstick[i] = 1;                 else put down left.
          put down left;
      }
   until (chopstick[i] == 0 and chopstick[i+1] == 0);}until I've got both.
   EAT		                        EAT
   put down left;
   chopstick[i] = 1;		        put down left
   put down right;
   chopstick[i+1] = 1;                  put down right
}