Einführung

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

Startseite   Tutorials   Einführung