Prozessautomatisierungstechnik - uni-due.de · • Synchrone Programmierung ist ungeeignet für die Reaktion auf zeitlich nicht vorhersehbare (asynchrone) Ereignisse, z.B. Alarmsignal

WS 2013/14 Vorlesung: Prozessautomatisierung,· Prof. Dr.-Ing. Mohieddine Jelali 1

Mohieddine Jelali

Prozessautomatisierungstechnik

4. Echtzeitsysteme und Echtzeitprogrammierung


Inhaltsangaben zu Kapitel 4

Echtzeitsysteme und Echtzeitprogrammierung

4.1 Echtzeitsysteme

4.2 Aufgaben von Echtzeitsystemen

4.3 Echtzeitsysteme – Beispiele

4.4 Anforderungen an Echtzeitsysteme

4.5 Echtzeit-Programmierverfahren

4.6 Synchronisierung von Tasks

4.7 Synchronisierungsverfahren

4.8 Scheduling-Verfahren


4.1 Echtzeitsysteme

Automatisierung mit Echtzeitanforderungen

Automatisierungssystem

Technisches System (Produkt oder Anlage)

Schnittstelle (Kommunikation)

Schnittstelle (Aktorik)

Schnittstelle (Sensorik)

Zeitabhängige Ausgangsdaten

Zeitabhängige Eingangsdaten

Ech

tzeit

bezu

g


Echtzeitsteuerung (Real Time Control)

Bei der Datenverarbeitung in Echtzeitsystemen muss die Erfassung,

Verarbeitung und Ausgabe von (gültigen, fehlerfreien) Daten zu bestimmten,

durch das System und seinen Zustand vorgegebenen Zeitpunkten

(oder innerhalb bestimmter Zeitintervalle) erfolgen.

Das Ergebnis ist nur dann fehlerfrei, wenn es inhaltlich und zeitlich den

gestellten Anforderungen entspricht.

Echtzeitanforderungen

- Harte Anforderungen: verspätete Reaktion einer Komponente führt zum

Systemausfall, zu Schadensfällen oder zu Katastrophen.

- Weiche Anforderungen: Überschreitungen von Zeitlimits können

ausnahmsweise toleriert werden, ohne dass der technische Prozess in

gefährliche oder fatale Systemzustände übergeht.

Nichteinhaltung von vorgegebenen Reaktionszeiten führt zu ansteigenden Kosten

4.1 Echtzeitsysteme


Komponenten eines Echtzeit-Steuerungssystems

Anwendung

Regel- und Steuerprogramm

Bedienung und Visualisierung

Echtzeit-Betriebssystem, Run-Time-System, Run-Time-Umgebung

Hardware

Schnittstelle Timer

Prozessperipherie Bus

Verarbeitungs- und Steuerungsalgorithmen

Mensch-Maschine-Schnittstelle (HMI: Human Machine Interface)

Programm zur Verwaltung der Rechenprozesse und Betriebmittel in Echtzeit

An

wen

du

ng

s-

so

ftw

are

Betr

ieb

s-

so

ftw

are

Hard

ware

4.1 Echtzeitsysteme


Aufgaben des Timer

- zyklische Interruptgenerierung zur Realisierung von zeitabhängigen

Systemdienste („Weckrufe“)

- Zeitmessung, z.B. zur Ermittlung von Geschwindigkeiten

- Watchdog-Funktionen, z.B. zur Zeitüberwachung in kritischen Prozessen

- Zeitsteuerung für periodische Dienste, z.B. Messwertübertragung

Anforderungen bei Echtzeitprogrammierung

- Rechtzeitigkeit: Reaktion zur richtigen Zeit

- Gleichzeitigkeit: gleichzeitige Reaktion auf mehrere Dinge

- Verlässlichkeit: Zuverlässigkeit, Sicherheit, Verfügbarkeit

- Vorhersehbarkeit: Planbarkeit und Determiniertheit aller Reaktionen

4.1 Echtzeitsysteme



Hauptfunktion

Steuerung und Überwachung von quasi-parallelen Teilprogrammen bei

vorgegebenen Zeitbedingungen unter Berücksichtigung von Nebenbedingungen,

