Thema: Threads blockieren und wieder aufwecken

[FlashBurn]

Hm, ich bin mir gar nicht mal so sicher ob das wirklich eine schlechte/unperformante Lösung ist, das Kopieren (vom Stack zum Thread-Descriptor) ließt doch aus Speicher der mit extrem hoher Wahrscheinlichkeit noch im L1-Cache ist und das Schreiben wird beide male (beim PUSHAD wie beim MOVSD) per Write-Allocation bequem und unsichtbar im Hintergrund erledigt. Da es bei x86 ja wohl nicht ganz so einfach ist die Adresse des richtigen Thread-Descriptors schnell zu bekommen und man auch immer erst mal ein oder zwei Register aus dem Weg schaffen muss könnte die Variante mit PUSHAD im INT-Assembler-Stub und dann Kopieren im Hochsprachenteil tatsächlich sogar die Schnellste aller möglichen Lösungen auf x86 sein.

Das Kopieren passiert so kurz danach, das die Daten auf jeden Fall noch im L1-Cache sind (selbst bei älteren CPUs). Den Thread-Discriptor zu bekommen ist nicht mal das Problem, wenn ich es genau überlege könnte ich sogar den Pointer für den Thread-State sehr einfach bekommen, indem ich den auch in meiner CPU-lokalen-Struct packe (sind es halt 4bytes mehr, aber das macht da gar nix). Auf den Stack müsste ich es aber trotzdem pushen, weil ich die gesicherten Werte später in genau den gleichen Registern wieder brauche (beim Verlassen des Syscalls zurück in den UserMode).

Also das klingt wirklich unelegant, dagegen ist doch meine Job-Queue für die Idle-Aufgaben des Kernels noch ein Kinderspiel. Generierst Du für einen IRQ wirklich X andere IRQs (IPIs)? Hast Du schon mal die IRQ-Latenz in Deinem OS gemessen?

Ich habe das Gefühl du sprichst von was anderem als ich

Was ich beschrieben habe, ist der Weg wie die anderen CPUs (bzw. eine) erfahren das es einen neuen Thread gibt, der eine potentiell höhere Priorität hat als die gerade laufenden Threads. Das hat nix mit dem Idle-Thread zu tun.

Also ich bin schon der Meinung das der local-APIC für genau solche Dinge da ist (oder zumindest sein sollte). Das mit dem Debug-Register ist zwar ne nette Idee (kannte ich noch gar nicht) aber spätestens wenn Du mal vernünftig Debuggen willst wird Dir das Register fehlen. Ich bin mir aber sicher das man auch bei den MSRs (kommt den lokalen Controll-Registern auf meiner CPU auch am nächsten) einige Register finden wird die sich für sowas benutzen lassen und das ganz ohne das man da auf irgendeine wichtige Funktionalität verzichten muss. Spontan würden mir da z.B. die MTRRs einfallen, von den flexiblen MTRRs gibt es einige und ich denke das es recht unwahrscheinlich ist dass das BIOS wirklich alle davon benötigt (und selbst wenn doch hat es zumindest keine funktionalen Einschränkungen wenn man eines davon missbraucht sondern man beeinflusst nur die Perfomance ).

Das ist ne ganz schlechte Idee, du weißt weder beim APIC noch bei den MSRs (da sogar noch weniger), welche Register auf welcher CPU frei sind und ob sie sich nicht mit der nächsten Generation schon geändert haben.
Ich weiß das du mehrere Debugging-Register hast und nicht unbedingt alle brauchst, von daher sollte das nicht das Problem sein, ansonsten bietet sich halt ne CPU-lokale-Struktur an (die ich über Segmente und, in meinem Fall, das gs-Register ansprechen kann).

Nö, da fällt mir nix auf! Warum auch? Wenn z.B. ein Event gleich mehrere Male kurz hintereinander getriggert wird dann werden auch kurz hintereinander mehrere Threads geweckt (falls den genügend warten).

Ähm, das ist genau das was passiert wenn du mehrere Male kurz hintereinander bei einer Semaphore release() aufrufst

Also wenn du bei deinem Event event_wait() machst, wird der Thread der das macht, gequeuet, passiert bei einer Semaphore die man mit acquire() aufruft auch. Bei deinem Event wird dann von irgendwem event_trigger() aufgerufen und dieser Thread wird wieder "frei gelassen", passiert bei der Semaphore auch, wenn du release() aufrufst.

Ich sehe da immer noch keinen Unterschied.

Selbst zum Synchronisieren ist diese Art von Event IMHO nicht wirklich geeignet, höchstens zum Serialisieren.

Gut möglich das ich da im Moment etwas mit dem Vokabular durcheinander komme, aber ist das im Endeffekt nicht das gleiche?

[erik.vikinger]

Hallo,

indem ich den auch in meiner CPU-lokalen-Struct packe

Und wie kommst Du an den? Bzw. ganz generell, wie ermittelst Du die aktuelle CPU-Nummer (am besten linear von 0 bis Anzahl-1 durchnummeriert)?

Ich habe das Gefühl du sprichst von was anderem als ich

Nein, mir ist schon klar das es bei Dir um das weitergeben von Aufgaben (egal ob Threads oder IRQs) geht. Ich finde das extrem kompliziert, generell halte ich nicht sehr viel von IPIs, ich sehe darin keinen echten Nutzen bzw. eine extrem komplizierte Lösung für Probleme die auf einer anständig designten Plattform einfacher zu lösen wären oder erst gar nicht vorhanden wären. Mir ist klar das es bei x86 einige Dinge gibt die man ohne IPIs nur noch umständlicher gelöst bekommt, z.B. das globale TLB-Löschen auf allen CPUs, aber trotzdem empfinde ich dieses Konzept als ziemlich unelegant.

Mich würde trotz allem mal interessieren was Dein OS für eine IRQ-Latenz bietet.

Was ich beschrieben habe, ist der Weg wie die anderen CPUs (bzw. eine) erfahren das es einen neuen Thread gibt, der eine potentiell höhere Priorität hat als die gerade laufenden Threads. Das hat nix mit dem Idle-Thread zu tun.

Warum leitest Du IRQs nicht immer zu der CPU welche aktuell die SW mit der niedrigsten Priorität ausführt? Ich dachte eigentlich das es genau dafür dieses SW-Priority-Register im local-APIC gibt.

