Thema: Locking innerhalb des Kernels

[bluecode]

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?

[erik.vikinger]

Hallo,

verschiebe ich auf einen Eintrag im Wiki

Im Wiki ist natürlich auch eine super Idee.

den ich hoffentlich irgendwann Mitte/Ende der Woche anfange

Keine unnütze Hektik.

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.

Hm, naja ich hätte jetzt schon behauptet das ich den Unterschied zwischen lock-free und wait-free verstanden hab, aber ich lass mich auch gerne von Deinem Wiki-Artikel besser aufklären.

Ist das was du suchst eine Menge, die folgendes unterstützt:
[.....]

Ja, an sowas bin ich auf jeden Fall auch interessiert. Mir schwebt da z.B. die Thread-Liste der Prozesse vor die wohl häufig von vielen Seiten parallel bearbeitet werden muss.

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

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, schon auf einer modernen ccNUMA-Architektur wird das selbst vom Cache-Kohärenz-Protokoll nicht zugesichert (selbst wenn es möglich wäre die Liste in unendlich kurzer Zeit zu durchlaufen) dort hat auch jede CPU eine eigene Sicht auf den aktuellen Gesamt-Zustand des Speichers (eben weil der Gesamt-Zustand nicht in unendlich kurzer Zeit erfasst werden kann).

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

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 oder aber das der Benutzer sicherstellen muss das er das Set nie mehrmals mit dem selben X befüllt (bei meinen Thread-Listen möchte ich die zweite Variante nutzen weil ich dort die Thread-IDs aus einem CPU-lokalem Cache holen möchte der nur wenn er leer ist aus der zentralen und gelockten Ressource nachbefüllt wird so das eigentlich nie mehrmals die selbe ID in Benutzung ist, je nach Cache-Größe kann das auch trotz des Locks in der Zentrale ziemlich performant werden).

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.

Ja, daran hab ich auf jeden Fall großes Interesse. Vor allem wenn ich nach dem Lesen des Artikels in der Lage bin so einen Beweis für meine spezifische Problemlösung selber zu erbringen.

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.

Das LL/SC je nach Plattform verschiedene Einschränkungen haben ist klar, verschachtelbar sind die meines Wissens nach auf keiner real existierenden CPU. Für was würde man denn so eine Verschachtelung benötigen (LIFO-Prinzip voraus gesetzt)? Für meine CPU will ich ja auch auf LL/SC setzen, nur mit ein paar kleinen Enhancements wie z.B. das bereits der LL-Befehl meldet ob er überhaupt erfolgreichen eine Überwachung initiieren konnte so das die CPU wenigstens nicht unnütz rechnen muss wenn sie eh nicht erfolgreich sein kann (damit sie möglichst wenig Last erzeugt und die tatsächlich arbeitenden CPUs möglichst schnell vorwärts kommen), das mit dem Verschachteln ist zwar nicht ganz ohne Komplexität aber IMHO durchaus mit vertretbaren Coding-Aufwand umsetzbar so das ich bei guten Argumenten auch durchaus bereit bin sowas zu realisieren.

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 sehe schon, das mit den Lock-Free Algos wird ne harte Nuss

Einfach könnte ja jeder, aber echte LowLevel-Programmierer müssen schon ein wenig mehr drauf haben.


Grüße
Erik

[FlashBurn]

ironischerweise heißt die "Datenstrukturen"

Info-Student?

Hast du irgendeine Ahnung wo du ausgestiegen bist? Oder hast du garnicht verstanden was ich versucht habe zu erklären?

Also ich denke ich habe gar nicht verstanden was du versucht hast zu erklären, aber meine Frage/Bedenken läuft darauf hinaus, wie stellt man sicher, dass z.B. in einer Liste nicht 2x das gleiche Element eingetragen wird (beim Locking ist das ja ohne weiteres so)?

[bluecode]

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.

[bluecode]

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

[erik.vikinger]

Hallo,

Genau sowas meine ich

Gut, ich glaube dann reden wir zumindest nicht aneinander vorbei. Ob ich das alles auch so begriffen hab wie Du das eventuell erwartest kann ich momentan aber (noch) nicht sagen.

was korrekt ist hängt hier sehr stark von Forderungen an die Operation ab

