# [Threads] Gleichzeitiger Zugriff auf eine LinkedList



## Caracasa (27. Mrz 2008)

Hallo Zusammen,

habe dieses Forum erst gestern im Netz entdeckt und bin guter Dinge hier in Zukunft einen Teil meiner Freizeit zu verbringen. 

Ich programmiere derzeit einen Arkanoid-Klon und habe mich dafür entschieden, die *Berechnung der Physik* und das *Zeichnen der Ausgabe* (OpenGL /JOGL) auf *zwei Threads* aufzuteilen.

Beide Threads greifen auf eine *Singleton-Klasse "GameWorld"* zu, in der sich unter anderem *zwei von LinkedList abgeleitete Listen* für die Verwaltung der Partikeleffekte und der "Spielsteine" befindet.

Die *Physikberechnung und die OGL-Ausgabe sind jeweils Methoden dieser zwei Klassen/Listen* und werden von den Threads aufgerufen - das Rendern über den Standard-JOGL-Thread (meine Hauptklasse), die Physikberechnungen über einen eigenen Thread, der mit wait() periodisch durchlaufen wird.

Das Problem

Das Problem habt ihr wahrscheinlich schon erkannt. Durchläufe der Listen geschehen oft gleichzeitig, weil beide Methoden der Listen-klassen parallel aufgerufen werden. Das äußert sich auf auf meinen zwei Rechnern unterschiedlich stark z.B. durch falsches Entfernen von Steinen / Einfärben getroffener Steine. 

Abhilfe sollte da wohl das Monitor-Konzept (synchronized) von Java schaffen. Allerdings habe ich Schwierigkeiten, dieses korrekt auf mein Problem anzuwenden, weil ich den Zugriff auf die Objekte innerhalb der for-Schleifen an mehreren Stellen nicht zentral in eine synchronized Methode packen kann. 

Soweit zumindest mein Verständnis des Problems.

Habe ich evtl. einen Fehler im Konzept oder nur keinen Peil, wie ich es richtig anstellen muss?

Könnt ihr mir an diesem Punkt weiterhelfen?

Heute Nachmittag könnte ich auch meinen Code entsprechend aufbereiten und hier posten, falls das Problem noch nicht verständlich ist.

Viele Grüße,
Christian



Hier noch zwei Beispiele wie die Liste in den beiden nebenläufigen Methoden durchlaufen wird:



```
public void draw(GL gl) {
		for (int i = 0; i <= super.size()-1; i++) {	
			Particle par = (Particle)super.get(i);
			par.draw(gl);
		}
		
	}
	public void process() {
		for (int i = 0; i <= super.size()-1; i++) {	
			Particle par = (Particle)super.get(i);	
		        //Berechne Position etc. des Partikels
                        // ...
                }
       }
```


----------



## maki (27. Mrz 2008)

Änderst du die Listen?

Nebenbei bemerkt, sollte man Collections und Unterklassen eigentlich nicht per get(...) durchlaufen, Iteratoren sind dafür besser geeignet und bei LinkedList viel schneller.

Musst du deine eigene List Implmentierung verwenden?

Sieh dir doch mal das hier an:
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#synchronizedCollection(java.util.Collection)


----------



## Marco13 (27. Mrz 2008)

Hm. Wenn du mit einer for(i..)-Schleife  durch die Listen läust, verstehe ich nicht, warum du eine LinkedList verwendest... Da hat der indizierte Zugriff ja eine Laufzeit von O(n), d.h. wenn du "viele" Steine hast, wird das ganze vmtl. schrecklich langsam. Also, wenn du nicht ganz gezielt eine _Linked_List brauchst (und ich wüßte kaum, wofür du die brauchen solltest) solltest du eine allgemeine List verwenden, und als Implementierung z.B. eine ArrayList. 

