Thema: spinlocks

[erik.vikinger]

Hallo,

Mit solchen Infos ist Intel immer sehr zurückhaltend

Sag ich doch, ein fürchterlicher Geheimniskrämer der damit eigentlich nur seine zahlenden Kunden verärgert.

Wie das dann mit dem Cachekohärenzprotokolloverhead ist weiß ich nicht.

Aber genau darum geht es doch. Wenn eine bestimmte CPU eine bestimmte Cache-Line zur exklusiven Verwendung haben will dann muss diese CPU sicherstellen das diese Cache-Line in keiner anderen CPU vorhanden ist. Das geht nur über Broadcast oder über ein vollständiges Verzeichnis, da letzteres zu viel Speicher erfordert bleibt eben nur Broadcast übrig und das wird gerade bei vielen CPUs einiges an Last darstellen und reichlich Zeit benötigen.

Genauso haben alle anderen Threads mehr Bandbreite wenn du mit deinem Lock den Memorybus nicht zusätzlich belastest.

Es gibt keinen BUS mehr in einem modernen Multi-CPU-System! Oder meinst Du die Verbindung zwischen der CPU und den (eventuell mehreren) lokalen Speichermodulen? Das ist das einzigste was man noch als BUS bezeichnen könnte.

Außerdem gehe ich mal davon aus, das Intel dieses Vefahren nicht im Optimierungsguide angeben würde, wenn es effektiv nichts bringt.

Der Optimirungsguide ist sicher über mehrere CPU-Generationen gewachsen, ich glaube nicht das dort noch alles Up-To-Date ist.

Ich wäre ja an einer Variante wie man eine Queue implementiert mit Hilfe des cmpxchg Befehls! Dann könnte ich vielleicht die Locks für meine Messagequeue entschärfen.

Wenn Deine Queue eine einfach verkettete Liste ist in der es in jedem Element einen "Next"-Pointer gibt dann kannst Du ein neues Element bauen (dort ist der Next-Pointer noch NULL) und dieses mit einem cmpxchg auf den Next-Pointer des letzten Listenelement anhängen (dort ist der Next-Pointer auch noch NULL). Das heißt der cmpxchg prüft ob der Next-Pointer im letzten Element noch NULL war und schreibt dann den Pointer für Dein neues Element an diese Stelle und wenn das fehlschlägt (weil jemand anderes schneller war) dann probierst Du das bei dem neuen letzten Element eben erneut. Du versucht also nicht ständig den selben Next-Pointer zu bearbeiten sondern gehst nach jedem Fehlschlag weiter. Doof wäre nur wenn Deine Message-Queue in dieser Zeit leer werden sollte.


Grüße
Erik

[FlashBurn]

Es gibt keinen BUS mehr in einem modernen Multi-CPU-System! Oder meinst Du die Verbindung zwischen der CPU und den (eventuell mehreren) lokalen Speichermodulen? Das ist das einzigste was man noch als BUS bezeichnen könnte.

Ja, daran dachte ich. Das Problem mit dem Cachekohärenzprotokoll tritt ja "nur" auf, wenn der Lock freigegeben wurde ("nur" deshalb, weil dann ja die Cacheline mehrmals ungültig gemacht wird). Es kommt halt drauf an, wie lange man den Lock hat, bei 3-10 Assemblerinstruktionen kann es dann schon sein, das deine Variante vielleicht schneller ist, aber ich würde zumindest ne "pause" mit einsetzen. Denn gerade die neuen Core i-sowieso CPUs sollten wieder davon profitieren!

Der Optimirungsguide ist sicher über mehrere CPU-Generationen gewachsen, ich glaube nicht das dort noch alles Up-To-Date ist.

Ach der wird eigentlich laufend aktualisiert und genau da ist ja das Problem. Am Anfang schreiben sie, du sollst deine Loops so weit es geht unrollen und später schreiben sie, dass auf der Core Architektur das Loop unrolling nicht übertrieben werden sollte, weil die CPUs damit nicht mehr zurecht kommen Aber zum Thema Spinlocks sagen sie auch, das es im Cache liegen soll, aber eine Lock alleine in einer Cacheline! Naja ich denke wir einigen uns darauf, das jeder das nimmt was er für besser hält

Wenn Deine Queue eine einfach verkettete Liste ist in der es in jedem Element einen "Next"-Pointer gibt dann kannst Du ein neues Element bauen (dort ist der Next-Pointer noch NULL) und dieses mit einem cmpxchg auf den Next-Pointer des letzten Listenelement anhängen (dort ist der Next-Pointer auch noch NULL). Das heißt der cmpxchg prüft ob der Next-Pointer im letzten Element noch NULL war und schreibt dann den Pointer für Dein neues Element an diese Stelle und wenn das fehlschlägt (weil jemand anderes schneller war) dann probierst Du das bei dem neuen letzten Element eben erneut. Du versucht also nicht ständig den selben Next-Pointer zu bearbeiten sondern gehst nach jedem Fehlschlag weiter. Doof wäre nur wenn Deine Message-Queue in dieser Zeit leer werden sollte.

Genauso sieht meine Liste aus, aber wie ich es mir dachte, wird es wohl Probleme beim Löschen geben.
Ich habe ne doppelt verkettete Liste und speichere nur den Head ab. Der Pointer auf das letzte Element ist dann der Vorgänger vom Head, d.h. beim Löschen müsste ich 2 Pointer ändern und beim Einfügen müsste ich auch immer gucken ob der Head noch da ist. Also bleibe ich lieber bei ner Spinlock (ist ja auch nicht wirklich viel was hier passiert).

Ich bin mir nicht sicher ob es hierher passt, aber egal.
Was hälst du denn von Read-Write-Locks? Ich muss heute direkt mal nachgucken, ob es sowas auch als Semaphore gibt, habe ich nämlich noch nichts von gehört.

[erik.vikinger]

Hallo,

Das Problem mit dem Cachekohärenzprotokoll tritt ja "nur" auf, wenn der Lock freigegeben wurde ("nur" deshalb, weil dann ja die Cacheline mehrmals ungültig gemacht wird).

Anderes Szenario: 5 CPUs (von einigen mehr) wollen gleichzeitig einen Lock haben der momentan frei ist (was auch ein vorangegangener nicht-gelockter Lesebefehl bestätigt) und jede hat die betreffende Cache-Line im Zustand "Shared" im lokalen Cache. Um auf der Lock-Variable nun den gelockten cmpxchg (oder auch was anderes atomisches) auszuführen muss jede der CPUs die betreffende Cache-Line für sich exklusiv reservieren also wird ein "Read-For-Exclusive"-Broadcast an alle CPUs geschickt und auf alle Antworten gewartet. Jede der 5 CPUs erhält während sie auf Antworten wartet die Anfragen der jeweils 4 anderen CPUs. Nun muss nach irgendeinem Prioritätsschema ermittelt werden welche der 5 CPUs die Cache-Line für sich beanspruchen darf um sie in den Zustand "Exclusive" zu überführen, die anderen 4 CPUs müssen die Cache-Line invalidieren. Nachdem die erste CPU gewonnen hat und ihren gelockten Befehl ausführen konnte (die kümmert sich dann erst mal nicht weiter um die Cache-Line die dann "Modified" ist) geht das Spiel mit den restlichen 4 CPUs von vorne los, die wollen immer noch den einen gelockten Befehl ausführen. Das geht so lange bis auch die letzte der 5 CPUs ihren einen gelockten Befehl endlich ausführen konnte. Kannst Du Dir den Traffic auf dem CPU-Netzwerk annähernd ausmalen?
Dagegen sind 5 Anfragen die nur direkt an den betreffenden Heimat-Speicher-Controller geschickt werden, 5 Jobs im RAM-Controller (nur der erste Job muss die langen DRAM-Latenzen mitmachen, für die 4 folgenden Jobs ist die betreffende DRAM-Zeile noch aktiv) und 5 Antworten (nur die erste signalisiert "Lock erfolgreich bekommen") die wieder nur direkt zu den richtigen CPUs geschickt werden eine Kleinigkeit. Und deutlich schneller dürfte die Non-Cachable-Variante in diesem Szenario auch sein.

