Thema: aktivieren des Kernel bei SMP (beim booten)

[rizor]

Hallo Svenska,

ich glaube, dass deine Art des Schedulings sehr unperformant ist, da im ungünstigsten Fall alle APs Idle sind.
Für mich ist ein Scheduler etwas, das entscheidet auf welcher CPU welcher Task zu welcher Zeit läuft.
Mein Scheduler arbeitet so, dass er so geschrieben ist, dass jede CPU den Code bedenkenlos zu jeder Zeit ausführen kann (also Thread-safe).
Falls nun eine CPU nichts zu tun hat, versucht sie sich von den anderen CPUs (die gerade arbeiten) Tasks zu holen, damit sie wieder Arbeit bekommt.
Falls das nicht funktioniert, springt sie in den Idle-Zustand.
Außerdem gibt es noch einen Kernel-Thread, der in regelmäßigen Abständen sich die verschiedenen Listen anschaut und versucht eine gleichmäßige Verteilung zu erreichen.

An sich gibt es diesen Scheduler schon unter Linux (CFS), nur in einer sehr viel ausgefeilteren Art

Gruß,
rizor

[erik.vikinger]

Hallo,

Ich dachte, dass eine CPU, nachdem ihre Zeitscheibe abgelaufen ist, einfach aus einer CPU-eigenen Liste die nächste Aufgabe holt und diese abarbeitet. (Eventuell sind es auch mehrere Listen, je nach Priorität.)

Aufgabe des Schedulers ist es, diese Listen mit Inhalt (und Aufgaben zu füllen). Das heißt, wenn eine CPU keine Aufgaben in ihrer Liste findet, dann ruft sie den Scheduler auf, sofern er noch nicht läuft.

Aha, jetzt verstehe ich was Du meinst. Für Dich ist also der Scheduler die Komponente welche als übergeordnete Kontrollinstanz die Thread-Listen der einzelnen CPUs pflegt. In meinem derzeitigen Konzept habe ich nur eine globale (nach Priorität sortierte) Thread-Liste aus der sich alle CPUs bedienen wenn sie denn wieder etwas neues brauchen, also wenn vom aktuellem Thread die Zeitscheibe abgelaufen ist (und dieser wieder hinten an die Thread-Liste kommt) oder wenn in irgendeinem Syscall der aufrufende Thread blockiert werden muss und der Syscall eben kein IRET macht sondern den Scheduler aufruft und dieser dann einen neuen Thread holt und ihn auf die aktuelle CPU lädt (und dann ein IRET macht). Da diese Liste niemals leer sein darf gibt es idle (der hat mindestens so viele Threads wie CPUs da sind) und dessen Threads blockieren nie.

Mir ist klar das dieses Konzept ziemlich primitiv ist und sich viele nützliche/wichtige Features (wie Affinität oder Gruppierung) damit nicht realisieren lassen.

Läuft er bereits auf einer anderen CPU, macht die CPU die Idle-Schleife.

Damit dürfte ich bei meiner CPU-Architektur ein Problem haben da die CPU ja nicht in den User-Mode wechseln kann wenn es keinen runnable Thread gibt muss sie im Kernel-Mode busy-waiting auf den Haupt-Scheduler machen (pure Energieverschwendung) oder sich selbst abschalten (um Energie zu sparen) und dann kann sie wieder nur von einer anderen CPU eingeschaltet werden. Lösen könnte man das damit das jede CPU einen Thread von idle individuell zugewiesen bekommt und diesen Thread immer dann ausführt wenn die lokale Liste leer ist so das der dann die CPU per HLT zum Energie sparen anhält aber die CPU z.B. bei einem IRQ sofort aufwachen kann und der Kernel-IRQ-Handler eine asynchrone IPC-Nachricht generiert und für diese einen PopUp-Thread erstellt der dann sofort auf der aktuellen CPU los laufen kann.

Aber das wären alles Zukunftspläne denn einen ordentlichen Scheduler habe ich frühestens für eine spätere Release meines Kernels angedacht. Dann kann ich mir noch mal richtig Gedanken über dieses Thema machen. Die Idee von rizor macht auf mich auch einen recht interessanten Eindruck.


Grüße
Erik

[Svenska]

Auf welcher CPU soll denn der Scheduler deiner Meinung nach laufen? Und wie willst du bei dieser Art Verteilung sicher stellen, das auch ein neuer Thread der eine höhere Priorität hat als alle anderen gleich an die Reihe kommt? Wie willst du überhaupt die Threads vernünftig verteilen?

Der Scheduler wird immer auf der CPU ausgeführt, die als erste nichts zu tun hat.

Die Priorisierung läuft dadurch, dass du in die Listen ja nicht unbedingt "A, B, C, D" eintragen kannst, sondern auch "A, B, A, C, A, B". Der ungünstigste Fall ist demnach wirklich der, dass alle CPUs im Leerlauf sind; das ist aber ein Sonderfall. Denn der Scheduler sieht ja, dass er keine Aufgaben mehr an irgendwelche CPUs verteilen kann und führt dann ebenfalls die Idle-Schleife aus.

Falls nun eine CPU nichts zu tun hat, versucht sie sich von den anderen CPUs (die gerade arbeiten) Tasks zu holen, damit sie wieder Arbeit bekommt.

Eventuell wechselst du damit einen Task von einer CPU auf eine andere CPU, der dadurch große Performance-Nachteile bekommt, weil der CPU-lokale Cache nicht mehr benutzt werden kann und die entsprechenden Cache-Lines erst teuer in den RAM geschrieben werden müssen. Da musst du aufpassen.

Läuft er bereits auf einer anderen CPU, macht die CPU die Idle-Schleife.

Damit dürfte ich bei meiner CPU-Architektur ein Problem haben da die CPU ja nicht in den User-Mode wechseln kann wenn es keinen runnable Thread gibt muss sie im Kernel-Mode busy-waiting auf den Haupt-Scheduler machen (pure Energieverschwendung) oder sich selbst abschalten (um Energie zu sparen) und dann kann sie wieder nur von einer anderen CPU eingeschaltet werden.

Andersrum: Wenn einer CPU die Einträge in der Liste ausgehen, ruft sie die Einstiegsfunktion in den Scheduler auf.

Diese Einstiegsfunktion schaut nach, ob ein Scheduler bereits läuft und wenn er dies tut, kriegt die CPU die Idle-Schleife verpasst (die die CPU u.U. abschaltet).

Die CPU, auf der der Scheduler selbst läuft, darf sich natürlich nicht abschalten, wenn sie nur per CPU wieder aufgeweckt werden kann (müsste dann Busy-Waiting machen), aber der Scheduler darf in diesem Sonderfall ja auch gerne einen Alarm einstellen, nach dem er per Interrupt wieder geweckt werden möchte. Der Interrupt muss dann zwingend auch die CPU mit dem Scheduler aufwecken (das sollte sich lösen lassen) und die weckt dann alle CPUs wieder auf, die jetzt etwas Arbeit vertragen könnten. Müssen ja nicht alle sein.

Es gibt also an sich keinen Idle-Task mit einem Thread je CPU, sondern die Idle-Schleife ist ein spezieller Codepfad im Scheduler, der durchlaufen wird, wenn es nichts zu tun gibt.

Das meinte ich mit "aktiver Scheduler". Das aktive Verteilen von Aufgaben auf CPUs. Das einzige unelegante an diesem Konzept ist der Umgang mit spontanen Ereignissen. Da der Scheduler unter Last erst aufgerufen wird, wenn die erste CPU alle ihre anstehenden Tasks erfüllt hat, steigt die Latenz extrem an. Das lässt sich aber vermeiden, indem du die Liste auf n Einträge begrenzt (damit begrenzt du die Latenz auf n*Zeitscheibenlänge) oder in den Abholprozess die Möglichkeit einbaust, dass neue Einträge in die Liste injiziert werden können.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Die Priorisierung läuft dadurch, dass du in die Listen ja nicht unbedingt "A, B, C, D" eintragen kannst, sondern auch "A, B, A, C, A, B".

