SCHED_DEADLINE

SCHED_DEADLINE ist ein CPU- Scheduler, der seit Linux-Kernel -Version 3.14verfügbar ist ^{[ 1 ] [ 2 ].} Er basiert auf den Algorithmen Earliest Deadline First (EDF) und Constant Bandwidth Server (CBS) ^{[ 3 ]} und unterstützt Ressourcenreservierungen: Jeder nach dieser Strategie geplante Task ist mit einem Budget Q (auch Laufzeit genannt ) und einer Periode P verknüpft. P entspricht der Anweisung an den Kernel, dass der Task alle P Zeiteinheiten auf jedem Prozessor Q Zeiteinheiten benötigt. Dadurch eignet sich SCHED_DEADLINE besonders für Echtzeitanwendungen wie Multimedia oder industrielle Steuerungssysteme. Hierbei entspricht P der minimalen Zeit zwischen zwei aufeinanderfolgenden Aktivierungen des Tasks und Q der maximalen Ausführungszeit, die für jede Aktivierung des Tasks benötigt wird.

Der Linux-Kernel enthält verschiedene Scheduler-Klassen. ^{[ 4 ]} Standardmäßig verwendet der Kernel den Completely Fair Scheduler (CFS), der in Kernel-Version 2.6.23 eingeführt wurde. ^{[ 5 ]} Intern ist diese Standard-Scheduler-Klasse auch als SCHED_NORMAL bekannt . Der Kernel enthält außerdem zwei POSIX-konforme ^{[ 6 ]} Echtzeit-Scheduling-Klassen namens SCHED_FIFO (Realtime First-In-First-Out ) und SCHED_RR (Realtime Round-Robin ), die beide Vorrang vor der Standardklasse haben. ^{[ 4 ]} Die Scheduling-Klasse SCHED_DEADLINE wurde mit Version 3.14 des Linux-Kernel-Mainline-Branch , veröffentlicht am 30. März 2014, zum Linux-Scheduler hinzugefügt ^{[ 7 ] [ 8 ]} und hat Vorrang vor allen anderen Scheduling-Klassen.

Der Standard-Scheduler CFS eignet sich hervorragend für verschiedene Anwendungsfälle. Beispielsweise priorisiert CFS bei der Kombination von Batch-Workloads wie langlaufenden Codekompilationen oder numerischen Berechnungen und interaktiven Anwendungen wie Desktop-Anwendungen, Multimedia-Anwendungen usw. die Batch-Aufgaben dynamisch zugunsten der interaktiven Aufgaben. Benötigt eine Anwendung jedoch einen vorhersehbaren und präzisen Zeitplan, muss sie in der Regel auf einen der anderen Echtzeit-Scheduler SCHED_RR oder SCHED_FIFO zurückgreifen . Diese verwenden eine feste Priorität für die Aufgabenplanung und deren Aufgaben werden vor allen Aufgaben der Klasse SCHED_NORMAL eingeplant .

Wenn Echtzeit-Workloads mit heterogenen Timing-Anforderungen auf demselben System kombiniert werden, besteht ein bekanntes Problem von SCHED_RR und SCHED_FIFO darin, dass, da diese auf Aufgabenprioritäten basieren, Aufgaben mit höherer Priorität, die länger als erwartet laufen, Aufgaben mit niedrigerer Priorität willkürlich und unkontrolliert verzögern können.

