Seite 1

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingBewerten von (dyn.)Scheduling-Verfahren

Folgende grundlegenden Fragen sind zu beantworten:1) Ist es überhaupt möglich, alle Zeitbedingungen einzuhalten? Wenn ja, dann existiert

ein so genannter Schedule, d.h. eine zeitliche Aufteilung des Prozessors an die Task, die die Aufgabe löst.

2) Wenn dieser Schedule existiert, kann er in endlicher Zeit berechnet werden?3) Findet das Scheduling-Verfahren diesen Schedule, wenn er existiert und in

endlicher Zeit berechnet werden kann? (optimales Schedulingverfahren)

Verfahren Abk. Bewertung

FIFO Kann Einhaltung der Zeitbedingungen nicht garantieren trotz geringer Prozessorauslastung von z.B. 20%

Fixed Prio (preemptive) FPP Besser als FIFO, kein optimales S.-Verfahren

Fixed Prio (non-preemptive) FPN kein optimales S.-Verfahren

Least Laxity first (dynamisches S.) LLF Optimales S.-Verfahren für Einprozessorsysteme, wenn präemptiv verwendet, höherer Rechenaufwand als EDF

Guaranteed Percentage GP Optimales S.-Verfahren für Einprozessorsysteme, keine Abh. der Periodendauer von der Anzahl der Tasks

Time Slice Einfache Realisierung, Abh. der Periodendauer von der Anzahl der rechenwilligen Tasks

Earliest Deadline first (dynamisches S.)

EDF Optimales S.-Verfahren für Einprozessorsysteme, wenn präemptiv verwendet

Seite 2

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingProzessorauslastung

Prozessorauslastung (processor demand): H = benötigte Prozessorzeit / verfügbare Prozessorzeit

Beispiel Ausführungszeit Periodendauer H

Periodische Task 1

100 ms 200 ms 0,5

Periodische Task 2

50 ms 100 ms 0,5

Prozessorauslastung für beide Task ist 100% (Summe).

Bei einer Prozessorauslastung von <= 100% sollte immer ein Schedule existieren.

Seite 3

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingZeitparameter bei den Taskzuständen

t [ms]

ruhend

ablaufwillig

laufend

a r s c d

p

j e lTaskzu-

stände

a: Ankunftszeit (Arrival Time)r: Anforderungszeit (Request Time)s: Startzeit (Start Time)c: Beendigungszeit (Completion Time)d: Zeitschranke (Deadline)j: Reaktionszeit (Reaction Time, Release Jitter)e: Ausführungszeit (Execution Time)l: Spielraum (Laxity)p: Periode (Period)

Seite 4

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingFixed Priority Verfahren

Bei rein periodischen Anwendungen bekommen diejenigen Tasks die höchste Priorität zugewiesen, die die kürzeste Periodendauer haben (Rate-Monotonic Scheduling). Unter der Voraussetzung, dass• präemptives Scheduling verwendet wird,• die Periodendauer konstant ist,• die Zeitschranke (deadline) gleich der Periodendauer ist,• die Ausführungszeit konstant und bekannt ist und• die Tasks unabhängig voneinander sind, dann

gilt (Busy Period Analysis):

Tritt bei periodischen Tasks keine Verletzung der Zeitschranken bis zu dem Zeitpunkt auf, an dem der Prozessor das erste Mal in den Ruhezustand übergeht, dann wird auch danach keine Verletzung der Zeitschranken mehr auftreten.

Seite 5

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingÜbung 1

Aufgaben (Voraussetzung: Tasks werden EINEM Prozessor zugeteilt):1) Vergeben Sie die Prioritäten nach dem Rate Monotonic Prinzip 2) Stellen Sie den zeitlichen Verlauf aller 4 Tasks dar unter der Voraussetzung, dass alle Tasks gleichzeitig bereit sind (s. Lösungsblatt 1)3) Zeichnen Sie für die Task 3 ihre Zustände (ruhend, ablaufwillig, laufend) über eine Zeitachse von 0 bis 250 ms (s. Lösungsblatt 2).

Ausführungszeit Periodendauer Priorität

Task 1 20 ms 500 ms ?

Task 2 10 ms 40 ms ?

Task 3 30 ms 160 ms ?

Task 4 40 ms 110 ms ?

Seite 6

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingLösungsblatt 1

Task 4

100

t [ms]

Priorität

Task 3

Task 1

50 150 200

Lösung zu Aufgabe 1:In Abhängigkeit der Periodendauer ergibt sich folgende Prioritätsvergabe:P(2) > P(4) > P(3) > P(1)

Vorlage zur Aufgabe 2:

Task 2

250

Seite 7

BA Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme Aug 2008

SchedulingLösungsblatt 2

100

t [ms]

Zustand von Task 3

50 150 200

Taskzustände in Abhängigkeit der Zeit

250

ruhend

ablaufwillig

laufend

blockiert

In einem rein zeitgesteuerten System entfällt der Zustand blockiert (stattdessen ruhend). In ereignisgesteuerten Systemen wartet die Task auf ein Zeitgeberereignis und ist dann dem Zustand blockiert zuzurechnen.