Es kommt halt drauf an, wie lange man den Lock hat

Ganz genau.

bei 3-10 Assemblerinstruktionen kann es dann schon sein, das deine Variante vielleicht schneller ist, aber ich würde zumindest ne "pause" mit einsetzen.

Meiner Meinung nach gibt es 4 Varianten:

• kleine Schleife ohne irgendwas zur Unterbrechung (also z.B. der Code den ich ganz am Anfang vom Thread gepostet hatte): das lohnt sich IMHO bis etwa 5 Speicherzugriffe (von den eigentlichen Rechenbefehlen erwarte ich bei heutigen CPU-Leistungen keine nennenswerte extra Zeit)
• kleine Schleife mit einem pause-Befehl: das sollte sich für etwas längere Locks lohnen, wenn der zusätzliche pause-Befehl etwa doppelt so lange dauert wie der gelockte Befehl dann darf auch der Lock-Besitz etwa 3 mal so lange dauern als bei ohne pause-Befehl
• kleine Schleife mit Freigabe der Zeitscheibe, also anstelle des pause-Befehls ein sleep(0) oder ein anderer spezieller SYSCALL damit der aktuelle Thread geschedullt wird: das sollte sich für einen gelockten Vorgang lohnen der maximal etwa 5 bis 20 Zeitscheiben dauert
• Benutzung einer speziellen OS-Kernel-Funktion welche den wartenden Thread suspendiert und in eine Queue packt: damit gibt es dann keine Grenze mehr nach oben, die SYSCALLs sind zwar recht teuer aber dafür kostet das Warten gar nichts

Die nummerischen Werte entstammen meinem persönlichen Bauchgefühl und können in der Realität sicher je nach Plattform und Ausstattung etwas variieren.
Die ersten beiden Varianten sind auf einem Single-CPU-System eher nicht geeignet.
Man muss also immer das richtige Werkzeug wählen.

Der Optimirungsguide ist sicher über mehrere CPU-Generationen gewachsen, ich glaube nicht das dort noch alles Up-To-Date ist.

Ach der wird eigentlich laufend aktualisiert und genau da ist ja das Problem.

Eben, der sollte für jede CPU-Generation komplett neu geschrieben werden. Sicher kann man da viel 1:1 kopieren aber jedes kopierte Wort sollte von mehreren ausreichend qualifizierten Leuten geprüft werden damit sich nicht Schnee von Gestern durch mogelt.

Am Anfang schreiben sie, du sollst deine Loops so weit es geht unrollen und später schreiben sie, dass auf der Core Architektur das Loop unrolling nicht übertrieben werden sollte, weil die CPUs damit nicht mehr zurecht kommen

Ich persönlich würde Loop-Unrolling sowieso nicht übertreiben weil das ne Menge Platz im Code-Cache kostet. Ich weiß aber auch das die Intel-Compiler diese Neigung teilweise sehr exzessiv ausleben und damit auch oft sehr gute Performance erreichen.

Aber zum Thema Spinlocks sagen sie auch, das es im Cache liegen soll, aber eine Lock alleine in einer Cacheline!

Was dann wieder pure Speicherverschwendung ist, außerdem weißt Du doch nicht zur Link-Zeit die Cache-Line-Größe des Zielrechners.

Naja ich denke wir einigen uns darauf, das jeder das nimmt was er für besser hält

Full ACK!

Genauso sieht meine Liste aus, aber wie ich es mir dachte, wird es wohl Probleme beim Löschen geben.

Wenn Du Probleme beim leeren bekommst dann lass doch immer mindestens ein oder zwei Elemente drin und markiere sie nur als leer. Oder der Queue-Konsument hat einen eigenen Pointer in die Liste.

Ich habe ne doppelt verkettete Liste ...

Doppelt verkettete Liste geht IMHO nicht atomar.

Was hälst du denn von Read-Write-Locks? Ich muss heute direkt mal nachgucken, ob es sowas auch als Semaphore gibt, habe ich nämlich noch nichts von gehört.

Ich hab das mal auf Basis eines einfachen Locks (der die internen Verwaltungsstrukturen geschützt hat) implementiert. Es durften immer beliebig viele Leser gleichzeitig rein aber nur ein Schreiber und immer nur eine Sorte gleichzeitig. Die Schreiber hatten eine höhere Priorität. Das war wimre nicht sonderlich kompliziert.
Ich weiß gar nicht mehr wofür das damals benötigt wurde aber meine Kollegen haben sich nie beschwert, muss wohl ausreichend funktioniert haben.


Grüße
Erik

[FlashBurn]

Die ersten beiden Varianten sind auf einem Single-CPU-System eher nicht geeignet.

Warum? Auf nem Single-CPU-System bekommst du ne Spinlock immer (ich gehe jetzt mal frech vom Kernel aus)! Denn wenn du schon ne Spinlock nutzt dann bitte auch die IRQs ausmachen. Wenn du das ganze für den Userspace betrachtest, dann würde ich es so lösen, das du ne bestimmte Anzahl an Versuchen unternimmst und dann an den Scheduler abgibts und beim nächsten Mal geht es wieder von vorne los.

Was dann wieder pure Speicherverschwendung ist, außerdem weißt Du doch nicht zur Link-Zeit die Cache-Line-Größe des Zielrechners.

Also was ich so an Code vom Intel-Compiler gesehen haben, macht der sich um Speicherverschwendung nicht wirklich ne Rübe
Intel scheint in seinem Optimierungsguide sowieso davon auszugehen, das du alles immer nur auf einer bestimmten CPU laufen lässt und andere sind egal. (gut für Compilerprogrammierer sind die Infos schon wertvoll)

Du hattest mal was davon geschrieben, das AMD bei ihren aktuellen CPUs einen Teil des Level3 Caches dafür benutzt um die ganze Cachekohärenzprotokollsache zu minimieren. Dann frage ich mich schon was Intel mit ihren neuen Server-CPUs und bis zu 24MB Level3 Cache wollen, weil da müsste ja dann die Hölle los sein Zumal diese CPUs gerade für viele Sockel-Mainboard ausgelegt sind.

[erik.vikinger]

Hallo,

Die ersten beiden Varianten sind auf einem Single-CPU-System eher nicht geeignet.

Warum? Auf nem Single-CPU-System bekommst du ne Spinlock immer (ich gehe jetzt mal frech vom Kernel aus)!