Ganz recht. Ich bleibe mal bei der Prozess-spezifischen Thread-Liste, da ist es wichtig das man sagen kann ob Thread X vorhanden ist oder nicht, eine falsche Antwort könnte aber verschmerzbar sein weil der Aufrufer dann einfach davon ausgeht das die Einfüge-/Entfernen-Operation noch nicht durchgeführt wurde. Wenn der Aufrufer also nicht sicherstellen kann das die entsprechende Operation wirklich erfolgreich durchgeführt wurde dann muss er auch mit beiden möglichen Antworten zurecht kommen und wenn der Aufrufer sich eigentlich sicher ist das Thread X im Prozess vorhanden ist dann muss er eigentlich auch nicht die Liste abfragen. Kritisch ist da schon eher das Freigeben von den entsprechenden Strukturen (Thread-Descriptor) da diese ja eventuell noch bearbeitet werden können während sie bereits aus der Liste entfernt werden. 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. Ansonsten wollte ich die Menge der möglichen Operationen je nach Thread-Typ einschränken um so unnötige Kollisionen und unnötige Zusicherungen zu vermeiden.

die man im sequenziellen Umfeld automatisch geschenkt bekommt und über die man nie nachdenkt, weil niemand parallel versucht meine Operation zu untergraben

Dieses Nachdenken über die Nebenläufigkeit muss den Programmierer erst richtig eingeimpft werden so das dieser das bei jeder Zeile schon ganz unbewusst mit erledigt, dann fallen diesem Programmierer auch mehr von den potentiellen Stolperfallen auf die einem "normalen" Programmierer nicht auf fallen.

Aber hier müssen solche Forderungen plötzlich explizit gestellt werden (und kosten dann auch Komplexität/Performance).

Das ist ganz klar, es ist IMHO extrem wichtig das man vor der ersten Code-Zeile sich genau überlegt welche Anforderungen man eigentlich erfüllen möchte/muss.

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

Ich meinte damit eher ob man die Operatoren für das Set eventuell vereinfachen kann wenn man bestimmte Zusicherungen schon extern abhaken kann. Wenn ich z.B. zusichern kann das ich alle IDs erst dann wieder in den globalen Pool zurück gebe wenn diese sicher nicht mehr in Verwendung sind und auch das allozieren von IDs aus diesem Pool immer ordentlich funktioniert das man dann eventuell die Komplexität der Set-Operatoren reduzieren kann. Es kommt eben drauf an welchen Grad an Korrektheit man tatsächlich benötigt.

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

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

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.

Da bist Du mir gegenüber klar im Vorteil, ich kenne gar keinen Korrektheitsbegriff. Aber ich kann mir vorstellen das man noch andere Kriterien für die Korrektheit einer konkreten Implementierung definieren kann außer nur das es einen gültigen Linearisierungszeitpunkt geben muss. Bei z.B. einem Baum das er nie über einen gewissen Grad hinaus unausgeglichen ist.


Grüße
Erik

[bluecode]

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
}


[erik.vikinger]

Hallo,

Meine Philosophie wäre "eine Operation garantiert, was sie im worst-case des Verhaltens anderer noch garantieren kann".

Aus meiner Sicht richtig aber noch nicht vollständig, auch das eigene zeitliche Verhalten muss mit berücksichtigt werden (der CPU-Kern könnte ja gerade an einer kritischen Stelle mal für ein paar Millisekunden angehalten werden).

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.

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

Ein Enqueue dürfte ungefähr so aussehen ......

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.

Ich selbst will ja LL/SC unterstützen aber mit der Erweiterung das LL bereits meldet ob eine HW-Überwachung auch erfolgreich initiiert werden konnte so das mein Äquivalent das wäre (hier müsste Tail eigentlich immer zuverlässig auf das Ende zeigen) :

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();
}LL lädt den Wert auf den Parameter 1 zeigt immer nach Parameter 2 (egal ob die Überwachung initiiert werden konnte oder nicht) und meldet zurück ob eine Überwachung initiiert werden konnte, CS prüft ob die Überwachung am Parameter 1 noch intakt war und schreibt gegebenenfalls den Parameter 2 dort hinein. Das deaktivieren der IRQs sorgt im User-Mode dafür das dieser kurze Code-Abschnitt unterbrechungsfrei und störungsfrei durchgearbeitet werden kann (im Kernel-Mode ist das verzichtbar) so das die 2 PANICs eigentlich nie zuschlagen sollten.


Grüße
Erik

[bluecode]

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

[FlashBurn]

Ich stelle mal folgendes auf:

