[Java] Threadanzahl regulieren

Skyo · 26. April 2011

Sehr geehrte Computerbase-freunde!

Mich beschäftigt folgendes Problem. Ich habe ein Programm geschrieben, in dem mit Quicksort (rekursive Variante) ein sehr langes Array sortiert wird. Dabei entspricht jeder erneute rekursive Aufruf dem starten eines Threads.

(Dies ist natürlich ineffizient durch den riesigen Thread-overload.)

Ich möchte dennoch untersuchen, wie sich das Programm verhält, wenn ich eine maximale Threadanzahl setze. Gibt es ein Möglichkeit, dies in Java zu kontrollieren?
(außer die Stackgröße zu verringen und damit schneller Exceptions zu werfen...)

Edit: Ich hab so eben von der Klasse Threadgroups gelesen, die die aktiven Threads zählt. Also könnte man regulieren, dass keine neuen Threads eingefügt/ erstellt werden, solange die größe überschritten wird. Per sleep? :S dann hab ich aber das Problem, das ich aufpassen muss, das nicht gleichzeitig Threads hinzugefügt werden.

Bin für jeden Tipp und Link zum weiterlesen dankbar!

der_guru · 26. April 2011

Ich denke du suchst etwas wie ein Threadpool. Da holst du dir ein Thread und wenn er nicht mehr benötigt wird gibts du ihn zurück.

Forderst du einen an, und die maximale Anzahl Threads ist bereits vergeben, dann blockiert der Aufruf.
Du kannst sowas mit commons-pool von apache.org implementieren.

Es gibt sicherlich bereits auch einige Frameworks die eine weitgehendere Implementierung bereitsstellen.

MfG

real_general · 26. April 2011

Warum setzt du nicht einfach ne Rekursionsbremse ein?

DonnyDepp · 26. April 2011

studierst du informatik?
wenn ja, dann wirst du im zweiten semester semaphoren kennenlernen.

http://de.wikipedia.org/wiki/Semaphor_(Informatik)
so arbeitet sie: http://giu.me/13-02-2008-synchronisation-in-java-teil-2-semaphore.html
und das ist die klasse: http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/Semaphore.html

ist im grunde ein simpler thread-lock, den du u.a. auch auf ne anzahl limitieren kannst.

Airbag · 26. April 2011

Skyo schrieb:
Ich möchte dennoch untersuchen, wie sich das Programm verhält, wenn ich eine maximale Threadanzahl setze. Gibt es ein Möglichkeit, dies in Java zu kontrollieren?
(außer die Stackgröße zu verringen und damit schneller Exceptions zu werfen...)

Zum Überprüfen kannst du Profiler benutzen. Für Eclipse sei mal TPTP genannt.
Außerdem bringt es effektiv nichts es zu untersuchen, außer du willst ausprobieren, ob es funktioniert.
Es liegt nämlich daran, dass Multithreading zwar schneller arbeitet, aber die Komplexitätsklasse deins Algorithmus unverändert bleibt. Dies sieht man vor allem gut, wenn man den Term der KOmplexitätsklasse für limes gegen unendlich oder ein hohes Funktionsargument laufen lässt, dass zwischen Singlethread und Quadthreading beispielweise kaum noch ein Unterschied besteht.
Sieht man perfekt an den zwei Funktionen.
f(x)= 1/4x
und
g(x)=x

Green Mamba · 26. April 2011

Ideal wäre es zudem, wenn du uns mal deinen Code zeigen würdest.

Airbag · 26. April 2011

@Green Mamba

Wenn er von einem rekursiven Quicksort spricht, kann es ja schon nicht besonders perfomant sein.

snow1 · 26. April 2011

Skyo schrieb:
Mich beschäftigt folgendes Problem. Ich habe ein Programm geschrieben, in dem mit Quicksort (rekursive Variante) ein sehr langes Array sortiert wird. Dabei entspricht jeder erneute rekursive Aufruf dem starten eines Threads.

