Extension to the classical problem of synchronization – the Dining Philosophers problem. Solved using the Monitor construct built on top of Java’s synchronization primitives. The extension here is that sometimes philosophers would like to talk, but only one (any) philosopher can be talking at a time while he/she is not eating.

_DiningPhilosophers

Extension to the classical problem of synchronization – the Dining Philosophers problem. 
Solved using the Monitor construct built on top of Java’s synchronization primitives. 
The extension here is that sometimes philosophers would like to talk, but only one (any) philosopher can be talking at a time while he/she is not eating.
Moreover, deadlocks and starvations are handled.

BaseThread.java

import java.util.Random;

public class BaseThread extends Thread
{
	/*
	 * ------------
	 * Data members
	 * ------------
	 */

	/**
	 * Preserves value across all instances
	 */
	public static int siNextTID = 1;

	/**
	 * Our Thread ID
	 */
	protected int iTID;

	/**
	 * TID of a thread to proceed to the phase II
	 */
	private static int siTurn = 1;

	/*
	 * ------------
	 * Constructors
	 * ------------
	 */

	/**
	 * Default
	 */
	public BaseThread()
	{
		setTID();
	}

	/**
	 * Assigns name to the thread and places it to the specified group
	 *
	 * @param poGroup ThreadGroup to add this thread to
	 * @param pstrName A string indicating human-readable thread's name
	 */
	public BaseThread(ThreadGroup poGroup, String pstrName)
	{
		super(poGroup, pstrName);
		setTID();
	}

	/**
	 * Sets user-specified TID
	 */
	public BaseThread(final int piTID)
	{
		this.iTID = piTID;
	}

	/**
	 * Retrieves our TID
	 * @return TID, integer
	 */
	public final int getTID()
	{
		return this.iTID;
	}

	/**
	 * Sets internal TID and updates next TID on contruction time, so it's private.
	 */
	private final void setTID()
	{
		this.iTID = siNextTID++;
	}

	/**
	 * Just a make up for the PHASE I to make it somewhat tangeable.
	 * Must be atomic.
	 */
	protected synchronized void phase1()
	{
		System.out.println(this.getClass().getName() + " thread [TID=" + this.iTID + "] starts PHASE I.");

		System.out.println
		(
			"Some stats info in the PHASE I:\n" +
			"    iTID = " + this.iTID +
			", siNextTID = " + siNextTID +
			", siTurn = " + siTurn +
			".\n    Their \"checksum\": " + (siNextTID * 100 + this.iTID * 10 + siTurn)
		);

		System.out.println(this.getClass().getName() + " thread [TID=" + this.iTID + "] finishes PHASE I.");
	}

	/**
	 * Just a make up for the PHASE II to make it somewhat tangeable.
	 * Must be atomic.
	 */
	protected synchronized void phase2()
	{
		System.out.println(this.getClass().getName() + " thread [TID=" + this.iTID + "] starts PHASE II.");

		System.out.println
		(
			"Some stats info in the PHASE II:\n" +
			"    iTID = " + this.iTID +
			", siNextTID = " + siNextTID +
			", siTurn = " + siTurn +
			".\n    Their \"checksum\": " + (siNextTID * 100 + this.iTID * 10 + siTurn)
		);

		System.out.println(this.getClass().getName() + " thread [TID=" + this.iTID + "] finishes PHASE II.");
	}

	/**
	 * Test-and-Set for the iTurn variable.
	 *
	 * Use to proceed to the phase II in the correct order.
	 * Must be atomic.
	 *
	 * @param pcIncreasingOrder true if TIDs are in increasing order; false otherwise
	 *
	 * @return Returns true if if the TID of currently running thread  matches the turn, 'false' otherwise
	 */
	public synchronized boolean turnTestAndSet(boolean pcIncreasingOrder)
	{
		// test
		if(siTurn == this.iTID)
		{
			// set siTurn = siTurn +/- 1;
			if(pcIncreasingOrder == true)
				siTurn++;
			else
				siTurn--;

			return true;
		}

		return false;
	}

	/**
	 * Always assumes the increasing order
	 */
	public synchronized boolean turnTestAndSet()
	{
		return turnTestAndSet(true);
	}

	/**
	 * Allows setting arbitratu turn value. Should be set only before
	 * the threads are started
	 */
	public static void setInitialTurn(int piTurn)
	{
		siTurn = piTurn;
	}

