# Deadlock-Prevention



## Wang (3. Feb 2011)

Hallo,

die Lösung zur folgenden Aufgabe ist vorhanden (siehe unten), aber ich habe leider dennoch einige Schwierigkeiten:

--
Betrachten Sie die folgende Klasse:


```
public class Box
{
	private int content;
	
	synchronized int getContent()
	{
		return content;
	}
	
	synchronized void setContent(int v)
	{
		content = v;
	}
	
	synchronized void swapContent(Box other)
	{
		int c = getContent();
		int o = other.getContent();
		this.setContent(o);
		other.setContent(c);
	}
}
```

a. Welches Problem kann auftreten, wenn zwei oder mehr Threads sich zwei Instanzen dieser Klasse teilen?

b. Gehen Sie davon aus, dass zwei Threads T1 und T2 Zugriff auf zwei Instanzen a und b der Klasse Box besitzen. Geben Sie ein Beispiel für die Abfolge des Aufrufs der Methode 
	
	
	
	





```
swapContent()
```
 an, die das obige Problem provoziert.
Verwenden Sie dazu die folgende Notation:

```
<Thread>: <Methodenaufruf>
```

c. Finden Sie eine Möglichkeit, das Auftreten dieses Problems auszuschließen! Geben Sie den entsprechenden modifizierten Quellcode dazu an.
*Hinweis:*
Sie müssen zur Lösung dieses Problems eine Ordnung auf den Instanzen der Klasse Box erzwingen.
--
--
Lösung:
a) Deadlock

b)


```
Thread1			Thread2
a.swapContent(b)	b.swapContent(a)
a.getContent()		b.getContent()
b.getContent()		a.getContent()
```

c)


```
public void swapContent(Box other)
{
	if(other==this) return;
	else if (System.identifyHashCode(this) < System.identifyHash(other))
		this.doSwapContent(other);
	else
		other.doSwapContent(this);
}
```
--

Ich sehe hier leider nicht, wie eine Deadlock-Situation entstehen kann und deshalb ist mir die b) überhaupt nicht klar.

Der Code bei der c) scheint einige Leichtsinnsfehler zu beinhalten; davon mal abgesehen verstehe ich das Prinzip dahinter nicht ganz. Mit other==this wird überprüft, ob der übergebene Paramater auf das gleiche Objekt zeigt. Falls ja, wird nichts zurückgegeben. Warum eigentlich?


Hoffe Ihr seht hier mehr als ich und bedanke mich auf jeden Fall für Eure Hilfe

Gruß
Wang


----------



## Marco13 (3. Feb 2011)

a) bzw. b) sind vielleicht hier http://www.java-forum.org/java-basics-anfaenger-themen/111249-threads-wait-notify.html#post714806 erklärt.

c sieht seltsam aus :autsch: Dass nichts gewappt werden muss, wenn die beiden Objekte gleich== sind, sollte eigentlich klar sein, aber das mit dem hashCode ist suspekt... Funktioniert vielleicht, aber ... ich find's komisch :bahnhof:


----------



## tfa (3. Feb 2011)

Marco13 hat gesagt.:


> aber das mit dem hashCode ist suspekt... Funktioniert vielleicht, aber ... ich find's komisch :bahnhof:


Der Trick ist, dass die Threads 1 und 2 die beiden Objekte a und b in der selben Reihenfolge abfragen und nicht über kreuz. So kann es keinen Deadlock geben.


----------



## Wang (3. Feb 2011)

Marco13 hat gesagt.:


> a) bzw. b) sind vielleicht hier http://www.java-forum.org/java-basics-anfaenger-themen/111249-threads-wait-notify.html#post714806 erklärt.



Danke Marco. Die Erklärung dort trifft es 1:1. In meiner Aufgabe war ich total verwundert, wie hier ein Deadlock auftreten kann, denn ein Beispiel aus einem Java-Buch war da total anders (verständlicher) gelagert und die synchronized-Methoden benutzten sleep() und notify().


----------



## Marco13 (3. Feb 2011)

