Thema: Schedulingstrategien

[FlashBurn]

So nun mal zu einem interessanten Thema

Richtig interessant sind die ja erst auf Multi-CPU Systemen.

Ich nutze im Moment noch eine Queue wo sich alle CPUs bedienen. Ich weiß das es durchaus zu Engpäßen kommen kann, aber ich habe halt noch keine bessere Strategie gefunden mit der ich leben kann (und welche ich verstehe, das ist Voraussetzung).

Ich würde also gerne mal hören was ihr so für Strategien auf 1-CPU oder Multi-CPU System nutzen würdet/nutzt.

[rizor]

Du könntest für jeden Kern deine eigene Queue verwenden und dadurch gleichzeitig für eine gleichmäßige Verteilung sorgen.
Kann natürlich sehr unhandlich werden, wäre aber vllt eine erste Optimierung

[FlashBurn]

Das ist immer das erste was ich höre und damit habe ich ein Problem. Denn soweit ich mir das vorstellen kann gibt es nur genauso viele oder sogar mehr Probleme!

Einmal musst du ja irgendwie in die Queues einfügen können, also kann es an der Stelle schonmal passieren das du gerade in einer Queue was einfügst (von einer anderen CPU aus) und die CPU der die Queue gehört möchte den nächsten Thread aus dieser Queue haben, also muss die CPU warten. Toll das mache ich schon mit meiner einen Queue, also schonmal nen Minuspunkt (ich lasse mich hier aber gerne eines besseren belehren).

Dann kommt mein klassisches Bsp. CPU0 hat gerade nen Thread mit Prio 30 am Laufen und der nächste Thread hat Prio 28. Auf CPU1 läuft gerade ein Thread mit Prio 29 und der nächste hat die Prio 27. Während der Thread auf CPU0 noch viel Zeit hat und läuft, kommt auf CPU1 der Scheduler und lässt den Thread mit Prio 27 laufen, aber eigentlich müsste der Thread mit der Prio 28 laufen, der er wichtiger ist, aber er ist ja in der Queue auf der anderen CPU (nämlich CPU0). Also ist das nicht mehr sehr gerecht, um es gerecht zu machen müsste man nen ganz schönen Aufwand betreiben und da glaube ich ist mein Algo mit nur einer Queue noch am Besten.

Aber wie gesagt ich lasse mich gerne eines besseren belehren!

[Svenska]

Hallo,

elegant wäre es schon, je CPU eine Queue zu haben.

Wichtig ist es, möglichst lange den einzelnen Prozess auf einer CPU ausführen zu lassen, wenn du ständig die CPUs wechselst, verlierst du die Cache-Inhalte. Auf einer Mehrkern-CPU (wo der Cache von den Kernel geteilt wird) ist es besser, die Kernel gleichmäßig auszulasten, da du damit die thermische Erhitzung eher über das Die verteilst und die (mechanischen) Spannungen geringer sind. Das erhöht die Lebensdauer.

Was man davon allerdings wie stark berücksichtigen muss, weiß ich nicht.

Mein Vorschlag wäre eine große Queue pro Priorität, und zusätzlich noch eine Queue je CPU, um gewisse Prozesse auf dieser CPU festhalten zu können (bzw. auch einen Prozess von einer CPU auf eine andere verschieben zu können).

Damit kannst du neu entstehende Prozesse der CPU zuteilen, die gerade frei ist, und wenn eine CPU frei geworden ist, holst du dir aus dem Aufgabenpool den nächsten Prozess. Wenn ein Prozess blockt, wird er in den gemeinsamen Pool geschoben, wenn er seine Zeitscheibe aufgebraucht hat, landet er wieder in der CPU-eigenen Queue.

Auf einem normalen System haben die meisten Prozesse die gleiche Priorität, und viele verschiedene Prioritäten gibt es auch nicht (mein Hostlinux: boinc* hat 39, der Kernel hat RT, udev 16 und der Rest 20 ==> 4 verschiedene). Die Prioritätsinversion kann damit nur selten auftreten.

Gruß,
Svenska

[FlashBurn]

elegant wäre es schon, je CPU eine Queue zu haben.

