Echtzeitverarbeitung - Isabel Drost-Frommisabel-drost.de/bin/Echtzeitverarbeitung.pdfSemaphoren sind häufig binär (z.B. µP – INT – FF), manchmal aber auch mehrwertig (Wertevorat

Echtzeitverarb
eitung
HTWM Hochschule für Technik undWirtschaft Mittweida Technikumsplatz 17 09648 Mittweida

Erstellt von: Isabel Drost (if99wP1) Dozent: Prof. Dr. Ruck [email protected] http://www.isabel-drost.de Druckhinweis: in Buchform geschrieben

mailto:[email protected]

http://www.isabel-drost.de/

0 Motivation.....................................................................................................................................5 0.1 Literaturhinweise: ............................................................................................................................ 5

0.2 VO – Gliederung............................................................................................................................... 5

1 Sequentielle und parallele Prozesse ............................................................................................6 1.1 Parallele Prozesse werden in zwei Klassen unterteilt:................................................................... 6

1.2 Trennung von Prozessen und Programm....................................................................................... 7

2 Verwaltung paralleler Prozesse ...................................................................................................7 2.1 Klassifizierung paralleler Rechenprozesse..................................................................................... 7

2.2 Aufgaben der Prozessverwaltung.................................................................................................... 8

2.3 Werkzeuge der Prozessverwaltung ................................................................................................. 8

2.4 Verwaltungsstrategien: .................................................................................................................... 9

3 Das Echtzeitbetriebssystem MRT86 ..........................................................................................10

4 Betriebsmittelverwaltung ...........................................................................................................12 4.1 Prozessorverwaltung ...................................................................................................................... 12

4.2 Speicherverwaltung ........................................................................................................................ 13

4.3 Zeitgeberverwaltung ...................................................................................................................... 14

4.4 Ein-/ Ausgabeverwaltung............................................................................................................... 14

4.5 Prozessorbelastung ......................................................................................................................... 14

5 Beschreibung von Echtzeitsystemen..........................................................................................14 5.1 Petrinetze......................................................................................................................................... 14

5.2 Formale Beschreibungen und Zeitdiagramme............................................................................. 21

Echtzeitverarbeitung Motivation

0 Motivation sequentielle Denkweise für den Ablauf eines Einzelprozesses soll ergänzt werden um die nebenläufige beim Zusammenspiel abhängiger Prozesse Annahmen der klassischen Programmierung: • Ein Rechner führt genau ein Programm aus. (Im Gegensatz zu Multitasking – Systemen) • Ein Programm wird genau auf einem Rechner ausgeführt. (Im Gegensatz zum verteilten Rechnen) • Ein Programm erfüllt seine Funktion unabhängig vom Startzeitpunkt und benötigter Bearbeitungszeit. (Echtzeit-

verarbeitung setzt hier einen Gegensatz an.) Im Gegensatz zu diesen Annahmen existiert die:

concurrent, distributed, realtime dependend programs nebenläufige (simultane), verteilte und echtzeitabhängige Programme

Arbeitet man mit dieser Art von Programmen, muß zwischen dem Programm selbst und dem Prozess unterschieden werden.

0.1 Literaturhinweise: • Herrtwich, R.G.; Hommel, G.: nebenläufige Programme.Nebenläufige verteilte und

echzeitabhängige Rechenprozesse Berlin, Heidelberg, New York, Springer 1994 (siehe auch Bibliothek)

• Wettstein, H: Entwicklung von Betriebssystemen.München, Wien, Carl Hanser ... • Dannegger, Ch.: Gengelin-Dannegger: Parallele Prozesse unter UNIX.München, Wien, Carl

Hanser, 1991

0.2 VO – Gliederung • Sequentielle und parallele Prozesse

- Prozessbegriff - Demonstration der Zeitabhängigkeit voneinander abhängiger Prozesse

• Verwaltung paralleler Prozesse - Steuerung der simultan ablaufenden Prozesse - räuml. und zeitl. Verwaltung - Betriebsmittelbegriff - konkurierende und kooperierende Prozesse - Verwaltungsaufgaben (Prozeßkoordination, -synchronisation, -kommunikation) - Verwaltungswerkzeuge (Semaphor, Warteschlange, Nachrichtenpuffer) - Verwaltungsstrategien (RoundRobin, Ereignissteuerung) - Begriffe wie VM, ext. Ereignis, Echzeit, Deadlock

• BM- Verwaltung - Prozessor, Speicher, Clock, E/A-Kanäle

• Beschreibung von Echzeitsystemen - Petri-Netze ohne, mit, mit unterscheidbaren Marken - formale Beschreibungen - Zeitdiagramme

• EchtzeitBS - wichtige EZBS in der Praxis - zeitliches Verhalten von RT-BS

• Echzeitsprachen - zugeschnittenes RT-Sprachen für embedded systems - Möglichkeiten von C, Ada, Pearl - Ergänzung prozeduraler Sprachen (z.B. C) um einen RT-BS-Kern

Isabel Maine C. Drost Seite 5 von 29

Echteitverarbeitung Parallele Prozesse werden in zwei Klassen unterteilt:

1 Sequentielle und parallele Prozesse Ein System ist ein relativ abgeschlossener Teil der Welt, der über Ein- und Ausgangsrößen mit seiner Umwelt in Wechselwirkung steht. • in einem solchen System laufen Prozesse ab

- Ein Prozeß abstrakt definiert: Zeitlich geordnete Folge von Zuständen.

- Ein Prozeß konkret definiert: quantitative oder qualitative Änderung von Stoffen, Energien oder Informationen in Abhängigkeit von der Zeit.

• mehrere (separierbare) Prozesse laufen gleichzeitig ab,

sind aber nicht voneinander isoliert • für zwei Prozesse gelten folgende Beziehungen:

- sequentielle Prozesse, genau dann, wenn b beginnt, wenn a beendet ist oder umgekehrt - parallele Prozesse, genau dann, wenn b beginnt, bevor a beendet ist.

1.1 Parallele Prozesse werden in zwei Klassen unterteilt: • unabhängige Prozesse: es gibt keine Wechselwirkungen zw. den Prozessen, sie laufen vollständig assynchron • abhängige Prozesse: Wechselwirkungen existieren, der Zustand eines Prozesses ist vom Zustand eines anderen

Prozesses abhängig, laufen meist assynchron • in Multitask- und Echtzeitsystemen müssen

Berechnungsschritte simultan ausgeführt werden, weil andernfalls ein Informationsverlust möglich wäre

• Echtzeit: relative Lage der Prozesse zueinander • simultane Arbeitsweise bringt Probleme, die

durch die nicht vorherbestimmbaren relativen Ausführungsgeschwindigkeiten von Rechenpro-zessen entstehen

• es kann zu falschen Ergebnissesn (Zeitvarianz) bei abhängigen parallelen Rechenprozessen führen

Beispiel: Gegeben seien zwei parallele Prozesse a und b, die die externen Ereignisse 1 und 2 in einer gemeinsamen, globalen Variablen zählen.

U M W E L T

S Y S T E M

System = abgeschlossener Raum der Umwelt

Eingangs-größen

Ausgangs-größen

Abbildung 1-1; Ein System in seiner Umwelt

Zeit

AB

AB

Zeit

Zeit

Prozeß a und b beeinflußen sich nicht, laufen sequentiell ab

AB

A

Prozess a und b laufen gleichzeitig, beeinflußen sich nicht

Prozess a und b laufen parallel und beeinflussen sich

Zeiit

Abbildung 1-2; Visualisierung der Prozessarten

Prozess A | Prozess B E1 i++ | |i++ E2 `.´Zeit Ergebnis ist OK, die Summe ist zwei Beim Compilieren eines Programms, geschrieben in einer Hochsprache wird eine solche Anweisung im ungünstigsten Fall in mehrere Prozessorschritte zerlegt: Hole die Variable, Inkrementiere die Variable, Schreibe die Variable zurück. Somit ist das Ergebnis zeitabhängig.


Echtzeitverarbeitung Verwaltung paralleler Prozesse

Das gleiche Problem tritt bei quasisimultaner Aktionsfolge auf. (B sei höher priorisiert als A) Prozess A | Prozeß B E1 | a=i | E2 . | b=i . | b++ . | i=b a++ | i=a | `.´zeit

Folge: i ist wieder nur um eins erhöht!

Forderung: Die Ausgangsgrößen (Ergebnisse) eines Echtzeitsystems sind eine zeitunabhängige Folge der Eingangsgrö-ßen (Parameter).

1.2 Trennung von Prozessen und Programm • wichtiger Aspekt bei parallelen Rechenprozessen: Mehrere Prozesse können gleichzeitig dasselbe Programm

benutzen reentrante Programme • strikte Trennung zwischen Programm und Prozess Programm = Folge von Befehlen/ Anweisungen im Speicher oder auf einem externen Datenträger

- enthält die exakte Forumulierung eines Algorithmus in einer Programmiersprache - legt Regeln für die Verarbeitung von Informationen fest - kann einen Teil der Prozeßumgebung (Prozeßrumpf) bilden

Prozeß = existiert während der Ausführung eines Programmes auf einem Rechner

- ist ein dynamischer, lebendiger Vorgang - entsteht, wenn ein Progrmm gestartet wird - seine Lebensdauer beginnt mit der ersten und endet mit der letzten ausgeführten Anweisung

2 Verwaltung paralleler Prozesse Ziel: - Steuerung der gleichzeitig auf dem Rechner ablaufenden Prozesse - sinnvolle Aufteilung der Rechnerhardware, zeitliche Organisation der Prozesse Prozeßverwaltung: - räumliche und zeitliche Koordination von Benutzerprozessen auf dem Rechner - ist von konkreter Rechnerhardware abhängig aber von Funktionen der Benutzerprozesse unabhängig - Problemunabhängigkeit des Prozeßverwalters Betriebsmittel (BM): - physische Bestandteile eines Rechners (Speicher, CPU) - im erweiterten BM-Begriff gehören auch Nachrichtenpuffer, Semaphoren, Prozeßbeschreibungen (TCB) dazu

2.1 Klassifizierung paralleler Rechenprozesse - konkurrierende Prozesse

= unabhängige parallele Rechenprozesse kommen aufgrund ihrer Ausführung auf dem selben Rechner in Berührung

= konkurrieren um gemeinsam genutzte BM

- kooperierende Prozesse = abhängige Prozesse kommen aufgrund ihrer Ausführung auf dem selben Rechner sowie aufgrund des

Infromationsaustauschs in Berührung = laufen meist assynchron


Echteitverarbeitung Aufgaben der Prozessverwaltung

Typisch für konkurrierende Prozesse: • Multitasksysteme • Multiusersysteme (Auslastung der Rechnerhardware, Zugangsmöglichkeit für mehrere Nutzer) Typisch für kooperierende Prozesse: • Systeme der Prozessdatenverarbeitung mit einem gemeinsamen Steuerungsziel

2.2 Aufgaben der Prozessverwaltung • Prozeßkoordination

- wechselseitiger Ausschluß beim BM-Zugriff - für konkurierende und kooperierende Prozesse

• Prozeßsynchronisation - Gleichlauf von Prozessen zu bestimmten Zeiten - nur für kooperierende Prozesse

• Prozesskommunikation - Nachrichtenaustausch mit oder ohne zeitl. Entkopplung - nur für kooperierende Prozesse

2.3 Werkzeuge der Prozessverwaltung • Semaphor: globale Variable zum wechselseitigen

Ausschluß sowie zur Synchronisation paralleler Prozesse

Beispiel: Einseitige Synchronisation mit binärem Semaphor Semaphoren sind häufig binär (z.B. µP – INT – FF), manchmal aber auch mehrwertig (Wertevorat ist mindestens so groß, dass alle gesendeten aber noch nicht empfangenen Zeitsignale erfaßt werden können.)

Zustand n n+1 n+2

Zustand m

Prozeß A

Prozeß B

Semaphor

Prozeß B soll erst dann in den Zustand m+1 eintreten,wenn Prozeß A schon in n+2 war

warten

Zustand m+1

Abbildung 2-1; Beispiel für einen binären Semaphor

2.3.1 Einseitige Synchronisation in C EEiinnsseeiittiiggee SSyynncchhrroonniissaattiioonn iinn CC

p(sema) und v(sema) sind Operatoren, nach Dijkstra, die folgende Bedeutung haben: ......

iinntt sseemmaa==00;; //**SSeemmaapphhoorr wwiirrdd iinniittiiaalliissiieerrtt**// vvooiidd PPrroozzeessss__AA(()) {{ ...... vv((sseemmaa)) //**SSeemmaapphhoorr ffrreeiiggeebbeenn**// ...... }} vvooiidd PPrroozzeessss__BB(()) {{ ...... pp((sseemmaa));; //**SSeemmaapphhoorr aabbffrraaggeenn**// ...... }}

p ... Probieren/ request semaphor

v ... Erhöhen/ Release-Semaphore

sema--

sema<0j n

anfordernden Prozeß block.

Abbildung 2-2; Visualisierung der atomaren Funktion p


sema++

sema<=0j n

anfordernden Prozeß deblock.

Abbildung 2-3; Visualisierung der atomaren Funktion v

Echtzeitverarbeitung Verwaltung paralleler Prozesse

2.3.2 Zweiseitige Synchronisation und wechselseitiger Ausschluß ZZwweeiisseeiittiiggee SSyynncchhrroonniissaattiioonn uunndd wweecchhsseellsseeiittiiggeerr AAuusssscchhlluußß ......

iinntt sseemmaa==11;; vvooiidd PPrroozzeessss__AA(()) {{ ...... PP((sseemmaa));; //**EEiinnttrriitttt iinn kkrriittiisscchheenn AAbbsscchhnniitttt**// ...... VV((sseemmaa));; //**AAuussttrriitttt aauuss kkrriittiisscchheemm AAbbsscchhnniitttt**// ...... }} vvooiidd PPrroozzeeßß__BB(()) {{ ...... PP((sseemmaa));; ...... VV((sseemmaa));; ...... }}

2.3.3 Nachricht • zwischen parallelen Prozessen ausgetauschte Daten mit beiden kommunizierenden Seiten bekannter Bedeutung • Austausch im Rendevous bzw. mit zeitlicher Entkopplung bei Benutzung von BM

2.3.4 Warteschlange geordnete Liste von Prozessen, die auf Benutzung eines gemeinsamen BM warten

2.4 Verwaltungsstrategien:

2.4.1 nichtunterbrechbare Steuerung: • FCFS – First come first served • SJN – shortest job next • HRN highest response ratio next typisch für konventionelle Dtenverarbeitungsanlgen (effektive Rechnerauslastung, vorherschaubare Antwortzeiten, Antwortzeit: vom Start des Programms bis zum Ende, aber in Multitasking-Umgebung, Antwortverhältnis – Antowortzeit – Rechenzeit unterbrechende Steuerung: RoundRobin, EventControl • typisch für Echzeitsysteme, nicht effiziente Rechnerauslasturn, sondern Auslastung des kompletten Systems

entscheiden • RoundRobin: Zeitscheibenverfahren, in Multiuser- und –tasksystemen • Event Control: Verwaltung nur zu systemrelevanten Zeitpunkten, in Echtzeitsystemen und damit

Multitasksystemen, bei Ereigniseintritt (externe Unterbrechung, interner Aufruf) erfolgt Entscheidung, welcher Prozeß jetzt forzuführen ist

Virtuelle Maschine: • zur Ausführung eines Programms simulierte Funktion eines Rechners • gegenwärtige Prozessoren arbeiten sequentiell Widerspruch zu simultan zu lösenden Aufgaben • für jeden Prozeß eigener Prozessor emuliert • virtuelle Parallelmaschine, jeder Prozeß läuft auf eigenem Pseudoprozessor


Echteitverarbeitung Verwaltungsstrategien:

externes Ereignis: • Meldung des zu steuernden externen Prozesses an den steuernden Rechenprozeß, erfolgt meistens indirekt über

Verwaltungsprozeß (Bestandteil eines problemunabhängigen EchtzeitBSkerns • für Echtzeitsysteme entscheidend Ausrichtung des Steuerungsablaufes • Prozessorkapazität darf in Echtzeitsystemein nicht voll ausgeschöpft werden (20-30% üblich) Einführung eines

Leerlaufprozesses Begriff Echtzeit: nur für steuernden Prozeß relevant • Einhaltung der von den zu steuernden Prozessesn vorgegenen zeitlichen Bedingnungen durch steuernde

Rechenprozesse • Echtzeitbedingung erfüllt, wenn

- alle Rechenprozesse in zur Verfügung stehender Zeit bearbeitet - rechtzeitige Reaktion auf externes Ereignis erfolgt - keine Informationen verlorengehen

3 Das Echtzeitbetriebssystem MRT86 MRT86 – Multitask Realtime – Kernel für 80x86Prozessoren Smmlung von Funktionen für quasiparallele Prozesse auf Monoprozessorsystem Wichtige Eigenschaften: • dynmische Verwaltung von 1 ... 255 Prozessen • prioritätsgesteuerte Betriebsmittelverwaltung (v.a. für Prozessor) • zeit- oder ereignisssteuerung der Prozesse (ext./ int. Interupts) • für jeden Prozeß eigener Speicherbereich – Stack • Prozesskommunikation über Mailboxen • Prozesssynchronisation und –koordination über Semaphoren • strukturierte zeitoptimierte Verwaltungsaktionen Wichtige Verwaltungsrufe: • ACTIVATE_MRT86(EXITP, ERRC) ... aktiviert das Echtzeitsystem

exitp...Name der exitfkt.; errc ... Parameter für exitp (z.B. Fehlernummer) ist der erste Kernaufruf, Init der TaskControlblocks ITCB Zeitgeber auf 10ms umprogrammieren Start von idle

• START_PROCESS(PROC, PTY, SIZE, ADDR) Prozess starten, PROC ... Prozessnummer (1-255) PTY – Priorität (0-30) SIZE – Größe des belegten Speichers, Vielfaches von 256 byte

INACT RDY RUN

HOLD

BLOCK

BLOCK&HOLD

WAIT&HOLD

WAIT

stopstart

aw

ai t

Priorität

send

s

end

REQ - REL

s

t op

start

Abbildung 3-1; MRT86 Prozessmodell

• STOP_PROCESS(PROC) • HOLD_PROCESS()

Prozeß anhalten

• CONTINUE_PROCESS() • DELAY_PROCESS() • DELAY_ONCE(Proc_number, time_in_ms) • DELAY_CYCLIC() • ALTER_PRIORITY() • SEND_MESSAGE() • AWAIT_MESSAGE() • REQUEST_SEMAPHORE() • RELEASE_SEMAPHORE() • PLAN_EVENT()

Ereignisaktion planen (auf Int)

• MOVE_GLOBAL() globale Vriable lesen/ schreiben


Echtzeitverarbeitung Das Echtzeitbetriebssystem MRT86

• ENABLE_INTERRUPT() • DISABLE_INTERRUPT() • PROCESS_NUMBER() • PROCESS_STATUS()

Prozesszustand abfragen

• MESSAGE_AVAILABLE() Nachrichtenverfügbarkeit prüfen

Bsp. für C-Quellcode: ##iinncclluuddee <<mmrrtt8866..hh>> ...... vvooiidd mmaaiinn((vvooiidd)) {{ ...... AACCTTIIVVAATTEE__MMRRTT8866((eexxiitt,, 00));; ////CC--HHaauuppttpprroogg.. aallss PPrroozzeeßß 00 ...... }} Explizite Kerndeaktivierung: DEACT_MRT86() RETURN_CODE(1 ... Nummer des gestarteten Prozesses zurückgeben, 0 .. Prozess wurde nicht gestartet (bereits aktiv, Prozessstapel voll oder falsche Priorität) Funktion beim Prozeßstart: • der zu satrende Prozeß wird aktiviert – RDY • Aubau des Prozeßstapels (u.a. ADR bei Fortsetzungsadresse eintragen) • ist gestarteter Prozess höher priorisiert als startender – Prozessumschaltung • Fortsetzung des höchst priorisierten Prozesses, der RDY ist Beispiel: ##iinncclluuddee <<mmrrtt8866..hh>> PPRROOCCEESSSS PP11 {{ SSTTAARRTT__PPRROOCCEESSSS((22,, 00,, 00,, PP22));; SSTTOOPP__PPRROOCCEESSSS((00));; }} PPRROOCCEESSSS PP22 {{}} vvooiidd mmaaiinn ((vvooiidd)) {{ AACCTTIIVVAATTEE__MMRRTT8866((eexxiitt,, 00));; SSTTAARRTT__PPRROOCCEESSSS((11..55,, 00,, PP11));; }}


Echteitverarbeitung Prozessorverwaltung

4 Betriebsmittelverwaltung

4.1 Prozessorverwaltung Prozessor: Engpass des Systems Prozessoraufteilung von besonderer Bedeutung

4.1.1 Prinzipielle Steuerungsalgorithmen 1) Vollständige Bearbeitung in der Ankunftsreihenfolge – Stapelbetrieb

2) Vollständige Bearbeitung in der Prioritätsreihenfolge

Prozessor

Alaufender ProzessProzessorwarteschlange

F E D C BProzessor-aufrufProzeßstart

Prozessor-aufgabeProzeßstop

Prozessor-zuteilung

Abbildung 4-1; Betriebsmittelverwaltung - Stapelbetrieb

Es ist auch dann keine Unterbrechung möglich, wenn der derzeit laufende Prozeß niedriger priorisiert ist, als der aktuell höchstpriorisierte Prozeß, der Ready ist.

3) Prioritätsgesteuerte Bearbeitung mit Freigabe

Prozessor

Alaufender ProzessProzessorwarteschlange

B C E D FProzessor-aufrufProzeßstart


Prozessor-zuteilung9 8 6 4 2

nach fallender Priorität geordnet

5

Abbildung 4-2; Betriebsmittelverwaltung – Vollständige Bearbeitung in Prioritätsreihenfolge

4) Prioritätsgesteuerte Bearbeitung mit Prozessorentzug – preemptiv Scheduling

AProzessorwarteschlange

Prozessor-aufrufProzeßstart


Prozessor-zuteilung

E F

BM-Warteschlange

A B C

ProzessorfreigabeProzeßunterbrechungProzeßsuspendierungProzeßfreigabe

Abbildung 4-3; Betriebsmittelverwaltung – Prozeßumschaltung bei Warten auf BM

AProzessor-aufrufProzeßstart


Prozessor-zuteilung

E F

BM-Warteschlange

A B CProzessverdrängungProzessorentzug

Abbildung 4-4; Betriebsmittelverwaltung - Prozeßverdrängung


Echtzeitverarbeitung Betriebsmittelverwaltung

Prozeßverwaltung im MRT86: über einen TCB (Task – Control – Block) 0 1 2 3 4 Status RDY RDY HOLD RUN INACT Priorität 31 4 0 2 ... ... ... Zeiger auf nächsthöher priorisierten Prozeß NULL 0 1 Zeiger auf nächstniedrigeren Prozeß 1 3 Sobald ein neuer Prozeß in der Prozeßwarteschlange eintrifft, wird er in der Prozessorwarteschlange entsprechend seiner Priorität und seines Status eingeordnet. • Für die Verwaltung eines Prozesses in einem Echtzeitbetriebssystem kommt nur die vierte Art in Frage. • 3 Prinzipien des preemptiven Schedulings:

- Abfragesteuerung (Polling): "probeweise" Rückgabe des Prozessors in vernünftigen Zeitabständen dann Verwaltungsabschätzung

- Zeitsteuerung: zyklische Unterbrechung durch den Verwalter dann Verwaltungsentscheidung - Ereignissteuerung: Verwaltungsentscheidung nur bei Ereigniseintritt (Interrupt, Verwaltungsaufruf)

4.2 Speicherverwaltung • Unterscheidung zwischen globalem und lokalem Speicher • global: Variablen des Verwalters (TCB, Mailboxen, Stackliste, Zeitgeberschlangen, Semaphoren) • lokal: jedem Prozeß zugeordnete Variablen (u.a. generelle Registerinhalte bei Prozeßabschaltung)

Datensegment

Stacksegment

0000 Prozeßtabelle0900 Stacktabelle

0A00 Mailbox Zeitgeberliste MRT86 - Variable

xxxx globale Variable

ffff frei

ST SB SL SH ML MH NX UP RC

08000000

00FF

Status | Priorität0 RDY/RUN1 HOLD2 WAIT3 W&H4 Block5 B&H6 INACT

0 ... 31

Stack k

...

Stack iStack 0frei

Speicherorganisation

0000

FFFF

SBSH, SL

Abbildung 4-5; Speicherorganisation beim MRT86


Echteitverarbeitung Zeitgeberverwaltung

I

4.3 Zeitgeberverwaltung • in Echtzeitsystemen definierte relative Zeitlage von Aktionen

zueinander • Aufgabe kann nicht durch den Prozessor, sondern muß durch

einen Zeitgeber übernommen werden. • Anzahl der Zeitgeberkanäle ist begrenzt – Schaffung

mehrerer virtueller Zeitgeberkanäle (alle durch einen physischen Zeitgeber versorgt)

CTC - Interruptfreigabe

Prozessorunterbrechung

Zeitgeber aktiv.0.01 sImpulsgeber (CTC)

Zeitgeberschlange(RAM)

Prozeßfreigabeimpuls

Abbildung 4-6; Zeitgeberverwaltung

4.4 Ein-/ Ausgabeverwaltung • ist nicht Bestandteil des Echtzeitbetriebssystemskerns, sondern wird Treibern (die als spezielle Prozesse ablaufen)

überlassen • E/A-Kanäle werden speziellen Prozessen zugeordnet, die mit anderen Systemprozessen kommunizieren

Prozessverwalter bleibt somit problemunabhängig

4.5 Prozessorbelastung • worst-case Abschätzungen für die Prozessorbelastung erforderlich • Belastungen durch Anwender und durch Verwaltungsprozesse können nicht immer vernachlässigt werden Beispiel Prozessorbelastung durch Verwaltungsaktionen:

p ... Prozessorbelastung zwischen 0 und 1 (rel. Anteil) nkc *+ c ... konstanter Laufzeitanteil der Verwaltungsaktionen

T V 5

5••

5•

•• De Ea

sabel Maine C. Drost

Tp = k ... relativer, prozessbezogener Anteil an Verwaltungsaktionen

n ... Anzahl der Prozesse ... mittlere Zeit für eine Aktion

erschiebung der Kurve nach rechts für größeres n!

Beschreibung von Echtzeitsystemen

.1 Petrinetze zur anschaulichen Darstellung von nebenläufigen Systemen und der Wechselwirkun 1962 durch Petri (Dissertation) vorgestellt

.1.1 Petrinetze ohne Marken Der Platz, von dem aus eine Kante zu einer Transition führt, heißt

Eingangsplatz.

g

AbbilduMarke

Nächstgelegene Plätze sind Ausgangsplätze. Auf einem Pfad wechseln sich die Plätze und Transitionen ab.

er Platz stellt den Zustand eines Prozesses dar, während eine Transition inen Zustandswechsel darstellt.

s ist möglich aus verschiedenen Plätzen über eine Transition in verschiedene ndere Plätze zu gelangen.

p1

0 T

Seite 14 von 29

gen zwischen den Prozessen

Transition

Stelle/ Platz

erichtete Kanten

ng 5-1; Petrinetz ohne

Echtzeitverarbeitung Beschreibung von Echtzeitsystemen

Struktur eines Petrinetzes:

Knotenmengen sind disjunkt – der Durchschnitt aus Stellen und Transitionen ist Null. Knotenmenge enthält mindestens eine Stelle oder eine Transition. 0≠∪ TS

0=∩ TS

)()( TxSSxTF ∪⊆ die Kantenmenge F enthält nur Elemente, die Knoten verschiedener Mengen miteinander verbinden

Isolierte Netze repräsentieren unabhängige nebenläufige Systeme:

s t Abbildung 5-2; Isolierte Netze s und t

Zyklische Netze:

Abbildung 5-4; zyklisches Netz

Abbildung 5-3; zyklisches Netz

Platz: passive Systemkomponente Transition: aktive Systemkomponente Beispiel: Darstellung einer Bestellung

Bestellung Bestellaufnahme Lieferauftrag

Prod-Auftrag Produktion Lager

Auslieferung

Ware

Abbildung 5-5; Petrinetz für die Darstellung einer Bestellung

Verfeinerung von Einzelknoten – meistens Transitionen am Beispiel

Lieferauftrag

Lager

Auslieferung

Lieferschein-erstellung

Lieferschein

Verpackung VerpackteWare

Versenden

Ware

Abbildung 5-6; Verfeinerung der Transition Auslieferung


Echteitverarbeitung Petrinetze

Zusammenfassen von übergeordneten Teilnetzen zu Einzelknoten

Abbildung 5-7; Zusammenfassen von übergeordneten Teilnetzen zu Einzelknoten

5.1.2 Petrinetze mit Marken • werden verwendet zur Beschreibung der dynamischen Eigenschaften eines Systems • Dynamik durch veränderte Markierung der Plätze beschrieben Der Übergang von einer Markierung zur nächsten wird durch Schaltregeln (fire rules) beschrieben. Petrinetze mit Marken heißen Stellen – Transitionsnetze. Marken werden als Punkte in den Plätzen dargestellt. Die Anzahl der Marken ist nicht konstant: Nach dem Feuern wird von jedem Eingangsplatz eine Marke abgezogen und in jedem Ausgangsplatz eine hinzugefügt.

• falls keine Kantenwichtung angegeben ist, fließt beim Schalten von Transitionen über jede Kante genau eine Marke

Abbildung 5-8; Petrinetze mit Marken vor und nach dem Feuern

• fehlende Kapazitätsangabe für Plätze beschreiben ihre unendliche Kapazität

Nichtschaltende Transitionen:

2

3

2

3

Abbildung 5-9; Feuern von Petrinetzen mit Marken und gewichteten Kanten

3

1

Abbildung 5-11; Nichtschaltende Transition2

2

Abbildung 5-10; Nichtschaltende Transition 1



• Das Schalten der Transition erfordert keine Zeit, erfolgt schlagartig. • Im Allgemeinen wird keine Verweildauer für die Marken in Plätzen festgelegt. • Wenn alle Plätze ihre Maximalkapazität erreicht haben, nennt man das Netz todesgefährdet. (Also dann, wenn ein

Zustand erreicht werden kann, in dem keine Transition mehr schalten kann.) • In allen anderen Fällen heißt das Netz lebendig.

Abbildung 5-13; lebendiges Netz

Abbildung 5-12; todesgefährdetes Netz

Sichere und unsichere Netze Ein Netz nennt man dann sicher, wenn eine Erhöhung der Platzkapazitäten nicht zu mehr Schaltmöglichkeiten führt.

n

Abbildung 5-14; ein sicheres Netz

n

1

Abbildung 5-15; unsicheres Netz

5.1.3 Wozu werden Petrinetze benutzt? • Darstellung von Nebenläufigkeiten von Prozessen • Darstellung von Synchronisations- und Kommunikationsmethoden

Darstellung der Nebenläufigkeit von Prozessen im Petrinetz tt11;; ccoonncc tt22 |||| tt33 eenndd ccoonncc;; tt44;; Auf eine Transition t1 folgen parallel t2 und t3, danach t4. Darstellung im Netz wie folgt:

t1

t2

t3

t4

Abbildung 5-16; Nebenläufige Prozesse

Darstellung eines nichtdeterminierbaren Auswahl von Zustandswechseln: tt11;; sseelleecctt tt22||||tt33 eenndd sseelleecctt;; tt44


t1

t2

t3

t4

Abbildung 5-17; nichtdeterministische Auswahl


Beschreibung des wechselseitigen Ausschlusses in Petrinetzen P1: t1; crit k do t2 end crit; t3 P2: t1; crit k do t2 end crit; t3

t1 t4

P1

crit t2 end crit

t1 t4

P1

crit t2 end crit

Abbildung 5-19; Beschreibung von wechselseitigem Ausschluss

t1 t4

P1

crit t2 end crit

t1 t4

P1

crit t2 end crit

Abbildung 5-18; wechselseitiger Ausschluß unter Nutzung einer gemeinsamen Semaphore

einseitige Synchronisation ProzeßA: t1; set b; t2; ProzeßB: t3; await b; t4;

b

Prozeß A

Prozeß B

await b

set b t2t1

t3 t4 Abbildung 5-20; einseitige Synchronisation

zweiseitige Synchronisation Prozess A: t1; set b; await c; t2; Prozess B: t3; set c; await b; t4;

b

Prozeß A

Prozeß B

set bt1

t3 t4

t2await c

await bset c

c

Abbildung 5-21; zweiseitige Synchronisation



Client – Server – Beziehung

A: t1; send a; await f; t2; B: t3; receive a; t4; send f;

Leser – Schreiber – Beziehung

b

Prozeß A

Prozeß B

set bt1

t3 t4

t2await c

await b set c

c

Abbildung 5-22; Client – Server – Beziehung

Leser 1

Un

kritischEintritt

Kritis

ches Lesen

Austritt

Leser 1

Un

kritischEintritt

Kritis

ches Lesen

Austritt

Leser 2

Unkritis

ch

Eintritt

Kritisches

Lesen

Austritt

Leser 3

Unkritisch

Eintritt

Kritis

ches Lesen

Austritt

Unkritisch

Eintritt

Kritisches Lesen

Austritt

Abbildung 5-23; Leser – Schreiber – Beziehung mit drei Lesern



Speisende Philosophen

Philosoph 1

denkt

speist

Philosoph 3

denkt

speist

Philosoph 4

denkt

speist

Philosoph 2

denkt

speist

Philosoph 5

denkt

speist

G

abel 1

G

abel 2

G

abel 3

Gabel 4

G

abel 5

Abbildung 5-24; Die speisenden Philosophen – einzige Verklemmungsmögichkeit: Jeder Philosoph sitzt mit einer Gabel/ Stäbchen da und kann noch nicht essen.

5.1.4 Petri – Netze mit unterscheidbaren Marken – Prädikatstransitionsnetz• Petrinetze mit vielen gleichartigen Abläufen (wie oben) legen nahe, das Petrinetz zu

falten und die gleichartigen Teile dabei übereinanderzulegen Probleme bei der Faltung: • Gabeln werden nicht unterschieden (Die Philosophen können derzeit irgendeine

Gabel nehmen, die evtl. gar nicht neben ihnen liegt) • Auch die Prozesse werden nicht unterschieden. Lösung: Einführung von unterscheidbaren Marken. Bei der Verwendung von unterscheidbaren Marken, müssen auch die Transitionen um Schaltbedingungen und Schaltwirkungen er-weitert werden.

denkt

speist

12 3

4

5i

i

g1, g2

12 3

4

5

Gabel

g1=ig2=i%5+1

Isabel Maine C. Drost

e Philosoph 3

denkt

speist

G

abeln

5

22

i

ig1=ig2=i%5+1

g1, g2n

x

y

z

358

17

142

410

x=2y

z=2x+y

BedinungWirkung

x

y

z

35

817

142

4

10

x=2y

z=2x+y

vor dem Schallten

nach dem Schalten

20

Seite 20 von 29


5.2 Formale Beschreibungen und Zeitdiagramme Beschreibungstechnik muß folgende Aufgaben erfüllen: 1) verteilte Problemstellungen und verteilt operierende Algorithmen bearbeiten 2) Systeme und Algorithmen unter Verwendung von verteilten Berechnungen analysieren 3) Systeme und Verfahren zur Deadlockbehandlung einheitlich darstellen Gesamtfunktionalität eines Echtzeitsystems besteht aus den Teilen : • Basisfunktionalität • Deadlockbehandlung

