www.wikidata.de-de.nina.az

Maximale Laufzeit Die maximale Laufzeit oder maximale Ausführungszeit englisch Worst Case Execution Time WCET gibt die l

Maximale Laufzeit

Die maximale Laufzeit oder maximale Ausführungszeit (englisch Worst Case Execution Time, WCET) gibt die längste Zeit an, die ein Computerprogramm oder Programmteil auf einer bestimmten Plattform zur Ausführung benötigen kann. Sie wird bestimmt durch:

Die Kenntnis der WCET oder zumindest einer sicheren oberen Schranke ist ein notwendiges Kriterium zur Implementierung eines harten Echtzeitsystems. Bei Echtzeitsystemen ist es sehr wichtig, das logisch richtige Ergebnis zu exakten Zeitpunkten zu erhalten. Nur kurze Verzögerungen könnten katastrophale Auswirkungen haben. Die wichtigsten Anwendungsgebiete für Echtzeitsysteme sind z. B. Autoairbagsteuerungen, Flugzeugsteuerungen, Steuerungen in Kraftwerken. Bei Autosteuerungen kann das verspätete Herausschleudern des Airbags tödliche Folgen für die Insassen des Kraftfahrzeuges haben. Daher ist es wichtig, dass Echtzeitsysteme das richtige Ergebnis in einer bestimmten Zeit bereitstellen.

Die Ausführungszeit Bearbeiten

Grundsätzlich wird zwischen BCET (best case execution time) und WCET (worst case execution time) unterschieden. Die BCET ist die schnellste Ausführungsdauer, indem das Programm ein Ergebnis liefert, d. h. das Programm kann unter keinen Umständen schneller ausgeführt werden. Die WCET ist die längstmögliche Ausführungsdauer, in der der Programmcode ein Ergebnis bereitstellt.

Grundsätzliche Probleme der Laufzeitbestimmung Bearbeiten

Theoretische Grenzen Bearbeiten

Im allgemeinen Fall ist es unmöglich die maximale Ausführungszeit für ein beliebiges Programm zu bestimmen.

Um die maximale Ausführungszeit zu bestimmen, müsste man folgendes Problem lösen: Gegeben ist ein Programm P. Gesucht ist ein weiteres Programm WCET, das die maximale Ausführungszeit von P, also WCET(P), berechnet. Da alle jene Programme, die in eine Endlosschleife laufen, eine maximale Ausführungszeit haben, könnte man das Programm WCET benutzen, um zu entscheiden, ob das zugrundeliegende Programm überhaupt terminiert und somit das Halteproblem lösen. Das Halteproblem ist jedoch nachweislich unentscheidbar, somit kann es das Programm WCET nicht geben.

Eine Obergrenze der WCET kann aber für eine relevante Untermenge aller möglichen Programme bestimmt werden.

Praktische Probleme Bearbeiten

Die Schedulingstrategien moderner Betriebssysteme verhindern eine zuverlässige Voraussage zu welchem Zeitpunkt ein Task dran kommt. Abhilfe schaffen hier Echtzeitbetriebssysteme oder Direktimplementierungen ohne Betriebssystemschicht.

Auf modernen Prozessorarchitekturen hängt die Ausführungszeit eines Tasks mitunter stark von dem Zustand des Prozessorcaches ab. Selbst bei Verwendung eines Echtzeitbetriebssystems kann es so zu Beeinflussungen zweier Tasks über den Cache kommen.

Methoden zur Bestimmung Bearbeiten

Es gibt verschiedene Methoden die WCET zu berechnen, die sich allerdings nur durch Genauigkeit und Anwendbarkeit unterscheiden. Eine wichtige Bedeutung ist es, wie genau die WCET abgeschätzt werden kann. Die Methoden versuchen daher so nahe wie möglich an die wirkliche Ausführungszeit heranzukommen, das Ergebnis darf aber nie kleiner als die tatsächliche Ausführungszeit sein.

