Deadlocks (Blocage)

3.10.1 Definition
Un blocage se produit lorsque deux threads ou plus ont besoin d'une ressource pour terminer leur exécution qui est détenue par l'autre thread.

3.10.2 Exemple: Philosophes

prend la fourchette à gauche
prend la fourchette à droite
mange pendant un certain temps
met les deux fourchettes à la table
pense pendant un certain temps

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

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

class Fork{
	private boolean taken;
	private String name;
	Fork(String name){
		taken = false;
		this.name=name;
	}
	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;
	}
	synchronized void pose(){
		taken = false;
		notify();
	}
	public String toString(){
		return name;
	}
}

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

P1 take fork 0
P1 look for the second fork
P2 take fork 1
P2 look for the second fork
P3 take fork 2
P3 look for the second fork
P4 take fork 3
P4 look for the second fork
P5 take fork 4
P5 look for the second fork

3.10.3 Éviter le blocage (l'approche la plus souvent utilisée) - demande des ressources dans un ordre croissant d'énumération.

L'approche la plus souvent utilisée pour éviter attente circulaire est d'imposer un ordre total de tous les types de ressources. Chaque thread demande des ressources dans un ordre croissant d'énumération. Ainsi, s'il existe unе liste ordonnée de n ressources {r1,r2,..rn} et un thread nécessite les ressources ri et ri+j pour accomplir une tâche, il doit d'abord demander ri puis ri+j.

3.10.4 Modifier le programme des philosophes pour demander des ressources dans un ordre croissant d'énumération

3.10.5 Éviter le blocage - introduire "tolérance" dans les threads

La deuxième approche modifie le comportement des threads pour éviter préemption. Un thread doit s'assurer qu'il libère automatiquement toutes les ressources actuellement détenues si la ressource nouvellement demandée n'est pas disponible. Quand le philosophe constate que la fourchette n'est pas libre (une exception est générée) il se retire en laissant les fourchettes pour un certain temps avant de réessayer de les prendre.

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

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

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

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();
		}		
	}
}