Im Kernel (ausgehend davon, das während man ein Lock hält die Ints aus sind) kann man ruhig Locks nehmen, da die meisten Probleme (außer Deadlock) dort nicht existieren. Das sollte wahrscheinlich sogar das performanteste sein (und auch der Stromverbrauch, da man beim spinnen "pause" nutzen kann) und im UserSpace setzt man am besten auf Lock-Free (sollte Performance mäßig und auch Problem mäßig, vorrausgesetzt die Algos sind in Ordnung, die bessere Variante sein) mit der Einschränkung nur da wo paralleler Zugriff auch Sinn macht (z.B. Dateisystem). Denn es gibt auch viele Bsp. wo paralleler Zugriff einfach kein Sinn macht und man alles eh serialisieren muss (z.B. Laufwerke).

Kann man das so stehen lassen?

[bluecode]

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.

[FlashBurn]

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

Jap, meine Idee war irgendwann mal, das es nicht schlecht wäre alles Lock-Free zu haben, aber bestimmte Argumente (die mich überzeugen) sprechen halt dagegen, wenn es darum geht das die Ints aus sind.

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.

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.

Solch eine Diskussion hatten wir schonmal und ich (ich möchte meinen erik auch) bin irgendwie nicht davon überzeugt. Allerdings nur auf Grund eines einzigen Problemes. Wozu hat man dann noch Prioritäten (nur noch um die Länge der Zeitscheibe zu bestimmen)? Denn bei einer solchen Variante kann nicht mehr sichergestellt werden, das die Threads mit der höchsten Priorität auch wirklich immer laufen und auch die Verteilung kann nicht sichergestellt werden.

Problem (was ich sehe) ist doch das auf CPU-A 2 Threads mit hoher Priorität laufen (und beide immer laufen) und auf CPU-B 2 Threads mit normaler Priorität laufen (und beide wieder immer laufen). Beide CPUs haben keinen Grund der anderen einen Thread wegzunehmen, aber eigentlich (laut Priorität) müssten auf beiden CPUs jeweils einer der beiden Threads mit hoher Priorität laufen.
Das nächste ist, was passiert wenn jetzt ein Thread mit einer Priorität erzeugt wird, die genau zw. hoch und normal liegt, und das auch noch auf der CPU wo die beiden Threads mit hoher Priorität laufen? Wird der neue Thread in eine globale Queue gepackt? Wenn ja, wie kommt dann der Thread auf CPU-B (wo er ja eigentlich laufen müsste, da seine Priorität höher ist als die beiden Threads die dort schon laufen)?

[bluecode]

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.

[erik.vikinger]

Hallo,

Wenn derjenige der den Lock hat, nich geschedult wird oder abgebrochen wird, gehts garnichtmehr weiter.

Deswegen ja das Abschalten der INTs im User-Mode. Die einzigste Problemursache die dann noch existiert sind Exceptions innerhalb des gelockten Abschnitts (z.B. Speicher-Schutz-Verletzung) und wenn sowas passiert ist eh alles zu spät.

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.
Klar ist der Code so nicht Lockfrei aber es gibt eine determinsitisch bestimmbare Obergrenze wie lange der Lock maximal gehalten wird und das ist die Zeit die der kurze Code (dürften kaum mehr als 10 Assemblerbefehle sein) eben braucht. Deswegen ja das Abschalten der INTs.

aber die Definition ist so denke ich nicht gedacht

Sorry, aber was die Definition sich denkt ist mir persönlich ziemlich wurscht, mich interessiert eine funktionierende Lösung und funktionierend bezieht sich auf Korrektheit (in dem Umfang den ich benötige) und auf typische Performance (wenn es ein paar extrem seltene Ausreißer gibt mach ich mir da keine großen Sorgen solange trotzdem die Korrektheit gewährleistet ist).

und da will man wohl cli/sti nicht erlauben bzw. nichtmal per syscall

Ich denke das hängt davon ab wie das realisiert ist. Wenn z.B. die Hardware (CPU) sicher stellt das die INTs nur für einen klar begrenzen Zeitraum (z.B. maximal die nächsten 20 Assembler-Befehle) deaktiviert sind dann ist es IMHO kein Problem sowas zu erlauben.


Was mich an den Lock-Frei-Algorithmen stört ist das die immer nach sehr viel Arbeit aussehen wogegen ein gelockter Mechanismus meistens nur aus einem sehr kurzen und linearen Code-Abschnitt besteht. Rein subjektiv würde ich sagen das die Lock-Frei-Algorithmen eine ziemlich große System-Last erzeugen und das selbst in den Situationen wo der betreffende Thread nicht wirklich vorwärts kommt. In meinem Beispiel von Heute Früh verursacht nur das while eine permanente aber geringe Last (die ohne das PAUSE zwar höher wäre aber immer noch verhältnismäßig klein bliebe), selbst die CAS-Variante vom bluecode ist da schon deutlich belastender für das System als ganzes. Über den Energiebedarf können wir auch gerne nachdenken aber den sehe ich momentan gar nicht mal als das wesentliche Kriterium.