Eine Möglichkeit zur Abschätzung der WCET sind Messmethoden. Bei diesen Methoden wird durch verschiedenste Testläufe auf der Zielhardware die Zeit gemessen, welche der Code benötigt, um ein Ergebnis zu liefern. Diese Methode ist sehr aufwändig, da nie alle Zustände getestet werden können (Kombinatorische Explosion).

Bei der WCET-Analyse wird hingegen der längste Ausführungsweg ermittelt und die Ausführungszeit für eine bestimmte Zielhardware so errechnet.

Messbasierte Ansätze Bearbeiten

Die messbasierten Ansätze führen statt einer Analyse des Codes das Programm einfach auf der Zielhardware aus und messen die Ausführungszeit. Messbasierte Ansätze führen jedoch im Allgemeinen zu einer Unterschätzung der WCET, da die Ausführungszeit von Programmen generell von den Eingabedaten abhängt. Durch Analyse des Sourcecodes können jedoch Eingabedatensätze erzeugt werden, welche alle Pfade des zu testenden Programms abdecken. Diese Methode vereinfacht zwar die Portierung einer Software, leidet aber ebenfalls unter komplexen Prozessorarchitekturen.

WCET-Analyse Bearbeiten

Die WCET-Analyse berechnet den schlechtesten Fall der Ausführungszeit eines bestimmten Codes einer Anwendung, jedoch besteht keine Garantie der Richtigkeit der Ergebnisse des Codes. Weiter ist die WCET vom Programmcode und von der zugrundeliegenden Hardware abhängig, d. h. verschiedene Programmcodes haben auf verschiedenen Rechnerarchitekturen unterschiedliche Worst Case Execution Times. Daher sollte die Analyse immer mit den Hardwarekomponenten durchgeführt werden die auch das Zielsystem besitzt. Bei dieser Methode wird der Programmcode untersucht und der tatsächlich längste Ausführungsweg ermittelt. Dann addiert man die benötigten Prozessorzyklen aller im Pfad befindlichen Maschinencodebefehle und man erhält die WCET.

Probleme bei der WCET-Analyse Bearbeiten

Es gibt drei Problemdomänen bei der WCET-Analyse. Einerseits das Herausfinden des auszuführenden Pfades, die Übersetzung des Sourcecodes in den Maschinencode und die Maschinencodeanalyse.

Bestimmung des auszuführenden Pfades (Programmfluss): Ein Problem der WCET-Analyse ist es, den längsten Weg bezüglich der Laufzeit des Sourcecodes herauszufinden. Ein gutes Beispiel dafür sind Schleifen, die nach Abhängigkeit der Eingabe eine andere Ausführungszeit benötigen. Hierbei muss jeder Eingabefall durchgespielt werden. Allerdings ist das bei komplexeren Systemen unmöglich, weil es zu viele verschiedene Eingabemöglichkeiten gibt.

Übersetzung vom Sourcecode in den Maschinencode: Wenn der Pfad bekannt ist, kann der Sourcecode in den Maschinencode übersetzt werden. Das Problem in diesem Fall ist, dass bei neuen Übersetzern sich auch der Programmfluss im Maschinencode ändert. Daraus folgt dann, dass der gefundene Programmfluss mit übersetzt werden muss, damit er mit dem Maschinencode übereinstimmt.

Maschinencodeanalyse: Die Dauer der Ausführung ist auch von der verwendeten Hardware abhängig. Der Cache und die Befehlspipelines bestimmen den Zustand der Hardware. Dabei hängt der Cache wieder vom gesamten bis dahin ausgeführten Programm ab. Es kann somit nicht angenommen werden, dass kein Cache existiert. Des Weiteren können auch keine statischen Werte verwendet werden, da sonst die WCET zu ungenau werden würde.

Lösungsansätze der Probleme Bearbeiten

Es gibt Lösungsansätze für jedes der drei Probleme, die bei der WCET-Analyse auftreten.

