Nachrichten

41

OS-Design / Re:Locking innerhalb des Kernels

« am: 17. August 2011, 10:07 »

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).

42

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 21:42 »

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...

43

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 19:27 »

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.

44

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 18:30 »

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.

45

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 18:09 »

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.

46

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 17:32 »

Nehmen wir an, 2 Threads (auf verschiedenen Cores) kommen bis nach das

Code: [Auswählen]

 if (LocalTail->next != null)
   { PANIC(); }
mit dem selben LocalTail = Tail, anschließend schafft der eine sein

Genau das wird doch von

Code: [Auswählen]

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

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?
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.

47

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 12:40 »

Wieso könnten also Lock-Free Algos auch im Kernel schneller sein? Zumal man auch den Stromverbrauch dann nicht außer acht lassen sollte, insbesondere, da man ne Spinlock durch "pause" wohl ganz gut "entspannen" kann.

Jeder Lockfreie Algorithmus besteht im Endeffekt aus genau der gleichen Schleife (siehe zB oben), in der man Anfangs einen Snapshot von ein paar Sachen macht, dann bisschen was rechnet, dann versucht man die Datenstruktur zu aktualisieren. Man kann falls man es nicht schafft die Datenstruktur zu aktualisieren theoretisch ein "pause" machen, aber es macht wenig Sinn. Warum? Weil wenn ich eine Änderung feststelle, dann ist der andere bereits mit seiner Aktion fertig und ich habe dann sofort die Chance im nächsten Durchlauf es zu schaffen, was bei einem Spinlock anders ist.
edit: Wobei ich natürlich keine Ahnung habe wie das in der Praxis aussieht mit/ohne "pause" (und ich muss auch sagen mich interessieren die Hardwaredetails dazu überhaupt nicht, für mich würde es einfach auf Benchmarken hinauslaufen). Ich sag nur, dass die Möglichkeit besteht eines zu machen, ich aber nicht so richtig sehe warum man das sollte.

Ich weiß leider nicht ob/wie die queue mit Prioritäten umgeht, aber es könnte für bestimmte Anwendungen irrelevant sein (HPC/Server oder so), weil da der selbe Typ Anwendung (apache oder SETI) läuft. Aber auf jeden Fall ist die Vermeidung von Contention und die Cachelokalität, die man quasi geschenkt bekommt, relevant. Ist halt eventuell nichts für ein Desktop-OS. Aber wie gesagt, Hammer & Nagel.

48

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 11:31 »

Ich würde "nein" sagen, lockfreie Algorithmen können trotzdem im Kernel schneller sein als Locks, aber es bringt nichts zu versuchen alles lockfrei zu machen (das schien mir irgendwie Anfang des Threads dein Ansatz zu sein). Das wirst du bei einem allgemeinen Kernel sowieso nicht hinkriegen, weil es die entsprechenden Datenstrukturen [noch] nicht gibt. Im speziellen habe ich gehört, dass für den Scheduler eine work-stealing queue ziemlich gut sein soll. Die prinzipielle Idee dabei ist, dass jeder Core erstmal seine eigene queue mit Threads hat. wenn die aber leer wird kann man von anderen was klauen. So wie ich gehört habe, braucht man bei der Datenstruktur sogar nur dann ein CAS, wenn man feststellt, dass es einen Konflikt gibt (was man scheinbar kann).
Aber es ist wohl schon richtig, dass der Performancegewinn im Userspace größer sein dürfte bzw. auch die Stabilität was Performance betrifft. Es ist halt so wie immer: Nur weil man einen neuen, glitzernden Hammer gefunden hat, ist noch lange nicht alles ein Nagel.

49

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 09:00 »

Im Speziellen hat man die Garantie, dass das globale System weiterkommt, wenn auch nicht der Einzelne.

Wenn man mal von Dead-Locks, Live-Locks oder Priority-Inversion absieht hat man diese Garantie doch auch bei Locks, mindestens einer bekommt ihn und so geht es doch irgendwie zumindest vorwärts. Das Problem ist das man die genannten Hemmnisse zuverlässig ausschalten muss.