wie z.B. der Prozesspriorität

Allgemeine Organisationsaufgaben

- Laden und Starten von Anwendungsprogrammen

- Organisation von Schnittstellen-Operationen (Ein- und Ausgabe,

Datentransport)

- Speichermanagement

- Klassifizierung von Fehlern und Handhabung von Ausnahmezuständen

(Neuanlauf nach Stromausfall, Alarmfunktionen usw.)


Koordinierungssaufgaben

- Entscheidung der Reihenfolge der Abarbeitung von Teilprogrammen

- Gegenseitiger Ausschluss zweier oder mehrerer Tasks, um zu verhindern,

dass mehrere Prozesse auf die gleichen Resourcen zugreifen.

- Zuordnung der Tasks zu den Prozessoren bei Multiprozessorsystemen

- Verwaltung der Systemprozesse

- Verwaltung von Interrupts



Verwaltung von Interrupts

- Unterbrechung des geplanten Programmablaufs

- Anstoß einer Behandlungsroutine

- Priorisierung von Interrupts

- Hardwarefunktionen für die Interrupt-Behandlung

Steuerungsprogramm

t

Steuerungsprogramm Steuerungsprogramm

ISR 1 Interrupt Service Routine

Ste

igende

Pri

o.

Interrupt 1

Geplanter Programmablauf (ohne Interrupt):

Tatsächlicher Programmablauf (mit Interrupt):

t



Speicherverwaltung

- Optimale Ausnutzung der “schnellen” Speicher

- Koordinierung des gemeinsamen Zugriffs auf einen Speicherbereich

- Schutz des Speicherbereichs verschiedener Rechenprozesse gegen

Fehlzugriffe

- Zuweisung von physikalischen Speicheradressen für die logischen Namen in

Anwenderprogrammen

Ein-/Ausgabesteuerung

- Hardwareunabhängige Ebene für die Datenverwaltung und den

Datentransport

- Hardwareabhängige Ebene, die alle gerätespezifischen Eigenschaften

berücksichtigt (Treiber-Programme).



Klassifikation und Behandlung von Fehlern und irregulärer

Betriebszustände

- fehlerhafte Benutzereingaben

- fehlerhafte Anwenderprogramme

- Hardwarefehler/-ausfälle

• Erkennung von Hardwarefehlern bzw. –ausfällen

• Rekonfigurierung ohne die fehlerhaften Teile

• Abschaltsequenzen bei Stromausfällen

- Deadlocks (Verklemmungen) aufgrund dynamischer Konstellationen



4.3 Echtzeitsysteme - Beispiele

Übersichtsdiagramm für ein Mini-Betriebssystem

Zeit

Zyklus Zeit- zähler

Deakti- vierung

Akti- vierung

Suche

Rechenpro

zesscode

Interrupt 1

Interrupt 2

Interrupt k

Uhrimpuls-interrupt

Exte

rne I

nte

rrupts

Unter- brechungs- verwaltung

Zeit- verwaltung

Task- verwaltung

Prozessor- verwaltung

Verwal- tungs- block


Aktuelle Beispiele für Echtzeitbetriebssysteme

- QNX: kommerzielles Unix-ähnliches Betriebssystem speziell für eingebettete

Systeme (Embedded systems); POSIX-konform (Portable operating system

interface for Unix)

- OS9: relativ stark verbreitet in Steuerungssystemen, ursprünglich für den

8-Bit-Prozessor 6809 von Motorola entwickelt.

- VxWorks (wurde bei der Pathfinder-Mission zum Mars eingesetzt)

- RTLinux: Erweiterung von Linux für Echtzeitanforderungen

- Windows CE: sehr kleines Echtzeitbetriebssystem, das auf vielen

Pocket-PCs läuft.




Auswahl kommerzieller Echtzeit-Betriebssysteme



Auswahl kommerzieller Echtzeit-Betriebssysteme



Nicht-Echtzeit-Datenverarbeitung

Echtzeit-Datenverarbeitung

Zeitabhängige Eingangsdaten

Automatisierungs- system

Technischer Prozess

Daten- Verarbeitung