Eine List kann man thread-safe machen, wie hier
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#synchronizedList(java.util.List)
beschrieben. Falls die geposteten Schleifen Codestücke gleichzeitig durchlaufen können werden sollen (was heikel sein kann, weil man nie genau weiß, welcher Zustand gerade gemalt wird), müßte man sich aber was einfallen lassen - es KÖNNTE dann sinnvoll sein, z.B. für's Zeichnen eine Kopie der Liste zu erstellen (dann braucht man die Synchronization auch nicht mehr, nur ggf. beim Erstellen der Kopie). ...


----------



## Caracasa (27. Mrz 2008)

Danke für eure Antworten.

Die Methode draw(GL gl) liest jedes einzelne Objekt der Liste und zeichnet es in den Buffer.
Die Methode process() liest und verändert jedes einzelne Objekt (addiert z.B. die Beschleunigung der Gravitation)

Ich habe meine Methoden nun konsequent *auf Iteratoren umgestellt.* Diese ganzen von _Collection_ abgeleiteten Klassen (Listen & Co) und den damit verbundenen Konzepten sind mir noch ziemlich neu, aber ich gelobe Besserung. 

_LinkedList_ ist mir beim Programmieren einfach über den Weg gelaufen - _ArrayList_ scheint mir aber wirklich besser geeignet, da ich bisher nur sequentiell durch die Daten muss. Danke, wird umgehend geändert.

Die Kollisionen der beiden Threads äußern sich beim intensiven Gebrauch von Iteratoren nun als Exceptions und nicht mehr als geringfügiges Fehlverhalten.

_SynchronizedList_ scheint da wirklich die Lösung dafür zu sein:


```
public class ParticleManager { 
	List content;

	//[...]

	ParticleManager() {
		content = Collections.synchronizedList(new ArrayList<Particle>());
	}

	//[...]

	public synchronized void draw(GL gl) {
		Iterator<Particle> i = content.iterator(); 
		
		while (i.hasNext())
			i.next().draw(gl);		
	}

	public synchronized void process() {	
		Iterator<Particle> i = content.iterator();
		
		while (i.hasNext()) {
			Particle par = i.next();
			
			//[...]
	      		//Verändere Partikel
		}
	}
}
```

Eine Exception hatte ich jetzt nach einem kurzen Test noch nicht, aber das muss ja nichts heißen, 

Ist der Code so in Ordnung oder muss ich in den Methoden noch mit _synchronized(content) {}_ arbeiten?

An dieser Stelle schon einmal ein herzliches "Dankeschön"!


----------



## maki (27. Mrz 2008)

> Ist der Code so in Ordnung oder muss ich in den Methoden noch mit synchronized(content) {} arbeiten?


IMHO ja, zumindest wenn man der Doku glaubt 

Wenn du die Liste mit einem Iterator änderst und gleichzeitig mit dem anderen Iterator durchwanderst, solltest du irgendwann eine ConcurrentModificationException bekommen, aber das kann man relativ einfach lösen:
1. Du kopierst die Liste.
oder
2. Du schreibst eine eigene List Implementierung der das egal ist.

Die 2. Lösung ist übrigens viel einfacher umzusetzen als man glaubt, sind insgesamt nur ein paar Zeilen Code 
Dafür ist es schneller, da keine Kopie erstellt werden muss.

Ansonsten: Die LinkedList nicht immer langsamer als die ArrayList.

ArrayList bietet sich an, wenn sich die Größe der Liste nicht oft ändert, und wenn man den index Basierten Zugriff benötigt (zB. get(1)).
Ansonsten ist LinkedList nicht verkehrt


----------



## Caracasa (27. Mrz 2008)

Über die Zugriffsgeschwindigkeiten der einzelnen Listen hab ich bisher einfach gesprochen:"Null Ahnung".  

Der Inhalt des _PartikelManagers_ ändert sich allerdings laufend - da sollte ich dann wohl doch auf die ArrayList verzichten oder? 

Hab ich das "Gleichzeitige Durchlaufen" nicht durch den Einsatz von _synchronizedList()_ verhindert? 

So richtig verstanden habe ich das Ganze wohl noch nicht. 