Wie oben bereits gesagt, das wesentliche ist, dass was nicht in der Definition steht. Bei lockfreien Algorithmen darf ein Thread beliebig lange (auch unendlich) nicht geschedult werden und andere können währenddessen trotzdem Fortschritt machen, genau das geht bei Locks nicht. Wenn derjenige der den Lock hat, nich geschedult wird oder abgebrochen wird, gehts garnichtmehr weiter.

.... aber nach dem Freigeben kann es ja dann sein, dass andere immernoch auf dem Lock spinnen.

Hm, in der Tat. Da muss ich wohl noch mal drüber nachdenken. Obwohl ja derjenige der den Lock hat auch den Zustand des Threads ändern kann, z.B. auf Killed, und derjenige der den Lock gerne haben möchte muss diesen Zustand mit beobachten und seine Versuche gegebenenfalls abbrechen. Aber dafür ist es erforderlich das der Thread-Struckt mindestens die Zeit in diesem Zustand bleibt die es im worstesten Worst-Case dauert bis alle die spinnen das auch merken, auch nicht schön.

Exakt.

Ich schau mir den Code später an, aber ich wette, dass er nicht lockfrei ist.
Ne das Problem ist wohl eher, dass der Code nicht korrekt ist. Nehmen wir an, 2 Threads (auf verschiedenen Cores) kommen bis nach das

Code: [Auswählen]

 if (LocalTail->next != null)
   { PANIC(); }
mit dem selben LocalTail = Tail, anschließend schafft der eine sein

Code: [Auswählen]

LocalTail->next = NewNode;
früher als der andere. Der andere wird dann das Element des einen aus der Liste verdrängen, d.h. effektiv machst du die Datenstruktur kaputt. Ein anderes noch schlimmeres Problem im weiteren Verlauf wäre, wenn der eine jetzt vorher sein CAS macht und der andere danach, dann zeigt Tail effektiv auf den verdrängten Knoten, dann wirds aber richtig zappenduster  

Ich hatte da eigentlich an etwas gedacht wo zwei verschachtelte LL/SC-Pärchen nötig wären, dafür fällt mir kein richtiges Beispiel ein.

Das brauchst du hier aber schon, LocalTail->next ist global im Speicher, das sollte man nicht einfach so überschreiben. Deswegen macht der andere Code das mit einem CAS. Und wenn du beide CAS haben willst, brauchst du zwei LL/SC "verschachtelt" (wie gesagt, ist wohl nicht so richtig LIFO), weil es CAS auf verschiedene Speicherstellen sind.

Noch was zu Lockfreiheit: Man kann das im Kernel wohl auch dadurch hinbiegen, dass man IRQs bzw. den Scheduler deaktiviert, aber die Definition ist so denke ich nicht gedacht, d.h. man geht schon davon aus, dass man einen Scheduler hat, der einen jederzeit unterbrechen kann, d.h. der Algo sollte auch im Userspace funktionieren können (und da will man wohl cli/sti nicht erlauben bzw. nichtmal per syscall).

50

OS-Design / Re:Locking innerhalb des Kernels

« am: 16. August 2011, 07:57 »

hm, ich hab nochmal über dein zeitliches Verhalten nachgedacht und ich glaube ich verstehe jetzt was du meinst. Meine Vermutung wäre dass sich das in "eine Operation garantiert abhängig vom Verhalten andere Threads unterschiedlich viel" zusammenfassen lässt. Das mag manchmal ein fruchtbarer Ansatz sein, da man eventuell das Verhalten der anderen Einschränken kann (zB wenn man den Kernel herunterfährt, wird wahrscheinlich nur ein Thread den Mist aufräumen). Meine Philosophie wäre "eine Operation garantiert, was sie im worst-case des Verhaltens anderer noch garantieren kann".
Anfangs dachte ich auch, dass du die Performance meinst, aber das ist bei lockfreien Algos viel weniger als bei Locks der Fall. Im Speziellen hat man die Garantie, dass das globale System weiterkommt, wenn auch nicht der Einzelne.

Deswegen wollte ich in jeden Thread-Descriptor ein eigenes Lock einbauen so das diese Strucktur vor jeder Modifikation (und dazu gehört auch das Freigeben) erst mal gelockt werden muss

Ich sehe da nicht sofort wie man das korrekt machen kann, denn wenn ich den Lock zum freigeben habe (und der Lock Teil der Threadstruktur ist), dann gebe ich den Lock mit frei, aber nach dem Freigeben kann es ja dann sein, dass andere immernoch auf dem Lock spinnen.