Mit SCHED_DEADLINE deklarieren Tasks ihre Zeitanforderungen unabhängig voneinander in Form einer taskbezogenen Laufzeit , die pro Task- Periode benötigt wird (und innerhalb einer taskbezogenen Frist ab Periodenbeginn fällig ist). Der Kernel akzeptiert diese nach einem Planbarkeitstest im Scheduler. Versucht ein Task, länger als sein zugewiesenes Budget zu laufen, hält der Kernel diesen Task an und verschiebt seine Ausführung auf die nächste Aktivierungsperiode. Diese nicht-arbeitserhaltende Eigenschaft des Schedulers ermöglicht die zeitliche Isolation der Tasks. Dies führt zu der wichtigen Eigenschaft, dass auf Einzelprozessorsystemen oder partitionierten Mehrprozessorsystemen (wo Tasks auf die verfügbaren CPUs verteilt sind, sodass jeder Task an eine bestimmte CPU gebunden ist und nicht migriert werden kann) garantiert wird, dass alle akzeptierten SCHED_DEADLINE- Tasks in jedem Zeitfenster ihrer Periode für eine Gesamtzeit eingeplant werden, die ihrem Budget entspricht – es sei denn, der Task selbst blockiert und muss nicht ausgeführt werden. Eine besondere Eigenschaft des CBS-Algorithmus ist die Gewährleistung der zeitlichen Isolation auch dann, wenn Aufgaben blockieren und ihre Ausführung fortsetzen: Dies wird erreicht, indem die Frist für die Aufgabenplanung um eine ganze Periode verschoben wird, sobald eine Aufgabe zu spät aufwacht. Im allgemeinen Fall von Aufgaben, die auf einem Mehrprozessorsystem frei migriert werden können, gilt, da SCHED_DEADLINE globales EDF implementiert, die allgemeine Verspätungsgrenze für globales EDF, wie in ^{[ 9 ]} erläutert.

Um die Funktionsweise des Schedulers besser zu verstehen, betrachten wir eine Menge von SCHED_DEADLINE -Tasks mit potenziell unterschiedlichen Laufzeiten, wobei die Deadline der Laufzeit entspricht. Für jeden Task speichert der Kernel neben der konfigurierten Laufzeit und der (relativen) Laufzeit auch die aktuelle Laufzeit und die aktuelle (absolute) Deadline . Die Tasks werden mithilfe des globalen EDF basierend auf ihren aktuellen Deadlines auf den CPUs eingeplant. Wenn eine Task-Scheduling-Richtlinie initial auf SCHED_DEADLINE gesetzt wird , wird die aktuelle Deadline auf die aktuelle Zeit plus die konfigurierte Laufzeit initialisiert und das aktuelle Budget auf das konfigurierte Budget gesetzt. Jedes Mal, wenn ein Task zur Ausführung auf einer beliebigen CPU eingeplant wird, lässt der Kernel ihn maximal so lange laufen, wie das aktuelle Budget verfügbar ist. Wird der Task aus dem Scheduler entfernt, verringert sich sein aktuelles Budget um die Laufzeit. Sobald das aktuelle Budget auf null sinkt, wird der Task bis zur nächsten Aktivierungsperiode angehalten (gedrosselt). Dann wird das aktuelle Budget wieder auf den konfigurierten Wert aufgefüllt und die Deadline um die Laufzeit des Tasks nach vorne verschoben.

Dies reicht nicht aus, um eine zeitliche Isolation zu gewährleisten . Eine Aufgabe, die sich kurz nach ihrer Aktivierung selbst anhält und dann nahe ihrer aktuellen Deadline oder sogar darüber hinaus wieder aufwacht, würde mit nahezu ihrem gesamten konfigurierten Budget aufwachen, mit einer aktuellen Deadline, die kurz vor dem Ablauf steht oder sogar bereits vergangen ist. In diesem Fall würde diese Aufgabe vor allen anderen eingeplant werden und könnte auf einem Einprozessorsystem die Ausführung jeder anderen Deadline-Aufgabe um die Dauer ihres Budgets verzögern. Um dieses Problem zu vermeiden, verwendet SCHED_DEADLINE die im CBS-Algorithmus definierte Wake-up-Scheduling-Regel. Wenn eine Aufgabe aufwacht und seit ihrer Blockierung nur eine relativ kurze Zeit vergangen ist, bleiben die vorherige Deadline und das Budget für die Aufgabe unverändert. Ist jedoch zu viel Zeit vergangen, setzt der Kernel die aktuelle Deadline auf die aktuelle Zeit plus den Reservierungszeitraum und das aktuelle Budget auf das zugewiesene Reservierungsbudget zurück. Eine ausführlichere Erklärung mit Beispielen findet sich in ^{[ 9 ] .}

