Lowlevel

Ich glaube du verwechselst da was mit den Hazard-Pointern

Full ACK!
Ich hab auch immer noch nicht so ganz begriffen an welcher Stelle genau die eigentlich Sicherheit bringen sollen. Ein Szenario was ich glaube ich so langsam begriffen hab ist das Datenstrukturen niemals direkt modifiziert werden sondern nur kopiert und dabei modifiziert und zum Schluss passend eingehangen werden, hier kann es aber passieren das wenn mehrere Threads gleichzeitig das probieren das dieser Job doppelt so oft als nötig durchgeführt wird und dabei eine ziemliche Menge an Daten kopiert wird so das ich da (je nach Strukturgröße) kaum an einen echten Performancevorteil für die Lock-Free-Version glauben kann. Es kommt dabei zwar nicht mehr zu einem Dead-Lock aber eventuell zu einem gefühlten Live-Lock weil einige Threads sehr oft den selben Job immer wieder durchführen bis sie dann auch tatsächlich mal erfolgreich damit sind. Hier könnte ein kleine Schleife die versucht einen Lock zu bekommen und nach jedem Fehlversuch ein PAUSE macht eventuell deutlich schonender mit den globalen Ressourcen (Speicherbandbreite usw.) umgehen.

Ich schätze mal wir können uns hier auf ein "hängt von der gegebenen Situation ab" einigen. ;)

Der Gedanke mit dem Skalieren ist gar nicht mal so verkehrt, aber seien wir ehrlich, ich denke nicht das die Performance von bisherigen Lock, Lock-Free oder Wait-Free (die ja eh performancemäßig schlecht sind) Algos in den Deminsionen irgendwas reißen können.

Was mir persönlich an diesen Hazard-Pointern nicht gefällt ist das die selber nicht gut skalieren. Man kann das zwar für eine im Voraus bekannte Anzahl an Threads recht gut implementieren (vom Speicherverbrauch bei vielen Threads mal abgesehen) aber wenn das eben nicht bekannt ist (und das trifft bei einem General-Purpose-OS IMHO immer zu) sind Hazard-Pointer wohl keine gute Wahl und werden in einer dynamischen Variante sicher auch kein O(1) mehr erreichen (oder höchstens mit irgendwelchen Randbedingungen die man in einer unvorhersehbaren General-Purpose-Umgebung eben nicht zusichern kann).

Wenn wir von 16 oder 32 Threads reden, sind ja anscheinend (da mein Mathe einfach zu schlecht ist, um es irgendwie beweisen zu können) Lock-Free Algos wesentlich besser, wieso sollten sie also bei >10000 Threads wieder schlechter werden?

Ich glaube gar nicht mal das es hierbei allzu sehr auf die Anzahl der Threads ansich ankommt sondern wohl eher darauf wie vorhersehbar oder dynamisch diese ist. Was mir als nächstes in dem PDF von diesem Michael nicht gefällt ist das er mit LL/SC einfach nur ein CAS emuliert, ich weiß ja nicht genau was für Beschränkungen PowerPC dem LL/SC-Pärchen auferlegt aber wenn diese nicht allzu extrem sind dann kann man damit sehr viel besseres bauen (falls man die Idee hinter LL/SC wirklich verstanden hat). Ich unterstelle daher einfach mal (ohne es zu beweisen, bitte widersprecht mir wenn ich mich irre) das die gezeigten Bench-Mark-Ergebnisse von keiner relevanten Bedeutung sind.

Zumal du bei einer solchen Thread Anzahl wahrscheinlich ganz andere Probleme hast.

Wieso? Wir haben doch hier auch schon darüber diskutiert das ein HTTP-Server der einfach forkt durchaus eine gute Performance bringen kann (und da war wimre von mehr als 10000 Prozessen die Rede), also zumindest das damalige Linux hat mit einer großen Anzahl an Prozessen keine Probleme bekommen und von einem modernen General-Purpose-OS erwarte ich auch keine Probleme mit einer entsprechenden Anzahl an Threads (ich könnte jetzt natürlich erzählen das es in einem 32Bit-Flat-Memory-System eventuell schwierig werden könnte entsprechend viele Stacks in den einen virtuellen Prozess-Adressraum zu quetschen aber das hatten wir ja schon mal ;)).