Ich weiß, ich habe halt nur noch keinen Algorithmus gefunden der mir zusagt

Wichtig ist es, möglichst lange den einzelnen Prozess auf einer CPU ausführen zu lassen, wenn du ständig die CPUs wechselst, verlierst du die Cache-Inhalte.

Ich würde jetzt erstmal wissen wollen, was du unter einem Prozess verstehst.

Mein Vorschlag wäre eine große Queue pro Priorität, und zusätzlich noch eine Queue je CPU, um gewisse Prozesse auf dieser CPU festhalten zu können (bzw. auch einen Prozess von einer CPU auf eine andere verschieben zu können).

In gewisser Weise habe ich das schon, mir fehlt nur noch die Queue per CPU. Nur bin ich noch von dem einen Prozess auf einer CPU "festpinnen" nicht so richtig überzeugt. Ich wüsste jetzt spontan nicht mal wofür das gut sein sollte.

Damit kannst du neu entstehende Prozesse der CPU zuteilen, die gerade frei ist, und wenn eine CPU frei geworden ist, holst du dir aus dem Aufgabenpool den nächsten Prozess. Wenn ein Prozess blockt, wird er in den gemeinsamen Pool geschoben, wenn er seine Zeitscheibe aufgebraucht hat, landet er wieder in der CPU-eigenen Queue.

Klingt erstmal nicht schlecht, aber dadurch könnte es auch passieren das eine CPU 2 Threads hat und ne andere gar keine, weil die 2 Threads immer ihre Zeitscheibe aufbrauchen. In dem Moment wär es also besser wenn einer der beiden Threads in die globale Queue geschoben wird und dann die CPU die gar keine hat sich diesen nehmen kann. Wo wir wieder bei meinem ein Queue System wären, was in dem Moment wahrscheinlich effektiver wäre. Genauso hast du da die selben Problem die ich auch schon mit nur einer Queue habe (das andere CPUs eventuell warten müssen bis sie auf die globale Queue zugreifen können).

Auf einem normalen System haben die meisten Prozesse die gleiche Priorität, und viele verschiedene Prioritäten gibt es auch nicht (mein Hostlinux: boinc* hat 39, der Kernel hat RT, udev 16 und der Rest 20 ==> 4 verschiedene). Die Prioritätsinversion kann damit nur selten auftreten.

soweit ich weiß hat Linux 256(??) Prioritäten (-127 bis 128). Auch verwendet er (wie ich) dynamische Prioritäten (war so als ich das letzte mal geguckt habe), wird also durchaus verschiedene Prios geben. Vorallem auf meinem OS (so wie es mir momentan vorschwebt) wird es unterschiedliche geben (im Bereich von 10 bis 20) und ich würde auch diesen "seltenen" Fall gerne vermeiden. Außerdem kann ich ja vorher nicht wissen was für Programme mit welchen Prios auf meinem System laufen.

Du merkst schon, ist ein schwieriges Thema für mich

[Svenska]

Hallo,

Wichtig ist es, möglichst lange den einzelnen Prozess auf einer CPU ausführen zu lassen, wenn du ständig die CPUs wechselst, verlierst du die Cache-Inhalte.

Ich würde jetzt erstmal wissen wollen, was du unter einem Prozess verstehst.

Auch Tasks. Oder auch Threads, genaueres ist Definitionsfrage.

Nur bin ich noch von dem einen Prozess auf einer CPU "festpinnen" nicht so richtig überzeugt. Ich wüsste jetzt spontan nicht mal wofür das gut sein sollte.

Damit kannst du ein vorhersehbareres Zeitverhalten fördern oder Prozesse, die sehr stark cachelastig sind und sonst ständig die CPU wechseln würden, daran hindern. Außerdem, wenn du zwei stark CPU-lastige Prozesse am Laufen hast und die auf je eine CPU festpinnst, hast du eine bessere (gleichmäßigere) Grundauslastung. Nennt sich unter Linux CPU-Affinität.

Wenn du einen Core frei von den üblichen Anwendungen (außer einer zeitkritischen) hast, dann bekommst du Near-Realtime allein im Userspace.