Auf Mehrprozessor- oder Mehrkernsystemen implementiert SCHED_DEADLINE globales EDF, sodass Aufgaben auf die verfügbaren CPUs verteilt werden können. In diesem Fall entspricht das konfigurierte Budget der gesamten Laufzeit, die eine Aufgabe innerhalb eines Zeitraums auf einer beliebigen CPU verbringen darf. Der Scheduler berücksichtigt jedoch auch die Affinitätsmasken der Aufgaben . Dadurch lassen sich problemlos partitionierte Scheduling-Szenarien erstellen, bei denen Aufgaben in Gruppen zusammengefasst werden, wobei jede Gruppe auf eine bestimmte CPU beschränkt ist. Alternativ können auch Cluster-Scheduling-Szenarien erstellt werden, indem zusätzlich CPUs partitioniert werden und jede Aufgabenpartition einer bestimmten CPU-Partition zugeordnet wird.

Technische Details zu SCHED_DEADLINE finden Sie in der Dokumentation im Kernel-Quellcode. ^{[ 9 ]} Weitere Informationen zum CBS und dessen Funktionsweise zur zeitlichen Isolation finden Sie in der Originalveröffentlichung zum CBS ^{[ 3 ]} oder im Abschnitt über das CBS in diesem Artikel ^{[ 10 ],} der auf lwn.net erschienen ist.

Die ursprüngliche Idee einer Linux-Scheduling-Klasse basierend auf dem Earliest Deadline First (EDF)-Algorithmus entstand im kleinen Rahmen des Real-Time Systems (ReTiS) Lab der Scuola Superiore Sant'Anna ^{[ 11 ]} und dessen Spin-off-Unternehmen Evidence Srl ^{[ 12 ]} . Evidence Srl nutzte anschließend die Förderung des ACTORS-Projekts ^{[ 13 , 14 ] ,} das von der Europäischen Kommission im Rahmen des FP7-Rahmenprogramms unterstützt wurde, um die Entwicklung der ersten Patch-Versionen zu finanzieren und voranzutreiben. Die Originalversion wurde von Dario Faggioli (im Auftrag von Evidence Srl für die Entwicklung der ersten drei Versionen) und Juri Lelli (ab der vierten Version) ^{[ 15 ]} mit gelegentlicher Unterstützung von Michael Trimarchi und Fabio Checconi entwickelt. Johan Eker war für die Koordination innerhalb von ACTORS und die Unterstützung durch Ericsson zuständig. Juri Lelli, Luca Abeni und Claudio Scordino haben an der Entwicklung der Rückgewinnungs- (d. h. GRUB ^{[ 16 ]} ) und Frequenzskalierungsfunktionen (d. h. GRUB-PA ^{[ 17 ]} ) mitgewirkt.

Der Patch wurde regelmäßig über die Linux-Kernel-Mailingliste (LKML) an die Kernel-Community veröffentlicht. Jede Version passte den Code an die neueste Kernel-Version an und berücksichtigte die Kommentare der vorherigen Version. Mit zunehmender Beliebtheit des Schedulers beteiligten sich immer mehr Kernel-Entwickler mit Feedback und Beiträgen.

Das Projekt hieß ursprünglich SCHED_EDF und wurde 2009 der Linux-Kernel-Community vorgestellt. ^{[ 18 ]} Unter diesem Namen wurde es einige Wochen später auch dem Real-Time Linux Workshop präsentiert. ^{[ 19 ]} Auf Wunsch der Linux-Kernel-Community wurde der Name dann in SCHED_DEADLINE geändert. ^{[ 20 ]}

Im Laufe der Jahre wurden folgende Versionen veröffentlicht:

