Achtung : Skript gibt den mündlichen Vortrag nur teilweise wieder !!!
                        

1. Einführung; logische und zeitliche Domäne

Mit der Einführung des Zeitbegriffs kommt eine Fülle neuer interessanter Begriffe ins Spiel, die es möglich machen, technische Systeme nicht nur nach ihrem logischen Verhalten zu charakterisieren, sondern auch nach ihrem zeitlichem Verhalten.

Als zentraler Grundsatz gilt hier, dass die Zeit Priorität über die Logik hat! Damit ist nicht gemeint, dass die Logik gleichgültig oder weniger Wert ist, sondern dass die Einhaltung der zeitlichen Anforderungen absolute Priorität besitzt. Ein Programm mag logisch noch so 'schön' sein, wenn es die Zeitanforderungen nicht einhalten kann, dann kann es nicht verwendet werden. Dies bedeutet, dass jede Programmlogik im Kontext von Realzeitsystemen immer auch unter dem Aspekt ihres zeitlichen Verhaltens zu betrachten ist. Für jede einzelne Funktion muss offen liegen, wieviel Zeit sie benötigt, und im Falle von interagierenden Funktionen muss deren Gesamtbedarf an Zeit zweifelsfrei geklärt sein. mehr noch, dieser analysierte Zeitbedarf muss innerhalb bestimmter Eckwerte garantiert werden! Ohne solche Garantien sind Realzeitsysteme nicht möglich bzw., würde man Systeme ohne solche Garantieren bauen, der Einsatz solcher nicht vollständig garantierter Systeme wäre ein nicht vertretbares Sicherheitsrisiko.

Aus diesen Überlegungen folgt u.a., dass die Anforderungen an das Softwareengineering von Realzeitsystemen erheblich höher sind als für Nicht-Realzeitsysteme. Und wenn man weiss, wie schwer schon die Bereitstellung guter softwaretechnischer Verfahren für Nicht-Realzeitsysteme ist, dann wird man sich nicht wundern, dass es im Bereich Softwareengineering von Realzeitsystemen noch erhebliche Lücken zu verzeichnen gibt. Hier liegt eine grosse Herausforderung an die Informatik.

Einige der zentralen Aspekte bei der Analyse des Realzeitbedarfs von Realzeitsystemen sollen nun weiter herausgearbeitet werden, insbesondere der Begriff der Zuverlässigkeit (engl.: reliability).

START

2. Zuverlässigkeit (Reliability)

(Die Ausführungen zur Zuverlässigkeit orientieren sich am Kap.7 des sehr guten Buches von [STOREY 1998]; für mehr Details und weitere Informationen sei auf dieses Buch verwiesen).

Einer der wichtigsten Aspekte von Realzeitsysteme ist sicher der ihrer Zuverlässigkeit (Reliability), definieren sie sich doch gerade dadurch, dass sie --im Gegensatz zu Nicht-Realzeitsystemen (siehe Klassifikation weiter unten)-- bestimmte Zeitvorgaben (Deadlines) einhalten. Andererseits weiss man, dass Realzeitsysteme konkrete technische Systeme sind und damit im Bereich Hardware und Software Fehlfunktionen aufweisen können, die die Zuverlässigkeit beeinträchtigen können.

Nehmen wir im folgenden an, dass ein System aus verschiedenen Komponenten (components) besteht, die entweder hintereinander oder parallel geschaltet sein können und die alle zum Gesamtverhalten des Systems beitragen. Nehmen wir ferner an, dass die möglichen Fehler (failures) nicht systematischer, sondern nur zufälliger (random) Natur sind

START

2.1 Verknüpfte Systeme

Um die nachfolgend benötigten Begriffe einführen zu können, muss an dieser Stelle der Systembegriff aus der vorausgehenden Vorlesung geringfügig erweitert werden. Wir unterscheiden nun zwischen atomaren Systemen (ASYS) und Systemen (SYS), die komplex sein können. Komplexe Systeme entstehen dadurch, dass man sie sequentiell oder parallel schaltet oder beliebige Kombinationen von sequentiellen und parallelen Verbindungen bildet.

mit I := Inputmenge, O := Outputmenge, IS := Menge von internen Zustaenden und f := Systemfunktion mit
f : I x IS ---> O

Man kann dann definieren:

Ausgehend von der Basismenge der atomaren Systeme ASYS kann man jetzt induktiv eine komplexe Obermenge SYS definieren:

Das nachfolgende Bild zeigt ein einfaches komplexes Systems A mit zwei sequentiell geschalteten Einheiten AND(1,2) und AND(3,4); diese beiden Einheiten sind wiederum parallel angeordnet OR( ...). Der Output des Systems hängt also davon ab, ob entweder die Serie (1,2) funktioniert oder die Serie (3,4).

START

2.2 Fehlerrate Lambda eines Systems

