Autor Thema: Scheduling, Taskverwaltung und Timing … Ich brauche meinungen :)  (Gelesen 8875 mal)

RedEagle

  • Beiträge: 244
    • Profil anzeigen
    • RedEagle-OperatingSystem - Projekt
Gespeichert
Hi
Das Multitasking, so wie ich es derzeit implementiert habe, gefällt mir nicht mehr :) Es ist meiner Meinung nach etwas umständlich, und sehr experimentell (habe einfach auf gut Glück drauf los programmiert  8-) ).
Maw.: Es wird Zeit es richtig zu machen… zumal ich derzeit mit einem recht fiesen Bug zu kämpfen habe der u.U. vielleicht sogar damit zusammenhängen könnte :D

Was mich am meisten belastet ist die Frage nach dem Timing. Mit welcher Frequenz sollten Taskwechsel stattfinden? Derzeit wird der Scheduler mit 1kHz aufgerufen. Er besteht aus etwa 80 Zeilen assembler-code.
Meine Frage ist jetzt, wie man das "Taskwechsel-Aufwand" - "Tasklaufzeit" - Verhältnis am besten wählt. Andere Kernel haben einen in C geschriebenen Scheduler. Ich mache mir sorgen dass dann 50% der Zeit nur für das Wechseln der Tasks verloren geht…

Des weiteren spiele ich mit dem Gedanken eine etwas komplexere Struktur für die Prozesse/Threads zu verwenden. Derzeit befindet sich Prozesse und Threads in einer liste die von Scheduler durchgearbeitet wird. Die einzige Beziehung zwischen Prozessen und deren Threads ist der Eintrag der parent-PID in der task-struktur des Threads. - Es ist also recht aufwändig herauszufinden ob zu einem Prozess noch Threads gehörten auf die gewartet werden muss...
Wie könnte man das am besten angehen? Einfach zu jedem Prozess/Thread eine Child-list hinzufügen? Dann hätte der Scheduler allerdings viel Arbeit.
Derzeit spiele ich mit dem Gedanken beides zu machen - also eine liste für den Scheduler, und eine für den Prozessmanager.

Wie sind eure Erfahrungen so? Wie macht ihr das?

kevin

  • Administrator
  • Beiträge: 2 767
    • Profil anzeigen
Gespeichert
1000 präemptive Taskwechsel pro Sekunde sind zu viel, würde ich sagen. 50 sollten mehr als genug sein. Das wirklich teure am Taskwechsel ist auch nicht die Zeit, die der Scheduler braucht, um einen neuen Task rauszusuchen, sondern die Kosten vom Kontextwechsel.

In tyndur macht der Scheduler überhaupt nichts mit Prozessen, er arbeitet nur mit Threads. Jeder Prozess besteht also aus mindestens einem Thread. Prozesse haben eine Liste aller ihrer Threads und Threads einen Pointer auf ihren Prozess. Wenn der Scheduler nichts mehr zu tun hat, packt er alle lauffähigen Threads in eine Liste und arbeitet dann bei den nächsten Timer-Interrupts diese Liste ab. Bei vielen aktiven Tasks holen die meisten Taskwechsel also einfach nur das nächste Element aus der Liste.

Komplizierter kann man das natürlich alles immer noch machen und sicher einen deutlich besseren Scheduler schreiben. Aber für den Moment reicht das. ;)
Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.

RedEagle

  • Beiträge: 244
    • Profil anzeigen
    • RedEagle-OperatingSystem - Projekt
Gespeichert
1000 präemptive Taskwechsel pro Sekunde sind zu viel, würde ich sagen. 50 sollten mehr als genug sein. Das wirklich teure am Taskwechsel ist auch nicht die Zeit, die der Scheduler braucht, um einen neuen Task rauszusuchen, sondern die Kosten vom Kontextwechsel.
hm… bei nur 50 Tastwechseln sieht das natürlich alles viel entspannter aus  :mrgreen:

In tyndur macht der Scheduler überhaupt nichts mit Prozessen, er arbeitet nur mit Threads. Jeder Prozess besteht also aus mindestens einem Thread. Prozesse haben eine Liste aller ihrer Threads und Threads einen Pointer auf ihren Prozess. Wenn der Scheduler nichts mehr zu tun hat, packt er alle lauffähigen Threads in eine Liste und arbeitet dann bei den nächsten Timer-Interrupts diese Liste ab. Bei vielen aktiven Tasks holen die meisten Taskwechsel also einfach nur das nächste Element aus der Liste.
Das hört sich nach einem guten Kompromiss an… Hat vor allem den Vorteil dass ich bei einem Thread-wechsel nicht das PD neu laden muss :)