Das ist ne ganz schlechte Idee, du weißt weder beim APIC noch bei den MSRs (da sogar noch weniger), welche Register auf welcher CPU frei sind und ob sie sich nicht mit der nächsten Generation schon geändert haben.

Das ist natürlich richtig, aber viele der MSRs sind seit dem ersten Pentium unverändert (wozu wimre auch die MTRRs gehören) und die bestehende SW verlässt sich darauf dass das auch so bleibt, von daher denke ich dass das kein allzu großes Problem ist.

Ich weiß das du mehrere Debugging-Register hast und nicht unbedingt alle brauchst, von daher sollte das nicht das Problem sein

Schon klar das man von den Debugging-Registern nicht unbedingt alle braucht aber wenn Du sie doch mal nutzen möchtest und eines fehlt ist das einfach ziemlich doof, nebst dessen das sich die existierenden Debugger auch auf die spezifizierte Anzahl verlassen und vielleicht kräftig auf die Nase fliegen wenn das unerwartet nicht klappt.

ansonsten bietet sich halt ne CPU-lokale-Struktur an (die ich über Segmente und, in meinem Fall, das gs-Register ansprechen kann).

Stimmt, das ist auch noch ne gute Variante. Leider sind dafür nur 2 Segment-Register verfügbar und eines davon wirst Du schon für TLS nutzen wollen. Trotz allem wäre es cool wenn Intel/AMD in die MSRs einfach 2 bis 4 frei nutzbare Register integrieren würde die dem OS zuverlässig nach eigenem Ermessen zur Verfügung stehen, das tät kaum nennenswert Transistoren kosten aber auf jeden Fall einige Dinge erheblich vereinfachen.


Das Deine Vorstellung von einem Semaphor meiner Vorstellung von einem Event-Mechansimus (bei einigen Embedded/RT-OSen firmiert das auch unter dem Namen "Signal-Slot") ungefähr entspricht mag ja sein aber ich finde nicht das es deswegen das Selbe ist oder Beides gegeneinander ersetzbar/austauschbar wäre.


Grüße
Erik

[FlashBurn]

Und wie kommst Du an den? Bzw. ganz generell, wie ermittelst Du die aktuelle CPU-Nummer (am besten linear von 0 bis Anzahl-1 durchnummeriert)?

Ich nutze das fs-Register für TLS und das gs-Register für die CPU-lokale-Struct, wo auch die CPU-Nummer drin steht (aber die würdest du auch durch den APIC bekommen und der ist immer an der selben Stelle gemappt).

Ich finde das extrem kompliziert, generell halte ich nicht sehr viel von IPIs, ich sehe darin keinen echten Nutzen bzw. eine extrem komplizierte Lösung für Probleme die auf einer anständig designten Plattform einfacher zu lösen wären oder erst gar nicht vorhanden wären. Mir ist klar das es bei x86 einige Dinge gibt die man ohne IPIs nur noch umständlicher gelöst bekommt, z.B. das globale TLB-Löschen auf allen CPUs, aber trotzdem empfinde ich dieses Konzept als ziemlich unelegant.

Wie löst du das denn auf deiner Architektur (andere CPUs benachrichtigen)?

Mich würde trotz allem mal interessieren was Dein OS für eine IRQ-Latenz bietet.

Mich auch

Was verstehst du denn darunter? Die Zeit vom feuern des IRQ´s bis zum Senden des EOI? Wie würde man sowas überhaupt messen?

Warum leitest Du IRQs nicht immer zu der CPU welche aktuell die SW mit der niedrigsten Priorität ausführt? Ich dachte eigentlich das es genau dafür dieses SW-Priority-Register im local-APIC gibt.

Wie soll ich es sagen ... genau das mache ich

Wenn ich so darüber nachdenke, kann die Situation das die anderen CPUs eine IPI-Nachricht bekommen müssen, im Falle von IRQs eh nie auftreten. Allerdings muss ich bei der If-Abfrage noch eine kleine Änderung vornehmen.
Wenn die Priorität des aktuellen Threads kleiner des neuen Threads ist, wird nur die aktuelle CPU in den Scheduler geschickt, ist die Priorität größer als die des neuen Threads, wird eine IPI-Nachricht versendet und wenn sie gleich ist wird gar nichts gemacht (und das ist dann für die IRQs wichtig).
Weil im Falle der IRQs kann es nur zu der Situation kommen, dass entweder der Thread der aktuellen CPU kleiner oder gleich ist, womit keine IPI-Nachricht nötig ist.

Da kommen wir aber zu einem Thema, was besser einem neuem Thread diskutiert wird, nämlich Scheduling-Strategien und sowas. Da zählt dann auch rein, wann man eine CPU im Ruhezustand lässt und wann man sie besser aufweckt. Denn es ist ja nicht immer nötig eine CPU aufzuwecken, bei einem IRQ z.B. würde ich lieber eine CPU nutzen die eh schon läuft als eine aufzuwecken.

Das Deine Vorstellung von einem Semaphor meiner Vorstellung von einem Event-Mechansimus (bei einigen Embedded/RT-OSen firmiert das auch unter dem Namen "Signal-Slot") ungefähr entspricht mag ja sein aber ich finde nicht das es deswegen das Selbe ist oder Beides gegeneinander ersetzbar/austauschbar wäre.

Was ist denn mit deinem Event möglich, was nicht mit einer Semaphore geht?

[erik.vikinger]

Hallo,

wo auch die CPU-Nummer drin steht (aber die würdest du auch durch den APIC bekommen und der ist immer an der selben Stelle gemappt).

Kann bei Dir auch der User-Space an die CPU-Nummer ran? Ist die CPU-Nummer in den local-APICs wirklich linear durchgezählt (das wäre sehr nützlich um diese als Index für ein Array nutzen zu können)?

Wie löst du das denn auf deiner Architektur (andere CPUs benachrichtigen)?

Gar nicht. Diese Funktionalität ist auf meiner Plattform nicht vorgesehen, ich wüsste auch nicht wozu.

Was verstehst du denn darunter? Die Zeit vom feuern des IRQ´s bis zum Senden des EOI? Wie würde man sowas überhaupt messen?

