Sporadic Scheduling

Bei der Sporadic-Scheduling-Strategie handelt es sich um ein echtzeitfähiges Scheduling-Verfahren, das im POSIX-Standard 1003.1b festgelegt ist. Ziel ist es, azyklische (sporadische) Aufgaben so zu behandeln, als wären es zyklische.

Bei Systemen, die eine Echtzeitanforderung haben – was bedeutet, dass bestimmte Aufgaben spätestens zu definierten Zeitpunkten erledigt sein müssen – werden besondere Anforderungen an das Scheduling-Verfahren gestellt: Dieses regelt die Zuordnung der begrenzten Ressource „CPU“ an die laufenden Prozesse. Die zu erledigenden Aufgaben lassen sich dabei grob in zwei Gruppen einteilen: Zum einen gibt es zyklische Aufgaben wie z. B. Messwertaufnahmen, die regelmäßig in bestimmten Zeitabschnitten anfallen. Zum anderen gibt es Aufgaben, die sporadisch oder azyklisch auftreten wie z. B. Fehlersituationen, auf die ebenfalls reagiert werden muss. Da sporadische Aufgaben ungeplant auftreten, kann ihre Abarbeitung die zeitgerechte Abarbeitung der zyklischen Aufgaben verhindern. Hier setzt Sporadic-Scheduling an.

Motivation

Die Annahme, dass alle Aufgaben zyklisch abgearbeitet werden können, ist oft unrealistisch. Daher braucht man ein Scheduling-Verfahren, das gewährleistet, auch bei zyklischen Aufgaben auf azyklische Ereignisse reagieren zu können, ohne die Rechtzeitigkeit der zyklischen Aufgaben zu beeinflussen. Andere Scheduling-Strategien, wie z. B. Prioritäts-Scheduling oder Deadline-Scheduling, sind bedingt auch für diese Aufgabe geeignet. Sie erschweren aber den Echtzeitnachweis für das System erheblich.

Prinzip

Jede zyklische Aufgabe wird mit minimaler Prozesszeit und der ermittelten maximalen Verarbeitungszeit modelliert. Die Aufgaben, die azyklisch auftreten können und somit eine variable Prozesszeit aufweisen, werden ebenfalls als zyklische Aufgaben modelliert. Alle diese zyklischen Aufgaben bekommen ihre Prioritäten nach der Rate-Monotonic – Annahme, welche die Priorität an die Prozesszeit koppelt. Da alle Prozesse jetzt als zyklische Aufgaben realisiert sind, kann die Auslastung aus der Summe der Verhältnisse der Verarbeitungszeit zur Prozesszeit berechnet werden. Sollte diese Auslastung verletzt werden, indem eine Aufgabe ihre Prozesszeit verletzt, wird die auslösende Aufgabe bestraft und in ihrer Priorität herabgesetzt. Daraus folgt, dass nur die sporadische Aufgabe ihre Rechtzeitigkeitsbedingung verletzt, wenn die Auslastung 100 % aufweist.

Echtzeitnachweis

Da alle Aufgaben zyklisch abgearbeitet werden und deren Prioritäten nach der Rate-Monotonic – Annahme vergeben wurden, kann ein Echtzeitnachweis über die Hinreichende Scheduling Bedingung erfolgen. Zusätzlich muss noch die 1. Echtzeitbedingung geprüft werden.

Umwandlung von azyklischen in zyklische Aufgaben

Für sporadische Tasks müssen für den Scheduler zusätzliche Angaben gemacht werden, um sie zyklisch verwalten zu können. Neben der Priorität des zyklischen Prozesses, muss eine Prozesszeit bestimmt werden, die eine Abschätzung der Häufigkeit dieses Ereignisses widerspiegelt. Um die Ausführungszeit zu beschränken, muss eine Prozesszeit für diese Aufgabe dem Scheduler bekannt sein. Sollte die Aufgabe in der angegebenen Zeit nicht fertig werden, wird die Aufgabe automatisch auf eine konfigurierte Hintergrundpriorität herabgestuft.

Umsetzung in POSIX

Für jeden sporadischen Task müssen in POSIX die folgenden Werte spezifiziert werden:

• Replenishment Period:[T] Die angenommene Prozesszeit: Innerhalb dieser Zeit kann der Task seine Ausführungszeit C verbrauchen
• Initial Budget:[C] Ausführungszeit, die ein Thread mit normaler Priorität innerhalb der Replenishment Period läuft, bevor er auf die geringere Priorität L gesetzt wird.
• Priority:[N] Priorität, mit der der Thread läuft, solange sein Initial Budget nicht verbraucht ist.
• Low Priority:[L] Priorität, auf die der Thread gesetzt wird, sobald seine Ausführungszeit verbraucht ist.
• Maximal number of pending replenishments : Begrenzung des Systemoverheads durch Beschränkung der Replenishments.

Ablauf eines Scheduling-Intervalls

Zeitpunkt	Aktion
t0	Task erhält CPU
t1	CPU wird entzogen. Für Zeitpunkt t0 + T wird geplant, C um die verbrauchte Rechenzeit (t1-t0) zu erhöhen.

Quellen

• developer.blackberry.com: Sporadic scheduling