Danke für die Tipps :)

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
Hallo,


Hat vor allem den Vorteil dass ich bei einem Thread-wechsel nicht das PD neu laden muss :)
Aber nur wenn der alte und der neue Thread vom selben Prozess sind.

Ich bin mir nicht sicher ob es geschickt ist immer wenn die Liste der runnable Threads leer ist diese wieder neu zu befüllen. Ich persönlich würde lieber jeden Thread der vom Scheduler verdrängt wird (der aber noch lauffähig also nicht blockiert ist) einfach wieder hinten ran hängen.

Kleiner als 20ms würde ich eine Default-Zeitscheibe auch nicht machen, wenn ein Thread wirklich was CPU-lastiges zu tun hat dann sollte man ich auch ein wenig gewähren lassen. Die übergroße Mehrheit aller Threads wird aber vor Ablauf der Zeitscheibe eine blockierende Funktion aufrufen so das dann zwangsweise der Scheduler den nächsten Thread holen muss. Ich kann mir gut vorstellen das in einem interaktiv genutzten System manchmal auch mehr als 1000 Kontextwechsel in einer Sekunde auftreten (vor allem bei einem Micro-Kernel-OS) aber das dürfte trotzdem nur die Ausnahme sein. Meistens wird einfach nur der Idle-Thread die CPU zum Strom sparen anhalten bis eben dessen Zeitscheibe abgelaufen ist (oder irgendein IRQ kommt der dann wieder einen Thread aufweckt so das es wieder was richtiges zu tun gibt).


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

RedEagle

  • Beiträge: 244
    • Profil anzeigen
    • RedEagle-OperatingSystem - Projekt
Gespeichert
Hat vor allem den Vorteil dass ich bei einem Thread-wechsel nicht das PD neu laden muss :)
Aber nur wenn der alte und der neue Thread vom selben Prozess sind.
Natürlich :) … Das ist bei meiner alten Lösung "das Problem"… dort musste ich immer das PD neu laden weil ich die Threads und Prozesse in der selben Liste hatte…

Ich bin mir nicht sicher ob es geschickt ist immer wenn die Liste der runnable Threads leer ist diese wieder neu zu befüllen. Ich persönlich würde lieber jeden Thread der vom Scheduler verdrängt wird (der aber noch lauffähig also nicht blockiert ist) einfach wieder hinten ran hängen.

Der Scheduler geht, bzw soll es, wenn er fertig ist :D, einfach durch die Liste, von Prozess zu Prozess. Bei jeden Prozess lädt er dessen PD und geht dann all seine Threads durch. Ist die Thread-liste eines Prozesses durchlaufen wird der nächste Prozess genommen und dessen PD geladen usw...
Sind alle Prozesse abgearbeitet geht es wieder von vorne los :)
Trifft er dabei auf ein blockierten Thread wird einfach der nächste geladen.

So ist es zumindest erstmal geplant… hatte aber noch nicht die Zeit gefunden mir das ins Detail zu überlegen… Wenn der Scheduler auf die selben Listen zugreift die der Prozessmanager - so war es bei dem alten - Gibt es natürlich einige kritische Momente wie z.B. das entfernen eines Prozesses…

rizor

  • Beiträge: 521
    • Profil anzeigen
Gespeichert
Der Scheduler geht, bzw soll es, wenn er fertig ist :D, einfach durch die Liste, von Prozess zu Prozess. Bei jeden Prozess lädt er dessen PD und geht dann all seine Threads durch. Ist die Thread-liste eines Prozesses durchlaufen wird der nächste Prozess genommen und dessen PD geladen usw...
Sind alle Prozesse abgearbeitet geht es wieder von vorne los :)
Trifft er dabei auf ein blockierten Thread wird einfach der nächste geladen.