Ein konkretes System S besteht gewöhnlich aus Hardware oder Hardware und Software. Dabei besitzt jedes System ganz spezifische Eigenschaften die ein ganz spezifisches Fehlerverhalten bedingen. Besteht das System aus Standardkomponenten, die nach Standardverfahren zusammengebaut werden, dann kann man aufgrund von empirischen Daten zu solchen System das Verhalten des Systems bezüglich der Fehlerrate parametrisieren. Ein Vorrreiter war in diesen Dingen das amerikanische Verteidigungsministerium (Department of Defense (DoD)), das aufgrund der immensen Komplexität der militärischen Systeme schon sehr früh gezwungen war, die Herstellungs- und Testverfahren von militärischen Systemen zu standardisieren. In diesem Zusammenhang wurden über die Jahre umfangreiche Daten gesammelt, die im Dokument MIL-HDBK-217 zusammengetragen worden sind (man beachte die Updates!).

Eine allgemeine Definition der Fehlerrate Lambda ist die folgende:

Angenommen, ein System s1 hat 5 Fehler in 10^6 Stunden, dann würde gelten

Lambda(S1) = 5/1*10^6 h = 0.000005

Im Standard MIL-HDBK-217 werden zahlreiche Bauteile 'normiert'. So wird z.B. die Fehlerrate Lambda für Halbleiter Speicherbausteine angegeben mit der Formel:

START

2.3 MTTF (Mean Time To Failure)

Hat man Lambda gegeben, dann kann man eine Reihe weiterer Begriffe definieren. Z.B. wird die Grösse MTTF wie folgt definiert:

MTTF = 1/Lambda

Bsp: Ein Webserver, der 1x pro Woche ausfällt hätte also die Werte:

(1 Woche = 24h * 7 = 168h)

Lambda = 1/168 = 0.0059524

MTTF = 1/lambda = 168h

START

2.4 MTTR ('Mean Time to Repair')

Wartbarkeit hat damit zu tun, wieviel Zeit man benötigt, um das Auftreten eines Fehlers im System zu entdecken, ihn zu lokalisieren, ihn zu beheben und das System wieder in den korrekten betriebsfähigen Zustand zu versetzen. Ein hier vielfach benutzter Begriff ist der Begriff Mittlere Zeit zur Wiederherstellung ('Mean Time to Repair', MTTR). Setzt man eine konstante Reparaturrate my an (Reparaturen pro Stunde), dann kann man --analog zu MTTF-- vereinbaren: MTTR = 1/my.

START

2.5 MTBF ('Mean Time Between Failure')

MTBF = MTTF + MTTR

START

2.6 Availability/ Unavailability

Verfügbarkeit beschreibt die Zeit, in der ein Dienst verfügbar ist (MTTF) im Verhältnis zur Zeit in der er wegen Reparatur nicht verfügbar ist (MTTR) und verfügbar ist (MTTF), also MTTR+MTTF. Im Falle konstanter Fehler- und Reparaturraten gilt dann:

A = MTTF/(MTTF+MTTR)

Unavailability = 1 - Availability

Das nachfolgende Schaubild fasst einige der Begriffe nochmals zusammen:

START

2.7 Zuverlässigkeit R(t); Unzuverlässigkeit Q(t)

Auf der Basis von Lambda kann man nun aber auch den Begriff der Zuverlässigkeit (Reliability) definieren als die Wahrscheinlichkeit, mit der ein bestimmtes System in einem bestimmten Zeitintervall (t₀,t) korrekt funktionieren wird.

Es gilt die Formel:

t = t' - t₀

t₀ := Startzeit

t' := Endzeitpunkt

(Für die Formeln in dieser Vorlesung benutze ich das Opensource-Werkzeug scilab); hier die benutzen Formeln im scilab-Format.

Entsprechend kann man die Unzuverlässigkeit definieren als:

Angenommen, ein System hat eine Fehlerrate Lambda von 0.001 pro Stunde, dann ergibt sich der Wert MTTF zu 1000 Stunden. Setzt man diese Werte in die Formel ein, so bekommt man:

reliability(1000,0,0.001) = 0.3678794

Das bedeutet, die Wahrscheinlichkeit, dass das System bis zum Zeitpunkt t = 1000, also der vollen MTTF-Zeit von 1000 Std, das System korrekt funktioniert, liegt nur bei ca. 37 %! Oder, wegen

Q(t) = 1 - R(t) = 1 - 0.3678794 = 0.6317525

Die Wahrscheinlichkeit, dass das System in den 1000 Std. einen Fehler haben wird, liegt bei ca. 63%.

Dabei ist zu bedenken, dass aufgrund des exponentiellen Charakters der Funktion die Zuverlässigkeit mit wachsender Betriebszeit abnimmt (siehe Schaubild):