Dadurch müssen die Listen aber noch länger werden als eh schon.

Eventuell wechselst du damit einen Task von einer CPU auf eine andere CPU, der dadurch große Performance-Nachteile bekommt, weil der CPU-lokale Cache nicht mehr benutzt werden kann und die entsprechenden Cache-Lines erst teuer in den RAM geschrieben werden müssen.

Das kann schon sein aber ich denke die Zeit-Strafe ist schlimmer wenn der Thread auf eine CPU wartet die voll ausgelastet ist (während nebenan sich 2 CPUs langweilen). Außerdem werden die modifizierten Cache-Lines heutzutage nicht mehr in den Speicher geschrieben sondern direkt von der einen CPU an die andere CPU überstellt (so das die dann der neuen CPU gehören).

Diese Einstiegsfunktion schaut nach, ob ein Scheduler bereits läuft und wenn er dies tut, kriegt die CPU die Idle-Schleife verpasst (die die CPU u.U. abschaltet).

Diese idle-Schleife kann bei mir aber nicht Teil des Kernels sein sondern muss im User-Mode laufen also benötige ich doch genügend idle-Threads die eben dann dran genommen werden wenn sonst nichts mehr da ist.

Die CPU, auf der der Scheduler selbst läuft, darf sich natürlich nicht abschalten, wenn sie nur per CPU wieder aufgeweckt werden kann (müsste dann Busy-Waiting machen), aber der Scheduler darf in diesem Sonderfall ja auch gerne einen Alarm einstellen, nach dem er per Interrupt wieder geweckt werden möchte. Der Interrupt muss dann zwingend auch die CPU mit dem Scheduler aufwecken (das sollte sich lösen lassen) und die weckt dann alle CPUs wieder auf, die jetzt etwas Arbeit vertragen könnten.

Wenn eine meiner CPUs abgeschaltet hat dann interessiert diese sich auch nicht mehr für Interrupts o.ä. sondern reagiert nur noch auf ein spezielles Trigger-Signal (das u.a. den Start-IP als Parameter enthalten muss damit die CPU weiß wo sie loslaufen soll). Selbst Reset nützt nichts weil eine CPU ja nach dem Reset automatisch wieder im Shut-Down landet. Das übermitteln von Interrupts an eine bestimmte CPU hab ich nicht vorgesehen, viel mehr soll sich die CPU den Interrupt holen welche gerade den Code mit der niedrigsten Priorität ausführt, der HLT-Befehl stellt dabei den untersten Wert dar so das bevorzugt CPUs unterbrochen werden die gar nichts tun.

Das einzige unelegante an diesem Konzept ist der Umgang mit spontanen Ereignissen. Da der Scheduler unter Last erst aufgerufen wird, wenn die erste CPU alle ihre anstehenden Tasks erfüllt hat, steigt die Latenz extrem an. Das lässt sich aber vermeiden, indem du die Liste auf n Einträge begrenzt (damit begrenzt du die Latenz auf n*Zeitscheibenlänge) oder in den Abholprozess die Möglichkeit einbaust, dass neue Einträge in die Liste injiziert werden können.

Das klingt aber nach einem extremen Hemmschuh. Das möchte ich dann lieber doch nicht haben und bleibe erst mal bei meinem Primitiv-Konzept. Aber vielleicht kann ich ja was einbauen das zumindest dafür sorgt das die Threads nicht nach dem Zufallsprinzip über alle CPUs verteilt werden sondern immer möglichst lange auf der selben CPU bleiben. In Windows-XP ist mir aufgefallen das bei 2 CPUs und nur einen Thread (der gerade voll läuft) beide CPUs zu etwa 50% ausgelastet sind so das ich davon ausgehen muss das der eine Thread wild hin und her gereicht wird.


Grüße
Erik

[FlashBurn]

Ich sehe mit Svenska´s Scheduler noch das Problem das der Scheduler warten muss bis er in eine Liste schreiben darf, wenn gerade die CPU auf ihre Liste zugreift und wenn das dann im worst-Case auf allen CPUs der Fall ist entsteht da ne ganz schöne Zeit.

Das nächste ist, wie schon gesagt die "unerwarteten" Events (eigentlich gibt es doch weit weniger Threads die immer laufen als Threads die immer mal wieder aufgeweckt werden oder auch schnell wieder blockieren) und da dürfet das Konzept dann richtig schlecht sein (lasse mich gerne vom Gegenteil überzeugen) und damit wäre der Scheduler nicht für ein interaktives System geeignet.

Auch gehst du davon aus das du in die Zukunft sehen kannst, wenn du die Threads verteilen willst. Ich meine wozu habe ich Prioritäten wenn auf einer CPU ein Thread mit ner niedriegen Priorität läuft, aber in irgendeiner Liste steckt ein Thread mit hoher Priorität? Dann kann ich doch das Konzept mit den Prioritäten gleich lassen.

Das ist auch der Grund warum ich nichts von per CPU-Listen halte und bisher konnte mich noch keiner vom Gegenteil überzeugen.

[rizor]

Das ist auch der Grund warum ich nichts von per CPU-Listen halte und bisher konnte mich noch keiner vom Gegenteil überzeugen.

Du hast nur ein größeres Problem. Die Skalierbarkeit bei einer Runqueue ist echt grausam. Wenn du ein System mit 128 CPUs hast, prügeln sich unter Umständen 128 CPUs um ein Lock.
Das Problem hat man auf verteilten Listen nicht. Für verteilte Listen muss man dann halt einen Verteiler schreiben, der dafür sagt, dass die CPUs nicht Idle laufen, bzw. nur dann, wenn sowieso niemand was zu tun hat.
Wenn du dir mal den CFS anschaust, der macht genau das mit verteilten Listen und schafft das auch echt gut mit Prioritäten.

Eventuell wechselst du damit einen Task von einer CPU auf eine andere CPU, der dadurch große Performance-Nachteile bekommt, weil der CPU-lokale Cache nicht mehr benutzt werden kann und die entsprechenden Cache-Lines erst teuer in den RAM geschrieben werden müssen.

Das kann schon sein aber ich denke die Zeit-Strafe ist schlimmer wenn der Thread auf eine CPU wartet die voll ausgelastet ist (während nebenan sich 2 CPUs langweilen). Außerdem werden die modifizierten Cache-Lines heutzutage nicht mehr in den Speicher geschrieben sondern direkt von der einen CPU an die andere CPU überstellt (so das die dann der neuen CPU gehören).

Wenn man davon ausgeht, dass die Tasks schon länger nicht mehr liefen, kann es auch gut sein, dass die Daten nicht mehr im Cache liegen (also nicht in dem, der direkt zu der CPU gehört).
Von daher ist das Problem, wahrscheinlich kein ganz so großes, solange man nicht die Tasks migriert, die bis vor kurzem noch liefen.

[FlashBurn]

Für verteilte Listen muss man dann halt einen Verteiler schreiben, der dafür sagt, dass die CPUs nicht Idle laufen, bzw. nur dann, wenn sowieso niemand was zu tun hat.

Aber wie stellst du sicher das immer die Threads laufen die die höchste Priorität haben? Im Endeffekt kann ich mir nicht vorstellen wie du die Threads anständig verteilen willst und wer das machen soll. Kann es passieren das du erst in allen CPU eigenen Listen nachgucken musst ob da Threads drin sind (um dir dann einen Thread rauszunehmen damit der auf deiner CPU laufen kann)? Wo kommen neue Threads hin? Usw.

[rizor]

Für verteilte Listen muss man dann halt einen Verteiler schreiben, der dafür sagt, dass die CPUs nicht Idle laufen, bzw. nur dann, wenn sowieso niemand was zu tun hat.

Aber wie stellst du sicher das immer die Threads laufen die die höchste Priorität haben? Im Endeffekt kann ich mir nicht vorstellen wie du die Threads anständig verteilen willst und wer das machen soll. Kann es passieren das du erst in allen CPU eigenen Listen nachgucken musst ob da Threads drin sind (um dir dann einen Thread rauszunehmen damit der auf deiner CPU laufen kann)? Wo kommen neue Threads hin? Usw.