Ist das nicht etwas ineffektiv? Vor allem ist das ganze recht unsicher, denn ein Prozess kann immer wieder Threads erstellen und somit nie die Kontrolle an andere Prozesse abgeben.
Ich finde, dass du die Kosten eines PD-Wechsels ueberbewertest. Du opferst die Interaktivitaet deines Systems, damit die PD-Wechsel so gut wie nie stattfinden.
Ich weisz zwar nicht wie du deiner Treiber gestalten willst, aber falls er auch mal die Kontrolle abgeben kann und nicht immer sofort die Berechnungen abschlieszt, werden die Berechnungen nur sehr langsam abgeschlossen.

So ist es zumindest erstmal geplant… hatte aber noch nicht die Zeit gefunden mir das ins Detail zu überlegen… Wenn der Scheduler auf die selben Listen zugreift die der Prozessmanager - so war es bei dem alten - Gibt es natürlich einige kritische Momente wie z.B. das entfernen eines Prozesses…

Wie waere es, wenn du den Prozessmanager vom Scheduler trennst?
Die beiden haben ja auch nicht viel miteinander zu tun. Der Prozessmanager verwaltet ja nur die Prozesse/Threads und Rechte und der Scheduler ist fuer die Ausfuehrung der Threads zustaendig.

grusz,
rizor
Programmiertechnik:
Vermeide in Assembler zu programmieren wann immer es geht.

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
Du kannst für jeden Scheduleralgorithmus ein Verfahren konstruieren, mit dem er unglaublich schlecht performt.

Ich denke, dass Threads und Prozesse getrennt betrachtet werden sollten. Der Kernel (Scheduler) teilt also Prozessen die CPU-Zeit zu, wenn ein Thread dieses Prozesses dann nix mehr zu tun hat, die Zeitscheibe des Prozesses aber noch nicht aufgebraucht ist, kommt der nächste Thread dieses Prozesses dran - bis entweder die Threads oder die Zeitscheibe alle sind.

Mit diesem Verfahren kannst du wenigstens die Anzahl an PD-Wechseln konstant halten (pro Zeitscheibe ein Wechsel), allerdings wird ein Prozess mit vielen Threads stark benachteiligt.

Als Zeitscheibenlänge ist irgendetwas zwischen 100ms und 10ms angemessen, das ist ein Kompromiss zwischen Interaktivität und Durchsatz. Beides musst du gegeneinander aufwiegen - wenn du Restzeitscheiben weiternutzt (den Kontextwechsel also vorziehst), kann die Zeitscheibe eher länger sein. Bei den heutigen schnellen Multicoresystemen spielt die exakte Länge weniger eine Rolle, da die meisten Prozesse entweder schnell (weil interaktiv) oder garnicht blockieren (weil CPU-bound). Bei letzteren ist eine lange Zeitscheibe von Vorteil, bei ersteren eine sinnvolle Nutzung des Zeitscheibenrestes; die gefühlte(!) Interaktivität ist das dritte Kriterium.

Unter Windows ist der Mauszeiger unabhängig von der Systemauslastung, da sehr hoch priorisiert - im Gegensatz zu Linux.

rizor

  • Beiträge: 521
    • Profil anzeigen
Gespeichert
Du kannst für jeden Scheduleralgorithmus ein Verfahren konstruieren, mit dem er unglaublich schlecht performt.

Natuerlich kannst du das machen, aber ich denke, dass es bei diesem Konzept ein reales Problem ist.

Ich denke, dass Threads und Prozesse getrennt betrachtet werden sollten. Der Kernel (Scheduler) teilt also Prozessen die CPU-Zeit zu, wenn ein Thread dieses Prozesses dann nix mehr zu tun hat, die Zeitscheibe des Prozesses aber noch nicht aufgebraucht ist, kommt der nächste Thread dieses Prozesses dran - bis entweder die Threads oder die Zeitscheibe alle sind.

Wenn mich nicht alles taeuscht, ist das eine extrem schlechte Art des Co/Gang-Schedulings, denn dieses Konzept bietet sich eigentlich nur auf Multicore-Systemen an, bei der dann die Prozesse die CPU-Zeit bekommen und die Threads eines Prozesses auf alle verfuegbaren CPUs gelegt werden.

Mit diesem Verfahren kannst du wenigstens die Anzahl an PD-Wechseln konstant halten (pro Zeitscheibe ein Wechsel), allerdings wird ein Prozess mit vielen Threads stark benachteiligt.

Ist das denn so ein groszer Vorteil, dass sich dadurch die anderen groszen Nachteile ignorieren lassen?

Unter Windows ist der Mauszeiger unabhängig von der Systemauslastung, da sehr hoch priorisiert - im Gegensatz zu Linux.