Zeitabhängige Ausgangsdaten

Eingangsdaten Ausgangsdaten

Daten- Verarbeitung

Eingangsdaten Ausgangsdaten

Zeit Zeit Zeit


Forderung nach Rechtzeitigkeit - unterschiedliche Fälle

Ausführung eines Programms zu bestimmten Zeitpunkten ti

Ausführung eines Programms zu bestimmten Zeitpunkten ti unter Zulassung von Toleranzintervallen

Ausführung eines Programms bis spätestens zu einem bestimmten Zeitpunkt ti

Ausführung eines Programms frühestens ab einem bestimmten Zeitpunkt ti


t

1

0 t1 t2 t3 t4

t

1

0 t1 t2

Toleranz- bereich

t

1

0 ti

1

0 ti t


Forderung nach Gleichzeitigkeit

- Vorgänge in Umwelt laufen gleichzeitig ab

• “gleichzeitige” Reaktion der Echtzeit-Systeme erforderlich

• Gleichzeitige Durchführung von mehreren Datenverarbeitungsaufgaben

- Beispiele:

• Reaktion auf gleichzeitige Fahrt mehrerer Züge

• Verarbeitung mehrerer gleichzeitig anfallender Messwerte bei einer

Heizungsregelung

• Motorsteuerung und ABS-System gleichzeitig

- Realisierung der Gleichzeitigkeit:

• Ideal: Getrennter Rechner für jede Datenverarbeitungsaufgabe

echt parallel

• Praxis: Einen Rechner führt alle Datenverarbeitungsaufgaben durch.

quasi-gleichzeitig / quasi-parallel



Forderung nach Vorhersagbarkeit/Determiniertheit

- Determiniertheit:

• Eindeutige Bestimmbarkeit der Menge von Ausgangsinformationen und

des nächsten Zustandes für jeden möglichen Zustand und für jede Menge

an Eingangsinformationen

• Voraussetzung: endliche Menge von Systemzuständen; bei digitalen

Rechnersystemen immer gegeben.

- Zeitliche Determiniertheit:

Antwortzeit für jede Menge von Ausgangsinformationen bekannt!

- Determiniertheit als elementar wichtige Eigenschaft für harte Echtzeitsysteme:

• Voraussetzung für Garantie der Sicherheit bei sicherheitskritischen

Systemen

• Geringste zeitliche Verschiebungen können zu vollkommen

unterschiedlichen Abläufen führen.




Synchrone Programmierung

- Prinzip:

Planung des zeitlichen Ablaufs vor der Ausführung der Programme

- Vorgehensweise:

• Teilprogramme werden zyklisch abgearbeitet.

• Zyklischer Ablauf wird mit Hilfe einer Echtzeituhr über ein vorgegebenes

Zeitraster synchronisiert. (Zeittriggerung)

• Reihenfolge der Teilprogramme wird vorher festgelegt.



- Beispiel:

Heizungsregelung;

Aufgabenstellung


T3 = 5T

Teilstrecke 1 „Heizkreis Wohnung“

Teilstrecke 2 „Heizkreis Büro“

Teilstrecke 3 „Heizkessel“

REGLER 3

REGLER 2

REGLER 1

AD

U

y1(t)

y2(t)

y3(t)

u1(t)

u2(t)

u3(t)

DAU

Bedien- terminal

Echtzeit- Uhr

Vorlauf-temperatur

Raum-temperatur Büro

Raum-temperatur Wohnung

T3 = 2T

T3 = T

Automatisierungsrechner



- Beispiel:

Heizungsregelung;

Grobentwurf des

Steuerungsprogramms


ANFANG

Interruptsignale von der Echtzeit-Uhr mit der Zykluszeit T

Alle T1 = T REGLER 1 aufrufen

Alle T2 = 2T REGLER 2 aufrufen

Alle T3 = 5T REGLER 3 aufrufen

Warteschleife



- Beispiel:

Heizungsregelung; Feinentwurf des

Steuerungsprogramms


ANFANG

Definition der Zählvariablen Z2 und Z3

Warteschleife

Z2:=1 Z3:=1