Zitat von: erik.vikinger
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.

Weiß ich doch, ich wollte damit nur ausdrücken das wenn es in den Bereich des Möglichen kommt die Version zu treffen das dann der eigentliche Pointer auch keine so große Hürde mehr ist.

Der Suchvorgang ist nur dazu da Speicher freizugeben, d.h. das kann man ne ganze Weile rausschieben.
[....]
Deswegen habe ich oben auch schon gesagt, dass es problematisch sein kann, da man bei vielen Threads ewig keinen Speicher freigibt.

Aha, ich denke jetzt verstehe ich etwas besser. Der Speicherverbrauch ist dann aber das eigentliche Problem (was durch die exponentiell großen internen Listen in diesen Hazard-Pointern noch zusätzlich verstärkt wird) und in einer Umgebung mit einer dynamischen Anzahl an Threads könnte es dann eventuell zu einem Out-of-Memory kommen obwohl eigentlich genug Speicher da ist.

Zitat von: erik.vikinger
Nebst dessen das auch dieses Suchen auf ein einigermaßen deterministisches zeitliches Verhalten angewiesen ist.
Nein.

Und wie soll dann mein Szenario vom 12.08. Abends gelöst werden?

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.

Aber zum Entnehmen aus der Queue benötigt man dann ja doch wieder einen Lock oder einen weiteren Lock-Free-Algorithmus. Damit ist doch dann eigentlich die erforderliche Seriallisierung bereits erledigt oder meinst Du eine Single-Writer/Multiple-Reader-Situation?

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.

Okay, ich glaub das hab ich verstanden. Trotzdem bin ich der Meinung das man das mit LL/SC sehr viel besser hinbekommen kann und das ganz ohne irgendwelche Listen usw. Ich vermute der Grund warum das in dem PDF vom Michael so schlecht performt ist darin zu suchen das er eben ein CAS nachbaut obwohl das mit dem Next-Pointer sich mit LL/SC auch direkt lösen lässt (sogar mit extremen Einschränken beim LL/SC-Pärchen).

Zitat von: erik.vikinger
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? :roll:

Wenn jeder Thread eine andere Struktur locken und bearbeiten will dann schon (wenn jeder dieser Strukturen in einer anderen Cache-Line liegt dann gibt es nicht mal spürbare Performance-Probleme). Wenn alle durch ein Nadelöhr wollen (z.B. Anhängen an eine Queue) ist das natürlich was anderes aber das ist wohl sowieso kein Fall für Hazard-Pointer.

Erwartest du ernsthaft eine "Silberkugel" die alle Parallelitätsprobleme löst?

Natürlich nicht. Ich denke Hazard-Pointer können dann einen Vorteil bringen wenn es sich um wenige und vor allem um eine einigermaßen bekannte Anzahl an Threads handelt.

Und dann auch noch so, dass jeder Idiot der 10000 Threads erzeugt ohne Probleme damit durchkommt?

Ja, das schon. Erwartest Du da etwa Probleme?

Zitat von: FlashBurn am 13. August 2011, 12:00

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

Beweisen nicht aber plausibel erklären sollte möglich sein (unter der Voraussetzung das wir Computer als deterministische Systeme betrachten ;)).

Ich denke solche Themen dürften alle hier weiterhelfen.

Dem möchte ich mich ebenfalls anschließen.

Grüße
Erik

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 14. August 2011, 20:38

Zitat von: erik

Hier könnte ein kleine Schleife die versucht einen Lock zu bekommen und nach jedem Fehlversuch ein PAUSE macht eventuell deutlich schonender mit den globalen Ressourcen (Speicherbandbreite usw.) umgehen.

Das höre ich nicht zum ersten Mal, aber warum scheinen alle die Arbeiten dazu geschrieben haben zu einem anderen Ergebnis zu kommen? Bzw. wieso hört man aus der akademischen Welt nicht dass das absolut Unsinn ist?

Zitat von: erik

Was mir als nächstes in dem PDF von diesem Michael nicht gefällt ist das er mit LL/SC einfach nur ein CAS emuliert

Da wären wir wieder schön bei den Problemen von portablen Code, er wollte eine Variante zeigen, die auf allen Architekturen läuft, die irgendeine Art und Weise von CAS kann und da man mit LL/SC CAS emulieren kann, aber nicht umgekehrt, hat er sich wohl dafür entschieden.

