[Threads] Gleichzeitiger Zugriff auf eine LinkedList

Status
Nicht offen für weitere Antworten.

Caracasa

Mitglied
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:


Code:
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
                        // ...
                }
       }
 
M

maki

Gast
Ä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

Top Contributor
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 LinkedList 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

Mitglied
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:

Code:
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"!
 
M

maki

Gast
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

Mitglied
Ü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

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

Code:
// 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

Top Contributor
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

Mitglied
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

Mitglied
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. :)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Gleichzeitiger zugriff auf ein Long über Threads Allgemeine Java-Themen 2
J 2 Threads: Gleichzeitiger Zugriff auf ein Objekt Allgemeine Java-Themen 2
rode45e Java Threads Allgemeine Java-Themen 4
M Threads Allgemeine Java-Themen 1
L Threads Threads in Chatroom Allgemeine Java-Themen 30
berserkerdq2 run-methode eines Threads so programmieren, dass 30x die Sekunde etwas ausgeführt wird. Allgemeine Java-Themen 44
berserkerdq2 Threads, wie genau läuft das in Java ab? (Ich kann Threads erstellen und nutzen, nur das Verständnis) Allgemeine Java-Themen 6
CptK Backpropagation parallelisieren: Kommunikation zwischen den Threads Allgemeine Java-Themen 7
J Eine Frage zu den Threads und Task Allgemeine Java-Themen 1
W Wieviele Threads sind sinnvoll? Allgemeine Java-Themen 8
W Alternative für Threads Allgemeine Java-Themen 6
V Threads Probleme beim Aufrufen von Methoden einer anderen Klasse (Threads) Allgemeine Java-Themen 14
T Multithreading: Wie viele Threads sollte ich erstellen? Allgemeine Java-Themen 12
G Threads vom Mainprogramm steuern Allgemeine Java-Themen 8
S BlockingQueue mit dynamischer Anpassung der Anzahl von Producer und Consumer Threads Allgemeine Java-Themen 1
x46 Threads Threads anhalten Allgemeine Java-Themen 1
J Threads verbessern die Performance NICHT ? Allgemeine Java-Themen 8
W Threads Problem Allgemeine Java-Themen 15
T Threads Tic Tac Toe mit Threads Allgemeine Java-Themen 1
M Threads über Kommandozeile Allgemeine Java-Themen 5
mrbig2017 Threads Chat Programm mit Threads? Allgemeine Java-Themen 2
J Threads - java.lang.IllegalThreadStateException Allgemeine Java-Themen 6
J Internet Broswer in Threads öffnen Allgemeine Java-Themen 1
B Threads Multithreading Threads sollen warten Allgemeine Java-Themen 12
N 1000 MQTT Messages die Sekunde - 1000 Threads erstellen ? Allgemeine Java-Themen 10
D Threads Parallel laufende Threads Allgemeine Java-Themen 4
J Unvorhersehbares Verhalten - benutze ich die falsche Bedingungsprüfung oder brauche ich Threads? Allgemeine Java-Themen 12
D Eine Forschleife mit Threads abarbeiten um es zu schneller zu machen. Ist das möglich? Allgemeine Java-Themen 20
S Wie kann ich eine kleine Stelle in meinem Code mit multiplen Threads abarbeiten..? Allgemeine Java-Themen 20
P Threads Parallelisierte DB-Abfragen mit variabler Anzahl an Threads Allgemeine Java-Themen 4
J Threads Threads Allgemeine Java-Themen 9
Viktim Threads Liste In unterschiedlichen Threads bearbeiten Allgemeine Java-Themen 23
E Threads Ausführung in Threads ist langsamer als ohne Threads Allgemeine Java-Themen 13
A Anzahl an Threads Systemweit Allgemeine Java-Themen 2
Tausendsassa Input/Output Problem mit der gleichzeitigen Ausgabe zweier Threads Allgemeine Java-Themen 8
S Alle Methodenaufrufe eines Threads notieren..? Allgemeine Java-Themen 7
M Threads JPanel eingeforen mit Threads Allgemeine Java-Themen 2
F Threads Allgemeine Java-Themen 6
F Threads Allgemeine Java-Themen 2
M Sinn von Threads? Allgemeine Java-Themen 1
J Wie erschaffe ich einen sicheren Datenaustausch zwischen Thread und Nicht-Threads Allgemeine Java-Themen 8
L Abfragen ob Threads fertig Allgemeine Java-Themen 3
P Threads Java Zugreifen Allgemeine Java-Themen 6
K Problem: Java-Klasse mit mehreren Threads als eigenen Prozess starten Allgemeine Java-Themen 3
K KeyEvent in Threads Allgemeine Java-Themen 11
V Threads Weshalb funktionieren meine Threads nicht? Allgemeine Java-Themen 2
Thallius Speicherverhalten von Properties und mehreren Threads Allgemeine Java-Themen 5
L Threads beenden Allgemeine Java-Themen 4
P Threads Threads nicht gleichzeitig starten Allgemeine Java-Themen 3
S Threads Threads werden nicht beendet Allgemeine Java-Themen 2
S Start des zweiten Threads erst nach Beenden des ersten Threads Allgemeine Java-Themen 13
N Threads statische Methoden in Threads Allgemeine Java-Themen 5
P 4 Threads in einer Methode Allgemeine Java-Themen 2
M Eclipse Mehrere Threads, mehrere Konsolen Allgemeine Java-Themen 4
OnDemand Threads und synchronized Allgemeine Java-Themen 9
R LinkedList und Threads: Strukturprobleme bez. löschen von Elementen Allgemeine Java-Themen 3
R LinkedList und Threads - welche Methode ist besser? Allgemeine Java-Themen 2
OnDemand Threads und synvhronized Allgemeine Java-Themen 2
S Problem mit Threads Allgemeine Java-Themen 1
W Threads Threads warten lassen Allgemeine Java-Themen 5
H Optimierung durch Threads Allgemeine Java-Themen 31
B Threads halten sich irgendwie auf... Allgemeine Java-Themen 6
M Threads Allgemeine Java-Themen 8
K JNI: Methoden aus unterschiedlichen Threads aufrufen Allgemeine Java-Themen 3
A Applet Alle Threads beim schließen des Applets beenden Allgemeine Java-Themen 8
A Problem mit der Synchronisierung von Threads Allgemeine Java-Themen 15
R SecurityManager für einzelne Klassen/Threads? Allgemeine Java-Themen 38
O Threads und If Befehle Allgemeine Java-Themen 7
P Threads abwechseln lassen mit wait() und notify() Allgemeine Java-Themen 2
H Sehr viele Threads effizient Verwalten Allgemeine Java-Themen 13
C Threads und Exceptions Allgemeine Java-Themen 7
H java.lang.OutOfMemoryError bei der wiederholten Erzeugng von Threads Allgemeine Java-Themen 8
S Threads Abarbeitungsstatus von Threads in Datei schreiben Allgemeine Java-Themen 2
M Zugriff zweier Threads auf diesselbe Methode Allgemeine Java-Themen 16
E Threads Sudoku Threads Allgemeine Java-Themen 8
M Java Threads - Wait Notify - Verständnisproblem Allgemeine Java-Themen 5
Gossi Threads mit unterschiedlichen Aufgaben in einer Klasse? Allgemeine Java-Themen 9
G Threads Ablauf von Threads im Spezialfall Allgemeine Java-Themen 4
V Threads bei quadcore Allgemeine Java-Themen 10
V 1000 Threads oder Iterativ? Allgemeine Java-Themen 11
4 Simple(?) Frage zu Threads Allgemeine Java-Themen 14
B Threads Game of Life - Threads Allgemeine Java-Themen 49
R Threads Exceptions von Threads abfangen im ThreadPool Allgemeine Java-Themen 5
S Threads Ende sämtlicher Threads abwarten Allgemeine Java-Themen 6
S Frage zu Threads (Sichtbarkeit und Verhalten) Allgemeine Java-Themen 11
M Java-Threads und Datentypen-Zugriffe Allgemeine Java-Themen 7
P Threads- Programming Allgemeine Java-Themen 2
G Threads Klasse Sound und Threads bleiben hängen Allgemeine Java-Themen 4
C Threads Zwei Threads greifen auf LinkedList zu. Allgemeine Java-Themen 12
M OutOfMemoryError in nebenläufigen Threads Allgemeine Java-Themen 6
M Threads dauerhafte bewegung mit threads Allgemeine Java-Themen 11
frankred Threads Auf eine Gruppe von Threads warten Allgemeine Java-Themen 11
J Eure Meinung: Threads verwenden, oder nicht? Allgemeine Java-Themen 6
K Warum wartet diese Funktion auf beenden des Threads? Allgemeine Java-Themen 3
F Mehrere Threads - ein Stack Allgemeine Java-Themen 6
O Wie kann ich das Ende eines Threads melden? Allgemeine Java-Themen 7
J Writer und Threads Allgemeine Java-Themen 2
G mehrere Threads starten/stoppen Allgemeine Java-Themen 4
E Verständnisfrage bezüglich Threads Allgemeine Java-Themen 4
K Zeitkritische Threads Allgemeine Java-Themen 14

Ähnliche Java Themen

Neue Themen


Oben