5.2.1 Ereignisse und Prozesse • sind zentrale Elemente der Beschreibung von Echtzeitsystemen • Funktionalität von Systemen wird durch Ereignisse beschrieben, die von Prozessen zur Laufzeit erzeugt werden. • die räumliche und zeitliche Ausprägung der Gesamtheit der Ereignisse heißt verteilte Berechnung Ereignis: ... ist ein einmaliges Geschehnis, das genau zu einem Zeitpunkt und an einem genau definierten Ort eintritt. Ein Ereignis ist ein Punkt in der RaumZeit. Ereignisse dauern keine Zeit (Dimension 0) Prozeß: ... ist eine sequentielle Folge von Ereignissen, zur grafischen Veranschaulichung von Prozessverläufen werden häufig Zeitdiagramme benutzt. Z.B.: Telefonat:

T t

Hörer abnehmen (1)Nummer wählen(2)

Verbindung aufgebaut(3)

Gespräch beenden (4)Hörer auflegen(5)

Abbildung 5-29; Zeitdiagramm zu einem Telefonat

Ereignisse können formal folgendermaßen beschrieben werden: Ein Prozeß Pi ist beschrieben durch das Tupel (εi, <i) mit der Ereignismenge εi und der lokalen Ordnung <i auf der Ereignismenge. Es gilt e<f (e findet vor f statt) für Ereignisse e, f ει genau dann, wenn e vor f stattfindet. Beispiel dafür anhand des Telefonates: T=(εT, <i) εT={1, 2, 3, 4, 5} <T={(1, 2), (2, 3), (3, 4), (4, 5)} Sind e, f ειEreignisse eines Prozesses Pi und gilt e<f, so ist das von ihnen gebildete Zeitintervall [e, f] (geschlossenes Intervall).

