5.2 Performanzbewertung
267
5.2.2 Größtmögliche Ausführungszeiten
Die Ablaufplanung oder das Scheduling von Tasks erfordert Wissen über deren Ausführungsdauer, insbesondere wenn das Einhalten von Zeitbedingungen garantiert
werden muss, wie etwa in Echtzeitsystemen. Die größtmögliche Ausführungszeit
(engl. Worst Case Execution Time (WCET)) ist die Ausgangsbasis der meisten Scheduling-Algorithmen. Einige im Zusammenhang mit der größtmöglichen Ausführungszeit wichtige Definitionen sind in Abb. 5.4 und der nachfolgenden Definition
aufgeführt.
Abb. 5.4 Begriffe im Zusammenhang mit der größtmöglichen
Ausführungszeit
Verteilung von Laufzeiten
EST
EST
WCET
BCET
WCET
BCET
t
Definition 5.9: Die größtmögliche Ausführungszeit (engl. Worst Case Execution
Time (WCET)) ist das Maximum über alle Ausführungszeiten, die ein Programm benötigen kann, wenn beliebige Eingaben und ein beliebiger Anfangszustand möglich
sind.
Leider ist die WCET nur sehr schwer berechenbar. Allgemein ist es sogar unentscheidbar, ob die WCET endlich ist oder nicht. Dies ist eine direkte Folge davon,
dass es nicht entscheidbar ist, ob ein Programm terminiert oder nicht. Daher lässt sich
die WCET nur für bestimmte Programme oder Tasks berechnen. Beispielsweise kann
die WCET für Programme berechnet werden, die weder Rekursion noch Schleifen
mit einer unbekannten Anzahl an Wiederholungen enthalten. Doch auch die Anwendung solcher Einschränkungen macht es meist in der Praxis unmöglich, die WCET zu
berechnen. Die Auswirkungen der Fließbänder (engl. pipelines) von modernen Prozessorarchitekturen, die verschiedene Arten von Hazards (Risiken) erzeugen können
und Speicherhierarchien mit begrenzter Vorhersagbarkeit von Trefferraten sind nur
schwer während des Entwurfs vorhersagbar. Die Berechnung der WCET für Systeme
mit Caches, Verdrängungen von Prozessen, Unterbrechungen und virtuellem Speicher ist eine noch größere Herausforderung. Daher müssen wir uns damit zufrieden
geben, eine gute obere Schranke für die WCET angeben zu können.
Solche oberen Schranken werden als geschätzte WCETs (engl. Estimated
WCETs) oder WCET EST bezeichnet. Diese Schranken sollten zumindest diese beiden Eigenschaften besitzen:
1. die Schranken sollten sicher sein (WCET EST ≥ WCET) und
2. die Schranken sollten gut sein (WCET EST -WCET ≪ WCET).
267
5.2.2 Größtmögliche Ausführungszeiten
Die Ablaufplanung oder das Scheduling von Tasks erfordert Wissen über deren Ausführungsdauer, insbesondere wenn das Einhalten von Zeitbedingungen garantiert
werden muss, wie etwa in Echtzeitsystemen. Die größtmögliche Ausführungszeit
(engl. Worst Case Execution Time (WCET)) ist die Ausgangsbasis der meisten Scheduling-Algorithmen. Einige im Zusammenhang mit der größtmöglichen Ausführungszeit wichtige Definitionen sind in Abb. 5.4 und der nachfolgenden Definition
aufgeführt.
Abb. 5.4 Begriffe im Zusammenhang mit der größtmöglichen
Ausführungszeit
Verteilung von Laufzeiten
EST
EST
WCET
BCET
WCET
BCET
t
Definition 5.9: Die größtmögliche Ausführungszeit (engl. Worst Case Execution
Time (WCET)) ist das Maximum über alle Ausführungszeiten, die ein Programm benötigen kann, wenn beliebige Eingaben und ein beliebiger Anfangszustand möglich
sind.
Leider ist die WCET nur sehr schwer berechenbar. Allgemein ist es sogar unentscheidbar, ob die WCET endlich ist oder nicht. Dies ist eine direkte Folge davon,
dass es nicht entscheidbar ist, ob ein Programm terminiert oder nicht. Daher lässt sich
die WCET nur für bestimmte Programme oder Tasks berechnen. Beispielsweise kann
die WCET für Programme berechnet werden, die weder Rekursion noch Schleifen
mit einer unbekannten Anzahl an Wiederholungen enthalten. Doch auch die Anwendung solcher Einschränkungen macht es meist in der Praxis unmöglich, die WCET zu
berechnen. Die Auswirkungen der Fließbänder (engl. pipelines) von modernen Prozessorarchitekturen, die verschiedene Arten von Hazards (Risiken) erzeugen können
und Speicherhierarchien mit begrenzter Vorhersagbarkeit von Trefferraten sind nur
schwer während des Entwurfs vorhersagbar. Die Berechnung der WCET für Systeme
mit Caches, Verdrängungen von Prozessen, Unterbrechungen und virtuellem Speicher ist eine noch größere Herausforderung. Daher müssen wir uns damit zufrieden
geben, eine gute obere Schranke für die WCET angeben zu können.
Solche oberen Schranken werden als geschätzte WCETs (engl. Estimated
WCETs) oder WCET EST bezeichnet. Diese Schranken sollten zumindest diese beiden Eigenschaften besitzen:
1. die Schranken sollten sicher sein (WCET EST ≥ WCET) und
2. die Schranken sollten gut sein (WCET EST -WCET ≪ WCET).