Mehr Threads als CPUs zu starten bringt in der Regel nichts, bzw wirkt irgendwann eher kontraproduktiv, da ja immer zwischen den Threads hin und her geschalten wird. Aber ich vermute ohnehin mal, dass eher der Speicher limitieren wird...

Skyo schrieb:
Edit: Ich hab so eben von der Klasse Threadgroups gelesen, die die aktiven Threads zählt. Also könnte man regulieren, dass keine neuen Threads eingefügt/ erstellt werden, solange die größe überschritten wird. Per sleep? :S dann hab ich aber das Problem, das ich aufpassen muss, das nicht gleichzeitig Threads hinzugefügt werden.

Mit den Threadgroups kannst du dir leicht so eine Art Threadpool bauen. Damit du nicht gleichzeitig mehrere Threads startest, etc., musst du einen synchronized Abschnitt einbauen.

Airbag schrieb:
Es liegt nämlich daran, dass Multithreading zwar schneller arbeitet, aber die Komplexitätsklasse deins Algorithmus unverändert bleibt. Dies sieht man vor allem gut, wenn man den Term der KOmplexitätsklasse für limes gegen unendlich oder ein hohes Funktionsargument laufen lässt, dass zwischen Singlethread und Quadthreading beispielweise kaum noch ein Unterschied besteht.
Sieht man perfekt an den zwei Funktionen.
f(x)= 1/4x
und
g(x)=x

Wahnsinns Argument

Ob ein Algorithmus nun 5 oder 20 Minuten läuft macht also keinen Unterschied, nur weil die Algorithmen im Grenzfall gegen Unendlich ähnlich komplex sind?

Airbag · 26. April 2011

Ich glaube du verstehst mich falsch. Ich meine damit nämlich, dass ein ineffizienter Algorithmus auch mit effizienten Multithreading inperfomant bleibt. Ich habe ja nicht davon gesprochen, dass es keinen Sinn macht auf Mulithreading zu optimieren.
Außerdem habe ich nicht nur von einem Grenzfall gegen unendlich gesprochen. Gerade das Beispiel vom TE zeigt, dass es bezüglich vieler Gesichtspunkte sehr ineffizient ist. Nicht nur bei der Zeit.
Natürlich ist aber auch oft der Fall, dass es für ein Problem keinen besseren Algorithmus gibt als einen mit exponentieller Komplexität. (Z.b ein leicht abgeändertes Problem zum Djikstra-Algorithmus )

ehr Threads als CPUs zu starten bringt in der Regel nichts, bzw wirkt irgendwann eher kontraproduktiv, da ja immer zwischen den Threads hin und her geschalten wird. Aber ich vermute ohnehin mal, dass eher der Speicher limitieren wird...

Klar wenn der Overhead zu groß wird.

Tumbleweed · 26. April 2011

Zur eigentlichen Frage (und Stichwort Thread Pool):

Code:

ExecutorService threadPool = Executors.newFixedThreadPool(20);

Könnte interessant sein.

Executors bietet auch noch weitere Arten an.

snow1 · 26. April 2011

Airbag schrieb:
Ich glaube du verstehst mich falsch. Ich meine damit nämlich, dass ein ineffizienter Algorithmus auch mit effizienten Multithreading inperfomant bleibt.

Aber die Rede ist vom Quicksort, der im Average Case in O(n log n) liegt und damit wohl nicht zu den ineffizienten Algorithmen gehört.

Des weiteren kann man Quicksort gut parallelisieren und dabei ist linearer Speedup ist möglich.

Im Grunde würde ich eher den Quicksort parallelisieren, denn dann hast du immer eine Beschleunigung ggü dem sequentiellen Quicksort, auch wenn du nur eine Liste zu sortieren hast.

Airbag · 26. April 2011

Es ist Ansichtssache. Es kann auch n^2 sein .
http://de.wikipedia.org/wiki/Quicksort

Es ist aber schwer zu sagen, welchen Ansatz er implementiert hat. Wenn es der naive Ansatz ist, ist der Algorithmus recht ineffizient.

ice-breaker · 26. April 2011