Man kann den Blickpunkt auch verändern und fragen, wie sich die Fehlerrate Lambda verändert, wenn man die Zuverlässigkeit konstant hält. Die zugehörige Formel bekommt man durch Umformung:

Für einen Wert von R(t) = 0.3678794 bekommt man für einen Zeitraum von t = 0 * 100 bis t = 10 * 100 die folgende Kurve:

Für einen Wert von R(t) = 0.999 bekommt man für den gleichen Zeitraum von t = 0 * 100 bis t = 10 * 100 die folgende Kurve:

Man erkennt hier direkt, dass man für die Einhaltung eines bestimmten Zuverlässigkewitswertes auch bei einem 'fortgeschrittenen' Zeitpunkt eine sehr niedrige Fehlerrate garantieren muss.

Handelt es sich bei dem zu prüfenden System um ein komplexes System, so setzt sich das Verhalten aus dem Verhalten der Teilsysteme zusammen. Entsprechend muss man das Gesamtverhalten durch Berechnung der Verhalten der Teilsysteme berechnen.

START

2.8 Zuverlässigkeit bei sequentiellen Systemen

Besteht das komplexe System aus einer Sequenz von k-vielen atomaren Systemen, dann addiert sich die Fehlerrate Lambda von jedem Teilsystem:

Für die Zuverlässigkeit gilt in diesem Fall:

START

2.9 Zuverlässigkeit bei parallelen Systemen

Besteht das komplexe System aus einer Parallelschaltung von k-vielen atomaren Systemen, dann kann man die Zuverlässigkeit über die Unzuverlässigkeit annähern:

Wegen R(t) = 1 - Q(t) gilt dann:

START

2.10 Zuverlässigkeit bei kombinierten Systeme

In der Praxis treten natürlich Systeme auf, die sowohl sequentielle Kombinationen von Systemen umfassen wie auch parallele, dies zusätzlich gemischt.

In einem solchen Fall muss man so vorgehen, dass man von innen nach aussen reine Sequenzen bzw. Parallelschaltungen berechnet und diese Schaltungen dann weiterhin wie ein einziges System behandelt. Auf diese Weise wird die komplexe Verknüpfung nach und nach immer mehr vereinfacht.

In dem vorausgehenden Beispielsystem A bestand A aus einer Parallelschaltung von zwei sequentiellen Schaltungen: OR( AND(1,2), AND(3,4)). In diesem Beispiel würden zunächst die beiden sequentiellen Schaltungen jede für sich ausgerechnet, so dass man z.B. die Werte bekäme OR(0.955, 0.914). Dann würde man die parallele Schaltung berechnen, also:

START

2.11 Zusammenfassung: eine anhaltend schwierige Situation

Die hier vorgestellten Begriffe und Methoden bilden nur einen Ausschnitt aus einem ganzen Spektrum. Zur Vertiefung sei nochmals verwiesen auf das Buch von [STOREY 1998]

Grundsätzlich ist festzuhalten, dass zwar der Bedarf an zuverlässigen Systemen beständig steigt, eine alle Fehler berücksichtigende und erfassende Methodik aber bis heute nicht in Sicht ist. Dies betrifft sowohl die Fehlervermeidung während der Erstellung des Systems, die Fehlervoraussage wie auch das Testen von zuverlässigen Systemen.

START

3. Klassifikation von Realzeit-Systemen

Für die Klassifikation von Realzeit-Systemen stehen zahlreiche Kategorien zur Verfügung. Einige seien hier aufgelistet:

1. Fail-safe/Fail-operational: In einem System, das 'fail-safe' ist, kann das System mit hoher Wahrscheinlichkeit einen Fehler erkennen und dann einen sicheren Zustand ansteuern. In Situationen, in denen keine sicheren Zustände verfügbar sind, ist das System 'fail-operational'.




2. Guaranteed-Response/ Best-Effort: eine garantierte Antwort ('guaranteed-response') liegt vor, wenn ein System so umfassend analysiert worden ist, dass es in allen voraussagbaren Belastungssituationen eine definierte Antwort zu geben vermag. Ist eine umfassende Analyse nicht verfügbar, dann kann es nur 'beste Versuche' ('best effort') geben, eine Antwort bereitzustellen; dies kann mangelhaft sein.




3. Resource-Adequate/ Resource Inadequate: in einem ressourcenadäquaten System stehen in allen Belastungsfällen genügend Ressourcen zur Verfügung. In vielen Systemen wird aber aus Wirtschaftlichkeitsüberlegungen mit limitierten Ressourcen gearbeitet, die aufgrund von Wahrscheinlichkeitsüberlegungen dynamisch verwaltet werden. Bei schlechten Einschätzungen sind damit Störfälle wahrscheinlich.