@FlashBurn:
Dein Szenario mit dem Scheduler ist zwar gut aber ich würde in diesem Thread gerne zuerst das mit dem Lock-Frei an einem möglichst einfachen Beispiel klären bevor wir uns einem so komplexen Szenario zuwenden.
edit: Bei den Prioritäten muss ich Dir aber zustimmen, trotzdem sollten wir das IMHO entweder später oder in einem anderen Thread diskutieren.


Grüße
Erik

[FlashBurn]

@erik

Ich wollte das mit dem Scheduler auch nur mal einwerfen Sollte jetzt nicht wieder in eine Diskussion ausarten.

Mir ist das mit den Locks auch erstmal wichtiger!

Wenn wir hier über Locks/Lock-Free diskutieren können wir dann aber bitte immer eindeutig sagen das wir von einem "normalen" System reden bzw. wenn du von deiner CPU redest, dann muss das klar erkennbar sein. Ich will darauf hinaus, das Ints im UserSpace immer an sind und nicht ausgeschaltet werden können!

[erik.vikinger]

Hallo,

Mir ist das mit den Locks auch erstmal wichtiger!

Gut.

bzw. wenn du von deiner CPU redest, dann muss das klar erkennbar sein

Einverstanden. Aber ich würde zumindest die Variante mit "normalem" LL/SC auch gerne mit einschließen.

Deswegen hätte ich ja auch gerne ein Beispiel dafür :

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

Nur CAS zu betrachten fände ich hierbei nicht gut.


edit:

das Ints im UserSpace immer an sind und nicht ausgeschaltet werden können!

Wenn Du dir aber mal den Titel des Threads anschaust sollten wir sicher schnell einig werden das auch die Szenarien mit ausgeschalteten INTs mit berücksichtigt werden sollten.
Mal ganz davon abgesehen wie das konkret erreicht wird. Das ich das auch im User-Mode haben will liegt vor allem daran das ich mir einen Performancevorteil erhoffe wenn ich dem User-Mode zumindest kurzfristig Kernel-Privilegien gebe.


Grüße
Erik

[Svenska]

Hallo,

Beispiel: Der Ansatz des Giant Lock funktioniert prima, ist einfach und ist verdammt schnell für Uniprozessorsysteme (da sind die Locks immer frei). Auch bei 2..4 CPUs ist er gut

Du meinst also der Giant Lock (vorallem wenn ich da zwangsläufig an Linux = monolith denke) ist auch noch bei 2 bis 4 CPUs gut? Das kann ich einfach nicht glauben.

Dann lässt du es halt bleiben.

Allerdings sollten wir erstmal klären, was genau meinst du mit Giant Lock? Einen Lock der im Endeffekt den gesamten Kernel schützt?

Exakt: Nur ein Thread im System kann gleichzeitig im Kernel aktiv sein.

Würde ich den bei mir verwenden, würde schon das Initialisieren des Kernels linear pro CPU ansteigen und bei nem monolithen dürfte es noch schlechter sein als bei nem MikroKernel (zwecks das die ganzen Subsysteme außerhalb des Kernels liegen und erstmal nicht direkt davon betroffen sind).

Richtig, aber da verwechselst du wieder Skalierbarkeit ("lineares Zeitverhalten") mit Performance ("absolute Dauer"). Wenn deine Initialisierung 1s @ 1CPU dauert und 2s @ 64CPU, dann spielt das effektiv keine Rolle.

Angenommen, Threads verbringen nur einen sehr geringen Teil ihrer Zeit im Kernel und den Großteil ihrer Zeit rechnen oder schlafen sie. Für n CPUs hast du maximal n aktive Threads. Die Kollisionswahrscheinlichkeit, dass zwei Threads gleichzeitig in den Kernel wollen, ist für n=1 gleich Null, bei unendlich vielen CPUs gleich Eins, dazwischen dürfte es ein logarithmisches Verhalten haben. Das ändert sich grundsätzlich auch bei feineren Locks nicht (Skalierbarkeit bleibt schlecht, Performance wird wesentlich verbessert).