Damit kannst du neu entstehende Prozesse der CPU zuteilen, die gerade frei ist, und wenn eine CPU frei geworden ist, holst du dir aus dem Aufgabenpool den nächsten Prozess. Wenn ein Prozess blockt, wird er in den gemeinsamen Pool geschoben, wenn er seine Zeitscheibe aufgebraucht hat, landet er wieder in der CPU-eigenen Queue.

Klingt erstmal nicht schlecht, aber dadurch könnte es auch passieren das eine CPU 2 Threads hat und ne andere gar keine, weil die 2 Threads immer ihre Zeitscheibe aufbrauchen.

Wenn eine CPU wartet und die andere CPU noch Aufgaben zu erledigen hat, kann man die ja verschieben. Man weist also einer CPU ihre Prozesse zu und wenn sich die Aufteilung als schlecht erweist, wird nachträglich geändert. Das sollte auch recht sinnvoll skalieren.

In dem Moment wär es also besser wenn einer der beiden Threads in die globale Queue geschoben wird und dann die CPU die gar keine hat sich diesen nehmen kann.

Oder, dass sich die leerlaufende CPU bei anderen CPUs bedient. Wenn auf jeder CPU Prozesse laufen, die ihre Zeitscheibe aufbrauchen, dann passiert nichts, da der Scheduler ja über alle CPUs hinweg gleichzeitig die Zuteilung vornimmt.

Wo wir wieder bei meinem ein Queue System wären, was in dem Moment wahrscheinlich effektiver wäre. Genauso hast du da die selben Problem die ich auch schon mit nur einer Queue habe (das andere CPUs eventuell warten müssen bis sie auf die globale Queue zugreifen können).

Die globale Queue wäre für mich ein zentraler Aufgabenpool für Prozesse, die ihre Zeitscheibe nicht aufgebraucht haben - die damit also nur selten aufgerufen werden. CPUs, die ausgelastet sind, laufen also selbstständig ihre Prozesse ab und belasten die Hauptqueue nicht.

Eventuell sollte man den Scheduler mit einer gewissen Weitsicht ausstatten und selbst auf eine CPU festpinnen, so dass er die CPU-Zuteilung zentral regeln kann (und zwar so, dass er bereits die zukünftigen Zeitscheiben verteilt). Das benachteiligt interaktive Prozesse allerdings stark, so dass die Hauptqueue bevorzugt abgearbeitet werden muss; sie sollte aber die meiste Zeit leer oder sehr kurz sein (Prozesse, die ihre Zeitscheibe nicht aufbrauchen, brauchen meist die folgenden Zeitscheiben auch nicht).

Auf einem normalen System haben die meisten Prozesse die gleiche Priorität, und viele verschiedene Prioritäten gibt es auch nicht (mein Hostlinux: boinc* hat 39, der Kernel hat RT, udev 16 und der Rest 20 ==> 4 verschiedene). Die Prioritätsinversion kann damit nur selten auftreten.

soweit ich weiß hat Linux 256(??) Prioritäten (-127 bis 128). Auch verwendet er (wie ich) dynamische Prioritäten (war so als ich das letzte mal geguckt habe), wird also durchaus verschiedene Prios geben. Vorallem auf meinem OS (so wie es mir momentan vorschwebt) wird es unterschiedliche geben (im Bereich von 10 bis 20) und ich würde auch diesen "seltenen" Fall gerne vermeiden. Außerdem kann ich ja vorher nicht wissen was für Programme mit welchen Prios auf meinem System laufen.

Prioritätsinversion kannst du vermeiden, indem du beispielsweise für jeden Durchlauf der hohen Prioritätsqueue (mind.) einen Eintrag der niederen Priorität ausführst und so ein Verhungern vermeidest. Solange du aber keine tausende Prozesse auf deinem System laufenlassen möchtest, die alle verschiedene Prioritäten haben, bleibt es ein relativ seltenes Ereignis.

Es gibt Anwendungsfälle, die jeden Scheduler ineffizient machen. Bei nur zwei CPUs ist es sinnvoll, den Scheduler - auf Kosten des Durchsatzes - selbst zu verteilen, um eine bessere Auslastung zu bekommen. Bei sehr vielen CPUs ist es wieder sinnvoller, den Scheduler selbst auf eine CPU festzunageln, um den Durchsatz zu steigern. Der "wandernde" Scheduler führt dort zu größeren Verlusten.

