Lowlevel
Lowlevel => OS-Design => Thema gestartet von: erik.vikinger am 23. January 2011, 01:39
-
Hallo,
ich bin gerade auf ein kleines Design-Problem in meinem Boot-Prozess gestoßen: Wie aktiviert man am besten die einzelnen CPUs bei einem SMP-System wenn damit das aktivieren des Kernels verbunden ist?
Meine Situation ist folgende:
Der Kernel liegt im RAM und ist komplett vorbereitet (also alle internen Datenstrukturen sind einsatzbereit und 3 User-Mode-Prozesse sind auch eingerichtet, die Lebendgeburt könnte also jetzt stattfinden) aber die eine aktive CPU (BSP, ist noch im Code vom Boot-Loader) muss nun erst noch die anderen (APs) aktivieren weil der Kernel selber das nicht kann (warum sollte der Code für diese Funktionalität auch Platz im Kernel belegen wenn das doch nur ein einziges mal beim booten gemacht werden muss). Ich hatte erst die Idee alle CPUs der Reihe nach aufzuwecken und alle warten zu lassen bis wirklich alle da sind so das alle CPUs gleichzeitig per IRET in den User-Mode springen (auf jeder CPU läuft dann ein individueller Thread vom idle-Prozess) aber das erscheint mir irgendwie unpraktisch. Ich würde lieber eine CPU nach der anderen Aufwecken und die springen sofort in den User-Mode und von dort dann nach der kurzen initial-Zeitscheibe der idle-Threads zurück in den Scheduler welcher dann den init-Prozess ans laufen bringt. Es kann also passieren das einige CPUs schon voll normalen User-Mode-Code und normalen Kernel-Code (IRQ-Handler usw.) abarbeiten während andere CPUs noch deaktiviert sind oder sich noch im INIT-Mode befinden (und Boot-Loader-Code ausführen). Bei der ersten Möglichkeit würde das nicht passieren weil alle CPUs gleichzeitig mit der richtigen Arbeit anfangen so das mein OS ein einem einzigen Moment zum Leben erwacht und nicht in mehreren kleinen Häppchen. Ich möchte trotzdem lieber die zweite Möglichkeit benutzen, schon weil da schneller angefangen wird das eigentliche System hochzufahren (die APs warten eben nicht bis der BSP alle APs aktiviert hat sondern es gibt sofort Action).
Seht Ihr da irgendein Problem?
Ich hoffe ich habe mich einigermaßen verständlich ausgedrückt (trotz der Uhrzeit). Wenn nicht dann Bitte einfach nachfragen.
Wie gestalten andere eigentlich das Aufwecken der restlichen CPUs? Wimre haben doch hier ein paar Leute SMP ans laufen bekommen.
Grüße
Erik
-
Hallo,
ist zu diesem Zeitpunkt der Scheduler bereits aktiv? Für den BSP allein, der noch den Bootcode ausführt, ist er nicht notwendig. (Sofern der Bootstrap-Code rein linear ist.)
Ansonsten könntest du nämlich einfach alle CPUs außer des BSP aktivieren und in die Idle-Schleife schicken; die letzte Aktion des Bootloaders wäre dann, den Scheduler zu starten, der dann die Verteilung der Usermode-Prozesse auf die CPUs vornimmt. Das System beginnt also mit dem Tod des Bootloaders an zu leben.
Die CPUs einzeln zu aktivieren und direkt mit Usermode-Prozessen zu befüllen halte ich aus verschiedenen Gründen nicht für sinnvoll:
(a) Sollten Prozesse eine gewisse CPU-Affinität haben, um den CPU-eigenen Cache besser ausnutzen zu können. Startest du dein Vierprozessorsystem jetzt CPU-weise, dann landen erstmal alle Prozesse auf CPU2 (CPU1 ist noch mit dem Bootstrap beschäftigt) und der Scheduler muss sie dann später auf andere CPUs verteilen und zerstört somit unnötigerweise deren Cache.
(b) Weißt du nicht unbedingt, ob eine CPU defekt ist. Wenn die Idle-Schleife allerdings abstürzt, kannst du sie direkt wieder aus dem System entfernen, ohne schon Usercode ausgeführt zu haben. Die Wahrscheinlichkeit, dass du eine defekte CPU findest, ist beim Systemstart wesentlich höher als zu einem späteren Zeitpunkt, an dem sie schon Code ausgeführt hat...
(c) Der Boot-Prozess ist in der Regel nicht CPU-limitiert. Das Hauptproblem ist die I/O-Last. Die paar tausend Taktzyklen, die du gewinnst, wenn du die CPUs während des Bootstraps schon direkt ins aktive Scheduling übernimmst, bringen nichts, weil die Daten erst noch umständlich geladen werden müssen. (Das gilt natürlich nur, wenn dein Userspace von einem sekundären Medium geladen wird. Das sollte aber der Normalfall sein.)
Normalerweise machen Kernel keine Lebendgeburt. Bei Linux hast du den Fall, dass der Kernel als Uniprozessor läuft und dann der Reihe nach CPUs aktiviert. Sie sind dann auch direkt im Scheduling eingebunden. Da aber das System zu dem Zeitpunkt nicht nur lebensfähig ist, sondern sogar lebendig, ist das etwas anderes.
Hoffe, das hilft dir ungefähr weiter.
Gruß,
Svenska
-
@Svenska
zu a) Eine gewisse, aber nicht das man sagt das ein Prozess nur noch auf dieser einen CPU läuft. Denn das läuft dann darauf hinaus, dass viele CPUs idlen und ein paar, auf denen die Threads gestartet wurden, machen die ganze arbeit. Von daher würde ich das als nicht so schlimm erachten.
zu b) Defekte CPUs (die nicht vom BIOS deaktiviert wurden, bei x86) würde ich komplett ignorieren. Weil wie stellst du fest ob sie defekt sind? Ich würde wenn mir der Idle-Prozess abstürzt das ganze System in einen Panic schicken, weil normal ist das nicht. Soll der Nutzer erstmal die CPU tauschen und dann wieder neu versuchen.
zu c) Also gut ich starte für jede vorhandene Hardware einen Thread der die Hardware initialisiert. Viele Threads heißen für mich, es wäre gut wenn man die auch auf viele CPUs verteilen kann. Würde also schon was bringen.
Ich lasse die vorhandenen APs vom Bootloader starten und die warten dann an einer Spinlock. Wenn der Kernel dann läuft und sich soweit initialisert hat (ein wenig arbeit wird noch vom Kernel verrichtet), lässt er jede CPU, nacheinander, loslaufen und die wiederrum müssen auch noch ein paar Initialisierungen machen, aber die laufen zum Großteil schon parallel ab. Ab einer gewissen CPU Anzahl macht es sich durchaus bemerkbar ob der Code parallel oder hintereinander abläuft.
Im hinblick auf die Zukunft, ich denke da an so Many-Core Projekte von Intel, wo man zwar 100 und mehr Cores hat, der einzelne Core aber wesentlich langsamer ist als heutige Cores, macht es wieder Sinn so schnell wie möglich alles parallel laufen zu lassen.
-
Hallo,
ist zu diesem Zeitpunkt der Scheduler bereits aktiv?
Ja. Also sobald die erste CPU in den User-Mode wechselt kann diese CPU auch eine Kontext-Switch-Exception ausführen und damit den Scheduler auf den Plan rufen. Da ich für den erste Aktivierung eine kurze Rest-Zeitscheibe von 1µs vorgeben möchte dürfte es also problemlos möglich sein das der erste AP bereits einen kompletten Kontext-Switch über den Scheduler erledigt hat (also vom ursprünglichen idle-Thread zum init-Thread gewechselt hat) während der BSP noch damit beschäftigt ist die restlichen APs aufzuwecken.
Für den BSP allein, der noch den Bootcode ausführt, ist er nicht notwendig. (Sofern der Bootstrap-Code rein linear ist.)
Für den Boot-Code selber ist kein Scheduler erforderlich. Der eigentliche Kernel ist da auch noch nicht am Leben. Worum es mir hier geht ist quasi der letzte Schritt im Boot-Code, nämlich die eigentliche Lebendgeburt (alle notwendigen Vorbereitungen sind schon erledigt bevor der Boot-Code hiermit anfängt).
Ansonsten könntest du nämlich einfach alle CPUs außer des BSP aktivieren und in die Idle-Schleife schicken; die letzte Aktion des Bootloaders wäre dann, den Scheduler zu starten, der dann die Verteilung der Usermode-Prozesse auf die CPUs vornimmt. Das System beginnt also mit dem Tod des Bootloaders an zu leben.
Das war ja meine erste Idee die aber bedeutet das es erst dann los geht wenn der Boot-Code alle APs aufgeweckt hat und das kostet IMHO unnötig Zeit. Nebst dessen das ich meinen Scheduler nicht aktivieren kann, er ist eine Art Exception-Handler der von der CPU automatisch aufgerufen wird wenn die Zeitscheibe abgelaufen ist. Also so bald ich eine CPU das erste mal in den User-Mode schicke muss der Scheduler bereits voll funktionsfähig sein und das ist er auch weil er vom Boot-Code passend vorbereitet wurde (noch vor der Lebendgeburt).
(a) Sollten Prozesse eine gewisse CPU-Affinität haben, um den CPU-eigenen Cache besser ausnutzen zu können....
Ich denke das ist für den Boot-Vorgang erst mal absolut unerheblich. In diesem Moment existieren nur 3 Prozesse. init und exec haben jeweils nur einen Thread (exec ist ein Service der eh nur auf Zuruf arbeitet) und idle hat so viele Threads wie CPUs vorhanden sind (wird vom Boot-Code so vorbereitet). Erst init erstellt dann weitere Prozesse (mit Hilfe des exec-Service), init ist bei mir ne Art initrd mit etwas integriertem Code als eigenständiger User-Mode-Prozess realisiert.
(b) Weißt du nicht unbedingt, ob eine CPU defekt ist....
Und wie soll ich feststellen ob eine CPU defekt ist? Wenn die CPU aufwacht ist sie erst mal im INIT-Mode (auch eine Art System-Mode) und führt noch etwas Code vom Boot-Code aus (um die Register vorzubereiten usw.) und macht dann ein IRET, in diesem winzigen Boot-Code könnte man ja noch einen kurzen Selbsttest unterbringen aber mehr kann ein OS IMHO nicht tun. Wenn ein System wegen einer defekten CPU abstürzt dann muss eben der User die CPUs tauschen, außerdem gibt es ja noch die Maschine-Check-Architekture die es vielleicht ermöglicht wenigstens eine einigermaßen brauchbare Fehlermeldung auszugeben damit der User zumindest eine wage Idee hat was wohl defekt sein könnte.
(c) Der Boot-Prozess ist in der Regel nicht CPU-limitiert. Das Hauptproblem ist die I/O-Last. Die paar tausend Taktzyklen, die du gewinnst, wenn du die CPUs während des Bootstraps schon direkt ins aktive Scheduling übernimmst, bringen nichts, weil die Daten erst noch umständlich geladen werden müssen. (Das gilt natürlich nur, wenn dein Userspace von einem sekundären Medium geladen wird. Das sollte aber der Normalfall sein.)
In dem Moment wo die Lebendgeburt meines Kernel passieren soll gibt es im System nichts weiter außer ein paar CPUs und den Haupt-Speicher, es gibt noch keine PCI-Devices (die sind alle noch im Reset) und der physische Adressraum ist ansonsten noch komplett leer. Alles was das OS benötigt um an eine HDD (oder auch an eine LAN-Freigabe) zu kommen muss also in init enthalten sein und von diesem entpackt und gestartet werden bis dann endlich der richtige Boot-Vorgang anfangen kann. Wenn wir von einem schlanken Linux-Kernel mit fetter initrd (die alle möglichen Treiber als Module enthält) ausgehen dann muss der Linux-Kernel ja auch erst mal das Plug-&-Play über den PCI laufen lassen und alle nötigen Treiber aus der initrd holen bis er dann endlich das root-File-System mounten kann um dann von dort /sbin/init zu starten, dieser Abschnitt im Boot-Prozess dürfte wohl schon im wesentlichen CPU-limitiert sein. Bei einem Micro-Kernel ist nur der Unterschied das dieser bereits voll einsatzfähig ist weil ja Treiber usw. gar nicht zu seinen Aufgaben gehören. Mein Kernel weiß gar nicht das es überhaupt PCI gibt, der kennt nur CPUs und Speicher und so bald das beides da ist kann er glücklich leben und den Rest dem User-Mode überlassen.
Normalerweise machen Kernel keine Lebendgeburt.
Ich will ja auch keine normale Plattform entwickeln. ;) Das mit der Lebendgeburt empfinde ich persönlich als ganz gute Variante weil ich so auch vermeiden kann das Code im Kernel ist der nur genau ein einziges mal benötigt wird, außerdem will ich ja einen schlanken Microkernel bauen bei dem gar nicht viel vorzubereiten ist (eigentlich nur ein paar Datenstrukturen und die Einsprungspunkte der Exception-Handler müssen den CPUs bekannt gemacht werden). Mein Kernel ist eigentlich nur eine Ansammlung von Interrupt/Exception/Syscall-Handlern und enthält keine eigenständigen Aktivitäten.
Grüße
Erik
-
aber die eine aktive CPU (BSP, ist noch im Code vom Boot-Loader) muss nun erst noch die anderen (APs) aktivieren weil der Kernel selber das nicht kann (warum sollte der Code für diese Funktionalität auch Platz im Kernel belegen wenn das doch nur ein einziges mal beim booten gemacht werden muss).
Hotplugging willst du schon per Design verbieten?
-
Hallo,
Hotplugging willst du schon per Design verbieten?
Du meinst Hotplugging von CPUs? Zum jetzigen Zeitpunkt definitiv ja, ich will ja das mein System überhaupt erst mal funktioniert. Was ich später vielleicht mal alles unterstützen möchte steht noch in den Sternen. Und das bisschen Code dann doch noch in den Kernel zu holen sehe ich nun auch nicht als so grundsätzliche Designänderung das es quasi unmachbar wäre.
Edit: bevor ich es vergesse: wie habt ihr denn bei tyndur das CPU-Hotplugging designtechnisch umgesetzt? ;) Ich glaube das können überhaupt nur ganz wenige OSe auf diesem Planeten.
Grüße
Erik
-
[CPU-Affinität] Eine gewisse, aber nicht das man sagt das ein Prozess nur noch auf dieser einen CPU läuft. Denn das läuft dann darauf hinaus, dass viele CPUs idlen und ein paar, auf denen die Threads gestartet wurden, machen die ganze arbeit. Von daher würde ich das als nicht so schlimm erachten.
Das ist mir schon klar. Einfacher ist es aber, wenn der Scheduler alle beim Start vorhandenen CPUs sieht und die Anwendungen direkt gleichmäßig verteilt, anstatt erstmal alle Anwendungen auf CPU2 zu legen und später von dort nochmal wegzunehmen.
Defekte CPUs (die nicht vom BIOS deaktiviert wurden, bei x86) würde ich komplett ignorieren. Weil wie stellst du fest ob sie defekt sind? Ich würde wenn mir der Idle-Prozess abstürzt das ganze System in einen Panic schicken, weil normal ist das nicht. Soll der Nutzer erstmal die CPU tauschen und dann wieder neu versuchen.
Ist ja auch in Ordnung. Zu der Zeit sollte aber noch kein Usercode gelaufen sein. Wenn du CPU-Hotplugging irgendwann unterstützt, dann kannst du die CPU auch einfach nicht in den aktiven Scheduler übernehmen.
Also gut ich starte für jede vorhandene Hardware einen Thread der die Hardware initialisiert. Viele Threads heißen für mich, es wäre gut wenn man die auch auf viele CPUs verteilen kann. Würde also schon was bringen.
Bringt nichts, weil dein Kernel erstmal für jeden Thread den Hardwaretreiber von sekundärem Speicher laden muss (sofern du nichts initrd-artiges benutzt). Das Problem sind nicht die paar Zyklen Ineffizienz, weil du noch während des CPU-Bootstraps schon sämtliche Hardware initialisieren möchtest, sondern die Wartezyklen, die durch I/O geschehen. Es geht hier ausschließlich um den Zeitraum, in dem du der Reihe nach alle vorhandenen CPUs erstmalig einschaltest.
Im hinblick auf die Zukunft, ich denke da an so Many-Core Projekte von Intel, wo man zwar 100 und mehr Cores hat, der einzelne Core aber wesentlich langsamer ist als heutige Cores, macht es wieder Sinn so schnell wie möglich alles parallel laufen zu lassen.
Ja, die sind aber weit von dem entfernt, was dein OS unterstützt und auch das, was eriks Plattform bietet. Bei euch geht es um 100..101 CPUs.
Das war ja meine erste Idee die aber bedeutet das es erst dann los geht wenn der Boot-Code alle APs aufgeweckt hat und das kostet IMHO unnötig Zeit. Nebst dessen das ich meinen Scheduler nicht aktivieren kann, er ist eine Art Exception-Handler der von der CPU automatisch aufgerufen wird wenn die Zeitscheibe abgelaufen ist. Also so bald ich eine CPU das erste mal in den User-Mode schicke muss der Scheduler bereits voll funktionsfähig sein und das ist er auch weil er vom Boot-Code passend vorbereitet wurde (noch vor der Lebendgeburt).
Okay. Das mit dem "unnötig Zeit" sehe ich unkritisch. Wieviel Zeit ließe sich denn einsparen? Wieviele Millisekunden dauert es denn, eine CPU hochzufahren? Solange du keine großen CPU-Mengen im System hast, lohnt es sich u.U. nicht.
Dein Aufbau klingt allerdings stark danach, dass es an sich total egal ist, ob du alle CPUs gleichzeitig aufweckst oder nacheinander. Von daher ist die Antwort ebenfalls egal (und eine Geschmackssache).
Erst init erstellt dann weitere Prozesse (mit Hilfe des exec-Service), init ist bei mir ne Art initrd mit etwas integriertem Code als eigenständiger User-Mode-Prozess realisiert.
Zu dem Zeitpunkt, wo du anfänst, Usercode auszuführen, sollte meiner Meinung nach das System schon einigermaßen stabil sein. Das heißt, RAM und CPU sind voll einsatzfähig.
Wenn ein System wegen einer defekten CPU abstürzt dann muss eben der User die CPUs tauschen, außerdem gibt es ja noch die Maschine-Check-Architekture die es vielleicht ermöglicht wenigstens eine einigermaßen brauchbare Fehlermeldung auszugeben damit der User zumindest eine wage Idee hat was wohl defekt sein könnte.
Das wäre übrigens ein Grund dafür, den BSP als allererstes ins aktive Scheduling zu übernehmen. Denn der hat den Boot-Code bereits ausgeführt und funktioniert garantiert; also kann er auch die Fehlermeldung ausgeben. Deine Herangehensweise ist ja, dass du den BSP als allerletztes aktivierst, da er bis zuletzt noch das System hochfährt.
Alles was das OS benötigt um an eine HDD (oder auch an eine LAN-Freigabe) zu kommen muss also in init enthalten sein und von diesem entpackt und gestartet werden bis dann endlich der richtige Boot-Vorgang anfangen kann.
Ja, und die Frage ist, ob zu diesem Zeitpunkt noch CPUs aktiviert werden sollen oder nicht. Ich bin der Meinung "nein", allerdings aus Prinzip. Wenn man sehr viele CPUs hat, mag es sich lohnen, ich sehe allerdings keinen Vorteil. Das System bootet nur äußerst selten (verglichen mit der Laufzeit). Wenn dein Kernel rein passiv ist, spielt es im Übrigen keine Rolle.
Wenn wir von einem schlanken Linux-Kernel mit fetter initrd (die alle möglichen Treiber als Module enthält) ausgehen dann muss der Linux-Kernel ja auch erst mal das Plug-&-Play über den PCI laufen lassen und alle nötigen Treiber aus der initrd holen bis er dann endlich das root-File-System mounten kann um dann von dort /sbin/init zu starten, dieser Abschnitt im Boot-Prozess dürfte wohl schon im wesentlichen CPU-limitiert sein.
Sicher ist das Zerpflücken der initrd im wesentlichen CPU-limitiert, aber es macht nur einen äußerst geringen Bruchteil der Bootzeit aus. Das Mounten des root-Dateisystems dauert wesentlich länger, weil du dazu auf die Festplatte warten musst usw. Aber das ist egal, weil du diesem Zeitpunkt definitiv alle CPUs aktiv sein sollten.
Bei einem Micro-Kernel ist nur der Unterschied das dieser bereits voll einsatzfähig ist weil ja Treiber usw. gar nicht zu seinen Aufgaben gehören. Mein Kernel weiß gar nicht das es überhaupt PCI gibt, der kennt nur CPUs und Speicher und so bald das beides da ist kann er glücklich leben und den Rest dem User-Mode überlassen.
Ja. Also ist er dafür zuständig, dass die CPUs auch funktionieren und aktiv sind. :-)
Ich persönlich mag es, Initialisierung vom Rest danach zu trennen.
Das macht übrigens auch das Debugging einfacher. Wenn das System noch während der CPU-Initialisierung abstürzt, den Grund zu finden (ist es der BSP? irgendein AP? der AP, der gerade Init ausführt? Init selbst?), stell ich mir schwierig vor.
Machen musst du es am Ende eh selbst. ;-)
Gruß,
Svenska
-
Wenn du CPU-Hotplugging irgendwann unterstützt, dann kannst du die CPU auch einfach nicht in den aktiven Scheduler übernehmen.
Äh doch, das ist theoretisch jetzt schon möglich. Wenn ich denn wollte könnte ich CPUs einfach anhalten und wieder loslaufen lassen, ohne dass das Probleme gibt (jedenfalls nicht mit dem Scheduler).
Du stellst dir den Scheduler wahrscheinlich wie eine Art Verteiler vor oder? Bei mir gibt es eine Queue wo alle Threads drin sind die bereit sind und was machen wollen (vereinfacht gesagt) und jede CPU ruft bei einem Timer-Int den Scheduler-Code auf. Dieser holt sich dann den Thread mit der höchsten Priorität aus dieser Queue und lässt ihn laufen. Ist die Zeitscheibe von dem Thread abgelaufen, kommt er wieder zurück in die Queue.
Ja, die sind aber weit von dem entfernt, was dein OS unterstützt und auch das, was eriks Plattform bietet. Bei euch geht es um 1..100 CPUs.
Naja, theoretisch (nur durch Qemu getestet) läuft mein OS auch mit 255 CPUs (ich habe es gerade testen wollen und irgendwo in meinem Init-Code, der schon im Kernel läuft, gibt es noch einen Fehler).
Die Anzahl ist im Moment auch nur durch die APIC-IDs beschränkt.
Wenn das System noch während der CPU-Initialisierung abstürzt, den Grund zu finden (ist es der BSP? irgendein AP? der AP, der gerade Init ausführt? Init selbst?), stell ich mir schwierig vor.
Ich weiß nicht was du unter abstürzen meinst, aber wenn es eine Exception gibt, gebe ich mit an auf welcher CPU die aufgetreten ist und damit weiß ich dann schon wo die passiert ist.
-
Hallo,
Einfacher ist es aber, wenn der Scheduler alle beim Start vorhandenen CPUs sieht
Was ist daran einfacher? Mein Scheduler sieht die CPUs gar nicht, er wird einfach aufgerufen (von irgendeiner CPU wenn dort der Zeitscheiben-Counter abgelaufen ist), legt den aktuellen Thread wieder nach hinten in die "runnable"-Queue und holt sich den nächsten Thread vom vorderen Ende der "runnable"-Queue. Dazu muss der Scheduler noch nicht mal wissen wie viele CPUs es eigentlich gibt oder auf welcher CPU er gerade aktiv ist. Solange das reinlegen und rausholen von Threads in/aus der Queue atomar passiert können auch mehrere CPUs gleichzeitig den Scheduler aufrufen.
und die Anwendungen direkt gleichmäßig verteilt anstatt erstmal alle Anwendungen auf CPU2 zu legen und später von dort nochmal wegzunehmen.
Zu diesem Zeitpunkt gibt es genau einen Thread der tatsächlich vernünftige Arbeit leistet und das ist der eine Thread von init. Auf welcher CPU der läuft ist erst einmal ziemlich egal solange er überhaupt möglichst schnell an die Reihe kommt (was auch ziemlich schnell passieren dürfte da ja die vielen idle-Threads alle eine niedrigere Priorität haben).
Wobei ich auch ehrlich sagen muss das ich mir um (dynamische) CPU-Affinität noch keine Gedanken gemacht habe, das muss ich gleich mal auf meine Todo-Liste setzen (aber mit niedriger Priorität, ist ja schließlich nur ein Performance-Aspekt und keine richtige Funktionalität).
Das mit dem "unnötig Zeit" sehe ich unkritisch. Wieviel Zeit ließe sich denn einsparen? Wieviele Millisekunden dauert es denn, eine CPU hochzufahren? Solange du keine großen CPU-Mengen im System hast, lohnt es sich u.U. nicht.
Selbst bei 100 CPUs dürfte es hier wohl höchstens um eine zweistellige Millisekunden-Zeit gehen (es sei denn ich baue in den Boot-Code noch einen aufwendigen CPU-Selbsttest ein). Es geht mir hier eher um das Design und eine elegante Umsetzung, aber auch ein klein wenig um die benötigte Zeit für das Hochfahren. Erst alle CPUs vor einer Barriere zu sammeln damit diese dann von allen CPUs (möglichst, exakt geht ja eh nicht) gleichzeitig überschritten wird ist zwar interessant aber auch aufwendig (also Tipp/Debug-Aufwand für den Code) und IMHO völlig unnötig.
Dein Aufbau klingt allerdings stark danach, dass es an sich total egal ist, ob du alle CPUs gleichzeitig aufweckst oder nacheinander. Von daher ist die Antwort ebenfalls egal (und eine Geschmackssache).
Nun, wenn es egal ist dann kann ich ja beruhigt den einfacheren Weg benutzen (das dieser auch noch eine Winzigkeit schneller ist nehme ich dankend mit). ;)
Zu dem Zeitpunkt, wo du anfänst, Usercode auszuführen, sollte meiner Meinung nach das System schon einigermaßen stabil sein. Das heißt, RAM und CPU sind voll einsatzfähig.
Da ist auf jeden Fall gewährleistet, auch wenn noch nicht alle CPUs dabei sind. Bis dann überhaupt der PCI-Scan fertig ist und die ersten Treiber instantiiert werden (also tatsächlich mehrere nützliche Threads gerne eine CPU bekommen wollen) sollten dann auch tatsächlich alle CPUs mitten im Spiel sein.
Das wäre übrigens ein Grund dafür, den BSP als allererstes ins aktive Scheduling zu übernehmen. Denn der hat den Boot-Code bereits ausgeführt und funktioniert garantiert; also kann er auch die Fehlermeldung ausgeben.
Und das restliche Bootstrapping einem ungetesteten AP überlassen? Hm, das halte ich für keine gute Idee. Dann soll lieber der BSP, bevor er selber in den User-Mode wechselt, prüfen ob auch wirklich alle APs in Action sind. Eine Maschine-Check-Exception kann ansich jede andere CPU auch ausgeben, auf meiner Plattform ist das ausführen von externen Interrupts (Maschine-Check-Exceptions werden bei mir über den Chipsatz abgewickelt weil die "fehlerhafte" CPU einfach in den Shutdown zurück geht) nicht an bestimmte CPUs gebunden sondern es nimmt immer die CPU den Interrupt an welche gerade den User-Mode-Code mit der niedrigsten Priorität ausführt.
Deine Herangehensweise ist ja, dass du den BSP als allerletztes aktivierst, da er bis zuletzt noch das System hochfährt.
Ja, so habe ich mir das gedacht.
Ja, und die Frage ist, ob zu diesem Zeitpunkt noch CPUs aktiviert werden sollen oder nicht.
Ich gehe stark davon aus das bis da hin wirklich alle CPUs aktiv sind. Es müssten schon tausende CPUs im System vorhanden sein wenn das nicht mehr zuverlässig erreicht werden soll. Und selbst wenn wirklich noch nicht alle CPUs da sind, solange die bedürftigen Threads alle eine CPU abbekommen ist es doch auch egal.
Also ist er dafür zuständig, dass die CPUs auch funktionieren und aktiv sind. :-)
Ganz klar jein. Der Kernel soll die CPUs verwalten, das eigentliche Aktivieren ist aber erst mal noch nicht seine Aufgabe. Die CPUs, die aktiviert werden, kommen früher oder später eh beim Kernel vorbei, spätestens wenn das erste mal der Zeitscheiben-Counter abgelaufen ist muss die CPU in den Kernel-Mode.
Das macht übrigens auch das Debugging einfacher. Wenn das System noch während der CPU-Initialisierung abstürzt, den Grund zu finden (ist es der BSP? irgendein AP? der AP, der gerade Init ausführt? Init selbst?), stell ich mir schwierig vor.
Ich sehe das Problem nicht. Abstürzen bedeutet ja nicht zwangsläufig dass das System plötzlich gar nichts mehr tut (gerade auf einem SMP-System) sondern das irgendetwas nicht so läuft wie es soll und eben diese Abweichung muss man finden und dann sieht man meistens auch recht schnell die Ursache dafür.
Machen musst du es am Ende eh selbst. ;-)
Das ist ja gerade der Grund warum ich überhaupt damit angefangen hab. ;)
Grüße
Erik
-
Tja, da ihr mir jetzt endgültig alle Argumente zerstört habe, ist es mir jetz auch egal. :-P
Erst alle CPUs vor einer Barriere zu sammeln damit diese dann von allen CPUs (möglichst, exakt geht ja eh nicht) gleichzeitig überschritten wird ist zwar interessant aber auch aufwendig (also Tipp/Debug-Aufwand für den Code) und IMHO völlig unnötig.
Kann ich nicht einschätzen.
Ich trenne in Gedanken den Bootvorgang in Phasen auf, wobei jede Phase vollständig erledigt sein muss, ehe es in die nächste Phase übergeht. Das Ineinanderfließen finde ich halt nicht schön. Beides ist möglich.
Das wäre übrigens ein Grund dafür, den BSP als allererstes ins aktive Scheduling zu übernehmen. Denn der hat den Boot-Code bereits ausgeführt und funktioniert garantiert; also kann er auch die Fehlermeldung ausgeben.
Und das restliche Bootstrapping einem ungetesteten AP überlassen? Hm, das halte ich für keine gute Idee.
Wenn der BSP ins aktive Scheduling überführt wird, ist das Bootstrapping komplett beendet. Da gibt es insbesondere keinen Rest. ;-) Init wird also auf dem "ehemaligen" BSP ausgeführt.
Der AP führte während des Bootstraps eine Idle-Schleife (oder Testprogramm oder Minibenchmark oder...) aus, ist also nicht ganz ungetestet.
Gruß,
Svenska
-
Hallo,
Tja, da ihr mir jetzt endgültig alle Argumente zerstört habe, ist es mir jetz auch egal. :-P
Sorry, so wollte ich das nun auch wieder nicht.
Trotzdem bleibt wohl das Ergebnis das es scheinbar keinen triftigen Grund gibt der gegen ein gestaffeltes aktivieren der CPUs spricht.
Ich trenne in Gedanken den Bootvorgang in Phasen auf, wobei jede Phase vollständig erledigt sein muss, ehe es in die nächste Phase übergeht. Das Ineinanderfließen finde ich halt nicht schön. Beides ist möglich.
Das sehe ich eigentlich genau so wie Du auch aber in diesem konkreten Fall erschien mir das beharren darauf irgendwie unbequem und deswegen hab ich dann diesen Thread gestartet um mal andere Meinungen dazu zu bekommen. Danke!
Wenn der BSP ins aktive Scheduling überführt wird, ist das Bootstrapping komplett beendet. Da gibt es insbesondere keinen Rest.
Wenn der BSP vorher alle APs aktiviert hat (egal ob alle gleichzeitig oder gestaffelt) dann hast Du natürlich recht aber wenn der BSP noch davor (so wie von Dir vorgeschlagen) in den aktiven Dienst übergeht (also in den User-Mode wechselt und damit dem laufenden Kernel und nicht mehr dem Boot-Code gehört) dann bleibt ja eben noch die Arbeit übrig die restlichen CPUs zu aktivieren. Da das nicht der Kernel selber machen soll (das müsste man dann ja irgendwie in einen der Handler mit integrieren da der Kernel ja keine eigenständigen Aktivitäten besitzt) bleibt dafür nur der Boot-Code übrig. Das ganze einem User-Mode-Prozess (z.B. init) zu überlassen finde ich doof weil dazu ne ganze Menge an privilegierten Befehlen nötig sind für die dann extra Syscalls (mit zugehöriger Rechteprüfung damit da nur init ran kann) implementiert werden müssten. Ich bin schon der Meinung dass das aktivieren aller CPUs Teil des Boot-Code sein sollte (solange ich nicht CPU-Hotplugging unterstützen möchte).
Init wird also auf dem "ehemaligen" BSP ausgeführt.
Wenn alle CPUs wirklich gleichzeitig aktiviert werden (in den User-Mode wechseln) dann ist es ziemlich zufällig welche CPU dann als erstes im Scheduler landet (es sein denn ich benutze gestaffelte Zeitscheiben so das damit eine Reihenfolge entsteht) und damit init bekommt, wenn die CPUs gestaffelt los laufen dann ist es eben die erste CPU die vom Boot-Code aktiviert wurde und wenn das der BSP sein soll dann muss einer der APs das Aufwecken der restlichen CPUs übernehmen.
Der AP führte während des Bootstraps eine Idle-Schleife (oder Testprogramm oder Minibenchmark oder...) aus, ist also nicht ganz ungetestet.
Während der BSP den Boot-Code abarbeitet sind alle anderen CPUs noch im Shutdown-Modus, haben also noch keinen einzigen Befehl ausgeführt. Erst durch das antriggern vom letzten Abschnitt des Boot-Code wachen die CPUs auf und sind dann an einer beim antriggern übergebenen Position im Boot-Code (meine CPUs sollen erst mal in einem System-Modus aufwachen) und dort kann eventuell noch ein kurzer Selbsttest geschehen bevor dann das Springen in den User-Mode (per IRET) vorbereitet (also Register laden usw.) und durchgeführt wird. In der gestaffelten Version wird dieser allerletzte Code-Abschnitt dann auch vom BSP ausgeführt, nachdem er alle APs aufgeweckt hat und eventuell geprüft hat ob auch wirklich alle APs laufen.
Grüße
Erik
-
Mal noch ein paar Gedanken für den parallelen Start von CPUs.
Wenn man eine SSD im System hat dürfte wahrscheinlich eher ein CPU-Limit als ein I/O-Limit vorhanden sein. Vorallem da erik ja auf seiner eigenen Platform nicht die Performance aktueller CPUs erreichen möchte.
Das nächste ist, das jede CPU bestimmt irgendwelche Initialisierungs Arbeiten machen muss und da wäre es schon schön, wenn das alles so gleichzeitig wie möglich passieren würde.
-
Hallo,
Wenn man eine SSD im System hat dürfte wahrscheinlich eher ein CPU-Limit als ein I/O-Limit vorhanden sein.
Eine SSD ist zwar schnell aber so schnell nun auch wieder nicht. Die Daten müssen immer noch über das SATA-Kabel, AHCI-Controller und den PCIe-BUS bis in den RAM gelangen und das dauert auch seine Zeit. Interessant ist die SSD vor allem wenn viele parallele Anforderungen kommen oder wenn große Mengen an Daten zu übertragen sind, beides dürfte auf einen üblichen Boot-Vorgang nur begrenzt zutreffen.
Vorallem da erik ja auf seiner eigenen Platform nicht die Performance aktueller CPUs erreichen möchte.
Was heißt hier möchte? Das ist vor allem eine finanzielle Frage. Selbst mit nem FPGA aus der Ober-Klasse (der dann problemlos mehrere Tausend Dollar kostet) dürfte ich kaum über 300MHz CPU-Takt hinaus kommen. Und nen eigenen Chip anfertigen zu lassen ist erst recht unbezahlbar, zumindest für mich als Privatperson.
Das nächste ist, das jede CPU bestimmt irgendwelche Initialisierungs Arbeiten machen muss und da wäre es schon schön, wenn das alles so gleichzeitig wie möglich passieren würde.
Das wäre in beiden von mir bedachten Szenarien der Fall. Es geht mir nur darum ob ich die CPUs vor dem Übertritt in den User-Mode (nach der CPU-Initialisierung) an einer Barriere sammeln soll oder ob ich darauf verzichten kann. Das Sammeln an einer Barriere würde nur den Übertritt in den User-Mode aller CPUs verzögern bzw. an die zuletzt aktivierte CPU anpassen wogegen ohne die Barriere die ersten CPUs schon etwas früher mit der eigentlichen Arbeit beginnen. Die Initialisierungsarbeit pro CPU findet immer parallel statt, nur leicht gestaffelt weil der BSP ja einen AP nach dem anderen aktiviert.
Grüße
Erik
-
Interessant ist die SSD vor allem wenn viele parallele Anforderungen kommen oder wenn große Mengen an Daten zu übertragen sind, beides dürfte auf einen üblichen Boot-Vorgang nur begrenzt zutreffen.
Warum nicht? Warum nicht die Treiber parallel laden lassen, jeder in einem extra Thread und dann auch so initialisieren lassen?
Vorallem auf deiner Architektur sollte die SSD ein CPU Limit bewirken können. Ich habe letztens irgendwo gelesen das es schon einer verdammt schnellen CPU (und da war schon von den schnellsten SandyBridges die rede) verlangt damit man überhaupt so viele Anforderungen an die SSD stellen kann damit sie nicht mehr hinterher kommt. Denn die Daten müssen ja auch verarbeitet werden.
Es geht mir nur darum ob ich die CPUs vor dem Übertritt in den User-Mode (nach der CPU-Initialisierung) an einer Barriere sammeln soll oder ob ich darauf verzichten kann.
Warum solltest du sie aber sammeln, welchen Vorteil hätte das oder welchen Nachteil wenn du es nicht machen würdest?
Ich würde sie loslaufen lassen sobald es möglich ist.
-
Hallo,
Warum nicht? Warum nicht die Treiber parallel laden lassen, jeder in einem extra Thread und dann auch so initialisieren lassen?
Treiber werden IMHO von einem Plug&Play-Manager gestartet, wenn er eine passende Hardware findet, und den müsste man dazu parallelisieren bzw. das Treiberstarten in zusätzliche Worker-Threads auslagern, das kann man machen aber für den Einstieg ist das IMHO noch nicht unbedingt nötig.
Vorallem auf deiner Architektur sollte die SSD ein CPU Limit bewirken können.
Auf meiner Plattform werden noch viel kleinere Dinge ein CPU-Limit bewirken, dessen bin ich mir voll bewusst. :cry:
Warum solltest du sie aber sammeln, welchen Vorteil hätte das oder welchen Nachteil wenn du es nicht machen würdest?
Um genau diese Frage zu diskutieren habe ich ja diesen Thread gestartet.
Ich würde sie loslaufen lassen sobald es möglich ist.
Das möchte ich ja auch tun, aber es verwischt eben die Grenze zwischen Bootstrap-Vorgang und dem Laufen des eigentlichen OS. Das ist so als würde auf einem x86-System auf ein paar CPUs noch das BIOS arbeiten während auf anderen CPUs schon munter das OS läuft.
Grüße
Erik
-
Das möchte ich ja auch tun, aber es verwischt eben die Grenze zwischen Bootstrap-Vorgang und dem Laufen des eigentlichen OS. Das ist so als würde auf einem x86-System auf ein paar CPUs noch das BIOS arbeiten während auf anderen CPUs schon munter das OS läuft.
Wo wäre das Problem? Bzw. was dauert denn solange das es dazu kommen könnte?
Ich muss fairerweise sagen, das ich solch eine Barriere habe, weil ich ja den TSC aller CPUs halbwegs gleich haben möchte.
-
Wenn der BSP vorher alle APs aktiviert hat (egal ob alle gleichzeitig oder gestaffelt) dann hast Du natürlich recht aber wenn der BSP noch davor (so wie von Dir vorgeschlagen) in den aktiven Dienst übergeht (also in den User-Mode wechselt und damit dem laufenden Kernel und nicht mehr dem Boot-Code gehört) dann bleibt ja eben noch die Arbeit übrig die restlichen CPUs zu aktivieren.
Nein. Ich war von einem aktiven Scheduler ausgegangen, also einem Stückchen Code, welches aktiv Prozesse auf CPUs verteilt.
Der Bootstrap-Code endet und legt genau dieses Stückchen Code auf den ehemaligen BSP. Die anderen APs sind zu dem Zeitpunkt schon voll aktiv, haben nur keine Aufgaben zu erledigen (und führen darum die Idle-Schleife aus). Die müssen nicht mehr aktiviert werden, nur mit Aufgaben zugebombt. ;-)
Wenn der Scheduler so aufgebaut ist, dass er neue Aufgaben bevorzugt auf die CPU legt, auf der er gerade läuft (sich also auf diese Weise beendet), dann landet init auch definitiv auf dem ehemaligen BSP. ;-)
Allerdings ist das bei einem rein passiven Scheduler etwas hässlich zu implementieren, daher gebe ich dir recht.
Gruß
-
Hallo,
Wo wäre das Problem?
Nun, dieser Thread hat ja nun ergeben das es da wohl kein echtes Problem zu geben scheint.
Bzw. was dauert denn solange das es dazu kommen könnte?
Es ist einfach nicht möglich alle CPUs gleichzeitig zu aktivieren, auch wenn das eigentliche antriggern ein recht kurzer Vorgang ist (wohl im Bereich weniger µs) so ist er doch nicht unendlich kurz und daraus ergibt sich damit immer eine gewisse Staffelung.
Ich war von einem aktiven Scheduler ausgegangen, also einem Stückchen Code, welches aktiv Prozesse auf CPUs verteilt.
Hä, also da verstehe ich jetzt absolut nicht was Du meinst. Der Scheduler kann doch nur der CPU einen neuen Thread zuweisen auf der er gerade läuft. Er kann doch nicht auf CPU 3 laufen (weil dort gerade die Zeitscheibe des dort laufenden Threads abgelaufen ist) und der CPU 5 einen neuen Thread zuweisen. Wie soll das gehen? Was passiert mit dem Thread der gerade auf CPU 5 läuft?
Die anderen APs sind zu dem Zeitpunkt schon voll aktiv, haben nur keine Aufgaben zu erledigen
Das ist doch ein Widerspruch in sich. Eine aktive CPU führt auch etwas aus (und sei es nur ein while(true){HLT;} auch wenn das aus User-Sicht nichts sinnvolles ist). Entweder eine CPU ist aktiv und führt Code aus oder sie ist inaktiv (Shutdown, Schlafzustand o.ä.) und macht nichts.
(und führen darum die Idle-Schleife aus)
Also bei meiner CPU soll es so sein das es unmöglich ist eine CPU unbegrenzt lange im User-Mode zu halten, der Zeitscheiben-Counter zählt gnadenlos bis 0 runter und dann gibt es eine Yield-Exception (egal ob der User-Mode-Code das will oder nicht) und die CPU kommt damit wieder in den Kernel-Code (der Scheduler ist ja Teil des Kernels). Auch auf anderen Plattformen kommt doch früher oder später der Timer-IRQ (falls da nicht irgendwo etwas maskiert wurde) und holt die CPU in den Kernel zurück. Es ist in meiner Vorstellung eigentlich unmöglich die idle-Schleife unbegrenzt lange auszuführen.
Wenn der Scheduler so aufgebaut ist, dass er neue Aufgaben bevorzugt auf die CPU legt, auf der er gerade läuft (sich also auf diese Weise beendet), dann landet init auch definitiv auf dem ehemaligen BSP. ;-)
Ich weiß zwar nicht wie Du das mit dem Scheduler meinst aber auf dem BSP landet init mit hoher Wahrscheinlichkeit nicht. Wenn alle CPUs gleichzeitig losgelassen werden (die Variante mit der Barriere) dann ist es mehr oder weniger Zufall wo init landet und wenn die CPUs gestaffelt loslaufen (also ohne Barriere) dann landet init wohl auf der ersten CPU die den Scheduler aufruft und das ist wohl die CPU die als erstes vom BSP aktiviert wurde (und damit nicht der BSP selber).
Grüße
Erik
-
Hallo,
okay, gut, ich sehe wir verstehen unter Scheduler verschiedene Dinge.
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. Läuft er bereits auf einer anderen CPU, macht die CPU die Idle-Schleife.
Der Scheduler markiert global, dass er aktiv ist, und verteilt dann die noch nicht (wieder) verteilten Prozesse des Systems auf die einzelnen CPUs, die dann mit Beginn der nächsten Zeitscheibe ihre Listen abarbeiten.
Die APs werden vom Bootstrap-Code mit leeren Listen versehen, außerdem wird markiert, dass der Scheduler bereits läuft. Also führen alle APs die Idle-Schleife aus. Wenn der Boot-Code endet, startet er den Scheduler auf seiner eigenen CPU und wenn der das möchte, führt er "Init" auch auf dieser CPU aus.
Die Barriere ist also nur, dass der Scheduler Aufgaben verteilen muss (am Anfang stehen außer "init" keine an).
Gruß,
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?
-
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
-
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
-
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
-
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
-
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.
-
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.
-
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.
-
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
-
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. ;-)
-
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
-
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
-
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
-
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? :-P
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 :P).
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ß
-
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
-
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ß
-
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