Real Time Analysis in Real Time

Schedulability

Problembeschreibung

Performanzanalyse in beschränkter Zeit Iteratives Verfahren mit Schedulability Analysen Hier: SPP Schedulability Analyse in beschränkter Zeit

Wie die Zeit beschränken? Welche Faktoren Beeinflussen die Laufzeit? Optimierungen und ihr Einfluss auf die Laufzeit Möglichkeiten der Einflussnahme auf die Laufzeit

Ableitung einer Analysestrategie

Anatomie Busy-Window Algorithmen

Berechne Busy-Window

Busy-Window = Initialwert (0)

Mehr Preemptions?ja

Weitere Aktivierungen im Busy Window?ja

Preemption von höher prioren Tasks

Große Bursts

N+=1

Betrachte Aktivierung N=0Wähle N = letzter vom Burst

Untere Schranke für Busy Window als Initialwert

Beschränke Anzahl Durchläufe

Einfluss von Last und Jitter

Konstante WCET Jitter = 0 Periode T0 -> WCET T0

Viele Preemptionsschwierig

Konstante WCET Konstante Periode Jitter 0->1000*P

Großer Jitter nur schwierig für zu Analysierenden Task

Empirische Analyse - Ansatz

Generiere Taskset: Anzahl Tasks gleichverteilt [2..MAX_Tasks] WCET gleichverteilt [1..MAX_WCET] Periode gleichverteilt [1..MAX_PER] Jitter gleichverteilt [0..MAX_JIT]

Analysiere WCRT des niedrig priorsten Tasks Metriken:

Maximale Anzahl Busy-window Vergrößerungen (pro Aktivierung)

Anzahl zu Analysierender Aktivierungen Gesamtzahl Busy-Window Vergrößerungen

Analysedauer zufällig generierter Tasksets

Kein Jitter Analyse meist einfach

Großer Jitter Analyse schwierig

Großer Jitter mit Optimierungen

Gibt Hoffnung Aber: nicht Anwendbar, wenn

minD

Minimalabstand als Parameter

Genauere (= kleinere) WCET Größerer Akzeptanzfaktor

Beeinflussbar per Shaper im System

Zerstört Burst-Optimierung Längere Analysen

MinD Verwenden

Generisches Beispiel – Gain Exploriert über minD

0Periode

Analysedauer in Iterationen für obiges Beispiel

Minimalabstand als Parameter

Genauere (= kleinere) WCET

Größerer Akzeptanzfaktor

Beeinflussbar per Shaper im System

Zerstört Burst-Optimierung Längere Analysen

Verkürzt Analysedauer! (?)

Analysedauer, empirisch

Viele Versuche mit verschiedenen minD

Setze minD zu x%Periode Exploriert über x Durchschnitt,

Standardabweichung

Betrachtung von minD nur komplex für minD < 0,2 * P

Komplexe minD Probleme Abschätzen

Berechne Busy-Window

Busy-Window = Initialwert

Mehr Preemptions?ja

Weitere Aktivierungen im Busy Window?ja

N+=1

Betrachte Aktivierung N=0

Komplexe minD Probleme Abschätzen

Berechne Busy-Window

Busy-Window = Initialwert

Mehr Preemptions?ja

Weitere Aktivierungen im Busy Window?ja

N+=1

Betrachte Aktivierung N=0

N>K?

Dmin = 0

N = maxBurst

Exploration über verschiedene K

Versuch wie oben Nur Average K maximale Anzahl mit

minD Rot: ohne minD zu

beachten Keine Aussage:

Genauigkeit

Genauigkeit

Versuch wie oben Nur Average K maximale Anzahl

mit minD Ohne MinD = 0

Erkenntnisse bis jetzt

Schwierige Probleme Große Last mit hochfrequentem höherpriorem Task Großer Burst mit minD << P und K groß

Fragen: Wie K wählen? Wie viele Iterationen rechnen?

Was für Ergebnisse geben schwierige Probleme?

WCRT/WCET zu # Zyklen

WCRT/WCET = 500 (will man nicht)

Selbst für große K kann maxTotalCycles <150 gewählt werden

MaxTotalCycles = 50 fängt bei K< 20 die meisten Fälle mit WCRT/WCET < 500

K=10: Shortcut-Effekt?

Abstrakt gesehen

Existierende Probleme

Nicht Existierende Probleme

WC

RT

/ W

CE

T

Analysedauer

K -> 0

K ->

Infeasible wg. Latenz-Constraints

Tighter Constraints

500

200

Abbruch für WCRT > Pfadlatenz

Existierende Probleme

Nicht Existierende Probleme

WC

RT

/ W

CE

T

Analysedauer

K -> 0

K ->

Infeasible wg. Latenz-Constraints

Analysen können relativ früh abgebrochen werden

Tradeoff:Analysedauer – Genauigkeit über K

Strategie für die lokale Analyse

Schedulability Analyse in O(n) -> siehe Literatur WCRT Analyse nur für Tasks, die Latenz-Constrained sind

Wenn WCRT > Gesamtlatenz abbrechen Alle Abkürzungen von oben, K wählbar. (für schnelle Analysen

wähle K=0) Gedanken:

Bei Latenz-Beschränkungen kann schnell abgebrochen werden Andere, evtl. schwierige Probleme durch schedulability Analyse

erschlagen -> Schwierig zu analysierende Tasks wahrscheinlich nicht Latenz-Kritisch.

Conclusion

Goal: Perform SPP Analysis in bounded number of iterations Use Optimizations of Sjödin/Hanson

Esp. Init Burst Top-Down Analysis of tasks (not further investigated)

Use minD shortcut Shaper will help in Analysis complexity Tradeoff – Accuracy vs # of analyzable problems possible

Hard Problems will produce very large WCRTs Only analyse Tasks that have a latency constraint WCRT > constraint is abort-condition for analysis