Ich vermute, dass lockfreie Algorithmen aufwändiger und damit langsamer sind. Wenn also (Kollisionswahrscheinlichkeit * durchschnittliche Wartezeit) kleiner ist als der Overhead durch einen lockfreien Algorithmus, dann solltest du Locks implementieren, sonst nicht. Daher meine unbewiesene Behauptung, dass für n=2..4 Locks das Optimum sind (und auch Giant Locks nicht unbedingt das schlechteste). während großem n jegliche Locks eher schädlich sind.

Und schon bist du wieder bei Kompromisslösungen. (Es lässt sich übrigens für jeden Algorithmus ein Worst Case konstruieren, der ihn schlecht aussehen lässt.)

Im Kernel (ausgehend davon, das während man ein Lock hält die Ints aus sind) kann man ruhig Locks nehmen, da die meisten Probleme (außer Deadlock) dort nicht existieren.

Nur, weil ein Algorithmus ein Problem löst, welches in einem gewissen Kontext nicht existiert, ist er noch lange nicht schlecht. Aber ja, im Kernel kann man Locks benutzen - tun die meisten Betriebssysteme ja auch.

Das sollte wahrscheinlich sogar das performanteste sein (und auch der Stromverbrauch, da man beim spinnen "pause" nutzen kann) und im UserSpace setzt man am besten auf Lock-Free (sollte Performance mäßig und auch Problem mäßig, vorrausgesetzt die Algos sind in Ordnung, die bessere Variante sein) mit der Einschränkung nur da wo paralleler Zugriff auch Sinn macht (z.B. Dateisystem).

Das eine hat mit dem anderen nichts zu tun: Code ist Code, ob der jetzt im Kernel oder im Userspace rumliegt, ist für die Performance von Algorithmen relativ egal. Locks skalieren halt scheiße, das betrifft die Kernel-Interna selbst aber genauso wie die Brücke zwischen Userspace und Kernel. (Wenn 20k Threads gleichzeitig READ aufrufen, ist ein Lock für die benutzten Datenstrukturen schlecht, auch im Kernel.) Im eigentlichen Userspace kann dir das als OS-Entwickler übrigens egal sein, weil ob die einzelnen Apache-Threads nun lockfrei auf den Apache-Kern zugreifen oder nicht, ist nicht dein Problem.

Es hängt halt grundsätzlich vom Einzelfall ab und von den Kosten, die entstehen. Wenn man mit dem Worst Case rechnet, dann sind Locks böse (Deadlock), aber normalerweise geht man vom Average Case aus und versucht, den zu optimieren. Und für wenig gleichzeitige Zugriffe sind Locks halt recht effizient.

Denn es gibt auch viele Bsp. wo paralleler Zugriff einfach kein Sinn macht und man alles eh serialisieren muss (z.B. Laufwerke).

Laufwerke sind dank NCQ und modernen COW-Dateisystemen durchaus parallel ansprechbar. Serialisieren tut dann erst der Controller. Paralleler Zugriff auf eine serielle Schnittstelle ist da schon schlimmer.

Gruß,
Svenska

[FlashBurn]

Angenommen, Threads verbringen nur einen sehr geringen Teil ihrer Zeit im Kernel und den Großteil ihrer Zeit rechnen oder schlafen sie.

Auf welche Art von Arbeiten trifft das denn zu und wo kommt die Arbeit her?

Das eine hat mit dem anderen nichts zu tun: Code ist Code, ob der jetzt im Kernel oder im Userspace rumliegt, ist für die Performance von Algorithmen relativ egal.

Dem muss ich klar wiedersprechen. Zwecks für den Mutex musst du in den Kernel (kostet Zeit), bei nem Lock-Free Algo nicht. Genauso muss du bei nem Mutex der im Kernel ist, nicht erst in den Kernel. Also macht es doch nen Unterschied.

Im eigentlichen Userspace kann dir das als OS-Entwickler übrigens egal sein

Nicht wenn man den UserSpace mit zum OS zählt, was bei einem MikroKernel ganz klar der Fall ist.

Und für wenig gleichzeitige Zugriffe sind Locks halt recht effizient.

Um wieder zum Giant Lock zu kommen und zu einem Monolithen. Ich geh mal davon aus, das dort relativ viel auf den Kernel zugegriffen wird, weil einfach so ziemlich alles im Kernel ist (bei nem MikroKernel eigentlich nicht anders, da man ständig aufs IPC zugreifen muss).

