Thema: Locking innerhalb des Kernels

[FlashBurn]

@svenska

Die Arbeiten die du aufgezählt hast, sind ja alles Arbeiten wo die Locks überhaupt nicht interessieren Um es mal überspitzt zu sagen, bei den Arbeiten kann mir die Performance des OS scheiß egal sein, aber spätestens beim Kompilieren + Video (siehe Linux ) ist es dann nicht mehr (ich weiß das es in dem Fall der Scheduler war).

Im reinen Userspace musst du für einen Mutex nicht durch den Kernel, wenn er in der C-Bibliothek (auch Userspace) korrekt implementiert ist.

Wie das? Ein Mutex ist doch praktisch ne Semaphore mit nem Counter von 1, oder? Und sowas kann man nur eigentlich nur sinnvoll im Kernel machen, weil du einen Lock brauchst um Queue und Counter zu schützen und du willst ja Threads in die Queue packen und dann schlafen legen (spätestens da musst du in den Kernel).

Ich glaube, du überschätzt da den Einfluss ganz gewaltig.

Sehr wahrscheinlich

Aber was ist dann z.B. mit Interrupts, die würden ja dann auch blockiert werden, nur weil irgend ein Thread was im Kernel macht, oder? Muss nicht auch die Video-Ausgabe irgendwann in den Kernel (also 24 mal in der Sekunde)?

Warum soll ich einen langsamen O(n)-Algorithmus nehmen, wenn doch mein O(n^3)-Algorithmus für reale Werte von n viel, viel schneller ist?

Die Einstellung gefällt mir, sehe ich nämlich genauso

Um zu verdeutlichen das O() nichts über die Laufzeit aussagt, sage ich immer auch ein O(n^3)-Algo kann schneller sein als ein O(1)-Algo!

[erik.vikinger]

Hallo,


@ Svenska + FlashBurn :
Das mit den Locks müsste man einfach mal anhand einer konkreten Aufgabenstellung benchmarken aber solange das keiner vernünftig macht können wir hier noch lange theoretisch streiten. Der Nachteil von Locks wird dadurch bestimmt wie viele Interessenten gleichzeitig da ran wollen und für wie lange die es normalerweise halten (für beides muss man den Worst-Case genauso wie den Average-Case analysieren). Ersteres kann man z.B. mit feiner verteilten Locks erheblich reduzieren und am Zweiten kann man mit algorithmischen bzw. technischen Tricks arbeiten. Bei beidem hat man IMHO viel Potential so das Locks noch längst nicht zum alten Eisen gehören.
Einen zuverlässigen Lock kann man auf allen aktuellen CPUs auch nur allein im User-Mode bauen (egal wie dämlich der Scheduler auch sein mag) aber wenn dann noch Features wie schlafen lassen der Threads dazu kommen soll benötigt man eben die Hilfe des Kernels. Auch performt so ein reiner User-Mode-Lock nicht besonders gut wenn der Scheduler nicht mitspielt bzw. nicht zur Mitarbeit gezwungen werden kann (z.B. über das IE-Flag).

Wie das? LL Lädt doch nur die Speicherzelle in der Tailpointer drinsteht und nicht den Knoten (bzw. dessen next-Zeiger) und garantiert mir, mich beim SC (auf &Tail) zu warnen, wenn sich da was verändert hat? Wie schließt das aus, dass zwei den gleichen Tail lesen und dann weitermachen und das Tail->next kaputtmachen?

Bei einem herkömmlichen LL hast Du recht aber normalerweise weiß das LL doch ob es die Hardware-Überwachung erfolgreich einrichten konnte oder nicht nur meldet dies eben nicht an den CPU-Kern weiter und genau an der Stelle möchte ich ansetzen indem mein LL-Befehl ebenso ein Flag nur dann setzt wenn es erfolgreich war. Das bedeutet das hier bereits beim LL erkennbar ist ob der Hardware-Lock mir gehört oder nicht, deswegen ja auch das while zum spinnen (inklusive PAUSE zum Last und Strom sparen).

Mir scheint, dass ich dann LL/SC nicht verstehe, wenn das korrekt sein soll Soweit ich weiß tut das nur auf eine Speicherzelle, und &Tail und Tail->next sind aber zwei verschiedene.

Nein, ich denke ich hab nicht deutlich genug auf meinen kleinen Zusatztrick hingewiesen.

Laufwerke sind dank NCQ und modernen COW-Dateisystemen durchaus parallel ansprechbar.

Wie lange predige ich das nun schon? Und wie viele nehmen das ernst?
Moderne Hardware ist hochgradig parallelisierbar und das trifft nicht nur auf AHCI-SATA-Controller sondern auch auf viele andere zu.


Grüße
Erik

[bluecode]

Nein, ich denke ich hab nicht deutlich genug auf meinen kleinen Zusatztrick hingewiesen.

Worin genau besteht der Trick? Ein Lock für den ges. Speicher? Das ist dann äquivalent zu einem Spinlock der alles lockt... das saugt bestimmt Performance. Ansonsten versteh ich immernoch nicht, welche Semantik dein LL bzw. dein SC hat und warum niemand anders eine nicht ge'LL'te Speicherzelle überschreiben kann.

[erik.vikinger]

Hallo,

Ansonsten versteh ich immernoch nicht, welche Semantik dein LL bzw. dein SC hat und warum niemand anders eine nicht ge'LL'te Speicherzelle überschreiben kann.

Jeder kann eine ge'LL'te Speicherzelle normal lesen und auch überschreiben (beim Überschrieben würde dann das SC fehlschlagen aber das Lesen hat keinen Effekt) aber niemand kann eine solche Zelle ebenfalls mit einem LL erfolgreich locken weil die Hardware ja schon einen Lock für diese Zelle kennt. Mein Trick besteht darin das dieses Erfolgreich/Nicht-Erfolgreich der SW mitgeteilt wird (der Returnwert der im while ausgewertet wird) die drauf passend reagieren kann.
Wie viele solcher Locks es parallel geben kann hängt davon ab was der Memory-Controller kann (es kann also passieren das LL fehlschlägt obwohl die gewünschte Zelle nicht gelockt ist und das nur weil das Limit des Memory-Controllers an gleichzeitigen Locks erschöpft ist, in den ersten ARMv6-Implementierungen war dieses Limit auch 1 was für ein Single-CPU-System ja schon mal reicht aber heutige ARM-SoCs können da meines Wissens nach mehr). Der Nachteil vom klassischen LL ist der das dieser Fehlschlag nicht für die Software sichtbar ist so das die immer erst beim SC merkt ob sie erfolgreich war und daher immer probieren muss anstatt das System (und die Stromrechnung) mit spinnen (und Pausen) zu entlasten.