Die Intention is klar ... einerseits könnte man es fast als "elegant" bezeichnen (zumindest aber als "trickreich"), ich persönlich würde aber einfach nicht auf die Idee kommen, zwei identityHashCodes in dieser Form zu verleichen... Ich meine, dass das wohl schwer in eine allgemeine "best practice" zu übersetzen ist, aber für das swap im speziellen könnte es OK sein...


----------



## Wang (3. Feb 2011)

tfa hat gesagt.:


> Der Trick ist, dass die Threads 1 und 2 die beiden Objekte a und b in der selben Reihenfolge abfragen und nicht über kreuz. So kann es keinen Deadlock geben.



Irgendwie verstehe ich das noch nicht... Das Objekt, das zuerst angelegt wurde (hier: a) besitzt einen niedrigeren Hash-Wert als das Objekt, das später angelegt wurde (hier: b)?

Falls ja, sehe ich noch nicht, wie das einen Deadlock verhindern kann? ???:L

P.S. Solche theoretischen Aufgaben sind echt das Schlimmste was es gibt...


----------



## Marco13 (3. Feb 2011)

Nein, die haben irgendwelche hashCodes - aber mit an Sicherheit grenzender Wahrscheinlichkeit haben sie _unterschiedliche_ hashCodes. Das entscheidende ist nicht, in welcher Reihenfolge sie benutzt werden, sondern dass sie überall in der gleichen Reihenfolge benutzt werden.


----------



## tfa (3. Feb 2011)

Wang hat gesagt.:


> Irgendwie verstehe ich das noch nicht... Das Objekt, das zuerst angelegt wurde (hier: a) besitzt einen niedrigeren Hash-Wert als das Objekt, das später angelegt wurde (hier: b)?
> 
> Falls ja, sehe ich noch nicht, wie das einen Deadlock verhindern kann? ???:L
> 
> P.S. Solche theoretischen Aufgaben sind echt das Schlimmste was es gibt...



a und b haben unterschiedliche IdentityHashcodes - wie die aussehen oder zustande kommen ist erstmal uninteressant.

Ohne den Trick ruft T1 den Getter von a auf und hält somit das Lock auf a.
T2 ruft gleichzeitig den Getter von b auf und lockt b.
Jetzt will T1  b.getContent() aufrufen, braucht dafür aber das Lock auf b, das T2 hält. T1 muss warten.
Gleichzeitig will T2 a.getContent() aufrufen, braucht dafür aber das Lock auf a, das T1 hält. T2 muss warten.
T1 und T2 warten also aufeinander bis in alle Ewigkeit.

Mit dem Trick rufen T1 und T2 gleichzeitig a.swapContent(b), und nicht einer a.swapContent(b) und der andere b.swapContent(a). Das funktioniert immer, da die gesamte Methode synchronisiert ist und so von einem Thread komplett abgearbeitet wird, bevor der nächste dran ist.


----------



## Wang (3. Feb 2011)

Also interessiert der Hash-Wert eines Objektes gar nicht und die Abfrage "WENN Hash-Wert x < als Has-Wert y, dann gehe so vor SONST gehe anders vor" dient nur dazu, immer nach der gleichen Ordnung vorzugehen(?).

Ich sehe aber leider noch immer nicht den springenden Punkt, warum damit verhindert wird, dass ein Deadlock entsteht (die a) bzw. b) sind mir dank Deiner Erklärung im verlinkten Beitrag klar). ???:L

EDIT:
War mit dem Tippen zu langsam, lese mir gerade die Erklärung aus dem Beitrag darüber durch.


----------



## Wang (3. Feb 2011)

Um mir sicher zu sein, dass ich es verstanden habe, frage ich besser direkt nach bzw. beschreibe die Problematik in einer Zusammenfassung, so wie ich sie dank Eurer Hilfe jetzt sehe:

Die Lösung zur b) weiter unten mal etwas seziert:


```
Thread1			Thread2
a.swapContent(b)	b.swapContent(a)
a.getContent()		b.getContent()
b.getContent()		a.getContent()
```

Das große Problem ist, dass es zwei Objekte einer Klasse gibt und jedes logischerweise über die Methode "swapContent" verfügt; "swapContent" besitzt intern einen Getter für die entsprechende Variable seines eigenes Objektes und einen Getter, mit dem auf die entsprechende Variable des anderen Objektes zugegriffen wird.