	/**
	 * Default ascending order
	 */
	public static void setInitialTurnAscending()
	{
		setInitialTurn(1);
	}

	/**
	 * Descending order
	 */
	public static void setInitialTurnDescending()
	{
		setInitialTurn(siNextTID - 1);
	}

	/**
	 * Calls yield() several (4-40, pseudorandomly) times.
	 * Next to useless, but helps to mix up the execution of phases.
	 * Must NOT be atomic.
	 */
	public void randomYield()
	{
		// Generate from 5 to 40 yield()'s pseudorandomly
		int iNumYields = (int)((new Random()).nextFloat() * 35) + 5;

		for(int i = 0; i < iNumYields; i++)
			yield();
	}
}

// EOF

Chopstick.java

class Chopstick{
    
    boolean pickedUp; //variable to determine if the chopstick is currently picked up or not
    int lastPickedUpBy; //variable to determine which thread had picked this particular chopstick last time

    //Initialize the datamembers
    Chopstick(){ 
        pickedUp = false;
        lastPickedUpBy = -1;
    }

    //A function that would determin whether thread with 'pid' was last seen holding or not.. could be holding it currently
    boolean lastPickedUpByMe(final int pid){
        return (lastPickedUpBy == pid);
    }

    //A function that would tell if any other thread than thread with 'pid' is currently holding it or not
    boolean pickedUpByElse(final int pid){
        return (lastPickedUpBy != pid) && pickedUp;
    }

    //A function that would help thread with 'pid' to pick up the chopstick
    void pickUp(final int pid){
        pickedUp = true;
        lastPickedUpBy = pid;
    }

    //A function that would putdown the chostick and make it available for others.
    void putDown(){
        pickedUp = false;
    }
}

DiningPhilosophers.java

public class DiningPhilosophers 
{
	/*
	 * ------------
	 * Data members   
	 * ------------
	 */

	/**
	 * This default may be overridden from the command line
	 */
	public static final int DEFAULT_NUMBER_OF_PHILOSOPHERS = 4;

	/**
	 * Dining "iterations" per philosopher thread
	 * while they are socializing there
	 */
	public static final int DINING_STEPS = 10;

	/**
	 * Our shared monitor for the philosphers to consult
	 */
	public static Monitor soMonitor = null;

	/*
	 * -------
	 * Methods
	 * -------
	 */

	/**
	 * Main system starts up right here
	 */
	public static void main(String[] argv)
	{
		try
		{
			/*
			 * TODO:
			 * Should be settable from the command line
			 * or the default if no arguments supplied.
			 */
			int iPhilosophers = DEFAULT_NUMBER_OF_PHILOSOPHERS;

			// Checking for input from the user.
			if(argv.length>0){
				iPhilosophers = Integer.parseInt(argv[0]);
				if(iPhilosophers<1)
					throw new Exception("Non-positive Input.");
			}

			// Make the monitor aware of how many philosophers there are
			soMonitor = new Monitor(iPhilosophers);

			// Space for all the philosophers
			Philosopher aoPhilosophers[] = new Philosopher[iPhilosophers];
			
			System.out.println
			(
				iPhilosophers +
				" philosopher(s) came in for a dinner."
			);
			// Let 'em sit down
			for(int j = 0; j < iPhilosophers; j++)
			{
				aoPhilosophers[j] = new Philosopher();
				aoPhilosophers[j].start();
			}

			// Main waits for all its children to die...
			// I mean, philosophers to finish their dinner.
			for(int j = 0; j < iPhilosophers; j++)
				aoPhilosophers[j].join();

			System.out.println("All philosophers have left. System terminates normally.");
		}
		catch(InterruptedException e)
		{
			System.err.println("main():");
			reportException(e);
			System.exit(1);
		}
		//Exception when the input is not a desired integer.
		catch(Exception e){
			if(e.getMessage().equals("Non-positive Input.")){
				System.out.println(argv[0] + " is not a positive decimal integer");
				System.out.println("Usage: java DiningPhilosophers [NUMBER_OF_PHILOSOPHERS]");
			}
			else
				System.out.println(e.getMessage());
		}
	} // main()

	/**
	 * Outputs exception information to STDERR
	 * @param poException Exception object to dump to STDERR
	 */
	public static void reportException(Exception poException)
	{
		System.err.println("Caught exception : " + poException.getClass().getName());
		System.err.println("Message          : " + poException.getMessage());
		System.err.println("Stack Trace      : ");
		poException.printStackTrace(System.err);
	}
}