Ich hoffe ich habe mich jetzt deutlich genug ausgedrückt, wenn nicht dann Bitte noch mal fragen.


Grüße
Erik

[bluecode]

D.h. in dem Fall (bzw. in jedem von Interesse?) ist es äquivalent zu einem Spinlock? Dann ist es aber nicht sehr interessant, weil es genausoviel Parallelität bietet wie ebendieser.
Mir scheint das auch nicht wirklich irgendwas mit LL/SC zu tun zu haben: Soweit ich weiß können mehrere ein LL auf die gleiche Zelle machen und der der zuerst schreibt hat halt dann gewonnen. Das ist ein ganz anderes Konzept imho.

[erik.vikinger]

Hallo,

D.h. in dem Fall (bzw. in jedem von Interesse?) ist es äquivalent zu einem Spinlock?

Ja, eigentlich immer, nur das hier für den Lock nicht ein bestimmter Wert steht sondern das man eine ganz normale Variable mit beliebigen Inhalt benutzen kann (in meinem Beispiel die Variable Tail die ein Pointer ist der nie ungültig ist, das spart mindestens die zusätzlichen Speicherzugriffe für eine dedizierte Lock-Variable) und auch das ABA-Problem zuverlässig ausgeschlossen ist (beim Schreiben wird nicht der Inhalt verglichen sondern nur der SC-Schreibvorgang ansich beendet den Lock in der Hardware).

Dann ist es aber nicht sehr interessant, weil es genausoviel Parallelität bietet wie ebendieser.

Aber dafür oft schneller verarbeitet werden kann als z.B. eine Lösung mit CAS, mit meinem Zusatztrick ist das sogar immer schneller als CAS bzw. zumindest schonender weil gespinnt werden kann.

Mir scheint das auch nicht wirklich irgendwas mit LL/SC zu tun zu haben: Soweit ich weiß können mehrere ein LL auf die gleiche Zelle machen und der der zuerst schreibt hat halt dann gewonnen. Das ist ein ganz anderes Konzept imho.

Nein, auch ein normales LL richtet einen Lock in der Hardware ein (der CPU-Kern bekommt darauf eine Art Tocken als zusätzliche Antwort des LL den er dann beim SC wieder mitliefern muss damit der Lock-Mechanismus im Memory-Controller auch erkennt ob der SC vom richtigen CPU-Kern kommt, das dürfte einer der Gründe sein warum auf keiner CPU LL/SC verschachtelbar ist) und der dessen LL zuerst vom Memory-Controller verarbeitet wird (der Memory-Controller muss zwangsläufig serialisieren) hat gewonnen. Dieser Lock wird nur von einem SC aufgehoben wenn das SC von der richtigen CPU kommt (und nur dieses SC meldet auch Erfolgreich zurück wogegen alle anderen SCs verworfen werden (also den Speicher nicht verändern) und auch ein Nicht-Erfolgreich zurückmelden) oder von einem normalen Schreibzugriff (egal von welcher CPU). Wenn so ein Lock von einem normalen Schreibbefehl zerstört wird ist das doof weil dann gar keiner gewonnen hat, daher möchte ich das so ein normaler Schreibzugriff immer mit einer Exception endet damit der Programmierer hier keine unerlaubten Dinge anstellen kann (es gibt IMHO auch keinen Grund eine solche Variable die als Lock benutzt wird mit anderen Speicherzugriffsbefehlen als LL und SC zu bearbeiten).

Ich weiß das Du Dich nicht für die Hardware interessierst aber vielleicht solltest Du Dir mal die AXI-Spezifikation (kann man bei ARM irgendwo runterladen) durchlesen um zu sehen wie bei diesen speziellen Befehlen die Kommunikation zwischen CPU und Memory-Controller abläuft. Wimre gibt es in den ARM-CPU-Manuals auch eine gute Beschreibung dieser Befehle und wie diese intern arbeiten.

In dem Hazard-Pointer-Dokument von diesem Michael wird auch angemeckert das keine CPU einen VL-Befehl anbietet, dieser würde nur prüfen ob es auf einer bestimmten Speicherzelle momentan einen Lock gibt und ermöglicht so eine Art vorgelagerte Schleife zum spinnen. Das wäre dann immerhin schon mal ein kleiner Vorgeschmack auf einen LL-Befehl der eine Erfolgreich-Meldung bietet und könnte zumindest dabei Helfen die System-Last (und den Energiebedarf) zu senken.


Grüße
Erik

[bluecode]

ABA-Problem zuverlässig ausgeschlossen ist (beim Schreiben wird nicht der Inhalt verglichen sondern nur der SC-Schreibvorgang ansich beendet den Lock in der Hardware).

Das ABA-Problem hat man doch erst wenn überhaupt jemand parallel schreiben darf, wenn das niemand darf (weil er auch vorher ein LL macht, per Algorithmus) kommt das Problem auch nicht auf. Insofern "vermeidet" es das ABA-Problem genauso wie ein Spinlock das tut und zwar dadurch, dass man die Parallelität einschränkt.

edit: Wobei, vielleicht wäre es sinnvoll zu sehen wie du ein Dequeue machst, falls da doch kein LL auf die selbe Speicherstelle zuerst kommt, könnte es interessanter werden.

Dann ist es aber nicht sehr interessant, weil es genausoviel Parallelität bietet wie ebendieser.

Aber dafür oft schneller verarbeitet werden kann als z.B. eine Lösung mit CAS, mit meinem Zusatztrick ist das sogar immer schneller als CAS bzw. zumindest schonender weil gespinnt werden kann.

Wieso kann man bei CAS denn nicht spinnen?

Nein, auch ein normales LL richtet einen Lock in der Hardware ein