Das mit den Prioritäten habe ich mir noch nicht genau überlegt.
Die Verteilung übernimmt ein Kernel-Thread, der in regelmäßigen Abständen läuft.
Außerdem bekommen die CPUs, die zu wenig bzw. zu viel Arbeit haben, die Möglichkeit selber die Verteilung zu übernehmen.
Dabei wird dann halt versucht von der am stärksten belasteten CPU Tasks an andere CPUs zu geben.
Erst einmal mache ich es so, dass neue Threads direkt auf die CPU gelegt werden, die sich um die Erstellung gekümmert haben.
Den Rest macht der Dispatcher

[Svenska]

Ich sehe mit Svenska´s Scheduler noch das Problem das der Scheduler warten muss bis er in eine Liste schreiben darf, wenn gerade die CPU auf ihre Liste zugreift und wenn das dann im worst-Case auf allen CPUs der Fall ist entsteht da ne ganz schöne Zeit.

Nicht unbedingt. Der Scheduler wird von der CPU aufgerufen, deren Queue leer ist. Stört also nicht weiter, solange ich nur diese eine CPU mit Daten befülle. Außerdem läuft der Scheduler als ein normaler Thread ab, also innerhalb der Zeitscheibe - und da sind die CPUs entweder mit Aufgaben beschäftigt oder idle.

Auch gehst du davon aus das du in die Zukunft sehen kannst, wenn du die Threads verteilen willst. Ich meine wozu habe ich Prioritäten wenn auf einer CPU ein Thread mit ner niedriegen Priorität läuft, aber in irgendeiner Liste steckt ein Thread mit hoher Priorität? Dann kann ich doch das Konzept mit den Prioritäten gleich lassen.

Im Zeitmittel läuft ein Thread mit höherer Priorität öfter. Du musst einen niederpriorisierten Thread also nicht zwingend direkt von der CPU nehmen, nur weil ein höherpriorisierter Thread vorbeimarschiert. Bei einer CPU heißt das, dass du eine Latenz von einer Zeitscheibeneinheit hast, wenn der höherpriorisierte Thread die Echtzeitpriorität hat.

Ich bin der Meinung, dass ein guter Scheduler nicht billig zu haben ist. Entweder du hast einen relativ primitiven, aber schnellen Scheduler oder du hast einen fairen/guten Scheduler mit eigenem hohen Verbrauch. Mein Vorschlag ist eine Art Mittelweg: Du hast einen Scheduler-Codepfad, der sofort wichtige Ereignisse in die Queue injiziert (wird oft aufgerufen) und du hast einen komplexen, verteilenden Scheduler, der seltener aufgerufen wird (wenn eine Queue endet).

Die Priorisierung läuft dadurch, dass du in die Listen ja nicht unbedingt "A, B, C, D" eintragen kannst, sondern auch "A, B, A, C, A, B".

Dadurch müssen die Listen aber noch länger werden als eh schon.

Nur, wenn du viele verschiedene Prioritätsstufen brauchst.

Das kann schon sein aber ich denke die Zeit-Strafe ist schlimmer wenn der Thread auf eine CPU wartet die voll ausgelastet ist (während nebenan sich 2 CPUs langweilen). Außerdem werden die modifizierten Cache-Lines heutzutage nicht mehr in den Speicher geschrieben sondern direkt von der einen CPU an die andere CPU überstellt (so das die dann der neuen CPU gehören).

Trotzdem wird der Bus belastet und die Kosten sind spürbar. Wenn du sicher bist, dass der Thread "vor kurzem" noch lief und "in ungefähr der nächsten Zeitscheibe" ohnehin wieder dran ist, dann solltest du ihn definitiv nicht migrieren, egal wieviele CPUs noch frei sind. Passiert das allerdings ständig, solltest du doch migrieren. Um sowas zu realisieren, brauchst du aber einen recht komplexen Scheduler, der vor allem einen Gesamtüberblick braucht.

In Windows-XP ist mir aufgefallen das bei 2 CPUs und nur einen Thread (der gerade voll läuft) beide CPUs zu etwa 50% ausgelastet sind so das ich davon ausgehen muss das der eine Thread wild hin und her gereicht wird.

Der Vorteil des Springens auf Mehrkern-CPUs(!) ist eine erhöhte Lebensdauer der CPU: Wenn du einen Kern belastest, wird er wärmer, als wenn er idlet. Wird er wärmer, dehnen die Strukturen sich aus und es gibt thermische Spannungen. Belastest du beide Kerne gleichmäßig, ist der Temperaturgradient über die Fläche kleiner und du belastest die CPU mechanisch weniger.

Ist ein Grund. Ich halte ihn für inzwischen vernachlässigbar.

Aber wie stellst du sicher das immer die Threads laufen die die höchste Priorität haben? Im Endeffekt kann ich mir nicht vorstellen wie du die Threads anständig verteilen willst und wer das machen soll. Kann es passieren das du erst in allen CPU eigenen Listen nachgucken musst ob da Threads drin sind (um dir dann einen Thread rauszunehmen damit der auf deiner CPU laufen kann)? Wo kommen neue Threads hin? Usw.

Du willst nicht immer die höchstpriorisierten Threads laufenlassen (das führt zum Verhungern). Und durch die einzelnen CPU-Listen tingeln, um eine optimale Verteilung zu kriegen, schreit nach Lock-Problemen.

Ein Scheduler verteilt die Threads des Systems präventiv auf die CPUs und analysiert dann, ob er richtig gelegen hat. Das Ziel ist nicht, immer die optimale Verteilung zu bekommen - das ist nicht möglich, weil du sonst vor dem Threadstart eine Codeanalyse durchführen müsstest - sondern du versuchst, ein Standardverhalten zu haben, welches die meisten Fälle hinreichend gut abdeckt und in der Lage ist, schlecht getroffene Sonderfälle nachträglich zu korrigieren.

Der CFS ist natürlich eine schöne Sache, du kannst Prozesse in Gruppen stecken und dann die CPU-Zeit für die Gruppen begrenzen (ähnlich disk-quota) und so weiter. Die Kosten für die Flexibilität sind einerseits, dass der Scheduler selbst sehr komplex ist, andererseits hat er auch nicht den Durchsatz, den ein simpler, kleiner Scheduler hat. Nur brauchst du in den seltensten Fällen den maximalen Durchsatz. Das ist wie mit Echtzeitfähigkeit: Du möchtest hinreichend guten Durchsatz, und bei Echtzeitanwendungen eine hinreichend gute garantierte Latenz.

Ein System, welches garantiert innerhalb von zwei Sekunden auf einen Tastendruck reagiert, ist echtzeitfähig.

[erik.vikinger]

Hallo,

Der Scheduler wird von der CPU aufgerufen, deren Queue leer ist. Stört also nicht weiter, solange ich nur diese eine CPU mit Daten befülle.

Aber es dürfte häufig der Fall zutreffen das sich diese CPU Threads von anderen CPUs holen muss damit eine gleichmäßigere Verteilung erreicht werden kann und dafür müssen dann eben doch die Listen der anderen CPUs gelockt werden. Das könnte z.B. passieren wenn mehrere Prozesse liefen wo jeder mit vielen Threads möglichst viel CPU-Leistung abbekommen wollte und dan ein Teil der Prozesse endet und die restlichen eben wieder neu Verteilt werden müssen. Dazu kommt das man eigentlich auch immer die gewünschte Auslastung der CPUs tracken muss, also wenn ich 4 CPUs habe und darauf 4 Prozesse laufen von denen wieder jeder 4 Threads hat dann sind diese insgesamt 16 Threads ja nicht zwangsläufig symmetrisch über die CPUs verteilt und wenn dann einer der Prozesse endet könnte ja die Situation entstehen das zwar alle CPUs mindestens einen Thread haben der volle CPU-Leistung will (also keine CPU idlen muss) aber eben nicht jede CPU 3 Threads hat so das bei einigen CPUs sich viele Threads (>3) um diese CPU Streiten und bei anderen CPUs sich nur wenige Threads (<3, im Extremfall gar nur einer) streiten müssen. Daher ist es IMHO wichtig das die übergeordnete Instanz auch solche Zustände erkennt.