Tumbleweed schrieb:
Zur eigentlichen Frage (und Stichwort Thread Pool):

Code:

ExecutorService threadPool = Executors.newFixedThreadPool(20);

Könnte interessant sein. Executors bietet auch noch weitere Arten an.

ja, Executors sind sind für den Anwendungsfall eine optimale Lösung, bzw. sogar sehr oft.

Airbag schrieb:
Es ist Ansichtssache. Es kann auch n^2 sein .
http://de.wikipedia.org/wiki/Quicksort

Auf die O(n^2) kommst du aber nur, wenn die Liste schon vorsortiert ist.
Nämlich genau dann, wenn dein Pivot-Element die Liste in 2 Teile mit 1 Element und n-1 Elementen teilt.

Skyo · 26. April 2011

-- hier stand der code -- wird bearbeitet ...

ice-breaker · 26. April 2011

Du hast aber schon gesehen, dass die submit-Methode ein Runnable-Objekt möchte und kein Thread?

Nein, du musst keine Threads erzeugen, das macht der alles intern.

Skyo · 26. April 2011

--> Code aktualisiert, Executor vorhanden!

Tatsache, submit will runnables, vielleicht liegt es daran, dass meine testmain nicht mehr terminiert...

(Sortierung erfolgt auch nciht mekr korrekt...)

Da stellt sich die Frage, was will Threads?

Ich meine Threads implementierieren die Runnable Schnittstelle... :S Außerdem bin ich auf die Joinfunktion der Threads angewiesen :S

NEUANSATZ per Semaphore, mal sehen was ich schaffe!

ice-breaker · 26. April 2011

Wenn du es auf den Executorservice umbaust, musst du schon die Logik ändern, ist doch klar, Thread.join() geht nicht mehr, du musst dir also etwas anderes einfallen lassen, und vor allem auch keine Semaphoren die blockieren.
Alles sollte Non-Blocking laufen.

DonnyDepp · 27. April 2011

wieso non blocking?
wenn er auf die threads warten muss, dann sollten die auch blockieren, wenn die semaphore alle token vergeben hat.
ich schätze er will ja einen massiv parallelen algorithmus für eine bestimmte anzahl prozessoren simulieren.
somit werden logischerweise bei betrachtung des schedulings einige passagen durch das blockierende verhalten sequentiell.

aber dein hauptthread sollte auch auf die semaphore warten, ohne sie zu belegen.
sonst erzeugst du alle parallelen threads, wovon sich die meisten schlafen legen und du hast die trotzdem im speicher.

ice-breaker · 27. April 2011

DonnyDepp schrieb:
wieso non blocking?
wenn er auf die threads warten muss, dann sollten die auch blockieren, wenn die semaphore alle token vergeben hat.

weil er dann wieder das Problem hat, dass 1 Task 1 Thread benötigt, seine benötigte Threadanzahl also unendlich hoch wird und er das gleiche Problem wie im Anfangspost hat.
Zudem wird sein Programm sich bei einem beschränkten Thread-Pool dann einfach aufhängen, wenn er mehr blockierende Threads haben wird, als Threads für den Pool vorgesehen sind.

Der Schlüssel zu effizientem Multi-Threading sind Non-Blocking-Operationen und Asynchronität.

BullshitBingo · 27. April 2011

Der Einsatz von Semaphoren ist nicht zu empfehlen, da die paarweise Verwendung der P/V - Operationen bei allgemeinen Semaphoren sehr fehleranfällig ist. Verwende lieber einen Monitor und für wechselseitigen Ausschluss Mutex bzw. binären Semaphor.

[Java] Threadanzahl regulieren

Ensign

Lieutenant

Captain

Lt. Commander

Fleet Admiral

Green Mamba

Gast

Fleet Admiral

Lt. Junior Grade

Fleet Admiral

Captain

Lt. Junior Grade

Fleet Admiral

Commodore

Ensign

Commodore

Ensign

Commodore

Lt. Commander

Commodore

BullshitBingo

Gast

Ähnliche Themen