ANHANG: RTS Grundbegriffe

Ausgehend von diesen allgemeinen Bestimmungen eines Realzeitsystems kann man jetzt noch einige weitere Eigenschaften anführen. So benötigen Prozesse in der realen Welt immer Ressourcen, und diese benötigen, sofern sie in Prozesse eingebunden sind, generell Zeit. Zeit wiederum wird technisch realisiert durch eine Uhr, deren unterscheidbaren Zeitpunkte sich als Zeitmarken extern und intern repräsentieren lassen. Ohne solche Zeitmarken könnte man ein bestimmtes System S1 nicht mit einem anderen System S2 synchronisieren.

Die Ereignisse kann man nach ihrer 'Herkunft' charakterisieren oder nach dem zeitlichen Muster ihres Auftretens. Nach Herkunft kann man unterscheiden zwischen externen (ein Stimulus), internen (ein Interrupt) und zeitbedingten (ein Taktereignis). Nach dem zeitlichen Muster ihres Auftretens kann man unterscheiden periodische, sporadische oder aperiodische Ereignisse. Periodische Ereignisse sind solche, die nach bekannten, festen Zeitintervallen auftreten. Sporadische Ereignisse treten 'irgendwann' auf, man weiss nicht, wann, aber, wenn sie auftreten, dann vergeht eine bekannte definierte minimale Zeitspanne bis zum nächsten Auftreten. Aperiodische Ereignisse sind hinsichtlich ihres Verhaltens in der Zeit völlig unbestimmt; sie können zu beliebigen Zeitpunkten mit beliebigen Intervallen auftreten. Weitere Charakterisierung von Ereignissen ist möglich, z.B. eine Charakterisierung bzgl. der Abhängigkeit der Ereignisse untereinander. Weitere häufig vorkommende Unterscheidungen sind z.B. auch gebundene Ereignisse; dies sind solche, die entweder mit einer minimalen oder einen maximalen Zeit zwischen ihrem auftreten beschreibbar sind. Ferner gibt es noch die Unterscheidung gehäufte ('bursty') Ereignisse. Diese sind gekennzeichnet durch ein Häufungsintervall ('burst interval') und eine Häufungsgrösse ('burst size'); beide Grössen zusammen liefern die Häufungsdichte ('burst density'). Ein Beispiel wäre eine Anzahl von 50 Transaktionen innerhalb von 1 Sekunde, wobei das genaue Auftreten dieser Transaktionen innerhalb dieser Sekunde offen ist. Statt von aperiodischen Ereignissen kann man dann auch von ungebundenen Ereignissen sprechen; diese haben keinerlei Beschränkungen.

Die Ressourcen des Systems werden gebildet durch alle Betriebsmittel, die vom System in Anspruch genommen werden. Am wichtigsten sind hier natürlich die verfügbare CPU-Zeiten, die verfügbaren Speicher und Komunikationskanäle mit den daran geknüpften Transaktionszeiten. Zu beachten sind auch Latenzzeiten hervorgerufen z.B. durch Unterbrechungen ('interrupts'), Speicherzugriffe, komplexe Befehle (wie Divison), Sprünge und damit verbundene Umgruppierungen in der CPU-Pipeline) oder auch Umschaltzeiten durch Kontextwechsel). Welche Systemfunktion auch immer ausgeführt werden mag, die durch die Ressourcen vorgegebenen Eckwerten dürfen nicht unterlaufen werden und müssen daher vollständig in der Analyse eines Realzeitsystems eingebracht werden.

Die Verwaltung der Tasks -meist Scheduling genannt- hat darüber zu entscheiden, welcher Task bei welchem Ereignis welche Ressource zugeteilt bekommt. Dabei ist zu beachten, dass die Task-Verwaltung selbst auch Ressourcen benötigt! In einem schlecht aufgesetzten System kann die Task-Verwaltung u.U. mehr Ressourcen benötigen als die Tasks selbst. Hierfür gibt es den Begriff des WCAO := Worst Case Administrative Overhead.