Du merkst schon, ist ein schwieriges Thema für mich

Joa, aber ich möchte ja auch etwas bei lernen.

Gruß,
Svenska

[FlashBurn]

Auch Tasks. Oder auch Threads, genaueres ist Definitionsfrage.

Ich sag jetzt mal du bist genau in die "Falle" gelaufen die ich dir stellen wollte

Wenn du jetzt nämlich sagst das du einen Task (und damit verstehe ich dann sämtliche Threads des Tasks) möglichst lange auf einer CPU laufen lassen möchtest, wozu dann Multithreading? Dann kannst du dir den ganzen Quatsch auch sparen, denn Multithreading kann nur effektiv sein, wenn die Threads wirklich parallel laufen und nicht nur scheinbar parallel!

Wenn eine CPU wartet und die andere CPU noch Aufgaben zu erledigen hat, kann man die ja verschieben. Man weist also einer CPU ihre Prozesse zu und wenn sich die Aufteilung als schlecht erweist, wird nachträglich geändert. Das sollte auch recht sinnvoll skalieren.

Genau mit diesem Verschieben, habe ich so meine Probleme! Erstmal hast du da wie gesagt das Problem, das du in dem Moment wo du mit der Queue einer anderen CPU rumspielst, diese durch einen Lock schützen musst und das dann diese CPU warten muss (wenn sie gerade im Scheduler ist) bis du den Lock wieder freigibst. Dann kommt auch noch der ganze Aufwand um die Threads hin und her zu schieben und die richtige CPU zu finden dazu. Ich behaupte jetzt das dieser ganze Overhead meine eine globale Queue effizienter erscheinen lässt (ohne das theoretisch und praktisch beweisen zu können, ist nur mein Eindruck).

Eventuell sollte man den Scheduler mit einer gewissen Weitsicht ausstatten und selbst auf eine CPU festpinnen, so dass er die CPU-Zuteilung zentral regeln kann (und zwar so, dass er bereits die zukünftigen Zeitscheiben verteilt). Das benachteiligt interaktive Prozesse allerdings stark, so dass die Hauptqueue bevorzugt abgearbeitet werden muss; sie sollte aber die meiste Zeit leer oder sehr kurz sein (Prozesse, die ihre Zeitscheibe nicht aufbrauchen, brauchen meist die folgenden Zeitscheiben auch nicht).

Das musst du mir genauer erklären. Ich meine der Scheduler muss in dem Sinne auf jeder CPU laufen, zumindest um einen Thread, dessen Zeitscheibe abgelaufen ist, wieder in die Queue zu packen und einen neuen raus zu holen. Das einzigste was ich jetzt darunter noch verstehen würde, ist das man den Scheduler der die ganze rechnerei übernimmt welcher Thread auf welcher CPU laufen soll auf eine CPU gepinnt wird und die Scheduler auf den eigentlichen Arbeits CPUs nur noch mit ihrer eigenen Queue arbeiten (was sich aber meiner Meinung nach erst wirklich bei sehr vielen CPUs lohnt).

Prioritätsinversion kannst du vermeiden, indem du beispielsweise für jeden Durchlauf der hohen Prioritätsqueue (mind.) einen Eintrag der niederen Priorität ausführst und so ein Verhungern vermeidest. Solange du aber keine tausende Prozesse auf deinem System laufenlassen möchtest, die alle verschiedene Prioritäten haben, bleibt es ein relativ seltenes Ereignis.

Dieses oder ein ähnliches Prinzip verwendet glaub ich auch der Haiku-Scheduler.

Solch ein verhungern gibt es in meinem (momentanen) Scheduler nicht, weil ...

Ich habe ne Ready- und ne Run-Queue, ein neuer Thread kommt immer aus der Ready-Queue, ist seine Zeitscheibe aufgebraucht kommt er in die Run-Queue, ist die Ready-Queue leer, wird geguckt ob in der Run-Queue Threads drin sind, ist das der Fall werden die beiden Queues vertauscht und der Spaß geht wieder von Vorne los. Sind beide Queues leer, wird meine Idle-Queue durchgelaufen, ist auch diese leer, wird der Idle-Thread genommen (was bei mir besonders effizient abläuft).