Zitat von: erik

Wenn alle durch ein Nadelöhr wollen (z.B. Anhängen an eine Queue) ist das natürlich was anderes aber das ist wohl sowieso kein Fall für Hazard-Pointer.

Nur dieser Fall ist interessant, weil ansonsten hat man weder mit der einen Varianten, noch mit der anderen ein Problem (außer das Locking bei einzelnen Threads schneller ist als Lock-Free) und genau dieser Fall ist ein Fall für Lock-Free Algos und damit Hazard-Pointers.

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. Also wer macht mal nen Thread dazu auf ;)

Titel: Re:Locking innerhalb des Kernels
Beitrag von: Svenska am 14. August 2011, 21:32

Ich habe das Gefühl, dass ihr hier Skalierbarkeit und Performance verwürfelt... ob Hazard-Pointer oder Locks besser skalieren, sagt nämlich nichts darüber aus, was von beidem besser performt.

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, aber bei 64+ CPUs ist er halt scheiße.

Der Webserver skaliert besser, wenn er fork() benutzt, als wenn er poll() benutzt. Das sagt wiederum nichts über die absolute Performance aus und es stand dabei, dass sämtliche getesteten Betriebssysteme (einschl. Linux) während des Vernichtens der Prozesse nicht mehr reagieren; auch das hat interessante Konsequenzen unter Last.

So, jetzt könnt ihr bei dem Thema weitermachen. Ich halte fein granulierte Locks für eine gute Möglichkeit, weil ich sie (im Gegensatz zu den anderen hier genannten Methoden) verstehe. ;-)

Gruß,
Svenska

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 14. August 2011, 21:38

Hallo,

Zitat von: FlashBurn am 14. August 2011, 20:38

Das höre ich nicht zum ersten Mal, aber warum scheinen alle die Arbeiten dazu geschrieben haben zu einem anderen Ergebnis zu kommen? Bzw. wieso hört man aus der akademischen Welt nicht dass das absolut Unsinn ist?

Das wüste ich auch gerne mal, ich hab in der letzten Zeit auch mal etwas gesucht und einiges positives über Lock-Free gefunden, z.T. auch mit ansprechenden BenchMark-Ergebnissen drin. Das Problem ist das ich nur selten wirklich sagen kann ob da nicht eventuell die Gegenseite schlechter gemacht wird als sie ist (womit ich definitiv keine Absicht sondern aller höchstens Unkenntnis unterstellen möchte).

Zitat von: FlashBurn am 14. August 2011, 20:38

Da wären wir wieder schön bei den Problemen von portablen Code, er wollte eine Variante zeigen, die auf allen Architekturen läuft, die irgendeine Art und Weise von CAS kann und da man mit LL/SC CAS emulieren kann, aber nicht umgekehrt, hat er sich wohl dafür entschieden.

Wenn er sich für CAS entscheidet dann soll er auch eine Plattform nehmen die das nativ anbietet. Ein ordentlich implementierter CAS-Befehl ist mit Sicherheit schneller als zwei unabhängige LL/SC-Befehle (dafür sind letztere deutlich Leistungsfähiger so das man mit einem passenden SW-Algorithmus hier wieder schneller ist, bei ansonsten vergleichbarer Plattformperformance wie Speicherbandbreite/latenz usw., nebst dessen das LL/SC sicherer ist weil prinzipbedingt kein ABA-Problem o.ä. auftreten kann). Das Argument mit dem portablen Code lass ich auch nicht durchgehen da LL/SC gerade in der besseren RISC-Welt (Alpha / ARM / MIPS / PowerPC / SPARC / ...) recht verbreitet ist. Das ist so als würde ich aus Kompatibilität zur rollenden Fortbewegung das manuelle Fahrrad wählen und ignorieren das es motorisierte Autos gibt.

Zitat von: Svenska am 14. August 2011, 21:32

Ich habe das Gefühl, dass ihr hier Skalierbarkeit und Performance verwürfelt...

Sicherlich etwas, ja. Aber woher bekommt man da mal belastbare BenchMark-Ergebnisse?

Zitat von: Svenska am 14. August 2011, 21:32

