Взаимно блокиране (Deadlocks)

Взаимното блокиране е ситуация при която една или повече нишки очакват да се изпълни неизпълнимо условие. Най- често това се случва, когато всяка от нишките очаква другата да направи нещо.

Задачата за хранещите се философи е една от най-често използваните за илюстриране на проблема:

Алгоритъм - всеки от философите циклично

взима лявата вилица
взима дясната вилица
яде известно време
оставя двете вилици
мисли известно време

Алгоритъмът на всеки философ се реализира чрез отделна нишка. Ако дадена вилица е заета нишката се блокира до освобождаване на вилицата. Ситуация Deadlocks: всички философи са взели лявата вилица и очакват да вземат дясната, която обаче е взета от друг философ.

 

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++){
			 leftFork.take(this);
			 System.out.println(name+" look for the second fork ");
		     try {
		         sleep((int)(Math.random()*2));
		     } catch (InterruptedException e){}  

			 rightFork.take(this);
			 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;
	String name;
	Fork(String name){
		taken = false;
		this.name=name;
	}
	synchronized void take(Philosopher p){
		while(taken){
	        try{     wait();   }
	        catch(InterruptedException e){
	            System.err.println(e);
	        }
		}
		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();
		}		
	}
}
 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

Избягване на взаимното блокиране

Най-често използвания подход за избягване на взаимно блокиране е да се въведе подреждане на заключваните обекти и заключването им да се извършва винаги в нарастващ ред. Това няма да промени нищо в поведението на философите от Р1 до Р4 - винаги те ще започват с лявата вилица. Философ Р5 обаче ще трябва да започне с дясната вилица - ако тя вече е заета от философ Р1 - нишката ще се блокира без да взима ресурси и ще позволи на Р4 да вземе втората вилица. В този случай най-малко една от нишките Р1,Р2,Р3 или Р4 ще има ресурси да работи и взаимно блокиране няма да се получи

 

 

Контролни въпроси