Könntest Du hierzu mal Bitte ein kurzes Beispiel geben (Pseudo-Code reicht völlig).

Ein Enqueue dürfte ungefähr so aussehen (Zum Verständnis: Tail zeigt nicht immer auf den letzten Knoten, sondern entweder auf den letzten oder auf den vorletzten.)

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;

  bool Success = false;
  while (! Success)
  {
    Node* LocalTail = atomic_read(Tail);
    Node* LocalNext = atomic_read(LocalTail->next);
    if (LocalTail == atomic_read(Tail))
    {
       if (LocalNext != null) // Tail zeigt auf den vorletzten Knoten
         CAS(&Tail, LocalTail, LocalNext); // Tail eins weiter schieben und alles nochmal versuchen
       else // Tail zeigt auf den letzten Knoten
         Success = CAS(&LocalTail->next, null, NewNode) // Versuchen NewNode in die verkettete Liste nach Tail einzuhängen
    }
  }
  CAS(&Tail, LocalTail, NewNode); // Versuchen Tail eins weiter zu schieben
}


51

OS-Design / Re:Locking innerhalb des Kernels

« am: 15. August 2011, 17:10 »

Also ich denke ich habe gar nicht verstanden was du versucht hast zu erklären

ich hab versucht zu erklären, dass selbst wenn man durch eine einfach verkettete Liste lockfrei laufen kann (was zB in dem Paper zu dem Set realisiert wird), dass dann die Operation die du dir zusammenbaust trotzdem in den allermeisten Fällen nicht "korrekt" (bezogen auf Linearisierbarkeit) ist. Und Linearisierbarkeit (Es gibt einen Zeitpunkt zu dem die Operation atomar ausgeführt wird) ist denke ich ein Korrektheitsbegriff den man gerne hätte. In meinem obigen Beispiel gibt es halt keinen Zeitpunkt zu dem die Menge  so aussieht wie sie von der Operation zurückgeliefert wird. Wenn man jetzt nur eine Pi-mal-Daumen-Approximation der Menge braucht, ist das natürlich ausreichend. Wenn aber die Menge ursprünglich immer interessante weitere Eigenschaften hatte (zB alles summiert sich auf 1, was jetzt in dem konkreten Beispiel wohl sowieso nicht geht, aber was solls), dann können diese verloren gehen (weil man plötzlich ein Element mehr in der Menge hat).

52

OS-Design / Re:Locking innerhalb des Kernels

« am: 15. August 2011, 16:39 »

Das dieser Zeitpunkt ohne X und ohne Y nie existiert hat ist zwar ein Korrektheitsproblem aber normale Software sollte auf sowas eh nicht zwingenst angewiesen sein. [...]

Wenn du mit so wenig Semantik glücklich werden kannst, dann prima.

Ich denke das wird man müssen ansonsten muss man dem System zwangsläufig die Zeit geben die unterschiedlichen Sichtweisen der verschiedenen CPUs zu vereinheitlichen (z.B. mit geeigneten Befehlen die den Abschluss (Commit) aller noch laufenden Speicheroperationen abwarten).

Genau sowas meine ich, was korrekt ist hängt hier sehr stark von Forderungen an die Operation ab, die man im sequenziellen Umfeld automatisch geschenkt bekommt und über die man nie nachdenkt, weil niemand parallel versucht meine Operation zu untergraben. Aber hier müssen solche Forderungen plötzlich explizit gestellt werden (und kosten dann auch Komplexität/Performance). Deswegen sag ich ja die ganze Zeit, dass man nicht ohne genaue Beschreibung der Operation auskommt. Sonst nimmt jemand einfach die Operation, glaubt ihm reicht die Semantik, und fährt damit gegen die Wand. Oder man baut noch ein paar Operationen dran, macht aber dabei die Lockfreiheit kaputt (die natürlich sehr stark davon abhängt, was andere Operationen machen dürfen).

Andernfalls musst du ganz klar definieren was die Operation tun soll.

Auf Dein obiges Set bezogen würde ich sagen das man z.B. die Möglichkeit hat zu definieren dass das Set doppelte X selber anmeckert

