Modell der Systemfunktion (Alte Version)

Um dieses Verhaltensmodell zu bedienen, benötigt man das Modell eines Systems, das das geforderte Verhalten bedienen kann. Dazu wählen wir als Einstieg zwei Darstellungsweisen: (i) Grafische Darstellungen der Systemkomponenten und (ii) eine formale (mathematische) Darstellung der Struktur. Die Struktur wird dann weiter konkretisiert.

Die Grundelemente eines Realzeitsystems für diese Aufgabe kann man der grafischen Darstellung 2.6 entnehmen:

Figure 2.6: RTS-Systemfunktion Daten- und Funktions-Komponenten

$$RTS(x) gdw \langle E, Q, Q^{*}, X, TT, \Gamma, \Pi, RES, Sched \rangle$$ (2.1)

$$RES = \{CLCK_{int},CPU, CRES\}$$ (2.2)

mit

$$TT : E \longmapsto \Gamma$$ (2.3)

$$\Gamma \subseteq \Phi \times T \times D \times C$$ (2.4)

Auf der Inputseite kann das System RTS registrieren, zu welchem Zeitpunkt $CLCK_{ext,int}$ welche Ereignisse $E$ aus der Umgebung auftreten. Zugleich verfügt es über eine Technische Tabelle $TT$, anhand deren eine Zuordnung von Ereignissen zu Tasks $\Gamma$ stattfinden kann. Hier wird angenommen, daß auch wetere wichtige Informationen sowohl zu den Ereignissen $E$ -also Auftretenszeit $\Phi$, Deadline $D$ und Periode $T$- wie auch zu den einzelnen Tasks -hier vor allem die Gesamtausführungszeit ('computation time') $C$- festgehalten sind. Ferner gibt es eine Menge von Prioritätsregeln $PRIOR, \Pi$, anhand deren sich die Prioritäten für aktuelle Tasks berechnen lassen. Aus der Menge der aktuellen Ereignisse $E$ und der Menge der noch wartenden Tasks aus den vorausgehenden Zeitpunkten $Q$ wird die Menge $Q$ jeweils neu gebildet. Treten kritische Ressourcen $CRES$ auf, so müssen diese zusätzlich verwaltet werden. Bezüglich der Ressourcen $RES$ kann man weitere Unterscheidungen treffen. Neben den kritischen Resssourcen gibt es eine interne Uhr $CLCK_{int}$ und mindestens einen Prozessor ('central processing unit') $CPU$. Es ist Aufgabe des Scheduling-Algorithmus $Sched$ aus allen diesen Daten den Task $\tau_{i} \in \Gamma$ zu ermitteln, der aktuell ausgeführt werden soll, geschrieben $\tau_{i} \in X$ (mit $X$ als die Menge der aktuell auszuführenden Tasks.

Scheduling Algorithmus: Die Grundstruktur eines Schedulingalgorithmus für Realzeitsysteme läßt sich durch folgendes einfaches Schema beschreiben:

Der Schedulingalgorithmus $Sched$ beginnt mit der Nullsetzung der Parameter $t, X, Q$. $t \in CLCK_{int}$ ist die aktuelle Zeit, $X \subseteq \Gamma$ ist die Menge der aktuell auszuführenden Tasks und $Q$ ist die vereinigte Menge der neuen $TT(E)$ und der noch nicht vollendeten Tasks. Die aktive Schleife des Algorithmus beginnt mit der Überprüfung, ob die zuletzt ausgeführten Tasks aus der Menge X schon vollständig abgearbeitet sind. Falls 'JA', dann werden sie aus der Menge Q entfernt: if(checkX(X) == FINISHED) then Q = Q - X. Anschließend wird die Menge X auf jeden Fall auf Null gesetzt, da für den neuen Zyklus alle Tasks -auch die noch in Verarbeitung befindlichen- bezüglich ihrer Prioritäten neu überprüft werden müssen. X = $\emptyset$. Danach werden alle Tasks ermittelt, die aufgrund neuer Ereignisse zu Q hinzukommen müssen: $Q = Q + TT(E)$. Nachdem die Menge $Q$ neu gebildet wurde, muss $Q$ mittels der gewünschten Prioritätsregeln $\Pi$ als Menge $Q^{*}=order(Q,\Pi)$ neu nach Prioritäten geordnet werden. Nachdem geklärt wurde, in welcher Reihenfolge die Tasks ausgeführt werden müssen, kann man überprüfen, ob einer dieser Tasks $\tau_{i}$ aus $Q^{*}$ seine relative Deadline $D_{i}$ überschritten hat. Falls dies der Fall ist, also checkD($Q^{*}$) == true), dann stoppt der Algorithmus mit einer Fehlermeldung; das Scheduling hat dann versagt. Wurde keine Deadline gebrochen, dann wird das erste Element aus $Q^{*}$ ausgewählt und in die Menge $X$ eingefügt $first(Q_{*}) \in X$.