Ich halte fein granulierte Locks für eine gute Möglichkeit, weil ich sie (im Gegensatz zu den anderen hier genannten Methoden) verstehe. ;-)

Da bist Du nicht der einzigste.
Gerade das ist auch ein sehr wichtiges Argument. Dinge die der Programmierer nicht so richtig verstanden hat sind eventueller etwas verbugter oder nur suboptimal umgesetzt.

Grüße
Erik

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 14. August 2011, 22:03

Zitat von: svenska

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. Allerdings sollten wir erstmal klären, was genau meinst du mit Giant Lock? Einen Lock der im Endeffekt den gesamten Kernel schützt?

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

Zitat von: erik

Das Argument mit dem portablen Code lass ich auch nicht durchgehen da LL/SC gerade in der besseren RISC-Welt (Alpha / ARM / MIPS / PowerPC / SPARC / ...) recht verbreitet ist. Das ist so als würde ich aus Kompatibilität zur rollenden Fortbewegung das manuelle Fahrrad wählen und ignorieren das es motorisierte Autos gibt.

Das war erstmal nur eine Vermutung meinerseits, aber gucke dir doch Android an, was man da zwecks Portabilität gemacht hat (ich sag nur VM).

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode 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.

Zitat

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 :mrgreen:

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 15. August 2011, 13:37

Ich sehe schon, das mit den Lock-Free Algos wird ne harte Nuss ;)

So mir ist jetzt aber noch ein Grund eingefallen warum sie besser (im Sinne von Schneller und Skalieren) sein könnten (ich hoffe es doch). Auch wenn das Thema hier Locking im Kernel ist, kann man im UserSpace nicht mal einfach die Ints ausmachen (womit dann Spinlocks sehr teuer werden können). Sprich man hat die Wahl ob man ne Spinlock nimmt, die kann aber unter Umständen die ganze Zeit des Threads durch sinnloses spinnen verschwenden (selbst wenn man nach einigem Warten abgibt oder gleich abgibt, kommt als Zeit, noch die Threadwechsel dazu), man kann auch nen Mutex nehmen, aber das erfordert wiederrum den Eintritt in den Kernel und wieder zwei Threadwechsel (einen zum Thread hin, der gerade die Mutex hat und einen wieder zurück zum Thread, der versucht hat die Mutex zu bekommen). Bei Lock-Free Algos kann aber jeder Thread fortschritte machen, egal ob gerade ein anderer Thread auch versucht etwas zu ändern. Sprich der worst-case, nämlich Thread A hat alles soweit das er die Datenstruktur ändern will und wird unterbrochen und Thread B kommt an die Reihe und will auch etwas ändern, bei einer Spinlock und der Mutex muss er warten bis Thread A fertig ist, aber bei einem Lock-Free Algo kann Thread B einfach ganz normal sein Ding durchziehen, ohne das er von Thread A behindert/ausgebremst wird. Spinning im UserSpace ist sogar richtig gefährlich, weil es ja sein kann das Thread A den Lock hat und Thread B eine viel höhere Priorität hat, damit wird Thread A unterbrochen und Thread B blockiert beim Spinnen die Freigabe des Locks.

@bluecode

Ich, und ich denke auch erik, bin sehr darin interessiert. Ich muss aber ehrlich zugeben, ich habe irgendwie nichts von dem was du geschrieben hast wirklich verstanden :(

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 15. August 2011, 14:01

Zitat von: FlashBurn am 15. August 2011, 13:37

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

Zitat

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

Auch nicht den letzten Beitrag von mir? :cry:

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 15. August 2011, 14:05

Zitat von: bluecode

Auch nicht den letzten Beitrag von mir?

Den meinte ich ja ;)

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode 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" :-D . Hast du irgendeine Ahnung wo du ausgestiegen bist? Oder hast du garnicht verstanden was ich versucht habe zu erklären?

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 15. August 2011, 15:21

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.

Zitat von: bluecode am 15. August 2011, 14:01

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.

Zitat von: FlashBurn am 15. August 2011, 13:37

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 15. August 2011, 15:28

Zitat von: bluecode

ironischerweise heißt die "Datenstrukturen"

Info-Student?

Zitat von: bluecode

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 15. August 2011, 16:39