Im Falle der Tasks sind zwei Unterscheidungen wichtig: ob ein Task t von einem Task t' abhängig oder unabhängig ist, oder ob ein Task während seiner Ausführung unterbrochen werden darf -Präemption (engl.: 'preemption')- oder nicht.

Unter Berücksichtigung der hier genannten Eigenschaften wären also Systeme mit Systemfunktionen, die nur unabhängige Tasks zulassen, die nicht präemptiv sind (nicht unterbrochen werden dürfen), die 'theoretisch einfachsten' Systeme.

Auch im Bereich der Tasks ist die Unterscheidung in periodische, sporadische sowie aperiodische üblich. Die Bedeutung ist analog zur Menge der Ereignisse.

Für manche Analysen erweist es sich als hilfreich, wenn man den Begriff des 'Task' nochmals weiter herunterbricht auf das Konzept der Aktion als kleinstmöglichster Analyseeinheit. Eine Aktion selbst ändert laut Definition keine Ressourceneinstellung, wohl aber beginnen und enden Aktionen mit sogenannten Planungs-Punkten ('scheduling points'). Die Planungspunkte korrelieren mit Zeitpunkten, an denen Entscheidungen bzgl. Ressourcennutzung vorgenommen werden können (z.B. Änderung der Priorität, Start/Stopp von I/O-Aktivitäten, Synchronisierung mit anderen Aktionen).

Schliesslich muss man die Typen der Interaktion der Tasks/Aktionen festlegen. Mindestens zwei Typen erweisen sich als wichtig: in einer sequentiellen ('sequential') Ordnung folgen die Tasks einer nach dem anderen; in einer parallelen ('parallel') Ordnung können die Tasks zeitlich gleichzeitig auftreten. Formal kann man die Menge der Tasks und deren Anordnung als Graphen repräsentieren. Dazu nehmen wir $K$ als eine endliche Menge von Knoten ('nodes', 'vertices') und $O =\{s,p\}$ als eine endliche Menge von $Ordnungstypen \{s := sequentiell, p := parallel\}$ an. Es soll dann gelten

$$AtomareTasks = \{t\vert t \in K \times O \times K \}$$

Atomare Tasks wären dann z.B. $\langle t1,s,t2 \rangle$ (auch geschrieben als $t1 \longrightarrow t2$) oder $\langle t1,p,t2 \rangle$ (auch geschrieben als $t1 \parallel t2$). Dann können wir die Menge der Tasks $TASK$ wie folgt definieren:

1. $AtomareTasks \subseteq TASK$
2. $t,t' \in TASK \Longrightarrow \langle t,s,t' \rangle \in TASK \wedge \langle t,p,t' \rangle \in TASK$
3. Nur was nach (1) und (2) gebildet wird ist ein Task

Ein Beispiel für einen nicht atomaren Task ist folgender Ausdruck (vgl. auch Bild 14.1):

$$A \longrightarrow ( B \parallel C )$$

In diesem Beispiel folgen auf ein System A sequentiell zwei Systeme B und C, wobei B und C untereinander parallel sind.

Figure 14.1: Graph mit drei Systemen A,B,C sequentiell und parallel

Da wir schon wissen, dass ein Task nicht nur eine rein 'logische' Grösse ist, sondern unterschiedlichste Ressourcen benötigt, die wiederum eine Auswirkung auf den Zeitbedarf haben, muss man den Taskgraphen mit zusätzlichen Informationen anreichern.

Für jeden Task muss eine Reihe von Eigenschaften geklärt werden, die die Basis für die weitere Analyse bilden. Die wichtigsten Eigenschaften sind hier aufgeführt:

Welche Ressourcen ein Task benötigt, z.B. CPU, Datenobjekt, Device, Bus, LAN, anderes

PRIORITÄT:

Prioritäten sind geordnete Werte, die bei der Zuteilung von Ressourcen benutzt werden, um Präferenzen zu realisieren. Z.B. (höchster Wert zuerst) Hardware, Kernel, very high, high, medium, low, very low, +. '+' wird benutzt, um anzuzeigen, dass die Priorität von einem vorausgehenden Task geerbt wird.