Sorry, ich bin vom User-Mode ausgegangen. Auf nem Single-CPU-System braucht man im Kernel keine Locks da reicht IRQs ausschalten auch. Im User-Mode ist es auf einem Single-CPU-System IMHO Zeitverschwendung mehrmals hintereinander zu versuchen einen Lock zu bekommen, ein Versuch pro Zeitscheibe sollte reichen.
Meine 4 Lock-Varianten sind aber offensichtlich noch nicht der Weisheit letzter Schluss, da bleibt noch Verbesserdungspotential.

Du hattest mal was davon geschrieben, das AMD bei ihren aktuellen CPUs einen Teil des Level3 Caches dafür benutzt um die ganze Cachekohärenzprotokollsache zu minimieren.

Ich galube aber nicht das sie damit das Problem komplett los sind, schon weil keine CPU den gesamten Traffic sieht. Es wird wohl nur etwas reduziert werden.

Dann frage ich mich schon was Intel mit ihren neuen Server-CPUs und bis zu 24MB Level3 Cache wollen, weil da müsste ja dann die Hölle los sein Zumal diese CPUs gerade für viele Sockel-Mainboard ausgelegt sind.

Die Frage ist eher was "viele" Sockel sind. Ich persönlich habe den Eindruck das AMD da in etwas größerem Maßstäben denkt. Sieh Dir mal http://www.intel.com/technology/quickpath/demo/demo.htm an. Intel lebt IMHO davon das QPI nominal etwas schneller ist und damit etwas mehr Broadcast vertragen kann, außerdem machen größere Caches das Anfordern von externen Daten seltener. Ich denke bei Intel wird ein etwas höherer Anteil an Broadcast-Traffic unterwegs sein und dafür aber seltener echte Daten transferiert werden.
An der Stelle versucht AMD wohl anzusetzen, durch die lokalen Infos über fremde Cache-Lines muss eine simple Anfrage oft nicht an alle anderen CPUs gesendet werden sondern nur an die interessanten Kandidaten. Dadurch wird der Vorgang zwar nicht unbedingt beschleunigt erzeugt aber weniger Traffic so das anderes parallel schneller wird.

Verstehst Du denn jetzt warum ich bei vielen Sockeln eher zur Non-Cachable-Variante tendiere?


Grüße
Erik

[FlashBurn]

Im User-Mode ist es auf einem Single-CPU-System IMHO Zeitverschwendung mehrmals hintereinander zu versuchen einen Lock zu bekommen, ein Versuch pro Zeitscheibe sollte reichen.

Du solltest vielleicht mal definieren was du unter einer Zeitscheibe verstehst. Also ich denke mal du meinst die Zeit die ein Thread vom Scheduler bekommt. So wie du es schilderst verstehe ich darunter das du nur einmal versuchen willst den Lock zu bekommen und dann abgibts, aber dann nimm bitte eine Semaphore! Denn wenn du beim nächsten mal wieder versuchst den Lock zu bekommen und ihn wieder nicht bekommst, kostet das nur unnötig Performance (TLB und so´n Zeug).

Ich kann so langsam nachvollziehen wieso du uncacheable besser findest. Ich habe gerade ne News auf Golem gelesen und fand die Idee ganz gut (ein oder mehrere Kerne nur für die Speicherverwaltung). Wenn man die Idee jetzt mal weiter denkt, dann macht es sich ganz gut, immer einen Kern für eine bestimme Aufgabe zu nehmen (nur was das OS so zur Verfügung stellt) und alle anderen Kerne können von den Programmen genutzt werden. Das sollte das Cacheproblem doch wesentlich verringern.

edit::

Auf nem Single-CPU-System braucht man im Kernel keine Locks da reicht IRQs ausschalten auch. Im User-Mode ist es auf einem Single-CPU-System IMHO Zeitverschwendung mehrmals hintereinander zu versuchen einen Lock zu bekommen, ...

Mein Kernel läuft dummerweise auf Single und Multi-CPU Systemen. Auch kannst du als Programmierer ja nicht wissen ob dein Spinlockcode jetzt auf nem Single-CPU System läuft oder nicht.

[Svenska]

Als Programmierer nicht, aber wenn du das Locking zweimal implementierst, einmal als simples CLI/STI für Uniprozessor und einmal komplizierter für SMP, kannst du dynamisch umschalten. Ist halt nur noch ein Abstraktionsgrad mehr, ob sich das lohnt, kann ich nicht einschätzen.

Wenn der Kernel läuft, sollte er wissen, auf wievielen CPUs er läuft.

[FlashBurn]

Als Programmierer nicht, aber wenn du das Locking zweimal implementierst, einmal als simples CLI/STI für Uniprozessor und einmal komplizierter für SMP, kannst du dynamisch umschalten. Ist halt nur noch ein Abstraktionsgrad mehr, ob sich das lohnt, kann ich nicht einschätzen.

Das könnte ich machen, wenn ich den Code nicht inlinen würde

Ich habe es auch mal gebenchmarkt (auf nem K5-100) und was ich durch nur die Ints ausmachen sparen würde, würde durch den Funktionsaufruf wieder drauf gehen (Prob ist nur der K5 hat natürlich ne verdammt gute Integerleistung).

Wenn der Kernel läuft, sollte er wissen, auf wievielen CPUs er läuft.

Weiß meiner auch

[erik.vikinger]

Hallo,

Du solltest vielleicht mal definieren was du unter einer Zeitscheibe verstehst. Also ich denke mal du meinst die Zeit die ein Thread vom Scheduler bekommt.

Ja.

So wie du es schilderst verstehe ich darunter das du nur einmal versuchen willst den Lock zu bekommen und dann abgibts, aber dann nimm bitte eine Semaphore!

Genau, auf einem Single-CPU-System wird sich der Status des Lock/Semaphore/sonstwas nicht ändern wenn der wartende Thread die eine CPU nicht wieder abgibt, das mehrfache probieren kostet nur Zeit und Energie (in Zeiten von Green-IT sollte man auch daran denken ). Was hat das nun wieder mit Semaphore zu tun?

Denn wenn du beim nächsten mal wieder versuchst den Lock zu bekommen und ihn wieder nicht bekommst, kostet das nur unnötig Performance (TLB und so´n Zeug).

Wenn der momentane Lock-Besitzer diesen nur kurz benötigt aber dummerweise gerade in diesem kurzen Code-Abschnitt vom Scheduller unterbrochen wurde dann ist das eben blöd und kostet etwas Performance. Aber deswegen noch mehr Performance für nen aufwändigen OS-Kernel-Service zu beanspruchen (der meist gar nicht nötig wäre) ist IMHO auch nicht zielführend. Einen passenden Service vom OS-Kernel zu nutzen lohnt IMHO erst wenn der Lock/Semaphore/sonstwas für längere Zeit beansprucht wird, ein wartender Thread also einige male vom Scheduller aufgerufen würde.

Ich kann so langsam nachvollziehen wieso du uncacheable besser findest. Ich habe gerade ne News auf Golem gelesen und fand die Idee ganz gut (ein oder mehrere Kerne nur für die Speicherverwaltung). Wenn man die Idee jetzt mal weiter denkt, dann macht es sich ganz gut, immer einen Kern für eine bestimme Aufgabe zu nehmen (nur was das OS so zur Verfügung stellt) und alle anderen Kerne können von den Programmen genutzt werden. Das sollte das Cacheproblem doch wesentlich verringern.