Gut, dann ist LL/SC nicht wirklich interessant, weil es die Parallelität genauso wie ein Spinlock einschränkt. Bietet also "intellektuell" nichts neues, nur einen "schickeren Spinlock". Wobei das nicht so abwertend sein soll, wie es da steht. Was ich damit meine ist, dass mein Interessengebiet eher Algorithmik & Datenstrukturen ist und aus der Warte gesehen ist das halt nichts Neues, sondern lässt sich unter (natürlich performancerelevantes) "Implementierungsdetail" abhacken.
edit: Zumindest wenn es sich effektiv nicht anders als ein Spinlock nutzen lässt. Ich schließe hier halt von dem Beispiel oben auf die Allgemeinheit.

[erik.vikinger]

Hallo,

Insofern "vermeidet" es das ABA-Problem genauso wie ein Spinlock das tut und zwar dadurch, dass man die Parallelität einschränkt.

Ist richtig, aber das klassische LL/SC und auch CAS erlauben effektiv auch nicht mehr Parallelität weil ja nur einer wirklich vorwärts kommt (eben der der zum Schluss erfährt ob er gewonnen hat).

edit: Wobei, vielleicht wäre es sinnvoll zu sehen wie du ein Dequeue machst, falls da doch kein LL auf die selbe Speicherstelle zuerst kommt, könnte es interessanter werden.

Gerne, aber da müsstest Du Bitte etwas deutlicher beschreiben was Du genau möchtest.

Wieso kann man bei CAS denn nicht spinnen?

Das hat Du doch selber erklärt und korrekt begründet, man muss immer neu versuchen (also intensiv arbeiten) bis man tatsächlich erfolgreich ist. Für mich bedeutet spinnen das man wartet und nicht arbeitet.

Bietet also "intellektuell" nichts neues, nur einen "schickeren Spinlock"....

Im wesentlichen hast Du Recht, ja.

edit: Zumindest wenn es sich effektiv nicht anders als ein Spinlock nutzen lässt. Ich schließe hier halt von dem Beispiel oben auf die Allgemeinheit.

Ich bin schon der Meinung das man mit LL/SC auch etwas über den simplen Spin-Lock hinaus gehen kann, deswegen möchte ich ja auch immer noch wissen was Du für Ideen mit mehreren LL/SC-Pärchen kennst.


Grüße
Erik

[bluecode]

edit: Wobei, vielleicht wäre es sinnvoll zu sehen wie du ein Dequeue machst, falls da doch kein LL auf die selbe Speicherstelle zuerst kommt, könnte es interessanter werden.

Gerne, aber da müsstest Du Bitte etwas deutlicher beschreiben was Du genau möchtest.

Naja, bisher war das nur ein Enqueue, ich möchte aber auch manchmal was aus einer Queue rausholen

Wieso kann man bei CAS denn nicht spinnen?

Das hat Du doch selber erklärt und korrekt begründet, man muss immer neu versuchen (also intensiv arbeiten) bis man tatsächlich erfolgreich ist. Für mich bedeutet spinnen das man wartet und nicht arbeitet.

Muss man nicht, ich sehe nur nicht den Sinn dahinter, denn sobald ich die Änderung sehe (das CAS fehlschlägt), ist der andere bereits fertig und ich hab eine Chance, wenn ich es sofort wieder versuche.

edit: Zumindest wenn es sich effektiv nicht anders als ein Spinlock nutzen lässt. Ich schließe hier halt von dem Beispiel oben auf die Allgemeinheit.

Ich bin schon der Meinung das man mit LL/SC auch etwas über den simplen Spin-Lock hinaus gehen kann, deswegen möchte ich ja auch immer noch wissen was Du für Ideen mit mehreren LL/SC-Pärchen kennst.

Da ich wohl falsch verstanden habe, was LL/SC macht (mir ist irgendwie schleierhaft, was das in der Form soll), ist das irgendwie schwierig. Alle Algorithmen die ich kenne verwenden nativ natürlich CAS. Und wenn du die so komplett umschreibst, dass sie effektiv einen Spinlock drumrumbauen, dann ist das irgendwie wenig sinnvoll...

[erik.vikinger]

Hallo,

Naja, bisher war das nur ein Enqueue, ich möchte aber auch manchmal was aus einer Queue rausholen

Nichts leichter als das.
Ich verwende noch mal den selben Code und hänge nur das Dequeue dran, eigentlich müsste man da noch prüfen ob die Queue überhaupt etwas enthält usw. aber fürs grobe Verständnis des Prinzips sollte es reichen :

Code: [Auswählen]

struct Node
{
  T value;
  Node* next;
};

// global
// einfach verkettete Liste die bei Head anfängt
Node* Tail;
Node* Head;

void Enqueue(T value)
{
  Node* NewNode = new Node();
  NewNode->value = value;  NewNode->next = null;

  Node* LocalTail;

  IRQ_Disable();

  // probieren bis Tail mir gehört :
  while ( LL(&Tail,&LocalTail) != true ) { IRQ_Enable(); Pause(); IRQ_Disable(); }

  if (LocalTail->next != null)
   { PANIC(); }

  // anhängen :
  LocalTail->next = NewNode;

  // Tail weitersetzen :
  if ( CS(&Tail,NewNode) != true )
   { PANIC(); }

  IRQ_Enable();
}