Pi

Pj

t

t

(i:s(M,j)) = Sendeereignis

(j:r(M,i)) = Empfangsereignis Abbildung 5-30; Sende- und Empfangsereignisse

Ereignis = Zustandswechsel Zeitintervall = Prozeßzustand Prozesse laufen in Systemen nicht isoliert ab, sondern haben Wechselwirkungen mit anderen Prozessen. Hierbei wird die Ereignisreihenfolge zweier Prozesse eingeschränkt: • ein Prozess setzt ein Sendeereignis ab (Nachricht),

während ein zweiter Prozess ein Empfangsereignis erhält (Nachrichtenempfang)

Pi

Pj

t

t

(i:s(M,X)) = Sendeereignis

(j:r(M,i)) = EmpfangsereignisPk

t

Plt

(k:r(M,i)) = Empfangsereignis

(l:r(M,i)) = Empfangsereignis Abbildung 5-31; Broadcast von Ereignissen

• werden als korrespondierende Kommunikationsereignisse bezeichnet.


Echteitverarbeitung Formale Beschreibungen und Zeitdiagramme

Prozesssynchronisation am Beispiel des Telefonats:

5PA IEu Ee D B BFr((r( C((( 2 ( (

I

t

t

Nummer wählen

Telefon klingelt

T

U

Hörer abnehmen

Hörer abnehmen

Verbindung aufgebaut

.2.2 Systembeschreibung durch Ereignisse
rozeßsystem mit den Eigenschaften SEQ und X (SEQ ... sequentielle nforderungen, X ... Zugriffe auf die Betriebsmittel sind exklusiv)
m System existieren dann 2 aktive Komponenten: Prozesse = aktive inheiten des Systems; Controller = Komponente zur Steuerung der Prozesse nd Verwaltung der Betriebsmittel.

Prozesse

Controller

Request Reply

Abbildung 5-33; Prozesse und

in Request ist eine Anforderungsnachricht an den Controller, währendessen in Reply die dazugehörige Bewilligung ist.

ie Freigabe des BM erfolg durch ein release:

t

t

Pi

C

start

req(R) req(S)

grant(R) grant(S)

rel(R) rel(S)

Controller eispiel: Kreuzung mit gleichrangigen Straßen:

eschreibung der Aktionen durch Pseudocode: ahrzeug F eq(R) F: s(req(R), C)) F:r(grant(R), C)) // benutzen el(R) F:s(rel(R), C))

ontroller (1. Ansatz) C:r(req(R), F) C:s(grant(R),F)) C:r(rel(R), F) gebe R frei

. Ansatz

C:r(req(R), F) if(free[R]=true then (C:s(grant(R), F)) free[R]=false

C:r(rel(R), F)) free[R]=true

sabel Maine C. Drost

R3 R2

R4 R1

C

F1

R1req(R1) req(R2)

grant(1) grant(2)

fahren rel(R1) rel(R2)

Seite 22 von 29



Die Verklemmung ist nur zu verhindern, indem die Betriebsmittel-vergabe en bloc realisiert wird. (Req(R1, R2, R3). 3. Ansatz für den Controller (mit Warteschlange) (C:r(req(R), F)) if(free[R]) then (C:s(grant(R), F)); free[R]=false else append(waits(R), F) (C:r(rel(R), F)) free[R]=true if(waits(R)!=nil then

(C:s(grant(R), head(waits(R)))) free[R]=false

F1

C

F2

req(R1)Req(R2)

Req(R2)Req(R3) rel(R2), (R3)

rel(R1, R2)

Linksabiegen

F1

C

F2

req(R1)Req(R3)

Req(R3)Req(R4) req(R1)Verklemmung, da beide das BM haben wollen, das derjeweils andere schon hat! Abbildung 5-37; Ein verklemmter Controller

Atomare Ausführung von Aktionsfolgen

F1

C

F2

R1

R2 ... Request wird etwas verzögert,da die Aktionen des Controllers (bestehendaus receive request und send grant atomar sein müssen!)

F1

C

F2

R1

R2

R2

R3R2

Die Bewilligung für ein freiesBM muß sofort erfolgen, genauer: bevor eine neue Anforderungfür deses BM eintrifft

Abbildung 5-38 Atomare Ausführung von Aktionsfolgen

Verteilte Berechnungen:

i

j

k

e1 e2 e3 e4

e5 e6 e7 e8 e9 e10

e11 e12 e13 e14 e15 Abbildung 5-39; Verteilte Berechnungen

Verteilte Berechnung = Tripel(P, ε,<) (P = Prozessmenge, ε=globale Ereignismenge, < = Ordnungsrelation der Ereignisse) εi heißt lokale Ereignismenge des Prozesses i < heißt partielle Ordnung der Ereignismenge mit e<f, wenn gilt:

• e und f sind Ereignisse genau eines Prozesses • oder e ist Sende- und f ist korrespondierendes Empfangsereignis

e und f heißen nebenläufig, falls sie in < nicht geordnet sind: e||f ⋅(e<f) Ν⋅(f<e) andernfalls heißen sie geordnet in <. Beispiel: siehe obiges Bild: 1) Ereignisse eines Prozesses sind vollständig geordnet (z.B.: e1<e2 oder e12<e14) 2) Ereignisse verschiedener Prozesse können geordnet sein, z.B. durch korrespondierende Sende und Empfangsereig-

nisse (z.B.: e5 < e2, e1 < e8) 3) Ereignisse können durch die Transitivität von < geordnet sein (z.B.: e1<e15, e12<e7) 4) In < nicht geordnete Ereignisse sind nebenläufig (z.B.: e1|| e6)

Echteitverarbeitung Echtzeitbetrieb

Kausalität von Ereignissen:

Zwei Ereignisse sind kausal, wenn sie einerseits nacheinander stattfanden, e kann f dann kausal beeinflus-sen. Und andererseits ein Weg vom früheren zum späteren Ereignis exisitert. e vor f sowie es existiert ein Ereignispfad von e nach f. Das Ereignis e kann f kausal beeinflußen, muss aber nich – beachte dazu auch: Nicht jeder, der zur Tatzeit am Tatort gewesen sein könnte, ist automatisch der Täter! Sige

Raum

Zeit

Aktivität Täter

Tat

möglicher Aufenthaltsortdes Verdächtigen

scheidet als Verdächtiger aus Abbildung 5-40; Kausalität am Beispiel eines Verdächtigen

nd e, f ∈ε, so heißt e potentiell kausal abhängig von f nau dann, wenn f<e.

Die Menge der Ereignisse, von denen e potentiell kausal abhängig ist, heißt Vergangenheit von e: Pe={f|f<e} (für

die Menge der Ereignisse gilt: f fand vor e statt und es existiert ein Weg von f zu e. Ein Ereignis f, das stattgefunden haben muss, bevor Ereignis e stattfindet, heißt Voraussetzungsereignis von e: e f (e ∈ε f ∈ε∧f<e) (erster Pfeil : !...: - zu malen) FIFO Eigenschaften von Kommunikationskanälen:

Ein Schnappschuß s einer verteilten Berechnung (P, ε, <) ist eine Teilmenge der globalen Ereignismenge s⊂ε. Ein Schnappschuß heißt dann konsistent, wenn gilt (∀e, f∈ε) (s ∧ f<e)

P

Q

Fifo - Kanal verboten!

Schappschüsse

P

Q

R1

R2

R2

R3 rel(R2, R3)

Momentanschnappschüssedes Prozesssystems, aufgrundtechn. Grenzen können IRLInkonsitenzen auftreten

Abbildung 5-41; Fifo – Eigenschaften und Systemschnappschüsse

Ein Schnappschuß teilt partitioniert die Ereignismenge in solche, die vor und solche, die nach dem Betrachtungszeitpunkt stattfinden. Ein Schnappschuß ist konsitent, falls für jede Empfangsoperation auch die korrespondierende Sendeoperation stattgefunden hat. Beispiel: erster, zweiter und dritter sind konsitent, da keine Kommunikationskanten gekreuzt werden. Die andere ist inkonsitent, da zu dem im Schnappschuss liegenden Empfangsereignis kein zugehöriges Sendeereignis stattgefunden hat.

6 Entwurf von Echtzeitsystemen

6.1 Echtzeitbetrieb • Rechenlage steht über Peripheriegeräte mit der Umwelt in Verbindung • sie muß auf Eingaben aus der Umwelt innerhalb einer vorgegebenen Frist mit Ausgaben reagieren • Korektheit des Echtzeitsystems schwer nachzuweisen, da Anforderungszeitpunkte zufällig sind, daher häufig

Worst-Case – Analyse angewendet • Nachteil dieser Analysemethode: Häufigkeit, evtl. Zeitpunkt und Dauer der eintreffenden Ereignisse müssen

bekannt sein.


Echtzeitverarbeitung Entwurf von Echtzeitsystemen

• jedoch Dauer ist oft programmiersprachen-/übersetzungsabhängig max 30-50% Auslastung, Lastspitzen werden

aufgefangen Multitaskingsystem/ Multiusersysteme sind „Grundlastkraftwerke“

6.2 Zeitbedingungen • Unterscheidung der Echtzeitsysteme nach zu erfüllenden Zeitbedingungen: Harte Zeitbedingungen: stehen präzise fest, Übertretungen können wirtschaftliche Verluste oder Personenschäden nach sich ziehen. (Bsp.: Industrierobotersteuerung) Weiche Zeitbedinungen: sind nicht genau festgelegt, Übertretungen verursachen zwar Störungen, jedoch wird das Betriebsziel, wenn auch evtl. mit Verspätung, noch erreicht. (z.B. Flugbuchung mit mehrfach vergebenen Plätzen) In der Prozeßdatenverarbeitung vorwiegend harte Zeitbedingungen: Umgebung = techn. Prozeß, Rechenanlage = Prozeßrechner. Im Prozeßrechner befindet sich ein Modell des techn. Prozesses: relevate Größen eines techn. Prozesses heißen Prozeß-größen, während die aktuellen Werte als Prozeßdaten bezeichnet werden. Bei der Zeitanalyse in Echtzeitsystemen muß die benötigte Rechenzeit mit der maximalen Antwortzeit verglichen werden.

Materialtechn. Prozeß

EnergieProdukt

Prozeß-rechner

MeßwerteMeßwerte Steuersig.

Aufgaben des Prozeßrechners:Überwachen (blau)Steuern (rot)Regeln (rot und blau)

Abbildung 6-1; Zusammenspiel von Prozeßrechner und techn. Prozeß

Beispiel: Meßwerterfassung mit definierter Abtastrate Anmerkung: im System existiert als größte relevante Frequenz fmax Shannon-Theorem: Abtastfrequenz fs >= 2fmax; Praktisch: fs=5 ... 10 * fmax zyklische Ausführung folgender Aktivitäten: A1´... Messung der Temperatur mit Zykluszeit T1 A2 ... Messung des Drucks mit Zykluszeit T2 A3 ... Abfrage der Schalterstellung mit Zykluszeit T3

tT1 T2 T35T14T1

3T12T1

A1A1A1 A2A1 A2 A3A1A2 A3 A1T1:T2:T3 = 1:2:4 Aktionen A haben gleiche Dauer aber unterschiedliche Häufigkeit: Spitzenlast im Intervall: [4kT1, (4k+1)T1] k aus N Prozeßdaten häufig durch Unterbrechungsbehandlung eingegeen und daraus Ausgabewerte abgeleitet. Prozeßrechner reagiert mit Verzögerung.

Unterbrechungswerk(z.B. E/A-Kanal, Bus,PIC, ...)

ProzessorHW

SW

T1 T2

t1 t2 t3 t4 t5 t6

t1 … Unterbrechungssignal kommt im Unterbrechungswerk ant2 … Unterbrechungssignal zum Prozessor gemeldett3 … laufender Prozeß wird unterbrochent4 … Unterbrechungsbehandlung beginnt

T3

T4

T5

lfd. Prozeß

Abbildung 6-2; Unterbrechungsbehandlung

• T1 ... Durchlaßzeit • T2 ... Latenzzeit • T3 ... Erkennungszeit • T4 ... Ausführungszeit • T5 ... Rückkehrzeit T1+T2+T3 ... Reaktionszeit T1+T2+T3+T4 ... Antwortzeit T3+T4+T5 ... Unterbrechungszeit


Echteitverarbeitung Zeitgerechte Einplanung


6.3 Zeitgerechte Einplanung

tA tS tetz

Laufzeit

t0

Restlaufzeit (l(t0))

Spielraum s(t0)

Restantwortzeit a(t0)

Abbildung 6-3; Zeitgerechte Einplanung – Gant-Diagramm

Es müssen hier bekannt sein: - frühester Startzeitpunkt tA - tatsächlicher Startzeitpunkt ts (ts>=ta) - spätester Endzeitpunkt tz - tatsächlicher Endzeitpunkt tE (tE<=tz) - häufig statt tz Restantwortzeit a(t) angegeben: a(t) = tz – t - Restlaufzeit l(t) gibt die Zeitdauer bis zur Beendigung der

Aktionen an: für t<ts gilt: l(t)=L (L ... Laufzeit der Aktion) - Spielraum s(t) ist die Differenz von Antwortzeit und

Laufzeit der Aktion s(t)=a(t) – l(t)

6.3.1 Planung für Einprozessorsysteme • bei Einplanung von Prozessen (Aktionen), bei der alle

vor ihrem spätesten Endzeitpunkt tz beendet sind, heißt zeitgerecht (timely)

• gesucht ist ein Algorithmus, für die zeitgerechte Einplanung

Prinzipielle Planungsverfahren:

1) Einplanung nach Vorabprioritäten 2) Einplanung nach Antwortzeiten (relativ aufwendig)

3) Einplanung nach Spielraum (am günstigsten:

Berücksichtigung der Restlaufzeit)

Laufzeit von P1

P2

P3

Einzuplanende Prozesse

spätester Endzeitpunkt

P2P3

Einplanung nach Antwortzeit

Spielraum

P2 P3

Bei 2 und 3 müssen à priori Laufzeit, Startzeit und Endzeit jedes Prozesses bekannt sein. Spontane Anforderungen aus technischem Prozeß werden nicht abgedeckt. Aus diesem Grund wird meist 1. eingesetzt (damit steuerbar, dass systemrelevante Funktionen garantiert sind.

6.3.2 Planung für Meterprozessorsysteme

Laufzeit von P1

P2

P3


spätester Endzeitpunkt

P2

P3

Einplanung nach Antwortzeit

Spielraum

P2 P3

Prozessor 1

Prozessor 2

Prozessor 1

Prozessor 2

Antwortzeitverletzung

Zeitgerechte Einplanung



P2

P3


Spielraum

Prozessor 1

Prozessor 2

P5

P6

P7

P2 P5 P6

P7

P2

P1

P3

P4

P5

P6

P7

P2

Keine Antwortzeitverletzung, da der Prozess 2 auf beideProzessoren verteilt wird.

Abbildung 6-5; zeitgerechte nicht-algorithmische Lösung

P2

P3


Spielraum

Prozessor 1

Prozessor 2

P5

P6

P7

P2

P3

P5

P3

P6

P7

P2

P1

P3

P4

P5

P6

P7

Antwortzeitverletzung

Abbildung 6-4; nicht zeitgerechte algorithmische Lösung: Verteilung von 7 Prozessen auf zwei Prozessoren

6.3.3 Zeitangaben in Programmen • Vorgabe der Zeiten:

a) absolut (z.B.: „um 8.30“) b) relativ (z.B.: „in 15 min“ oder „alle 15 min“)