Diese Idee ist nicht neue, in dem von Dir verlinkten Dokument kann man von den 20 386ern auch nur maximal 18 nutzen, mindestens 2 behält das System für andere Dinge für sich. Prinzipiell ist das eine interessante Idee aber wenn das OS gerade nichts zu tun hat aber ein rechenintensives möglich viel CPU-Leistung will dann sollte es auch alle CPUs bekommen.

Mein Kernel läuft dummerweise auf Single und Multi-CPU Systemen. Auch kannst du als Programmierer ja nicht wissen ob dein Spinlockcode jetzt auf nem Single-CPU System läuft oder nicht.

Dann kompiliere den Kernel 2 mal (einmal für Single-CPU und ein mal für SMP) und lass den Boot-Loader den passenden nehmen. Die älteren NT-basierenden Windowsen haben das so gemacht (wie das in aktuellen Windowsen aussieht weiß ich nicht).

Als Programmierer nicht, aber wenn du das Locking zweimal implementierst, einmal als simples CLI/STI für Uniprozessor und einmal komplizierter für SMP, kannst du dynamisch umschalten.

2 mal implementieren ist gut aber ich würde das zur Compilezeit entscheiden lassen und eben 2 mal compilieren, das kosten zur Laufzeit wenigstens keine Performance. Alternativ könnte man auch sagen "Single-CPU stirbt eh aus, meinen Kernel gibt es nur als SMP-Version", dafür verzichtet man auf Single-CPU-System auf ein klein wenig Performance.

Wenn der Kernel läuft, sollte er wissen, auf wievielen CPUs er läuft.

Das Install-Programm sollte das auch wissen und den passenden Kernel beim Boot-Loader eintragen.

Ich habe es auch mal gebenchmarkt (auf nem K5-100) und was ich durch nur die Ints ausmachen sparen würde, würde durch den Funktionsaufruf wieder drauf gehen (Prob ist nur der K5 hat natürlich ne verdammt gute Integerleistung).

Echt, kann der K5 nicht so schnell Funktionen aufrufen? Gerade Code der von vielen Stellen benötigt wird profitiert oft nicht vom inlinen sondern davon nur ein mal da zu sein und auch nur ein mal im Cache zu liegen, es sei den der zu inlinende Code ist kleiner als der Funktionsaufruf selber (also bei x86 kleiner als 5 Byte). Was hat damit eigentlich die Integerleistung zu tun?


Grüße
Erik

[FlashBurn]

Dann kompiliere den Kernel 2 mal (einmal für Single-CPU und ein mal für SMP) und lass den Boot-Loader den passenden nehmen. Die älteren NT-basierenden Windowsen haben das so gemacht (wie das in aktuellen Windowsen aussieht weiß ich nicht).

Ist nicht wirklich ne Option für mich (ist halt Einstellungssache ). Problem ist speziell bei meinem Kernel, das er erst zur Laufzeit gelinkt wird und das würde heißen das ich nicht nur meinen Kernel 2mal bräcuhte sondern auch die "Module" die mindestens für den Kernel nötig sind (bei mir z.b. CPU, FPU, IRQ, PMM, Scheduler, Syscall und Timer) Das wird dann schon ein wenig umständlich.

Echt, kann der K5 nicht so schnell Funktionen aufrufen?

Wenn sie erstmal im Cache liegen dann bestimmt, aber ich kann nicht immer davon ausgehen, das alles im Cache liegt.

Gerade Code der von vielen Stellen benötigt wird profitiert oft nicht vom inlinen sondern davon nur ein mal da zu sein und auch nur ein mal im Cache zu liegen, es sei den der zu inlinende Code ist kleiner als der Funktionsaufruf selber (also bei x86 kleiner als 5 Byte).

Rein von der Anzahl an Instruktionen ist der Code Single-CPU Code mit Funktionsaufruf und SMP-Code ohne, aber mit best Case (was auf Single-CPU Systemem ja immer zutrifft) gleich "lang". Was du sparst (was aber auf älteren System nicht wirklich schlimm zu sein scheint) ist der gelockte Speicherzugriff. Am teuersten ist das CLI auf den älteren CPUs. Ich habe meinen Code auch mal auf meinem Q9550 gebencht und der ist selbst auf Taktebene wesentlich schneller als der K5 (was ich vorallem auf das CLI zurückführe).

Was hat damit eigentlich die Integerleistung zu tun?

Naja, alles was nicht FPU ist, ist halt Integerleistung. Ich hätte vielleicht sagen sollen das er ein verdammt gutes Verhältnis von Instruktionen pro Takt hat. Taktbereinigt zieht er halt auch viele spätere Generationen ab (bei der Integerleistung, nicht bei der FPU).

Wenn der momentane Lock-Besitzer diesen nur kurz benötigt aber dummerweise gerade in diesem kurzen Code-Abschnitt vom Scheduller unterbrochen wurde dann ist das eben blöd und kostet etwas Performance. Aber deswegen noch mehr Performance für nen aufwändigen OS-Kernel-Service zu beanspruchen (der meist gar nicht nötig wäre) ist IMHO auch nicht zielführend. Einen passenden Service vom OS-Kernel zu nutzen lohnt IMHO erst wenn der Lock/Semaphore/sonstwas für längere Zeit beansprucht wird, ein wartender Thread also einige male vom Scheduller aufgerufen würde.

Das kommt auf die Schedulingstrategie an und was bei Sleep(0) wirklich passiert. Bei meinem OS würde das mit dem Abgeben (ich habe da nen extra Syscall für, nutze also kein Sleep(0)) funktionieren, zumindestens noch. Wenn ich meinen Scheduler mal ändern sollte (was sehr wahrscheinlich ist), dann sieht es schon wieder ganz anders aus.

[erik.vikinger]

Hallo,

Ist nicht wirklich ne Option für mich

War ja nur ein Vorschlag. Ich denke das man heutzutage nicht allzu viel verkehrt macht wenn man "nur" einen SMP fähigen Kernel hat.

Naja, alles was nicht FPU ist, ist halt Integerleistung.

Das ist aber schon eine recht merkwürdige Herangehensweise.
Es gibt viele Befehle die nichts mit Rechnen oder Integern zu tun haben, z.B. die vielen MOV-Varianten inklusive der Speicherzugriffe.
Das auf älteren CPUs die Befehle cli/sti so langsam sind liegt IMHO da dran das damit die Flags als ganzes bearbeitet werden und die CPU dabei immer höllisch aufpassen muss das der Code nichts tut was er nicht tun darf. Aus diesem Grund ist (war) z.B. auch der Befehl popf ziemlich langsam. In der Zwischenzeit haben sich AMD und Intel sehr bemüht diese Engstelle deutlich zu beschleunigen, da x86 nur ein zentrales Flag-Set hat, und dort dummerweise auch noch die System-Flags mit drin sind, ist das von hoher Wichtigkeit.

Das kommt auf die Schedulingstrategie an und was bei Sleep(0) wirklich passiert.

Also bei sleep(0) solte das selbe passieren wie wenn der Timer-IRQ kommt, bei einem x86-SMP eben der IRQ vom Local-APIC-Timer.
In meiner Plattform soll auch jede CPU einen eigenen kleinen Timer haben der eine extra Kontext-Switch-Exception auslößt ohne dafür den IRQ-Controller o.ä. zu bemühen und weil das so direkt mit dem CPU-Kern verkoppelt ist gibt es zusätzlich einen extra Befehl der das selbe macht auch wenn der Timer noch nicht abgelaufen ist.