Das wichtigste ist aber, wenn ich jetzt nach deiner Philosophie gehe (den Average-Case optimieren und den beachten), dann ist es im Endeffekt wahrscheinlich egal ob Lock oder Lock-Free, weil einfach nicht genügend Zugriffe zustande kommen werden (wenn das der Average-Case ist). Gehe ich aber davon aus, das ich mit sehr vielen Gleichzeitigen Zugriffen rechnen muss ist der Worst-Case schon interessant.

Was ist z.B. wenn ich gleichzeitig ein Video gucke und Kompiliere, dann könnten die ständigen Festplattenzugriffe bei einem Giant-Lock schon ein Problem werden.

[Svenska]

Angenommen, Threads verbringen nur einen sehr geringen Teil ihrer Zeit im Kernel und den Großteil ihrer Zeit rechnen oder schlafen sie.

Auf welche Art von Arbeiten trifft das denn zu und wo kommt die Arbeit her?

Das betrifft so ziemlich alle normalen Anwendungen:

• interaktive Anwendungen warten die meiste Zeit auf Benutzereingaben und reagieren
• Daemonen warten die meiste Zeit auf Anfragen von außen und reagieren darauf
• Hintergrundprozesse tun Dinge, wenn sonst keiner was tut (System aktualisieren, Defragmentieren, etc.)
  

Das eine hat mit dem anderen nichts zu tun: Code ist Code, ob der jetzt im Kernel oder im Userspace rumliegt, ist für die Performance von Algorithmen relativ egal.

Dem muss ich klar wiedersprechen. Zwecks für den Mutex musst du in den Kernel (kostet Zeit), bei nem Lock-Free Algo nicht. Genauso muss du bei nem Mutex der im Kernel ist, nicht erst in den Kernel. Also macht es doch nen Unterschied.

Im reinen Userspace musst du für einen Mutex nicht durch den Kernel, wenn er in der C-Bibliothek (auch Userspace) korrekt implementiert ist. Relevant für den Kernel sind alle diese Dinge nur, wenn es um Kernel-Funktionalität geht - und das meinte ich mit Kernel-Userspace-Brücke.

Und für wenig gleichzeitige Zugriffe sind Locks halt recht effizient.

Um wieder zum Giant Lock zu kommen und zu einem Monolithen. Ich geh mal davon aus, das dort relativ viel auf den Kernel zugegriffen wird, weil einfach so ziemlich alles im Kernel ist (bei nem MikroKernel eigentlich nicht anders, da man ständig aufs IPC zugreifen muss).

Was für Anwendungen benutzt du so?

Das wichtigste ist aber, wenn ich jetzt nach deiner Philosophie gehe (den Average-Case optimieren und den beachten), dann ist es im Endeffekt wahrscheinlich egal ob Lock oder Lock-Free, weil einfach nicht genügend Zugriffe zustande kommen werden (wenn das der Average-Case ist).

Das meinte ich. Am Ende des Tages ist es scheißegal.

Gehe ich aber davon aus, das ich mit sehr vielen Gleichzeitigen Zugriffen rechnen muss ist der Worst-Case schon interessant.

Ja, maximale Anzahl der theoretisch maximal möglichen gleichzeitigen Zugriffe == Anzahl der logischen CPUs (wenn du ein bisschen aufpasst). Das heißt, ein Algorithmus, der langsam und lockfree ist, ist auf einem System mit wenigen logischen CPUs langsamer als ein Algorithmus, der Locks verwendet und schlecht skaliert.

Was ist z.B. wenn ich gleichzeitig ein Video gucke und Kompiliere, dann könnten die ständigen Festplattenzugriffe bei einem Giant-Lock schon ein Problem werden.

Nö. Erstmal hat dein Block-Layer einen Plattencache. Dann hat der Video-Player einen Cache, um den Videostrom vor der Anzeige schon zu dekodieren (viel rechnerei, wenig Syscalls!) und um wechselnde Festplattenzugriffszeiten abzufedern und liest immer nur Stücke aus der Videodatei. Der Compiler wiederum liest extrem viele Dateien (hält die Locks immer nur kurzzeitig) und rechnet ewig an einer Datei rum (wenig Syscalls!).

Ich glaube, du überschätzt da den Einfluss ganz gewaltig. OpenBSD nutzt immernoch Giant Locks (Sicherheit), FreeBSD und Linux setzen auf fein granulierte Locks (Performance). Lockfree wird da relevant, wo es um Skalierbarkeit geht, aber auch da hängt viel mehr vom Design und Algorithmus selbst ab als von der Implementation selbst. 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?

Gruß,
Svenska

[bluecode]

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.