Das macht das oben erwähnte Set auch, aber nur, wenn die Menge eine totale Ordnung hat (z.B. natürliche Zahlen, oä).

Für was würde man denn so eine Verschachtelung benötigen (LIFO-Prinzip voraus gesetzt)?

Für eine Queue und sehr wahrscheinlich auch für das Set (bzw. darauf aufbauend ein Hashset). Wobei es kein so richtiges LIFO ist, denn es werden zwei LL's gemacht und dann entweder auf das eine oder auf das andere ein SC (bei der Queue).

insofern würde ich (im Ggs. zu erik) behaupten, dass in keinster Weise irgendwas vom zeitlichen Verhalten abhängt...

Unter der Vorausetzung das in Deinem vorherigen Beispiel es Okay ist das der Suchlauf weder X noch Y gefunden hat obwohl es eigentlich keinen Zeitpunkt gab an dem weder X noch Y im Set waren.

Ich kenne nur den Korrektheitsbegriff der Linearisierbarkeit (eine Operation wird zu einem atomaren Zeitpunkt, dem Linearisierungszeitpunkt, ausgeführt) und da kann sowas natürlich nicht passieren.

Info-Student?

Jo

meine Frage/Bedenken läuft darauf hinaus, wie stellt man sicher, dass z.B. in einer Liste nicht 2x das gleiche Element eingetragen wird?

Wenn du die Elemente geordnet speicherst, kannst du verhindern (was von dem was ich hier schreibe natürlich keinesfalls offensichtlich ist ), dass 2x das gleiche eingetragen wird.

53

OS-Design / Re:Locking innerhalb des Kernels

« am: 15. August 2011, 14:18 »

Ich kann heute Abend versuchen das anders zu erklären - ich muss jetzt erstmal weiter für eine Prüfung morgen lernen, ironischerweise heißt die "Datenstrukturen"  . Hast du irgendeine Ahnung wo du ausgestiegen bist? Oder hast du garnicht verstanden was ich versucht habe zu erklären?

54

OS-Design / Re:Locking innerhalb des Kernels

« am: 15. August 2011, 14:01 »

Bei Lock-Free Algos kann aber jeder Thread fortschritte machen [...]

Das stimmt so nicht ganz. Man kann nicht isoliert auf jeden Thread sagen dass dieser Fortschritt macht (im Sinne von "er kommt seinem Ziel näher"), sondern man kann nur sagen, dass immer wieder irgendein Thread seine Operation fertig ausgeführt hat (Das ist quasi genau die Definition von lockfree). Das für sich genommen ist nicht unbedingt spannend, viel spannender ist, welche Ereignisse dabei nicht ausgeschlossen werden: Es wird nicht ausgeschlossen, dass ein Thread endlich oder unendlich lang nicht geschedult wird oder das er einfach abgebrochen wird. Es kann also per Definition keinen Deadlock, Livelock oder Priority Inversion geben. Und im Prinzip hat die Performance viel weniger mit dem Scheduler zu tun als bei Algorithmen mit Locks, insofern würde ich (im Ggs. zu erik) behaupten, dass in keinster Weise irgendwas vom zeitlichen Verhalten abhängt...

Ich muss aber ehrlich zugeben, ich habe irgendwie nichts von dem was du geschrieben hast wirklich verstanden

Auch nicht den letzten Beitrag von mir?

55

OS-Design / Re:Locking innerhalb des Kernels

« am: 15. August 2011, 13:20 »

@erik: Ich glaube dir zu antworten, verschiebe ich auf einen Eintrag im Wiki, den ich hoffentlich irgendwann Mitte/Ende der Woche anfange. Aber ich bin mir ziemlich sicher, dass du nicht weißt, was die Definition von lockfrei ist, was wohl das erste sein wird, was in den Eintrag kommt.

So um nochmal eins festzuhalten, ich habe im Moment ein Problem wie man bei Lock-Free Algos z.B. das Iterieren durch eine Liste machen können soll und davon ausgehen können soll, das die Daten auch in Ordnung sind.

