6. Design von Echtzeitsystemen

Transcrição

Übersicht
1.
2.
3.
4.
5.
Einführung
Design-Prozesse
Modellierungs-Sprachen
Analyse
Zusammenfassung
Vorlesung Real-Time Systems
6. Design von Echtzeitsystemen
Friedhelm Stappert – Design von RTS – Real-Time Systems - SoSe 2009 – Hochschule Darmstadt
1
1. Einführung
2
1. Einführung
Neben diesen "klassischen" Designaspekten müssen für Echtzeitsysteme
insbesondere die folgenden Punkte im Detail berücksichtigt werden:
Dieses Kapitel gibt einen Einblick in ausgewählte Aspekte des Systementwurfs. Der
Fokus liegt hier auf den speziellen Echtzeitaspekten.
Allgemeine Aspekte des Systementwurfs:
• Identifizieren von harten und weichen Echtzeitbedingungen
• Strukturieren der Anwendung in eine Anzahl konkurrierender Tasks
• Festlegen der korrekten Timing-Bedingungen für jede Task
• Wahl einer geeigneten Plattform, mit der die gegebenen Zeitbedingungen
garantiert werden können
• Analyse der Umgebung
• physikalische Gegebenheiten, insbesondere bzgl. Timing
• Analyse / Auswahl der Sensoren und Aktuatoren bezüglich
• Reaktionsgeschwindigkeit, Verzögerungen etc.
• Umgebungsbedingungen (Temperaturbereich, Feuchtigkeit, …)
• Ausfallsicherheit
• Analyse / Verifikation der Timing-Eigenschaften des realisierten Systems
• Response Times, Execution Times, Signallaufzeiten, etc.
• Anwendung, Anforderungen
• Was will der Kunde?
• Welche Anwendung soll erstellt werden?
• Funktionen
• Welche Funktionen soll die Anwendung haben?
• Architektur
• Was wird in SW, was wird in HW realisiert?
• Wie soll die SW strukturiert sein?
• Welche HW-Architektur wird benutzt?
• Prozesse
• Wie kommt man von den Anforderungen zur Realisierung durch eine konkrete
HW- und SW-Architektur?
• Modellierung
• Wie werden Anforderungen, Funktionen, Architektur, etc. formal beschrieben?
3
4
1
1. Einführung
Anforderungen (Requirements) an ein System gliedern sich in:
2. Prozesse
Ein Design-Prozess für den Systementwurf teilt den gesamten Entwurf in
kleinere, überschaubare Phasen auf. Dazu existiert eine Reihe von
strukturierten Methoden (s.u.).
Echtzeitaspekte müssen dabei in jeder Phase des Entwurfsprozesses
berücksichtigt werden, von Anfang an. Je später ein Timing-Fehler in einem
System bemerkt wird, desto teurer wird seine Behebung (vgl. Pathfinder
Beispiel). Das Aufspüren und Debuggen eines Timing-Fehlers kann, im
Gegensatz zu funktionalen Fehlern, extrem schwierig und aufwändig sein.
• Funktionale Anforderungen
• Anforderungen an die Funktionen, die das System realisieren soll: z.B.
Berechnungen, Datenspeicherung, Benutzeroberfläche.
• Nichtfunktionale Anforderungen
• Timing-Anforderungen
ß hier relevant
• Antwortzeiten, Rechenzeiten, Abtastperioden, Jitter, …
• Zuverlässigkeit
• Reliability (Ausfallsicherheit), Safety, Security
• Maintainability: Reparaturzeit nach einem Fehler
• Availability: Betriebszeit / (Betriebszeit + Reparaturzeit)
• Kosten
• Ressourcenverbrauch
• Termine
Idealerweise sollte daher jederzeit im Entwurfsprozess klar sein,
• welche Timing-Anforderungen an das System existieren,
• welche Timing-Eigenschaften das System hat bzw. haben wird.
Dadurch kann kontinuierlich – d.h. nicht erst am fertigen System – verifiziert
werden, ob das System mit seinen Eigenschaften die gegebenen
Anforderungen erfüllen kann.
Im Folgenden werden einige gängige Prozessmodelle kurz vorgestellt.
5
2. Prozesse
Das Wasserfallmodell
Entwurf
Vorteile:
• Einfach verständlich
• Wenig Managementaufwand
• Klare Abgrenzung der Phasen
Entwurf von Komponenten
Implementierung
Programmieren der Komponenten
Integration
Zusammensetzen der Komponenten
zum Gesamtsystem
Test gegen Anforderungen
Test
Fortschritt
6
2. Prozesse
Das Wasserfallmodell ist ein "dokumentgetriebenes" Modell, d.h. am Ende jeder
Phase ("Meilenstein") steht ein fertiges Dokument bzw. Sourcecode.
Anforderungsermittlung
Analyse
Installation
Rückkopplung
Inbetriebnahme
Einsatz
Nachteile:
• Klare Abgrenzung der Phasen ist unrealistisch
• Testen erfolgt erst sehr spät => Fehler werden zu spät erkannt
• Beteiligung des Kunden nur in der Anfangsphase; Änderungen stellen einen
Neuauftrag dar.
Wartung
7
8
2
2. Prozesse
Das Spiralmodell
2. Prozesse
Das Spiralmodell ist eine Weiterentwicklung des Wasserfallmodells. Das
Vorgehen ist risikogetrieben, d.h. die Minimierung des Restrisikos steht im
Mittelpunkt.
Vorteile:
• Sehr universell einsetzbar. In den Zwischenschritten kann das Spiralmodell
auch andere Vorgehensmodelle verwenden.
• Kostenkontrolle
• Anforderungen können sich während der Entwicklung ändern
• Unterstützt SW-Wiederverwendung
Nachteil:
• Hoher Managementaufwand; für kleine Projekte weniger geeignet
9
2. Prozesse
Das V-Modell
AnforderungsAnalyse
SystemIntegration
SystemDesign
Fortschritt
Vorteile:
• Universell einsetzbar, allgemeingültig für alle Arten von Projekten
• Standard in vielen Bereichen
• Sehr detaillierte Vorgaben
IntegrationsTest
SoftwareArchitektur
10
2. Prozesse
Das V-Modell ist dokumentgetrieben, d.h. am Ende jeder Phase stehen
entsprechende Dokumente bzw. Sourcecode. Üblicherweise gibt es auch im VModell Iterationen zwischen den einzelnen Phasen (nicht eingezeichnet). Der
V-Zyklus deckt nicht nur die SW-Entwicklung, sondern ein komplettes Projekt
ab. Die aktuelle Weiterentwicklung des V-Modells ist das V-Modell XT.
Abnahme
SystemAnalyse
Nachteile:
• Hoher Managementaufwand, für kleine Projekte weniger geeignet
• Testen erfolgt relativ spät im Entwurfsablauf
• Phasenablauf zu starr (im V-Modell XT flexibler)
ModulTest
Implementierung
Verifikation / Validierung
11
12
3
3. Sprachen
In der modellbasierten Entwicklung (Model Driven Architecture, MDA) wird ein
System – möglichst in allen Phasen des Entwurfsablaufs – in einer formalen
Modellierungssprache beschrieben. Diese Modelle dienen z.B. als Basis für
Analyse, Simulation, Verifikation und Codegenerierung.
MDA hat eine Reihe von Vorteilen:
• Modelle (insbes. graphische Darstellungen) sind einfacher zu verstehen als
Sourcecode.
• Zum Verständnis der Modelle ist wenig Vorwissen nötig.
• Modelle sind unmissverständlich im Gegensatz zu Umgangssprache.
• Systeme können simuliert werden. Dadurch können Designentscheidungen
vorab evaluiert werden.
• Automatische Codegenerierung => Programmierung ist weniger fehleranfällig.
• Ein Modell kann auf gewisse Eigenschaften hin überprüft werden.
3. Sprachen
Einige Beispiele für visuelle Modellierungssprachen:
• IEC-Standards 1131, 1491
• Prozessleittechnik, Automatisierungstechnik, etc.
• MATLAB/Simulink/Stateflow, Statemate
• Automaten/Statecharts und Datenfluss- / Block-Konzepte
• Luft- und Raumfahrttechnik, Automobiltechnik, etc.
• SDL (Specification and Description Language)
• Telekommunikation, etc.
• Esterel
• synchrone Sprache
• SystemC
• C++ Bibliothek zur Modellierung + Simulation von HW und SW
Eine Modellierungssprache beschreibt sowohl die Struktur / Architektur als auch
das Verhalten des Systems. Für Echtzeitsysteme sind natürlich auch Konzepte
zur Modellierung von Timing-Eigenschaften erforderlich.
13
3. Sprachen
UML (Unified Modelling Language) ist inzwischen ein weit verbreiteter Standard
zur Modellierung von Systemen in allen Phasen des Entwurfsablaufs. Die
Sprache definiert verschiedene Diagrammtypen (graphische Notationen) zur
Beschreibung von statischen Architekturen sowie zur Beschreibung des
dynamischen Verhaltens eines Systems.
14
3. Sprachen
Verhalten:
• Anwendungsfalldiagramm (use case diagram)
• Zustandsdiagramm (statechart)
• Aktivitätsdiagramm (activity diagram)
Statechart
Struktur:
• Klassendiagramm (class diagram)
• Objektdiagramm (object diagram)
• Komponentendiagramm (component diagram)
• Kompositionsstrukturdiagramm
(composite structure diagram)
• Verteilungsdiagramm (deployment diagram)
• Paketdiagramm (package diagram)
Klassendiagramm
Quelle: AUTOSAR.org
15
Quelle: AUTOSAR.org
16
4
3. Sprachen
Interaktion:
• Sequenzdiagramm (sequence diagram)
• Interaktionsübersichtsdiagramm (interaction overview diagram)
• Kommunikationsdiagramm (communication diagram)
• Zeitdiagramm (timing diagram)
3. Sprachen
Die Behandlung von Echtzeitaspekten wird in der (Standard-) UML noch nicht
unterstützt. Dazu existieren einige Erweiterungen, z.B. das UML Profile for
Modelling and Analysis of Real-Time and Embedded Systems (MARTE) von
der OMG.
Basierend auf UML und MARTE wurde/wird in der Automobilindustrie die
EAST-ADL (EAST Architecture Description Language) entwickelt. Sie entstand
2002 – 2004 in dem Forschungsprojekt "EAST-EEA" (daher der Name), und hat
sich inzwischen zu einem breit akzeptierten de facto Standard entwickelt. Die
aktuelle EAST-ADL2 (2008) enthält bereits einige Erweiterungen. Insbesondere
an der Integration von Echtzeitaspekten wird derzeit noch gearbeitet (geplant
für 2010).
Sequenzdiagramm
Ein ähnlicher Standard ist die AADL (Architecture Analysis & Design
Language). Sie wurde vorwiegend in der Luftfahrtindustrie angewendet und ist
daher auch unter dem Namen "Avionics Architecture Description Language"
bekannt.
Quelle: AUTOSAR.org
17
3. Sprachen
Die EAST-ADL2:
3. Sprachen
Die EAST-ADL2 definiert 5 Abstraktionsebenen (in Anlehnung an das VModell), auf denen ein System mit wachsendem Detaillierungsgrad modelliert
werden kann.
Die beiden unteren Ebenen werden durch die AUTOSAR SW-Architektur
abgedeckt.
Ziel der EAST-ADL2:
• Eine einzige Architekturbeschreibungssprache für die Behandlung aller
Informationen, die während der Systementwicklung benötigt werden, z.B.:
• Anforderungen
• Variabilität (Variantenmanagement)
• Sicherheit
• Verhalten
• Modellierung der Umwelt
• Design-Methodik
Feature content
Vehicle Level
Analysis Level
Design Level
Implementation Level
Operational Level
Abstract functional
architecture
Functional architecture,
HW architecture, platform
abstractions
AUTOSAR Software
architecture
Embedded system in
produced vehicle
Die Sprache ist in Form eines UML2-Profils implementiert und wird bereits
durch ein Prototyp-Werkzeug ("Papyrus") unterstützt.
18
19
20
5
3. Sprachen
Ein typisches Szenario:
3. Sprachen
• Der Automobilhersteller entscheidet, welche Funktionen das nächste Produkt
enthalten soll.
• Features sind z.B. Bremse, Scheibenwischer, Tempomat
• Alle Features werden im Vehicle Feature Model beschrieben
• Dabei können auch Varianten (z.B. Scheibenwischer mit/ohne
Regensensor) beschrieben werden.
• Ein Ingenieur entwickelt einen neuen Steuerungsalgorithmus (ABS, ESP).
• Der Algorithmus wird definiert als ADLFunction auf der "Analysis Level"
Ebene
• Die EAST-ADL2 beschreibt die Struktur. Das Verhalten kann durch
vorhandene Werkzeuge / Sprachen (z.B. Statecharts) beschrieben
werden.
• Das so erstellte Modell kann leicht zwischen Hersteller und Zulieferer
ausgetauscht werden.
• Verschiedene Funktionen können bereits
integriert werden, bevor SW und HW existiert.
• Die Interaktion (Schnittstellen) zwischen
Vehicle Level
Funktionen kann bereits verifiziert werden.
Analysis Level
Vehicle Level
Analysis Level
Design Level
Design Level
Operational Level
Operational Level
21
3. Sprachen
3. Sprachen
• Ein Systemarchitekt spezifiziert die detaillierte Systemarchitektur.
• HW-Architektur
• Allokierung, Mapping
• Anforderungen an die Implementierung
• Sensoren, Aktuatoren
• Ein SW-Architekt definiert die detaillierte SW-Architektur.
• Spezifikation der AUTOSAR SW-Komponenten
• Konfiguration der AUTOSAR Basic Software
• RTE Generierung
22
• Integration der SW auf ECUs.
• Validierung / Verifizierung des Gesamtsystems.
Vehicle Level
Vehicle Level
Analysis Level
Analysis Level
Design Level
Design Level
Operational Level
Operational Level
23
24
6
3. Sprachen
Abstraktionsebenen sind das fundamentale Konzept der EAST-ADL2. Elemente
auf den unteren Ebenen realisieren jeweils die Elemente auf den höheren
Ebenen.
Realize
3. Sprachen
Anwendung: Timing-Spezifikation in EAST-ADL2 und AUTOSAR
AUTOSAR
• Standard SW-Architektur für Steuergeräte
• Standard Austauschformate, Methodik, Applikationsinterfaces
• Erweiterungen für Timing Spezifikation
EAST-ADL2
• Beschreibungssprache für alle relevanten Informationen
im Entwurfsprozess
• Verschiedene Abstraktionsebenen
• Spezifikation von Timing noch eingeschränkt
Vehicle Level
Analysis Level
Design Level
Operational Level
Operational Level
TIMMO – Timing Model
• Sprache: Formale Spezifikation von Timing-Eigenschaften und -Anforderungen auf
allen Abstraktionsebenen. Erweiterungen der EAST-ADL
• Methodik: Formale Spezifikation von Timing-Eigenschaften und -Anforderungen in
allen Entwicklungsphasen.
Realize
25
3. Sprachen
26
3. Sprachen
Timing-Anforderungen und -Eigenschaften
EAST ADL Abstraktionsebenen und AUTOSAR
Feature
Level
Feature
Model
Analysis
Level
Functional Analysis
Architecture
Design
Level
Functional Design
Architecture
Environment
Models
Operational
Level
OEM – «Anforderung» Die Türen sollen entriegelt werden
spätestens 1 Sekunde nachdem ein gültiges Schlüsselsignal
erkannt wurde.
Feature
Level
Analysis
Level
Functional
View
Middleware
Abstraction
Hardware
Design
Architecture
Operational Architecture
AUTSAR System and ECU View
?
Wie werden Timing Anforderungen aufgeteilt
in Timing Anforderungen / Eigenschaften?
Wie werden Timing Eigenschaften transformiert
in Timing Anforderungen / Eigenschaften?
Implementation
Level
AUTOSAR
Software
and
Hardware
View
Operational
Level
«Anforderung», «Eigenschaft»
...
Zulieferer – «Eigenschaft» Die Funktion (runnable) unlockDoor
antwortet innerhalb 120 ms auf die Aufforderung, die Türen zu
entriegeln. [Annahme: Ausführung auf einem X12 6MHz
Prozessor ... ]
Abstraktionsebene
Artefakt
«Anforderung», «Eigenschaft»
...
Design
Level
Implementation Architecture
AUTOSAR VFB View, System, ECU
Mapping
Abstraktionsebene
Design Level
Realize
Implementation
Level
Vehicle Level
Analysis Level
27
28
7
3. Sprachen
3. Sprachen
Events, Timing
Feature
Level
Events
Analysis
Level
Beispiel System – Was möchte ich spezifizieren
Events werden auf allen
Abstraktionsebenen verfeinert.
Ein Event auf einer Ebene
kann dabei zu einer Folge von
Events auf der nächsttieferen
Ebene verfeinert werden.
End-to-End Delay
Brake Pedal
Position
Monitor
Event-Modelle (periodic,
sporadic, pattern, arbitrary)
können spezifiziert werden.
Design
Level
Implementation
Level
Synchronisation
Vehicle Functionality
Braking
Brake Force
Actuation
Brake Controller
Auf dem Operational Level
erscheinen alle Events in
zeitlicher Reihenfolge.
Wheel
Speed
Calculation
Brake Force
Actuation
Events
Operational
Level
Zeit
Stop Light
Actuation
End-to-End Delay
Synchronisation
Abstraktionsebenen
29
3. Sprachen
3. Sprachen
AUTOSAR Virtual Function Bus Sicht
AUTOSAR System Sicht
ECU #1
Sensor
SWC
SWC
#1
30
SWC
#2
SWC
#3
SWC
#4
FL
Actuator
SWC
Wheel
FL
Actuator
SWC
Wheel
RR
Sensor
SWC
ECU #2
SWC
ECU #3
RTE
RTE
Basic SW
ECU Wheel FL
SWC SWC SWC
#1
#2
#3
SWC
SWC
#4
RTE
Basic SW
Basic SW
Actuator
SWC
RTE
Basic SW
ECU Wheel RR
SWC
#4
Actuator
SWC
RTE
Basic SW
Bus #1
Virtual Function Bus
ECU
Abstraction
Component
(Sensor)
SWC Software Component
AUTOSAR
Service
Bus #2
ECU
Abstraction
Component
(Actuator)
ECU
Abstraction
Component
(Actuator)
Observable Events
31
Sensor
Actuator
Signalweg
RTE Run Time Environment
Observable
Events
SWC Software Component
Actuator
ECU Electronic Control Unit
32
8
3. Sprachen
3. Sprachen
AUTOSAR ECU Sicht
ECU #1
Sensor
SWC
SWC
Sensor
SWC
SWC
RTE
RTE
Basic SW
Communication
Services
I/O HW
Abstraction
Communication
Hardware
Abstraction
I/O Drivers
Communication
Drivers
Peripheral
Communication
Controller
Observable Events
"Observable Events":
Zusammenfassung: Events, Anforderungen, Beschreibungen
• ECU Sicht: Basic Software Module Entry
Called, Basic Software Module Entry
Returned
• Internal Behaviour: Runnable Entity
Activated, Runnable Entity Started,
Runnable Entity Terminated, Basic
Software Module Entity Activated, Basic
Software Module Entity Started, Basic
Software Module Entity Terminated
• Kommunikation: Signal Sent To COM,
Signal Available For RTE, IPDU Sent To
Interface, IPDU Received by COM, Frame
Queued for Transmission, Frame
Transmitted on Bus, Frame Received by
Interface
TIMMO / EAST-ADL2 liefern eine Sprache für die Spezifikation von TimingAnforderungen und -Eigenschaften:
• Events
• hierarchische Event-Ketten
• Anforderungen an Events:
• Reihenfolge
• Dauer / Verzögerung
• Synchronisation
• Event Triggering (Arbitrary, Concrete Pattern, Periodic, Sporadic)
• Beschreibung / Eigenschaften:
• ECU Sicht, VFB Sicht, Internal Behaviour, Kommunikation
33
3. Sprachen
Programmiersprachen
Die TIMMO-Sprache liegt in Form eines UML-Metamodells vor. Teile davon
fließen in AUTOSAR R4.0 (Ende 2009) ein. Die TIMMO Konzepte werden in
das UML2 Profil der EAST-ADL2 (Mitte 2010), integriert.
34
3. Sprachen
Die meisten (eingebetteten) Echtzeitsysteme werden heute in C / C++ realisiert,
obwohl diese Sprachen eigentlich keine speziellen Echtzeit-Konstrukte bieten.
Ada ist eine Programmiersprache, die speziell für die Entwicklung von
sicherheitskritischen, verteilten Echtzeitsystemen entwickelt wurde. Sie
wurde/wird meist in militärischen Systemen angewendet. Z.B. schreibt das USDepartment of Defense und das deutsche Verteidigungsministerium BMVg den
Einsatz von Ada bei allen Softwareentwicklungen vor.
Allgemein hat Ada sich allerdings (noch?) nicht durchgesetzt. Gründe hierfür
könnten sein:
• Keine Objektorientierung; OO-Konzepte wurden erst nachträglich integriert.
• Extrem viele Sprachkonstrukte im Vergleich zu anderen Sprachen.
• Daher sowohl für Anwender als auch für Compilerbauer sehr komplexe
Sprache
• Abneigung gegen militärische Standards (?)
Die Sprache bietet viele Konzepte für die Modularisierung und die Entwicklung
nebenläufiger Programme (s. [Burns, Wellings]). Ada z.B. war eine der ersten
Sprachen, die ein Exception Handling Konzept eingebaut hat. Strenge
Typisierung und Prüfungen zur Laufzeit (z.B. Speicherüberläufe) machen die
Sprache "sicherer" als z.B. C.
35
36
9
3. Sprachen
Real-Time Java
Prinzipiell hat Java viele Vorteile gegenüber C/C++:
• Sicherer: viele typische Programmierfehler in C / C++ sind in Java nicht
möglich (z.B. beim Freigeben von Objekten).
• Portabilität, Prozessorunabhängigkeit
• Konzepte zur Programmierung verteilter Systeme (Threads, Monitor, rmi)
• Weit verbreiteter, akzeptierter Standard.
Für die Anwendung in Echtzeitsystemen ist Java allerdings nicht geeignet, z.B.:
• Scheduling: Zu wenig Prioritätsklassen, keine Möglichkeiten zur Anbindung
besserer Schedulingalgorithmen mit mehr Prioritätsklassen
• Garbage Collector: Hat höchste Priorität, führt zu unvorhersagbaren und
langen Latenzzeiten
• Priority inversion: kein Priority Ceiling Protocol
• Physical Memory Access: Java unterstützt nicht den Zugriff auf ganz
bestimmte Speicherbereiche (z.B. für Memory Mapped I/O)
37
3. Sprachen
Scheduling, Threads:
• Zusätzlich zu den „normalen“ Threads gibt es RT-Threads mit höheren
Prioritäten.
• Bestimmte RT-Threads dürfen keine Objekte auf dem Heap anlegen und
dürfen deshalb den Garbage Collector beliebig unterbrechen.
• Das priority ceiling protocol wird unterstützt
• RT-Threads haben verschiedene Scheduling-Parameter wie Ausführungszeit,
Deadline, Periode, etc., die für Scheduling-Algorithmen und -Analysen
verwendet werden können.
3. Sprachen
Die Real-Time Specification for Java [www.rtsj.org] definiert entsprechende
Erweiterungen, die die Programmierung von Echtzeitsystemen in Java
unterstützen sollen. Grundlegende Ziele dabei waren:
• Keine Einschränkungen auf eine bestimmte Klasse von Entwicklungsumgebungen (z.B. Micro Edition J2ME)
• Rückwärtskompatibilität: existierende Standard-Java-Programme sollen auch
auf RT-JVMs ausführbar sein
• Portabilität
• Unterstützung für heute gängige RT-Konzepte (wie z.B. RMS), aber offen für
Fortentwicklungen
• Vorhersagbare Ausführungszeiten
• Keine syntaktischen Erweiterungen / Änderungen der Sprache
• Variantenbildung möglich: die Spezifikation soll verschiedene
Implementierungen mit z.B. unterschiedlichen Scheduling-Algorithmen
erlauben
Die Erweiterungen betreffen i.W. Scheduling, Threads und
Speichermanagement (s. [Burns, Wellings]).
38
3. Sprachen
Darüber hinaus gibt es auch Ansätze, den Garbage Collector unterbrechbar zu
implementieren ("inkrementeller Garbage Collector"). Das wird aber von der
RTSJ nicht gefordert.
Die Echtzeitfähigkeit einer RT-JVM (bzw. eines Ada-Programms) ist natürlich
nur gegeben, wenn sie zusammen mit einem RTOS verwendet wird.
Speichermanagement:
• Scoped Memory:
• Einem RT-Thread wird ein Scoped-Memory-Bereich zugeordnet.
• Alle (mit new) angelegten Objekte werden im Scope angelegt.
• Beim Verlassen eines Scopes (run-Methode des RT-Threads terminiert)
wird der aktuelle Scope mit allen Objekten gelöscht.
• Immortal Memory: Objekte leben für immer (bis zum Ende der Anwendung).
• Verwendung ganz bestimmter Speicherbereiche und Zugriff auf absolute
Adressen kann erzwungen werden.
39
40
10
3. Sprachen
Programmierstil
Die speziellen Eigenschaften von eingebetteten Echtzeitsystemen erfordern
einen extrem sorgfältigen Programmierstil, um Ressourcenbedarf und
Performance eines Programms zu optimieren. Hier einige Hinweise (ohne
Anspruch auf Vollständigkeit):
Allgemein:
• Zeitkritische Tasks sollten möglichst keine bzw. wenige Systemaufrufe
verwenden.
• Verwende kritische Abschnitte sparsam, insbesondere bei Tasks mit niedriger
Priorität (à Prioritätsinversion).
• Verlagere zeitaufwändige Aufgaben in eigene Tasks.
3. Sprachen
• Vermeide dynamische Speicherallokation
• Dynamische Speicherverwaltung ist aufwändig (Fragmentierung) und
schwer vorhersagbar; "out-of-memory"-Risiko.
• Verwende Bibliotheksfunktionen (memcp, strcpy, …)
• Solche Funktionen sind i.d.R. für die gegebene Zielplattform optimiert.
• Verwende niemals Zählschleifen zum Warten
• z.B. for( i=0; i < 100000; i++ )
; // wait
•
•
•
•
Ist nicht portierbar.
Funktioniert nicht bei preemptivem Scheduling.
Ein guter Compiler optimiert das weg.
Verwende stattdessen Systemaufrufe wie sleep(), pause(), …
Programmierung:
• Vermeide Rekursion
• Rekursion führt zu hohem Speicherverbrauch auf dem Stack. Dabei kann
ein rekursiver Algorithmus immer auch in einen iterativen überführt werden
(das kann u.U. auch der Compiler machen).
41
3. Sprachen
• Vermeide Busy Waiting
• z.B. Polling von I/O Registern:
while (*RegisterAdr == 0)
; //Wait until button pressed
• Verbraucht unnötig CPU-Leistung
• Benutze stattdessen (wenn möglich) einen Interrupt für das entsprechende
I/O Register
Compiler-Optimierungen:
Die Beachtung der folgenden Hinweise macht es dem Compiler leichter,
bestimmte Optimierungen bei der Codegenerierung anzuwenden. Auf einem
Desktop-Computer sind die Effekte zwar meist minimal, auf einem embedded
µController können sie aber durchaus signifikant werden.
[Jakob Engblom: "Getting the Least Out of Your C Compiler". Embedded
Systems Conference, San Francisco. 2001].
43
42
3. Sprachen
• Verwende immer den kleinstmöglichen Datentyp
• C definiert int als mindestens 16 Bit lang. Auf einem 8-Bit µController
führt die Verwendung von int daher zu Overhead.
• Überprüfe den "richtigen" Datentyp bei einer Portierung des Codes!
• Benutze unsigned wenn möglich
• Insbesondere Bit-Shift-Operationen können für negative Zahlen
unerwartete Ergebnisse liefern. Wenn der Compiler weiß, dass negative
Zahlen nicht vorkommen, kann er entsprechend effizienteren Code
erzeugen.
• Deklariere alle Funktionen korrekt
• Kennt der Compiler den Funktionsprototyp nicht, muss er für
Rückgabewert und Parameter per default int bzw. double annehmen.
Das kann zu unnötigen cast-Operationen führen.
44
11
3. Sprachen
• Gruppiere Funktionsaufrufe
• Vor einem Funktionsaufruf müssen Registerwerte u.U. wieder ins RAM
geschrieben werden, da die Register für Parameter und Rückgabewert
gebraucht werden. Beispiel:
void foo (int a, b, c, d)
{
}
void foo (int a, b, c, d)
{
//a, b, c, d in Registern
//a, b, c, d in Registern
struct S s;
s.A = a;
s.B = bar(b);
s.C = c;
//c nicht mehr im Register
s.D = c;
s.E = baz(d);
}
struct S s;
s.A = a;
s.C = c;
s.D = c;
s.B = bar(b);
s.E = baz(d);
45
3. Sprachen
• Vermeide "cleveren" Code
• Möglichst viele Operationen in eine Anweisung zu packen ist nicht nur
unleserlich, sondern führt auch fast nie zu effizienterem Object-Code.
• Generell gilt: Code, der für einen Menschen leichter verständlich ist, ist
auch vom Compiler besser zu handhaben und optimieren.
• Beispiel:
int bar (char *str) {
return foo (str + (*str == '+'));
//braucht zusätzlichen Speicher / Register
//für Zwischenergebnis
}
46
4. Analyse
Ziel der Analyse eines (Echtzeit-) Systems ist es, die Korrektheit so weit wie
möglich formal und automatisch nachzuweisen. Testen allein ist i.d.R nicht
ausreichend, da dadurch bekanntlich nur die Anwesenheit, aber nicht die
Abwesenheit von Fehlern nachgewiesen werden kann.
Für verschiedene Aspekte von (Echtzeit-) Systemen existieren verschiedene
Analyseverfahren, z.B. die Schedulability-Analyse (s. Kapitel 2, 4), Model
Checking, oder WCET-Analyse.
int bar (char *str) {
if(*str == '+')
str++;
return foo (str);
}
Model Checking wird verwendet um nachzuweisen, dass ein System:
• Niemals bestimmte Fehlerzustände erreicht,
• "Das Getriebe wird niemals in den Rückwärtsgang schalten, wenn das
Fahrzeug vorwärts fährt."
• Einen gewünschten Zustand irgendwann erreicht,
• "Der Motor wird irgendwann im Normalmodus laufen."
• Nach einem Zustand x immer Zustand y erreichen wird.
• "Wenn der Motor läuft, wird er nach Drücken des Stop-Knopfes
irgendwann aus sein."
Viele solcher Regeln und Hinweise sind in firmen- und branchenspezifischen
Coding Rules festgelegt (z.B. MISRA-C, Motor Industry SW Reliability
Association). Das Hauptziel solcher Regeln ist, den Source-Code sicherer zu
machen, indem kritische und fehleranfällige Konzepte der Sprache
eingeschränkt bzw. ganz verboten werden.
3. Sprachen
• Mache lokale Funktionen static
• Ermöglicht Inlining, da der Compiler weiß, dass die Funktion nicht von
extern aufgerufen wird.
• Mache lokale Variablen static
• Mehr Optimierungsmöglichkeiten, da der Compiler weiß, dass nicht von
extern auf die Variable zugegriffen wird.
• Vermeide inline-Assembler
• Inline-Assembler zwingt den Compiler, die meisten Optimierungen
auszuschalten, da er nichts darüber weiß, welche Effekte der AssemblerCode hat.
• Schreibe compilerfreundliche Schleifen
• Die Indexvariable sollte im Schleifenrumpf nicht verändert werden.
• Die Indexvariable sollte nach der Schleife nicht mehr verwendet werden.
47
48
12
4. Analyse
Die Zustände des Systems und die Übergänge zwischen den Zuständen
werden durch endliche Automaten dargestellt. Die Aussagen über das System
("Fehlerzustände werden nie erreicht", etc.) werden mittels temporaler Logik
formal ausgedrückt.
CTL (Computation Tree Logic) ist eine temporale Logik, mit der formale
Aussagen über Zustände und (unendliche) Folgen von Zuständen gemacht
werden können. Die Zustandsfolgen bilden Pfade bzw. Bäume.
Syntax:
f und g seien Aussagen über das System, die entweder wahr oder falsch sein
können. Die Quantoren E und A stehen für "entlang mind. eines Pfades" (Exist),
bzw. "entlang aller Pfade" (All). Ausgehend von einem Startzustand können die
folgenden Aussagen gemacht werden:
• AX f:
Für alle direkten Nachfolger gilt f ("neXt state").
• EX f:
Es existiert ein direkter Nachfolger, für den f gilt.
• A (f U g): f gilt immer bis zum ersten Auftreten von g.
• E (f U g): Für mind. einen Pfad gilt: Bis zum ersten Auftreten von g gilt f.
49
4. Analyse
Beispiele:
EF f
AG f
• AF f:
• EF f:
• AG f:
• EG f:
• ¬ f:
• f ∧ g:
4. Analyse
Auf allen Pfaden wird ein Zustand erreicht, in dem f gilt ("Future state").
Auf mind. einem Pfad erreicht man einen Zustand, in dem f gilt.
Auf allen Pfaden gilt in jedem Zustand f ("Globally").
Auf mind. einem Pfad gilt in jedem Zustand f.
Negation.
UND.
Bemerkung:
• AF f = A (true U f)
• EF f = E (true U f)
• AG f = ¬E (true U ¬f)
• EG f = ¬A (true U ¬f)
50
4. Analyse
Model Checking:
Ausgehend vom Startzustand exploriert ein Model Checker alle möglichen
Nachbarzustände:
• Auswahl eines noch nicht evaluierten Zustandes
• Prüfung aller möglichen Zustandsübergange:
• bereits bekannter Zustand: verwerfen
• unbekannter Zustand: Eigenschaft prüfen
• falls Eigenschaft nicht erfüllt, Abbruch und Präsentation eines
Gegenbeispiels
• falls erfüllt, zur Menge der nicht evaluierten Zustände hinzufügen
• Abbruchbedingung: alle erreichbaren Zustände wurden überprüft
AF f
EG f
• Problem: Zustandsraumexplosion
• Die Menge der möglichen Zustände und Pfade ist exponentiell groß.
• Es existieren aber effiziente Model Checking Algorithmen (symbolische
Model Checker, bounded Model Checker), so dass das Verfahren in der
Praxis auch für komplexe Systeme anwendbar ist.
51
52
13
4. Analyse
Worst-Case Execution Time (WCET) Analyse
4. Analyse
?
Programmverhalten:
l # Schleifendurchläufe
l Abhängigkeiten zw.
if-Statements
l Funktionsaufrufe
l etc.
WCET:
• längstmögliche Ausführungszeit eines Programms auf einer gegebenen
Zielhardware
• ohne Interrupts und Context Switches
Objekt-Code Ebene
Technik: statische Analyse
• Das Programm wird nicht ausgeführt, sondern analysiert
• Im Prinzip unmöglich à Halteproblem!
Häufigkeit
tatsächl.
BCET
Hardwareverhalten
l Ausführungszeiten für Programmteile
l Berücksichtigung von Hardware-Eigenschaften
Berechnung
Berechnung
sichere WCET
Schätzungen
mögliche Ausführungszeiten
genauer
genauer
WCET Berechnung
l durch Kombination der Ergebnisse von
high- und low-level Analyse
Zeit
53
4. Analyse
Kontrollfluss-Analyse
Hierarchischer Kontrollflussgraph:
A
B
C
I
f
i=
or(
for
1..
(j=
.n)
1..
D
.
E if(
en
th F
G
..)
s
el
e
H
inner loop
J
Low-Level
Low-Level
Analyse
Analyse
tatsächl.
WCET
sichere BCET
Schätzungen
0
KontrollKontrollfluss
fluss
Analyse
Analyse
Source-Code Ebene
.i)
Knoten sind die Basisblöcke des
Programms, d.h. Folgen von Instruktionen
ohne Verzweigungen
Gesucht: Informationen über mögliche
– und unmögliche – Programmabläufe
• Anzahl der Iterationen
• unmögliche Pfade (z.B. "wenn C dann nicht
G")
54
4. Analyse
Low-Level Analyse: Pipelines
• überlappende Ausführung von Instruktionen
• erhöht den Durchsatz
• vgl. Fließbandproduktion
• heute Standard in fast allen Prozessoren
Beispiel: 3 Stufen
• Instruction Fetch, Execute, Write Back
• Ausführungszeiten sind abhängig von benachbarten Instruktionen
Takt: 1 2 3 4 5 6 7 8 9 10
IF
EX
WB
non-pipelined
pipelined
Superscalare Architekturen
• verarbeiten mehrere Instruktionen gleichzeitig
• mehrere parallele Einheiten (z.B. Integer und Floating Point)
outer loop
Takt: 1 2 3 4 5 6 7 8 9 10
IF
EX
WB
Informationsquellen:
• Programmierer
• Codegeneratoren
• Analyseverfahren
• z.B. "abstract interpretation"
WCET
WCET
Schätzung
Schätzung
55
56
14
4. Analyse
Analyseverfahren:
• abstraktes (SW-) Modell des Prozessors
• Folgen von Instruktionen "simulieren" bzgl. Zeitverhalten
• Ergebnis: Zustand der Pipeline nach Ausführung der Instruktionen
• "Addition" von größeren Blöcken durch Konkatenation der Pipelines
4. Analyse
Ergebnis der Low-Level Analyse:
Annotierter Kontrollflussgraph
δ AI
tA = 5
IF
EX
WB
tB = 7
tI
IF
EX
WB
I
• Ausführungszeiten pro Knoten isoliert
tB B
δ BC
δ BD
• Pipeline-Effekt pro Kante (negativ)
tC C
δ CE
δ EF
tF
tAB = 10
δ IJ
IF
EX
WB
..
Aufgabe der Analyse:
• Vorhersage "cache hit" / "cache miss"
für Speicherzugriffe zur Laufzeit
• Modellieren des Cache-Verhaltens
• Abbildung RAM à Cache
• Verdrängungsstrategie (LRU, FIFO, ...)
57
...
RAM
Instruction
Cache
D tD
δ DE
δ HB
E tE
δ EG
δ JA
G tG
δ GH
H
F
δ FH
tH
δ HJ
tJ
•AB = tAB – (tA + tB) = –2
4. Analyse
Low-Level Analyse – Caches
• kleiner, schneller (daher teurer)
.
Pufferspeicher
• behält zuletzt verwendete Blöcke
aus dem RAM
• Zugriff i.d.R. innerhalb 1 Takt
• Laden aus dem RAM: ca. 50 Takte
tA A
δ AB
InnerLoop
J
OuterLoop
58
4. Analyse
Algorithmus:
• Für jeden Knoten v des Kontrollflussgraphen
• IN(v):
Cache-Inhalt am Anfang von v
• OUT(v): Cache-Inhalt nach Ausführung von v
Data
Cache
for each v do
IN (v) := { }
OUT(v) := { }
Prozessor
Prozessor
while 'any change' do
choose v
∩
IN (v) :=
{OUT (p) | p ∈ Vorgänger(v)}
OUT (v):= 'simuliere Cache-Verhalten innerhalb v'
cache miss
Takt: 1 2 .
IF
EX
WB
.
. .
Am Besten in topologischer
Reihenfolge
50
59
60
15
4. Analyse
4. Analyse
Für die Berechnung der WCET gibt es 2 Ansätze:
IN = { }
OUT = {a, d, e}
a = 7;
if (d > e)
{
c = d / e;
if (a > c)
{
a = c;
}
c = b;
}
else
{
c = e / d;
}
e = b + c;
ILP (Integer Linear Programming)
• gesucht: maximale Ausführungshäufigkeit xi je Knoten / Kante
• WCET = maximiere •(xi * ti)
IN = {a, d, e}
OUT = {a, c, d, e}
δ AI
• Struktur-Constraints
IN = {a, c, d, e}
OUT = {a, c, d, e}
• xE • xCE + xDE
• Kontrollfluss-Constraints
I
• xA • 42
IN = {a, c, d, e}
OUT = {a, b, c, e}
tF
δ IJ
Graphbasiert:
• gesucht: der längste Weg im
Kontrollflussgraphen
• effizient (O(m)), aber weniger mächtig
IN = {a, c, e}
OUT = {a, b, c, e}
61
4. Analyse
A
tB
δ BC
B
D tD
δ DE
δ CE
E
tE
δ EG
δ HB
δ JA
G tG
δ GH
F
δ FH
tH
δ AB
δ BD
C
δ EF
• komplex (NP-schwer!), aber mächtig bzgl.
Kontrollflussinformationen
IN = {a, d, e}
OUT = {a, c, d, e}
tC
tI
tA
H
δ HJ
tJ
InnerLoop
J
OuterLoop
62
4. Analyse
Komplexität der Berechnung:
start
t =11
A
δ =-2
δ =-2
t =15
B
δ =-1
δ =-2
D
t =5
δ =-3
δ =-1
E
F
δ =-3
Benchmark
insertsort
jfdctint
matmult
compress
nsichneu
nsichneu2
nsichneu3
t =17
C
δ =-3
t =19
Berechnung des längsten Weges
• Für jede Schleife
• Bottom-up: innere Schleifen
zuerst
• Modifikationen am Graphen
• Rückwärtskanten eliminieren
• Schleifen aufrollen
• unmögliche Pfade eliminieren
t =29
Variablen Constraints
51
61
86
99
224
262
701
753
4656
4290
5186
4833
5456
5109
Zeit (s)
ILP
Graphb.
0,04
0,01
0,08
0,01
0,29
0,02
2,04
0,06
76,79
0,21
98,53
113,44
108,53
317,75
• ILP Laufzeit explodiert mit der Problemgröße
• Graphbasierte Methode explodiert mit der Komplexität der Constraints
δ =-1
G
t =15
δ =-1
end
δ =-2
cont
63
64
16
4. Analyse
Stand der Technik: WCET Tools
• Die Low-Level Analyse (Modellierung von Prozessorarchitekturen) ist sehr
ausgereift. Allerdings werden die Prozessoren auch immer komplexer und
schwerer analysierbar.
• Kommerzielle WCET Tools:
• aiT (Deutschland)
• Bound-T (Finnland)
• RapiTime (England)
• Open Source / Research Tools:
• SWEET (Schweden / Deutschland)
• Chronos (Singapur)
• Heptane (Frankreich)
• ...
5. Zusammenfassung der Vorlesung
Timing ist ein Thema, das durchgehend im gesamten Entwurfsprozess
berücksichtigt werden muss.
Eigenschaften von RTS
Allgemein
Spezielle Probleme bei RTS
Scheduling
RTS
RTOS
Verteilte RTS
Anwendungen
• Avionics, z.B. Airbus A380 flight control Software (aiT)
• ESA (Bound-T)
• Automotive
RTS Design
65
66
Periode T
Taskmodell
Ausführungszeit C
Deadline D
D=T
Eigenschaften von RTOS
RMS
DMS
POSIX
optimale Prioritätsvergabe
Standards
statisch
D <= T
RTA
Blockiert-Zeiten
OSEK
AUTOSAR
Priority Inversion
Scheduling
Priority Inheritance
RTOS
Priority Ceiling
Tasks, Scheduler
Release Jitter
Timer
OS-Overhead
RTOS Elemente
(D>=T)
Events
Message Queues
EDF
dynamisch
Interrupts
LLF
67
68
17
spezielle Aufgaben beim Design von RTS
zentral
Uhrensynchronisation
Allgemein
verteilt
fehlertolerant
Anforderungen an Prozesse für RTS Design
CAN
event-triggered
Prioritäten für Nachrichten
Wasserfallmodell
Prozesse
Busarbitrierung
Spiralmodell
V-Modell
statischer Teil
Echtzeitkommunikation
Verteilte RTS
FlexRay
time-triggered
dynamischer Teil
Model Driven Architecture
Uhrensynchronisation
Middleware
UML
RTS Design
RT-CORBA
Modellierungssprachen
EAST-ADL
Abstraktionsebenen
AUTOSAR RTE
Events, Event-Ketten
holistische Analyse
Scheduling in
verteilten Systemen
Ada
Deadline Monotonic
Scheduling in verteilten
Systemen
Programmiersprachen
RT-Java
Programmierstil
Berechnung der
Übertragungsdauer
(Token ring)
Scheduling
Temporale Logik
Simulated Annealing
Analyse
Allocation
Model Checking
WCET Analyse
69
70
18

6. Design von Echtzeitsystemen

Transcrição

Documentos relacionados

Eröffnung Heinerfest 2015 Darmstadt

Ad-hoc-Betreuung an der Waldspirale in Darmstadt

3 66 88 99 Centralstation/Im Carree/Darmstadt

Eisenbahnmuseum Darmstadt Kranichstein Vernissage am

Anfahrt Darmstadt

das Original PDF - Orplid

Lernunterstützung

DARMSTADT LEONHART OPEN

6. Elemente eines RTOS