5 mal langsamer ist ein wenig viel, kommt aber auch auf deinen Rechner an.
Auf meinem Rechner sinds etwa 6s mit MCS-Lock und 5.4s mit TCAS.
Man braucht im unlock() compareAndSet.
Ist vielleicht deine SortedList noch zu grobgranular gelockt?
Was hast du mit den Futures vor? Die Aufgabe ist so gedacht, dass ihr
die atomaren Instruktionen, die auf dem Angabenblatt stehen nutzt, d.h.
compareAndSet() und getAndSet().
Danke nachdem ich meine 12 locks im code nochmal kritisch zur Disposition gestellt habe läufts jetzt dann doch in 4,6 statt 63 Sekunden. 
Also bei mir dauert das ganze irgendwie TCAS 10,8 zu MCS 63 Sekunden, bei 4 Threads und n = 8192 * 8.
Interessanterweise ist mein CAS mit 10,6 sogar schneller als mein TCAS… Habe ich das mit dem TCAS vielleicht falsch verstanden? ich habe die überprüfung ob das lock wieder frei ist dabei mit [m]get[/m] gemacht und erst wenn das [m]get[/m] ok sagt versucht er ein [m]compareandswap[/m]
Wie oft locked Ihr etwas in der SortedListImpl? ich habe 3 [m]lock[/m] und 5 [m]unlock[/m], wobei natürlich 2 [m]unlock[/m] von 2 anderen ausgeschlossen werden.
Hmm also bei mir ist TCAS schneller als CAS. Aber beheb erstmal dein 63sek Problem vielleicht wird dann auch der TCAS schneller im Vergleich zum CAS. Da ich selber auch ca 63 sek hatte denke ich mal, daß du das gleiche Problem hast: Deine locks passen nicht.
Bei mir war es so, daß ich 2 zeilen im Code zunächst nicht ganz verstanden habe und für überflüssig hielt. Aber als ich dann meine locks überdacht habe wurden sie mir klar und halfen mir die Idee dahinter zu erkennen und die locks richtig zu setzen.
…
} else {
node = prev.next;
continue;
}
…
Also mir ist schon klar was diese Zeilen da machen… meine locks sind immer nur direkt vor vergleichen und eventuellen änderunden an den verglichenen dingen, damit kein anderer Thread in the Read-Write reinfunken kann…
Sag mir mal lieber wie viele [m]lock[/m] aufrufe du in der [m]add[/m] hast? vielleicht habe ich ja einen Denkfehler und locke was was ich gar nicht brauche…
EDIT: AHA! eine Sache habe ich gefunden =P die hing auch mit dem was du geschrieben hast zusammen, aber vor allem hiermit:
prev = node;
node = node.next;
Jetzt braucht mein CAS 3,3 - 3,8, TCAS 3,1 - 3,8 und MCS 7,5 - 7,8. An diesem Puntk glaube ich nichtmehr, dass das mit der ListImpls zu tun hat sondern eher mit den Locks selber, wie oben bereits geschrieben:
Habe ich das mit dem TCAS vielleicht falsch verstanden? ich habe die überprüfung ob das lock wieder frei ist dabei mit [m]get [/m]gemacht und erst wenn das get ok sagt versucht er ein [m]compareandswap[/m]
Interessant ist auch, died verhältnismäßige Diskrepanz zwischen deinem MCS und meinem, im Verhältnis zum CAS und TCAS
Die Idee von TCAS hast du richtig verstanden.
Wieviele atomare Instruktionen hast du denn im lock() und im unlock()
beim MCSLock?
Ich denke dass du mit atomaren Instruktionen nur die „Zugriffe“ auf tail meinst:
Im [m]lock[/m] habe ich ein [m]getAndSet[/m].
Im [m]unlock[/m] ein [m]compareAndSet[/m].
Ansonsten nur ein paar [m]if[/m]s, eine [m]while [/m]im [m]unlock [/m]und einige zuweisungen, und natürlich [m]throws [/m]für die [m]IllegalMonitorStateExceptions [/m]=P
Edit: im [m]lock[/m] natürlich auch noch ne [m]while[/m] woops =P
Ich meinte saemtliche getAndSets/compareAndSets, die du verwendest.
Aber deiner Beschreibung nach hast du es sehr wahrscheinlich so implementiert,
wie wir und das vorgestellt haben. 
Irgend eine Idee warum ich dann bei CAS und TCAS schneller, dafür bei der MCS langsamer als Ekkelin bin? Prozessor ist ein i5-3570k wenn das was hilft =P
Habt ihr beiden es denn auf der selben Maschine getestet?
Wenn nein, dann sind die unterschiedlichen CPUs der Grund.
Wie habt ihr das Warten realisiert? Genügt der Aufruf von tail.wait() ?
Egal was du in der Aufgabe mit wait() vor hast, es ist falsch 
Einfach so lange „nichts“ tun, bis sich U eingetragen hat?
/* Bitte löschen, hab absoluten Schmarrn geschrieben. =D */
Hmm, meint ihr 25s (CAS) - 37s (MCS) sind bei einem älteren schwachbrünstigen DualCore-Rechner noch ok? Oder ist meine Liste noch zu grobgranular?
Glaube schon…
Mein E8400 (Core 2 Duo, 2x3GHz) hat auch knapp mehr als 15 Sekunden gebraucht, für MCS nochmal bissl länger.
Hab auch einen E8400 und damit läuft testSortedList in ~7 sec unter verwendung von MCSLock. CASLock und TCASLock brauchen ~5 sec.
Betriebssystem ist Gentoo Linux 64 bit. Java 1.7.0_21