// EOF

Makefile

JAVAC=javac
JFLAGS=-g
JVM=java
EXE=DiningPhilosophers

ASMTDIRS := .

# Lists of all *.java and *.class files
JAVAFILES := $(ASMTDIRS:%=%/*.java)
CLASSES := $(ASMTDIRS:%=%/*.class)

all: $(EXE).class 
	@echo "Dining Philosophers Application has been built."

$(EXE).class: $(JAVAFILES)
	$(JAVAC) $(JFLAGS) $(EXE).java

run: all
	$(JVM) $(EXE)

regression: all
	@for arg in 3 4 5; do $(JVM) $(EXE) $$arg; done
	rm *.class

clean:
	rm -f $(CLASSES) #* *~

# EOF

Monitor.java

public class Monitor   
{
	/*
	 * ------------    
	 * Data members 
	 * ------------
	 */

	//Equal no of chopsticks as the noOf philosophers, a variable that tells if anyone is talking at the moment or not
	//If there is one philosopher then his/her left chopstick acts as a right chopstick as well.
	int noOfPhilosophers;
	Chopstick[] chopsticks;
	boolean isTalking;
	/**
	 * Constructor
	 */
	public Monitor(int piNumberOfPhilosophers)
	{
		// TODO: set appropriate number of chopsticks based on the # of philosophers
		//Initiliazing all the variables.
		noOfPhilosophers = piNumberOfPhilosophers;
		
		isTalking = false;

		chopsticks = new Chopstick[noOfPhilosophers];

		for(int i=0;i<noOfPhilosophers;i++)
			chopsticks[i] = new Chopstick();
	}

	/*
	 * -------------------------------
	 * User-defined monitor procedures
	 * -------------------------------
	 */

	/**
	 * Grants request (returns) to eat when both chopsticks/forks are available.
	 * Else forces the philosopher to wait()
	 */
	public synchronized void pickUp(final int piTID){
		int pid = piTID-1;

		while(true){

			//If the left or right chopstick is picked up or not. If anyone is picked up then enter
			if(chopsticks[pid % noOfPhilosophers].pickedUpByElse(pid) || chopsticks[(pid+1)%noOfPhilosophers].pickedUpByElse(pid)){
				//if it's the right one and
				//if left is not picked up and it wasn't picked up by the same thread the last time then pick the left.
				if(!chopsticks[pid].pickedUp && !chopsticks[pid].lastPickedUpByMe(pid))
					chopsticks[pid].pickUp(pid);
				else if(!chopsticks[(pid + 1) % noOfPhilosophers].pickedUp && !chopsticks[(pid + 1) % noOfPhilosophers].lastPickedUpByMe(pid))
					chopsticks[(pid + 1) % noOfPhilosophers].pickUp(pid);
				//if it's the left one and
				//the right is not picked up and it wasn't picked up by the same thread the last time then pick the left. If it was then go and wait.
			}
			//If not then pick both of them and exit
			else{
				chopsticks[pid%noOfPhilosophers].pickUp(pid);
				chopsticks[(pid+1)%noOfPhilosophers].pickUp(pid);
				break;
			}

			try{
				wait();
			}
			catch(InterruptedException e){
				System.err.println("Monitor.pickUp():"+piTID);
				DiningPhilosophers.reportException(e);
				System.exit(1);
			}
		}
		
	}

	/**
	 * When a given philosopher's done eating, they put the chopstiks/forks down
	 * and let others know they are available.
	 */
	public synchronized void putDown(final int piTID)
	{
		//Put down both the chopsticks and notify all the others.
		int pid = piTID-1;
		chopsticks[pid%noOfPhilosophers].putDown();
		chopsticks[(pid+1)%noOfPhilosophers].putDown();

		notifyAll();
	}

	/**
	 * Only one philopher at a time is allowed to philosophy
	 * (while she is not eating).
	 */
	public synchronized void requestTalk()
	{
		// If someone is talking then wait
		while(isTalking){
			try{
				wait();
			}
			catch(InterruptedException e){
				System.err.println("Monitor.requestTalk():");
				DiningPhilosophers.reportException(e);
				System.exit(1);
			}
		}

		isTalking = true;

	}

	/**
	 * When one philosopher is done talking stuff, others
	 * can feel free to start talking.
	 */
	public synchronized void endTalk()
	{
		// When you stop talking then notify others that you have stopped.
		isTalking = false;
		notifyAll();
	}
}