Naja, Windows und Linux unter Beachtung der GUI zu vergleichen ist nicht ganz fair fuer Linux ;)
Die GUI liegt ja komplett im Kernel-Space bei Windows und dann hat Windows ja auch noch den Turbo-Boost, den Prozesse erhalten, die momentan vom Benutzer verwendet werden. Also bei denen der GUI Fokus liegt.
Auszerdem verwenden Linux und Windows ja grundlegend verschiedene Scheduling-Algorithmen, wodurch ein Vergleich sehr schwer wird.
Programmiertechnik:
Vermeide in Assembler zu programmieren wann immer es geht.

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
Ich denke, dass Threads und Prozesse getrennt betrachtet werden sollten. Der Kernel (Scheduler) teilt also Prozessen die CPU-Zeit zu, wenn ein Thread dieses Prozesses dann nix mehr zu tun hat, die Zeitscheibe des Prozesses aber noch nicht aufgebraucht ist, kommt der nächste Thread dieses Prozesses dran - bis entweder die Threads oder die Zeitscheibe alle sind.
Wenn mich nicht alles taeuscht, ist das eine extrem schlechte Art des Co/Gang-Schedulings, denn dieses Konzept bietet sich eigentlich nur auf Multicore-Systemen an, bei der dann die Prozesse die CPU-Zeit bekommen und die Threads eines Prozesses auf alle verfuegbaren CPUs gelegt werden.
Was ich meinte ist, dass du die CPU-Zeit den Prozessen zuschlägst. Welche Threads des Prozesses dann von der Zeitscheibe profitieren, liegt darunter.

Das ist aber eine Designentscheidung.

Die GUI liegt ja komplett im Kernel-Space bei Windows und dann hat Windows ja auch noch den Turbo-Boost, den Prozesse erhalten, die momentan vom Benutzer verwendet werden. Also bei denen der GUI Fokus liegt.
Bei Windows NT 3.x und ab Vista ist die GUI wieder Userspace. Und auch Linux priorisiert interaktive Prozesse im Scheduling.

Auszerdem verwenden Linux und Windows ja grundlegend verschiedene Scheduling-Algorithmen, wodurch ein Vergleich sehr schwer wird.
Wären es identische Algorithmen, gäbe es nichts zu vergleichen.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
Hallo,


Mit diesem Verfahren kannst du wenigstens die Anzahl an PD-Wechseln konstant halten (pro Zeitscheibe ein Wechsel)
Bei den meisten Prozessen (nicht CPU-bound) dürften alle Threads blockiert sein, so das es eher Unsinn ist deren PD überhaupt zu laden. Ich persönlich bin der Meinung das sich der Scheduler nicht primär für die Prozesse sondern für die Threads interessieren sollte. Hier könnte man höchstens den Prozessen mit vielen (nicht blockierten) Threads einen negativen Bonus geben damit die nicht das ganze System zu stark blockieren können. Viel wichtiger ist es meiner Meinung nach dass das Aufwecken und wieder schlafen legen von Threads möglichst schnell geht, also der Scheduler seine Strategie möglichst flexibel und effizient schnell wechselnden Bedingungen anpassen kann. Das wäre z.B. bei asynchronen Ereignissen (HW-IRQs usw.) sehr wichtig um die gefühlte Interaktivität möglichst hoch zu halten. Heutige Computer sind im allgemeinen schnell genug das die meisten Programme eher als IO-Bound gelten und genau das sollte man entsprechend berücksichtigen.

allerdings wird ein Prozess mit vielen Threads stark benachteiligt.
Eben. Und gerade die Prozesse die stark CPU-Bound sind erzeugen ja oft auch viele Threads (meistens genau so viele wie CPUs vorhanden sind, falls eine gute Job-Library o.ä. verwendet wird) um möglichst viel von der verfügbaren endlichen CPU-Leistung ab zu bekommen.