Für die IRQ-Latenz gibt es zwei Definitionen: einmal vom HW-IRQ-Signal bis der erste Befehl vom tatsächlichen IRQ-Handler ausgeführt wird (diese Definition hat einen großen Jitter weil IRQs ja auch ab und an mal gesperrt sein können, aber gerade hierbei ist der Worst-Case für harte Echt-Zeit-Systeme relevant) und zum anderen vom Ausliefern durch den IRQ-Controller an eine CPU bis der erste Befehl vom tatsächlichen IRQ-Handler ausgeführt wird (hierbei spielt die Effizienz der IRQ-Verarbeitung des OS die entscheidende Rolle, da dürften eigentlich monolithische OSe klar im Vorteil sein). Für Dein OS würde mich mal der zweite Wert interessierten aber der ist dem Best-Case des ersten Wertes sehr ähnlich so das er relativ einfach zu ermitteln sein müsste. Bei beiden Definitionen ist aber gerade das mit dem ersten Befehl vom tatsächlichen IRQ-Handler (womit der des eigentlichen Geräte-Treibers gemeint ist) ein schwieriges Problem weil das in modernen OSen oft etwas verzerrt ist. Unter Windows soll die eigentliche Bearbeitung des IRQ erst im sogenannten DPC-Handler passieren und da kann zwischen dem vorgelagerten kurzen IRQ-Handler (an dessen Ende auch das EOI an den IRQ-Controller gemeldet wird) und diesem DPC-Handler doch schon mal einiges an Zeit vergehen. Linux und wimre auch MAC OS X haben ähnliche Mechanismen die vor allem wegen den shared IRQs nötig sind. Ein Micro-Kernel-OS das auf einer Plattform ohne IRQ-Sharing läuft hat also gute Chancen besser zu sein als die etablierten OSe auf x86.


Grüße
Erik

[FlashBurn]

Kann bei Dir auch der User-Space an die CPU-Nummer ran?

Jein, nicht über diese CPU-lokale-Struct, aber durch die CPUID Instruktion.

Ist die CPU-Nummer in den local-APICs wirklich linear durchgezählt (das wäre sehr nützlich um diese als Index für ein Array nutzen zu können)?

Auch wieder jein

Praktisch schon, theoretisch solltest du nicht darauf bauen. "Problem" ist, falls ein Kern defekt oder was weiß ich nicht ist, hat er trotzdem seine Nummer. Du hast ja z.B. bei ACPI eine Liste mit lokalen APICs und dort ist ja jedes Mal nen Flag ob die CPU in Ordnung ist. Praktisch fällt mir kein Szenario ein wo das mal vorkommen sollte, aber theoretisch ist es halt so.

Aber wieso willst du über ein Index in ein Array gehen, wenn du genau dafür doch sehr gut Segmente nutzen kannst?

Gar nicht. Diese Funktionalität ist auf meiner Plattform nicht vorgesehen, ich wüsste auch nicht wozu.

Also auf x86 brauchst du es für die TLBs und ich brauche es (in meiner naiven Sicht) für den Scheduler, weil ich der Meinung bin, das immer die Threads mit der höchsten Priorität laufen sollten. Also brauche ich die Möglichkeit die anderen CPUs zu benachrichtigen das es neue Threads mit höherer Priorität gibt. Etwas was ich bisher nur an einer Stelle brauche, sind Rendez-Vous Punkte und da machen sich IPI´s auch ganz gut, z.B. beim Panic um alle CPUs zu stoppen.

Für Dein OS würde mich mal der zweite Wert interessierten aber der ist dem Best-Case des ersten Wertes sehr ähnlich so das er relativ einfach zu ermitteln sein müsste.

Naja, der Handler im Kernel macht nix anderes als Nachrichten zu verschicken (und da kann man nur hoffen, das nicht zu viele Geräte den gleichen IRQ nutzen), was wiederrum ja pro Nachricht eine Thread Erstellung bedeutet und dann wird sofort auf diesen Thread gewechselt (sofern nicht ein anderer Treiber-Thread schon läuft). Wobei man natürlich noch "kurz" durch den Scheduler muss.

Interessant wäre es, ob es nicht für die Latenz gut wäre, wenn man bei mehreren Nachrichten die anderen CPUs in den Scheduler (per IPI) zwingt. Weil so würde die anderen CPUs erstmal bis zum Ende der Zeitscheibe arbeiten und dann feststellen das es neue Threads mit höherer Priorität gibt (da wären wir dann wieder bei Scheduling-Strategien).

[erik.vikinger]

Hallo,

Jein, nicht über diese CPU-lokale-Struct, aber durch die CPUID Instruktion.

Aber CPUID liefert wimre nur eine physische CPU-Position, in der Art von Sockel/Core/Thread, und keine lineare Nummer, oder?

Praktisch schon, theoretisch solltest du nicht darauf bauen. "Problem" ist, falls ein Kern defekt oder was weiß ich nicht ist, hat er trotzdem seine Nummer.

Gut, dann hätte man eben bei einer defekten CPU einen unbenutzten Eintrag im Array, da das doch ziemlich selten ist denke ich das man diese kleine Speicherverschwendung problemlos akzeptieren kann.

Aber wieso willst du über ein Index in ein Array gehen, wenn du genau dafür doch sehr gut Segmente nutzen kannst?

Ich denke da z.B. an den CPU-lokalen Slot-Mechanismus eines SLAB-Allocators (auch im User-Mode) für den es essenziell wichtig ist möglichst performant an die CPU-Nummer zu kommen und auch das diese linear durchgezählt ist damit man eben die zugehörigen Datenstrukturen in einem simplen und schnellen Array ablegen kann. Für jeden Kram gleich wieder ein eigenes Segment zu erstellen hallte ich nicht für sehr geschickt, nebst dessen das auch meine 16 Segmentregister irgendwann aus gehen wenn man zu viele davon für feste Aufgaben reserviert (ich hab da bis jetzt nur TLS vorgesehen ansonsten benötige ich sowas weder im User-Mode noch im Kernel-Mode).

und ich brauche es (in meiner naiven Sicht) für den Scheduler, weil ich der Meinung bin, das immer die Threads mit der höchsten Priorität laufen sollten.