Bislang stelle ich es mir so vor, dass der Zugriff auf den Iterator solange bei Thread 1 verzögert wird, bis Thread 2 in seiner Methode den Zugriff auf die Liste beendet hat. Lieg ich da falsch? Muss ich auch um die Iteratoren einen "Monitor" basteln?

*Nachtrag:* Ich bekomme wie von dir prophezeit _ConcurrentModificationExceptions_. 

Ich versuche das ganze mal auf eigene Faust zu implementieren ... wird schon schiefgehen.  :toll:


----------



## Janus (27. Mrz 2008)

die methoden synchronized zu machen bringt dir nichts. du musst den zugriff auf die liste selbst synchronisieren.


```
// lock auf 'content' anfordern
synchronized( content )
{
  // content ist für den aktuellen thread reserviert
}
// lock aufgehoben
```

diesen synchronized block brauchst du in _beiden_ methoden.

ansonstent kannst du dir auch nochmal die lock klassen in java.util.concurrent angucken, ReentrantLock z.b.
für dein problem ist synchronized aber gut geeignet.

und achte darauf, synchronized blöcke so kurz wie möglich zu halten, um andere threads nicht unnötig lange zu blockieren.


----------



## Marco13 (27. Mrz 2008)

Caracasa hat gesagt.:
			
		

> Der Inhalt des _PartikelManagers_ ändert sich allerdings laufend - da sollte ich dann wohl doch auf die ArrayList verzichten oder?


Kommt drauf an - ist aber gut möglich: Bei einer LinkedList kann man ein einzelnes Element (wenn man einen Iterator hat, der darauf zeigt) direkt entfernen, und das hat Laufzeit O(1) (geht also immer gleich schnell, egal, wie groß die Liste ist). Wenn man aber KEINEN Iterator hat, sondern indiziert zugreifen muss, dann relativiert sich das schon wieder: Dann hat zwar das Löschen O(1), aber der Zugriff schon O(n), d.h. wenn man sowas wie 
linkedList.remove(10000);
macht, dauert das u.U. vergleichsweise lange. 

Bei einer ArrayList ist der indizierte Zugriff mit O(1) immer schnell, aber wenn man z.B. das Element mit Index 3 löscht
arrayList.remove(3);
dann müssen ALLE nachfolgenden Elemente um 1 nach vorne verschoben werden (d.h. dort hat dann der Zugriff O(1), aber das Löschen selbst O(n) :wink: )

Bei einer ArrayList gibt es aber noch einen "Trick": Wenn die Reihenfolge der Elemente egal ist, kann man auch sowas machen wie
Element lastElement = arrayList.get(arrayList.size()-1);
int indexOfElementToDelete = 3;
arrayList.set(indexOfElementToDelete, lastElement);
arrayList.remove(arrayList.size()-1);
Also das gelöschte Element immer durch das letzte Element ersetzen. (Gibt aber nicht sooo viele Anwendungsmöglichkeiten dafür)


----------



## Caracasa (28. Mrz 2008)

Ich werde mir jetzt erst einmal alle im Netz verfügbaren Informationen zu synchronized besorgen, bevor ich hier anfange zu "verschlimmbessern". Zum lustigen Herumprobieren fehlt mir einfach  die Möglichkeit die Exception bzw. den entsprechenden fehlerhaften Zugriff auf die Liste kontrolliert auszulösen.

Die Partikel werden beim Durchlauf der Liste nach Lebensdauer und nach "Aufschlägen" an der Spielfeldbegrenzung entfernt. Da das oft 30x pro Durchlauf passiert, setze ich lieber wieder auf die LinkedList. Das "Ausbessern" scheint mir da effektiver zu sein, als die Verschiebereien bei der ArrayList.


----------



## Caracasa (28. Mrz 2008)

Ich habe nun alle meine Methoden, die auf die Liste zugreifen entsprechend dem Code von Janus komplett gekapselt.

Keinerlei Probleme mehr seit diesem Zeitpunkt. 

Vielen Dank in die Runde.


----------