REGLER1 abarbeiten

REGLER2 abarbeiten

REGLER3 abarbeiten

Z3:=5?

Z3:=1

Z2:=2?

Z2=1

Im Zeitabstand T aufeinanderfolgende Interruptsignale bewirken Start an dieser Stelle

Z3:=Z3+1

Z2:=Z2+1

ja

ja

nein

nein

Z2 und Z3 initialisieren


ca. 5T

T 2T

1T 2T 3T 4T 5T 6T 7T 8T 9T 10T 11T


- Beispiel:

Heizungsregelung;

Zeitlicher Ablauf der

Teilprogramme

Annahmen: - Rechenzeit für Teilprogramme gleich groß - Summe der Rechenzeiten der drei Teilprogramme kleiner als Zykluszeit


t

REGLER3

REGLER2

REGLER1

Steuerprogramm



- Eigenschaften:

• Forderung nach Rechtzeitigkeit wird nur näherungsweise erfüllt.

• Forderung nach Gleichzeitigkeit wird erfüllt, wenn Zykluszeiten der

Regelstrecken groß sind gegenüber den Rechenzeiten der Teilprogramme.

• Synchrone Programmierung ist gut für Echtzeit-Systeme mit

zyklischen Programmabläufen.

• Synchrone Programmierung ist ungeeignet für die Reaktion auf zeitlich

nicht vorhersehbare (asynchrone) Ereignisse, z.B. Alarmsignal

„Brennerstörung“ im Bespiel der Heizungsregelung.

Erhöhung der Rechenzeit durch ständiges Abfragen,

Verzögerung der Reaktion

• Gesamte Programmstruktur muss geändert werden, wenn die

Aufgabenstellung geändert wird.

Steuerprogramm ist unflexibel.



Asynchrone Programmierung/Parallelprogrammierung

- Prinzip:

Organisation des zeitlichen Ablaufs während der Ausführung der Programme

- Vorgehensweise:

• Aufruf der Teilprogramme erfolgt nach Zeitbedingungen und Anforderungen

aus dem Prozess.

• Konfliktsituation wird durch bestimmte Strategie (Scheduling-Strategie)

gelöst.

- Typische Scheduling-Strategie:

• Vergabe von Prioritäten

• Priorität umso höher, je niedriger die Prioritätsnummer




- Beispiel:

Heizungsregelung;

Aufgabenstellung


T3 = 5T

Teilstrecke 1 „Heizkreis Wohnung“

Teilstrecke 2 „Heizkreis Büro“

Teilstrecke 3 „Heizkessel“

REGLER 3

REGLER 2

REGLER 1

AD

U

y1(t)

y2(t)

y3(t)

u1(t)

u2(t)

u3(t)

DAU

Bedien- terminal

Echtzeit- Uhr

Vorlauf-temperatur

Raum-temperatur Büro

Raum-temperatur Wohnung

T3 = 2T

T3 = T

Automatisierungsrechner

Brenner

Alarm Brenner-störung



- Beispiel:

Heizungsregelung: Zuordnung von Prioritäten


Teilprogramm Bezeichner Abtastzeit Prioritäts-nummer

Priorität

Reaktion auf Brennerstörung mit Alarmmeldung

ALARM - 1 höchste

Temperatur-Regler 1 für „Heizkreis Wohnung“

REGLER1 T1 = T 2 zweithöchste

Temperatur-Regler 2 für „Heizkreis Büro“

REGLER2 T2 = 2T 3 dritthöchste

Temperatur-Regler 3 für „Heizkessel“

REGLER3 T3 = 5T 4 niedrigste



- Beispiel:

Heizungsregelung: Zeitlicher Verlauf der Teilprogramme


REGLER3 (Priorität 4) REGLER2

(Priorität 3)

REGLER1 (Priorität 2)

ALARM (Priorität 1)

REGLER3

REGLER2

REGLER1

ALARM

Betriebssystem



- Eigenschaften:

• Forderung nach Rechtzeitigkeit wird nur näherungsweise erfüllt;

Je höher die Priorität ist, desto besser wird die Anforderung erfüllt.