Außerdem läuft der Scheduler als ein normaler Thread ab, also innerhalb der Zeitscheibe

Das dürfte bei einem minimalistischen Mikro-Kernel (zumindest bei meinem der ja keine eigenen Aktivitäten hat) aber dazu führen das der Scheduler ein User-Mode-Prozess sein muss und dieser für die Informationsbeschaffung und auch die Konfiguration der CPU-Listen eine Menge an Syscalls durchführen muss (also Overhead). Nebst dessen der der Kernel auch ne Weile ohne ihn auskommen können müsste da ja dieser User-Mode-Sheduler eventuell nicht sofort dran kommt. Ich persönlich bin eher der Meinung das der übergeordnete Scheduler Teil des Kernels sein muss und eben immer dann aufgerufen wird wenn sich die Last-Situation geändert hat oder Ungleichgewichte bestimmte Schwellen überschreiten.

Du musst einen niederpriorisierten Thread also nicht zwingend direkt von der CPU nehmen, nur weil ein höherpriorisierter Thread vorbeimarschiert.

Ein Thread mit hoher Priorität entsteht ja nicht aus dem Nichts sondern wird entweder aufgeweckt, neu erstellt oder es wird die Priorität eines Threads geändert. Bei einem stark interaktiv genutzten System sind das IMHO Dinge die recht häufig vor kommen. Wenn man jetzt jedes mal versucht die Threads neu optimal über die CPUs zu verteilen geht da eine Menge Rechenleistung für drauf. Nebst dessen das die Priorität eines Threads nichts darüber aussagt ob dieser überhaupt seine Zeitscheibe gedenkt voll zu nutzen. Der Decoder-Thread in einem Media-Player wird auch eine hohe Priorität haben aber nicht immer seine Zeitscheibe voll aufbrauchen sondern immer nur den Puffer wieder auffüllen (bei einem MP3-Player auf einer heutigen CPU dürfte dieser Thread wohl höchstens ein paar Prozent seiner Zeitscheibe wirklich nutzen). Gerade dieses soziale Verhalten sollte der Scheduler aber auch positiv honorieren obwohl es vielleicht auch sinnvoll sein könnte diesen Thread nur so häufig auf zu rufen das er wenigstens X Prozent seiner Zeitscheibe auch wirklich nutzt damit der Kontext-Switch nicht teurer ist als die eigentliche Arbeit.

Bei einer CPU heißt das, dass du eine Latenz von einer Zeitscheibeneinheit hast, wenn der höherpriorisierte Thread die Echtzeitpriorität hat.

Also das wäre IMHO schon viel zu lang. Da bei einem Mikro-Kernel die IRQ-Handler ja auch ganz normale User-Space-Threads sind wäre ich schon sehr daran interessiert das dieser bei einem IRQ auch sofort dran kommt (falls auf der aktuellen CPU ein Thread mit niedrigerer Priorität läuft und da bei mir IRQs immer an die CPU gehen sollen die gerade den User-Mode-Code mit der niedrigsten Priorität abarbeitet dürfte das sehr häufig zutreffen).

Ich bin der Meinung, dass ein guter Scheduler nicht billig zu haben ist. Entweder du hast einen relativ primitiven, aber schnellen Scheduler oder du hast einen fairen/guten Scheduler mit eigenem hohen Verbrauch.

Das ist (leider) wahr.

Mein Vorschlag ist eine Art Mittelweg: Du hast einen Scheduler-Codepfad, der sofort wichtige Ereignisse in die Queue injiziert (wird oft aufgerufen) und du hast einen komplexen, verteilenden Scheduler, der seltener aufgerufen wird (wenn eine Queue endet).

Wenn der Verteiler nur selten dran kommt dann hast Du oft sehr lange Latenzen auf asynchrone Ereignisse, das wäre IMHO noch nicht einmal für einen Desktop-PC geeignet.

Die Priorisierung läuft dadurch, dass du in die Listen ja nicht unbedingt "A, B, C, D" eintragen kannst, sondern auch "A, B, A, C, A, B".

Dadurch müssen die Listen aber noch länger werden als eh schon.

Nur, wenn du viele verschiedene Prioritätsstufen brauchst.

Der Nice-Wert ist wimre eine 32Bit-Zahl.

Trotzdem wird der Bus belastet und die Kosten sind spürbar.

Stimmt.

Wenn du sicher bist, dass der Thread "vor kurzem" noch lief und "in ungefähr der nächsten Zeitscheibe" ohnehin wieder dran ist, dann solltest du ihn definitiv nicht migrieren, egal wieviele CPUs noch frei sind. Passiert das allerdings ständig, solltest du doch migrieren. Um sowas zu realisieren, brauchst du aber einen recht komplexen Scheduler, der vor allem einen Gesamtüberblick braucht.

Das klingt alles ziemlich komplex (vor allem das mit dem "Gesamtüberblick"), da fürchte ich fast das der Scheduler mehr Zeit für sich selber benötigt als es dauern würde den Thread zu migrieren.

Der Vorteil des Springens auf Mehrkern-CPUs(!) ist eine erhöhte Lebensdauer der CPU: ....

Ich denke das ist auch bei heutigen CPUs nicht unbedingt zu vernachlässigen wenn auch sicher ziemlich abgeschwächt. Aber im Fall von Windows XP ist das IMHO eher einfach ein primitiver Scheduler.

Du willst nicht immer die höchstpriorisierten Threads laufenlassen (das führt zum Verhungern).

Das ist gerade ein Aspekt der mir am CFS sehr gut gefällt, da kommen zwar Threads mit niedriger Priorität nur noch extrem selten dran aber sie müssen wenigstens nicht ganz verhungern (so wie das bei meiner Liste der Fall wäre).

Und durch die einzelnen CPU-Listen tingeln, um eine optimale Verteilung zu kriegen, schreit nach Lock-Problemen.

Anders dürfte sich aber ein vollständiger Gesamtüberblick wohl kaum realisieren lassen.

Ein Scheduler verteilt die Threads des Systems präventiv auf die CPUs und analysiert dann, ob er richtig gelegen hat.

Dazu müsste jede CPU z.B. immer analysieren wie viele Threads sie hat die ihre Zeitscheibe voll aufbrauchen und wenn da ein Ungleichgewicht über die einzelnen CPUs entsteht muss eben wieder korrigiert werden. Gerade dieses Analysieren ist aber eventuell recht rechenintensiv und hat auch immer den Nachteil das sich diese Analyse immer auf die Vergangenheit bezieht.

Der CFS ist natürlich eine schöne Sache, du kannst Prozesse in Gruppen stecken und dann die CPU-Zeit für die Gruppen begrenzen (ähnlich disk-quota) und so weiter.

Ja, auch das Gruppieren ist eine echt tolle Sache des CFS. Das würde z.B. die Gefahr von DoS-Angriffen auf mein IPC-Konzept stark eindämmen indem der PopUp-Thread immer die Gruppe des Client-Threads erbt, so würde z.B. der entsprechende Thread im SATA-Treiber immer noch logisch zu dem Prozess gehören der ursprünglich das fread an den VFS-Service geschickt hat.

Ein System, welches garantiert innerhalb von zwei Sekunden auf einen Tastendruck reagiert, ist echtzeitfähig.

Nicht für mich! Mit so einem System könnte ich hier noch nicht einmal meine überlangen Beiträge verfassen.


Grüße
Erik

[Svenska]

Aber es dürfte häufig der Fall zutreffen das sich diese CPU Threads von anderen CPUs holen muss damit eine gleichmäßigere Verteilung erreicht werden kann und dafür müssen dann eben doch die Listen der anderen CPUs gelockt werden.

Richtig. Wenn der Scheduler aber in einer ganz normalen Zeitscheibe läuft, spielt das keine Rolle - das Lock ist zu diesem Zeitpunkt immer frei.

Außerdem läuft der Scheduler als ein normaler Thread ab, also innerhalb der Zeitscheibe