Schon klar aber eigentlich gibt es doch nur 2 Quellen für neue Threads (die dann potentiell eine höhere Priorität haben können): einmal HW-IRQs und dann der CreateThread()-Syscall. Bei der zweiten Möglichkeit wird eben anhand der Priorität entschieden welcher Thread als nächstes auf der aktuellen CPU läuft, falls der neue Thread eine höhere Priorität haben soll als der der ihn erstellt dann startet die CPU eben als erstes den neuen Thread und der Ersteller-Thread wird als RUNNABLE markiert und in die runnable-Liste des Schedulers eingetragen (falls auf einer anderen CPU ein Thread mit einer niedrigeren Priorität läuft dann wird der Scheduler das spätestens am Ende von dessen Zeitscheibe merken). Bei der erstem Möglichkeit kann es sein das für einen HW-Geräte-IRQ ein neuer PopUp-Thread mit hoher Priorität erstellt wird und dann läuft dieser eben auf der aktuellen CPU weiter und der unterbrochene Thread kommt in die runnable-Liste des Schedulers (wenn die IRQ-Priorität mit der Priorität des IRQ-Handler-Threads übereinstimmt und das prioritätsbasierende IRQ-Routing gut funktioniert dann sollte der IRQ ja eh nur von einer CPU angenommen werden die aktuell einen Thread mit einer niedrigeren Priorität ausführt). Es kann aber auch sein das durch einen IRQ, z.B. vom Timer, ein existierender Thread geweckt wird und ob dieser Thread den aktuellen Thread verdrängt hängt eben davon ab ob der geweckte Thread eine höhere Priorität als der unterbrochene Thread hat, in jedem Fall wird der unterlegene Thread in die runnable-Liste des Schedulers eingetragen.

Viele Worte, wenig Sinn: ich sehe keinen Grund warum man dafür IPIs benötigt. Klar gibt es Szenarien wo ein Thread mal nicht dran kommt obwohl auf einer anderen CPU gerade ein Thread mit einer niedrigeren Priorität läuft (es könnte z.B. passieren das während eine CPU für einen IRQ einen neuen Thread erzeugt oder einen bestehenden aufweckt auf einer anderen CPU gerade ein Syscall ausgeführt wird (so das diese CPU den IRQ eben nicht annehmen kann) aber der Syscall-verursachende Thread eine noch niedrigere Priorität hat als der auf der ersten CPU unterbrochene Thread, dann bleibt der unterbrochene Thread eben solange untätig in der runnable-Liste des Schedulers liegen bis auf der anderen CPU die Zeitscheibe für den niedrig priorisierten Thread abgelaufen ist) aber was solls Du entwickelst doch kein hartes Echtzeit-OS oder? Solange Deine Zeitscheiben nicht zu lang sind (bei Threads mit recht niedriger Priorität kannst Du die ja noch zusätzlich verkürzen) dürfte für ein normales Desktop-System keinerlei Problem daraus entstehen.

Also brauche ich die Möglichkeit die anderen CPUs zu benachrichtigen das es neue Threads mit höherer Priorität gibt.

Das ist etwas was IMHO nur dann Sinn ergibt wenn jede CPU eine eigene runnable-Liste hat und der übergeordnete Scheduler die Last mal wieder fair über alle CPUs verteilen muss, solange es nur eine globale runnable-Liste gibt wird sich doch eh recht zügig ein Gleichgewicht einstellen.

Etwas was ich bisher nur an einer Stelle brauche, sind Rendez-Vous Punkte und da machen sich IPI´s auch ganz gut, z.B. beim Panic um alle CPUs zu stoppen.

Hm, darüber hab ich noch gar nicht wirklich nachgedacht, eigentlich bin ich der Meinung keine Rendez-Vous-Punkte zu benötigen aber das mit dem Panic erscheint mir dann doch wichtig. Beim normalen Shutdown wollte ich es eigentlich so machen das alle normalen Prozesse beendet werden und dann auch die ganzen Treiber entladen werden (wobei auch die Dateisysteme entmountet werden) und zum Schluss der init-Prozess einfach das Netzteil abschaltet, meinem OS-Kernel und der innersten Personality will ich gar nicht die Fähigkeit zum kontrollierten Abschalten geben.

Interessant wäre es, ob es nicht für die Latenz gut wäre, wenn man bei mehreren Nachrichten die anderen CPUs in den Scheduler (per IPI) zwingt. Weil so würde die anderen CPUs erstmal bis zum Ende der Zeitscheibe arbeiten und dann feststellen das es neue Threads mit höherer Priorität gibt (da wären wir dann wieder bei Scheduling-Strategien).

Wenn pro IRQ gleich mehrere Threads erstellt/geweckt werden müssen, was bei IRQ-Sharing ja leider gegeben ist, dann ergibt es natürlich Sinn diese mehreren Threads möglichst schnell auf mehrere CPUs zu verteilen aber dazu würde es doch eigentlich reichen wenn man die Restzeitscheibe der anderen CPUs auf 0 setzt so das diese direkt in den Scheduler gehen (so als wäre dort ein Yield aufgerufen worden). Da man auf x86 ja auch immer an die anderen local-APICs ran kommt sollte das doch kein Problem sein. Für echte IPIs sehe ich noch immer keinen Grund, von dem TLB-Flush bei x86 mal abgesehen.


Grüße
Erik

[FlashBurn]

Aber CPUID liefert wimre nur eine physische CPU-Position, in der Art von Sockel/Core/Thread, und keine lineare Nummer, oder?

Weiß ich gerade auch nicht, aber braucht man die CPU-Nummer im UserSpace? Als Index für ein Array kannst du es schonmal nicht benutzen, denn die CPU könnte ja, während du den Index benutzt, gewechselt werden. Von daher wird ja z.B. beim Slab-Allocator im UserSpace die Thread-ID für sowas genommen.

Ich denke da z.B. an den CPU-lokalen Slot-Mechanismus eines SLAB-Allocators (auch im User-Mode) für den es essenziell wichtig ist möglichst performant an die CPU-Nummer zu kommen und auch das diese linear durchgezählt ist damit man eben die zugehörigen Datenstrukturen in einem simplen und schnellen Array ablegen kann.

Richtig, da war ja was Genau dafür nutze ich das ja auch.

Schon klar aber eigentlich gibt es doch nur 2 Quellen für neue Threads (die dann potentiell eine höhere Priorität haben können): einmal HW-IRQs und dann der CreateThread()-Syscall.

