COMET-Methodik: Realzeit
Karsten Balzer
Entwicklung verteilter eingebetteter
Systeme
Februar 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?
Task Structuring
Was sind Tasks?
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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äufigkeit
Unterscheidung in
• Input/Output Tasks, für Objekte, die nach Außen
kommunizieren
• interne Tasks
Task Structuring Einleitung
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
COMET-Phase: Software Design
Ziele:
•
•
•
•
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 Einleitung 2
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Task Structuring Phase 1
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
I/O Task Structuring
Criteria
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Beispiel I/O Task
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Task Priority Criteria
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
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
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
Task Structuring
Task Clustering Criteria
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Beispiel Task Clustering
ElevatorContol,
ElevatorLampInterface
Passive output device:
Lampen für Fahrstuhl
Output nur bei Bedarf
Aufrufender Task muss
warten, bis der Output-Task
fertig ist
Zusammenfassen nach
Control Clustering Criterion
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
Task Structuring
Task Inversion
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Ergebnis Elevator
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
Performance Analysis Einleitung
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
COMET-Phase: Detailed Software Design, kann
gleich nach dem Task Structuring beginnen
Ziel: Potentielle Performance Probleme finden und
beheben
Zeitkritische Tasks müssen Deadlines einhalten
Deadlines sind vorgegebene Termine, vor denen
ein Task beendet sein muss
Dabei sind gegeben:
• Hardwarekonfiguration
• Prozessorlast der einzelnen Tasks
Task Structuring
Event Sequence Analysis
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
Real-Time Scheduling
Theory
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
ursprünglich für unabhängige, periodische Tasks
Berechnung basiert auf Prioritäten der Tasks
CPU 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ät
Dies stellt eine Vereinfachung dar, zeitkritische
Tasks werden zunächst nicht betrachtet
Task Structuring
Utilization Bound Theorem
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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:
C1  ...  Cn  n(21/ n  1)  U(n)
T1
Tn
U(n) konvergiert dabei zu 0.69
Utilization U ist die prozentuale Nutzung des
Prozessors während der betrachteten Zeitspanne
Task Structuring
Completion Time Theorem
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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
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-CaseAnnahme, 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 (3) 3(21/ 3 1)  0.790
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?
Completion Time Theorem
Mathematische Formel
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
Eine Menge aus n unabhängigen, periodischen Tasks
hält bei Anwendung des Rate Monotonic Algorithm seine
Deadlines genau dann ein, wenn gilt:
1  pTk 
i,1  i  n, min  C j

 1
pTk  Tl 
j 1
(k , p)  Ri
i
Ri  {( k , p) | 1  k  i, p  1,...,Ti / Tk }
Betrachtungen am Ende einer Periode p des Tasks k
Task i ist der momentan betrachtete Task, alle Task k
können diesen aufgrund höherer Priorität unterbrechen
Generalized Utilization
Bound Theorem
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
• 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:

Cj

Ui  
 jH T
 n j
 1

 T
 i


 Ci  Bi   Ck 


kH1


H n : Menge der T asks,die eine höherePrioritätund eine kürzerePeriodeals ein T ask ti haben
H1 : Menge der T asks,die eine höherePrioritätund eine längerePeriodeals ein T ask ti haben
Bi : WorstCase BlockingT imefür T ask ti
• Eine entsprechende Verallgemeinerung existiert auch für das Completion
Time Theorem
Beispiel: Request Elevator
Event Sequence
Periode: 200 msec
Ausfü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 Elevator
Event 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 Elevator
Event Sequence 3
Task Structuring
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
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 < period
U = 0.15 + 0.23 = 0.38 < 0.69
Die Deadline wird also eingehalten.
Task Structuring
Was tun bei Engpässen?
Was sind Tasks?
Was isrt Task Structuring?
Strukturierungskriterien
Beispiele
Performance Analysis
Einleitung
Verfahren zu Analyse
Beispiel
Was tun bei Engpässen?
Engpässe entstehen, wenn zeitkritische Tasks
ihre Deadlines nicht einhalten können
Tasks neu strukturieren
Overhead reduzieren durch Task Inversion
Hardware ändern
schnellerer Prozessor, ...
Zusammenfassung
Tasks sind aktive Objekte mit Kontrollfluß
Sie werden mit Hilfe von Scheduling Kriterien erst
erzeugt und danach gruppiert
Dabei erhalten sie eine Priorität
In Echtzeit-Systemen müssen Tasks gegebene
Deadlines einhalten
Ob 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

Vortrag