Zitat von: erik.vikinger am 15. August 2011, 15:21

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. [...]
Zitat von: bluecode am 15. August 2011, 13:20
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).

Zitat

Zitat von: bluecode am 15. August 2011, 13:20
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).

Zitat

Zitat von: bluecode am 15. August 2011, 14:01
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.

Zitat

Info-Student?

Zitat

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 :wink: ), dass 2x das gleiche eingetragen wird.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 15. August 2011, 17:10

Zitat

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 15. August 2011, 22:18

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.

Zitat von: erik.vikinger am 15. August 2011, 15:21
Zitat von: bluecode am 15. August 2011, 13:20
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.

Zitat von: erik.vikinger am 15. August 2011, 15:21
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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode 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.

Zitat

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.

Zitat

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
}

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 08:50

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.

Zitat von: FlashBurn am 16. August 2011, 11:57

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 16. August 2011, 09:00

Zitat

Zitat von: bluecode am 16. August 2011, 07:57
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.

Zitat

Zitat von: bluecode am 16. August 2011, 07:57
.... 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. :-D

~~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 :-D

Zitat

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 16. August 2011, 10:53

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?

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode 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. :-D

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 16. August 2011, 11:57

Zitat von: 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).

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.

Zitat von: bluecode

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode 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. :-D

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 12:49

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

Zitat von: FlashBurn am 16. August 2011, 12:55

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 16. August 2011, 12:55

@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!

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 13:25

Hallo,

Mir ist das mit den Locks auch erstmal wichtiger!

Gut.

Zitat von: FlashBurn am 16. August 2011, 12:55

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 :

Zitat von: FlashBurn am 16. August 2011, 12:55

Zitat von: erik.vikinger am 15. August 2011, 15:21
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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: Svenska am 16. August 2011, 15:01

Hallo,

Zitat von: FlashBurn am 14. August 2011, 22:03

Zitat von: svenska
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. :-P

Zitat von: FlashBurn am 14. August 2011, 22:03

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.

Zitat von: FlashBurn am 14. August 2011, 22:03

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

Zitat von: FlashBurn am 16. August 2011, 10:53

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. :-P Aber ja, im Kernel kann man Locks benutzen - tun die meisten Betriebssysteme ja auch.

Zitat von: FlashBurn am 16. August 2011, 10:53

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.

Zitat von: FlashBurn am 16. August 2011, 10:53

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

Gruß,
Svenska

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 16. August 2011, 15:54

Zitat von: 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?

Zitat von: svenska

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.

Zitat von: svenska

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.

Zitat von: svenska

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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: Svenska am 16. August 2011, 17:05

Zitat von: 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.)

Zitat von: svenska
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.

Zitat von: svenska
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.

Zitat von: bluecode am 16. August 2011, 17:32

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 16. August 2011, 17:32

Zitat

Zitat von: bluecode am 16. August 2011, 09:00
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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: FlashBurn am 16. August 2011, 17:40

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

Zitat von: svenska

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

Zitat von: svenska

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

Sehr wahrscheinlich :D

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

Zitat von: svenska

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!

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 18:06

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

Zitat von: bluecode am 16. August 2011, 17:32

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.

Zitat von: Svenska am 16. August 2011, 15:01

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 16. August 2011, 18:09

Zitat von: erik.vikinger am 16. August 2011, 18:06

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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 18:24

Hallo,

Zitat von: bluecode am 16. August 2011, 18:09

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode 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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 19:07

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.

Zitat von: erik.vikinger am 16. August 2011, 19:07

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 16. August 2011, 19:27

Zitat

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.

Zitat von: bluecode am 16. August 2011, 18:30
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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 20:32

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.

Zitat von: erik.vikinger am 16. August 2011, 20:32

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 16. August 2011, 21:42

Zitat von: bluecode am 16. August 2011, 19:27
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 :wink:

Zitat

Zitat von: bluecode am 16. August 2011, 19:27
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.

Zitat

Zitat von: bluecode am 16. August 2011, 19:27
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...

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 16. August 2011, 23:57

Hallo,

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

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 17. August 2011, 10:07

Zitat

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

Jo, das war mir schon bewusst.

Zitat

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.

Zitat

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.

Zitat

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

Zitat

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.

Zitat