Es gibt noch einen 3. Grund, nämlich wenn ein Thread "aufgeweckt" wird, vom Schlafen oder vom Warten (z.B. Semaphore).

falls auf einer anderen CPU ein Thread mit einer niedrigeren Priorität läuft dann wird der Scheduler das spätestens am Ende von dessen Zeitscheibe merken

Ich weiß nicht wie lange deine Zeitscheiben so sind, aber wir reden da schon von mehreren ms und wenn du dann Audio und Video machst, könnte das schon zu dem Problem führen was ich ja unter Windows habe (knacksen im Sound und Bildstocken, auf nem QuadCore).

Das ist etwas was IMHO nur dann Sinn ergibt wenn jede CPU eine eigene runnable-Liste hat und der übergeordnete Scheduler die Last mal wieder fair über alle CPUs verteilen muss

Der Vorteil einer globalen runnable-Liste liegt für mich genau da, dass immer die Threads mit der höchsten Priorität laufen. Wenn ich das da auch nicht umsetze, kann ich ja gleich mehrere Listen (pro CPU eine) nehmen (was ich ja später auch noch vor habe).

Hm, darüber hab ich noch gar nicht wirklich nachgedacht, eigentlich bin ich der Meinung keine Rendez-Vous-Punkte zu benötigen aber das mit dem Panic erscheint mir dann doch wichtig. Beim normalen Shutdown wollte ich es eigentlich so machen das alle normalen Prozesse beendet werden und dann auch die ganzen Treiber entladen werden (wobei auch die Dateisysteme entmountet werden) und zum Schluss der init-Prozess einfach das Netzteil abschaltet, meinem OS-Kernel und der innersten Personality will ich gar nicht die Fähigkeit zum kontrollierten Abschalten geben.

Ich habe für sowas ne STOP-IPI. Damit kann man entweder alle, außer der sendenden, CPUs anhalten und kann halt z.B. nen kontrollierten Panic machen oder diese eine CPU den PC runterfahren lassen.

Wenn pro IRQ gleich mehrere Threads erstellt/geweckt werden müssen, was bei IRQ-Sharing ja leider gegeben ist, dann ergibt es natürlich Sinn diese mehreren Threads möglichst schnell auf mehrere CPUs zu verteilen aber dazu würde es doch eigentlich reichen wenn man die Restzeitscheibe der anderen CPUs auf 0 setzt so das diese direkt in den Scheduler gehen

Das halte ich ersten für Overhead (da ich durch eine Liste durchgehen muss) und zweitens, desto länger die Liste ist, desto schneller ist eine IPI-Nachricht. Dann kommt noch hinzu, dass es bei mir eher schwierig wird auf den APIC der anderen CPUs zu zugreifen (geht das überhaupt, dazu müsste man mindestens die physikalische Adresse der einzelnen APICs unterschiedlich setzen, aber ich glaube dass das trotzdem nicht geht).

[kevin]

Praktisch schon, theoretisch solltest du nicht darauf bauen. "Problem" ist, falls ein Kern defekt oder was weiß ich nicht ist, hat er trotzdem seine Nummer. Du hast ja z.B. bei ACPI eine Liste mit lokalen APICs und dort ist ja jedes Mal nen Flag ob die CPU in Ordnung ist. Praktisch fällt mir kein Szenario ein wo das mal vorkommen sollte, aber theoretisch ist es halt so.

Wenn ich mich nicht täusche, hat Homix letztens erzählt, dass er auf seinem System nur jeden zweiten Index genutzt hat, weil bei seiner CPU das Hyperthreading deaktiviert ist.

[FlashBurn]

Wenn ich mich nicht täusche, hat Homix letztens erzählt, dass er auf seinem System nur jeden zweiten Index genutzt hat, weil bei seiner CPU das Hyperthreading deaktiviert ist.

Wäre bei mir auch kein Problem, da ich die ID´s selbst vergebe. Mein SMP-Startup Code serialisiert die Ausführung des Init Codes der CPUs und da wird einfach der Wert von nem Counter genommen. Von daher sollte man sich darüber keinen Kopf machen.

[Svenska]

Aber CPUID liefert wimre nur eine physische CPU-Position, in der Art von Sockel/Core/Thread, und keine lineare Nummer, oder?

Weiß ich gerade auch nicht, aber braucht man die CPU-Nummer im UserSpace?

Wenn man einen Prozess/Thread auf eine CPU festpinnen können möchte, muss man die CPU eindeutig identifizieren können. Von daher wäre das schon sinnvoll.

[FlashBurn]

Wenn man einen Prozess/Thread auf eine CPU festpinnen können möchte, muss man die CPU eindeutig identifizieren können. Von daher wäre das schon sinnvoll.

Das könnte man ja per Syscall lösen, aber ich stehe diesem Festpinnen eher skeptisch gegenüber. Wozu soll das gut sein, außer um Multithreading-Probleme zu beseitigen und dass ist aus meiner Sicht der falsche Weg dafür.

[Svenska]

Wenn du einen Prozess auf eine CPU festpinnst und alle anderen Prozesse von dieser CPU entfernst, dann hast du plötzlich die Möglichkeit, weiche Echtzeitanforderungen zu erfüllen. Außerdem kann man durch das Festpinnen den Scheduler entlasten.

[Jidder]

Und der Thread wandert dann nicht zwischen den CPUs (und der Inhalt der Caches mit ihm).

[FlashBurn]

Wenn du einen Prozess auf eine CPU festpinnst und alle anderen Prozesse von dieser CPU entfernst, dann hast du plötzlich die Möglichkeit, weiche Echtzeitanforderungen zu erfüllen.

Hmm, ich sage jetzt mal (ohne konkrete Erfahrung zu haben), das muss durch den Scheduler und einer geeigneteten Wahl der Thread-Priorität zu regeln sein.

Außerdem kann man durch das Festpinnen den Scheduler entlasten.

Meinen (einfachen/primitiven) Scheduler würde es eher noch komplexer machen und ihn nicht wirklich entlasten (was meinst du damit genau?).

Und der Thread wandert dann nicht zwischen den CPUs (und der Inhalt der Caches mit ihm).