• Ist-Zeitablauf kann sich gegenüber Soll-Zeitablauf stark verschieben,

dass sich Teilprogramme gegenseitig überholen können.

• Aufeinanderfolge der Teilprogramme ist nicht determiniert; Sie kann durch

sporadisch auftretende Ereignisse dynamisch beeinflusst werden.

• Bei Programmerstellung lässt sich nicht im Voraus angeben, welches

Teilprogramm zu welchem Zeitpunkt ablaufen wird.

einfache Entwicklung,

Komplexität im Verwaltungsprogramm,

Programmablauf schwer durchschaubar



Rechenprozess = Task

ein von einem Echtzeit-Betriebssystem gesteuerter Vorgang der Abarbeitung

eines sequenziellen Programms


Grundzustände von Tasks

- „ablaufend (running)“:

• Teilprogramm ist in Bearbeitung.

- „bereit/ablaufwillig (runnable)“:

• alle Zeitbedingungen für den Ablauf sind erfüllt.

• Es fehlt der Start durch das Betriebssystem.

- „blockiert (suspended)“:

• Rechenprozess wartet auf den Eintritt eines Ereignisses

• Wenn das Ereignis eingetreten ist, Übergang aus dem Zustand “blockiert”

in den Zustand “bereit”.

- „ruhend (dormant)“:

• Rechenprozess ist nicht ablaufbereit, weil Zeitbedingungen oder sonstige

Voraussetzungen nicht erfüllt sind.


Zustandsdiagramm einer Task

Einplanung bedeutet:

- die Beauftragung eines Rechenprozesses

zyklisch oder zu bestimmten Zeiten

- der Übergang vom Zustand “ruhend” in den

Zustand “bereit”


ruhend

blockiert bereit

laufend

Vereinbarung der Task

Löschen der Task

Einplanung


t

Beispiel zum Zustandsverlauf

Task REGLER3 bei der Heizungsregelung

REGLER 1/2 (höhere Prio.) läuft ab.


Task REGLER3 ist:

ablaufend (aktiv)

blockiert ablaufwillig (bereit) ruhend

0 T 2T 3T 4T 5T 6T 7T


Prioritätsvergabe für Tasks

- statische Prioritätsvergabe

- dynamische Prioritätsvergabe (z.B. durch Verwendung von Deadlines)

Zeitparameter einer Task

A: Arrival time (Ankunftszeitpunkt)

R: Request time (Einplanungszeitpunkt)

S: Start time (Startzeit, Zuteilung eines Betriebsmittels)

C: Completion time (Beendigungszeitpunkt)

D: Deadline (Maximalzeit)

E: Execution time (maximale Ausführungsdauer)

P: Period time (maximale Antwortzeit)

L: Laxity (Spielraum)

F(t): Flow time (Antwortzeit)

RF(t): Remaining flow time (Restantwortzeit)



Auftreten der Zeitparameter einer Task

A R S C E D E

E(t) = Ealt(t) + Eneu(t)

L = D S E

A: Arrival time

R: Request time

S: Start time

C: Completion time

D: Deadline

L: Laxity


t

Antwortzeit F(t) Restantwortzeit RF(t)

Maximale Antwortzeitdauer P

Spielraum L Maximale

Ausführungsdauer E

Ealt(t) Eneu(t)

Task-

zustände

„laufend“

„blockiert“

„bereit“

„ruhend“

A R S C D Betrachtungs-

zeitpunkt



Begriffe

- Synchronisierung: zeitliche Koordinierung

- Zwei Aktionen (Threads) in Tasks heißen parallel, wenn sie gleichzeitig

ablaufen können.

- Zwei Aktionen heißen sequenziell, wenn sie in einer bestimmten Reihenfolge

angeordnet sind.

- Zwei Aktionen aus zwei verschiedenen Tasks heißen nebenläufig, wenn sie

gleichzeitig ablaufen können (äußere Parallelität).

- Zwei Aktionen einer Task heißen simultan, wenn sie gleichzeitig ausgeführt

werden können (innere Parallelität).

Abhängigkeiten zwischen Tasks

- Logische Abhängigkeiten aufgrund der Vorgänge im technischen Prozess