4. Event-triggered/ Time-triggered: in ereignisgetriebenen ('event triggered') Systemen reagiert ein System ausschliesslich auf das Auftreten bestimmter Ereignisse, die durch sogenannte Unterbrechungen ('interrupts') 'bekannt' werden. Das System muss dann dynamisch auf diese Unterbrechungen reagieren. Im Unterschied dazu orientieren sich zeitgetriebene ('time triggered') Systeme ausschliesslich an einem Systemtakt ('system clock'), der fest mit bestimmten Aktionen verknüpft ist. In verteilten Systemen stellt dabei die Synchronisation der verschiedenen Systemtakte eine wichtige Aufgabe dar (siehe oben)..




5. Hard Real-Time/ Soft Real-Time: der zentrale Unterschied zwischen Hard Realtime Systemen und Soft Realtime Systemen kann wohl am besten am Verhältnis zur Umwelt festgemacht werden. Ein hartes Realzeit-System muss absolut synchron bleiben mit den Ereignissen in seiner Umgebung, wohingegen ein weiches Realzeit-System seine Antwortzeiten unter Belastung bis zu einem gewissen Grad gegenüber der Umgebung verlangsamen kann (z.B. dauern die Reaktionszeiten eines Servers im Netz dann einfach länger) ohne dabei Schaden anzurichten. Die Zeitanforderungen von harten Realzeit-Systemen liegen auch oft in kleineren Zeiteinheiten (Milisekunden und weniger) als bei weichen Realzeitsystemen (Sekunden). Damit harte Realzeit-Systeme ihre Leistungen zuverlässig erbringen können, müssen sämtliche Belastungssituationen, auch die eher seltenen, vollständig analysiert sein, so dass eine garantierte Antwort gewährleistet wird. Bei weichen Systemen reicht in der Regel eine durchschnittliche Antwortzeit. Ferner verlangen harte Realzeit-Systeme eine sehr zuverlässige autonome Fehlererkennung und Fehlerbehandlung innerhalb klar definierter zeitlicher Grenzen. Für harte Realzeit-Systeme ist es ferner wichtig, dass ihre zeitlichen Daten innerhalb sehr enger Grenzen absolut zuverlässig sind; die impliziert, dass es sich um kleine Datensätze handelt. Demgegenüber operieren viele weiche Realzeit-Systeme mit grossen Datensätzen, deren Integrität über lange Zeiträume zu gewährleisten ist. Roll-Back-Strategien weicher Realzeit-Systeme sind wegen der sehr engen zeitlichen Schranken für harte Realzeitsysteme in der Regel nicht anwendbar.

START

4. Zeit- und Ereignisgetrieben; Interrupts

