Task-Management Realtime- und Deadline-Scheduling von Linux

Anbieter zum Thema

Andreas Klinger

PresseBox - unn | UNITED NEWS NETWORK GmbH

Seit dem Linux-Kernel 3.14 steht das Deadline-Scheduling zur Verfügung. Dadurch besteht die Aussicht, dass die Parametrisierung der Tasks direkt als zeitliche Vorgabe und nicht nur als abgeleitete Priorität erfolgt.

Dieser Artikel zeigt, wie sich das Scheduling im aktuellen Kernel gestaltet. Ein Task kann sein:

- Userspace-Prozess,

- Userspace-Thread (Posix-Thread),

- Kernel-Thread.

Alle Tasks sind gleichwertig, egal zu welcher der drei Kategorien sie gehören. Welcher Task wen unterbricht, entscheidet der Scheduler nach der Scheduling-Klasse. Dies sind nach absteigender Priorität (Scheduling-Policy in Klammern):

• Deadline (SCHED_DEADLINE),

• Realtime (SCHED_FIFO und SCHED_RR),

• Normaler Task (SCHED_OTHER) einschließlich Batch-Task (SCHED_BATCH),

• Idle (SCHED_IDLE).

Diese vier Scheduling-Klassen, die mittels der Scheduling-Policy eingestellt werden, bestimmen in erster Instanz, welcher Task wen unterbricht. Ein höher angeordneter unterbricht immer alle darunterliegenden. Jede Scheduling-Klasse enthält jeweils ein anderes Scheduling-Verfahren, welche nachfolgend vorgestellt werden sollen.

Die Klasse der Realtime-Tasks unter der Lupe

Tasks in dieser Scheduling-Klasse werden nach einem Priority-Based-Preemptive-Scheduling- Verfahren eingeteilt. Dabei gibt es 99 Prioritätsstufen. Ein Task unterbricht immer alle Tasks der niedrigeren Prioritäten.

Innerhalb einer Prioritätsstufe gibt es zwei Verfahren: Bei SCHED_FIFO rechnet der Task so lange, bis er durch einen mit höherer Priorität unterbrochen wird oder freiwillig Rechenzeit abgibt durch Aufruf einer wartenden oder blockierenden Funktion. Im Gegensatz dazu bekommt ein Task der SCHED_RR-Policy eine Zeitscheibe zugeteilt, nach welcher er durch einen Realtime-Task der gleichen Priorität abgelöst werden kann. Das Verhalten gegenüber anderen Prioritätsstufen ist aber in beiden Varianten das gleiche.

Beispiel: Start einer Shell mit der Policy SCHED_FIFO und der Priorität 80:

chrt -f 80 /bin/bash

Abfrage der Scheduling-Policy:

chrt -p 789

Nun würde ein wildgewordener Task aus der Klasse der Realtime-Tasks die gesamte CPU an sich ziehen und die Tasks aus dem Pool der normalen Tasks, welche in aller Regel die überwiegende Mehrheit des Linux-Systems darstellen, gar nicht an die Reihe kommen lassen.

Damit dies nicht so leicht passiert, existiert ein Verfahren namens RT-Throttling. Dabei wird ab dem Zeitpunkt, an dem RT-Tasks gescheduled werden, eine maximale Runtime den RT-Tasks insgesamt zur Verfügung gestellt (Defaultwert ist 950 ms).

Bildergalerie

Bildergalerie mit 6 Bildern

Rechnen nun RT-Tasks ununterbrochen diese Zeit, ohne Rechenzeit an die normalen Tasks abzugeben, dann werden die RT-Tasks gedrosselt. Dabei gibt der Scheduler die bis zur Zeitperiode verbleibende Zeit den normalen Tasks (Default 50 ms).

Die entsprechenden Zeiten können im /proc-Filesystem mit den Dateien /proc/sys/kernel/sched_rt_period_us und/proc/sys/kernel/sched_rt_runtime_us in Mikrosekunden eingestellt werden.

