View
106
Download
0
Category
Preview:
Citation preview
COMET-Methodik: Realzeit
Karsten BalzerEntwicklung verteilter eingebetteter SystemeFebruar 2002
Übersicht
Task Structuring• Was sind Tasks?• Was ist Task Structuring?• Strukturierungskriterien• Beispiele
Performance Analysis• Einleitung• Verfahren zu Analyse• Beispiel
Was tun bei Engpässen?
Was sind Tasks?
Auch Thread oder Prozeßaktive Objekte, dies sind autonome Objekte mit
eigenem, sequentiellen Kontrollflußsie repräsentieren sequentielle Programme oder
sequentielle Teile aus nebenläufigen Programmen
innerhalb von Tasks gibt es keine NebenläufigkeitUnterscheidung in
• Input/Output Tasks, für Objekte, die nach Außen kommunizieren
• interne Tasks
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Structuring - Einleitung
COMET-Phase: Software DesignZiele:
• Analyse-Modell zu Task Architektur umwandeln• Separation of concerns, Tasks nach Aufgaben
aufteilen• Einfaches und klares Design• Minimierung von Overhead in Form von Inter-Task
Kommunikation und Synchronisation
Kriterien sind Richtlinien und Heuristiken um diesen Konflikt zwischen übersichtlichem Design und geringem Overhead zu lösen
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Structuring - Einleitung 2
Die Strukturierung ist eingeteilt in zwei Phasen:Phase 1: Jedes aktive Objekt erhält einen
Task• I/O task structuring criteria• Internal task structuring criteria• Task priority criteria
Phase 2: Zusammenfassen der Tasks aus Phase 1
• Task clustering criteria• Task inversion criteria
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Structuring Phase 1
Jedem aktiven Objekt wird genau ein „Candidate Task“ zugeordnet, also vorläufige Tasks, die später noch verändert werden
Dadurch können die Aufgaben jedes einzelnen Tasks schnell ersehen werden
Tasks werden Prioritäten zugeordnet• Zeitkritische Tasks werden identifiziert und
erhalten höhere Prioritäten• oder Tasks mit kürzerer Periode erhalten eine
höhere Priorität als Tasks mit längerer Periode
wichtig für die Performance Analyse
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
I/O Task Structuring Criteria
Unterscheidung nach• Asynchrone/aktive I/O Devices, die einen
Interrupt bei Input oder nach Output generieren• Passive I/O Devices, Input bzw. Output wird nur
bei Bedarf oder periodisch gelesen oder generiert • Communication Links, die zur Kommunikation mit
anderen Systemen dienen, z.B. via TCP/IP
Jedem dieser Objekte wird ein eigener Task zugeordnet
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Beispiel I/O Task
FloorButtonInterface Asynchronous Input Device:
Durch Drücken eines Knopfes wird der Fahrstuhl gerufen
Nach dem I/O Task Structuring Criteria erhält das FloorButtonInterface einen eigenen Task
Internal Task Structuring Criteria
Unterscheidung in• Periodische Tasks: Ein durch einen Timer ausgelöster, periodischer
Task• Asynchrone Tasks: Bei Bedarf durch interne Nachrichten oder
Events aktivierte Objekte• Control Tasks: Tasks zu zustandsorientierten Kontrollobjekten,
deren Statecharts keine parallelen Zustände aufweisen• User Interface Tasks: Dienen zur Kommunikation zwischen
Benutzer und System• Mehrere Tasks desselben Typs: Tasks zu gleichartigen Objekten,
die aber in unterschiedlichen Zuständen sein können
Jedem dieser Objekte wird ein eigener Task zugeordnet
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Priority Criteria
Generell werden Prioritäten nach dem Rate Monotonic Algorithm vergeben
Darüber hinaus wird unterschieden in• Zeitkritische Tasks: Typischerweise asynchrone
I/O Tasks oder Tasks die für Output-Tasks wichtige Berechnungen durchführen. Diese erhalten höhere Prioritäten, damit das System schnell reagieren kann
• Nicht-zeitkritische Tasks: Diese Tasks können niedrigere Prioritäten erhalten, damit sie von zeitkritischen Tasks unterbrochen werden können
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Structuring Phase 2
Kritierien:• Task Clustering• Task Inversion
Candidate Tasks aus Phase 1 werden zusammengefaßt
Dadurch werden Overhead und Komplexität reduziert
Task Inversion faßt stärker zusammen als Task Clustering
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Clustering Criteria
Zusammenfassen von Tasks, dabei wird unterschieden nach
• Temporal Clustering: Tasks, die von dem selben Event ausgelöst werden und die in beliebiger Reihenfolge ausgeführt werden
• Sequential Clustering: Tasks, die sich sequentiell durch Events gegenseitig starten
• Control Clustering: Ein Task, der ein sequentielles Statechart startet, kann mit Objekten zusammengelegt werden, die von diesem Statechart angestoßen werden
• Mutually Exclusive Clustering: Tasks, von denen maximal einer gleichzeitig aktiv ist
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Beispiel Task Clustering
ElevatorContol, ElevatorLampInterface
Passive output device: Lampen für Fahrstuhl
Output nur bei BedarfAufrufender Task muss
warten, bis der Output-Task fertig ist
Zusammenfassen nach Control Clustering Criterion
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Task Inversion
Zusammenfassen von Tasks zum Zweck der Reduzierung von Overhead
Unterscheidung in• Multiple-Instance Task Inversion: Mehrere identische
Tasks werden zusammengefaßt• Sequential Task Inversion: Sequentiell ausgeführte
Tasks, die mit Hilfe von Nachrichten kommunizieren• Temporal Task Inversion: Tasks, die von dem selben
Timer gestartet werden, können inklusive des Timers zusammengefaßt werden
Für das Design meist unschöne Veränderungen, daher oft nur für Optimierung benutzt
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Ergebnis Elevator
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Performance Analysis - Einleitung
COMET-Phase: Detailed Software Design, kann gleich nach dem Task Structuring beginnen
Ziel: Potentielle Performance Probleme finden und beheben
Zeitkritische Tasks müssen Deadlines einhaltenDeadlines sind vorgegebene Termine, vor denen
ein Task beendet sein mussDabei sind gegeben:
• Hardwarekonfiguration• Prozessorlast der einzelnen Tasks
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Event Sequence Analysis
Zu jedem Use-Case werden Event Sequenzen betrachtet und überprüft
Diese Sequenzen werden durch einen externer Event ausgelöst
Betrachtet werden die Rechenzeiten für:• I/O-Task• die folgende Sequenz interner Tasks• CPU Overhead• bekannte, parallel ablaufende Tasks
Die Summe diese Zeiten kleiner als die gewünschte Reaktionszeit des Systems, um Echzeitanforderungen zu erfüllen
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Real-Time Scheduling Theory
ursprünglich für unabhängige, periodische TasksBerechnung basiert auf Prioritäten der TasksCPU Belastung der Tasks wird als bekannt
vorausgesetzt. Nach COMET basieren sie auf Abschätzungen aufgrund vorheriger Projekte
Ein Task hält seine Deadline ein, wenn seine Ausführung innerhalb seiner Periode endet
Rate Monotonic Algorithm: Jeder Task erhält basierend auf seiner Periode eine feste Priorität
Je kürzer die Periode desto höher die PrioritätDies stellt eine Vereinfachung dar, zeitkritische Tasks
werden zunächst nicht betrachtet
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Utilization Bound Theorem
Grobe Worst-Case-Abschätzung auf Basis des Rate Monotonic Algorithm
Jeder Task hat eine Periode T und eine Ausführungszeit C
n unabhänge, periodische Tasks halten ihre Deadlines ein, wenn gilt:
U(n) konvergiert dabei zu 0.69Utilization U ist die prozentuale Nutzung des
Prozessors während der betrachteten Zeitspanne
U(n))12(... /1
1
1 n
n
n nTC
TC
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Completion Time Theorem
Ebenfalls eine Worst-Case-Abschätzung, allerdings viel genauer als das Utilization Bound Theorem
Voraussetzung: Wenn ein Task seine erste Deadline einhält, hält er auch alle späteren Deadlines ein
Wenn ein Task seine Deadline in der ersten Periode einhält und alle Tasks gleichzeitig gestartet werden, tun sie dies bei allen möglichen Kombinationen aus Startzeiten
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Completion Time Theorem Beispiel
t1 : C1 = 20, T1 = 100, U1 = 0.2 t2 : C2 = 30, T2 = 150, U2 = 0.2 t3 : C3 = 90, T3 = 200, U3 = 0.45 Beginn mit der Worst-Case-
Annahme, dass alle drei Tasks gleichzeitig gestartet werden
Nach dem Diagramm halten alle Tasks ihre Deadline ein
Utilization U = U1+U2+U3 = 0.85 Vergleich zum Utilization Bound
Theorem: U > U(n), trotzdem werden die
Deadlines eingehalten
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
790.0)12(3)3( 3/1 U
Completion Time Theorem Mathematische Formel
Eine Menge aus n unabhängigen, periodischen Tasks hält bei Anwendung des Rate Monotonic Algorithm seine Deadlines genau dann ein, wenn gilt:
Betrachtungen am Ende einer Periode p des Tasks kTask i ist der momentan betrachtete Task, alle Task k
können diesen aufgrund höherer Priorität unterbrechen
}/,...,1,1|),{(
),(
11
min,1,1
kii
i
l
k
k
i
jj
TTpikpkR
Rpk
T
pT
pTCnii
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Generalized Utilization Bound Theorem
• Läßt man neben dem Rate Monotonic Algorithm zu, dass zeitkritische Tasks höhere Prioritäten erhalten, müssen zusätzlich folgende Punkte beachtet werden:
– Unterbrechung durch höher priorisierte Tasks mit längerer Periode– Blocken durch niedriger priorisierte Tasks
• Alle Deadlines werden eingehalten, wenn die Utilization jedes Tasks kleiner als 0,69 ist. Die Utilization wird hier berechnet mit:
• Eine entsprechende Verallgemeinerung existiert auch für das Completion Time Theorem
1
1
Hkkii
iHj j
ji CBC
TT
CU
n
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
i
i1
i
Task tfür Time Blocking CaseWorst :
haben Task tein als Periode längere eine undPriorität höhere eine die Tasks,der Menge:
haben Task tein als Periode kürzere eine undPriorität höhere eine die Tasks,der Menge:
i
n
B
H
H
Beispiel: Request ElevatorEvent Sequence
Periode: 200 msecAusführungszeit der
Tasks in der Event Sequenz
• Floor Button• InterfaceScheduler• Elevator Manager• C = 4 + 20 + 6 = 30
msec• U = C/T = 0.15
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Beispiel: Request ElevatorEvent Sequence 2
Unterbrechung durch höher priorisierte Tasks mit kürzerer Periode
• Arrival Sensors Interface und Elevator Controller zusammen max. 28 msec
• Elevator Button Interface und Elevator Manager zusammen max. 18 msec
• C = 28 + 18 = 46• U = C/T = 0.23
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Beispiel: Request ElevatorEvent Sequence 3
Unterbrechung durch höher priorisierte Tasks mit längerer Periode
• Diese Event Sequenz hat die längste Periode
Zeit, die der Task beblockt werden kann• keine, T = 0
Da diese beiden Punkte nicht beachtet werden müssen, gilt der Rate Monotonic Algorithm. Also kann das Utilization Bound Theorem angewandt werden.
T = 30 + 46 + 0 = 46 msec < periodU = 0.15 + 0.23 = 0.38 < 0.69Die Deadline wird also eingehalten.
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Was tun bei Engpässen?
Engpässe entstehen, wenn zeitkritische Tasks ihre Deadlines nicht einhalten können
Tasks neu strukturierenOverhead reduzieren durch Task Inversion
Hardware ändernschnellerer Prozessor, ...
Task Structuring Was sind Tasks? Was isrt Task Structuring? Strukturierungskriterien Beispiele
Performance Analysis Einleitung Verfahren zu Analyse Beispiel
Was tun bei Engpässen?
Zusammenfassung
Tasks sind aktive Objekte mit KontrollflußSie werden mit Hilfe von Scheduling Kriterien
erst erzeugt und danach gruppiertDabei erhalten sie eine PrioritätIn Echtzeit-Systemen müssen Tasks gegebene
Deadlines einhaltenOb dies der Fall ist, lässt sich mit Hilfe von
Eventsequenz-Analysen und verschiedenen Theoremen abschätzen
Werden die Grenzen nicht eingehalten, müssen die Tasks weiter zusammengefaßt werden
Recommended