274
5 Bewertung und Validierung
5.2.3 Realzeitkalkül
WCET-Berechnungen erlauben es uns, obere Schranken für eine einzelne Ausführung eines Programms zu bestimmen. Die resultierenden Werte reichen aber noch
nicht aus, um zu garantieren, dass ein Strom von Ereignissen von einer Hardwareplattform mit ausreichender Performanz rechtzeitig verarbeitet wird. Dies kann aber
z.B. für Teile des Internets der Dinge wichtig sein.
Eine Prüfung auf eine ausreichende Verarbeitungsleistung ist mit Thieles Realzeitkalkül (engl. Real-Time Calculus (RTC)) möglich. Dieser Kalkül basiert auf
einer Beschreibung der Rate der eingehenden Ereignisse2. Diese Beschreibung umfasst auch Fluktuationen dieser Rate. Zu diesem Zweck werden charakteristische
Eigenschaften eingehender Ströme von Ereignissen durch ein Tupel von Ankunftskurven (engl. arrival curves) dargestellt
α
u (∆), α
l (∆) ∈ R ≥ 0, ∆ ∈ R ≥ 0
α u (∆) und α l (∆) beschreiben jeweils die maximale bzw. die minimale Anzahl von
Ereignissen, die in einem Intervall der Länge ∆ eingehen. Es gibt also höchstens
α u (∆) und mindestens α l (∆) eingehende Ereignisse in einem Intervall (t, t + ∆) für
alle t ≥ 0. Abb. 5.12 beschreibt die Zahl möglicher Ereignisankünfte für mögliche
Modelle von Ereignisströmen. Bei periodischen Ereignisströmen mit einer Periode
∆
1
2
3
α
α
u
l
l
u
α
α
3
2
1
∆
T
2T 3T
T-J T
T+J
2T 3T
Abb. 5.12 Ankunftskurven: links: periodischer Strom; rechts: periodischer Strom mit Jitter J
T findet in einem Intervall (0,T) maximal ein einzelnes Ereignis statt3. Entsprechend gibt es eine obere Grenze von höchstens zwei ankommenden Ereignissen im
Zeitintervall (T, 2 T).
Betrachten wir nun die untere Schranke für das Zeitintervall (0,T). Möglicherweise findet kein einziges Ereignis in diesem Intervall statt. Die untere Schranke ist also
Null. Im Zeitintervall (T, 2 T) muss es mindestens ein Ereignis geben. Daher ist die
Schranke ebenfalls eins. Für ∆ = 0, 5 T gibt es also mindestens Null und maximal ein
ankommendes Ereignis (siehe Abb. 5.12 (links)). Bei periodischen Ereignisströmen
mit Jitter J werden die Kurven um diesen Betrag verschoben. Die obere Schranke ist
2 Unsere Darstellung basiert auf Thieles Beitrag im Buch von Zurawski [536]. Entsprechende
Betrachtungen auf Systemebene heißen Modular Performance Analysis (MPA).
3 Wir vermeiden hier die subtile Diskussion der Unstetigkeiten für ∆ = n ∗ T .
5 Bewertung und Validierung
5.2.3 Realzeitkalkül
WCET-Berechnungen erlauben es uns, obere Schranken für eine einzelne Ausführung eines Programms zu bestimmen. Die resultierenden Werte reichen aber noch
nicht aus, um zu garantieren, dass ein Strom von Ereignissen von einer Hardwareplattform mit ausreichender Performanz rechtzeitig verarbeitet wird. Dies kann aber
z.B. für Teile des Internets der Dinge wichtig sein.
Eine Prüfung auf eine ausreichende Verarbeitungsleistung ist mit Thieles Realzeitkalkül (engl. Real-Time Calculus (RTC)) möglich. Dieser Kalkül basiert auf
einer Beschreibung der Rate der eingehenden Ereignisse2. Diese Beschreibung umfasst auch Fluktuationen dieser Rate. Zu diesem Zweck werden charakteristische
Eigenschaften eingehender Ströme von Ereignissen durch ein Tupel von Ankunftskurven (engl. arrival curves) dargestellt
α
u (∆), α
l (∆) ∈ R ≥ 0, ∆ ∈ R ≥ 0
α u (∆) und α l (∆) beschreiben jeweils die maximale bzw. die minimale Anzahl von
Ereignissen, die in einem Intervall der Länge ∆ eingehen. Es gibt also höchstens
α u (∆) und mindestens α l (∆) eingehende Ereignisse in einem Intervall (t, t + ∆) für
alle t ≥ 0. Abb. 5.12 beschreibt die Zahl möglicher Ereignisankünfte für mögliche
Modelle von Ereignisströmen. Bei periodischen Ereignisströmen mit einer Periode
∆
1
2
3
α
α
u
l
l
u
α
α
3
2
1
∆
T
2T 3T
T-J T
T+J
2T 3T
Abb. 5.12 Ankunftskurven: links: periodischer Strom; rechts: periodischer Strom mit Jitter J
T findet in einem Intervall (0,T) maximal ein einzelnes Ereignis statt3. Entsprechend gibt es eine obere Grenze von höchstens zwei ankommenden Ereignissen im
Zeitintervall (T, 2 T).
Betrachten wir nun die untere Schranke für das Zeitintervall (0,T). Möglicherweise findet kein einziges Ereignis in diesem Intervall statt. Die untere Schranke ist also
Null. Im Zeitintervall (T, 2 T) muss es mindestens ein Ereignis geben. Daher ist die
Schranke ebenfalls eins. Für ∆ = 0, 5 T gibt es also mindestens Null und maximal ein
ankommendes Ereignis (siehe Abb. 5.12 (links)). Bei periodischen Ereignisströmen
mit Jitter J werden die Kurven um diesen Betrag verschoben. Die obere Schranke ist
2 Unsere Darstellung basiert auf Thieles Beitrag im Buch von Zurawski [536]. Entsprechende
Betrachtungen auf Systemebene heißen Modular Performance Analysis (MPA).
3 Wir vermeiden hier die subtile Diskussion der Unstetigkeiten für ∆ = n ∗ T .