Programmflussanalyse: bei der Programmflussanalyse gibt es mehrere Lösungsansätze. Einer davon wäre, Programmiersprachen zu verwenden, die keinen unüberschaubaren Code erlauben, wie z. B. Rekursionen oder zeitlich unbegrenzt laufende Schleifen. Ein anderer Lösungsansatz wäre es, dem Programmierer im Sourcecode eine Möglichkeit zu geben, Informationen über den Sourcecode zu vermerken. Für diesen Vorschlag müsste jedoch ein spezieller Compiler entwickelt und verwendet werden. Falls man keine speziellen Compiler dafür verwenden will, kann der Programmierer auch seine Informationen außerhalb des Sourcecodes in einer Beschreibungssprache angeben. Eine Bestimmung der Ausführungszeit ist aber nur auf Maschinencodeebene möglich. Somit muss ein WCET-Analyse Tool eine Abbildung von Sourcecodeannotationen auf Maschinencode vornehmen, was nur unter genauer Kenntnis des Compilerverhaltens möglich ist. Dies erfordert eine enge Zusammenarbeit mit dem Analysetool- und Compilerhersteller.

Übersetzung vom Sourcecode in den Maschinencode: das größte Problem liegt jedoch in der Umwandlung des Programmflusses des Sourcecodes in den Programmfluss des Maschinencodes. Ein Lösungsansatz in diesem Fall wäre es, den Programmfluss erst im Maschinencode zu ermitteln. Dadurch fällt die Übersetzung weg. Jedoch ist diese Variante nur schwer lösbar, da der Maschinencode schwer lesbar ist. Die Qualität der WCET-Abschätzung leidet auch darunter, da genaue Informationen zur Ausführungszeit nur im Sourcecode vermerkt werden können.

Maschinencodeanalyse: Einer der sichersten Ansätze um die WCET zu ermitteln ist es, immer einen Cache-Miss anzunehmen, bis die Variable im Datencache steht. Bei der Maschinencodeanalyse wird die Zeit einzelner Befehle und die Beeinflussung anderer Befehle bestimmt. Meistens ist bekannt, wie lange ein Prozessor benötigt, um bestimmte Befehle abzuarbeiten.

Berechnungsmethoden Bearbeiten

Die Berechnung der WCET erfolgt aus den Informationen aus Maschinencodeanalyse und Programmflussanalyse. Es gibt verschiedene Möglichkeiten, die WCET zu berechnen. Bei der pfadbasierenden Methode werden alle möglichen Pfade im Programm ermittelt und ihre Ausführungszeit berechnet. Danach wird das Maximum der Ausführungszeit ermittelt. Eine weitere Methode zur Berechnung der WCET ist die baumbasierende Methode. Hierbei wird das gesamte Programm durch einen Parse-Baum ersetzt. Dann wird zu jeder Gruppe von Befehlen eine Ausführungszeit ermittelt. Mit dieser Methode können Programmflussinformationen nur schwer eingebaut werden. Die letzte Methode verwendet einen Integer-Linear-Programm-Solver. Bei dieser Methode wird in jeder möglichen Programmverzweigung eine Integervariable angegeben. Diese Variable erfasst, wie oft der bestimmte Codeteil ausgeführt wurde. Die Zeit für einen bestimmten Pfad im Programm wurde durch die Maschinencodeanalyse ermittelt. Mit dieser Methode wird zusätzlich auch noch der längste Pfad ermittelt.