NUTZUNGSZEIT:

Jene Zeit ('usage', 'time used'), für die ein Task eine Ressource benötigt, wenn er nicht konkurrieren muss. Falls die Ressource eine CPU ist, spricht man von Ausführungzeit ('execution time'). Gewöhnlich wird die 'worst-case' Zeit genommen; es gibt aber auch Fälle, wo eine durchschnittliche Zeit ('average time') nützlich ist

RESSOURCEN-ALLOKATIONS-POLICY:

Diese ist abhängig von der jeweiligen Ressource.

1. Im Falle der Ressource CPU würde man von einer CPU_POLICY sprechen (z.B.: Fixed priority, Dynamic Priority, Round Robin, Time Slice, Cyclic executive).
2. Im Falle eines Datenobjektes von einer DATA_POLICY (z.B.: FIFO, Priority Queue, Basic priority Inheritance Protocol (PIP), Highest Locker (HL), Priority Ceiling Protocol (PCP))
3. Im Falle von Devices von einer DEVICE_POLICY (z.B.: FIFO, Priority Queue)
4. Im Falle von einem Bus von einer BUS_POLICY (z.B.: FIFO, Hardware Priority Policy, Hardware Slot Policy, Software Priority Policy )
5. Im Falle von Netzwerk-Adaptern von einer ADAPTER_POLICY (z.B.: FIFO, Message Priority Policy, Connection Priority Policy)
6. Im Falle von Netzwerk-Medium von einer LAN_POLICY (z.B.: Ethernet, Token-Ring, FDDI etc.)

EXKLUSIVITÄT:

Kann der Task die Ressourcen alleine benutzen oder muss der Task die Ressourcen mit anderen Tasks teilen.

WELCHER JITTER:

Man muss festlegen, welche Art von Jitter -falls überhaupt- berücksichtigt werden soll (s.u.).

Eine andere bewährte Darstellungsform ist die Tabelle. Sehr ausführliche Darstellungen findet man z.B. in dem exzellenten Handbuch Mark H.KLEIN et al. 1993:3-35ff[44]. Wir übernehmen für unsere Zwecke eine vereinfache Form, die bei Mark H.KLEIN et al. 1993:3-40 'technique table' heisst; wir nennen sie analog technische Tabelle:

Event (e)	Rel. (r)	Period	Task (a)	Exec. (C))	Prior. (P))	Blockg. (B))	Deadl. (D)
e1	r0 = 0	40	a1	4	v.high	0	40
e2	r0 = 0	150	a2	10	high	15	150
e3	r0 = 0	180	a3	20	medium	0	180
e4	r0 = 0	250	a4	10	low	5	250
e5	r0 = 0	300	a5	80	v.low	0	300

Event ID:

Eine eineindeutige Bezeichnung des Ereignisses

Release Time:

Zeitpunkt zu dem das Ereignis erstmalig auftritt. Standardmässig wird Zeitpunkt t=0 angenommen.

Period:

Periode, Zeidauer zwischen dem Auftreten und Wiederauftreten eines Ereignisses

Task ID:

Eine eineindeutige Bezeichnung des Tasks

Execution Time:

Zeitdauer für die vollständige Ausführung eines Tasks

Priority:

Priorität eines Tasks während des Verwaltens (Scheduling) der aktiven Tasks

Blocking Delay:

Damit ist gemeint, dass ein abhängiger Task t bei seiner Ausführung auf die Beendigung anderer Tasks t' warten muss. Die Ausführungszeit dieser anderen Tasks t' blockiert den wartenden Task t. Davon zu unterscheiden ist die Wartezeit, die dadurch entsteht, dass in einem präemptiven System ein Task warten muss, weil ein anderer eine höhere Priorität hat.

Deadline:

Relative Deadline vom letzten Auftreten eines Ereignisses bis zur vollständigen Ausführung des zugehörigen Tasks.