Verwendet man RT-Tasks, so übersetzt man die Anforderungen an einzelne Aufgaben in statische Prioritäten. Dort wo die Latenz geringer sein muss, wird eine höhere Priorität eingestellt. Dabei kann Echtzeitverhalten nur für den am höchsten priorisierten Task pro CPU gewährleistet werden. Bereits für den zweithöchsten kann Determinismus nicht mehr erwartet werden. Sollte der mit der höchsten Priorität mehr Rechenzeit benötigen als geplant, hat das schon für den nächsten übermäßige Latenzen zur Folge.

Ein Ansatz, Echtzeitfähigkeit mit mehreren Tasks zu erreichen und auch die Spezifikation direkter übersetzen zu können, sind die Deadline-Tasks, die nun vorgestellt werden.

Deadline-Tasks kombinieren zwei Scheduling-Verfahren

Deadline-Tasks sind eine Kombination zweier Scheduling-Verfahren:

• Earliest-Deadline-First-Scheduling (EDF)

• Constant-Bandwith-Server (CBS)

Earliest-Deadline-First bedeutet, dass es gar keine Priorisierung mehr gibt. Für jeden Task wird eine Deadline definiert, wann er drankommen muss, und der Scheduler gibt zu einem Zeitpunkt immer demjenigen Rechenzeit, bei welchem die Deadline am nächsten liegt. Es wird also dynamisch immer wieder neu entschieden, wer rechnen darf. Ausschlaggebend dafür ist die angegebene Deadline.

Damit wäre grundsätzlich die Möglichkeit gegeben, dass mehrere Tasks gleich gut ihre Deadline treffen. Jedoch kann auch hier ein Task übermäßig Rechenzeit beanspruchen. Der Scheduler muss dann entweder die anderen Tasks ausbremsen oder er weiß nicht mehr, wem er zuerst Rechenzeit geben soll: Dem, der lange rechnet oder dem, der schon am längsten wartet.

Daher wurde das EDF-Scheduling durch ein zweites Verfahren erweitert, das CBS.

Beim Constant-Bandwith-Server (CBS) bekommen die Tasks jeweils einen Anteil an der zur Verfügung stehenden Rechenzeit zugewiesen. Diese Rechenzeit dürfen sie nicht überschreiten. Wenn doch, dann werden sie ausgesondert und kommen erst wieder in der nächsten Zeitperiode an die Reihe.

In der Linux-Implementierung werden diese beiden Verfahren kombiniert, indem für jeden Task festgelegt wird, welche maximale Runtime (wcet: worst case execution time) er innerhalb einer Zeitperiode zur Verfügung gestellt bekommt. Dabei werden drei Parameter für den Task festgelegt:

• runtime: maximale CPU-Rechenzeit pro Zeitperiode,

• deadline: Deadline, welche inklusive der Rechenzeit erreicht werden muss,

• period: Zeitperiode.

Die runtime ergibt sich als Worst-Case-Rechenzeit, welche innerhalb einer Zeitperiode benötigt wird. Es ist darauf zu achten, dass diese Zeit sorgfältig ermittelt wird und vor allem auch im Extremfall eingehalten werden kann. Sollte sie nicht eingehalten werden können, wird der Task unterbrochen und er darf erst nach Ablauf der Zeitperiode wieder rechnen, was besonders bitter sein kann.

deadline bezeichnet die Zeit, bis zu jener der Task ab dem Zeitpunkt, an dem er rechenbereit ist spätestens fertig gerechnet haben muss. Diese Zeit gilt jeweils ab dem sogenannten Wakeup, also der Zeitpunkt, an dem er den Zustand von Sleeping nach Running wechselt. Dies entspricht dem ftrace-Event sched_wakeup.

Mit period wird die Zeitperiode definiert, in der der Task die definierte Runtime bekommt. Diese Zeit kann als umgekehrte maximale Frequenz des Auftretens des Tasks betrachtet werden. Sollte ein Task innerhalb der Periode mehr Rechenzeit benötigen, als für ihn definiert wurde, dann muss er warten, bis die Zeitperiode abgelaufen ist und die nächste beginnt.

Dies heißt, dass auch diese Zeitperiode sorgfältig zu wählen ist. Speziell wenn der Task ein zweites Mal innerhalb der Periode rechnen möchte, wird die definierte Rechenzeit schnell erreicht.