Die Zeitscheibenlänge sollte IMHO so sein das ein normaler interaktiver Thread eher in die nächste Blockade läuft als ins Zeitscheibenende (auf aktuellen CPUs könnte das mit typischer SW durchaus unter 1 ms sein) so das diese Threads die Zeitscheibenlänge gar nicht zu spüren bekommen. Wenn die Zeitscheibe zu kurz ist bedeutet das vor allem das auch die interaktiven Threads stark ausgebremst werden. Für die CPU-Bound Threads wäre natürlich eine möglichst lange Zeitscheibe von Vorteil. Hier kommt dann vor allem die Situation wo mehr CPU-Bound-Threads als CPUs vorhanden sind ins Blickfeld. Da ist es wichtig die CPU-Zeit möglichst fair zu verteilen und um das einigermaßen gut hinzubekommen sollten die Zeitscheiben wieder nicht zu lang sein. Ein weiterer wichtiger Aspekt ist wie effizient die asynchronen interaktiven Threads sich vor die CPU-Bound-Threads drängeln können damit z.B. der Mauszeiger möglichst verzögerungsfrei über den Bildschirm bewegt werden kann.


Ist das denn so ein groszer Vorteil, dass sich dadurch die anderen groszen Nachteile ignorieren lassen?
IMHO Nein. Der Kontext-Wechsel besteht aus deutlich mehr als nur dem Laden eines neuen PD und gerade beim PD gibt es ja noch ein paar extra Tricks in der Trickkiste wie z.B. globale Pages. Außerdem könnten die CPU-Hersteller versuchen den TLB-Flush möglichst einzudämmen indem z.B. das PD (also der Wert im CR3) mit in die Tag-Infos kommt damit der TLB von mehreren Prozessen nutzbar wäre (zumindest bei den recht großen L2-TLBs heutiger CPUs könnte das IMHO echt was nützen).


Wären es identische Algorithmen, gäbe es nichts zu vergleichen.
Und wir hätten nichts zum diskutieren. ;)


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

rizor

  • Beiträge: 521
    • Profil anzeigen
Gespeichert
« Antwort #10 am: 02. April 2011, 17:33 »
Wären es identische Algorithmen, gäbe es nichts zu vergleichen.
Und wir hätten nichts zum diskutieren. ;)

Stimmt, da habe ich nicht wirklich weit gedacht ;)

Ich denke, dass Threads und Prozesse getrennt betrachtet werden sollten. Der Kernel (Scheduler) teilt also Prozessen die CPU-Zeit zu, wenn ein Thread dieses Prozesses dann nix mehr zu tun hat, die Zeitscheibe des Prozesses aber noch nicht aufgebraucht ist, kommt der nächste Thread dieses Prozesses dran - bis entweder die Threads oder die Zeitscheibe alle sind.
Wenn mich nicht alles taeuscht, ist das eine extrem schlechte Art des Co/Gang-Schedulings, denn dieses Konzept bietet sich eigentlich nur auf Multicore-Systemen an, bei der dann die Prozesse die CPU-Zeit bekommen und die Threads eines Prozesses auf alle verfuegbaren CPUs gelegt werden.
Was ich meinte ist, dass du die CPU-Zeit den Prozessen zuschlägst. Welche Threads des Prozesses dann von der Zeitscheibe profitieren, liegt darunter.

Das ist aber eine Designentscheidung.

Den Prozessen die CPU-Zeit zu geben macht aber nur bei einem mehrdimensionalen Scheduler sinn.
Nur momentan denkt vermutlich keiner von uns soweit einen Scheduler zu schreiben, der ueber die Zeit und ueber die CPUs Scheduling betreibt. Soweit ich das weisz macht das momentan nur Apple (aber auch nicht immer). Aber dabei bin ich mir nicht mal sicher. Meine Quelle ist da ein ganz groszer Apple-Liebhaber.

Ansonsten macht das wirklich nicht viel Sinn und die Scheduler sollten nur ueber die Zeit entscheidn und somit besser nur Threads beachten.
Programmiertechnik:
Vermeide in Assembler zu programmieren wann immer es geht.

RedEagle

  • Beiträge: 244
    • Profil anzeigen
    • RedEagle-OperatingSystem - Projekt
Gespeichert
« Antwort #11 am: 03. April 2011, 11:39 »
Hm… also nochmal zusammengefasst:

Scheduler und Prozessmanager trenne - käme meinem ursprünglichen Gedanken auch nah und wird sowieso von den Meisten so gemacht :D

