Thema: Locking innerhalb des Kernels

[erik.vikinger]

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

[FlashBurn]

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

[erik.vikinger]

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.

(Problem bei mir ist der VMM, der im worst-case schon mal ne Weile brauchen kann).

Es wird auch in einem Micro-Kernel einige Dinge geben die potentiell ziemlich lange brauchen. Neben dem VMM fällt mir da auch das Erstellen neuer (oder das Killen alter) Prozesse ein. Solange der Zeitbedarf der Aktion für den auslösendem Prozess akzeptabel ist (dem Programmierer ist schließlich klar das solche Aktionen potentiell sehr lange dauern können und darf sowas eben nicht machen wenn er einen deterministischen Programmablauf haben will, es muss nur sauber dokumentiert werden welche Syscalls wie lange dauern können, in allen Best/Average/Worst-Cases mit anständiger und nachvollziehbarer Begründung) ist das auch alles okay. Ein Problem wird das erst wenn dadurch auch andere Prozesse blockiert werden. Wenn also ein Prozess oder auch ein IRQ-Handler dadurch verzögert wird weil irgendein anderer Prozess ein vmalloc() oder CreateProcess() durchführt wird es kritisch. Auf einem Single-Core-System ist das quasi immer gegeben aber auf einem Multi-Core-System besteht bei guter Plattform-Architektur durchaus die Möglichkeit das die übrigen Prozesse und auch die IRQ-Handler nicht darunter leiden müssen nur weil mal einer ein CreateProcess() macht. Ich glaube man kann auch bei x86 das IRQ-Routing etwas flexibler konfigurieren so das nicht immer eine bestimmte CPU sondern eine beliebige CPU (eventuell nur aus einer eng begrenzen Gruppe, z.B. innerhalb eines Dies) die IRQs behandeln kann. Solange man genügend verfügbare CPU-Cores hat und solche langen Aktionen verhältnismäßig selten sind stellt das meiner persönlichen Meinung nach kein ernstes Problem dar. Sowas wie die Speicherverwaltung kann man mit CPU-lokalen Caches ja zumindest ein wenig entschärfen.


Grüße
Erik

[FlashBurn]

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

Naja, Problem ist halt, es geht nicht ohne

Ich brauche die für die Idle-Threads, für das Killen von Threads/Tasks und für das Erstellen von Tasks.

Naja, was heißt umständlich. Ich stelle mir das dann so vor, dass ich alle Infos in Variablen sammle. Dann die Ints ausmache, den Speicher freigebe und was sonst noch gemacht werden muss.

Neben dem VMM fällt mir da auch das Erstellen neuer (oder das Killen alter) Prozesse ein.

Interessant, dass immer diese beiden (erstellen und killen) Sachen genannt werden. Dabei bin ich mir sicher, dass das bei mir schneller ist als viele VMM aufrufe (wenn man nur eine Page mappen will, geht das klar schneller).
Ich habe das Erstellen und Killen halt in Threads ausgelagert (Kernelthreads) und weil die unterbrechbar sind (bzw. sein müssen) ist die Länge erstmal kein Problem, nur halt die Zugriffe auf den VMM und das ganz kurze Eintragen in Datenstrukturen.

Was ich vllt noch hätte zu den ticket locks schreiben sollen, sie schonen den Speicherbus (im Vergleich zur klassischen Spinlock). Aber auch sie sind nicht frei von Nachteilen und hier ist es das Cachesystem.
Der Vorteil ist ja, das pro Zugriff (also Lock bekommen und wieder freigeben), nur ein einziger lock Befehl ausgeführt werden muss. Das Spinnen findet dann im Cache statt.
Das ganze kann man auch noch entschärfen, aber mit mMn viel zu viel Speicheraufwand (Array von ticket locks und ein Element ist immer so groß wie eine Cacheline).

Ich habe heute auch alle meine Spinlocks durch diese ticket locks ersetzt und dadurch das ich mich auch nicht mehr um die Ints kümmern muss, ist der Code deutlich geschrumpft.

Ein Problem bleibt, aber trotzdem noch mit einem nicht unterbrechbaren Kernel. Die Locks werden dort nämlich noch teurer als bei einem Unterbrechbaren Kernel. Denn es kann passieren das alle CPUs gleichzeitig auf einen Lock zugreifen wollen und die letzte CPU muss dann sehr lange warten (abhängig von der Anzahl der CPUs und der Länge des kritischen Bereichs).
Entschärft wird das dadurch, dass die ersten CPUs ja theoretisch genügend Zeit haben einen IRQ entgegen zu nehmen, aber da kommt dann auch schon wieder ein anderes Problem. Soweit mir bekannt, kann man den IO-APIC ja so programmieren, dass immer die CPU den IRQ bekommt, die die niedrigste Priorität hat, aber wenn diese gerade die Ints aus hat, wird der IRQ auch nicht an eine andere CPU weitergegeben. Sprich wenn nun dummerweise die letzte CPU (aus obigem Beispiel) den IRQ bekommt, kann es auf Systemen mit vielen Cores doch wieder zu unschönen Latenzen kommen (von SingelCore gar nicht zu sprechen).