Bei meinem OS würde das mit dem Abgeben (ich habe da nen extra Syscall für, nutze also kein Sleep(0)) funktionieren, zumindestens noch. Wenn ich meinen Scheduler mal ändern sollte (was sehr wahrscheinlich ist), dann sieht es schon wieder ganz anders aus.

Der Scheduller in einem OS-Kernel sollte immer vernünftig mit Threads umgehen können die ihre restliche Zeitscheibe nicht komplett verbrauchen wollen, dafür gibt es sicher viele verschiedene sinnvolle Anwendungsszenarien.


Grüße
Erik

[FlashBurn]

Es gibt viele Befehle die nichts mit Rechnen oder Integern zu tun haben, z.B. die vielen MOV-Varianten inklusive der Speicherzugriffe.

Da kannst du aber davon ausgehen, das wenn du ne CPU von einem anderem Hersteller auf das selbe Board packst der Speicherzugriff (so fern er nicht vom Cache abgefangen wird) gleich lang dauern.
Zumal was macht man denn im Endeffekt, was wirklich Leistung kostet? Es läuft immer auf das Rechnen (ein Vergleich ist nichts anderes) mit Zahlen zurück. Du holst ne Zahl, bearbeitest (rechnest damit) sie und schreibst sie wieder irgendwo hin und diese Zahlen sind halt Integerzahlen (auch fixed Point Zahlen sind im Endeffekt Integerzahlen).

War ja nur ein Vorschlag. Ich denke das man heutzutage nicht allzu viel verkehrt macht wenn man "nur" einen SMP fähigen Kernel hat.

Naja, mein Kernel soll ab Pentium aufwärts laufen und zu sagen ich hätte nur nen SMP Kernel ist nicht ganz zutreffend. Denn viele Sachen werden anders gemacht oder findest du erst gar nicht im Kernel, wenn er auf nem SMP System läuft.
Ich wollte meinen Kernel so klein wie möglich halten (also der Code und die Daten die nachher im Speicher liegen), aber die Komplexität nicht bis ins unendliche treiben und da muss man halt irgendwo Abstriche machen (deswegen Spinlocks die eher für SMP Systeme sind, da ist der Worst-Case niedriger als wenn ich Funktionen nutzen würde).

Also bei sleep(0) solte das selbe passieren wie wenn der Timer-IRQ kommt, bei einem x86-SMP eben der IRQ vom Local-APIC-Timer.

Das ist halt interpretations Sache. Ich stelle mir das halt so vor, das Programm liest die aktuelle Zeit, rechnet ein wenig rum und liest dann wieder die aktuelle Zeit, bildet die Differenz und macht mit der Differenz nen "sleep(diff)". Wenn der Wert der sleep übergeben wurde "0" ist (aus welchem Grund auch immer) und der Thread theoretisch noch Zeit übrig hätte, lasse ich ihn sofort wieder laufen. Ich weiß jetzt allerdings nicht wie sleep mit einem Wert von "0" definiert ist, könnte mir aber vorstellen dass das nirgends richtig steht (jetzt mal auf POSIX bezogen, obwohl ich den Standard nicht sehr mag).

[erik.vikinger]

Hallo,

Zumal was macht man denn im Endeffekt, was wirklich Leistung kostet? Es läuft immer auf das Rechnen ....

Wenn du das so betrachtest dann hat vieles mit Rechnen zu tun, obwohl z.B. cli/sti eher nicht und die Adressberechnungen bei Speicherzugriffen passieren heutzutage auch nicht mehr in der (Integer-)ALU. Aber lassen wir das sonst streiten wir noch bis die Forums-Datenbank platzt.

Ich stelle mir das halt so vor, das Programm liest die aktuelle Zeit, rechnet ein wenig rum und liest dann wieder die aktuelle Zeit, bildet die Differenz und macht mit der Differenz nen "sleep(diff)".

Hä, für was soll sowas gut sein? Damit lastest Du die CPU zu exakt 50% aus (die Pausenzeiten sind ja immer genau so lang wie die Arbeitszeiten). Also ich kann mir beim besten Willen nicht vorstellen wozu das nützlich sein soll, da solltest Du erst erklären was damit bezweckt werden soll.

Wenn der Wert der sleep übergeben wurde "0" ist (aus welchem Grund auch immer) und der Thread theoretisch noch Zeit übrig hätte, lasse ich ihn sofort wieder laufen.

Wieso? Der Thread hat doch explizit um eine Pause gebeten. Die Zeitangabe wird als Minimum und nicht als Maximum interpretiert. Wenn alle anderen Threads im System gerade nichts zu tun haben (also blockierend warten o.ä.) dann kommt Dein Thread sowieso schnell wieder dran.

Ich weiß jetzt allerdings nicht wie sleep mit einem Wert von "0" definiert ist, könnte mir aber vorstellen dass das nirgends richtig steht (jetzt mal auf POSIX bezogen, obwohl ich den Standard nicht sehr mag).

Bis jetzt hab ich das immer so erlebt das sleep(0) einfach nur die restliche Zeitscheibe frei gibt. Für Windows hab ich das gefunden: http://blog.m-ri.de/index.php/2010/01/23/was-denn-nun-switchtothread-sleep0-sleep1-2/, die 2 Kommentare stellen einiges klarer (vor allem der erste). Ein Sleep(0) ist natürlich nur dann sinnvoll wenn man davon aus gehen kann das es andere Threads gibt welche die CPU gerne nutzen würden, was beim warten auf einen mittelkurzen Lock natürlich gegeben ist.
Wie das mit sleep(0) bei POSIX ist weiß ich aber auch nicht genau. Ich hab mal für ein kleines RT-OS programmiert (das offiziell POSIX-Konform ist) und dort hat sleep(0) auch nur die aktuelle Zeitscheibe freigegeben und den Thread hinten an die entsprechende Scheduller-Liste angehängt (stand so in der Doku).
Es steht Dir natürlich frei das in Deinem OS fundamental anders zu implementieren, aber was versprichst Du Dir davon?


Grüße
Erik

[FlashBurn]

Hä, für was soll sowas gut sein? Damit lastest Du die CPU zu exakt 50% aus (die Pausenzeiten sind ja immer genau so lang wie die Arbeitszeiten). Also ich kann mir beim besten Willen nicht vorstellen wozu das nützlich sein soll, da solltest Du erst erklären was damit bezweckt werden soll.

Ups, Denkfehler Ich meinte natürlich sowas, das er die Berechnung in einer bestimmten Zeit haben will und wenn noch Zeit über ist, dann macht er nen sleep(restlicheZeit) (wobei halt auch 0 raus kommen könnte).

