Proseminar Java Threads

Deadlock und Fairness

• 1. Deadlock

• 2. Lockstarvation

Deadlock

• Was ist Deadlock ( Beispiel 1)

• Verhinderung von Deaklock

• Korrektur von Beispiel 1 mit Lockhierachie

• Korrektur von Beispiel 1 mit Busyflag

• anderer Typ von Deadlock

Deadlock

ist ein Status, wobei die Treads zyklisch auf den Zugriff auf ein Objekt warten und die gesamte Prozesse deswegen nicht weiter gehen kann.

public class Kitchen{

static measuringCup theCup;

static Bowl theBowl;

public void makeOmelette(9{

synchronized (theBowl){

Eggs e[ ]=getBrokenEggs();

theBowl.putIngredients(e);

theBowl.mix();

synchronized (theCup){

theCup.measureOut(theBowl);

}

}

}

}

public void makeCookie(){ synchronized (theCup){ theCup.measureOut(1, theFlour); synchronized (theBowl){ theBowl.putIngredients(theCup); theBowl.mix(); } } }

Verhinderung von Deadlock

Regel 1: synchronized Methode darf nicht wieder synchronized Methode aufrufen.zwei Nachteile:

1. unprakisch

2. nicht erforderlich

in den Fall, wenn das synchronized Methode, wir aufrufen wollen, nicht mehr weitere synchronized Methode aufrufen.

Regel 2: Lock Hierarchie zu bilden

Class Hierarchy

M easu rin gC up V ec to r B ow l

O b jec t

Lock Hierachy

th eB ig g erC u p

th eC up

th eB ow l

Das Prinzip von Lockhierarchie:

Die Locks von den Objekte sind in dieser Reihenfolge zu bekommen. Damit sollte die Zyklisch-wartend-Status nicht geschehen.

public void makeCookie(){ synchronized (theBowl){ synchronized (theCup){ theCup.measureOut(1, theFlour); theBowl.putIngredients(theCup); theBowl.mix(); } }}

Korrekur von Beispiel 1 mit Lock Hierarchie

Anwendung von Busyflagpublic class Kitchen{ static MeasuringCup theCup; static Bowl theBowl; static BusyFlag theCupFlag, theBowlFlag;

public void makeCookie(){ theCupFlag.getBusyFlag(); theCup.measureOut (1, theFlour); theBowlFlag.getBusyFlag(); theBowl.putIngredients(theCup); theBowl.mix(); theBowlFlag.freeBusyFlag(); theCupFlag.freeBusyFlag();}

public void makeOmelette(){ theBowlFlag.getBusyFlag(); Eggs e[]=getBroeknEggs(); theBowl.putIngredients(e); theBowl.mix(); theCupFlag.getBusyFlag(); theCup.measureOut(theBowl); theCupFlag.freeBusyFlag(); theBowlFlag.freeBusyFlag(); }}

Das ist aber nur eine Umschreibung mit BusyFlag Class undhat das vorher auftretende Problem nicht gelöst.

public void makeCookie(){ theCupFlag.getBusyFlag(); theCup.measureOut (1, theFlour); if (theBowlFlag.trgGetBusyFlag()){ theBowl.putIngredients(theCup); theBowl.mix(); theBowlFlag.freeBusyFlag(); } else { //... do something else.. } theCupFlag.freeBusyFlag();}

Weiter mit Busyflags

else{ WaxedPaper thePaper=new WaxedPaper(); thePaper.emptyOnto(theCup); theCupFlag.freeBusyFlag(); theBowlFlag.getBusyFlag(); theBowl.putIngredients (thePaper); theBowl.mix(); theBowlFlag.freeBusyFlag(); }}

public class makeCookie(){ WaxedPaper thePaper=new WaxedPaper(); synchronized(theCup){ thecup.measureOut(1, theFlour); thePaper.emptyOnto(theCup); } synchronized(theBowl){ theBowl.putIngredients(thePaper); theBowl.mix(); }}

Die selbe Funktion aber mit Synchronized Block

Another Typ von Deadlock

• Thread stirbt während er noch das Lock hat

• In Java befreit Thread das Lock so gar in den Fall von Exception

• Busy-Flag Class verhält sich aber anders

• Fix von Busy-Flag Class mit try/finally scope

public void makeCookie(){ try{ flag.getBusy(); //...do some work... }finally{ flag.freeBusyFlag(); }}

Fix von Busy-Flag Class mit try/finally scope:

Nachteil :

Es kann unerwartete Situation verursachen.Zum Beispiel: Normalerweise macht das makeCookie() methoddie Schüssel sauber, aber wenn die Exception passiert und deswegen die Schüssel nicht sauber gemacht worden ist.Macht anderer Thread sein Gericht mit dem nicht sauber gemachten Schüsse.

Lockstarvation• Lockstarvation: Wenn ein bestimmter Thread

versucht, ein Lock zu bekommen, aber es geling ihm nie, denn anderer Thread hat das Lock. (mit Beispiel 2)

• Wann muß man auf Lockstarvation berücksichtigen

• Fix des Beispiels

• Reader-Writer Locks

• Priority-Inverting Locks

T0 T1 T2 T3 T4 T5 T6

InsychronizedBlock

Out ofsychronizedBlock

Time

500ms 500ms

Call graph of synchronized methods; thread A repeatedly calls a synchronized method.

T0 Thread A und Thread B sind im Runable Zustand, und Thread A läuftT1 Thread A läuft noch, und fordert das Objekt LockT2 Ein Scheduling Event passiert wegen Timeslicing-Mechanismus. Das lässt Thread B laufen.T3 Kurz nach Thread B fängt an zu laufen, versucht er in Synchronized-Block zu gehen. Das Versuch macht Thread B in blocked Zustand, was ein Scheduling-Event verursacht, so dass Thread A wieder „ the running thread“ wird.

Beispiel 2

T4 Thread A verlässt das Synchronized-Block. Thread B kommt in Runnable-Zustand, das ist aber kein Scheduling Event, so bleibt Thread A weiter laufen.

T5 Thread A geht wieder in Synchronized-Block und bekommt das Lock. B bleibt in Runnable-Zustand. T6 Thread B läuft wieder und versucht sofort, in das Synchronized-Block zu gehen, aber Thread A hat das Lock noch, so dass Thread A wieder in Blocked-Zustand gehen. Thread A läuft wieder und es ist genau wie in T3.

Hintergrund vom Beispiel 2:

die round-robin scheduling events geschehen während Thread A das Lock für das Synchronized-Block hat.

Das heißt noch: es gibt keine „fair“ Reihenfolge für die Threads, das Lock nacheinander zu erwerben.

Wann muß man Lockstarvation berücksichtigen?

• Einige Threads versuchen, das selbe Lock zu bekommen

• Die Zwischenergebnisse interessiert uns

• Alle Threads haben die selben Priorität

• Sie sind in einem Round-Robin Scheduler.

Ein Beispiel,

damit die Treads in „fair“ Reihenfolge das Lock bekommen können.

import java.util.*;

public class QueuedLock { private Vector waiters; private Thread current=null;

public QueuedLock(){ waiters=new Vector(); } public synchronized void acquire(){ Thread me=Thread.currentThread(); waiters.addElement(me); while ((Thread) waiters.elementAt(0) != me) try { wait(); } catch (Exception e){} current = me;}

public synchronized void release(){ if (Tread.currentThread() !=current)= throw new IllgealArgumentException(„QueuedLock not held“); waiters.removeElementAt(0); notifyAll();}}

public class DBAcess{ privat QueueLock lock; public DBAcess(){ lock=new QueuedLock(); } public Object read(){ Object o; try{ lock.acquire(); o=someMethodThatReturnsData(); return o; } finally{ lock.release(); }

public void write (Object o){ try { lock.acquire(); someMethodThatSendsData(o); } finally{ lock.release(); }}}

Reader-Writer Locks

• Motivation: Daten können gleichzeitig von mehreren Threads gelesen werden, aber nur von einem geschrieben werden.

• Es gibt nun Methode: lockRead(), lockWriter() und unlock().

• Die Information von Threads ist in RWNode zu speichern.

• Alle Thread, die das Lock erwerben wollen, befinden sich in Vector Waiter in einer bestimmten Reihefolge

• Lesen kann nur stattfinden, wenn kein Thread, der schreiben möchten, schon vor diesem Thread in Waiter steht.

• Mehrere Threads können gleichzeitig lesen, wenn die die obige Bedingung erfüllen.

• Schreiben kann nur stattfinden, wenn dieser Thread überhaupt der erster Thread in Waiter ist.

Import java.util.*;//Zum Speicher der Imformation des Threadsclass RWNOde { static final int READER=0; static final int WRITER=1; Thread t; int state; int nAcquires; RWNode (Thread t, int state){ this.t=t; this.state=state; nAcquires=0; }}

//wo diese Reihefolge von Threads gespeichert mit mehrereMethodepublic class RWLock { private Vector waiters;//Verwendet für Leselock private int firstWriter(){ Enumeration e; int index; for (index=0; e=watiers.elements();e.hasMoreElememts(); index++){ RWNode node=(RWNode) e.nextElement(); if (node.state==RWNode.WRITER) return index; } return Integer.MAX_VALUE;}

private int getIndex(Thread t){ Enumeration e; int index; for (index=0, e=waiters.elements; e.hasMoreElements(); index++){ RWNode node=(RWNode) e.nextElement(); íf (node.t==t) return index) } return -1;}

public RWLock(){ waiters=new Vector();}

//prüfe, ob noch Writer-Thread davor in Waiter steht, wenn nicht, bekommt der das Lesenlock.(Dabei wird geprüft, ob es überhaupt noch Reader-Threadgibt)public synchronized void lockRead(){ RWNode node; Thread me=Thread.currentThread(); int index = getIndex(me); if (index==-1) { node=new RWNode(me, RWNode.READEER); waiters.addElement(node); } else node=(RWNode) waiters.elementAt(index);

while (getIndex(me) > firstWriter()){ try{ wait(); }catch(Exception e) {}}node.nAcquires++;}

//prüft, ob dieser Writer-Thread der erster in Waiter ist, wenn ja,bekommt der das Writerlock.public synchronized void lockWrite(){ RWNode node; Thread me=Thread.currentThread(); int index=getIndex(me); if (index==-1){ node=new RWNode(me, RWNode.WRITER); waiters.addElement(node); }else{ node=(RWNode)waiters.elementAt(index); if (node.state==RWNode.READER) throw new IllegalArgumentException(„Upgrade lock“); node.state=RWNode.WRITER;}

while (getIndex(me)!=0){ try{ wait(); } catch(Exception e){}}node.nAcquires++;}

//Readlock und Writelock werden mit diesem Methode gelöstpublic synchronized void unlock(){ RWNode node; Thread me= Thread.currentThread(); int index; index=getIndex(me); if (index> firstWriter()) throw new IllegalArgumentException(„Lock not held“); node=(RWNode) waiters.elementAt(index); node.nAcquires--; if (node.nAcquires==0){ waiters.removeElementAt(index); notifyAll(); }}}

Priority-Inverting LocksPrioritätvererbung mit Busyflags

public class PriorityBusyFlag extends BusyFlag{

protected int currentPriority;

public synchronized void getBusyFlag(){

while (tryGetBusyFlag()==false){

Thread preOwner=getBusyFlagOwner();

try

{ int curP=Thread.currentThread().getPriority();

if curP>prevOwner.getPriority()){

prevOwner.setPriority(curP);

}

wait(); } catch(Exception e){} }}public synchronized boolean tryGetBusyFlag(){ boolean succeed=super.tryGetBusyFlag(); if (succeed) currentPriority=Thread.currentThread().getPriority(); return succeed;}public synchronized void freeBusyFlag(){ if (getBusyFlagOwner==Thread.currentThread()){ super.freeBusyFlag(); if (getBusyFlagOwner()==null){ Thread.currentThread().setPriority(currentPriority); notifyAll();

} } }}