T Dequeue(void)
{
  Node* OldNode;

  IRQ_Disable();

  // probieren bis Head mir gehört :
  while ( LL(&Head,&OldNode) != true ) { IRQ_Enable(); Pause(); IRQ_Disable(); }

  // Head weitersetzen :
  if ( CS(&Head,OldNode->next) != true )
   { PANIC(); }

  IRQ_Enable();

  // Value extrahieren :
  T value = OldNode->value;

  // Node freigeben :
  delete(OldNode);

  // Value abliefern :
  return value;
}Ich hoffe das ist einigermaßen verständlich. Das Prüfen auf PANIC könnte man auch einfach weg lassen aber ich las es mal drin um zu zeigen wie der Zustand der einzelnen Variablen sein sollte.
Das ist übrigens so nicht mit dem normalen LL/SC-Pärchen machbar, jenes fällt eher in die CAS-Methodik, mein Beispiel-Code hier funktioniert nur wenn LL auch Erfolgreich/Nicht-Erfolgreich an die Software melden kann. Auf jeden Fall sollte man deutlich erkennen wie enorm kurz der gelockte Code jeweils ist, klar scaliert das nicht unbedingt perfekt (in Richtung mehr CPUs) aber wenn jemand einen Lock-Freien-Algorithmus kennt der bei irgendeiner Anzahl an parallelen Versuchen besser performt dann würde ich den gerne mal sehen.
Bluecodes Code von Heute Morgen ist auf vergleichbarer Hardware auf jeden Fall langsamer. Für die einzelnen Threads selber geht es nicht schneller weil ja trotzdem nur einer nach dem anderen zum Zug kommen kann (die Variante ist zwar lock-free aber nicht wait-free) und jeder Versuch an sich erzeugt schon eine recht hohe Last (immer 3 atomic_read und gelegentlich 1 CAS + 2 oder 3 bedingte Verzweigungen pro Schleifendurchlauf). Ich behaupte einfach mal das diese Variante bei absolut keiner Anzahl an parallelen Interessenten (2 bis ∞) schneller ist als meine Variante (noch nicht einmal gleich schnell, selbst wenn ich die Pause weg lassen würde).

Muss man nicht....

Richtig, man muss nicht sofort neu probieren aber man muss auf jeden Fall probieren um überhaupt zu erfahren ob man überhaupt eine Chance hatte. Bei einem Spinlock kann man warten ohne eine größere Last zu erzeugen (die muss man nur ein einziges mal generieren wenn man den Lock tatsächlich hat) wogegen man bei der Lock-Frei-Variante ständig probieren (und Last erzeugen) muss. Klar kann man da Pausen einbauen aber probieren muss man trotzdem.

Da ich wohl falsch verstanden habe, was LL/SC macht (mir ist irgendwie schleierhaft, was das in der Form soll), ist das irgendwie schwierig. Alle Algorithmen die ich kenne verwenden nativ natürlich CAS. Und wenn du die so komplett umschreibst, dass sie effektiv einen Spinlock drumrumbauen, dann ist das irgendwie wenig sinnvoll...

Hm, schreibst Du da jetzt über meine Spezial-Variante von LL/SC oder über das normale (und bereits in vielen CPUs existierende) LL/SC-Konzept?


Grüße
Erik

[bluecode]

Das ist übrigens so nicht mit dem normalen LL/SC-Pärchen machbar

Jo, das war mir schon bewusst.

mein Beispiel-Code hier funktioniert nur wenn LL auch Erfolgreich/Nicht-Erfolgreich an die Software melden kann

Das viel wesentlichere ist doch eigentlich, dass dein SC im Enqueue niemals fehlschlägt, sobald das passiert, wird es nämlich falsch. Wie gut man das in Hardware implementieren kann kA.
Aber wie gesagt, das ist zwar schick, aber es hilft halt nichts bei der Diskussion über real existierende Hardware, da will man weder Interrupts deaktivieren (das ist wohl unbedingt notwendig, damit SC nicht fehlschlägt), noch hat man so ein LL/SC.

Auf jeden Fall sollte man deutlich erkennen wie enorm kurz der gelockte Code jeweils ist, klar scaliert das nicht unbedingt perfekt (in Richtung mehr CPUs) aber wenn jemand einen Lock-Freien-Algorithmus kennt der bei irgendeiner Anzahl an parallelen Versuchen besser performt dann würde ich den gerne mal sehen.

Ich kann halt nur auf die Paper verweisen. Da testen die wohl ausschließlich die Datenstruktur (also massiv parallel) und vergleichen mit lock-basierten Varianten (oder älteren lockfreien Algorithmen) und die Ergebnisse sind einiges besser.

Bluecodes Code von Heute Morgen ist auf vergleichbarer Hardware auf jeden Fall langsamer.

Das ist eine sehr gewagte Aussage, wo es doch diese "vergleichbare Hardware" nur in deiner Imagination gibt.

Für die einzelnen Threads selber geht es nicht schneller weil ja trotzdem nur einer nach dem anderen zum Zug kommen kann (die Variante ist zwar lock-free aber nicht wait-free)

Aber jeder ist vorbereitet.

Muss man nicht....

Richtig, man muss nicht sofort neu probieren aber man muss auf jeden Fall probieren um überhaupt zu erfahren ob man überhaupt eine Chance hatte. Bei einem Spinlock kann man warten ohne eine größere Last zu erzeugen (die muss man nur ein einziges mal generieren wenn man den Lock tatsächlich hat) wogegen man bei der Lock-Frei-Variante ständig probieren (und Last erzeugen) muss. Klar kann man da Pausen einbauen aber probieren muss man trotzdem.

Bei einem Spinlock muss man doch auch probieren zu schreiben (auf den Lock). Wie relevant ist es da wenn ich zusätzlich noch ein bisschen auf dem L1 Cache alleine rumarbeite (beim enqueue ist das ja meine Referenz)? Ernsthaft, ich seh einfach keine "relevante" Last die da mehr erzeugt wird. (Aber ganz eigentlich will ich darüber auch garnicht reden, nicht mein Gebiet, ich sehe Performancegraphen die sagen es ist besser, das reicht mir vollkommen)

Hm, schreibst Du da jetzt über meine Spezial-Variante von LL/SC oder über das normale (und bereits in vielen CPUs existierende) LL/SC-Konzept?

Deine Variante ist für mich effektiv ein Spinlock. Bei der normalen Variante glaube ich ehrlich gesagt noch nicht so Recht, dass da nur einer ein LL machen kann und dann eine Art Lock hat. Zumindest schreibt Wikipedia nichts davon und in den Papern die LL/SC angesprochen haben, dachte ich auch das anders verstanden zu haben.

Ich glaube aber nicht, dass du eine verkettete Liste echt durchlaufen kannst mit deinem LL/SC. Zumindest mit Locks lockt man da wohl immer zwei Knoten und zwar nichtmal LIFO, sondern verschränkt (zuerst nächsten holen, dann momentanen freigeben, dann nächsten holen, momentanen freigeben, etc).

[erik.vikinger]

Hallo,

