4.4 Linux für eingebettete Systeme
247
beiden Projekte unterscheiden sich in ihren Zielen und ihrer Implementierung. Allerdings unterstützen beide das Real-Time Driver Model (RTDM), einen Ansatz zur
Vereinheitlichung von Schnittstellen für Gerätetreiber und darauf basierender Anwendungen für echtzeitfähige Linux-Systeme. Der dritte Ansatz, der ebenfalls einen
unterliegenden Echtzeitkern verwendet, ist RTLinux [608], das als Projekt am New
Mexico Institute of Mining and Technology entwickelt und später von der Firma
FSMLabs, die im Jahr 2007 von WindRiver übernommen wurde, kommerzialisiert
wurde. Das zugehörige Produkt wurde bereits im Jahr 2011 eingestellt. Der Einsatz von RTLinux in Produkten wurde kontrovers diskutiert, da dessen Erfinder ihr
geistiges Eigentum, für das sie ein Software-Patent [607] erhielten, vehement verteidigten. Die Entscheidung, die Methoden hinter RTLinux zu patentieren, rief bei
Linux-Entwicklern wenig Begeisterung hervor, was schließlich zur Entwicklung der
oben erwähnten alternativen Projekte RTAI und Xenomai führte.
Ein neuerer Ansatz, Linux um Echtzeitfähigkeiten zu erweitern, ist SCHED_DEADLINE, das seit 2014 (Kernversion 3.14) im Linux-Kern integriert ist. Dabei handelt
es sich um ein CPU-Scheduling-Verfahren, das auf den Algorithmen für Earliest
Deadline First (EDF) und Constant Bandwidth Server (CBS) [3] basiert und die
Reservierung von Ressourcen unterstützt. Das SCHED_DEADLINE-Verfahren kann dabei gemeinsam mit anderen Linux Scheduling-Verfahren aktiv sein, es hat aber stets
Vorrang vor allen anderen Verfahren, um Echtzeiteigenschaften garantieren zu können.
Jede unter SCHED_DEADLINE eingeplante Task τ i erhält ein Laufzeit-Budget C i und
eine Periode T i . Dies zeigt dem Kern an, dass diese Task in einer Periode T i jeweils
C i Zeiteinheiten auf einem beliebigen Prozessor benötigt. Bei Echtzeitanwendungen
entspricht T i der minimalen Zeit zwischen zwei aufeinanderfolgenden Aktivierungen
der Task, C i entspricht der WCET für jede Ausführung der Task. Wenn eine neue
Task zum Scheduling-Verfahren hinzugefügt werden soll, wird ein Test auf Einplanbarkeit (schedulability) durchgeführt. Die Task wird nur akzeptiert, wenn der Test
erfolgreich ist. Während des Schedulings wird eine Task suspendiert und auf die
kommende Periode verlagert, wenn sie versucht, mehr Rechenzeit zu beanspruchen
als ihrem Budget entspricht. Diese sogenannte non-work conserving-Strategie18 ist
notwendig, um die temporale Isolation zwischen Tasks sicherzustellen. Daher ist
auf Einprozessorsystemen und partitionierten Mehrprozessorsystemen (mit Tasks,
deren Ausführung auf eine bestimmte CPU beschränkt ist) für alle akzeptierten
SCHED_DEADLINE-Tasks garantiert, dass sie für eine Gesamtzeit eingeplant werden,
die ihrem Zeitbudget in jedem Zeitfenster entspricht.
Für den allgemeinen Fall, in dem Tasks zwischen verschiedenen Kernen eines
Mehrprozessorsystems migrieren können, gilt die übliche tardiness-Grenze für globales EDF [128], da SCHED_DEADLINE globales EDF implementiert (wie im Detail
in Abschnitt 6.3.3 beschrieben). Benchmarks aus [337] geben den Anteil verpasster
Deadlines mit weniger als 0,2% an, wenn SCHED_DEADLINE auf einem Vierprozessorsystem mit einer Auslastung von 380% läuft und von weniger als 0,615% bei
einer Auslastung von 390%. Die angegebenen Zahlen für ein Sechsprozessorsystem
18 Dies bedeutet, dass der Prozessor idle sein kann, auch wenn Tasks ausgeführt werden könnten.
Eine Definition des Begriffs findet sich in Kapitel 6 auf Seite 336.
247
beiden Projekte unterscheiden sich in ihren Zielen und ihrer Implementierung. Allerdings unterstützen beide das Real-Time Driver Model (RTDM), einen Ansatz zur
Vereinheitlichung von Schnittstellen für Gerätetreiber und darauf basierender Anwendungen für echtzeitfähige Linux-Systeme. Der dritte Ansatz, der ebenfalls einen
unterliegenden Echtzeitkern verwendet, ist RTLinux [608], das als Projekt am New
Mexico Institute of Mining and Technology entwickelt und später von der Firma
FSMLabs, die im Jahr 2007 von WindRiver übernommen wurde, kommerzialisiert
wurde. Das zugehörige Produkt wurde bereits im Jahr 2011 eingestellt. Der Einsatz von RTLinux in Produkten wurde kontrovers diskutiert, da dessen Erfinder ihr
geistiges Eigentum, für das sie ein Software-Patent [607] erhielten, vehement verteidigten. Die Entscheidung, die Methoden hinter RTLinux zu patentieren, rief bei
Linux-Entwicklern wenig Begeisterung hervor, was schließlich zur Entwicklung der
oben erwähnten alternativen Projekte RTAI und Xenomai führte.
Ein neuerer Ansatz, Linux um Echtzeitfähigkeiten zu erweitern, ist SCHED_DEADLINE, das seit 2014 (Kernversion 3.14) im Linux-Kern integriert ist. Dabei handelt
es sich um ein CPU-Scheduling-Verfahren, das auf den Algorithmen für Earliest
Deadline First (EDF) und Constant Bandwidth Server (CBS) [3] basiert und die
Reservierung von Ressourcen unterstützt. Das SCHED_DEADLINE-Verfahren kann dabei gemeinsam mit anderen Linux Scheduling-Verfahren aktiv sein, es hat aber stets
Vorrang vor allen anderen Verfahren, um Echtzeiteigenschaften garantieren zu können.
Jede unter SCHED_DEADLINE eingeplante Task τ i erhält ein Laufzeit-Budget C i und
eine Periode T i . Dies zeigt dem Kern an, dass diese Task in einer Periode T i jeweils
C i Zeiteinheiten auf einem beliebigen Prozessor benötigt. Bei Echtzeitanwendungen
entspricht T i der minimalen Zeit zwischen zwei aufeinanderfolgenden Aktivierungen
der Task, C i entspricht der WCET für jede Ausführung der Task. Wenn eine neue
Task zum Scheduling-Verfahren hinzugefügt werden soll, wird ein Test auf Einplanbarkeit (schedulability) durchgeführt. Die Task wird nur akzeptiert, wenn der Test
erfolgreich ist. Während des Schedulings wird eine Task suspendiert und auf die
kommende Periode verlagert, wenn sie versucht, mehr Rechenzeit zu beanspruchen
als ihrem Budget entspricht. Diese sogenannte non-work conserving-Strategie18 ist
notwendig, um die temporale Isolation zwischen Tasks sicherzustellen. Daher ist
auf Einprozessorsystemen und partitionierten Mehrprozessorsystemen (mit Tasks,
deren Ausführung auf eine bestimmte CPU beschränkt ist) für alle akzeptierten
SCHED_DEADLINE-Tasks garantiert, dass sie für eine Gesamtzeit eingeplant werden,
die ihrem Zeitbudget in jedem Zeitfenster entspricht.
Für den allgemeinen Fall, in dem Tasks zwischen verschiedenen Kernen eines
Mehrprozessorsystems migrieren können, gilt die übliche tardiness-Grenze für globales EDF [128], da SCHED_DEADLINE globales EDF implementiert (wie im Detail
in Abschnitt 6.3.3 beschrieben). Benchmarks aus [337] geben den Anteil verpasster
Deadlines mit weniger als 0,2% an, wenn SCHED_DEADLINE auf einem Vierprozessorsystem mit einer Auslastung von 380% läuft und von weniger als 0,615% bei
einer Auslastung von 390%. Die angegebenen Zahlen für ein Sechsprozessorsystem
18 Dies bedeutet, dass der Prozessor idle sein kann, auch wenn Tasks ausgeführt werden könnten.
Eine Definition des Begriffs findet sich in Kapitel 6 auf Seite 336.