// EOF

Philosopher.java

public class Philosopher extends BaseThread
{
	/**
	 * Max time an action can take (in milliseconds)   
	 */
	public static final long TIME_TO_WASTE = 1000; 

	/**
	 * The act of eating.
	 * - Print the fact that a given phil (their TID) has started eating. 
	 * - Then sleep() for a random interval.
	 * - The print that they are done eating.
	 */
	public void eat()
	{
		try
		{
			//This would display the message that this philosopher has started eating, and then
			//put the thread on sleep for some time, representing the time taken to eat
			// And then would stop eating and display the message that it has finished eating
			System.out.println("Philosopher: "+getTID()+" started eating.");
			sleep((long)(Math.random() * TIME_TO_WASTE));
			System.out.println("Philosopher: "+getTID()+" finished eating.");
		}
		catch(InterruptedException e)
		{
			System.err.println("Philosopher.eat():");
			DiningPhilosophers.reportException(e);
			System.exit(1);
		}
	}

	/**
	 * The act of thinking.
	 * - Print the fact that a given phil (their TID) has started thinking.
	 * - Then sleep() for a random interval.
	 * - The print that they are done thinking.
	 */
	public void think()
	{
		try
		{
			//This would display the message that this philosopher has started thinking, and then
			//put the thread on sleep for some time, representing the time taken to think
			// And then would stop thinking and display the message that it has finished thinking
			System.out.println("Philosopher: "+getTID()+" has started to think.");
			sleep((long)(Math.random() * TIME_TO_WASTE));
			System.out.println("Philosopher: "+getTID()+" just finished thinking.");
		}
		catch(InterruptedException e)
		{
			System.err.println("Philosopher.think():");
			DiningPhilosophers.reportException(e);
			System.exit(1);
		}
	}

	/**
	 * The act of talking.
	 * - Print the fact that a given phil (their TID) has started talking.
	 * - Say something brilliant at random
	 * - The print that they are done talking.
	 */
	public void talk()
	{
		//This would display the message that this philosopher has started talking, and then
		//would randomly pickup a line from a given set of messages that would get printed
		// And then would stop talking and display the message that it has finished talking
		System.out.println("Philosopher: "+getTID()+" has started to talk to others.");
		saySomething();
		System.out.println("Philosopher: "+getTID()+" just finished talking on the table.");
	}

	/**
	 * No, this is not the act of running, just the overridden Thread.run()
	 */
	public void run()
	{
		for(int i = 0; i < DiningPhilosophers.DINING_STEPS; i++)
		{
			DiningPhilosophers.soMonitor.pickUp(getTID()); //This is necessary in order to pickup both the left and right chopstick

			eat(); // The act of eating

			DiningPhilosophers.soMonitor.putDown(getTID()); // This is putting down the left and right chopstick for other threads to pick up

			think(); // It doesn't require any condition, more than one philosopher can be thinking at a time, without the fact that what others are doing.

			/*
			 * TODO:
			 * A decision is made at random whether this particular
			 * philosopher is about to say something terribly useful.
			 */
			if(Math.random()<0.5) // A random decison 
			{
				//This is  necessary in order to check if anyone else is talking or not and if someone is talking then wait for him to finish.
				DiningPhilosophers.soMonitor.requestTalk();
				talk(); // The act of talking
				DiningPhilosophers.soMonitor.endTalk();
				// When one philosopher finishes talking it notifies other in waiting that it is done so that others can continue
			}


		}
	} // run()

	/**
	 * Prints out a phrase from the array of phrases at random.
	 * Feel free to add your own phrases.
	 */
	public void saySomething()
	{
		String[] astrPhrases =
		{
			"Eh, it's not easy to be a philosopher: eat, think, talk, eat...",
			"You know, true is false and false is true if you think of it",
			"2 + 2 = 5 for extremely large values of 2...",
			"If thee cannot speak, thee must be silent",
			"My number is " + getTID() + ""
		};

		System.out.println
		(
			"Philosopher " + getTID() + " says: " +
			astrPhrases[(int)(Math.random() * astrPhrases.length)]
		);
	}
}

// EOF