• Die erste Version des Schedulers wurde am 22. September 2009 unter dem Namen SCHED_EDF eingereicht . ^{[ 18 ]}
• Die erste Version des Schedulers, nachdem er in SCHED_DEADLINE umbenannt wurde , wurde am 16. Oktober 2009 bei LKML eingereicht. ^{[ 21 ]}
• Die zweite Version des Schedulers wurde am 28. Februar 2010 bei LKML eingereicht und enthielt eine erste Implementierung des Deadline-Inheritance-Protokolls. ^{[ 22 ]}
• Die dritte Version des Schedulers wurde am 29. Oktober 2010 bei LKML eingereicht und fügte die Unterstützung für globales/geclustertes Multiprozessor-Scheduling durch dynamische Task-Migrationen hinzu. ^{[ 23 ]}
• Die vierte Version des Schedulers wurde am 6. April 2012 bei LKML eingereicht und bietet eine verbesserte Handhabung der rq-Auswahl für die dynamische Aufgabenmigration sowie eine bessere Integration mit PREEMPT_RT . ^{[ 24 ]}
• Die fünfte Version des Schedulers wurde am 23. Mai 2012 bei LKML eingereicht. ^{[ 25 ]}
• Die sechste Version des Schedulers wurde am 24. Oktober 2012 bei LKML eingereicht. ^{[ 26 ]}
• Die siebte Version des Schedulers wurde am 11. Februar 2013 bei LKML eingereicht. ^{[ 27 ]} Interne mathematische Operationen wurden auf eine Auflösung im Mikrosekundenbereich beschränkt (um Überläufe zu vermeiden) und das RFC-Tag wurde entfernt.
• Die achte Version des Schedulers wurde am 14. Oktober 2013 bei LKML eingereicht. ^{[ 28 ]}
• Die neunte Version des Schedulers wurde am 7. November 2013 an LKML übermittelt. ^{[ 29 ]}
• Die letzte Version wurde in den Mainline-Linux-Kernel integriert (Commit-Nummer a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8 ^{[ 30 ]} ) und ist seitdem ein fester Bestandteil davon.

Artikel auf den Websites von Linux Weekly News ^{[ 31 ]} und Phoronix ^{[ 32 ]} argumentierten, dass SCHED_DEADLINE bereits in den nächsten Kernel-Releases in den Hauptkernel integriert werden könnte. Nach mehr als vier Jahren und neun Releases wurde der Patch schließlich akzeptiert und in den Linux-Kernel 3.14 integriert. ^{[ 7 ] [ 8 ]}

Vor dem Stichtag SCHED_DEADLINE hatte das Real-Time Systems (ReTiS) Lab ^{[ 11 ]} der Scuola Superiore Sant'Anna im Rahmen anderer europäischer Forschungsprojekte, darunter OCERA ^{[ 33 ]} , die AQuoSA - Architektur im FRESCOR-Projekt ^{[ 34 ]} und IRMOS ^{[ 35 ]} , verschiedene Open-Source-Implementierungen von CBS und seinen Varianten innerhalb des Linux-Kernels bereitgestellt. Diese früheren Bemühungen verfolgten jedoch einen akademischen Ansatz mit dem Hauptziel, experimentelle Ergebnisse für Forschungsprojekte zu sammeln, anstatt eine Implementierung bereitzustellen, die sich für die Integration in den Hauptkernel eignete. Mit IRMOS knüpfte das Labor erstmals ernsthafte Kontakte zu den Linux-Kernel-Entwicklern. ^{[ 10 ]}

Seit Kernel 4.13 unterstützt SCHED_DEADLINE die CBS-Funktionalität ^{[ 36 ]} mit dem GRUB-Algorithmus (Greedy Reclamation of Unused Bandwidth) ^{[ 37 ]} . Die Unterstützung wurde vom ReTiS Lab in Zusammenarbeit mit Evidence Srl entwickelt.

Seit Kernel 4.16 wurde SCHED_DEADLINE weiterentwickelt, um den Energieverbrauch auf ARM-Plattformen durch die Implementierung des GRUB-PA-Algorithmus zu reduzieren. ^{[ 17 ]} Die Arbeiten wurden von ARM Ltd. in Zusammenarbeit mit Evidence Srl und der Scuola Superiore Sant'Anna durchgeführt. ^{[ 38 ]}

SCHED_DEADLINE wurde bereits in verschiedenen akademischen Workshops, Konferenzen und Fachzeitschriften vorgestellt:

• Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, Eine EDF-Scheduling-Klasse für den Linux-Kernel , 11. Real-Time Linux Workshop (RTLWS), Dresden, Deutschland, September 2009 ^{[ 19 ] [ 39 ]}
• Nicola Manica, Luca Abeni, Luigi Palopoli, Dario Faggioli, Claudio Scordino, Schedulable Device Drivers: Implementation and Experimental Results , International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Brüssel, Belgien, Juli 2010 ^{[ 40 ] [ 41 ]}
• Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, Eine effiziente und skalierbare Implementierung von globalem EDF in Linux , Internationaler Workshop über Betriebssystemplattformen für eingebettete Echtzeitanwendungen (OSPERT), Porto (Portugal), Juli 2011. ^{[ 42 ] [ 43 ]}
• Enrico Bini, Giorgio Buttazzo, Johan Eker, Stefan Schorr, Raphael Guerra, Gerhard Fohler, Karl-Erik Arzen, Vanessa Romero Segovia, Claudio Scordino, Ressourcenmanagement auf Mehrkernsystemen: Der ACTORS-Ansatz , IEEE Micro, Bd. 31, Nr. 3, S. 72–81, Mai/Juni 2011. ^{[ 14 ]}
• Andrea Parri, Juri Lelli, Mauro Marinoni, Giuseppe Lipari, Entwurf und Implementierung des Multiprocessor Bandwidth Inheritance Protocol unter Linux , 15. Real-Time Linux Workshop (RTLWS), Lugano-Manno, Schweiz, Oktober 2013. ^{[ 44 ]}
• Luca Abeni, Juri Lelli, Claudio Scordino, Luigi Paolopoli, Greedy CPU reclaiming for SCHED_DEADLINE , Proceedings of 16th Real-Time Linux Workshop (RTLWS), Düsseldorf, Germany, October 2014. ^{[ 45 ]}
• Juri Lelli, Claudio Scordino, Luca Abeni, Dario Faggioli, Deadline scheduling in the Linux kernel , Software: Practice and Experience, 46(6): 821–839, Juni 2016. ^{[ 46 ]}
• Claudio Scordino, Luca Abeni, Juri Lelli, Energiebewusste Echtzeitplanung im Linux-Kernel , 33. ACM/SIGAPP Symposium On Applied Computing (SAC 2018), Pau, Frankreich, April 2018. ^{[ 47 ]}
• Claudio Scordino, Luca Abeni, Juri Lelli, Echtzeitfähigkeit und Energieeffizienz in Linux: Theorie und Praxis , ACM SIGAPP Applied Computing Review (ACR) Vol. 18 Nr. 4, 2018. ^{[ 48 ]}

Das Projekt wurde außerdem auf dem Kernel Summit 2010 ^{[ 49 ] [ 50 ]} , der Linux Plumbers Conference 2012 ^{[ 51 ] [ 52 ]} und der Embedded Linux Conference 2013 ^{[ 53 ] vorgestellt.}

Das Projekt verfügt über eine offizielle Webseite. ^{[ 54 ]} Vor der Integration in den Hauptzweig war der Code öffentlich auf einer GitHub-Website verfügbar, ^{[ 55 ]} die das vorherige Repository auf Gitorious ersetzte. ^{[ 56 ]} Seit der Integration in den Hauptzweig ist der offizielle Code im Quellcodebaum des Linux-Kernels enthalten.

Mehrere Artikel dazu erschienen in Linux Weekly News [ ^{1 ] [ 57 ] ,} Slashdot [ ^{58 ] ,} OSNews ^{[ 2 ] [ 59 ]} und LinuxToday ^{[ 60 ]} . Außerdem wurde ein Video auf YouTube hochgeladen ^{[ 61 ] .}

Vor der Integration in den Hauptkernel war SCHED_DEADLINE bereits in das Yocto-Projekt integriert . ^{[ 28 ]} Es gab auch Interesse an einer Aufnahme in Linaro -Projekte. ^{[ 62 ]}

• Frühester zulässiger virtueller Stichtag (EEVDF)