![]() |
Real-Time Scheduling-Algorithmen |
Die Ablaufplanung (Scheduling) ist eines der Hauptprobleme bei der Implementierung von Echtzeitsystemen.
Scheduling-Algorithmen können beim Entwurf eines Echtzeitsystems an verschiedenen Stellen benötigt
werden. Sehr grobe Schätzungen können bereits beim Erstellen der Spezfikation notwendig sein. Während
der Hardware/Software-Partitionierung sind genauere Vorhersagen über Schedules nötig. Nach
der Übersetzung der Software sind noch genauere Informationen über die Ausführungszeiten von Tasks
verfügbar, womit das Scheduling präzisiert werden kann. Schließlich ist es notwendig, zur
Laufzeit zu entscheiden, welche Task als nächstes ausgeführt wird.
Das Scheduling hängt eng mit Echtzeitbetriebssystemen (Real-Time Operating Systems(RTOS)) zusammen.
Trotzdem sind einige der Scheduling-Techniken vom verwendeten RTOS vollkommen unabhängig.
Scheduling-Algorithmen können nach verschiedenen Kriterien unterschieden werden. Einige der wichtigsten Kriterien zur Klassifizierung von Scheduling-Algorithmen sind:
Weiche und harte Zeitbedingungen:
Das Scheduling für weiche Zeitbedingungen basiert häufig
auf Erweiterungen von Standard-Betriebssystemen. Beispielsweise können Task- und Betriebssystemaufruf-
Prioritäten für ein System mit weichen Zeitbedingungen ausreichend sein. Für harte
Echtzeitanforderungne ist deutlich mehr Aufwand und eine detailliertere Analyse notwendig.
Scheduling für periodische und aperiodische Tasks:
Es wird zwischen periodischen, aperiodischen
und sporadischen Tasks unterschieden.
Tasks, die alle p Zeiteinheiten ausgeführt werden müssen,
heißen periodische Tasks, und p heißt ihre Periode. Jede Ausführung
einer periodischen Task heißt Job. Die Ausführungszeit c aller Jobs, die
zu einer Task gehören, wird als immer gleich angenommen. Die Zeit zwischen dem Zeitpunkt, zu dem eine
Task verfügbar wird und dem Zeitpunkt, zu dem die Ausführung beendet sein muss, heißt
Deadline-Intervall d. Der Spielraum (laxity oder Schlupf) l
wird definiert als l = d - c.
Tasks, die nicht periodische sind, heißen aperiodische Tasks. Die Begriffe Ausführungszeit,
Deadline-Intervall und Spielraum gelten auch für aperiodische Task.
Aperiodische Tasks, die den Prozessor zu unvorhersehbaren Zeiten anfordern, heißen sporadisch,
wenn eine minimale Zeit zwischen den Zeitpunkten vergeht, zu denen die Tasks den Prozessor anfordern.
Präemptives und nicht-präemptives Scheduling:
Nicht-präemptive Scheduler basieren
auf der Annahme, dass Tasks solange ausgeführt werden, bis ihre Ausführung abgeschlossen ist.
Folglich kann die Reaktion auf externe Ereignisse recht spät erfolgen, wenn einige Tasks eine lange
Ausführungszeit haben. Präemptive Scheduler, bei denen die Ausführung einer Task vom
Scheduler unterbrochen werden kann, müssen verwendet werden, wenn einige Tasks lange Ausführungszeiten
haben oder wenn die Reaktionszeit auf externe Ereignisse kurz sein muss.
Statisches und dynamisches Scheduling:
Dynamische Scheduler treffen ihre Entscheidungen zur Laufzeit.
Sie sind flexibel, erfordern aber zusätzlichen Aufwand zur Laufzeit. Man nennt sie daher auch on line-
Scheduler. Statische Scheduler treffen Entscheidungen zur Entwurfszeit, man spricht daher
auch von off line-Scheduling. Sie planen die Startzeiten der Tasks und erzeugen entsprechende Tabellen,
in denen die Startzeiten vermerkt sind. Die Tabellen werden an einen einfachen Dispatcher
weitergeleitet, der keine Entscheidungen trifft, sondern lediglich Tasks zu den in den Tabellen
angegebenen Zeiten startet.
Mono- und Multiprozessor-Scheduling:
Einfache Scheduling-Algorithmen behandeln lediglich
Ein-Prozessorsysteme, wohingegen komplexere Algorithmen auch mit Systemen umgehen können, die
aus mehreren Prozessoren bestehen. In diesem Fall kann man zwischen Algorithmen für homogene
Multiprozessorsysteme und solchen für heterogene Multiprozessorsysteme unterscheiden.
In den folgenden Unterkapiteln finden Sie eine kurze Beschreibung der Scheduling-Algorithmen, die Ihnen in diesem Lernmodul zur Verfügung stehen.
Einführung > Real-Time Scheduling-Algorithmen
zurück | weiter |