Auch für Deadline-Tasks gibt es eine Drosselung. Dabei wird das RT-Throttling gemeinsam von RT- und Deadline-Tasks genutzt. Dies bedeutet, dass beide Tasktypen gemeinsam die verfügbare Zeit nutzen können.

Beispiel für die Einstellung eines Deadline-Tasks der pid = 367 mit 200 ms Periodendauer = Deadline und 50 ms Runtime:

schedtool -E -t 50000000:200000000 367

Die Abfrage der Scheduling-Policy und der Parameter erfolgt mit

schedtool 367.

Der Umgang mit normalen Tasks

Normale Tasks werden in einem Round-Robin-Verfahren gescheduled. Dabei gibt es einen Nice-Wert, der festlegt, wie viel Rechenzeit der Task bei einem Scheduler-Durchlauf bekommt. Ein geringerer Nice-Wert bedeutet, dass der Task weniger nett ist, also mehr Rechenzeit beansprucht. Die Spanne reicht von -20 bis +19. Bei einem Durchlauf kommt jeder Task einmal dran.

Verdrängende Prioritäten können damit nicht eingestellt werden, sondern lediglich ein höherer Anteil an der Rechenzeit. Für latenzzeitkritische Anwendungsfälle eignet sich dieses Verfahren daher nicht.

Batch-Tasks sind ein Sonderfall von normalen Tasks, die eine sehr kleine Zeitscheibe erhalten. Auch die Idle-Tasks können für eigene Prozesse und Threads eingestellt werden. Sie rechnen dann, wenn nicht mal mehr ein normaler Task rechnen möchte.

Deadline-Tasks lassen sich dort gut einsetzen, wo es darum geht, ab einem Triggerzeitpunkt, ausgelöst etwa durch einen Interrupt, innerhalb eines vorgegebenen Zeitraumes (Deadline) eine Aufgabe auszuführen. Der Scheduler kümmert sich darum, dass der Task entsprechend der Vorgaben rechtzeitig an die Reihe kommt. Dies können sporadische wie auch zyklische Aufgaben sein.

Die Anwendung von Deadline-Tasks

Entscheidend ist in jedem Fall, dass sowohl die Runtime als auch die Periode gewissenhaft unter Worst-Case-Bedinungen bestimmt werden. Sollte einer der beiden Parameter nicht gehalten werden können, kommt es zum GAU: Der eigentlich hochpriorisierte Deadline-Task wird durch den Scheduler abgebrochen. Für die Ermittlung der Zeiten kann die Funktion clock_gettime() im Userspace verwendet werden.

Ferner sollte berücksichtigt werden, dass der zu planende Deadline-Task innerhalb seiner Runtime gegebenenfalls auf weitere Ressourcen warten muss. Dabei wird möglicherweise ein anderer Task aufgeweckt, mittels Prioritätsvererbung beschleunigt an die Reihe genommen, um dann wieder den Deadline-Task rechnen zu lassen.

Hier passiert eine klassische Prioritätsvererbung. Die Bemessung der Deadline-Zeit muss derartige Fälle berücksichtigen. Ein Beispiel für dieses Szenario ist in den beiden Kernelshark-Ausgaben zu sehen (Bild 5 und 6).

Konsequenzen für das Systemdesign

Im aktuellen Linux-Kernel stehen eine ganze Reihe an Scheduling-Verfahren zur Verfügung, die es erlauben, Tasks entsprechend ihrer Anforderung zu schedulen. Damit hat der Designer und Entwickler eine ganze Reihe an Möglichkeiten, sein System zu entwerfen. Zeitkritische Aufgaben können sowohl nach Deadline-Zeiten als auch nach Prioritäten gescheduled werden.

Dieser Beitrag wurde ursprünglich von unserem Schwesterportal Elektronikpraxis.de veröffentlicht.

* Andreas Klinger ist selbstständiger Diplom-Ingenieur (FH) und bietet Seminare zu Embedded- und Echtzeit-Linux an.

(ID:44416993)