Man kann leicht erkennen, dass dieser Algorithmus entweder nach endlichen vielen Schritten terminiert, wenn eine Deadline nicht bedient werden konnte, oder aber er läuft beliebig lange weiter, indem immer genau der Task mit der höchsten Priorität bearbeitet und ausgeführt wird.

Implementierung: Es gibt vielfältige Möglichkeiten, dieses Modell eines RTS mit einem Scheduler wie $Sched$ zu implementieren (siehe Übungsaufgaben).

Validierung: Nachdem ein Modell implementiert wurde, soll es getestet werden. Dies geschieht hier mit den Daten des Verhaltensmodells. Dazu nehmen wir an, dass die Prioritätsregel $\Pi$ anhand der Rate Monotonic (RM)-Regel definiert sein soll. Die RM-Regel lautet:

$$T_{i} < T_{j} \Longrightarrow P_{i} > P_{j}$$ (2.5)

mit der zusätzlichen Annahme, dass $D_{i} = T_{i}$, d.h. wenn die Periode $T_{i}$ des i-ten Ereignisses $e_{i}$ kleiner ist als die Periode $T_{j}$ des j-ten Ereignisses $e_{j}$, dann ist die Priorität $P_{i}$ des i-ten Ereignisses $e_{i}$ grßßer als die Priorität $P_{j}$ des j-ten Ereignisses $e_{j}$.

Eine Möglichkeit der Validierung besteht darin, das System anhand eines Zeitdiagramms zu überprüfen (vgl. Schaubild 2.7).

Figure 2.7: Loesungsbeispiel für eine Taskmenge mit RM-Prioritaetsregel

CLCK = -1:

Q = TT(E)= {1,2,3}; $Q^{*}$ = order({1,2,3}, RM) = {1,2,3}; first($Q^{*}$) = '1'; X={1}

CLCK = -1:

TT(E)={ }; Q = Q-X+TT(E)= {2,3}; $Q^{*}$ = order({2,3}, RM) = {2,3}; first($Q^{*}$) = '2'; X={2}

CLCK = -1:

TT(E)={ }; Q = Q-X+TT(E)= {3}; $Q^{*}$ = order({3}, RM) = {3}; first($Q^{*}$) = '3'; X={3}

CLCK = -1:

TT(E)={ 1 }; Q = Q-X+TT(E)= {1,3}; $Q^{*}$ = order({1,3}, RM) = {1,3}; first($Q^{*}$) = '1'; X={1}

CLCK = -1:

TT(E)={ 2 }; Q = Q-X+TT(E)= {2,3}; $Q^{*}$ = order({2,3}, RM) = {2,3}; first($Q^{*}$) = '2'; X={2}

CLCK = -1:

TT(E)={ }; Q = Q-X+TT(E)= {3}; $Q^{*}$ = order({3}, RM) = {3}; first($Q^{*}$) = '3'; X={3}

CLCK = -1:

TT(E)={1,3 }; Q = Q-X+TT(E)= {1,3}; $Q^{*}$ = order({1,3}, RM) = {1,3}; first($Q^{*}$) = '1'; X={1}

CLCK = -1:

TT(E)={ }; Q = Q-X+TT(E)= {3}; $Q^{*}$ = order({3}, RM) = {3}; first($Q^{*}$) = '3'; X={3}

CLCK = -1:

TT(E)={2 }; Q = Q-X+TT(E)= {2,3}; $Q^{*}$ = order({2,3}, RM) = {2,3}; first($Q^{*}$) = '2'; X={2}

CLCK = -1:

TT(E)={1 }; Q = Q-X+TT(E)= {1,3}; $Q^{*}$ = order({1,3}, RM) = {1,3}; first($Q^{*}$) = '1'; X={1}

CLCK = -1:

TT(E)={ }; Q = Q-X+TT(E)= {3}; $Q^{*}$ = order({3}, RM) = {3}; first($Q^{*}$) = '3'; X={3}