Das viel wesentlichere ist doch eigentlich, dass dein SC im Enqueue niemals fehlschlägt

Das sollte eigentlich weder in Enqueue noch in Dequeue jemals fehlschlagen.

sobald das passiert, wird es nämlich falsch

Der einzigste Grund warum das fehlschlagen könnte ist eine Exception o.ä. zwischen LL und SC oder ein externer normaler Schreibzugriff (was eigentlich ein SW-Implementierungsfehler ist).

Aber wie gesagt, das ist zwar schick, aber es hilft halt nichts bei der Diskussion über real existierende Hardware, da will man weder Interrupts deaktivieren (das ist wohl unbedingt notwendig, damit SC nicht fehlschlägt), noch hat man so ein LL/SC.

Falls ich meine Phantasien jemals realisieren kann verspreche ich Dir auch einen richtigen CAS zu implementieren so das wir dann mal vernünftige und objektive Benchmarks fahren können.

Ich kann halt nur auf die Paper verweisen. Da testen die wohl ausschließlich die Datenstruktur (also massiv parallel) und vergleichen mit lock-basierten Varianten (oder älteren lockfreien Algorithmen) und die Ergebnisse sind einiges besser.

Auf welche Paper? Wie objektiv sind die dort durchgeführten Benchmarks? Auf einer Architektur die kein CAS hat mit LL/SC ein CAS zu emulieren ist jedenfalls nicht besonders fair bzw. objektiv.

Aber jeder ist vorbereitet.

Aha, und das bedeutet was?

Wie relevant ist es da wenn ich zusätzlich noch ein bisschen auf dem L1 Cache alleine rumarbeite (beim enqueue ist das ja meine Referenz)?

Also die 3 atmoic_read gehen nicht in den lokalen L1-Cache sondern alle auf globale Variablen die alle von den anderen Threads auch gelesen werden, die werden auf jeden Fall zwischen allen beteiligten CPUs hin und her gereicht. Das selbe trifft auch auf beide CAS-Befehle innerhalb der while-Schleife zu. 3 oder 4 deutlich nach außen spürbare Operationen pro Versuch (Schleifendurchlauf) sind was anderes als 1 nach außen spürbarer Lock-Zugriff pro Versuch. Der Spinlock kann entweder schneller reagieren (weil er pro Zeit öfter probiert) oder er erzeugt eine geringere Last (weil er pro Versuch nur eine Operation benötigt). Ich vermute das ist es auch was FlashBurn zu denken und zweifeln gibt.

Deine Variante ist für mich effektiv ein Spinlock.

Korrekt.

Bei der normalen Variante glaube ich ehrlich gesagt noch nicht so Recht, dass da nur einer ein LL machen kann und dann eine Art Lock hat.

Wie soll das sonst funktionieren? Irgendwie muss der Memory-Controller (oder eine andere Instanz die gerade für die betreffende Speicherzelle autoritär verantwortlich ist) ja entscheiden ob zwischen einem SC und dem vorangegangenen dazugehörigem LL ein anderer (Schreib-)Zugriff stattgefunden hat. Eigentlich kann da jeder ein klassisches LL machen aber nur bei maximal einem davon wird der zugehörige SC auch ein "Erfolgreich" melden. Sollte gerade diese CPU zwischen LL und SC unterbrochen werden, so das der Lock im Memory-Controller abläuft, bekommt die auch kein "Erfolgreich" beim SC gemeldet. Das ist der große Nachteil dieses Locks gegenüber einem richtigem Lock mit einer echten dedizierten Lock-Variablen (letztere bleibt beliebig lang erhalten). Gerade diese "Persistenz" einer Lock-Variablen ermöglicht aber auch Dead-Locks, die beim klassischen (und auch meinem speziellem) LL/SC so nicht auftreten können.

Zumindest schreibt Wikipedia nichts davon und in den Papern die LL/SC angesprochen haben, dachte ich auch das anders verstanden zu haben.

Für die ist das ein unerhebliches Implementierungsdetail. Ließ Dir noch mal genau die gemachten Zusicherungen durch und überlege wie man das wohl praktisch realisieren kann.

Ich glaube aber nicht, dass du eine verkettete Liste echt durchlaufen kannst mit deinem LL/SC. Zumindest mit Locks lockt man da wohl immer zwei Knoten und zwar nichtmal LIFO, sondern verschränkt (zuerst nächsten holen, dann momentanen freigeben, dann nächsten holen, momentanen freigeben, etc).

Dazu benötigt man auch echte Locks (also zusätzliche Variablen) und kein dazugezaubertes Lock. Nebst dessen das Du hier plötzlich die Anforderungen an die Queue erweitert hast, vorher sollte man nur hinten anhängen und vorne wegnehmen können.


Grüße
Erik

[bluecode]

Das viel wesentlichere ist doch eigentlich, dass dein SC im Enqueue niemals fehlschlägt

Das sollte eigentlich weder in Enqueue noch in Dequeue jemals fehlschlagen.

Jo klar, ich will nur sagen, dass das dein SC garantieren muss. Bzw. genauer: Jedes Erfolgreiche LL muss garantieren, dass ein SC auch immer erfolgreich ist, solange niemand - ohne ein LL auf die Speicherzelle gemacht zu haben -, darauf schreibt.

sobald das passiert, wird es nämlich falsch

Der einzigste Grund warum das fehlschlagen könnte ist eine Exception [...]

Effektiv gibts dann kein Debugging, denn sobald man das tut, schlägt das SC fehl.

Ich kann halt nur auf die Paper verweisen. Da testen die wohl ausschließlich die Datenstruktur (also massiv parallel) und vergleichen mit lock-basierten Varianten (oder älteren lockfreien Algorithmen) und die Ergebnisse sind einiges besser.

Auf welche Paper? Wie objektiv sind die dort durchgeführten Benchmarks? Auf einer Architektur die kein CAS hat mit LL/SC ein CAS zu emulieren ist jedenfalls nicht besonders fair bzw. objektiv.