Auch das sollte Aufgabe des Schedulers sein. Genau dieses Argument kann ich nur für Single-Threaded Anwendungen gelten lassen, weil wenn wir die Caches optimal ausnutzen wollen, dann sollten alle Threads auf der selben CPU laufen, was wieder Multithreading ad absurdum führen würde. Wimre sind die Caches beim Bulldozer pro "Dual"-Core gleich (was eins der Probleme unter Windows ist) und damit wäre das nicht so schlimm.

Zumal wir wieder sehr zum Thema Scheduling-Strategien abtriften Und ich bin immer noch nicht wirklich vom Festpinnen überzeugt. Wieviel macht denn der Cache aus und wieviel kann ein guter Scheduler retten?

[Svenska]

Ich hab mal als Faustregel gelesen, dass man einen RAM-Zugriff so behandeln sollte, wie man früher einen HDD-Zugriff für Swap behandelt hatte, weil es so extrem viel langsamer ist als über den Cache zu gehen. Das heißt, dass Cache extrem wichtig ist.

Und du kannst einen optimal genialen ultimativ komplexen Scheduling-Algorithmus haben und ich behaupte, dass er für gewisse Verteilungen äußerst schlecht performt. In dem Fall ist es sinnvoll, ein bestimmtes Verhalten erzwingen zu können. Das wird dich zwar auch nicht überzeugen, aber dafür ist es dein Betriebssystem.

Ich mag es nicht, wenn ein OS alles besser weiß als ich und mir die Möglichkeiten nimmt, darauf einwirken zu können. Selbst dann, wenn ich es im Normalfall nie tun werde.

[FlashBurn]

Ich hab mal als Faustregel gelesen, dass man einen RAM-Zugriff so behandeln sollte, wie man früher einen HDD-Zugriff für Swap behandelt hatte, weil es so extrem viel langsamer ist als über den Cache zu gehen. Das heißt, dass Cache extrem wichtig ist.

Daraus lese ich heraus, des es also Sinn macht den Speicherverbrauch von Software eher zu verringern als zu vergrößern Weil so ist das gewünschte ja eher im Cache.

Und du kannst einen optimal genialen ultimativ komplexen Scheduling-Algorithmus haben und ich behaupte, dass er für gewisse Verteilungen äußerst schlecht performt. In dem Fall ist es sinnvoll, ein bestimmtes Verhalten erzwingen zu können. Das wird dich zwar auch nicht überzeugen, aber dafür ist es dein Betriebssystem.

Ich bin der Meinung, dass der genial ultimativ komplexe Scheduling-Algo so lange braucht, dass es wieder keinen Sinn macht ihn zu benutzen Und ja, ich mag das mit dem Festpinnen nicht. Macht die Sache mit dem Scheduler eher komplexer. Wieso ist da KISS nicht in Ordnung?

Ich mag es nicht, wenn ein OS alles besser weiß als ich und mir die Möglichkeiten nimmt, darauf einwirken zu können. Selbst dann, wenn ich es im Normalfall nie tun werde.

Ist das nicht Over-engineering?

[erik.vikinger]

Hallo,

Weiß ich gerade auch nicht, aber braucht man die CPU-Nummer im UserSpace?

Ich bin mir da auch nicht ganz sicher ob es abseits eines SLAB-Allocators noch andere Dinge gibt die auch im User-Mode von der CPU-Nummer abhängen aber das alleine war für mich Grund genug dem User-Space eine lineare und eine physische CPU-Nummer per Befehl anzubieten (ich nutze dazu den normalen Befehl der die lokalen Controll-Register, mein MSR-Äquivalent, liest und erlaube dem User-Mode genau diese 2 Werte).

Als Index für ein Array kannst du es schonmal nicht benutzen, denn die CPU könnte ja, während du den Index benutzt, gewechselt werden. Von daher wird ja z.B. beim Slab-Allocator im UserSpace die Thread-ID für sowas genommen.

Dem kann ich ja glücklicherweise vorbeugen indem ich es erlaube das auch der User-Mode (ohne Kernel-Mitwirkung) für kurze und begrenzte Zeit die INTs komplett abschalten kann, was auch das Ablaufen der Zeitscheibe hinausschiebt. Somit kann ich selbst im User-Mode die aktuelle CPU-Nummer für den SLAB-Allocator nutzen, die Thread-ID ist da IMHO völlig ungeeignet da diese eher zufällig ist (auf jeden Fall nicht linear numeriert), bei jedem neuen Thread auch eine neue Thread-ID vergeben wird und es vor allem sehr viel mehr Threads in einem Prozess als CPUs geben kann.

Es gibt noch einen 3. Grund, nämlich wenn ein Thread "aufgeweckt" wird, vom Schlafen oder vom Warten (z.B. Semaphore).

Das Aufwecken ist so ähnlich wie das neu Erstellen und lässt sich auf jeden Fall in die 2 Kategorien einsortieren. Entweder wird durch einen IRQ geweckt (z.B. wenn der Timer ein Event triggert auf das bereits ein Thread wartet) oder es wird durch eine Software-Aktion ausgelößt (so wie auch Dein Beispiel mit dem Freigeben eines Semaphors und gerade hier kann ja im release() geprüft werden ob ein Thread mit höherer Priorität als der aktuelle wartet und wenn ja dann wird dieser sofort auf die aktuelle CPU geholt und der der gerade den Semaphor freigegeben hat kommt in die runnable-Liste).

Ich weiß nicht wie lange deine Zeitscheiben so sind, aber wir reden da schon von mehreren ms und wenn du dann Audio und Video machst, könnte das schon zu dem Problem führen was ich ja unter Windows habe (knacksen im Sound und Bildstocken, auf nem QuadCore).

Ja, meine Zeitscheiben sollen auch mehrere ms lang sein (ich dachte so an 10 ms bis etwa 20 ms) und, ja, das ist keine harte Echtzeit mehr. Normalerweise sollten die SW-Buffer bei Audio und Video deutlich mehr als 100 ms überbrücken können aber ich weiß auch das man im professionellen Umfeld auch Applikationen hat wo möglichst kurze Latenzen und damit auch kleine Buffer benutzt werden, wer sowas benötigt benötigt eben auch ein passendes OS oder das OS bietet die Möglichkeit spezielle Scheduler-Features anzuschalten (wie z.B. das bei neuen Threads immer eine Optimierung über alle CPUs gefahren wird) was dann zwar mehr CPU-Leistung kostet aber eben auch kürzere Latenzen für die wichtigen Dinge ermöglicht (die weniger wichtigen Dinge werden dafür noch stärker verdrängt).

