Task-Management

Echtzeit- und Deadline-Scheduling von Linux

Seite: 2/3

Firmen zum Thema

Deadline-Tasks kombinieren zwei Scheduling-Verfahren

Deadline-Tasks sind eine Kombination zweier Scheduling-Verfahren: Earliest-Deadline-First-Scheduling (EDF) sowie 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.

Bildergalerie
Bildergalerie mit 6 Bildern

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.

Artikelfiles und Artikellinks

(ID:43962634)