Bis jetzt hab ich das immer so erlebt das sleep(0) einfach nur die restliche Zeitscheibe frei gibt. Für Windows hab ich das gefunden: http://blog.m-ri.de/index.php/2010/01/23/was-denn-nun-switchtothread-sleep0-sleep1-2/, die 2 Kommentare stellen einiges klarer (vor allem der erste). Ein Sleep(0) ist natürlich nur dann sinnvoll wenn man davon aus gehen kann das es andere Threads gibt welche die CPU gerne nutzen würden, was beim warten auf einen mittelkurzen Lock natürlich gegeben ist.
Wie das mit sleep(0) bei POSIX ist weiß ich aber auch nicht genau. Ich hab mal für ein kleines RT-OS programmiert (das offiziell POSIX-Konform ist) und dort hat sleep(0) auch nur die aktuelle Zeitscheibe freigegeben und den Thread hinten an die entsprechende Scheduller-Liste angehängt (stand so in der Doku).
Es steht Dir natürlich frei das in Deinem OS fundamental anders zu implementieren, aber was versprichst Du Dir davon?

Ich kann das ganz leicht implementieren, indem ich bei sleep(0) einfach meinen Syscall zum abgeben aufrufe.
Der Grund warum das so bei meinem Scheduler (im Moment) nicht funktioniert ist, das ich immer am Anfang einer Liste adde (ist einfacher und geht schneller). Desweiteren kommt hinzu das ich mich noch nicht richtig mit scheduling Strategien auseinander gesetzt habe, aber soweit ich weiß ist meine niht ganz "normal". Da ich ne Ready- und ne Runqueue habe (wenn die Zeitscheibe eines Threads abgelaufen ist kommt er in die Runqueue, ist die Readyqueue leer, wird sie mit der Runqueue vertauscht, so dass alle bis auf die Idle-Threads min. einmal dran kommen).

Mal wieder back to topic, ich werd demnächst (sobald ich dazu komme) mal nen kleinen Benchmark machen, wie sich das Schreiben/Lesen auf uncachble Speicher auswirkt. Ich kann da leider nur testen, wie der best case aussieht, obwohl wohl eher der worst case (viele/alle CPUs wollen den Lock) interessanter wäre.

[erik.vikinger]

Hallo,

Ups, Denkfehler Ich meinte natürlich sowas, das er die Berechnung in einer bestimmten Zeit haben will und wenn noch Zeit über ist, dann macht er nen sleep(restlicheZeit) (wobei halt auch 0 raus kommen könnte).

Das würde ich lieber mit einem periodischem Event machen. Da kannst Du Dich auch auf die Periodendauer verlassen, wenn Du selber immer mitrechnest akkumulieren sich Fehler auf. Wenn Du damit rechnest das 0 raus kommt musst Du auch damit rechnen das was negatives bei raus kommt. Auch da wäre der periodische Event die bessere Wahl, da könntest Du einzelne Ausreißer kompensieren falls Du im Durchschnitt immer deutlich unterm Zeitlimit bleibst.

Ich kann das ganz leicht implementieren, indem ich bei sleep(0) einfach meinen Syscall zum abgeben aufrufe.

Am besten noch in der libc.

Der Grund warum das so bei meinem Scheduler (im Moment) nicht funktioniert ist, das ich immer am Anfang einer Liste adde (ist einfacher und geht schneller).

Das ist bei einem Scheduler aber wahrlich keine gute Variante.

Desweiteren kommt hinzu das ich mich noch nicht richtig mit scheduling Strategien auseinander gesetzt habe, aber soweit ich weiß ist meine niht ganz "normal".

Ich hab mal in einem Scheduler für jede Priorität eine eigene Liste (simples und fixes Array) angelegt und für jede Liste einen Pointer gehabt der jedes mal wenn aus der Liste ein Thread dran kam inkrementiert wurde. Das ließe sich auch mit einer dynamischen einfach im Kreis verketteten Liste machen.

so dass alle bis auf die Idle-Threads min. einmal dran kommen).

Ich hab zwar auch nicht viel Ahnung von diesem Thema aber das klingt nicht nach einer guten Idee. Round-Robin kann man auch einfacher haben.

Mal wieder back to topic, ich werd demnächst (sobald ich dazu komme) mal nen kleinen Benchmark machen, wie sich das Schreiben/Lesen auf uncachble Speicher auswirkt.

Für die Lock-Variablen ist IMHO richtiges non-cachable die beste Variante. Wenn Du richtig kopieren möchtest (als Benchmark) dann würde ich mal "Write-Combining" probieren, das dürfte zumindest den Schreib-Teil beschleunigen. Eigentlich schade das es in aktuellen CPUs fürs Lesen keine Entsprechung zum "Write-Combining" gibt.

Ich kann da leider nur testen, wie der best case aussieht, obwohl wohl eher der worst case (viele/alle CPUs wollen den Lock) interessanter wäre.

Wie sich Dein OS auf einem SMP-System mit sehr vielen CPUs verhält kannst Du leider auch nur auf einem solchen System testen.


Grüße
Erik

[FlashBurn]

Das würde ich lieber mit einem periodischem Event machen. Da kannst Du Dich auch auf die Periodendauer verlassen, wenn Du selber immer mitrechnest akkumulieren sich Fehler auf. Wenn Du damit rechnest das 0 raus kommt musst Du auch damit rechnen das was negatives bei raus kommt. Auch da wäre der periodische Event die bessere Wahl, da könntest Du einzelne Ausreißer kompensieren falls Du im Durchschnitt immer deutlich unterm Zeitlimit bleibst.

Ich muss dir ganz ehrlich sagen, irgendwie versteh ich grad nur Bahnhof

Also stell dir vor du schreibst nen Framelimiter. Da holst du dir die aktuelle Zeit, berechnest den Frame, holst dir die nun aktuelle Zeit, bildest die Differenz und wartest gegebenenfalls (was für ein Wort ).

Am besten noch in der libc.

Ich würde eher sagen, da auch Denn du weißt nie was so ein Programmierer alles für Späße treibt.

Das ist bei einem Scheduler aber wahrlich keine gute Variante.

Wieso? Ich denke mal du hast mich nicht richtig verstanden (da ich dir Infos vorenthalten habe).

Also mein Scheduler hat 32 Prioritätswarteschlangen (die eher wie ein Stack aufgebaut sind), eine Idlewarteschlange und (jedenfalls bald) eine Realtimewarteschlange. Jede Warteschlange ist wie gesagt eher wie ein Stack aufgebaut, da ich immer am Anfang der Liste/Queue adde.
Dann habe ich noch 2 Arrays, einmal ReadyQueueArray und einmal RunQueueArray (beide sind halt Arrays mit 32 Elementen, 1 Element für eine Priorität). Hat ein Thread seine Zeitscheibe verbraucht, dann kommt er in das RunQueueArray, ist das ReadyQueueArray leer, wird geschaut ob das RunQueueArray Elemente enthält, wenn ja werden die beiden Arrays vertauscht und wenn nicht laufen entweder die Threads aus der IdleQueue oder der IdleThread.

Die Idee ist, das es ein O(1) Scheduler ist (an den alten Linuxscheduler angelehnt) und das jeder Thread seiner Priorität entsprechend dran kommt. So vermeide ich nebenbei auch, das ein Thread theoretisch das ganze System lahmlegen kann (vorausgesetzt die Priorität ist hoch genug).

Du könntest jetzt sagen, dass das sowieso nicht passieren dürfte, da man die Priorität ja ändern sollte, mach ich auch, aber immer nur im Bereich -5/+5 der am Anfang festgelegten Priorität. So will ich vermeiden, das ein CPU intensiver Thread ganz bis nach unten durchgereicht wird.

(Vielleicht sollte man dazu mal nen extra Thread aufmachen, wo dann über Schedulingstrategien diskutiert wird.)