[Svenska]

Hallo,

Auch Tasks. Oder auch Threads, genaueres ist Definitionsfrage.

Ich sag jetzt mal du bist genau in die "Falle" gelaufen die ich dir stellen wollte

"Prozess" ist mit Absicht allgemein ausgedrückt. Dazu gehören Tasks, aber eben auch - sofern sie unterstützt werden - Threads.

Wenn du jetzt nämlich sagst das du einen Task (und damit verstehe ich dann sämtliche Threads des Tasks) möglichst lange auf einer CPU laufen lassen möchtest, wozu dann Multithreading?

Ich redete ursprünglich von Prozessen. Tasks sind Prozesse in diesem Sinne, Threads auch. Mir ist schon klar, wozu Multithreading gut ist. Ob man Threads grundsätzlich sinnvoll findet, ist eine andere Frage.

Eventuell sollte man den Scheduler mit einer gewissen Weitsicht ausstatten und selbst auf eine CPU festpinnen, so dass er die CPU-Zuteilung zentral regeln kann (und zwar so, dass er bereits die zukünftigen Zeitscheiben verteilt). Das benachteiligt interaktive Prozesse allerdings stark, so dass die Hauptqueue bevorzugt abgearbeitet werden muss; sie sollte aber die meiste Zeit leer oder sehr kurz sein (Prozesse, die ihre Zeitscheibe nicht aufbrauchen, brauchen meist die folgenden Zeitscheiben auch nicht).

Das musst du mir genauer erklären. Ich meine der Scheduler muss in dem Sinne auf jeder CPU laufen, zumindest um einen Thread, dessen Zeitscheibe abgelaufen ist, wieder in die Queue zu packen und einen neuen raus zu holen. Das einzigste was ich jetzt darunter noch verstehen würde, ist das man den Scheduler der die ganze rechnerei übernimmt welcher Thread auf welcher CPU laufen soll auf eine CPU gepinnt wird und die Scheduler auf den eigentlichen Arbeits CPUs nur noch mit ihrer eigenen Queue arbeiten (was sich aber meiner Meinung nach erst wirklich bei sehr vielen CPUs lohnt).

Genau so hatte ich das gemeint. Der eigentliche Scheduler ist auf einer CPU festgepinnt, während die CPUs sich aus ihren eigenen Queues bedienen können, ohne sich um den "großen" planenden Scheduler kümmern zu müssen.

Unter Scheduler in dem Zusammenhang verstehe ich nur den Teil, der sich um Planung und Verwaltung kümmert.

Ich habe ne Ready- und ne Run-Queue, ein neuer Thread kommt immer aus der Ready-Queue, ist seine Zeitscheibe aufgebraucht kommt er in die Run-Queue, ist die Ready-Queue leer, wird geguckt ob in der Run-Queue Threads drin sind, ist das der Fall werden die beiden Queues vertauscht und der Spaß geht wieder von Vorne los. Sind beide Queues leer, wird meine Idle-Queue durchgelaufen, ist auch diese leer, wird der Idle-Thread genommen (was bei mir besonders effizient abläuft).

Das klingt alles prioritätsfrei, da du alle Threads, die gerade lauffähig sind, in einem Round Robin auch ausführst. Erst die Ready-, dann die Run-Queue, eventuell ein Tausch, wieder von vorne. Sind beide leer => Idle.

Gruß,
Svenska

[FlashBurn]

Das klingt alles prioritätsfrei, da du alle Threads, die gerade lauffähig sind, in einem Round Robin auch ausführst. Erst die Ready-, dann die Run-Queue, eventuell ein Tausch, wieder von vorne. Sind beide leer => Idle.

Das könnte daran liegen, dass ich die hälfte vergessen habe

Mit Queue meine ich in dem Fall ein Array (mit 32 Einträgen => 32 Prioritäten). Zu jeder Queue gehört eine Bitmap damit ich weiß in welche Prio mind. 1 Thread ist. Das dürfte so ziemlich dem alten O(1) Scheduler von Linux entsprechen, ich fand das Konzept nicht schlecht und habe es mal ganz frech übernommen