Liste von Maximale-Laufzeit-Analyse-Tools Bearbeiten

  • RapiTime
  • Bound-T
  • aiT
  • OTAWA

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström: The Determination of Worst-Case Execution Times-Overview of the Methods and Survey of Tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3), 2008.

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die maximale Laufzeit oder maximale Ausfuhrungszeit englisch Worst Case Execution Time WCET gibt die langste Zeit an die ein Computerprogramm oder Programmteil auf einer bestimmten Plattform zur Ausfuhrung benotigen kann Sie wird bestimmt durch die Programmlogik Kontrollflussgraph die Eingabedaten Auswirkungen auf Schleifendurchlaufzahlen etc den Compiler Optimierungsstufe und die Architektur und Taktfrequenz des Ausfuhrungsrechners Ausfuhrungsgeschwindigkeit unter Berucksichtigung von Cache und Pipelining Effekten Die Kenntnis der WCET oder zumindest einer sicheren oberen Schranke ist ein notwendiges Kriterium zur Implementierung eines harten Echtzeitsystems Bei Echtzeitsystemen ist es sehr wichtig das logisch richtige Ergebnis zu exakten Zeitpunkten zu erhalten Nur kurze Verzogerungen konnten katastrophale Auswirkungen haben Die wichtigsten Anwendungsgebiete fur Echtzeitsysteme sind z B Autoairbagsteuerungen Flugzeugsteuerungen Steuerungen in Kraftwerken Bei Autosteuerungen kann das verspatete Herausschleudern des Airbags todliche Folgen fur die Insassen des Kraftfahrzeuges haben Daher ist es wichtig dass Echtzeitsysteme das richtige Ergebnis in einer bestimmten Zeit bereitstellen Inhaltsverzeichnis 1 Die Ausfuhrungszeit 2 Grundsatzliche Probleme der Laufzeitbestimmung 2 1 Theoretische Grenzen 2 2 Praktische Probleme 3 Methoden zur Bestimmung 3 1 Messbasierte Ansatze 3 2 WCET Analyse 3 2 1 Probleme bei der WCET Analyse 3 2 2 Losungsansatze der Probleme 3 2 3 Berechnungsmethoden 4 Liste von Maximale Laufzeit Analyse Tools 5 Siehe auch 6 Literatur 7 WeblinksDie Ausfuhrungszeit BearbeitenGrundsatzlich wird zwischen BCET best case execution time und WCET worst case execution time unterschieden Die BCET ist die schnellste Ausfuhrungsdauer indem das Programm ein Ergebnis liefert d h das Programm kann unter keinen Umstanden schneller ausgefuhrt werden Die WCET ist die langstmogliche Ausfuhrungsdauer in der der Programmcode ein Ergebnis bereitstellt Grundsatzliche Probleme der Laufzeitbestimmung BearbeitenTheoretische Grenzen Bearbeiten Im allgemeinen Fall ist es unmoglich die maximale Ausfuhrungszeit fur ein beliebiges Programm zu bestimmen Um die maximale Ausfuhrungszeit zu bestimmen musste man folgendes Problem losen Gegeben ist ein Programm P Gesucht ist ein weiteres Programm WCET das die maximale Ausfuhrungszeit von P also WCET P berechnet Da alle jene Programme die in eine Endlosschleife laufen eine maximale Ausfuhrungszeit displaystyle infty nbsp haben konnte man das Programm WCET benutzen um zu entscheiden ob das zugrundeliegende Programm uberhaupt terminiert und somit das Halteproblem losen Das Halteproblem ist jedoch nachweislich unentscheidbar somit kann es das Programm WCET nicht geben Eine Obergrenze der WCET kann aber fur eine relevante Untermenge aller moglichen Programme bestimmt werden Praktische Probleme Bearbeiten Die Schedulingstrategien moderner Betriebssysteme verhindern eine zuverlassige Voraussage zu welchem Zeitpunkt ein Task dran kommt Abhilfe schaffen hier Echtzeitbetriebssysteme oder Direktimplementierungen ohne Betriebssystemschicht Auf modernen Prozessorarchitekturen hangt die Ausfuhrungszeit eines Tasks mitunter stark von dem Zustand des Prozessorcaches ab Selbst bei Verwendung eines Echtzeitbetriebssystems kann es so zu Beeinflussungen zweier Tasks uber den Cache kommen Methoden zur Bestimmung BearbeitenEs gibt verschiedene Methoden die WCET zu berechnen die sich allerdings nur durch Genauigkeit und Anwendbarkeit unterscheiden Eine wichtige Bedeutung ist es wie genau die WCET abgeschatzt werden kann Die Methoden versuchen daher so nahe wie moglich an die wirkliche Ausfuhrungszeit heranzukommen das Ergebnis darf aber nie kleiner als die tatsachliche Ausfuhrungszeit sein Eine Moglichkeit zur Abschatzung der WCET sind Messmethoden Bei diesen Methoden wird durch verschiedenste Testlaufe auf der Zielhardware die Zeit gemessen welche der Code benotigt um ein Ergebnis zu liefern Diese Methode ist sehr aufwandig da nie alle Zustande getestet werden konnen Kombinatorische Explosion Bei der WCET Analyse wird hingegen der langste Ausfuhrungsweg ermittelt und die Ausfuhrungszeit fur eine bestimmte Zielhardware so errechnet Messbasierte Ansatze Bearbeiten Die messbasierten Ansatze fuhren statt einer Analyse des Codes das Programm einfach auf der Zielhardware aus und messen die Ausfuhrungszeit Messbasierte Ansatze fuhren jedoch im Allgemeinen zu einer Unterschatzung der WCET da die Ausfuhrungszeit von Programmen generell von den Eingabedaten abhangt Durch Analyse des Sourcecodes konnen jedoch Eingabedatensatze erzeugt werden welche alle Pfade des zu testenden Programms abdecken Diese Methode vereinfacht zwar die Portierung einer Software leidet aber ebenfalls unter komplexen Prozessorarchitekturen WCET Analyse Bearbeiten Die WCET Analyse berechnet den schlechtesten Fall der Ausfuhrungszeit eines bestimmten Codes einer Anwendung jedoch besteht keine Garantie der Richtigkeit der Ergebnisse des Codes Weiter ist die WCET vom Programmcode und von der zugrundeliegenden Hardware abhangig d h verschiedene Programmcodes haben auf verschiedenen Rechnerarchitekturen unterschiedliche Worst Case Execution Times Daher sollte die Analyse immer mit den Hardwarekomponenten durchgefuhrt werden die auch das Zielsystem besitzt Bei dieser Methode wird der Programmcode untersucht und der tatsachlich langste Ausfuhrungsweg ermittelt Dann addiert man die benotigten Prozessorzyklen aller im Pfad befindlichen Maschinencodebefehle und man erhalt die WCET Probleme bei der WCET Analyse Bearbeiten Es gibt drei Problemdomanen bei der WCET Analyse Einerseits das Herausfinden des auszufuhrenden Pfades die Ubersetzung des Sourcecodes in den Maschinencode und die Maschinencodeanalyse Bestimmung des auszufuhrenden Pfades Programmfluss Ein Problem der WCET Analyse ist es den langsten Weg bezuglich der Laufzeit des Sourcecodes herauszufinden Ein gutes Beispiel dafur sind Schleifen die nach Abhangigkeit der Eingabe eine andere Ausfuhrungszeit benotigen Hierbei muss jeder Eingabefall durchgespielt werden Allerdings ist das bei komplexeren Systemen unmoglich weil es zu viele verschiedene Eingabemoglichkeiten gibt Ubersetzung vom Sourcecode in den Maschinencode Wenn der Pfad bekannt ist kann der Sourcecode in den Maschinencode ubersetzt werden Das Problem in diesem Fall ist dass bei neuen Ubersetzern sich auch der Programmfluss im Maschinencode andert Daraus folgt dann dass der gefundene Programmfluss mit ubersetzt werden muss damit er mit dem Maschinencode ubereinstimmt Maschinencodeanalyse Die Dauer der Ausfuhrung ist auch von der verwendeten Hardware abhangig Der Cache und die Befehlspipelines bestimmen den Zustand der Hardware Dabei hangt der Cache wieder vom gesamten bis dahin ausgefuhrten Programm ab Es kann somit nicht angenommen werden dass kein Cache existiert Des Weiteren konnen auch keine statischen Werte verwendet werden da sonst die WCET zu ungenau werden wurde Losungsansatze der Probleme Bearbeiten Es gibt Losungsansatze fur jedes der drei Probleme die bei der WCET Analyse auftreten Programmflussanalyse bei der Programmflussanalyse gibt es mehrere Losungsansatze Einer davon ware Programmiersprachen zu verwenden die keinen unuberschaubaren Code erlauben wie z B Rekursionen oder zeitlich unbegrenzt laufende Schleifen Ein anderer Losungsansatz ware es dem Programmierer im Sourcecode eine Moglichkeit zu geben Informationen uber den Sourcecode zu vermerken Fur diesen Vorschlag musste jedoch ein spezieller Compiler entwickelt und verwendet werden Falls man keine speziellen Compiler dafur verwenden will kann der Programmierer auch seine Informationen ausserhalb des Sourcecodes in einer Beschreibungssprache angeben Eine Bestimmung der Ausfuhrungszeit ist aber nur auf Maschinencodeebene moglich Somit muss ein WCET Analyse Tool eine Abbildung von Sourcecodeannotationen auf Maschinencode vornehmen was nur unter genauer Kenntnis des Compilerverhaltens moglich ist Dies erfordert eine enge Zusammenarbeit mit dem Analysetool und Compilerhersteller Ubersetzung vom Sourcecode in den Maschinencode das grosste Problem liegt jedoch in der Umwandlung des Programmflusses des Sourcecodes in den Programmfluss des Maschinencodes Ein Losungsansatz in diesem Fall ware es den Programmfluss erst im Maschinencode zu ermitteln Dadurch fallt die Ubersetzung weg Jedoch ist diese Variante nur schwer losbar da der Maschinencode schwer lesbar ist Die Qualitat der WCET Abschatzung leidet auch darunter da genaue Informationen zur Ausfuhrungszeit nur im Sourcecode vermerkt werden konnen Maschinencodeanalyse Einer der sichersten Ansatze um die WCET zu ermitteln ist es immer einen Cache Miss anzunehmen bis die Variable im Datencache steht Bei der Maschinencodeanalyse wird die Zeit einzelner Befehle und die Beeinflussung anderer Befehle bestimmt Meistens ist bekannt wie lange ein Prozessor benotigt um bestimmte Befehle abzuarbeiten Berechnungsmethoden Bearbeiten Die Berechnung der WCET erfolgt aus den Informationen aus Maschinencodeanalyse und Programmflussanalyse Es gibt verschiedene Moglichkeiten die WCET zu berechnen Bei der pfadbasierenden Methode werden alle moglichen Pfade im Programm ermittelt und ihre Ausfuhrungszeit berechnet Danach wird das Maximum der Ausfuhrungszeit ermittelt Eine weitere Methode zur Berechnung der WCET ist die baumbasierende Methode Hierbei wird das gesamte Programm durch einen Parse Baum ersetzt Dann wird zu jeder Gruppe von Befehlen eine Ausfuhrungszeit ermittelt Mit dieser Methode konnen Programmflussinformationen nur schwer eingebaut werden Die letzte Methode verwendet einen Integer Linear Programm Solver Bei dieser Methode wird in jeder moglichen Programmverzweigung eine Integervariable angegeben Diese Variable erfasst wie oft der bestimmte Codeteil ausgefuhrt wurde Die Zeit fur einen bestimmten Pfad im Programm wurde durch die Maschinencodeanalyse ermittelt Mit dieser Methode wird zusatzlich auch noch der langste Pfad ermittelt Liste von Maximale Laufzeit Analyse Tools BearbeitenRapiTime Bound T aiT OTAWASiehe auch BearbeitenKomplexitatstheorie Landau Notation ZeitkomplexitatLiteratur BearbeitenReinhard Wilhelm Jakob Engblom Andreas Ermedahl Niklas Holsti Stephan Thesing David Whalley Guillem Bernat Christian Ferdinand Reinhold Heckmann Frank Mueller Isabelle Puaut Peter Puschner Jan Staschulat and Per Stenstrom The Determination of Worst Case Execution Times Overview of the Methods and Survey of Tools ACM Transactions on Embedded Computing Systems TECS 7 3 2008 Weblinks BearbeitenHeiko Falk Der WCET Bewusste C Compiler WCC Infoseite uber das Forschungsgebiet und die aktivitat an der TU Dortmund Abgerufen von https de wikipedia org w index php title Maximale Laufzeit amp oldid 237160319