Der Vorteil einer globalen runnable-Liste liegt für mich genau da, dass immer die Threads mit der höchsten Priorität laufen.

Das sehe ich ganz genauso, nur ist eben eine Frage wie schnell dieses automatische Gleichgewicht sein soll. Hier ist es eben so das wenn man kürzere Latenzen haben will (vor allem auch im Worst-Case der ja sonst bis zu einer kompletten Zeitscheibe dauern kann) das man dafür zusätzliche CPU-Leistung opfern muss.

Ich habe für sowas ne STOP-IPI. Damit kann man entweder alle, außer der sendenden, CPUs anhalten und kann halt z.B. nen kontrollierten Panic machen oder diese eine CPU den PC runterfahren lassen.

Also über die Kernel-Panic hab ich mir noch nicht allzu genau nen Kopf gemacht (steht jetzt aber auf meiner ToDo-Liste)  aber das Runterfahren des PC (inklusive Ausschalten) soll bei mir eigentlich die User-Mode-Personality machen (also der init-Prozess).

Das halte ich ersten für Overhead (da ich durch eine Liste durchgehen muss) und zweitens, desto länger die Liste ist, desto schneller ist eine IPI-Nachricht.

Nö, ich würd einfach die nächsten X CPUs in den Scheduler zwingen, wobei X die Anzahl der neuen Threads ist welche eventuell noch einen kleinen Angstfaktor dazu bekommt. Das ist O(n), genauso wie das Verschicken von X IPIs.

dass es bei mir eher schwierig wird auf den APIC der anderen CPUs zu zugreifen (geht das überhaupt, dazu müsste man mindestens die physikalische Adresse der einzelnen APICs unterschiedlich setzen, aber ich glaube dass das trotzdem nicht geht).

Ich kenne mich bei x86 ja nicht mehr so gut aus aber wimre hat jeder APIC (auch die lokalen) eine individuelle physische Adresse, es gibt nur die zusätzliche Möglichkeit das von einer CPU aus der eigene local-APIC über eine zusätzliche physiche Alias-Adresse erreichbar ist. Diese zusätzliche Alias-Adresse ist auch nicht von außerhalb der CPU nutzbar, so das die nicht z.B. von einem PCI-Gerät benutzt werden kann.

Wenn ich mich nicht täusche, hat Homix letztens erzählt, dass er auf seinem System nur jeden zweiten Index genutzt hat, weil bei seiner CPU das Hyperthreading deaktiviert ist.

Das ist zwar doof aber auch kein Beinbruch wenn dadurch nur jeder zweite Eintrag in einem Array, das üblicherweise pro Element nur ein paar Controll-Variablen und Pointer enthält, ungenutzt bleibt. Es wäre aber auch sehr schön wenn sich in solchen Situationen das BIOS besser verhalten würde.

Wenn du einen Prozess auf eine CPU festpinnst und alle anderen Prozesse von dieser CPU entfernst, dann hast du plötzlich die Möglichkeit, weiche Echtzeitanforderungen zu erfüllen.

Das festpinnen mag sicher gut funktionieren aber ich bin mir nicht sicher ob es auch Möglichkeiten gibt alle anderen Thread von dieser CPU zu verbannen. Dabei entstehen IMHO einige Probleme. Was ist wenn dieser eine Thread gerade blockiert? Bleibt die CPU dann unbenutzt? Geht die dann in einen Stromsparzustand (was eventuell längere Aufwachzeiten und damit Latenzen verursacht)? Wie viele CPUs in einem System kann man den ruhigen Gewissens frei räumen? Ich persönlich würde maximal die Hälfte zulassen und das auch nur wenn mindestens 4 CPUs verfügbar sind. Wenn dieser spezielle Thread z.B. einen synchronen IPC-Vorgang initiiert wäre es doch praktisch wenn der Thread der diesen IPC bearbeitet dafür so lange die CPU haben könnte, schon damit die zu bearbeitenden Daten auch im richtigen Cache bleiben. Ich bin zwar auch der Meinung das festpinnen eine interessante Option darstellt aber ich sehe noch einige Probleme die gelöst werden müssen damit das auch in der Praxis eine wirklich zufriedenstellende Angelegenheit wird.

Ich gebe Dir auf jeden Fall recht das zu häufiges wechseln der CPU eher kontraproduktiv ist, wegen dem Umladen der Caches obwohl das auch erst auf Mehr-Sockel-Systemen zum Problem wird (innerhalb einer CPU sind die Cache-to-Cache-Transfers ziemlich schnell und bei Intel auch gar nicht nötig weil der L3-Cache ja "inklusive" ist).

Außerdem kann man durch das Festpinnen den Scheduler entlasten.

Also das sehe ich noch nicht.

Ich mag es nicht, wenn ein OS alles besser weiß als ich und mir die Möglichkeiten nimmt, darauf einwirken zu können. Selbst dann, wenn ich es im Normalfall nie tun werde.

Auch hier kann ich Dir uneingeschränkt zustimmen (und betrachte sowas auch nicht als Over-Engineering) aber ob das Festpinnen wirklich eine gute Lösung darstellt wage ich zu bezweifeln. Aus meiner Sicht könnte es eine gute Lösung sein wenn man den Scheduler zwingt nach jeder Änderung der Anzahl aktiver Threads oder der Priorität eines aktiven Threads die optimale Verteilung über alle CPUs neu zu berechnen (also den großen Scheduler aufzurufen), das kostet zwar einiges an zusätzlicher CPU-Leistung kann aber bestimmt etwas helfen das die wichtigen Jobs auch immer eine CPU abbekommen. Wobei der große Scheduler natürlich auch aufpassen muss das er Thread nur möglichst selten von einer CPU auf eine andere Wechselt. Auf meiner Plattform habe ich vor die maximale Aufrufhäufigkeit des großen Schedulers mit HW-Hilfe zu begrenzen so das wenn z.B. ein Thread kurz erstellt wird aber recht schnell wieder verschwindet (z.B. ein IRQ-Handler-PopUp-Thread) das der große Scheduler eventuell gar nichts tut weil sich die große Gesamtsituation nicht geändert hat. Diese Maximal-Frequenz könnte man signifikant erhöhen wenn z.B. eine Applikation explizit ein besseres Echtzeit-Verhalten anfordert (das wäre aus meiner Sicht eine sinnvolle Stellschraube die sicher auch einiges bewirken kann und wenn die Applikation auch genau weiß welche Latenzen sie akzeptieren kann könnte man das OS auf genau diesen Wert trimmen so das eben nicht zu viel zusätzliche CPU-Leistung für sowas geopfert wird).