Das dürfte bei einem minimalistischen Mikro-Kernel (zumindest bei meinem der ja keine eigenen Aktivitäten hat) aber dazu führen das der Scheduler ein User-Mode-Prozess sein muss und dieser für die Informationsbeschaffung und auch die Konfiguration der CPU-Listen eine Menge an Syscalls durchführen muss (also Overhead).

Ja, dass so ein Konzept bei dir nicht geht und reinpasst, sind wir uns immerhin ja einig.

Für mich ist der Kern eines Betriebssystems halt etwas mehr als nur ein rein passiver Service-zur-Verfügung-Steller.

Nebst dessen der der Kernel auch ne Weile ohne ihn auskommen können müsste da ja dieser User-Mode-Sheduler eventuell nicht sofort dran kommt. Ich persönlich bin eher der Meinung das der übergeordnete Scheduler Teil des Kernels sein muss und eben immer dann aufgerufen wird wenn sich die Last-Situation geändert hat oder Ungleichgewichte bestimmte Schwellen überschreiten.

Genau. Und nach einer gewissen Maximalzeit, um bei einem unter Last stehenden System auch noch dranzukommen.

Der Zeitpunkt "wenn eine CPU-Queue leer ist" ist eine Änderung der Lastsituation. Wenn sich die Queues allerdings selbst befüllen (also Ringpuffer), dann würde der Scheduler unter Last niemals drankommen, d.h. neue Prozesse würden niemals scheduled werden. Darum würde ich die maximale Queuetiefe beschränken und dem Scheduler damit Zwangsarbeit verordnen.

Mein Vorschlag ist eine Art Mittelweg: Du hast einen Scheduler-Codepfad, der sofort wichtige Ereignisse in die Queue injiziert (wird oft aufgerufen) und du hast einen komplexen, verteilenden Scheduler, der seltener aufgerufen wird (wenn eine Queue endet).

Wenn der Verteiler nur selten dran kommt dann hast Du oft sehr lange Latenzen auf asynchrone Ereignisse, das wäre IMHO noch nicht einmal für einen Desktop-PC geeignet.

Darum Mittelweg - oder auch Kompromiss. Asynchrone "Ereignisse" werden injiziert, kommen also direkt dran, das benötigt nicht den vollen Scheduler. (Natürlich nur, wenn das Ereignis auch höher priorisiert ist.)

Der richtige Verteiler sollte möglichst selten drankommen, denn er ist teuer. Und asynchrone Ereignisse ohne Priorität sind nicht wichtig. Im Übrigen kann man ja interaktive Tasks bevorzugen (man sieht ja, ob ein Task seine Zeitscheibe immer aufbraucht oder nicht) und eine (leicht) erhöhte Priorität geben.

Das klingt alles ziemlich komplex (vor allem das mit dem "Gesamtüberblick"), da fürchte ich fast das der Scheduler mehr Zeit für sich selber benötigt als es dauern würde den Thread zu migrieren.

Ja. Nur brauchst du zwingend einen Gesamtüberblick, um ein Gesamtsystem auch steuern zu können.

Das andere Extrem ist, dass jede CPU sich steuert und nur sich allein. Damit kriegt man nette Dinge wie CPU-Gruppen aber nicht mehr hin (vgl was ich oben zum CFS schrieb). Alles eine Kompromisslösung zwischen Latenz/Durchsatz/Komfort.

Und durch die einzelnen CPU-Listen tingeln, um eine optimale Verteilung zu kriegen, schreit nach Lock-Problemen.

Anders dürfte sich aber ein vollständiger Gesamtüberblick wohl kaum realisieren lassen.

Darum arbeitet der Scheduler für die Zukunft, nicht für die Gegenwart. Wenn ich durch alle CPUs laufen muss, um den Zustand rauszukriegen, habe ich verloren. Aber wenn ich den Zustand ja vorher bestimmt habe, muss ich es nicht.

Gerade dieses Analysieren ist aber eventuell recht rechenintensiv und hat auch immer den Nachteil das sich diese Analyse immer auf die Vergangenheit bezieht.

Eine Analyse kann sich nur auf die Vergangenheit beziehen, es sei denn, dein Scheduler macht präventiv eine statische Code-Analyse. (Und auch da ist nicht alles möglich.) Da ein Task in der Regel länger als nur eine Handvoll Zeitscheiben läuft, lohnt sich die Analyse meistens trotzdem. Und man muss sie ja auch nicht für jede Zeitscheibe machen.

Da gibt es viele, viele Tuneables.

Ein System, welches garantiert innerhalb von zwei Sekunden auf einen Tastendruck reagiert, ist echtzeitfähig.

Nicht für mich! Mit so einem System könnte ich hier noch nicht einmal meine überlangen Beiträge verfassen.

Was garantiert dir denn dein System so?

Und was garantiert es, wenn du "make -j128" im Kernel machst, dreißig TCP-Streams die Leitung verstopfen, du alle Festplatten parallel auf Fehler prüfst und dann noch eine DVD brennst? Garantiert dir dein System die zwei Sekunden immernoch?

Linux ist (ohne Patches) nicht echtzeitfähig, Windows (außer CE) ebenfalls nicht.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Wenn der Scheduler aber in einer ganz normalen Zeitscheibe läuft, spielt das keine Rolle - das Lock ist zu diesem Zeitpunkt immer frei.

Das trifft nur für die aktuelle CPU zu aber nicht für die anderen. Ob die anderen CPUs gerade einen Kontext-Switch durchführen (und deswegen die jeweils eigene Liste bearbeiten) oder nicht ist purer Zufall, egal ob der Haupt-Scheduler als Teil des Kernels läuft oder als User-Mode-Prozess.

Ja, dass so ein Konzept bei dir nicht geht und reinpasst, sind wir uns immerhin ja einig.

Na immerhin etwas, jetzt müssen wir unsere Übereinstimmungen nur noch wachsen lassen.

Für mich ist der Kern eines Betriebssystems halt etwas mehr als nur ein rein passiver Service-zur-Verfügung-Steller.

Das Du eher aus der Monolithen-Ecke kommst wissen wir ja nun alle. Ich hoffe nur das wir auch ein hübsches Konzept für Mikro-Kernel finden (schließlich ist dass das was hier die Mehrheit bevorzugt).

Der Zeitpunkt "wenn eine CPU-Queue leer ist" ist eine Änderung der Lastsituation. Wenn sich die Queues allerdings selbst befüllen (also Ringpuffer), dann würde der Scheduler unter Last niemals drankommen, d.h. neue Prozesse würden niemals scheduled werden. Darum würde ich die maximale Queuetiefe beschränken und dem Scheduler damit Zwangsarbeit verordnen.

Schon klar, aber wenn sich die Situation längere Zeit nicht mehr geändert hat also ein tolles Programm kontinuierlich alle CPUs voll auslastet und sonst nichts passiert (weil der User wie hypnotisiert den Fortschrittsbalken beobachtet) dann ist IMHO auch kein Big-Scheduler erforderlich (tät ja nur wertvolle CPU-Zeit kosten). Ich denke die Kunst besteht darin einen kleinen lokalen Scheduler zu haben den jede CPU für sich aufruft um den nächsten Thread zu bekommen und ein paar Statistiken zu updaten und dazu einen großen globalen Schduler zu haben der nur dann aufgerufen wird wenn sich der Status-Quo ändert (z.B. wenn beim Aktualisieren der Statistik durch den kleinen Scheduler ein Ungleichgewicht eine gewisse Schwelle übersteigt oder Threads dazu kommen bzw. verschwinden/blockieren). Das Problem ist das diese Ereignisse bei einem stark interaktiv genutzten System sicher sehr häufig sind so das man die Aufruf-Häufigkeit begrenzen muss (für meine Plattform würde mir da auch schon eine passende HW-Lösung einfallen, ach wie gut das ich nicht ein OS für eine starre altertümliche Plattform entwickeln muss).