Aber was die konstanten Zeitschlitze pro Prozess angeht, da bin ich noch nicht so glücklich mit… Wie bereits Svenska schrieb werden Prozesse mit vielen Threads da sehr benachteiligt. Ich würde da dann gar nicht mehr zwischen Prozess und Thread unterscheiden wollen - alles Tasks, alle eine von ihrer Priorität abhängig konstante Laufzeit.
Man kann dann immer noch, eine globale Laufzeit festlegen - also wenn alle Threads zusammen weniger als eine gewisse Zeit liefen kann den Rest IDLE bekommen. Laufen so viele Threads dass diese Zeit nicht mehr ausreicht, wird so viel Zeit für das Durchlaufen der Task bereit gestellt wie nötig…

Mein jetziger geistiger Entwurf: :D
Im Prozessmanager: Liste von Prozessen, jeder Prozess enthält eine Liste von Threads
Soll ein Thread laufen wird dieser von Prozessmanager in eine weitere Liste geschoben welche von Scheduler durchgegangen wird und den Thread dann entsprechend ausführt.
Soll er nicht mehr laufen, wird er wieder auch der Liste des Schedulers entfernt.

kevin

  • Administrator
  • Beiträge: 2 767
    • Profil anzeigen
Gespeichert
« Antwort #12 am: 03. April 2011, 12:05 »
Pro Prozess Zeit verteilen würde ich auch nicht machen. Warum sollte man fork() oder ähnliche Mechanismen gegenüber Threads bevorzugt behandeln? Wenn überhaupt, könnte man versuchen, top-down über den ganzen ProzessTaskbaum CPU-Anteile zu verteilen.
Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.

rizor

  • Beiträge: 521
    • Profil anzeigen
Gespeichert
« Antwort #13 am: 07. April 2011, 13:06 »
Aber was die konstanten Zeitschlitze pro Prozess angeht, da bin ich noch nicht so glücklich mit… Wie bereits Svenska schrieb werden Prozesse mit vielen Threads da sehr benachteiligt. Ich würde da dann gar nicht mehr zwischen Prozess und Thread unterscheiden wollen - alles Tasks, alle eine von ihrer Priorität abhängig konstante Laufzeit.
Man kann dann immer noch, eine globale Laufzeit festlegen - also wenn alle Threads zusammen weniger als eine gewisse Zeit liefen kann den Rest IDLE bekommen. Laufen so viele Threads dass diese Zeit nicht mehr ausreicht, wird so viel Zeit für das Durchlaufen der Task bereit gestellt wie nötig…

Das ist aber auch nciht wirklich gut. Wenn du mehr Threads hast als Zeit noetig ist, wuerde ich einfach extrem viele Threads generieren und somit sehr viel Rechenzeit bekommen.
Mit diesem Konzept kann man verdammt viel Unfug treiben.
Falls du an dem Konzept festhalten möchtest, würde ich das aber für SMP/SMT optimieren.
Dann kann jede CPU einn Prozess durchführen.
Ich würde dir aber empfehlen, dass die die Prozesse egal sind.
Sie sollten dir vllt die Priorität für deine Threads definieren und den ganzen anderen kram, aber der Schedluer sollte nichts von Prozessen wissen.
Programmiertechnik:
Vermeide in Assembler zu programmieren wann immer es geht.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #14 am: 08. April 2011, 20:55 »
Hallo,


Das ist aber auch nciht wirklich gut. Wenn du mehr Threads hast als Zeit noetig ist, wuerde ich einfach extrem viele Threads generieren und somit sehr viel Rechenzeit bekommen.
Mit diesem Konzept kann man verdammt viel Unfug treiben.
Das machen aber alle aktuellen OSe so oder so ähnlich. Ja, damit kann man theoretisch ein System extrem in die Knie zwingen bzw. zumindest alles was die selbe oder eine niedrigere Priorität hat als der Schadprozess nahezu blockieren. Um eben das zu verhindern oder zumindest abzumildern versuchen ja die ganz aktuellen OSe die CPU-Zeit über den Prozessbaum möglichst fair zu verteilen, so wie taljeth das auch meinte, dadurch werden zumindest die anderen Programme nicht total ausgebremst.

Ein zweiter Aspekt, der gerade für Micro-Kernel-OSe von großer Bedeutung ist, ist wie die CPU-Verteilung erfolgen soll wenn ein Ausführungspfad den Prozess wechselt (also wenn RPC bzw. synchrones IPC benutzt wird und der Caller blockiert bis der Callee fertig ist, dabei bleibt ja die Anzahl der runnable Threads konstant aber die sind dann anders über die Prozesse verteilt). Hier gibt es 2 gegenläufige Interessen: zum einen soll der Thread im Service (Callee) nicht plötzlich eine höhere Priorität haben als der ursprüngliche Client (Caller) damit ein Low-Priority-Task nicht plötzlich wichtiger wird als er eigentlich ist aber es soll auch nicht passieren das ein Low-Priority-Caller einen High-Priority-Caller blockiert weil der erste eine Ressource in Besitzt hat aber vom Scheduler nicht aufgerufen wird also Prioritätsinversion.