Ich habe nie einen Benchmark zwischen einem nativen CAS und einem über LL/SC. Wimre ist das nur im Paper der Vollständigkeit halber.
edit: Was ich da sage scheint nicht zu stimmen, bei den Hazardpointer und bei der Queue steht, dass sie CAS emuliert haben über LL/SC. Die Frage ist halt immernoch, gegen was man jetzt Benchmarken soll, wenn es keinen Algorithmus gibt, der nativ ein LL/SC (so wie es von der momentanen Hardware garantiert wird) verwendet.
Der Performancevergleich ist zwischen verschiedenen _Algorithmen_ und da schneiden lockfreie besser ab als andere (meist lock-basierte oder ältere lockfreie).

Aber jeder ist vorbereitet.

Aha, und das bedeutet was?

Das jeder der in den sequentialisierten Bereich kommt (ist ja bei der queue nur ein CAS) viel schneller fertig werden kann.
edit: btw. die Autoren des Hazard-Pointer Papers nennen einige Gründe warum die Ergebnisse die sie bekommen haben so sind, wie sie sind.

Bei der normalen Variante glaube ich ehrlich gesagt noch nicht so Recht, dass da nur einer ein LL machen kann und dann eine Art Lock hat.

Wie soll das sonst funktionieren?

In meiner Vorstellung verwaltet irgendwer eine Menge aus (CPUID, geLLteSpeicherzelle, WurdeBeschrieben). Falls jemand was schreibt (sei es per LL oder normal) wird die Menge durchgeschaut und bei allen matchenden (d.h. gleiche Speicherzelle) Trippeln wird "WurdeBeschrieben" auf true gesetzt. Bei einem LL kommt halt ein (CPUID, geLLteSpeicherzelle, false) und bei einem SC wird das entfernt. Vielleicht gibt es auch noch einen Timeout nach dem so ein Ding entfernt wird und nur ein SC bei dem ein passendes Trippel vorhanden ist, kann erfolgreich sein.

Zumindest schreibt Wikipedia nichts davon und in den Papern die LL/SC angesprochen haben, dachte ich auch das anders verstanden zu haben.

Für die ist das ein unerhebliches Implementierungsdetail. Ließ Dir noch mal genau die gemachten Zusicherungen durch und überlege wie man das wohl praktisch realisieren kann.

Wo? Im speziellen wo finde ich, dass ein erfolgreiches LL (was ich bei normalen Architekturen eh nicht feststellen kann) auch immer ein erfolgreiches SC nach sich zieht? Ist das wirklich irgendwo eine _Zusicherung_. Vor allem letzteres würde mich wundern, weil man als Benutzer den Fall eh nicht unterscheiden kann. Und ehrlich gesagt: Wenn es keine Zusicherung auf Ebene der Instruktionen ist, dann würde ich darauf auch nichts geben. Die nächste Generation der CPU macht das bestimmt wieder kaputt.
edit: Und wie du selbst sagst, Interrupts oder Exceptions machen das ganze wohl auf jeder Architektur kaputt. Und welche Architektur gibt es denn die es dem User erlaubt selbige zu deaktivieren?

Nebst dessen das Du hier plötzlich die Anforderungen an die Queue erweitert hast, vorher sollte man nur hinten anhängen und vorne wegnehmen können.

Wie kommst du darauf, dass das Anforderungen an eine Queue waren? Ich rede eher von anderen Datenstrukturen (im speziellen dachte ich an eine Hashtable)... Im speziellen nach dem du explizit danach gefragt hast, wo man ein verschachteltes LL/SC braucht.

[bluecode]

Zu deinem Algorithmus nochmal: Man kann das mit der leeren Queue wohl dadurch fixen, dass man einen Dummyknoten einfügt, auf den Tail zeigt. Beim Enqueue wird dann erstmal in diese Dummyzelle der Wert geschrieben und dann eine neue Dummyzelle angefügt. Beim Dequeue muss man dann bei Head schauen ob next null ist (dann sitzt man am Dummyknoten) oder nicht (dann kann man dequeuen).
Nicht zu vernachlässigen ist btw. bei dem momentanen Algo, dass das free auch ein Problem ist, da es dem Tail den Knoten unter dem Arsch wegzieht (deswegen den Dummyknoten einführen).

[erik.vikinger]

Hallo,

Effektiv gibts dann kein Debugging, denn sobald man das tut, schlägt das SC fehl.

Ja, ist auffallend richtig. Zwischen dem LL und dem zugehörigem SC darf es keine Break-Points o.ä. geben, was natürlich gerade bei Daten-Break-Points etwas doof ist aber man kann eben nicht alles haben.

Ich habe nie einen Benchmark zwischen einem nativen CAS und einem über LL/SC. Wimre ist das nur im Paper der Vollständigkeit halber.
edit: Was ich da sage scheint nicht zu stimmen, bei den Hazardpointer und bei der Queue steht, dass sie CAS emuliert haben über LL/SC. Die Frage ist halt immernoch, gegen was man jetzt Benchmarken soll, wenn es keinen Algorithmus gibt, der nativ ein LL/SC (so wie es von der momentanen Hardware garantiert wird) verwendet.

Deine Frage ist zwar berechtigt aber wenn er ein CAS verwendet dann soll er auch eine Architektur benutzen die das nativ unterstützt, z.B. x86 oder Itanium und nicht Power3.

In dem Stückchen Code sind übrigens zwei Bugs drin :

Code: [Auswählen]

{
do
 { if (LL(addr) != exp) return false; }
while(!SC(addr,new));
return true;
}Wer die findet darf sich bei mir zwei Bier abholen.
Kleiner Tipp: es hat etwas mit dem zeitlichen Verhalten und mit bestimmten Ausführungspfaden zu tun.

Der Performancevergleich ist zwischen verschiedenen _Algorithmen_ und da schneiden lockfreie besser ab als andere (meist lock-basierte oder ältere lockfreie).

Ich will ja nicht den ewigen Nörgler raus hängen lassen aber ein simples "es ist eben so" ist für mich persönlich keine zufriedenstellende Antwort.

Das jeder der in den sequentialisierten Bereich kommt (ist ja bei der queue nur ein CAS) viel schneller fertig werden kann.

Der sequentielle Bereich beginnt mit dem ersten Atomic-Read, das wird zwar nicht geschützt o.ä. aber wenn ein anderer Thread auch in diesem Bereich ist dann kann maximal einer da erfolgreich raus kommen.