Dadurch, dass es zwei Objekte der Klasse Box gibt, nutzt das synchronized der Methode "swapContent" nichts, sodass 
	
	
	
	





```
a.swapContent(b)
```
 und 
	
	
	
	





```
b.swapContent(a)
```
 bewirken, dass zwei gleiche Methoden gestartet werden (natürlich von unterschiedlichen Objekten). Diese Methoden greifen intern jeweils sowohl auf das eigene Objekt wie aber auch auf das andere Objekt quasi gleichzeitig zu.

```
a.swapContent(b)
```
 besitzt den Lock auf a und 
	
	
	
	





```
b.swapContent(a)
```
 besitzt den Lock auf b. 
	
	
	
	





```
a.swapContent(b)
```
 kann mit seinem internen Getter nicht auf b zugreifen und 
	
	
	
	





```
b.swapContent(a)
```
 kann mit seinem internen Getter nicht auf a zugreifen. ==> Deadlock

Wenn meine Argumentation wirklich stimmen sollte, hätte doch für die b) als Lösung bereits genügt


```
Thread1			Thread2
a.swapContent(b)	b.swapContent(a)
```

denn die beiden Zeilen darunter werden niemals erreicht?


Zur c):
Der Groschen will bei mir immer noch nicht fallen. 
Die Methode aus der Lösung heißt ja wieder "swapContent" und darin wird jetzt auf eine Methode namens "doSwapContent" zugegriffen. Ich denke mal mit "doSwapContent" ist die ursprüngliche Methode aus der Angabe namens "swapContent" gemeint...?

Ich bin mal ein kleines Beispiel durchgegangen. Angenommen a hat den Hashcode 2 und b hat den Hashcode 1 und man ruft 
	
	
	
	





```
a.swapContent(b)
```
 auf. Dann wird doch der else-Zweig angesprungen und somit "b.doSwapContent(a)", was doch zu einem ganz anderen Effekt führt, als man mit der Anfangsmethode 
	
	
	
	





```
a.swapContent(b)
```
 beabsichtigt hat. ???:L


Vielen Dank für Eure Hilfe!!!


----------



## tfa (3. Feb 2011)

> denn die beiden Zeilen darunter werden niemals erreicht?


Nein, denn der Deaklock tritt erst auf, wenn T1 auf b zugreift bzw.T2 auf a. Und dass passiert innerhalb der swap-Methode beim Aufruf der Getter.




> Die Methode aus der Lösung heißt ja wieder "swapContent" und darin wird jetzt auf eine Methode namens "doSwapContent" zugegriffen. Ich denke mal mit "doSwapContent" ist die ursprüngliche Methode aus der Angabe namens "swapContent" gemeint...?


Richtig. Beachte, dass swapContent nicht synchronisiert ist. doSwapContent sollte es aber sein.



> Ich bin mal ein kleines Beispiel durchgegangen. Angenommen a hat den Hashcode 2 und b hat den Hashcode 1 und man ruft a.swapContent(b)  auf. Dann wird doch der else-Zweig angesprungen und somit "b.doSwapContent(a)", was doch zu einem ganz anderen Effekt führt, als man mit der Anfangsmethode a.swapContent(b)  beabsichtigt hat.


Die swap-Methode tauscht ja nur die Werte der beiden Objekte. a.swapContent(b) und b.swapContent(a) machen also genau das gleiche - im Endergebnis.


----------



## Wang (3. Feb 2011)

tfa hat gesagt.:


> Nein, denn der Deaklock tritt erst auf, wenn T1 auf b zugreift bzw.T2 auf a. Und dass passiert innerhalb der swap-Methode beim Aufruf der Getter.



Also meinen die beiden Zeilen aus der Lösung zu b) die internen Getter von "swapContent"?


```
a.getContent()		b.getContent()
b.getContent()		a.getContent()
```


Thanks!


----------



## tfa (3. Feb 2011)

Ja. Die Getter, die innerhalb von swapContent() aufgerufen werden.


----------