Wie schon in der letzten Vorlesung bemerkt, unterscheidet man Systeme u.a. nach dem Aspekt 'zeitgetrieben' oder 'ereignisgetrieben'. Zeitgetriebene Systeme ('time triggered') sind vollständig von einem Systemtakt gesteuert; die Reaktion auf externe Ereignisse erfolgt ausschliesslich nach einem festen Plan. Für die meisten Situationen, in denen ein Realzeitsystem zum Einsatz kommen muss, ist dies aber ungenügend; typischerweise muss ein Realzeitsystem auf Ereignisse reagieren, deren Auftreten meist nicht vorausgesehen werden kann. Ausserdem kann die Zahl solcher unterschiedlicehr Ereignisse sehr gross sein. Ein festes Abfrageschema, wie es zeitgetriebene Systeme nur ermöglichen, kommt da schnell an seine Grenzen (z.B. ein System soll 50 verschiedene Ereignisse überwachen; eine Einzelüberprüfung sei mit 8 Systemtakten angenommen. 50 Überprüfungen wären dann 400 Systemtakte. Im worst-case Fall tritt das Ereignis Nr. 49 gerade dann ein, wenn das System Ereignis 50 überprüft. D.h. das System würde erst in 8 * 48 Takteinheiten feststellen, dass ein Ereignis vorliegt. Ferner wäre im worst-case Fall denkbar, dass alle Ereignisse 1-47 in der Zwischenzeit auftreten und eine Reaktion erzwingen. Bei einer durchschnittlichen Realtionsdauer von z.B. 10 *2 Takteinheiten pro Routine ergäbe dies eine Gesamtreaktionszeit von 8 * 48 + 47 * (10 * 2) = 1324 Takteinheiten. Angenommen, das System sollte im Falle von Ereignis 49 in spätestens 20 Mikrosekunden reagieren, dann wäre dies völlig inakzeptabel.

In dieser Situation macht es Sinn, ereignisgetriebene Systeme ('event triggered') einzusetzen. Solche Systeme reagieren nur dann, wenn ein Ereignis E_i auftritt. Eine solche ereignisgetriebene Reaktion muss in der Hardware des Systems (z.B. in einer CPU oder direkt in einem Mikrokontroller) fest eingebaut sein. Folgende Eigenschaften sind hier wichtig:

1. ID, Priorität:Jeder Interrupt besitzt eine eindeutige ID, eine eindeutige Priorität und innerhalb der Priorität evtl. noch einen Rang




2. Feste Abfolge:Die Zeit zwischen Interruptanforderung und Reaktion muss einer festen Abfolge folgen und darf eine definierte Zeitspanne nicht überschreiten. Dies beinhaltet, dass möglcherweise laufende Interruptbehandlungen unterbrochen werden müssen um einen Interrupt mit höherer Priorität vorzuziehen.




3. Multiple Interrupts: die Behandlung von mehreren Interrupts zur gleichen Zeit muss möglich sein, d.h. Interrupts müssen maskiert werden können.




4. Aktivierung einzeln: man kann die Abfragemaske für jeden Interrupt einzeln setzen bzw. nicht setzen.




5. Deaktivierung von allen: man muss alle Interrupts ausschalten können.




6. Jedem Interrupt seinen Interrupthandler: man muss für jeden Interrupt einen eigenen Handler bereithalten können.




7. Umkonfiguration im laufenden Betrieb: um z.B. 'Wechsel im Betriebsmodus' ('mode change') realisieren zu können, muss man die Zuordnung von Masken und Routinen im laufenden Betrieb ändern können; dazu gehört z.B., dass man die Interrupthandler für ein und denselben Interrupt je nach Modus an unterschiedlichen Stellen ablegen kann.

Dabei ist zu beachten, dass zusätzlich zu den Interrupts auch noch Ausnahmen auftreten können; Ausnahmen sind keine Interrupts, sondern dies sind definierte Fehlverhaltensereignisse die mit allerhöchster Priorität zu behandeln sind noch vor den Interrupts (z.B. Division durch 0).

Angenommen die zuvor beschriebene Situation beträfe ein ereignisgetriebenes System (ET := Event triggered System), dann könnte man z.B. dem Ereignis Nr. 49 einen hohen Prioritätswert zuweisen, z.B. 1. In diesem Fall würde das System bei Auftreten von Nr.49 die aktuelle Behandlung unterbrechen --bei blossem Umschalten der Speicherbereiche evtl. nur 2 Takteinheiten-- und sofort mit der Bearbeitung von Nr. 49 beginnen, also nach 2 Mikrosekunden anstatt nach 1324.

Schwieriger ist die Frage zu behandeln, wenn es mehr als 1 Interruptreignis der Priorität 1 ergibt. Ofensichtlich müssen die EntwicklerInnen des Systems vor dem Einsatz sehr genau klären, wieviele Interrupts vorkommen können, wie schnell diese jeweils zu bearbeiten sind und wie das gesamte System der Interrupts zu organisieren ist, damit keine 'tödliche Zonen' durch Konflikte zwischen gleichwertigen Interrupts entstehen.

Diese Überlegungen sollen nun noch weiter vertieft werden.-

START

5. Der Begriff des 'Task'; Synchronisation und Präemption

Für die weiteren Überlegungen ist es notwendig eine mögliche Komplexitätshierarchie innerhalb von Realzeitsystemen anzunehmen. Wir folgen hier wieder dem Buch von [Kopetz 1997:Chapt.4].

Kopetz nimmt an, dass ein Realzeitsystem aus einem Cluster von Fault Toleran Units (FTUs) bestehen kann. Eine FTU wiederum kann aus mehreren Nodes bestehen, die als Smallest Replacable Units (SRUs) gelten, also als kleinste ersetzbare Einheiten. Wenn ein Node in einer FTU ausfällt, dann könnte dieser sofort von einer anderen Node ersetzt werden. Ein Node wiederum besteht aus Tasks, die als kleinste funktionale Einheiten einer Node angesehen werden.

Auch wenn ein Task als kleinste funktionelle Einheit in einer Node gilt, so mus man hier doch noch eine wichtige Unterscheidung machen, nämlich die zwischen 'einfachen' und 'komplexen' Tasks.

Ein einfacher ('simple') Task ('S-Task') ist ein Prozess, der --wird er einmal gestartet-- auf keinen anderen Task mehr warten muss; ein einfacher Task hat alle Ressourcen, die er zur Erfüllung seiner Aufgabe benötigt. So gesehen ist er 'autonom'.

Demgegenüber zeichnet sich ein komplexer ('complex') Task ('C-Task') dadurch aus, dass er mindestens an einer Stelle die Ergebnisse eines anderen Tasks benötigt, d.h. er muss warten ('wait'-statement), bis der andere Task ihm diese Ergebnisse liefert.

Nennt man die Zeit, die ein Task a benötigt, um seine Aktion auszuführen,

(mit x := Input Daten von a, z := Kontrollsignal für a, s := interne Zustände von a), dann ist diese Zeit im Falle eines einfachen S-Tasks wohldefiniert, im Falle eines komplexen C-Tasks muss dies nicht der Fall sein. Wie später deutlich wird, kann das Auftreten von C-Tasks zu NP-harten Problemen führen.

Von der Eigenschaft der Synchronisation zu unterscheiden ist die Eigenschaft der Präemption. Präemption liegt vor, wenn ein Task --auch ein S-Task!-- aufgrund eines Interrupts unterbrochen werden muss.

START

6. WCAO := Worst Case Administrative Overhead

Zuvor wurde herausgestellt, wie vorteilhaft ereignisgetriebene Systeme gegenüber zeitgetriebenen Systeme sein können, wenn es darum geht, schnell und flexibel auf unerwartete Ereignisse zu reagieren. Allerdings darf nicht übersehen werden, dass die Unterbrechung eines laufenden Task a gefolgt von dem Umschalten ('switching') auf einen neuen Task b auch minimale Zeit benötigt, und zwar administrative Zeit, die zusätzlich ('overhead') zur normalen Task-Ausführungszeit entsteht. Im Englischen spricht man daher hier auch vom 'administrative overhead' (AO). Selbst wenn man heute schon in der Hardware diese Verwaltungsprozesse dadurch beschleunigt, dass man keine speziellen Register mehr benutzt, sondern nur noch Speicherbereiche, zwischen denen man hin- und herschaltet, benötigt man auch in diesem Fall minimale Verwaltungsprozesse, die das Wiederauffinden der verschiedenen Speicherbereiche sicherstellen.

Seien

die Ausführungszeiten, die die Tasks a und b 'für sich genommen' benötigen. Sei

die Umschaltzeit (switch-time) von a nach b und

die Umschaltzeit (switch-time) von b nach a. Dann ist einerseits klar, dass jede präemptive Unterbrechung zwei zusätzliche Verwaltungszeiten einführt. Selbst bei effektiver Hardwareorganisation muss man mindestens 2 Operationen annehmen, um diese zu realisieren (Zeiger setzen, Umschalten). Im Falle vieler 'blinder' Interrupts könnte dies den administrativen Overhead extrem erhöhen. Man kann ausrechnen, in welcher Konstellation der worst-case administrative overhead (WCAO) das Gesamtverhalten des Systems soweit stören würde, dass es die Realzeitanforderungen sprengen würde. Das Problem ist nur, dass die Ursachen für solche Umschaltvorgänge letztlich in Ereignissen gründen, deren Auftreten nicht vom System kontrolliert werden (man denke an die grossflächigen Zusammenbrüche der Energieversorgung in USA, Schweden und Italien in 2003).

START

7. WCET := Worst Case Execution Time

Eingangs der heutigen Vorlesung wurde festgestellt, dass bei Realzeitsystemen die Zeit Priorität geniesst, und zwar in dem Sinne, dass jede logische Funktionseinheit bzgl. ihres möglichen Zeitbedarfs im Rahmen fest vorgegebener Eckwerte eindeutig und verlässlich bestimmt werden muss.

Die nachfolgenden Überlegungen haben dann gezeigt, dass eine Bestimmung des Zeitbedarfs nicht auf einer Ebene alleine, sondern nur unter Berückichtigung aller Ebenen vorgenommen werden kann.

Das nachfolgende Diagramm bringt dies nochmals zusammenfassend zum Ausdruck:

Ausgangspunkt ist die Grösse WCET := worst case execution time. Wenn es eine Grösse gibt, die präzise und verlässlich bestimmt werden muss, dann diese. Die Einlösung dieser Forderung enthüllt aber die immense Schwierigkeit, die dem entgegensteht.

Ausgangspunkt bildet die Software auf der höchsten Ebene der Kodierung; möglicherweise sogar die Ebene der formalen Modellbildung. Nennen wir dies den A-Level für abstrakten Level. Dies ist die Ebene, auf der die logische Funktion der Software definiert ist. Dies ist ebenfalls die Ebene, auf der der Auftraggeber mit dem/der IngenieurIn kommuniziert. Die Aufgabe besteht hier darin, diese formale Darstellung der Software in eine solche formale Präsentation zu übersetzen, die es zweifelsfrei erlaubt, jedem Abschnitt des Softwarequelltextes eindeutig einen Zeitbedarf zuzuweisen. Eine von mehreren Möglichkeiten, dies zu tun, ist die Konvertierung des Quelltextes in Struktogramme. Da sich alle Algorithmen grundsätzlich vollständig in Struktogramme konvertieren lassen, ist garantiert, dass bei dieser Konvertierung nichts verlorengeht.

Im nächsten Schritt muss nun eine Zuordnung hergestellt werden zwischen Abschnitten des Quelltextes auf dem A-Level und dem Objekkode, der vom Compiler erzeugt wird. Nennen wir diese Ebene den O-Level. Ohne diese Zuordnung ist nicht klar, welcher Ressourcenbedarf dem Quelltext auf der hohen Ebene entspricht, also

Ist diese Abbildung gelungen, dann muss man nun eine Zuordnung herstellen wzischen den Elementen des Objektkodes und den Operationen der Mikroarchitektur; nennen wir diese den M-LEVEL, also:

Ist auch diese Zuordnung gelungen, dann lässt sich der Zeitbedarf eines Programms klar aussagen. Wichtig dabei ist, dass nicht alle Verarbeitungs-Pfade betrachtet werden müssen, sondern nur die kritischen Pfade ('critical paths'); dies sind jene, die die WCET gefährden könnten.

An dieser Stelle angekommen muss man feststellen, dass die Quantifizierung des M-LEVELS wahrscheinlich das grösste Problem darstellt; denn die modernen Prozessoren und Mikrokontroller sind fast ausnahmslos RISC-Prozessoren, die ausgefeilte Caching- und Pipelining-Verfahren beinhalten. Ein solches Verhalten ist indeterministisch! Es bleibt eine offene Frage, wieweit man in extrem zuverlässigen Kontexten solche CPUs überhaupt einsetzen kann; der Trend geht momentan allerdings dahin, fast ausschliesslich solche hochleistungsfähigen, aber inhärent indeterministisch, Prozessoren zu bauen.

Kann man schon alleine durch diese Analyse der Anforderungen der unterschiedlichen Realisierungsebenen erahnen, welche Herausforderungen Realzeitsysteme für den/die IngenieurIn bereithalten, so wird dies noch zusätzlich erschwert durch die Tatsache, dass die Annahme von S-Tasks ohne Präemption praktisch kaum vorkommt; selbst bei der vereinfachenden Annahme, dass nur S-Tasks auftreten, muss man doch meistens Präemption annehmen. Damit kommt aber nicht nur die Grösse WCAO ins Spiel, sondern auch der Faktor externer Ursachen, die vom System selbst nicht kontrolliert werden kömnen. Nimmt man weiterhin an --was 'normal' ist--, dass C-Tasks vorkommen, dann tritt zusätzlich das Synchronisationsproblem auf, das in der Berechnung berücksichtigt werden muss.

Angesichts dieser Komlexität überrascht es nicht, wenn [KOPETZ 1997:90] zur Frage der WCET-Bestimmung abschliessend schreibt:

START

8. Ausblick: Scheduling

Wie schon diese Überlegungen zeigen, geht mit den Phänomenen Interrupt, Präemption und Synhronisation das Scheduling-Problem einher. Dies soll in der nächsten Vorlesung etwas nähr betrachtet werden.

START

9. Berechnungsbeispiele zur Zuverlässigkeit

9.1 Serielle Schaltung: Q(t) gesamt

Gegeben sei eine serielle Schaltung mit K-vielen Komponenten, für die eine Zuverlässigkeit von R_c(t) = 0.999 für alle Komponenten gelten soll. Jede Komponenten wird als völlig unabhängig von den anderen angenommen.

Gefragt wird nach der Zuverlässigkeit R(t) der gesamten Schaltung bzw. nach der Unzuverlässigkeit Q(t) der gesamten Schaltung, für K = 100. Es gilt:

Am Beispiel der Unzuverlässigkeit kann man sehen, wie dramatisch die Unzuverlässigkeit ansteigt selbst dann, wenn die einzelnen Komponenten sehr zuverlässig sind. Bei 100 Komponeten steigt die Unzuverlässigkeit um den Faktor 950 !

START

9.2 Serielle Schaltung: Komponenten

Man hat eine serielle Schaltung mit K = 100 Komponenten und man will wissen, wie gross die individuellen Zuverlässigkeit R_c(t) sein muss, damit die Zuverlässigkeit R(t) des Gesamtsystems mindestens so gross ist wie R_SOLL(t)

Man erkennt, dass die Genauigkeit der einzelnen Komponenten erheblich grösser sein muss als die Genauigkeit des gesamten seriellen Systems.

Dieser Zusammenhang wird noch deutlicher, wenn man die Frage umformuliert. Man gibt einen SOLL-Wert R(t) mit z.B. 0.999 für das Gesamtsystem vor und einen IST-Wert R_c(t) für die einzelnen Komponenten. Dann fragt man nach der notwendigen Anzahl K von Komponenten, um den Gesamtwert zu erreichen.

START

9.3 Parallele Schaltung: Q(t) gesamt

Gegeben sei eine parallele Schaltung mit K Komponenten. Es sei wiederum angenommen, dass die Zuverlässigkeit einer einzelnen Komponenten R_c(t) = 0.999 sei. Gefragt ist nach der Zuverlässigkeit R(t) des Gesamtsystems.

Man sieht, ein paralleles System ist schon mit 3 Komponenten ertrem zuverlässig!

START

9.4 Parallele Schaltung: Komponenten

Auch im Falle der Parallelschaltungen kann man natürlich die Frage so stellen, dass man wissen will, mit wievielen Komponenten K man bei einer gegebenen Komponentenzuverlässigkeit von R_c(t) = IST eine bestimmte Gesamtzuverlässigkeit R_SOLL(t) erreicht wird.

Es sei angenommen, dass die Zuverlässigkeit R_c(t) der einzelnen Komponenten schlechter sei als die Zuverlässigkeit R_SOLL(t) des Gesamtsystems. Dann ergibt sich z.B. für einen Wert von R_c(t) = 0.70:

Mit einem ganzzahligen Wert von K = 6 erreicht das Gesamtsystem die Zuverlässigkeit von 0.999. Im Vergleich zum seriellen System sieht man, dass die Zuverlässigkeit von parallelen Schaltung auch bei geringerer Qualität der einzelnen Komponenten erheblich grösser ist als bei seriellen systemen.

START

10. Testfragen

1. Wenn sie ein System konstruieren sollen, das neben der logischen Dimension auch die Zeit explizit berücksichtigen muss, was verändert sich dadurch für Sie bei der Konstruktion?




2. Beschreiben sie, was ein atomares System ist?




3. Worin unterscheidet sich ein komplexes System von einem atomaren System?




4. Wie ist die Fehlerrate Lambda definiert?




5. Machen Sie einen Vorschlag, wie man die Fehlerrate Lambda für ein konkretes System ermittelt?




6. Was bedeuten die Kürzel MTTR, MTTF, MTBF?




7. Was versteht man unter der Availability bzw. Unavailability von Systemen?




8. Wie wird die Zuverlässigkeit (Reliability) eines Systems definiert?




9. Wie wird die Unzuverlässigkeit (Un-Reliability) eines Systems definiert?




10. Wie interpretieren Sie den Sachverhalt, dass ein System bei einer MTTF = 1000h einen Wert für die reliability von reliability(1000,0,0.001) = 0.3678794 besitzt?




11. Warum kann die Zuverlässigkeit eines Systems bei anwachsender Betriebszeit abnehmen?




12. Wie berechnen Sie die Zuverlässigkeit eines komplexen Systems, das sequentiell aufgebaut ist? Geben Sie ein konkretes Beispiel.




13. Wie berechnen Sie die Zuverlässigkeit eines komplexen Systems, das parallel aufgebaut ist? Geben Sie ein konkretes Beispiel.




14. Wie berechnen Sie die Zuverlässigkeit eines komplexen Systems, das sequentiell und parallel aufgebaut ist? Geben Sie ein konkretes Beispiel.




15. Beschreiben Sie die wichtigen Eigenschaften von fünf wichtigen Klassifikationen von Realzeitsystemen.




16. Geben Sie 7 Beispiele von Realzeitsystemen aus ihrer alltäglichen Umgebung an und geben sie Erfahrungswerte an für MTTF, MTTR und f+r die Zuverlässigkeit dieser Systeme.




17. Geben Sie 3 Beispiele von Realzeitsystemen aus ihrer alltäglichen Umgebung, deren Zuverlässigkeit ihrer Einschätzung nach vergleichsweise am höchsten liegen und 3 Beispiele von Realzeitsystemen, deren Zuverlässigkeit vergleichsweise am niedrigsten liegen.




18. Was ist der Unterschied zwischen einem zeit- und ereignisgetriebenen System?




19. Was ist ein Interrupt auf Hardwareebene?




20. Welche Informationen werden benötigt, damit ein Interruptkontroller Interrupts verwalten kann?




21. Welche Eigenschaften eines Interruptkontrollers sind aus Sicht eines/r Entwicklers/In wünschenswert?




22. In welchen Situationen ist ein zeitgetriebenes System günstiger als ein ereignisgetriebenes?




23. In welchen Situationen ist ein ereignisgetriebenes System günstiger als ein zeitgetriebenes?




24. Wie verhalten sich die Begriffe 'cluster', 'ftu', 'node' und 'task' zueinander?




25. Was unterscheidet einen S-Task von einem C-Task?




26. Was bedeutet es, wenn ein System 'präemptiv' ist?




27. Wenn Taskunterbrechung eintritt, welche Auswirkungen hat dies auf die Ressource Zeit?




28. Was verstehen Sie unter WCAO?




29. Was verstehen Sie unter WCET?




30. Warum spielen Abbildungsprozesse im Rahmen der Berechnung von WCET eine wichtige Rolle? Worin bestehen diese Abbildungsprozesse?




31. Nennen Sie Faktoren, die die Ermittlung von WCET erschweren bzw. beim heutigen Wissensstand letztlich unmöglich machen?

START