Für die Lock-Variablen ist IMHO richtiges non-cachable die beste Variante. Wenn Du richtig kopieren möchtest (als Benchmark) dann würde ich mal "Write-Combining" probieren, das dürfte zumindest den Schreib-Teil beschleunigen. Eigentlich schade das es in aktuellen CPUs fürs Lesen keine Entsprechung zum "Write-Combining" gibt.

Wo ist jetzt der Unterschied zw. non-cacheable und uncachceable (ich wollte das einfach über die Flags in der Pagetable machen)?
Wenn ich dich richtig verstehe, meinst du das man mehrere Lesebefehle koppelt und dann erst den Speicher liest? Ich meine das geht ja schlecht, wenn du nur 1byte liest und daraufhin dann viele Bytes schreibst, müsstest du ja ewig warten, oder habe ich da am Write-Combining was falsch verstanden?

[erik.vikinger]

Hallo,


Sorry, für mein Delay, ich hab eine recht bewegte Woche hinter mir.

Also stell dir vor du schreibst nen Framelimiter. Da holst du dir die aktuelle Zeit, berechnest den Frame, holst dir die nun aktuelle Zeit, bildest die Differenz und wartest gegebenenfalls (was für ein Wort ).

Genau so eine Anwendung schwebt mir auch vor. Üblicherweise löst man das Problem, das man regelmäßig bestimmten Code abgearbeitet haben möchte, damit das man von einem periodischen Event (der genau mit einer bestimmten Frequenz oder Periodendauer kommt) "angetriggert" wird.
Der User-Code sieht dann etwa so aus:

Code: [Auswählen]

event = EventCreatePeridoc(frequenz);  //erstelle ein Event-Object das mit einer bestimmten Frequenz immer wieder angetriggert wird

while(true)
{
EventWait(event);  //warte bis Event getriggert wurde, setzt den Event nach dem Warten wieder auf ungetriggert zurück, wenn der Event bereits getriggert wurde dann muss nicht gewartet werden
tuWas;             //Code der regelmäßig ausgeführt werden soll
}Solange der Code immer schnell genug fertig wird wartet der Thread immer genau die Rest-Zeit ab und macht dann weiter, falls der Code ein klein wenig zu lange braucht dann macht er sofort weiter. Der Vorteil ist das die ganze Zeitrechnerei nicht im User-Space mit relativen Zeiten sondern direkt im Kernel mit absoluten Zeiten stattfindet, der Kernel errechnet den nächsten Trigger-Zeitpunkt nicht als Differenz sondern absolut aus dem Zeitpunkt der Event-Erstellung und der Frequenz bzw. Periodendauer. Da die Triggerfrequenz nicht unbedingt Teilergleich (nennt man das so, ich denke da gibt es nen besseren Begriff) mit der System-Timer-Frequenz ist kommt es zu einem gewissen Jitter wenn die Trigger-Zeitpunkte in das System-Zeit-Raster überführt werden müssen, aber wenn die Rechnung im Kernel ordentlich gecodet ist dann ergibt sich auch auf lange Sicht keine Abweichung. Wenn man hingegen immer die sleep-Funktion mit einer Differenz aufruft dann werden sich da unvermeidlich Fehler aufakkumulieren, außerdem kannst Du sleep nicht mit negativen Werten benutzen falls Dein Code mal ein klein wenig überzogen hat (dann wäre auch Dein neuer Start-Zeitpunkt falsch).
Wenn Du möchtest können wir dazu aber mal einen neuen Thread aufmachen da eine ausführliche Erklärung sonst doch zu arg Offtopig wird.

Am besten noch in der libc.

Ich würde eher sagen, da auch Denn du weißt nie was so ein Programmierer alles für Späße treibt.

Ohja, ich kenn mich ja schließlich auch selber.

da ich dir Infos vorenthalten habe

Offensichtlich, is nicht schlimm.

Vielleicht sollte man dazu mal nen extra Thread aufmachen, wo dann über Schedulingstrategien diskutiert wird.

Gerne.
Zum diskutieren (und manchmal auch streiten) hab ich (fast) immer Lust.

Wo ist jetzt der Unterschied zw. non-cacheable und uncachceable (ich wollte das einfach über die Flags in der Pagetable machen)?

Ich glaube da ist kein Unterschied.
Die Bits (wimre 3 Bits) in den Page-Descriptoren werden als Index in ein spezielles MSR interpretiert und dort gibt es dann mehr Möglichkeiten, zumindest auf aktuellen CPUs. Ich weiß jetzt nicht mehr welches MSR das ist aber das sollte sich bestimmt in den einschlägig bekannten Dokus finden lassen, dieses MSR ist aber so vorbelegt das damit die alte/direkte Funktionalität der Descriptor-Bits quasi nachgeahmt wird.

Wenn ich dich richtig verstehe, meinst du das man mehrere Lesebefehle koppelt und dann erst den Speicher liest? Ich meine das geht ja schlecht, wenn du nur 1byte liest und daraufhin dann viele Bytes schreibst, müsstest du ja ewig warten,

Hä, was meinst Du? Kann es sein das Du "Schreibbefehle" und "schreibst" meinst?

oder habe ich da am Write-Combining was falsch verstanden?

Mit "Write-Combining" ist gemeint das der Schreibbefehl nicht sofort ausgeführt wird, also nicht sofort eine Write-Message mit den Daten losgeschickt wird, sondern das es einen kleinen zusätzlichen Write-Buffer (meistens 2 oder 4 Cache-Lines o.ä.) gibt in den der Schreibbefehl erst mal geht (und nicht in den normalen Cache) und wenn dann nachfolgenden Schreibbefehle in die selbe Cache-Line gehen dann landen die auch erst mal in diesem Puffer. Diese Puffer werden später in den Speicher geschrieben, aber da erst mal mehrere einzelne Schreibbefehle gesammelt werden müssen weniger richtige Schreibzugriffe auf den Speicher durchgeführt werden. Beim Schreibteil vom Kopieren werden damit immer ganze Cache-Lines gesammelt und am Stück zum Speicher gesendet, daher profitiert x86 beim memcpy mit mehr als 2000 Bytes auch (fast) gar nicht von ausgerichteten Daten. Siehe auch http://en.wikipedia.org/wiki/Write-combining.


Grüße
Erik

[FlashBurn]

Sorry, für mein Delay, ich hab eine recht bewegte Woche hinter mir.

Kein Prob, habe die Woche auch nichts wirklich zustande gebracht

Der Vorteil ist das die ganze Zeitrechnerei nicht im User-Space mit relativen Zeiten sondern direkt im Kernel mit absoluten  Zeiten stattfindet, der Kernel errechnet den nächsten Trigger-Zeitpunkt nicht als Differenz sondern absolut aus dem Zeitpunkt der Event-Erstellung und der Frequenz bzw. Periodendauer. Da die Triggerfrequenz nicht unbedingt Teilergleich (nennt man das so, ich denke da gibt es nen besseren Begriff) mit der System-Timer-Frequenz ist kommt es zu einem gewissen Jitter wenn die Trigger-Zeitpunkte in das System-Zeit-Raster überführt werden müssen, aber wenn die Rechnung im Kernel ordentlich gecodet ist dann ergibt sich auch auf lange Sicht keine Abweichung. Wenn man hingegen immer die sleep-Funktion mit einer Differenz aufruft dann werden sich da unvermeidlich Fehler aufakkumulieren, außerdem kannst Du sleep nicht mit negativen Werten benutzen falls Dein Code mal ein klein wenig überzogen hat (dann wäre auch Dein neuer Start-Zeitpunkt falsch).