edit: btw. die Autoren des Hazard-Pointer Papers nennen einige Gründe warum die Ergebnisse die sie bekommen haben so sind, wie sie sind.

Hm, muss ich am WE noch mal nach suchen.

In meiner Vorstellung verwaltet irgendwer eine Menge aus (CPUID, geLLteSpeicherzelle, WurdeBeschrieben)....

Ja, dann hast Du das IMHO schon ziemlich gut verstanden. Ob das nun über eine Liste mit den laufenden Locks oder mit einer Art Tocken gemacht wird ist letztlich egal (ein unwesentliches Implementierungsdetail), entscheidend ist das der Lock mit dem LL erstellt wird und es nur 3 Möglichkeiten gibt diesen zu löschen: den zugehörigen SC (ein nicht zugehöriger SC hat keine Auswirkung), ein beliebiger Schreibzugriff oder ein TimeOut (das ist wichtig damit Dead-Locks zuverlässig ausgeschlossen sind, wenn man sowas in HW realisiert dann muss man da schon etwas Vorsorge treffen ansonsten müsste der User den Computer jedes mal Resetten o.ä. um sowas zu beheben).

Im speziellen wo finde ich, dass ein erfolgreiches LL (was ich bei normalen Architekturen eh nicht feststellen kann) auch immer ein erfolgreiches SC nach sich zieht?

Diese Zusicherung gibt es nicht, auch bei mir nicht (bei mir möchte ich mit dem Abschalten der INTs nur nachhelfen damit das eben doch zuverlässig funktioniert).


Ansonsten würde ich mich auf jeden Fall sehr freuen dazu einen schönen Wiki-Artikel zu haben, schon damit wir auch mal über etwas konkretes diskutieren können.


Grüße
Erik

[bluecode]

In dem Stückchen Code sind übrigens zwei Bugs drin

Erzähl! Ich seh keinen und die Bier mag ich eh nicht.

Der Performancevergleich ist zwischen verschiedenen _Algorithmen_ und da schneiden lockfreie besser ab als andere (meist lock-basierte oder ältere lockfreie).

Ich will ja nicht den ewigen Nörgler raus hängen lassen aber ein simples "es ist eben so" ist für mich persönlich keine zufriedenstellende Antwort.

Du wirst von mir keine andere bekommen. Und ich habe bereits in dem vorherigen Beitrag darauf verwiesen, dass die Autoren (des Hazard-Pointer Paper) da einiges dazu schreiben.

Im speziellen wo finde ich, dass ein erfolgreiches LL (was ich bei normalen Architekturen eh nicht feststellen kann) auch immer ein erfolgreiches SC nach sich zieht?

Diese Zusicherung gibt es nicht, auch bei mir nicht (bei mir möchte ich mit dem Abschalten der INTs nur nachhelfen damit das eben doch zuverlässig funktioniert).

Wenn es das nicht als Zusicherung (bei abgeschalteten Interrupts gibt), dann ist dein Code inkorrekt.

[erik.vikinger]

Hallo,

Erzähl! Ich seh keinen und die Bier mag ich eh nicht.

Nö, so einfach verrate ich das auch nicht, vielleicht möchte sich ja hier noch jemand anderes ernsthaft daran versuchen.
Der Code (der aus dem Hazard-Pointer-PDF von diesem Michael kopiert ist) verursacht nicht wirklich einen Fehler oder gar Inkonsistenzen aber er kann in bestimmten Situationen ziemliche Performance-Probleme verursachen (fast Dead-Locks). Als korrekt würde ich ihn so auf jeden Fall nicht bezeichnen und in einem Benchmark wo es ja gerade um die Performance geht ist sowas IMHO auch ein Bug.
Ich bin jetzt das gesamte Wochenende über nicht da und habe auch keinen iNetz-Zugang, die Auflösung gibt es dann am späteren Sonntag Abend. Bis da hin wäre es aber schön wenn jemand anderes doch drauf kommt und sich bei mir ein Bier abholt. Viel Glück!

Du wirst von mir keine andere bekommen.

Hab ich von Dir auch nicht anders erwartet.

Und ich habe bereits in dem vorherigen Beitrag darauf verwiesen, dass die Autoren (des Hazard-Pointer Paper) da einiges dazu schreiben.

Ja, is ja gut, bei nächster Gelegenheit lese ich das noch mal gründlich durch.

Wenn es das nicht als Zusicherung (bei abgeschalteten Interrupts gibt), dann ist dein Code inkorrekt.

Bei abgeschalteten INTs werden die Rahmenbedingen so hingedreht das es eben trotzdem zuverlässig klappt. Aber das Abschalten der INTs ist keine Voraussetzung für die Benutzung dieser Befehle, es gibt auch einfachere Situationen wo man die auch mit INTs benutzen kann.


Grüße
Erik

[erik.vikinger]

Hallo,


wie ich sehe hat sich in den letzten 48 Stunden absolut gar nichts getan. Ich muss ehrlich sagen das ich sehr enttäuscht bin! War das etwa zu schwer? Soll ich noch mal ein paar Tage Zeit geben oder wollt Ihr lieber die Auflösung? Na ich will mal nicht so sein und Euch nicht länger auf die Folter spannen:

Der entscheidende Unterschied zwischen einem echten CAS und diesem emulierten CAS liegt in dem nach außen spürbaren Verhalten. Bei einem echten CAS gibt es nichts persistentes wohingegen beim LL/SC-Pärchen dann doch etwas persistentes, naja okay zumindest etwas semi-persistentes gibt. Dieser Lock in der Hardware bleibt ja wenn kein zugehöriges SC kommt erstmal eine Weile bestehen so das kein weiteres LL klappen kann, selbst wenn die CPU die das LL getätigt hat welches den Lock bekommen hat nun etwas anderes tut weil z.B. ein IRQ dazwischen gefunkt hat (eventuell gar der der das Ablaufen der Zeitscheibe signalisiert so das der Thread der beim LL gewonnen hat nun dummerweise geschedult wurde) oder weil das LL einfach nicht den gewünschten Wert geliefert hat so das die Funktion mit dem "return false" verlassen wurde (in diesem Pfad müsste eigentlich der Lock wieder freigegeben werden aber ohne einen anderen Wert zu schreiben).