Zitat von: bluecode am 16. August 2011, 21:42
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).

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 17. August 2011, 12:49

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.

Zitat von: erik.vikinger am 17. August 2011, 12:49

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 17. August 2011, 13:08

Zitat von: bluecode am 17. August 2011, 10:07
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.

Zitat

Zitat von: bluecode am 17. August 2011, 10:07
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.

Zitat

Zitat von: bluecode am 17. August 2011, 10:07
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).

Zitat

Zitat von: bluecode am 17. August 2011, 10:07
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.

Zitat

Zitat von: bluecode am 17. August 2011, 10:07
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.

Zitat

Zitat von: bluecode am 17. August 2011, 10:07
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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 17. August 2011, 14:17

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 19. August 2011, 15:57

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

Zitat von: erik.vikinger am 19. August 2011, 15:57

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 19. August 2011, 19:00

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

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

Zitat

Zitat von: bluecode am 17. August 2011, 13:08
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. :wink: Und ich habe bereits in dem vorherigen Beitrag darauf verwiesen, dass die Autoren (des Hazard-Pointer Paper) da einiges dazu schreiben.

Zitat

Zitat von: bluecode am 17. August 2011, 13:08
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.

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 19. August 2011, 20:06

Hallo,

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

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

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 21. August 2011, 19:40

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: bluecode am 01. September 2011, 12:11

