Probleme mit Random und Threads

[port29]

Hallo,

heute hat ein Kumpel mich um Hilfe gebeten. In der Uni hat er eine Aufgabe bekommen und diese auch bestmöglich gelöst. Die Aufgabe ist zwar "dumm", doch wir sind zufällig auf ein interessantes Phänomen gestoßen.

Die Aufgabe war es, Threads generieren zu lassen, die eine Last erzeugen und diese 30 Sekunden halten. In dem konkreten Programm erzeugt mein Kumpel die Last, indem er pi berechnet:

1
2
3
4
5
6
7
8
9
        int n = 310000000;                          
                
        int counter = 0;                            
        for(int i = 0; i<n; i++){                   
 
            double x = rand.nextDouble();
            double y = rand.nextDouble();
            if(x*x+y*y <= 1) counter++;
        }

Wie sinnvoll der Quelltext jetzt ist, sei nun mal dahingestellt. Es steht fest, dass wenn man den Code ausführt, er bei ihm 35 Sekunden läuft und bei mir 23. Die gleiche Laufzeit hat das Programm auch, wenn die Berechnung in einem extra Thread durchgeführt wird.

Jetzt lasse ich den gleichen Code in zwei Threads parallel ablaufen.

Vorhersage:
- Worst Case Laufzeit 23sek*2 + Overhead = 50sek
- Best Case 23 sek

Und die 23 Sekunden habe ich auch erwartet. Denn der Rechner hatte noch drei CPU Kerne, die er verwenden konnte. In der Realität sah ich aber etwas anderes. Im Task Manager konnte ich beobachten, wie die Auslastung der CPUs hochging. Die Berechnung war nach 150sek zu Ende. Und die Rechenzeit steigt exponentiell mit der anzahl der Threads an.

1 Thread = 23 sek
2 Threads = 151 sek
3 Threads = 442 sek

Als ich den Double Aufruf rausgenommen habe, hatte ich die erwarteten Resultate. Kann mir von euch jemand sagen, wieso ich so ein Verhalten bekomme?

[deepthroat]

Hi.

Kannst du mal den kompletten Quelltext hier posten?

Meine Vermutung wäre, das alle Threads die gleiche rand Variable verwenden.

Gruß

[port29]

Meine Vermutung wäre, das alle Threads die gleiche rand Variable verwenden.

Hi,

danke für den Tipp. Das Problem war tatsächlich:

1
private static Random rand = new Random();

bzw. Math.random() in dem Original Quelltext.

Dennoch kann ich dann trotzdem nicht verstehen, woher denn nun die überflüssige Last kam.

Wenn ich rand statisch deklariere, welcher Thread ist dann für rand zuständig?

[deepthroat]

Hi,

danke für den Tipp. Das Problem war tatsächlich:

1
private static Random rand = new Random();

bzw. Math.random() in dem Original Quelltext.

Dennoch kann ich dann trotzdem nicht verstehen, woher denn nun die überflüssige Last kam.

Wenn ich rand statisch deklariere, welcher Thread ist dann für rand zuständig?

Nun, alle Threads "teilen" sich die Variable, d.h. alle sind dafür zuständig. Java sorgt allerdings dafür, das der Zugriff auf die Variable synchronisiert wird. Je mehr Threads verwendet werden desto höher ist die Zahl der Kollisionen beim Zugriff.

Gruß

[port29]

Nun, alle Threads "teilen" sich die Variable, d.h. alle sind dafür zuständig. Java sorgt allerdings dafür, das der Zugriff auf die Variable synchronisiert wird. Je mehr Threads verwendet werden desto höher ist die Zahl der Kollisionen beim Zugriff.

Ich muss ehrlich zugeben, dass ich aus der ASM Welt komme und nicht daran gewöhnt bin, dass mir irgendeine VM dazwischenfunkt. Und der Zufallsgenerator ist für mich auch nur etwas, was ich lesen kann. Deshalb ist - aus meiner Sicht - keine Synchronisation notwendig. Aber da Java es so haben möchte.....

Was ich aber trotzdem nicht verstehe, ist wie die Kollisionen umgangen werden. Okay, wenn ich irgendwelche Bus Systeme implementiere, dann ziehen sich alle am Konflikt teilnehmenden Teilnehmer zurück und warten eine zufällige Zeit. Dann versuchen die es noch einmal. Hier bei Threads wird wohl ein Thread ein Lock gesetzt haben und die anderen haben einfach keinen Zugriff. Doch wieso habe ich trotzdem eine Last auf den Prozessoren?

[deepthroat]

Ich muss ehrlich zugeben, dass ich aus der ASM Welt komme und nicht daran gewöhnt bin, dass mir irgendeine VM dazwischenfunkt. Und der Zufallsgenerator ist für mich auch nur etwas, was ich lesen kann. Deshalb ist - aus meiner Sicht - keine Synchronisation notwendig. Aber da Java es so haben möchte.....

Nein, der Zufallsgenerator beinhaltet einen Zustand (den Random Seed), deshalb muss der Zugriff synchronisiert werden.

Was ich aber trotzdem nicht verstehe, ist wie die Kollisionen umgangen werden. Okay, wenn ich irgendwelche Bus Systeme implementiere, dann ziehen sich alle am Konflikt teilnehmenden Teilnehmer zurück und warten eine zufällige Zeit. Dann versuchen die es noch einmal. Hier bei Threads wird wohl ein Thread ein Lock gesetzt haben und die anderen haben einfach keinen Zugriff. Doch wieso habe ich trotzdem eine Last auf den Prozessoren?

Ja, bei statischen Attributen wird ein Lock auf die Klasse gesetzt. Häufig wird dabei "aktives Warten" verwendet, d.h. die Threads schlafen nicht eine gewisse Zeit, sondern fragen in einer Schleife ständig den Lock ab. Das würde dann die CPU-Last erklären.

Gruß

[RedWing]

Hallo,

Und der Zufallsgenerator ist für mich auch nur etwas, was ich lesen kann. Deshalb ist - aus meiner Sicht - keine Synchronisation notwendig. Aber da Java es so haben möchte.....

Es wird eben nicht nur lesend zugegriffen da bei einem Aufruf von nextDouble ja ein neuer Zufallswert berechnet wird. Durch eine evtl. auftretende Raise Condition könnte die deterministische Berechnung der Folge von Pseudozufallszahlen verfälscht werden und somit ist hier imo eine Synchronisation erforderlich.

Was ich aber trotzdem nicht verstehe, ist wie die Kollisionen umgangen werden. Okay, wenn ich irgendwelche Bus Systeme implementiere, dann ziehen sich alle am Konflikt teilnehmenden Teilnehmer zurück und warten eine zufällige Zeit. Dann versuchen die es noch einmal. Hier bei Threads wird wohl ein Thread ein Lock gesetzt haben und die anderen haben einfach keinen Zugriff. Doch wieso habe ich trotzdem eine Last auf den Prozessoren?

Um einen wechselseitigen Ausschluss garantieren zu können ist auch ein nicht unerheblicher Aufwand an Verwaltung von Threads erforderlich. Bspw. müssen Algorithmen ablaufen die eine Fairness aller beteiligten Threads garantieren usw. Das schlägt sich nat. auf die Laufzeit eines Programmes nieder.

//edit da war ich wohl zu spät

Gruß,
RedWing