Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 5.6
Wie lange sollte der Testcase für die Aufgabe denn dauern? Mir kommen meine Werte so groß vor:
Junit Time: 23,028s
Ausgegebene Zeit: 11614679868ns
Edit:
Ich hab den Testcase mal geändert und mir Zahlen für jede Thread anzahl zeigen lassen:
Threads: 1 Time: 1994144024ns
Threads: 2 Time: 2587538320ns
Threads: 4 Time: 2658606462ns
Threads: 8 Time: 2661644120ns
Glaube nicht dass das so sein soll oder?^^
Die Laufzeit die du fuer einen Thread hast, ist ok.
Aber es sollte mit zunehmender Thread-Anzahl schon schneller werden.
Weil bei dir die Zeiten immer in etwa gleich lang sind sieht es so aus, als ob
entweder die Aufteilung der Arbeit auf die Threads noch falsch ist,
oder die Threads sich gegenseitig blockieren, weil jeder Thread das
selbe Lock will.
Also der vorgegebene JUnit Test läuft bei mir überhaupt nicht, 102410244 Nodes produziert bei mir einen OutOfMemoryError beim Erstellen des Graphen, 1024*1024 läuft aber.
Fehler im Testcase
Ich glaube im Testcase TestParallelGraphColor.java ist den Erstellern ein kleiner Fehler unterlaufen:
Sollte bei
for (int i = 1; i < 8; i *= 2) {
long start = System.nanoTime();
graphColor.colorGraph(graph, i);
Assert.assertTrue(isValidColoring(graph));
long end = System.nanoTime();
count += (end - start);
for (int j = 0; j < graph.length; j++) {
graph[i].color = -1;
}
}das nicht graph[j].color = -1; heissen?
Hast du vielleicht noch eine 32-bit JVM? Da ist der Default-Wert für die maximale Heap-Größe 64 MB.
In dem Fall erhöhe den Wert einfach mit „-Xmx“.
Im CIP sollte der Test laufen. Wenn nicht, hast du dir zu viele unnötige Objekte angelegt. 
Bei weniger Nodes hast du das Problem, dass du keinen Speedup bekommst und damit nicht feststellen kannst,
ob du eine sinnvolle multi-threaded Implementierung hast.
Du hast Recht. Der reparierte Testcase sollte in Kuerze online sein.
Na ja das Problem is halt, dass ich ja wenn ein Knoten zum färben dran ist Ihn selbst und alle Nachbarn locken muss, da ansonsten ja ein andere Thread reinfunken könnte.
Wenn es dann natürlich unglücklich läuft und ein 2ter Thread irgendeinen dieser Knoten haben will muss ich Ihm das ja verbieten oder?
Überleg dir welche genau gelockt werden müssen, wie du das locken machst etc.
Andere bekommen ja auch Code mit Speedup hin
Na ja ich teil das Array in gleichgroße Teile auf wovon jeder Thread einen bekommt. Der Thread iteriert dann über diesen Teil und schaut ob der aktuelle node schon gefärbt ist, wenn nein, dann versucht er sich selbst und alle nachbarn gelockt zu bekommen. Wenn er das kann sucht er nach der Farbe und färbt die node ein und unlocked alles was er hatte wieder. Wenn er das Zeug nicht locken kann geht er direkt zum nächsten knoten und versucht bei dem dasselbe bei diesem. Wenn das ende des Arraybereichs erreicht ist fängt er wieder von vorne an. solange bis ein zähler feststellt, dass alle knoten aus dem bereich eingefärbt sind.
Das locken mache ich über ne Extra Klasse a la Waiter bei den Philosophen.
Ich zerbreche mir schon den ganzen Tag den Kopf, habe aber keine Ahnung wo hier das Bottleneck sein könnte…
Ich würde nicht x Mal über das Array laufen, einmal reicht.
Das könnte ein Problem sein (habs aber nicht getestet).
Mit nem Waiter wuerds gehen wenn mans richtig macht.
Gibt aber noch eine andere Variante der Philosophen,
die sich für das Problem gut eignet 
Die Variante mit nur einmal drüberlaufen und beim locken warten bis alle nötigen neighbors frei sind hatte ich auch schon. Die Zahlen sind leicht unterschiedlich, aber an dem Schema, dass es mit einem Thread am schnellsten ist ändert sich nichts.
Was meinst du mit „richtig“?
Mein Waiter hat halt 2 synchronisierte methoden, beim locken testet er ob alle verfügbar sind, wenn ja nimmt er sie sich wenn nein dann returned er mit false, genau wie auf dem vorlesungsfolien eigentlich. Das warten passiert entweder gar nicht, siehe variante mit mehrfach über das array laufen, oder im thread selber.
Ansonsten könnte man es auch mit einer Ordnung machen, dann müsste man halt die Neighbors jedes mal aufsteigend sortieren, das wollte ich vermeiden, da ich dachte, dass es über nen Waiter „einfacher“ geht.
Wenn die Methode synchronisiert ist, dann warten alle Threads immer wieder an der Methode →
Du hast ein fast sequentielles Programm mit Overhead beim schlafen legen und aufwecken der Threads
am synchronized.
Damit hast du das mit dem Waiter offensichtlich nicht richtig umgesetzt ;).
Genau so wurde es aber in den Folien erklärt? Siehe Folien 05-17 und 05-18.
Wie soll das denn sonst gehen beim Waiter wenn du das locken nicht als atomare aktion machst? klar ich könnte versuchen alle zu locken mit tryLock, und sobald ich eins finde was nicht geht alles andere wieder freigeben, aber ich bezweifle, dass das schneller ist^^
Mea culpa, das war schlecht ausgedrueckt ;).
Es war „richtig“ im Sinne von „dem Problem angemessen“ gemeint.
Das auf den Folien ist ne angemessene Waiter-Lösung für das Philosophen-Problem.
Beim Philosophen-Problem geht es darum, dass kein Deadlock ensteht.
Es gibt dabei auch kein Problem mit der Effizienz, da die Zeit, die ein Philosoph mit Essen und Denken verbringt,
viel Größer ist, als die Zeit die man braucht, um am synchronized wartende Threads aufzuwecken.
Es gibt aber durchaus andere Waiter-Lösungen.
Zum Beispiel kann der Waiter Deadlocks verhindern, indem er nicht zu lässt, dass alle Gabeln gleichzeitig verteilt werden.
Das kann ich mit einem AtomicInteger erreichen der schneller ist als ein synchronized.
Beim Graphfärben sieht das Ganze anders aus. Man muss zwar immer noch Deadlocks vermeiden,
aber is kommt auch auf die Effizienz der Implementierung an. Und die ist in diesem Fall extrem davon abhängig, wie wenig
Zeit die Threads im Warte-Zustand an Locks verbringen, da die eigentliche Arbeit (das Suchen und Setzen von einem passenden Int-Wert)
nur wenig Zeit kostet.
Unter dem „Waiter“-Begriff kann man viel verstehen. Generell geht es darum,
dass irgendwo eine zentrale Stelle sitzt, die den globaler Zustand kennt und zur Problemlösung nutzt.
Auf den Folien der Vorlesung ist der globale Zustand das globale Lock (synchronized),
das frei sein muss damit der Philosoph essen kann.
Ich habs nicht ausprobiert, aber ich würde um nen Kinderriegel wetten,
dass eine tryLock-Variante schneller ist. Schliesslich hast du 2 Millionen Locks und nur 2-8 Threads.
Es kommt also eher selten vor, dass sich die Threads an einem Lock treffen und einer warten muss.
Bei dir Treffen sich die Threads 2 Millionen mal an dem synchronized und bis zu 7 warten.
Eine mögliche Waiter-Variante würde also so aussehen, dass ein Thread erst mal versucht mit tryLock alle Locks zu nehmen.
Wenn es Probleme gibt, gibt er alle genommenen Locks wieder auf und ruft dann die Waiter-Methode erneut auf, um es wieder zu versuchen.
Dabei kann es eventuell zum Verhungern von einigen Threads kommen. Da kann man dann wiederum versuchen, das Verhungern zu verhindern.
Die Frage ist, ob das nicht schon wieder so viel Aufwand verursacht, dass es sich nicht lohnt.
Jetzt verstehe ich was gemeint ist… Joa und du hättest wohl nen Kinderriegel gewonnen =P:
[m]Threads: 1 Time: 3788 ms
Threads: 2 Time: 2093 ms
Threads: 4 Time: 1795 ms
Threads: 8 Time: 1243 ms
Threads: 16 Time: 1130 ms
Threads: 32 Time: 1393 ms[/m]
Das scheint mir schon eher richtig auszusehen^^ auch besonders, dass bei 32 Threads der Overhead von einplanen und einlasten der Threads die ganze Sache wieder langsamer macht =)
Muss man sich eig. um das Befüllen der neighbour listen bei den Knoten selbst kümmern, denn bei mir sind einige leer wenn ich die Testcases laufen lass !?!
Die getFreeColor übergebene ArrayList darf man modifizieren oder?
Nein, die Nachbarlisten brauchst du nicht fuellen.
Der Graph der gefaerbt werden soll wird zufaellig
generiert und es kann vorkommen, dass manche
Knoten keine Nachbarn haben.
Ich weiss nicht, was du vorhast, aber getFreeColor selbst muss an den Knoten
eigentlich nichts aendern.