ch redete ursprünglich von Prozessen. Tasks sind Prozesse in diesem Sinne, Threads auch. Mir ist schon klar, wozu Multithreading gut ist. Ob man Threads grundsätzlich sinnvoll findet, ist eine andere Frage.

Will man auch in Zukunft auch für aktuelle Systeme entwickeln, sollte man sich ganz schnell mit Multithreading anfreunden. Denn die Entwicklung geht in Richtung immer mehr Cores, aber dafür langsamer. Ohne Multithreading kommst du spätestens dann (obwohl das heute auch schon so ist) nicht sehr weit.

[erik.vikinger]

Hallo,


ich geb einfach auch mal meinen Senf dazu:


Für jede CPU eine eigene Queue finde ich persönlich eher ungeschickt, Gründe hat FlashBurn ja genug genannt. Bei einer globalen Queue muss man ja nicht unbedingt vom Anfang was wegnehmen, das heißt wenn CPU 0 gerade den nächsten Thread holen will und der erste Thread in der Queue ist aber auf CPU 1 festgepinnt dann wird eben weiter geschaut. Dazu müsste die Queue natürlich etwas komplexer sein, ich denke da an eine doppelt verkettete Liste und je einen Pointer auf den Anfang und das Ende. Für jede Priorität eine eigene Queue geht nur wenn es nicht zu viele Prioritäten gibt, ansonsten müsste man die eine Queue sortieren also beim Eintragen abgelaufener Threads diese an die richtige Stelle packen.

Von dem ganzen Planen welcher Thread auf welcher CPU laufen sollte halte ich auch nicht sehr viel, wenn man das wirklich ordentlich machen will dann muss man einiges berücksichtigen. Ein wichtiger Aspekt ist z.B. die Speicherlokalität, heutzutage gibt es ja Speicher an den die CPUs schnell rankommen (am eigenen Sockel angebunden) und Speicher der mit deutlich höheren Latenzen behaftet ist (an anderen Sockeln angebunden). Wenn man das aber ordentlich machen will muss das auch die Speicherverwaltung für die physischen Pages berücksichtigen (ich gehe da mal von einem klassischen Flat-Memory-System mit Paging aus) damit die Pages eines Prozesses nicht quer über den physischen Speicher zerstreut sind. Wenn dieser Prozess aber mit vielen Threads alle CPUs auslasten will dann wird es schon recht knifflig zu entscheiden in welchen physischen Speicher die Pages kommen sollen, allerhöchstens die Stacks könnte man passend ablegen.
Das mit der Cache-Effizienz sehe ich ebenfalls nicht so kritisch. Zum einen trifft das IMHO nur Threads die ihre Zeitscheibe komplett aufbrauchen, Threads die selber vorzeitig abgeben machen nur selten richtig CPU/Daten-intensive Dinge die in der nächsten Zeitscheibe wieder benötigt werden. Außerdem gibt es ja relativ schnelle Cache-to-Cache-Transfers.

Dynamische Zuweisung bestimmter Threads an bestimmte CPUs stelle ich mir wahrlich nicht einfach vor. Ein passender Algorithmus müsste schon reichlich komplex sein damit der auch wirklich was nutzt, aber dann kostet er selber einiges an CPU-Leistung. Wenn dazu jemand interessante Ideen hat dann würde ich die gerne mal lesen, mir fällt da jedenfalls nichts gescheites ein.

Ein weitere wichtiger Punkt ist das wenn man alle CPUs gleichmäßig auslastet das dann keine CPU sich schlafen legen kann. Hierfür eine passende Strategie zu finden nach der das OS sich eine oder mehrere CPUs aussucht welche dann abgeschaltet werden (um damit die anderen verbleibenden CPUs etwas zu beschleunigen, was wohl bald auch bei AMD klappt) ist sicher eine anspruchsvolle Aufgabe.

Das heutige Software viel zu wenig mit Prioritäten arbeitet ist leider Tatsache, da könnte man die gefühlte Performance des PC sicher noch etwas steigern.


