The Deadlocks

A deadlock occurs when two or more threads need a resource to complete their execution that is owned by the other thread.

The 5 Philosophers:

each of them:
take the fork on the left
take the fork on the right
eat for a while
puts both forks at the table
think for a while

public class Philosopher extends Thread{
    Fork first, second;
    Philosopher(String name,Fork left, Fork right){
        super.setName(name);
        first=left;
        second=right;
        start();
    }
    public void run(){
        for(int i=0;i<2;i++){
            first.take();
            System.out.println(getName()+" look for the second fork ");
                 try {
                         sleep((int)(Math.random()*2));
                 } catch (InterruptedException e){}

             second.take();
             System.out.println(getName()+" eating ");
                 try {
                         sleep((int)(Math.random()*1000));
                 } catch (InterruptedException e){}
                 System.out.println(getName()+" poses the forks - thinking");
                 first.pose();
                 second.pose();
                 try {
                         sleep((int)(Math.random()*1000));
                 } catch (InterruptedException e1){}
        }
        System.out.println(getName()+" stop dinning");
    }
}

public class Fork{
    private boolean taken;
    private String name;
    Fork(String name){
        taken = false;
        this.name=name;
    }
    public synchronized void take(){
        while(taken){
            System.out.println(Thread.currentThread().getName()+" waiting for "+name);
            try{     wait();   }
            catch(InterruptedException e){
                            System.err.println(e);
            }
        }
        System.out.println(Thread.currentThread().getName()+" take "+name);
        taken = true;
    }
    public synchronized void pose(){
        taken = false;
        notify();
    }
    public String toString(){
        return name;
    }
}

public class Dinner{
    public static void main(String arg[]){
        int number=5;
        Fork fk[]= new Fork[number];
        for(int i=0;i<number;i++){
            fk[i]= new Fork("fork "+i);
        }
        for(int i=0; i<number;i++){
            new Philosopher("P"+(i+1),fk[i],fk[(i+1)%number]);
        }
    }
}

Avoid blocking

The most often used approach to avoid circular waiting is to impose total ordering of all resource types. Each thread requests resources in ascending order of enumeration. Thus, if there exists an ordered list of n resources {r1,r2,..rn} and a thread requires resources ri and ri+j (j>0) to accomplish a task, it must first request ri then ri+j.

A second possible approach is based on thread "tolerance". A thread must ensure that it automatically releases all currently held resources if the newly requested resource is not available. When the philosopher notices that the fork is not free (an exception is generated) he withdraws, leaving the forks for a certain time before trying to take them again.

public class TakenExc extends Exception{
private static final long serialVersionUID = 1L;
}

public class Philosopher extends Thread{
	String name;
	Fork leftFork, rightFork;
	Philosopher(String name,Fork left, Fork right){
		this.name=name;
		super.setName(name);
		leftFork=left;
		rightFork=right;
	}
	public void run(){
		for(int i=0;i<2;i++){
			do {
				try {
					leftFork.take(this);
				}catch (TakenExc te) { 
					try {
						sleep((int)(Math.random()*600));
					} catch (InterruptedException e){}  
					continue;
				}
				System.out.println(name+" look for the second fork ");
				try {
					sleep((int)(Math.random()*2));
				} catch (InterruptedException e){}  

				try {
					rightFork.take(this);
				}catch (TakenExc te) { 
					leftFork.pose();
					System.out.println(name+" pose "+ leftFork + " waiting "+ rightFork);
					try {
						sleep((int)(Math.random()*600));
					} catch (InterruptedException e){} 
					continue;
				}
				break;
			}while(true);
			System.out.println(name+" eating ");
			try {
				sleep((int)(Math.random()*1000));
			} catch (InterruptedException e){}
			System.out.println(name+" poses the forks - thinking");
			leftFork.pose();
			rightFork.pose();
			try {
				sleep((int)(Math.random()*1000));
			} catch (InterruptedException e1){}
		}
		System.out.println(name+" stop dinning");
	}
	public String toString(){
		return name;
	}
}

public class Fork{
	private boolean taken;
	private String name;
	public Fork(String name){
		taken = false;
		this.name=name;
	}
	public synchronized void take(Philosopher p)throws TakenExc{
		if(taken){
			throw new TakenExc();
		}
		System.out.println(p+" take "+name);
		taken = true;
	}
	public synchronized void pose(){
		taken = false;
		notify();
	}
	public boolean canTake(){
		if (!taken)return true;
		else return false;
	}
	public String toString(){
		return name;
	}
}

public class Dinner{
	public static void main(String arg[]){
		int number=5;
		Philosopher ph[]= new Philosopher[number];
		Fork fk[]= new Fork[number];
		for(int i=0;i<number;i++){
			fk[i]= new Fork("fork "+i);
		}
		for(int i=0; i<number;i++){		
			ph[i] = new Philosopher("P"+(i+1),fk[i],fk[(i+1)%number]);
			ph[i].start();
		}		
	}
}