• Programmiersprache PEARL bietet hier die besten Möglichkeiten Besitzt zwei elementare Datentypen: DURATION (Zeitdauer), CLOCK (absoluter Zeitpunkt) Beispielinitialisierungen:

DCL messdauer DURATION INIT (2HRS, 25MIN, 32.5SEC); prodbeginn CLOCK INT(6 :30 :32.6) ;

• werden zur zeitgerechten Einplanung verwendet (z.B. Prozeßstart, -fortsetzung, -verzögerung, -beendigung) • verschiedene Einplanungen:

zeittaktbezogene relative Zeit für Steuerbarkeit (evtl. Periodendauer bei zyklischer Einplanung), z.B.: AFTER D1 ALL D2 DURING D3 [zu erledigende Aktivität] D1 ... D3 sind hier vom Typ Duration

AFTER 10 SEC ALL 5 MIN DURING 3 HRS [Aktivität, die in 10 Sekunden alle 5 min 3h lang auszuführen]

Systemzeitbezogene Einplanungen absoluter Zeitpunkt der Steueraktivität, z.B.: AT C1 EVERY D UNTIL C2 [Aktivität];

D vom Typ DURATION; C1, C2 vom Typ CLOCK) AT 8:30:00 EVERY 5 MIN UNTIL 10:00:00 ACTIVATE P1;