Im ganzen betrachtet bin ich der Meinung das ein möglichst primitiver Scheduler der selber möglichst wenig CPU-Takte kostet die beste Variante ist. Komplexe Algorithmen die versuchen die Threadverteilung zur Laufzeit zu optimieren sind IMHO keine sinnvolle Option. Außerdem hab ich dafür noch keinen guten Algorithmus gesehen. Einzig fürs Powermanagement (einzelne CPU-Kerne abschalten) würde ich passenden Aufwand betreiben, aber das läuft ja unabhängig vom eigentlichen Scheduler in einem Low-Prio-Thread welcher sich nur auf Infos vom eigentlichen Scheduler stützt.


Grüße
Erik

[FlashBurn]

Für jede Priorität eine eigene Queue geht nur wenn es nicht zu viele Prioritäten gibt, ansonsten müsste man die eine Queue sortieren also beim Eintragen abgelaufener Threads diese an die richtige Stelle packen.

Ich habe 32 Prios (31 normale, 1 Realtime), dann noch eine Queue wo alle Threads drin sind die nur laufen sollen wenn nichts los ist und halt den klassischen Idlethread.
Nur mal um ein Bsp. zu haben. Mit 32 Prios kann man die Organisation ganz schnell und komfortabel machen (auf 32bit CPUs, auf 64bit CPUs sogar bis 64 Prios). Du nimmst einfach ne Bitmap in der "gesetzt" heißt in der Queue ist mind. 1 Thread. Du machst also einfach nen "bts eax,[bitmap]" und schon hast du in eax die höchste Prio in der ein Thread bereit steht. Das ist genau das Verfahren was damals im Linux O(1)-Scheduler verwendet wurde und ich fands gut und habs übernommen

Damit kann ich die Zeit die die Queues für andere CPUs gesperrt sind, minimieren. Ich habe dann noch 2 (mehr fallen mir grad nicht ein) andere Sachen damit es möglichst selten vorkommt das mehrere CPUs gleichzeitg auf die Queues zugreifen wollen. Das alles funktioniert noch einiger Maßen optimal auf heutigen CPUs (8 Cores), aber bei viel mehr dürfte auch dieser Algo ziemlich ineffizient werden, weil dann die Wahrscheinlichkeit steigt das mehrere CPUs auf die Queue wollen (obwohl ich das warten bis 30-40 Instruktion (wahrscheinlich eher weniger)) ausgeführt sind, jetzt nicht sonderlich lange finde. Auf 16 CPUs hochgerechnet (15 CPUs (die erste muss ja nicht warten) * 40Instruktionen * 2Takte pro Instruktion (worst-case)) macht das 1200Takte, bei 2GHz sind das 600ns die die letzte CPU warten muss, die zweite müsste in dem Fall 40ns warten. Ich weiß jetzt nicht wieviel Takte es dauert bis etwas aus dem RAM geladen wurde, aber es waren glaub ich etwas über 100. Also das sollte noch gehen. Vorallem kommt hinzu, selbst wenn dieser Fall eintreten sollte, dann dürfte er so schnell nicht wieder auftreten, weil es unwahrscheinlich ist (bei einer Zeitscheibe von 1ms) das irgendwelche Threads zur selben Zeit fertig werden (ich ignorier jetzt mal ganz stur, das die Threads ja auch abgeben können ).

Ansonsten kann ich erik nur zustimmen.

Was ich vielleicht noch sage, jetzt muss nur noch jemand kommen der es schafft einen Algo zu entwerfen, der Queues für jede CPU hat und das ganze rechnen welcher Thread auf welcher CPU läuft, sollte in max 1200Takten passieren. Dann wären die Algos eventuell ca. gleich (da bin ich mir grad nicht sicher, denn das Entscheiden, welcher Thread auf welcher CPU, dürfte öfter passieren als der worst-case bei meinem Algo).

[bscreator]

Also anfangen würd ich mit FIRST-COME-FIRST-SERVED oder ROUND-ROBIN, da die wohl zu den einfachsten gehören.

Aber die Idee mit mehreren Warteschlangen würde ich auch verwenden.