- Abhängigkeiten durch die gemeinsame Benutzung von Betriebsmitteln (d.h.

Geräten oder Programmen)



Beispiel zur Abhängigkeit von Tasks

- Tasks 1 und 2 benutzen gemeinsam die Betriebsmittel Protokolldrucker und

Analog-Eingabe. Task 1: Messwert- erfassung

Task 2: Prozess-

überwachung

Treiberprogramm für Protokoll-

drucker belegen

Störungsmeldung an Protokoll-

drucker ausgeben

Prozessgrößen einlesen und überwachen

Analog- Eingabe belegen

Analog- Eingabe belegen

Betriebsmess- werte einlesen

und umrechnen

Ausdruck Betriebsmesswerte

und Uhrzeit

Treiberprogramm für Protokoll-

drucker belegen

Verklemmung (Deadlock)


Logische (aufgaben-/oder prozessorientierte) Synchronisierung

- Anpassung des Ablaufs der Rechenprozesse an den Ablauf der Vorgänge im

technischen Prozess

- Synchronisierung bedeutet:

Erfüllung von Anforderungen bezüglich der Reihenfolge von Aktionen

Berücksichtigung vorgegebener Zeitpunkte bzw. Zeitabstände

Reaktionen auf Unterbrechungsmeldungen aus dem technischen Prozess

Betriebsmittelorientierte Synchronisierung

Einhaltung von Bedingungen bezüglich der Verwendung gemeinsam benutzter

Betriebsmittel (Ressourcen)




Grundgedanke der Synchronisierung

- Rechenprozess muss warten, bis ein bestimmtes Signal bzw. Ereignis eintrifft.

- Einfügen von Wartebedingungen an den kritischen Stellen

Verfahren

- Semaphorkonzept

- kritische Regionen

- Rendez-Vous-Konzept


Semaphorkonzept

- Synchronisierung von Rechenprozessen durch Signale (nach Dijkstra)

- Einführung von zwei Semaphor-Variablen:

V(S) und P(S) (positive, ganzzahlige Werte)

V(Si): Verlassen-Operation:

Si Si + 1; Task wird fortgesetzt.

P(Si): Passieren-Operation:

Si wird abgefragt:

Si > 0: Si Si 1; Task wird fortgesetzt.

Si = 0: Si bleibt unverändert; Task geht in den Zustand „blockiert“ über.

Ein Verlassen dieses Zustandes ist nur möglich, wenn diese

Semaphor-Variable Si in einer anderen Task inkrementiert wird.



Semaphorkonzept

- Beispiel 1:

Zugverkehr über eine

eingleisige Strecke

P(S1) P(S2)

V(S2) V(S1)

Gleismagnet Gleismagnet

Gleismagnet Gleismagnet

Signal S2 Signal S1

Fahrt

richtu

ng

der

Züge

Anfangsbedingungen: S1 = 1 („grün“) S2 = 0 („rot“)

Ablaufreihenfolge: ABAB…



Semaphorkonzept

- Beispiel 2:

Zwei Rechenprozesse

A und B sollen stets

abwechselnd laufen.

Logische Synchronisierung


t t

S1 = 1 S2 = 0

S1 = 0

S2 = 1

P(S1)

V(S2)

S2 = 0

S1 = 1

P(S2)

V(S1)

S1 = 0

S2 = 1

P(S1)

V(S2)

S2 = 0 P(S2)

Task A

Task B


Kommunikation zwischen Tasks

Kommunikation: Austausch von Daten zwischen parallel ablaufenden Tasks

Möglichkeiten der Datenkommunikation

- Direkter Datenaustausch (Rendez-vous)

- Gemeinsam benutzter Speicher (Shared memory)

gemeinsame Variable

gemeinsame komplexe Datenstruktur

- Versenden von Nachrichten (Messages)

Übertragung von Nachrichten von einem Rechenprozessor zu einem anderen

(Message passing)

vor allem bei verteilten Systemen

Arten der Kommunikation

- Synchron: sendende und empfangende Task kommunizieren an einer

definierten Stelle im Programmablauf.

- Asynchron: Daten werden gepuffert.