Im Übrigen kann man ja interaktive Tasks bevorzugen (man sieht ja, ob ein Task seine Zeitscheibe immer aufbraucht oder nicht) und eine (leicht) erhöhte Priorität geben.

Das ist zwar eine gute Idee aber wie viele Threads trifft das? Ich denke es gibt nur ganz wenige Situationen wo man einen kontinuierlichen Fluss an Arbeit hat (mit relativ konstanten Arbeit-pro-Zeit-Wert) wo immer mal wieder etwas zu tun ist, klassisches Beispiel wäre der Decoder-Thread in einem Media-Player. Aber so lange das eher die Ausnahme ist muss man das nicht extra berücksichtigen. Diesen Decoder-Thread kann man auch einfach mit ner hohen Priorität ausstatten um sicher zu stellen das er oft genug dran kommt aber üblicherweise wird man davon nicht sehr viele parallel in einem System haben damit es sich lohnt diese spezielle Klasse an Threads extra zu berücksichtigen. Die überwiegende Mehrheit aller Threads arbeitet so lange bis die Arbeit zu Ende ist oder eine blockierende Aktion ausgeführt wird, ich denke das sind die 2 Fälle die ein Scheduler möglichst gut abdecken muss.

Nur brauchst du zwingend einen Gesamtüberblick, um ein Gesamtsystem auch steuern zu können.

Ach ne, echt? SCNR
Das Problem ist nur das dieser Gesamtüberblick um so teurer wird je größer das Gesamtsystem ist, also der Aufwand wächst mit der Anzahl der CPUs und mit der Anzahl der runnable Threads.

Alles eine Kompromisslösung zwischen Latenz/Durchsatz/Komfort.

"Ein Kompromiss ist die Kunst einen Kuchen so zu schneiden das jeder denkt er hätte das größte Stück!"

Wenn ich durch alle CPUs laufen muss, um den Zustand rauszukriegen, habe ich verloren. Aber wenn ich den Zustand ja vorher bestimmt habe, muss ich es nicht.

Wenn aber alle CPUs ihren Teil vom Überblick selber eintragen prügeln die sich auch alle um diese eine Ressource, an irgendeiner Stelle musst Du einfach in diesen sauren Apfel beißen, da führt kein Weg dran vorbei. Aber man könnte versuchen das die CPUs ihre Last-Situation nur dann melden wenn sie sich auch (wesentlich) geändert hat.
Eine wichtige Frage ist wie man die Lastsituation berechnet, ich würde ja sagen das der prozentuale Verbrauch der Zeitscheibe von allen Threads in der lokalen Run-List als Maßstab taugt (sicher muss da noch die Priorität mit rein gewichtet werden). Da könnte der große Scheduler gezielt Threads migrieren wenn da ein Ungleichgewicht entsteht. Und wenn es nur einen Thread gibt der voll arbeitet (und immer alle Zeitscheiben komplett nutzt) dann würde der große Scheduler wenigstens dafür sorgen das dieser Thread die CPU ganz für sich allein hat und alle anderen Threads auf andere CPUs verteilen.

Da ein Task in der Regel länger als nur eine Handvoll Zeitscheiben läuft, lohnt sich die Analyse meistens trotzdem. Und man muss sie ja auch nicht für jede Zeitscheibe machen.

Es dürfte aber auch einige Threads geben die für ein oder zwei Zeitscheiben gut Arbeit haben und dann wieder länger blockieren bevor wieder ein kleines Stück Arbeit zu erledigen ist (misst, mir fällt da jetzt gar kein Beispiel ein). Auch das Aufwachen und wieder Einschlafen von Threads ist ein wichtiges Ereignis das den großen Scheduler erforderlich machen kann (aber sicher nicht immer muss).

Da gibt es viele, viele Tuneables.

Ja, und mit jedem davon kann man es noch schlimmer machen als es vorher war.

Was garantiert dir denn dein System so?

Eigentlich gar nichts, nicht mal einen Blue-Screen innerhalb eines Quartals.

Und was garantiert es, wenn du "make -j128" im Kernel machst, dreißig TCP-Streams die Leitung verstopfen, du alle Festplatten parallel auf Fehler prüfst und dann noch eine DVD brennst? Garantiert dir dein System die zwei Sekunden immernoch?

So lange die fetten Jobs alle mit niedrigerer Priorität laufen sollte der Tastendruck durch kommen, theoretisch zumindest. Mir ist klar das Linux gar keine Zusicherungen macht aber zwei Sekunden für jeden Tastendruck ist schon recht lang, selbst mit einer oder zwei Compiler-Instanzen im Hintergrund konnte ich bis jetzt diese Beiträge hier immer ohne spürbare Verzögerung schreiben (da kostet manche Flash-Zappel-Werbung von nem anderen Browserfenster gefühlt mehr Performance).


Grüße
Erik

[Svenska]

Wenn der Scheduler aber in einer ganz normalen Zeitscheibe läuft, spielt das keine Rolle - das Lock ist zu diesem Zeitpunkt immer frei.

Das trifft nur für die aktuelle CPU zu aber nicht für die anderen. Ob die anderen CPUs gerade einen Kontext-Switch durchführen (und deswegen die jeweils eigene Liste bearbeiten) oder nicht ist purer Zufall, egal ob der Haupt-Scheduler als Teil des Kernels läuft oder als User-Mode-Prozess.

Hmm, das ist ein Argument: die Zeitschreiben müssen ja nicht auf allen CPUs synchronisiert ablaufen. Das macht's schwieriger.

Ich denke die Kunst besteht darin einen kleinen lokalen Scheduler zu haben den jede CPU für sich aufruft um den nächsten Thread zu bekommen und ein paar Statistiken zu updaten

Das war der von mir geschilderte zweite Codepfad (der mit dem Injizieren). Den kann man natürlich auch noch etwas eleganter machen und ausschmücken. Da kriegst du auch meine volle Zustimmung.

und dazu einen großen globalen Schduler zu haben der nur dann aufgerufen wird wenn sich der Status-Quo ändert (z.B. wenn beim Aktualisieren der Statistik durch den kleinen Scheduler ein Ungleichgewicht eine gewisse Schwelle übersteigt oder Threads dazu kommen bzw. verschwinden/blockieren).

Ja, allerdings sehe ich nicht so das große Problem (wenn der große Scheduler gut skaliert!), wenn er gelegentlich zwangsverordnet wird, sich um alles kümmert, und dann erstmal zukünftig der kleine Scheduler einfach abarbeitet, was der große Chef erzählte.

Das ist zwar eine gute Idee aber wie viele Threads trifft das? Ich denke es gibt nur ganz wenige Situationen wo man einen kontinuierlichen Fluss an Arbeit hat (mit relativ konstanten Arbeit-pro-Zeit-Wert) wo immer mal wieder etwas zu tun ist, klassisches Beispiel wäre der Decoder-Thread in einem Media-Player.

Der läuft eh mit einer höheren Priorität, schließlich ist Multimedia eine Echtzeitanwendung und die kannst du, wenn auch nicht garantieren, dadurch recht zuverlässig bereitstellen. Außerdem blockiert er ständig, wenn er nichts mehr zu tun haben möchte und lässt sich per Signal wieder aufwecken.

Die überwiegende Mehrheit aller Threads arbeitet so lange bis die Arbeit zu Ende ist oder eine blockierende Aktion ausgeführt wird, ich denke das sind die 2 Fälle die ein Scheduler möglichst gut abdecken muss.

Andersrum: Die Mehrheit aller Threads arbeitet ihre Zeitscheibe ab oder blockiert vorher. Andere Fälle (endet vorher) sind die absolute Ausnahme. Das meintest du doch, oder?

Threads, die ihre Zeitscheiben regelmäßig aufbrauchen, behandelst du normal; Threads, die das nicht tun, bevorzugst du etwas. Vielleicht eine Prioritätsstufe. Den Rest deiner Zeitscheibe gibst du dann einfach nicht-interaktiven Prozessen, die können damit sicherlich auch was anfangen. Oder (im Gegensatz zu oben) du löst sich komplett von dem Problem der Zeitscheiben. Das führt zu einem sehr komplexen Scheduler (und erfordert einen interruptfähigen Timer je CPU, und die Möglichkeit, Interrupts auf eine bestimmte CPU zu routen), wäre aber mal ein interessantes Konzept.