• in Ada existiert lediglich die Selbstverzögerung eines Prozesses, z.B.: delay 20; // Prozeß verzögert sich um 2 Sekunden

• unter Verwendung der Absolutzeit (Bibliothekseinheit CALENDAR) sind beliebige Einplanungen nachzubilden

Echteitverarbeitung Zeitgerechte Einplanung



Abbildung 2-1; Ein System in seiner Umwelt .....................................................................................................................6 Abbildung 2-2; Visualisierung der Prozessarten ...............................................................................................................6 Abbildung 3-1; Beispiel für einen binären Semaphor ........................................................................................................8 Abbildung 3-2; Visualisierung der atomaren Funktion p...................................................................................................8 Abbildung 3-3; Visualisierung der atomaren Funktion v...................................................................................................8 Abbildung 4-1; MRT86 Prozessmodell.............................................................................................................................10 Abbildung 5-1; Betriebsmittelverwaltung - Stapelbetrieb ................................................................................................12 Abbildung 5-2; Betriebsmittelverwaltung – Vollständige Bearbeitung in Prioritätsreihenfolge .....................................12 Abbildung 5-3; Betriebsmittelverwaltung – Prozeßumschaltung bei Warten auf BM......................................................12 Abbildung 5-4; Betriebsmittelverwaltung - Prozeßverdrängung .....................................................................................12 Abbildung 5-5; Speicherorganisation beim MRT86.........................................................................................................13 Abbildung 5-6; Zeitgeberverwaltung ...............................................................................................................................14 Abbildung 6-1; Petrinetz ohne Marke ..............................................................................................................................14 Abbildung 6-2; Isolierte Netze s und t ..............................................................................................................................15 Abbildung 6-3; zyklisches Netz.........................................................................................................................................15 Abbildung 6-4; zyklisches Netz.........................................................................................................................................15 Abbildung 6-5; Petrinetz für die Darstellung einer Bestellung........................................................................................15 Abbildung 6-6; Verfeinerung der Transition Auslieferung...............................................................................................15 Abbildung 6-7; Zusammenfassen von übergeordneten Teilnetzen zu Einzelknoten .........................................................16 Abbildung 6-8; Petrinetze mit Marken vor und nach dem Feuern ...................................................................................16 Abbildung 6-9; Feuern von Petrinetzen mit Marken und gewichteten Kanten.................................................................16 Abbildung 6-10; Nichtschaltende Transition 1 ................................................................................................................16 Abbildung 6-11; Nichtschaltende Transition2 .................................................................................................................16 Abbildung 6-12; todesgefährdetes Netz............................................................................................................................17 Abbildung 6-13; lebendiges Netz......................................................................................................................................17 Abbildung 6-14; ein sicheres Netz....................................................................................................................................17 Abbildung 6-15; unsicheres Netz......................................................................................................................................17 Abbildung 6-16; Nebenläufige Prozesse ..........................................................................................................................17 Abbildung 6-17; nichtdeterministische Auswahl ..............................................................................................................17 Abbildung 6-18; wechselseitiger Ausschluß unter Nutzung einer gemeinsamen Semaphore...........................................18 Abbildung 6-19; Beschreibung von wechselseitigem Ausschluss.....................................................................................18 Abbildung 6-20; einseitige Synchronisation.....................................................................................................................18 Abbildung 6-21; zweiseitige Synchronisation ..................................................................................................................18 Abbildung 6-22; Client – Server – Beziehung ..................................................................................................................19 Abbildung 6-23; Leser – Schreiber – Beziehung mit drei Lesern.....................................................................................19 Abbildung 6-24; Die speisenden Philosophen – einzige Verklemmungsmögichkeit: Jeder Philosoph sitzt mit einer Gabel/ Stäbchen da und kann noch nicht essen................................................................................................................20 Einseitige Synchronisation in C .........................................................................................................................................8 Zweiseitige Synchronisation und wechselseitiger Ausschluß .............................................................................................9


Documents

Echtzeitverarbeitung - Isabel Drost-Frommisabel-drost.de/bin/Echtzeitverarbeitung.pdfSemaphoren sind häufig binär (z.B. µP – INT – FF), manchmal aber auch mehrwertig (Wertevorat