Einen Scheduler so zu implementieren das er diese 2 Probleme (faire Verteilung der CPUs über den Prozess-Baum und effiziente Behandlung von RPC/IPC) gut löst ist sicher eine echte Herausforderung. IMHO sind alle derzeit existierenden Scheduler nur Kompromisslösungen (von Speziallösungen für bekannte und geschlossene Systeme mal abgesehen), ob man das überhaupt wirklich gut lösen kann muss wohl erst noch bewiesen werden.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

rizor

  • Beiträge: 521
    • Profil anzeigen
Gespeichert
« Antwort #15 am: 08. April 2011, 21:55 »
Das ist aber auch nciht wirklich gut. Wenn du mehr Threads hast als Zeit noetig ist, wuerde ich einfach extrem viele Threads generieren und somit sehr viel Rechenzeit bekommen.
Mit diesem Konzept kann man verdammt viel Unfug treiben.
Das machen aber alle aktuellen OSe so oder so ähnlich. Ja, damit kann man theoretisch ein System extrem in die Knie zwingen bzw. zumindest alles was die selbe oder eine niedrigere Priorität hat als der Schadprozess nahezu blockieren. Um eben das zu verhindern oder zumindest abzumildern versuchen ja die ganz aktuellen OSe die CPU-Zeit über den Prozessbaum möglichst fair zu verteilen, so wie taljeth das auch meinte, dadurch werden zumindest die anderen Programme nicht total ausgebremst.

Ich weiß nicht, was Windows macht, aber Linux verteilt die Zeit nicht über die Prozesse, sondern über die Threads. Er baut sich pro CPU Bäume auf, die anhand der verbracuhten CPU-Zeiten sortiert sind.
Es stimmt schon, dass in dem Fall eine Thread-Bomb auch viel Schaden anrichten kann, aber das blockt der Kernel glaub ich irgendwo anders.
Damit das Ausbremsen der anderen Threads nicht so schlimm ist, gibt es da ja dann noch die CGroups. Die verhindern diesen Schaden, falls der neuste Kernel mit seinem "Wunderpatch" verwendet wird.

Gruß,
rizor
Programmiertechnik:
Vermeide in Assembler zu programmieren wann immer es geht.

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #16 am: 16. August 2011, 15:37 »
Hallo,

um die Leiche dieses Threads zu zerfleddern, schenke ich euch hier drei Links. ;-)

Linux benutzt den CFS (Completely Fair Scheduler), der sehr komplex ist, wunderbar skaliert und viele tolle Features (z.B. cgroups) anbietet. Es gibt ein weiteres Konzept, den BFS (Brain Fuck Scheduler), der nicht besonders toll skaliert, diese Features alle nicht hat - aber für niedrige Latenzen und relativ wenige logische CPUs schneller ist.

Hier gibt es die Funktionsbeschreibung.
Hier gibt es die FAQ dazu.
Hier gibt es ein paar Benchmark-Ergebnisse (verglichen mit CFS) dazu.

Was ich damit sagen will: Ein simpler Scheduler, der die meisten Probleme die wir hier diskutieren ignoriert, kann durchaus gut performen. ;-)

Gruß,
Svenska
« Letzte Änderung: 16. August 2011, 15:40 von Svenska »

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #17 am: 06. November 2011, 19:30 »
Hallo,

um die Leiche dieses Threads noch weiter zu zerfleddern, schenke ich euch noch einen Link. ;-)

Diesmal geht es um den ULE-Scheduler, der von FreeBSD entwickelt und verwendet wird und dort der Nachfolger des 4BSD-Schedulers ist. Eine kurze Beschreibung, wie der grob funktioniert, gibt es dort auch und es wird (aber nur wenig) mit anderen Schedulern verglichen. Er nimmt auf SMP und auch SMT (HT) ein bisschen Rücksicht.

Das Paper (von 2003) gibt es hier.

Gruß,
Svenska

 

Einloggen