Das Problem ist nur das dieser Gesamtüberblick um so teurer wird je größer das Gesamtsystem ist, also der Aufwand wächst mit der Anzahl der CPUs und mit der Anzahl der runnable Threads.

Das ist das schöne, wenn du für die Zukunft planst: Du kennst den Gesamtzustand schon, bevor er überhaupt existiert. Jedenfalls, solange dein Plan stimmt; aber bei einem Scheduler spekulierst du so viel, dass eine Minderheit an Fehlspekulationen nicht weiter stören sollte.

Wenn du viele CPUs hast, kannst du auch potentiell mehr CPU-Zeit für den Scheduler ausgeben; gegenüber der Anzahl der vorhandenen Threads solltest du aber möglichst ein O(1) produzieren.

"Ein Kompromiss ist die Kunst einen Kuchen so zu schneiden das jeder denkt er hätte das größte Stück!"

Erzähle das bloß nicht den Prozessen, die du auf deinem System hast (oder entziehe ihnen vorher jede Möglichkeit der Zeitbestimmung ).

Es dürfte aber auch einige Threads geben die für ein oder zwei Zeitscheiben gut Arbeit haben und dann wieder länger blockieren bevor wieder ein kleines Stück Arbeit zu erledigen ist (misst, mir fällt da jetzt gar kein Beispiel ein).

Das ist irrelevant; wenn sie blockieren, fallen sie aus der Betrachtung raus. Es gibt aber nur wenige Threads, die ihre Zeitscheiben immer voll ausnutzen und dann umschalten auf nie ausnutzen.

Auch das Aufwachen und wieder Einschlafen von Threads ist ein wichtiges Ereignis das den großen Scheduler erforderlich machen kann (aber sicher nicht immer muss).

Ja. Wenn die Queue für die CPU lang genug ist, kann sie ja erstmal damit weitermachen, was sie hat.

So lange die fetten Jobs alle mit niedrigerer Priorität laufen sollte der Tastendruck durch kommen, theoretisch zumindest.

Du weißt aber schon, dass niedrige Priorität erstmal nichts mit den I/O-Prozessen zu tun hat, oder? Wenn du auf einem 2.6.26er Kernel ein paar hundert Megabyte mit USB 1.1 wegschreibst, dann steht dein System auch, weil der Kernel gerne für Datensicherheit ist und die Daten committen möchte. Konkret rechnet er nicht damit, dass ein I/O-Gerät für so große Datenmengen so unglaublich langsam sein kann und alle Systemprozesse leiden. (Der Fehler, der das offensichtlich gemacht hat oder noch macht, ist, dass die Speicherverwaltung nahezu blockiert, weil sie den Speicher für das I/O braucht.)

Das sind dann aber schon Probleme eines komplexen Zusammenspiels. Oder andersrum, wenn du viele optimale Lösungen kombinierst, muss das Gesamtsystem nicht unbedingt optimal sein (Pareto-Suboptimalität), womit wir dann wieder bei den Kompromisslösungen wären.

Gruß

[erik.vikinger]

Hallo,

die Zeitschreiben müssen ja nicht auf allen CPUs synchronisiert ablaufen.

Warum sollten sie auch, bei mir bekommt jede CPU einen lokalen Zeitscheiben-Counter (sowas wie den local-APIC-Timer nur primitiver) und die werden früher oder später auseinander driften (weil dieser Counter z.B. während IRQs steht und der IRQ-Handler ja nicht immer gleich lang benötigt), und da wir ja in diesem Thread beschlossen haben das ich meine CPUs gestaffelt loslaufen lassen kann wird es nicht mal nach dem Einschalten die Situation geben das alle Zeitscheiben synchron ablaufen.

Ja, allerdings sehe ich nicht so das große Problem (wenn der große Scheduler gut skaliert!), wenn er gelegentlich zwangsverordnet wird, sich um alles kümmert

Wenn der große Scheduler aber immer wieder den selben Plan ausarbeitet, weil sich am Status-Quo nichts geändert hat, dann ist das IMHO Verschwendung von CPU-Takten und sollte möglichst vermieden werden.

Die überwiegende Mehrheit aller Threads arbeitet so lange bis die Arbeit zu Ende ist oder eine blockierende Aktion ausgeführt wird, ich denke das sind die 2 Fälle die ein Scheduler möglichst gut abdecken muss.

Andersrum: Die Mehrheit aller Threads arbeitet ihre Zeitscheibe ab oder blockiert vorher. Andere Fälle (endet vorher) sind die absolute Ausnahme. Das meintest du doch, oder?

Ja, mit "bis die Arbeit zu Ende ist" meinte ich einen langen Zeitraum (z.B. bei einem Simulationstool oder Renderer der genau so viele Threads startet wie CPUs da sind und die für viele Stunden pausenlos beschäftigen kann).

Threads, die ihre Zeitscheiben regelmäßig aufbrauchen, behandelst du normal; Threads, die das nicht tun, bevorzugst du etwas.

Ich würde ja sagen das ich einfach immer zum nächsten Eintrag in der Liste übergehe und es mich nicht interessiert ob die Zeitscheibe ganz oder nur zum Teil aufgebraucht wurde. Ich bin immer noch der Meinung das Threads die Ihre Zeitscheibe selber per Yield abgeben (also nicht blockieren aber auch nicht voll durchrechnen bis der Zeitscheiben-Timer kommt) eher die Ausnahme sind, dafür extra Code im Scheduler vor zu sehen ist IMHO eher Verschwendung von CPU-Takten. Und Multimedia-Sachen macht man über die Priorität, wie Du ja auch selber geschrieben hast.

und erfordert einen interruptfähigen Timer je CPU, und die Möglichkeit, Interrupts auf eine bestimmte CPU zu routen

Den Timer pro CPU hab ich (der kann aber auch nur die lokale CPU unterbrechen) aber das Routen externer IRQs zu einer bestimmten CPU wird es nicht geben.

Das Problem ist nur das dieser Gesamtüberblick um so teurer wird je größer das Gesamtsystem ist, also der Aufwand wächst mit der Anzahl der CPUs und mit der Anzahl der runnable Threads.

Das ist das schöne, wenn du für die Zukunft planst: Du kennst den Gesamtzustand schon, bevor er überhaupt existiert.

Also das musst Du mir näher erklären, ich war immer der Überzeugung das SW nicht in die Zukunft blicken kann, genau so wenig wie der Programmierer.

Es dürfte aber auch einige Threads geben die für ein oder zwei Zeitscheiben gut Arbeit haben und dann wieder länger blockieren bevor wieder ein kleines Stück Arbeit zu erledigen ist (misst, mir fällt da jetzt gar kein Beispiel ein).

Das ist irrelevant; wenn sie blockieren, fallen sie aus der Betrachtung raus.

Ich meinte eher den Zeitpunkt wo sie wieder aufwachen (die Blockierung vorbei ist) und sie wieder volle CPU-Leistung wollen, da müssen die möglichst schnell wieder rein in die Betrachtung. Also ein Job für den großen Scheduler oder es ist noch mindestens eine geniale neue Idee fällig.

Du weißt aber schon, dass niedrige Priorität erstmal nichts mit den I/O-Prozessen zu tun hat, oder? Wenn du auf einem 2.6.26er Kernel ein paar hundert Megabyte mit USB 1.1 wegschreibst, dann steht dein System auch, weil der Kernel gerne für Datensicherheit ist und die Daten committen möchte. Konkret rechnet er nicht damit, dass ein I/O-Gerät für so große Datenmengen so unglaublich langsam sein kann und alle Systemprozesse leiden. (Der Fehler, der das offensichtlich gemacht hat oder noch macht, ist, dass die Speicherverwaltung nahezu blockiert, weil sie den Speicher für das I/O braucht.)