Wie ich oben schonmal versucht habe zu sagen, es ist wichtig, dass man zuerstmal genau spezifiziert was eine Operation (nach außen hin) leisten soll. "Iterieren durch eine Liste" ist aber genau eine Implementierung und keine Spezifikation eines Interfaces. Ist das was du suchst eine Menge, die folgendes unterstützt:
* set::contains(x): Gibt true zurück, falls die Menge x enthält
* set::insert(x): Fügt x hinzu falls es noch nicht in der Menge ist
* set::remove(x): Entfernt x, falls es in der Menge ist
Wie man diese Datenstruktur implementiert, kann man auch Michaels entnehmen (solange die Elemente eine totale Ordnung haben): Er benutzt dazu eine geordnete, einfach verkettete Liste. Die muss er natürlich auch durchlaufen, um ein Element zu finden. Das Problem ist jetzt, dass man nicht einfach dieses Durchlaufen der Liste in einem anderen Kontext verwenden kann.
Warum? Weil es doch überhaupt nicht klar ist, was das bedeuten soll, wenn sich die Liste vor und hinter "mir" verändert während ich durchlaufe. Ein ganz einfach Beispiel (das vollkommen unabhängig davon ist wie man es implementiert, es hängt nur davon ab, dass andere parallel etwas an der Datenstruktur machen dürfen): Es soll eine Methode implementiert werden, die alle Werte dieses Sets aufsammelt. Nehmen wir an ich bin eine Weile durch die Liste gelaufen und hab mir die Elemente gemerkt. Jetzt fügt jemand (irgendwo) hinter mir ein Element x ein und jemand anders löscht anschließend (irgendwo) vor mir ein Element y. Ich laufe jetzt weiter und stelle fest in meiner Menge ist weder x noch y. Jetzt natürlich die Masterfrage: Gab es überhaupt einen Zeitpunkt während meiner Operation, bei der weder x noch y in der Menge war? Nein, anfangs war y in der Menge, dann kam x dazu, dann wurde y entfernt und x blieb. Das heißt es gibt keinen atomaren Zeitpunkt, bei dem die Operation "ausgeführt wurde" (d.h. sie ist nicht linearisierbar, eine der wichtigsten Korrektheitsbegriffe für lockfreie Algorithmen und das zweite was in den Artikel kommt). Wenn du mit so wenig Semantik glücklich werden kannst, dann prima. Andernfalls musst du ganz klar definieren was die Operation tun soll.
Das andere ist: Es reicht auch nicht aus zu spezifizieren was eine der Operationen machen soll, sondern man muss vorher klären was man alles an Operationen unterstützen will. Beispiel: Ich will das Iterieren von vorhin, aber niemand darf löschen oder was hinzufügen. Dann ist wohl offensichtlich wie man das hinkriegt, der Erkenntnisgewinn ist allerdings gleich 0 (d'uh).

edit: Was ich damit sagen will ist auch, dass wenn ich dazu einen Eintrag verfassen soll, dass man dann Beweisen muss warum etwas korrekt ist (und bezogen auf was überhaupt, siehe Linearisierbarkeit oben) und man muss natürlich auch Beweisen das etwas lockfrei ist. Wenn ihr darin Interesse habt und Feedback gebt, kann ich da gerne anfangen, aber sonst würde ich das lassen.

Ich wollte noch was zu LL/SC sagen: Soweit ich weiß kann man die nicht verschachteln (also auf mehrere Speicheradressen gleichzeitig anwenden), was man aber braucht für andere Algorithmen. Und es löst nur das ABA-Problem, nicht aber das Problem, dass man gerne Speicher freigeben würde.

ROFLMAO, das war mein leetster Beitrag 

56

OS-Design / Re:Locking innerhalb des Kernels

« am: 13. August 2011, 18:43 »

Verstehe ich nicht wirklich, denn du überprüfst mit dem Validieren ja nicht, ob die Datenstruktur noch gleich ist (so etwas würde ja erst zum ABA-Problem führen), sondern nur, dass der Zeiger nicht freigegeben ist (zum Zeitpunkt des Validierens dann, was ich vorher wohl anders gesagt habe). Und nach dem validieren weiß ich, dass er nicht freigegeben werden darf (=> Man greift nicht auf einen bereits freigegebenen Zeiger im weiteren zu) und damit auch, dass er nicht wiederverwendet wird (=> Man hat kein ABA-Problem, bezogen auf diesen Zeiger).

57

OS-Design / Re:Locking innerhalb des Kernels

« am: 13. August 2011, 12:44 »

Um aber mal allgemein zu bleiben, mir will die Sache mit der Zeit nicht aus dem Kopf gehen. Ich meine was passiert, wenn sich ein Thread einen Pointer holt und dann, aus welchem Grund auch immer, ne Weile nicht an die Reihe kommt und der Zufall es so will das der Pointer und die ihn schützende Struktur gleich sind, aber sich ganz andere Daten dahinter befinden?

Das kann bei Hazard-Pointern eben nicht passieren. Du deallozierst den Pointer nur und er kann auch erst dann wiederverwendet werden bzw. wieder in der Datenstruktur vorkommen, wenn kein anderer Thread denselbigen hält.

Um auch nochmal erik´s Bsp aufzugreifen, auch wenn man das Freigeben bei Hazard-Pointern weit nach Hinten schiebt, kann die Situation auftreten (auch wenn sie erstmal nur theoretischer Natur ist), dass das Einfügen bzw. das Erstellen des Hazard-Pointers erst sehr lange nach dem Holen des Pointers passiert und der Pointer jetzt wieder dummerweise den selben Wert hat wie vorher (obwohl es sich um eine ganz andere Datenstruktur und Daten handelt). Geht das theoretisch?

Nein, du holst dir zuerst einen Snapshot des Pointers, packst den dann in deinen Hazardpointerrecord. Bevor du allerdings weitermachst überprüfst du nochmals ob der globale Pointer mit dem eigenen Snapshot übereinstimmt (das wird im Paper iirc als Validieren bezeichnet). Dadurch wird sichergestellt, dass zu dem Zeitpunkt zu dem der Thread den Hazardpointer in den Hazardpointerrecord geschrieben habe, dieser noch "in der Datenstruktur war" und noch niemand angefanngen hat ihn freizugeben (also auch noch nicht angefangen hat durch den Hazardpointerrecord zu laufen, um zu schauen ob andere diesen Pointer mitbenutzen).

58

OS-Design / Re:Locking innerhalb des Kernels

« am: 12. August 2011, 23:46 »

der ist mit Sicherhheit eher zu treffen als die Version

Du musst aber gerade beides treffen, damit ein CAS das scheitern sollte trotzdem gutgeht und die Datenstruktur damit kaputtmacht.

Gegen was genau sollen diese Hazard-Pointer eigentlich schützen?

Zum einen vor dem ABA-Problem, zum anderen sind sie dazu da, dass man überhaupt was (echt) freigeben kann und den Speicher für andere Zwecke nutzen kann. Außerdem natürlich das was FlashBurn sagt, für lockfreie Algorithmen.

Aber schon dieser Suchvorgang kann doch bei einer recht großen Anzahl an Threads schon enorm CPU-Zeit kosten, IMHO auf jeden Fall sehr viel mehr als ein schlechter Lock-Mechanismus brauchen würde.

Der Suchvorgang ist nur dazu da Speicher freizugeben, d.h. das kann man ne ganze Weile rausschieben. Und das wird auch in dem Paper gesagt, dass man wartet bis man zB 2 * #Threads * #HazardPointerProThread gesamelt hat, dann kann man auf jeden Fall die Hälfte freigeben, was dann O(1) pro Freigeben ergibt. Deswegen habe ich oben auch schon gesagt, dass es problematisch sein kann, da man bei vielen Threads ewig keinen Speicher freigibt.

Nebst dessen das auch dieses Suchen auf ein einigermaßen deterministisches zeitliches Verhalten angewiesen ist.

Nein.

Oder hab ich da irgendetwas falsch verstanden?

Ja, jeder versucht nur die Zeiger freizugeben die er aus der Datenstruktur entnommen hat. Stell dir zB eine Queue vor und jeder holt da einen Workitem raus. Da dabei nur einer einen bestimmten Workitem rausnimmt wird auch nur der versuchen diesen freizugeben.
edit: Der Algorithmus muss also klar vorgegeben haben, wem eine Referenz "gehört" (der darf sie dann auch Löschen), muss allerdings warten, bis alle anderen die Referenz nichtmehr Benutzen (was sie durch den Hazard pointer Record ja dem freigebenden Thread signalisieren). Und Benutzen heißt hier meist eher ein bisschen was anderes als man so intuitiv annehmen würde: zB bei der Queue bedeutet es, dass jemand noch einen Snapshot eines Zeigers für den (ehemaligen) Listenanfang der Queue hat, er aber noch nicht dazu gekommen ist, ein CAS für das echte dequeuen auszuführen (das dann sowieso scheitern wird, weil der Listenanfang ja bereits weitergezogen ist). Warum braucht er dazu überhaupt einen hazardpointer? Naja, er muss vor dem CAS die next-Referenz lesen (d.h. der andere darf nicht einfach deallozieren) und dann im CAS versuchen den momentanen Listenanfang gegen die next-Referenz einzutauschen.

Wie oben schon gesagt, kann ich nur wiederholen: Man kann bei solchen Sachen nicht einfach Methode X nehmen und blindlinks irgendwie einsetzen. Es hängt extrem stark vom konkreten Algorithmus ab, ob das dann überhaupt noch korrekt ist.

Das nächste ist das ich nicht glaube das dieser Mechanismus mit einer wirklich großen Anzahl an Threads (>10000) gut skaliert.

Und Locks machen das oder wie?
Erwartest du ernsthaft eine "Silberkugel" die alle Parallelitätsprobleme löst? Und dann auch noch so, dass jeder Idiot der 10000 Threads erzeugt ohne Probleme damit durchkommt?
Man müsste auch mal überlegen was genau mit Thread hier gemeint ist, es könnte sein, dass pro Kernelthread + Core (letzteres für Syscalls) ausreichend ist.

da mein Mathe einfach zu schlecht ist, um es irgendwie beweisen zu können

Was (reale) Performance angeht wüsste ich nicht, wie man da irgendwas auf Papier beweisen kann.

59

OS-Design / Re:Locking innerhalb des Kernels

« am: 12. August 2011, 18:27 »

Unwahrscheinlich ist immer schön, aber d.h. trotzdem nicht unmöglich und solange nichts passiert ist es ja gut und schön, aber wenn was passiert, nicht so toll

*sigh* Ich sags nochmal: Ich habe in dem Kontext an den du dachtest in keinster Weise reference-counting als Lösung vorgeschlagen und hab im Letzten Post auch klar gesagt, dass dafür hazard pointer unter anderem deswegen besser sind - wobei der eigentlich Grund ist, dass reference-counting es nicht ermöglicht die Dinge echt freizugeben und das benötigte DoppelCAS. Und bei dem Algorithmus den ich vorgeschlagen habe, hast du effektiv zu wenig speicher um 2^32 bzw. 2^64 Hazard pointer auf den Cache zu haben, insofern kann der referenzcounter da praktisch nicht overflowen.

60

OS-Design / Re:Locking innerhalb des Kernels

« am: 12. August 2011, 17:17 »

Ich glaube das war so, das jeder Pointer, durch nen "Counter" (weil der immer nur um eins erhöht wird) "geschützt" wird und das Problem war, das wenn die Zeit zw. 2 Zugriffen eines Threads zu lange ist, dass dann das Objekt freigegeben werden kann und durch nen anderen Thread wieder alloziert wird und dann der Counter zufällig den selben Wert hat wie der Thread der nun nach längerer Zeit wieder darauf zugreift, aber das Objekt ist jetzt nicht mehr das gleiche.

Korrekt. Aber ich sags nochmal: Das hat NICHTS mit dem Algorithmus den ich meinte zu tun. Was wiedermal bestätigt, dass man über einen konkreten Algorithmus reden sollte und nicht allgemein über irgendwas undefiniertes. Bei meinem Algorithmus von oben hat der reference-counter nur einen Overflow (was ja erst das Problem auslöst), wenn man ca. 4Mrd Leute hat, die eine Reference auf den Cache halten.

Wovon du hingegen sprichst, ist nicht wirklich reference-counting (wird aber so bezeichnet), sondern eine Art Versionierung bei der der Counter angibt, welche Version des Zeigers man gerade hat. Wenn man den Zeiger verändert, zählt man die Version hoch und alle anderen stellen dann fest, dass sie eine alte Version haben (obwohl eventuell der Zeiger vollkommen gleich ist). Dabei wird aber immer um 1 hochgezählt (und niemals runter), d.h. ein Overflow ist realistisch, aber es ist wohl extrem unwahrscheinlich, dass genau 4Mrd. Änderungen an diesem Zeiger zwischen meinem Snapshot und meinem Überprüfen (zu welchem Zweck auch immer) sind und zusätzlich noch der eigentliche Zeiger genau zu dem Zeitpunkt gleich. Der einzige Nachteil ist wie gesagt, dass man zum Ändern einen DoppelCAS braucht, was es auf x64 teilweise nicht gibt, damit man den Pointer+Counter atomar ändert. Aber ich sags nochmal: Von der Art reference-counting habe ich NICHT geredet und die Art sollte man besser durch hazard pointer ersetzen.
Übrigens kann man mit der Art reference-counting das Objekt nicht vollständig freigeben, weil andere noch auf der Referenz rumnudeln könnten (und auf den Counter vertrauen können müssen), d.h. sie Lösen zwar das ABA-Problem, aber man kann trotzdem nicht freigeben. Hazard pointer dagegen lösen beide Probleme.

und auch ob sie theoretisch 100% sicher sind

ja, das kann ich mit 100%iger Sicherheit sagen bzw. so sicher wie man sich sein kann, wenn man das für eine Queue bereits in einem Theorembeweiser selbst gezeigt hat und einen Beweis in selbigen für einen Stack kennt.

ob die performancemäßig [...] besser oder schlechter sind als Reference-Counting

Besser, im speziellen ist das DoppelCAS unschön.
Nachteil ist halt (im Vergleich zu der Art von reference-counting die ich bezogen auf Caches genannt habe) dass man nicht sobald wie möglich freigeben kann, sondern immer ein paar Referenzen hält und dann mehrere auf einmal freigibt (sonst kommt man nicht auf O(1) amortisiert fürs freigeben).

Ich habe eben ein Paper über Hazard Pointer gelesen und die sollen sehr viel performanter sein als Spinlocks sein.

Die meisten lockfreien Algorithmen skalieren massiv besser als Algorithmen mit Locks (zumindest sagen das alle Performancegraphen die ich dazu in Papern gesehen habe). Im speziellen hat man auch keine Probleme mit priority inversion, Deadlocks oder ein Problem falls ein anderer Thread der einen Lock hält abkackt, das sollte man auch nicht unterschätzen. Und sie skalieren besser, weil andere währenddessen ihre Aktion abarbeiten können, was bei einem Spinlock offensichtlich nicht geht. Auch wenn jeder einzelne Thread ein paar atomare Reads mehr macht.

Aber kann es sein, dass man die Verwaltung der Pointer trotzdem durch Locking sichern muss?

Wenn man ein Array fixer Größe (#Threads * #MaxHazardPointerProThread) dann auf jeden Fall nicht, da es ein Thread nur den eigenen Teil schreib und alle anderen Teile nur liest. Auch spielt es hier keine Rolle ob atomar gelesen wird oder nicht.
Für denn Fall, dass man das dynamisch vergrößern (zumindest was die Threadzahl angeht) behauptet Michaels, dass man es auch lockfrei hinbekommt. Darüber hab ich mir aber noch keine Gedanken gemacht ehrlich gesagt.

Aber wie ich schon einiges weiter oben sagte und FlashBurn zwei Posts weiter oben, kommt es bei der Art von Algorithmen _extrem_ auf die konkreten Details an. Im Speziellen sollte man _niemals_ die Reihenfolge von Reads/Writes auf globale Speicherzellen (die btw. von jedem Paper als atomar angenommen werden) auch nur ein bisschen ändern (auch wenn man meint, dass es korrekt wäre), kann ich aus eigener Erfahrung nur sagen

edit:

Meines Wissens nach gibt es dagegen nur 2 100%-tig sichere Abhilfen: zum einen ein richtiger atomarer Lock  [...]

Verstehe ich nicht. Ein CAS macht genau das?

aber soweit ich weiß sind viele von denen auf ein einigermaßen vorhersagbares zeitliches Verhalten des Code angewiesen

Das ist Humbug. Im Speziellen (siehe oben) hat es nichts mit der Zeit zu tun, sondern mit der Anzahl der Änderungen bei Versionierung/Reference-counting und wie oben gesagt, exakt ~4Mrd Änderungen und dann noch der gleiche Pointer ist einfach nur unwahrscheinlich.