Begriffe

- Scheduling (Planung): Vergabe des Prozessors an ablaufbereite

Rechenprozesse nach einem festgelegten Algorithmus (Scheduling-Verfahren)

- Scheduler (Planer): Teil eines Echtzeit-Betriebssystems zur Zuteilung des

Prozessors

- Schedule (Plan): vom Scheduler erzeugte Ablauf- und Zuteilungsplan

Notwendigkeit des Scheduling von Tasks

- Tasks benötigen Ressourcen (Prozessor, Ein-/Ausgabegeräte usw.)

- Ressourcen sind knapp

- Tasks konkurrieren um Ressourcen

- Zuteilung der Ressourcen muss verwaltet werden.




Grundsatzfragen zum Scheduling

1. Gibt es für einen Taskset einen ausführbaren Plan (Schedule)?

(Schedulability test)

2. Gibt es einen Algorithmus, der einen ausführbaren Schedule findet?

3. Ist der Algorithmus optimal in dem Sinne, dass er immer einen gültigen

Schedule findet, wenn dies durch eine Ausführbarkeitstest nachgewiesen

wurde?

Scheduling-Verfahren

statisch dynamisch

Nicht-preemptiv preemptiv Nicht-preemptiv preemptiv

Klassifizierung

Zeitpunkt der Planung

Art der Durchführung


Statisches Scheduling Synchrone Programmierung

- Planung des zeitlichen Ablaufs der Tasks erfolgt vor der Ausführung

(Dispatching table) vorhersehbar, aber unfexibel

- Berücksichtigung von Informationen über Taskset, Deadlines,

Ausführungszeiten, Reihenfolgebeziehungen, Ressourcen

- Dispatcher macht Zuteilung gemäß Dispatching Table

- minimaler Laufzeit-Overhead

- determiniertes Verhalten

Dynamisches Scheduling Asynchrone Programmierung

- Organisation des zeitlichen Ablaufs während der Ausführung der Tasks

- erheblicher Laufzeit-Overhead durch die „Online-Suche“ nach einem

ausführbaren Schedule



Preemptives Scheduling

- Laufende Task kann unterbrochen werden.

- Höherpriore Task verdrängt niederpriore Task.

Nicht-preemptives Scheduling

- Laufende Task kann nicht unterbrochen werden.

- Prozessorfreigabe erfolgt durch die Task selbst.

Wichtigste Scheduling-Verfahren

- FIFO-Scheduling (First-in-first-out)

- Zeitscheibenverfahren

- Scheduling mit festen Prioritäten

- Ratenmonotones Scheduling

- Verfahren der kleinsten Restantwortzeit

- Verfahren des kleinsten Spielraums



FIFO-Scheduling

- Nicht-preemptives Scheduling

- Task, deren Einplanung am weitesten zurückliegt, bekommt Prozessor.

Beispiel:

Einfache Realisierung, aber ungeeignet für harte Echtzeitsysteme!

Tasks werden in der Reihenfolge ausgeführt, in der sie ablauffähig werden:


t

Task A bereit

Task B bereit

Task C bereit Task D bereit

t

A B C D


Zeitscheibenverfahren (Round-Robin-Verfahren)

- Jede Task bekommt einen festgelegten Zeitschlitz, zu der sie den Prozessor

bekommt.

- Reihenfolge wird statisch festgelegt.

- Abarbeitung einer Task “Stück für Stück”

- Verwendung bei Dialogsystemen (Multi-Tasking-Systeme)

Ungeeignet für harte Echtzeitsysteme!

Beispiel:

4 Tasks mit Zeitdauern: A: 25ms, B: 20ms, C: 30ms, D: 20ms

Jeder Zeitschlitz sei 10ms groß.

Reihenfolge der zyklischen Abarbeitung: A-B-C-D


t [ms]

A B C D A B C D A C

10 30 50 70 90 110


Scheduling mit festen Prioritäten

- Prioritäten werden statisch vergeben.

- Task mit höchster Priorität bekommt Prozessor.

- Preemptive und nicht-preemptive Strategie ist möglich.

- einfache Implementierung