Ein Problem das IMHO auch zu einem gewissen Teil an dem Umstand liegt das der Linux-Kernel ein Monolith ist, in einem Mikro-Kernel (wo USB ein eigenständiger Service ist) kann sowas eigentlich grundsätzlich nicht passieren. Dazu kommt aber auch noch das UHCI/OHCI noch recht PIO-Lastig sind, ich denke bei einem xHCI-Controller an dem ein USB 1 Device hängt ist das Problem schon deutlich abgeschwächter weil der xHCI-Controller den Datentransfer komplett alleine managed und nur alle paar MB mal per IRQ um Nachschub bittet.

Das sind dann aber schon Probleme eines komplexen Zusammenspiels....

Eben. Das ist ja das was man oft aber nicht immer mit einem dezentralisierten Design umgehen kann (eben Mikro-Kernel).


Grüße
Erik

[Svenska]

Hallo,

Also das musst Du mir näher erklären, ich war immer der Überzeugung das SW nicht in die Zukunft blicken kann, genau so wenig wie der Programmierer.

Schon klar, aber du kannst immer den aktuellen Zustand, den du kennst, in einen zukünftigen Zustand extrapolieren (d.h. präventiv Zeitslots für vorhandene Threads verteilen).

Solange sich nichts ändert, ist dieser Plan optimal. Du musst also nur rauskriegen, wann sich Dinge ändern und den Plan für die zukünftigen Zeitscheiben dann entsprechend anpassen.

Ich meinte eher den Zeitpunkt wo sie wieder aufwachen (die Blockierung vorbei ist) und sie wieder volle CPU-Leistung wollen, da müssen die möglichst schnell wieder rein in die Betrachtung. Also ein Job für den großen Scheduler oder es ist noch mindestens eine geniale neue Idee fällig.

Jain, wenn ein Thread aus dem Blocking rausfällt, musst du ihn irgendwie wieder ins aktive Scheduling überführen, das ist richtig. Aber du brauchst nicht unbedingt die Messungen neu durchführen, wenn er vorher viel gearbeitet hat und jetzt nur mal einen Syscall machen musste, wird er wahrscheinlich wieder viel arbeiten wollen.

Das sollte also auch etwas einfacher gehen, als alles neu zu machen, schließlich hattest du die Arbeit ja schonmal erledigt. Am Ende läufts aber auf ein Abspeichern der Zustände raus, und das ist wieder Mist... kann keine geniale Idee mehr liefern (nichtmal eine nichtgeniale).

Dazu kommt aber auch noch das UHCI/OHCI noch recht PIO-Lastig sind, ich denke bei einem xHCI-Controller an dem ein USB 1 Device hängt ist das Problem schon deutlich abgeschwächter weil der xHCI-Controller den Datentransfer komplett alleine managed und nur alle paar MB mal per IRQ um Nachschub bittet.

Sicher, du darfst aber einen schlechten Scheduler (bzw. ein System, welches sich so aus dem tritt bringen lässt) nicht mit guter Hardware wegerklären.

Das sind dann aber schon Probleme eines komplexen Zusammenspiels....

Eben. Das ist ja das was man oft aber nicht immer mit einem dezentralisierten Design umgehen kann (eben Mikro-Kernel).

Eben: Nicht immer. Am Ende hast du ein Gesamtsystem, wo jeder Teil seine eigenen Anforderungen, Macken und Grenzen hat, die du alle brav verwalten und nach Möglichkeit optimal ausnutzen musst.

Gruß

[erik.vikinger]

Hallo,

aber du kannst immer den aktuellen Zustand, den du kennst, in einen zukünftigen Zustand extrapolieren (d.h. präventiv Zeitslots für vorhandene Threads verteilen).

Also doch eine Analyse über die Vergangenheit und dann auf die Zukunft schlussfolgern. Ich denke mal so lange beide Zeiträume (nach hinten wie nach vorn) relativ kurz sind sollte das noch in Ordnung gehen.

Solange sich nichts ändert, ist dieser Plan optimal. Du musst also nur rauskriegen, wann sich Dinge ändern und den Plan für die zukünftigen Zeitscheiben dann entsprechend anpassen.

Also wann sich Dinge ändern ist ja relativ klar: immer dann wenn ein Thread aus der Blockierung aufwacht oder neu erstellt wird und immer dann wenn ein Thread blockiert oder gekillt wird. Es dürfte aber offensichtlich sein das insbesondere das Blockieren/Aufwachen sehr häufig passieren wird. In einem stark interaktiv genutzten System könnte ich mir da über 1000 solcher Ereignisse pro Sekunde vorstellen und das ist dann definitiv zu häufig um immer den großen Scheduler aufzurufen, nebst dessen das sich dadurch die Gesamt-Situation meistens nur marginal ändert (oder zwischen 2 Lastzuständen hin und her wechselt).
Ich bin daher schon der Meinung das man zwar bei allen relevanten Ereignissen den großen Scheduler antriggern sollte aber das dieser trotzdem in seiner Aufruf-Häufigkeit geschickt Limitiert wird. Da wäre mir eben die Idee gekommen das man das Antriggern per HW erledigt (Antriggern wäre dann ein simpler Schreibzugriff in ein HW-Register) aber diese HW eben nur mit einer gewissen Maximal-Frequenz (vielleicht 25Hz) dann tatsächlich den großen Scheduler aufruft (als spezieller Interrupt, der hätte auch den Vorteil das er immer jeglichen User-Mode-Code unterbrechen kann und würde nicht aus dem Kontext eines kleinen Schedulers heraus aufgerufen). Das ließe sich auch sehr gut mit meinem rein passiven Kernel verbinden.

wenn ein Thread aus dem Blocking rausfällt, musst du ihn irgendwie wieder ins aktive Scheduling überführen, das ist richtig.

Gut, man könnte ihn einfach wieder der CPU zuweisen auf der er vorher schon lief, der große Scheduler hat sich doch bestimmt was dabei gedacht als er diesen Thread gerade dort hin gelegt hat (Außerdem sind vielleicht noch Reste im Cache falls das Blockieren nur sehr kurz war).

Aber du brauchst nicht unbedingt die Messungen neu durchführen, wenn er vorher viel gearbeitet hat und jetzt nur mal einen Syscall machen musste, wird er wahrscheinlich wieder viel arbeiten wollen.

Das stimmt. Also sollte man die Arbeitsstatistik der Threads beim Blockieren nicht wegschmeißen.

Am Ende läufts aber auf ein Abspeichern der Zustände raus, und das ist wieder Mist...

Ich finde das gar nicht so schlimm, so lange diese Statistik nur aus ein paar wenigen Werten besteht sollte das machbar sein. An irgendeiner Stelle kostet der Scheduler eben ein paar Takte und wenn dann würde ich die lieber in einen guten Informationsbestand investieren und hoffen das der große Scheduler mit guten Informationen vielleicht auch einen guten Plan erstellt.

kann keine geniale Idee mehr liefern (nichtmal eine nichtgeniale).

Keine Sorge, wir haben doch Zeit. Wir sind hier in einem Forum und nicht auf der Flucht.

Sicher, du darfst aber einen schlechten Scheduler (bzw. ein System, welches sich so aus dem tritt bringen lässt) nicht mit guter Hardware wegerklären.

Is klar, ich bin nur der Meinung das der Linux-Kernel da wohl auf eine Annahme hereingefallen ist die wohl davon ausgeht das HW nicht ganz so träge ist und diese Annahme würde eben bei xHCI wieder zutreffen trotz Low/Full-Speed-USB-Device. Das macht natürlich nicht wett des der Linux-Kernel eben von einer fehlerhaften Annahme ausgeht.

Am Ende hast du ein Gesamtsystem, wo jeder Teil seine eigenen Anforderungen, Macken und Grenzen hat, die du alle brav verwalten und nach Möglichkeit optimal ausnutzen musst.

Hm, also muss man vorher erst mal die globalen Anforderungen möglichst gut spezifizieren und dann alle Teile passend designen. Da ist der Grund warum ich am Anfang eines jeden Projekts immer eine gute Planung sehe.


Grüße
Erik


Edit:  Yeah! Top Ten!  SCNR