Nur mal als kurze Antwort, hast du schonmal versucht sowas zu schreiben (und dabei das restliche System nicht aus den Augen verloren)? Ich weiß das bei meinem Code eine Abweichung (welche auf nem alten PC mit nur nem PIT bei so 2µs pro Scheduler-Aufruf liegt) auftritt und die sich dann summiert. Bei nem Multi-CPU System liegt es am I/O-Aufkommen (und Spinlock Aufkommen) wie ungenau diese Zeit ist.

Hä, was meinst Du? Kann es sein das Du "Schreibbefehle" und "schreibst" meinst?

Du meintest doch das es nicht schlecht wäre ne Art "Read-Combining" zu haben oder? Und da müsstest du ja auf die Daten warten, bis halt genug Lesebefehle zusammengekommen sind, oder? Obwohl mir gerade auffällt dass das dann beim Write-Combining das selbe Problem geben würde, aber es scheint ja zu funktionieren. Ich habe halt gerade ein Problem damit, was passiert wenn du nur ein Byte schreiben willst, die CPU kann ja nicht warten bis andere Schreibbefehle den Buffer voll gemacht haben, denn es kann ja sein, das andere CPUs auf diesen Wert zugreifen wollen (dann würde dir auch ne Spinlock zum Schützen von kritischen Bereichen nichts nutzen).

Ich mach dann mal nen Thread für Schedulingstrategien auf, müsste mich damit ja eh mal befassen.

[erik.vikinger]

Hallo,

Nur mal als kurze Antwort, hast du schonmal versucht sowas zu schreiben (und dabei das restliche System nicht aus den Augen verloren)?

Ja, ich hab es allerdings nicht nur versucht sondern auch getan. Hat wunderbar funktioniert, war aber nur eine CPU, mit mehreren CPUs hätte mein damaliger Hack auch nicht funktioniert.

Ich weiß das bei meinem Code eine Abweichung (welche auf nem alten PC mit nur nem PIT bei so 2µs pro Scheduler-Aufruf liegt) auftritt und die sich dann summiert. Bei nem Multi-CPU System liegt es am I/O-Aufkommen (und Spinlock Aufkommen) wie ungenau diese Zeit ist.

Das es einen Jitter gibt ist völlig klar, aber wenn Du eine monotone Zeitquelle hast (wie z.B. den HPET, der PIT geht sicher auch aber da musst Du Dich mit einem groben Zeit-Raster arrangieren das kaum über 1000 Hz liegen wird) kannst Du doch mit der gleichmäßig voranschreitenden Zeit gut rechnen.
Wo genau hast Du bedenken? Soll ich dazu einen neuen Thread aufmachen?

Du meintest doch das es nicht schlecht wäre ne Art "Read-Combining" zu haben oder?

Ja. Ich würde mir dafür wünschen das die Write-Buffer auch für Lesebefehle benutzt werden können. Dieser Write-Buffer ist eine Art Cache, parallel (oder auch nachgeschaltet um Cache-Line-Write-Backs das normalen Caches aufnehmen zu können) zum normalen Daten-Cache, mit ein paar wenigen voll-assoziativen Cache-Lines, einfach aufgrund seiner winzigen Größe werden Daten dort nicht lange drin bleiben. Modifizierte Lines in diesem "Mini-Cache" werden, sobald sie nicht mehr die "zuletzt benutzte" sind, möglichst bald in den Speicher geschrieben. Schreibzugriffe werden dadurch nur kurz verzögert und sind eben auch nicht immer in korrekter Reihenfolge nach außen sichtbar. Mit WC markiert man nur Speicherbereiche die zwar nicht wirklich gecachet werden sollen aber bei denen eine kurze Verzögerung und inkorrekte Reihenfolge kein Problem sind, bestes Beispiel ist der Frame-Buffer auf einer Grafikkarte. Die Befehle MFENCE und SFENCE lehren/flushen wimre auch diesen Write-Buffer. Wenn in so einer Write-Buffer-Line nur ein paar modifizierte Bytes drin sind dann werden eben nur die zum Speicher gesendet wenn die betreffende Line verschwinden soll.

Beim Zusammenfassen von Lesezugriffen, was man dann wohl eher mit "Read-Ahead" umschreiben dürfte, stelle ich mir vor das zwar auch immer gleich ganze Cache-Lines gelesen werden und nachvolgende Lesebefehle sich gegebenenfalls auch daraus bedienen (so das nach außen nur ein Lesebefehl sichtbar ist) aber diese Cache-Lines nicht in den normalen Cache kommen, um dort länger zu bleiben, sondern in den kleinen Mini-Cache, um dort möglichst bald wieder zu verschwinden.

Lock-Variablen darf man in solche Speicherbereiche natürlich nicht legen. Die müssen entweder komplett ungecached sein oder richtig dem Cache-Kohärenz-Protokoll unterliegen. Solche schwach gecachten Speicherbereiche kann man aber zumindest mit normalen Locks absichern wenn man sich der Befehle LFENCE, SFENCE und MFENCE bedient, glaube ich zumindest aber so fit bin ich diesbezüglich bei x86 nun auch wieder nicht.

Ich mach dann mal nen Thread für Schedulingstrategien auf, müsste mich damit ja eh mal befassen.

Ich werd mal drüber nachdenken und dann was schreiben.


Grüße
Erik

[FlashBurn]

Wo genau hast Du bedenken? Soll ich dazu einen neuen Thread aufmachen?

Ein neuer Thread wäre nicht schlecht zu dem Thema (hatte ich zwar schon in einem anderem Board, aber neue Ideen sind immer willkommen). Mein Lieblingsbeispiel für Bedenken ist der PIT, weil der Zugriff alleine schon langsam ist (pro Zugriff in/out 838ns Verzögerung) und dann kann es durch das Ausschalten von den Ints auch noch zu einer zusätzlichen Verzögerung kommen und dadurch das ich den Timer (welchen ich auch immer nutze) im One-Shot-Modus benutze, kommen bei mir pro Scheduler Aufruf 5 Zugriffe (3x out, 2x in) auf den Timer (was beim PIT alleine schon ne Verzögerung von 4190ns ~ 4µs macht, pro Scheduleraufruf!). Ich bin da gerne offen für Vorschläge zur Verbesserung (gibt nur Beschränkungen die es erschweren).

Beim Zusammenfassen von Lesezugriffen, was man dann wohl eher mit "Read-Ahead" umschreiben dürfte, stelle ich mir vor das zwar auch immer gleich ganze Cache-Lines gelesen werden und nachvolgende Lesebefehle sich gegebenenfalls auch daraus bedienen (so das nach außen nur ein Lesebefehl sichtbar ist) aber diese Cache-Lines nicht in den normalen Cache kommen, um dort länger zu bleiben, sondern in den kleinen Mini-Cache, um dort möglichst bald wieder zu verschwinden.

Mit "Read-Ahead" kann ich schon mehr anfangen (und sowas haben wir ja auch in neueren CPUs). Ich weiß nicht, aber reicht nicht der Prefetcher?