Welcher Planungsalgorithmus wird unter Linux verwendet?

Kürzlich wurde ich in einem Interview nach dem Planungsalgorithmus gefragt, der vom Linux-Betriebssystem verwendet wird. Was ist der verwendete Algorithmus, warum?

In welchem ​​Algorithmus wird Echtzeit-Betriebssysteme verwendet und warum?

Der aktuelle Linux-Taskplaner heißt Completely Fair Scheduler (CFS). Weitere Informationen finden Sie unter http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt . Das Design ist recht komplex und meiner Meinung nach nicht für RTOS geeignet.

Eine in Echtzeitsystemen übliche Technik ist die ratenmonotone Planung, da sie starke Garantien bietet, wenn bestimmte Annahmen zutreffen (z. B. statische Aufgabenprioritäten und feste Ausführungszeit und -rate). Es gibt viele andere Algorithmen und es wurde viel geforscht. Im Grunde geht es also nur um die Eigenschaften, die Sie benötigen, und um das, was Sie über Ihre Aufgabe wissen und was behoben ist.

Ich bin mir nicht ganz sicher, ob Sie sich mit der E / A-Planung des Kernels befassen. Falls Sie dies nicht tun: Ignorieren Sie diese Antwort.

Wikipedia gibt an, dass die CFG (vollständig Fair Queuing) seit Kernel 2.6.18 Standard ist.

Auf meinem openSUSE (mit Kernel 2.6.37) kann ich zwischen CFG, NOOP und Deadline wechseln .

Der Round Robin-Algorithmus wird im Allgemeinen in Time-Sharing-Umgebungen verwendet.

Der vom Linux-Scheduler verwendete Algorithmus ist ein komplexes Schema mit einer Kombination aus präemptiver Priorität und voreingenommenem Time Slicing. Es weist Aufgaben mit höherer Priorität ein längeres Zeitquantum und Aufgaben mit niedrigerer Priorität ein kürzeres Zeitquantum zu.

Es identifiziert jeden Prozess entweder als Echtzeitprozess oder als normalen (anderen) Prozess. Echtzeitaufgaben werden statische Prioritäten im Bereich [0,99] zugewiesen, wobei eine niedrigere Zahl eine höhere Priorität anzeigt.

Alle anderen Aufgaben haben dynamische Prioritäten im Bereich [100, 139], basierend auf der Interaktivität einer Aufgabe, die auf ihren netten Werten plus oder minus dem Wert 5 basieren. Aufgaben, die interaktiver sind, haben normalerweise längere Schlafzeiten und sind daher wahrscheinlicher Anpassungen näher an −5 vornehmen, da der Scheduler interaktive Aufgaben bevorzugt. (Die Interaktivität einer Aufgabe wird dadurch bestimmt, wie lange sie während des Wartens auf E / A geschlafen hat.) Die Interaktivität einer Aufgabe bestimmt, ob der Wert 5 zum netten Wert addiert oder von diesem subtrahiert wird. Das Ergebnis solcher Anpassungen werden höhere Prioritäten für diese Aufgaben sein. Umgekehrt sind Aufgaben mit kürzeren Ruhezeiten häufig stärker an die CPU gebunden und haben daher niedrigere Prioritäten.

Der Kernel verwaltet eine Liste aller ausführbaren Aufgaben in einer Runqueue-Datenstruktur. Eine Runqueue enthält zwei Prioritätsarrays: aktiv und abgelaufen. Das aktive Array enthält alle Aufgaben, deren verbleibende Zeit in ihren Zeitscheiben verbleibt, und das abgelaufene Array enthält alle abgelaufenen Aufgaben. Jedes dieser Prioritätsarrays enthält eine Liste von Aufgaben, die nach Priorität indiziert sind. Der Scheduler wählt aus dem aktiven Array die Aufgabe mit der höchsten Priorität für die Ausführung auf der CPU aus. Wenn alle Aufgaben ihre Zeitscheiben erschöpft haben (dh das aktive Array ist leer), werden die beiden Prioritätsarrays ausgetauscht: Das abgelaufene Array wird zum aktiven Array und umgekehrt.

Die dynamische Priorität einer Aufgabe wird neu berechnet, wenn die Aufgabe ihr Zeitquantum erschöpft hat und in das abgelaufene Array verschoben werden soll. Wenn also die beiden Arrays ausgetauscht werden, wurden allen Aufgaben in dem neuen aktiven Array neue Prioritäten und entsprechende Zeitscheiben zugewiesen. (Hinweis: Dies ist ein Auszug aus dem Buch über Betriebssystemkonzepte (9. Ausgabe) von Abraham Silberschatz et al. Für Einzelheiten siehe Abschnitt 5.6.3 dieses Buches.)

Dies ist eine Antwort auf Ihre andere Frage. Es gibt zwei Arten von Echtzeitsystemen (RTS): hart und weich. Der CPU-Planungsalgorithmus für hartes RTS ist ein prioritätsbasierter präemptiver Algorithmus und der für weiches RTS ist eine nicht präemptive Priorität.