Nur bedingt geeignet für harte Echtzeitsysteme!

Beispiel:

Bei Tasks mit gleicher Priorität: weitere unterlagerte Bedingung nötig.

* FIFO-Scheduling: A war zuerst ablauffähig.


Task Prio.

A 1 höchste Prio.

B 1

C 2

D 3

E 3

t

A* B C D E


Ratenmonotones Scheduling

(Rate-Monotonic-Verfahren)

- Spezialfall des Verfahrens mit festen Prioritäten für zyklische Tasks

- Task mit kleinster Zykluszeit (Periode) erhält höchste Priorität.

- preemptive Strategie

Verfahren wird in der Praxis häufig verwendet!

Beispiel:

Erste geplante Ausführung aller Tasks bei t = 0 ms Danach werden die Tasks zyklisch wiederholt.

Task D wird unterbrochen.


Task Ausführungs- dauer

Zykluszeit

A B C D

10 ms 20 ms 10 ms 20 ms

40 ms 50 ms 80 ms 100 ms

t [ms]

A1 B1 C1 A2 B2 D1a A3 C2 B3 A4 D1b

20 40 60 80 100 120 0 140

Prio.

1 2 3 4


Verfahren der kleinsten Restantwortzeit

(Earliest-Deadline-First-Verfahren)

- Task mit kleinster Restantwortzeit bekommt Prozessor.

- preemptives Vorgehen

- hoher Rechenaufwand für das Scheduling

- Einhaltung von zeitlichen Anforderungen wird speziell unterstützt.

Beispiel:

Deadline von B ist früher als von A.

Deadline von E ist früher als von D. Unterbrechung


Task Dauer tmin tmax

A B C D E

10 ms 10 ms 30 ms 40 ms 10 ms

0 ms 0 ms 30 ms 50 ms 70 ms

40 ms 30 ms 100 ms 200 ms 90 ms

tmin: frühester Termin tmax: spätester Termin = Deadline

t [ms]

B A C Da E Db

20 40 60 80 100 120 0


Verfahren des kleinsten Spielraums

(Least-Laxity-Verfahren)

- Task mit kleinstem Spielraum erhält Prozessor.

- Berücksichtigung von Deadlines und Ausführungsdauern

- sehr aufwendiges Verfahren

Beispiel:

Am besten geeignet für harte Echtzeitsysteme!


Task Dauer Einplanung Deadline

A B C D E

30 ms 10 ms 30 ms 40 ms 10 ms

0 ms 0 ms 30 ms 50 ms 70 ms

40 ms 30 ms 100 ms 200 ms 90 ms

t [ms]

Aa C E D

20 40 60 80 100 120 0

B Ab

Spielraum

10 20 40 110 10


Ausführbarkeitstest (Schedulability Test)

Unter einem Schedulability-Test versteht man die Prüfung, ob der zeitliche

Ablauf für einen Taskset so geplant werden kann, dass jede Task ihre Deadline

einhält.

Theorem von Liu und Layland (Teil I)

Eine beliebige Menge periodischer Tasks (Deadline = Periodendauer) kann durch

das preemptive Earliest-Deadline-First-Verfahren ausgeführt werden, wenn

gilt (notwendige und hinreichende Bedingung):

1

1n

i

i i

C

T

mit:

n: Anzahl der Tasks

Ci: Ausführungszeit der Task i

Ti: Zykluszeit der Task i



Theorem von Liu und Layland (Teil II)

Eine beliebige Menge periodischer Tasks (Deadline = Periodendauer) kann

durch das Rate-Monotonic-Verfahren ausgeführt werden, wenn gilt

(hinreichende Bedingung):

1

*

1

*

1

*

2

*

3

*

2 1 , 1,2,

1,0

0,828

0,779

ln 2 0,693

ni n

n

i i

CU n n

T

U

U

U

U

mit:

Ui: Utilization (Prozessorauslastung): ii

i

CU

T


Documents

Prozessautomatisierungstechnik - uni-due.de · • Synchrone Programmierung ist ungeeignet für die Reaktion auf zeitlich nicht vorhersehbare (asynchrone) Ereignisse, z.B. Alarmsignal