Der Bug besteht also darin das diese Funktion regulär verlassen werden kann oder anderweitig unterbrochen werden kann obwohl der Hardware-Lock erfolgreich gewonnen wurde und nun bis zu seinem Time-Out bestehen bleibt so das kein anderes LL erfolgreich sein kann und damit auch kein anderes SC zum Ziel führt obwohl das spätere LL den richtigen Wert geliefert hat (aber eben nicht den Lock bekommen konnte).

In diesem Szenario gibt es IMHO nur eine unbekannte Variante: es wäre ja möglich das ein Thread zwar erfolgreich das Lock bekommt und dann entweder die Funktion verlässt oder unterbrochen wird und dann ein anderer Thread auf der selben CPU das SC durchführt (obwohl dieser eventuell auch zwischen LL und SC unterbrochen wurde aber wahrscheinlich von einer anderen Situation aus geht also mit einem anderen Wert in 'exp' aufgerufen wurde) so das dann die Frage aufkommt ob dieses SC zu einem "False-Positive"-Ergebnis führen kann. Eigentlich sollte die Hardware das absolut zuverlässig ausschließen, dazu reicht aber nicht allein eine CPU-ID in einer Liste sondern es ist IMHO auch ein zusätzliches Tocken (welches die CPU grundsätzlich bei jedem Modus-Wechsel vergisst) oder ein anderer Mechanismus innerhalb der CPU (der z.B. ein SC grundsätzlich unterbindet wenn nicht seit dem letzten Modus-Wechsel auch ein zugehöriges/vorangegangenes LL auf die selbe Speicherzelle stattgefunden hat). In meiner CPU möchte ich die zweite Lösung nutzen, die CPU muss immer die eigenen LL's mittracken und diese Information bei jedem Modus-Wechsel komplett vergessen so das ein unpassendes SC erst gar nicht nach Außen geht. Zusätzlich möchte ich das meine CPU bei jedem Löschen dieser Informationen immer noch ein Release-Lock ohne Schreibdaten durchführen (falls gerade ein Lock gehalten wurde) so das auch die nachfolgenden LL's nicht ausgebremst werden. Wie PowerPC das konkret macht weiß ich nicht (ist vermutlich auch nicht spezifiziert so das jede PowerPC-CPU das auf eigene Art erledigen kann) aber da dieser Michael in dem PDF auf dieses Problem nicht eingegangen ist nehme ich mal an das er sich darüber keine Gedanken gemacht hat (er sich dieser Problematik eventuell gar nicht bewusst ist).

Ich hoffe ich habe das alles einigermaßen verständlich formuliert, wenn nicht dann Bitte nachfragen.
Es würde mich freuen wenn jemand, der besser englisch kann als ich (wovon es hier sicher einige gibt), diesen Bug dem Autor des PDF melden könnte.


Grüße
Erik

[bluecode]

Transactional Memory könnte auch interessant sein, v.a. ist interessant, dass es jetzt zum ersten Mal in Hardware implementiert wurde (zumindest innerhalb des gleichen Prozessors funktioniert das).

[Svenska]

Die Arbeiten die du aufgezählt hast, sind ja alles Arbeiten wo die Locks überhaupt nicht interessieren Um es mal überspitzt zu sagen, bei den Arbeiten kann mir die Performance des OS scheiß egal sein, aber spätestens beim Kompilieren + Video (siehe Linux ) ist es dann nicht mehr (ich weiß das es in dem Fall der Scheduler war).

Da widerspreche ich. Wenn du 20 Prozesse hast, die gleichzeitig die CPU-begrenzt sind, dann muss dein Scheduler vernünftig arbeiten. Wenn du 20 Prozesse hast, die nur Festplattenzugriffe machen, dann muss dein I/O vernünftig arbeiten. Beide Fälle sind in der Reinform extrem selten, sie treten immer gemeinsam auf. Ein Giant Lock mit einer CPU kostet nichts, bei zwei CPUs gibt es nur dann Wartezeiten, wenn zwei Prozesse/Threads gleichzeitig I/O machen wollen. Es gibt aber immer noch einen anderen Prozess, der gerade CPU machen will - und der kann problemlos auf die "wartende" CPU verschoben werden, bis das Lock frei ist. Böse wird es beispielsweise, wenn du Festplattendaten übers Netzwerk schicken willst, aber auch dann hast du noch einiges an CPU-Verbrauch für die Paketstruktur usw.

Unerträglich wird der Ansatz bei vielen (>4, evtl. >2) CPUs, aber bis dahin ist er sehr einfach und ziemlich schnell. Und mit feinem Locking kann man diesen Faktor sehr weit rausschieben.

Ein Mutex ist doch praktisch ne Semaphore mit nem Counter von 1, oder? Und sowas kann man nur eigentlich nur sinnvoll im Kernel machen, weil du einen Lock brauchst um Queue und Counter zu schützen und du willst ja Threads in die Queue packen und dann schlafen legen (spätestens da musst du in den Kernel).

Das hängt davon ab, wie deine Threads implementiert sind. Liegen die komplett im Userspace, brauchst du dich um Locking zwischen einzelnen Threads des gleichen Prozesses nicht kümmern. Aber bei Kernel-Threads musst du das, richtig.

Aber was ist dann z.B. mit Interrupts, die würden ja dann auch blockiert werden, nur weil irgend ein Thread was im Kernel macht, oder?

Nicht, wenn Interrupts höher priorisiert sind als der Kernel selbst. Interrupthandler sollten normalerweise nur ein Ereignis im Kernel queuen, außerdem dürfen Interrupthandler keine Locks halten - damit stellt sich das Problem nicht.

Muss nicht auch die Video-Ausgabe irgendwann in den Kernel (also 24 mal in der Sekunde)?

Warum sollte sie? Seit wann musst du der Grafikkarte _jedes_ Bild schicken? Wenn sich nichts ändert, lässt du die einfach in Ruhe und das Bild bleibt stehen... und wenn du Videos darstellst, dann wird der Videospeicher (der Teil, der für das Overlay da ist, meist im Offscreen-Bereich) in den Adressraum der Anwendung gemappt und ab dann braucht es keine Kernelzugriffe mehr.

Gruß,
Svenska