Grüße
Erik

[Svenska]

Festpinnen ist meistens keine gute Lösung, aber es bietet eine Möglichkeit, um auf einen eventuell schlecht oder fehlerhaft funktionierenden Automatismus einzuwirken. Den Automatismus zu fixen ist die bessere Lösung, aber nicht immer möglich oder praktikabel.

Und FlashBurn: Ich glaube, du hast das KISS-Prinzip nicht so richtig verstanden.

[FlashBurn]

Ja, meine Zeitscheiben sollen auch mehrere ms lang sein (ich dachte so an 10 ms bis etwa 20 ms)

Was genau meinst du eigentlich mit Zeitscheibe, weil man da ja schon zw. periorischen Timer-IRQs und One-Shot-IRQs unterscheiden muss. Denn ich habe im Mom glaube eine max. Zeitscheibe für einen Thread von 62ms. Wenn du bei einem periodischen IRQ eine Zeitscheibe von 1ms hast, könnte man damit noch leben.

Nö, ich würd einfach die nächsten X CPUs in den Scheduler zwingen, wobei X die Anzahl der neuen Threads ist welche eventuell noch einen kleinen Angstfaktor dazu bekommt. Das ist O(n), genauso wie das Verschicken von X IPIs.

Der Punkt ist, das versenden einer IPI Nachricht um alle CPUs in den Scheduler zu zwingen ist nicht O(n), sondern O(1). Denn du versendest genau eine Nachricht. Genau ein paar CPUs in den Scheduler zu zwingen ist hingegen wieder O(n). Obwohl man auch das durch geschickten Einsatz einiger APIC Features bestimmt auf O(1) drücken kann.

Ich kenne mich bei x86 ja nicht mehr so gut aus aber wimre hat jeder APIC (auch die lokalen) eine individuelle physische Adresse

Nope, sind standardmäßig alle an die selbe Adresse gemappt. Wäre aber mal interessant zu wissen ob man durch verschiedene Adressen an die APICs der anderen CPUs ran kommt, aber da sehe ich ohnehin keinen Sinn drin.

und betrachte sowas auch nicht als Over-Engineering

Um ein wenig zu sticheln, also ist das jetzt doch Abhängig von der Sichtweise

Den Automatismus zu fixen ist die bessere Lösung, aber nicht immer möglich oder praktikabel.

Das KISS-Prinzip entstammt ursprünglich dem Bereich der Informatik. Als Designprinzip beschreibt es im Gegensatz zu einer Problemlösung in der Form eines Workarounds die möglichst einfache, minimalistische und leicht verständliche Lösung eines Problems, welche meistens als optimal angesehen wird.

Festpinnen ist also ein Workaround und ist laut dieser Definition nicht KISS.

Zumal man an dieser Definition auch schön sieht, dass KISS sehr wohl im Auge des Betrachters liegt:

leicht verständliche Lösung eines Problems, welche meistens als optimal angesehen wird

Also leicht verständlich ist mehr als nur subjektiv und "meistens" hilft da auch nicht wirklich

[erik.vikinger]

Hallo,

Was genau meinst du eigentlich mit Zeitscheibe

Das ist bei mir die Zeit die ein Thread jedes mal neu zugewiesen bekommt wenn er vom Scheduler auf eine CPU geladen wird, so lange kann ein Thread maximal laufen bevor wieder der Scheduler dran kommt. Meine CPUs haben alle einen eigenen Zeitscheiben-Counter (ein simpler Down-Counter mit fester Frequenz) der bei Ablauf der Zeit eine Yield-Exception für die eigene CPU auslöst, das entspricht quasi einem One-Shot-Timer. Fürs erste möchte ich den Wert, der vom Scheduler in diesen Timer geladen wird, als fest deklarierte Konstante realisieren aber später kann ich mir vorstellen das dieser Wert eventuell von der Priorität des jeweiligen Threads abhängt. Der richtige Timer, den es nur einmal gibt (und dem x86-HPET sehr ähnlich ist), wird bei mir nicht für die Zeitscheiben benutzt (schon allein deswegen weil er nicht eine bestimmte sondern immer nur eine zufällige CPU unterbrechen kann, der Timer-IRQ also nur sehr selten genau die CPU erreicht auf der der Thread läuft dessen Zeitscheibe gerade abgelaufen ist).

Der Punkt ist, das versenden einer IPI Nachricht um alle CPUs in den Scheduler zu zwingen ist nicht O(n), sondern O(1).

Okay, das wusste ich nicht. Das ist dann natürlich ein Argument für die IPIs.

Nope, sind standardmäßig alle an die selbe Adresse gemappt.

Um ehrlich zu sein glaube ich das nicht so wirklich, das erscheint mir irgendwie arg daneben, selbst für x86-Verhältnisse.

Um ein wenig zu sticheln, also ist das jetzt doch Abhängig von der Sichtweise

Das sehe ich anders. Es ist eben absolut unmöglich einen Automatismus zu schaffen der unter allen Bedingungen ein optimales oder wenigstens befriedigendes Ergebnis liefert. Gerade deswegen ist es IMHO eine sinnvolle Idee wenn das OS den Programmen ein paar Stellschrauben anbietet damit diese den Automatismus zumindest etwas auf die Sprünge helfen können.

Also Workarounds mag ich persönlich auch grundsätzlich nicht, trotzdem kann (nicht muss) die Umsetzung eines Workarounds durchaus dem KISS-Prinzip entsprechen. Es kann auch sein das eine echte Problemlösung zu komplex oder zu aufwendig ist so das ein Workaround durchaus zu einer insgesamt akzeptablen Lösung wird.


Grüße
Erik