Transactional Memory (http://arstechnica.com/hardware/news/2011/08/ibms-new-transactional-memory-make-or-break-time-for-multithreaded-revolution.ars) 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).

Titel: Re:Locking innerhalb des Kernels
Beitrag von: Svenska am 01. September 2011, 17:55

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.

Zitat von: bluecode am 01. September 2011, 12:11

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

Titel: Re:Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 02. September 2011, 23:10

Hallo,

Transactional Memory könnte auch interessant sein ....

Oh ja, das hab ich mir auch schon öfters mal überlegt. Dabei gibt es aber einige Probleme bei der praktischen Umsetzung: man muss z.B. ganz klar die Limits definieren also wie viele Speicherstellen maximal an so einer Transaktion beteiligt sein dürfen. Aus meiner Sicht wäre z.B. das Einfügen/Löschen eines Elements in/aus einer doppelt verketteten Liste so eine Operation für die man 2 Speicherstellen einbeziehen müsste (den Next-Pointer beim vorderen Element und den Prev-Pointer beim nachfolgenden Element). In dem Artikel steht drin dass das dort im Cache gemacht wird, insbesondere das mit den Versionen für die Daten klingt interessant aber auch aufwendig. Zum einen wird durch die Versionierung die Indexierung des Cache komplexer (und zwar immer und nicht nur für atomare Transaktionen, da ja komplexere HW-Logik erforderlich ist) und die Commit-Operationen müssten den Cache serialisieren (während einer Commit-Operation darf gar keine andere Operation gerade in diesem Cache stattfinden bzw. es muss sichergestellt werden das diese anderen Operationen nicht mit dem Commit kollidieren) was auch mit einigem Schaltungsaufwand verbunden ist und für die anderen CPUs Wartezeiten erzeugt. Da ich ja vor habe meiner CPU die Möglichkeit zu geben User-Mode-Code für kurze Code-Abschnitte ununterbrechbar zu machen hatte ich mir überlegt für so ein LL/SC-Pärchen die betreffende Cache-Line einfach so lange nicht raus zu rücken wenn eine andere CPU danach fragt, das würde die ganze Verwaltung dieses HW-Locks deutlich vereinfachen und auch das TimeOut wäre automatisch mit eingebaut da diese Ununterbrechbarkeit ja von begrenzter Dauer ist. Wenn es nun noch möglich wäre 2 solcher LL/SC-Pärchen zu verschachteln und die beiden SC-Zugriffe zu kombinieren (so das entweder beide klappen oder keiner klappt) dann hätte man eine simple Form des Transactional Memory und könnte damit zumindest das Einfügen/Löschen eines Elements in/aus einer doppelt verketteten Liste lockfrei realisieren. Wenn man die Cache-Line während dessen tatsächlich nicht raus gibt ist das erfolgreiche Abschließen des Commits (also der 2 SC-Befehle) eigentlich fast garantiert (solange man auch erfolgreich durch die 2 LL-Befehle gekommen ist, gerade deswegen betrachte ich es auch als so wichtig das der LL-Befehl ebenfalls melden kann ob er erfolgreich war und weil man damit die Ressourcen-Schonung des Busy-Waitings mit der optimistischen Vorgehensweise der lockfrei-Algorithmen verbindet) und wenn während dessen eine andere CPU mit einem LL-Befehl kommt dann wartet diese einfach ein paar Takte länger bis sie die betreffende Cache-Line zur exklusiven Nutzung bekommt (die Wahrscheinlichkeit für einen fehlgeschlagenen LL-Befehl ist damit auch sehr gering und es geht alles mit maximaler Geschwindigkeit vorwärts da ja jede CPU genau so lange wartet bis sie dran ist).

Was der Artikel aber sehr treffend beschreibt sind die vielen Einschränkungen die die existierenden CPUs bei LL/SC machen, damit wird dieses eigentlich gute Konzept erheblich beschnitten. Vor allem die vielen Möglichkeiten für "False Negatives" sind mMn ein echtes (Performance-)Problem.

Die Frage die ich mir stelle ist: ist dieser Transactional Memory wirklich schneller als ein Lock?
Man spart sich zumindest die zusätzlichen Lock-Variablen (so wie auch beim LL/SC). Wenn das Lock selber nichts kostet dann wohl nicht, denn zwischen Busy-Waiting und vergeblichen Versuchen ist IMHO kaum ein Unterschied (von der allgemeinen System-Last und dem Energieverbrauch mal abgesehen). Der entscheidende Punkt ist ob man beim Locking sofort merkt ob man erfolgreich war und wie das mit den Nachteilen ist (ob z.B. während so eines Code-Abschnitts geschedult werden kann). Klassisches Locking hat einige Nachteile die vor allem dadurch entstehen das der Lock belegt bleibt auch wenn der Besitzer-Thread geschedult oder gar gekillt wird (bei letzterem hat man sogar ein ernstes Problem weil dann ja eventuell die geschützte Datenstruktur in einem inkonsistenten Zustand ist kann man das Lock ja nicht so einfach wieder freigeben). Das ist ja gerade der Vorteil der CAS-Operation das es dort gar nichts persistentes gibt, wogegen es beim LL/SC-Pärchen und auch beim Transactional Memory ja doch irgendwie eine gewisse Persistenz gibt. Auch beim Transactional Memory muss diese atomare Transaktion ja irgendwo verzeichnet sein und könnte bei schlechter HW-Implementierung eventuell länger als nötig bestehen bleiben und möglicherweise andere Operationen behindern, bei der Variante mit der Cache-Line-Versionierung trifft das aber nicht zu (auf Kosten sicher erheblichen zusätzlichen HW-Aufwands).

Grüße
Erik

Titel: Re: Locking innerhalb des Kernels
Beitrag von: FlashBurn am 28. September 2011, 10:36

Nachdem ich erst jetzt auf diese Art von spinlock aufmerksam geworden bin, vielleicht ist ja für den ein oder anderen ein ticket lock interssant, weil es nen fairer Lock ist.

Ich bin jetzt dann soweit meinen Kernel doch so zu gestalten das er nicht unterbrechbar ist, aber das ich trotzdem Kernel-Threads habe, welche ja unterbrechbar sein müssen. Dort müsste ich die Ints per Hand an und aus machen.
Das eignet sich natürlich nicht für nen Monolith, sondern nur für nen Mikrokernel, der halbwegs kurze Funktionen hat (Problem bei mir ist der VMM, der im worst-case schon mal ne Weile brauchen kann).

Titel: Re: Locking innerhalb des Kernels
Beitrag von: erik.vikinger am 28. September 2011, 19:23

Hallo,

Ich bin jetzt dann soweit meinen Kernel doch so zu gestalten das er nicht unterbrechbar ist

;) eine seeeehr gute Idee. SCNR

ich trotzdem Kernel-Threads habe, welche ja unterbrechbar sein müssen. Dort müsste ich die Ints per Hand an und aus machen.

Hm, das klingt umständlich, davon würde ich persönlich eher abraten.

Das eignet sich natürlich nicht für nen Monolith, sondern nur für nen Mikrokernel, der halbwegs kurze Funktionen hat

Richtig.