Laufzeit (Informatik)

Der Begriff Laufzeit beschreibt in der Informatik im Wesentlichen die Zeitspanne, während der ein Programm von einem Rechner ausgeführt wird. Die Länge dieser Zeitspanne lässt sich aber häufig nur durch Ausprobieren bestimmen. Jeder Befehl eines Programms in einer Hochsprache wie z. B. Java wird vom Compiler in eine unbekannte Anzahl von Maschinenbefehlen übersetzt. Die Ausführung eines Befehls kann, je nach Hardware, weitere Verzögerungen ergeben – wenn z. B. Daten zwischen Hauptspeicher und Cache (das ist auf der ersten Ebene ein in die CPU eingebauter, sehr kleiner Zwischenspeicher für sehr oft benötigte Daten; auf tieferen Ebenen ist es ein spezieller Speicher auf dem Mainboard ("second-level-cache")) ausgetauscht werden, oder wenn die Daten erst von der Festplatte wieder in den Speicher eingelagert werden müssen (Paging). Weitere Abhängigkeiten ergeben sich von Betriebssystem, CPU-Taktrate, Größe des Hauptspeichers, Übertragungsrate des internen Bus-Systems (leitet Daten zwischen den diversen Bestandteilen eines PCs hin und her), und so weiter und so fort.

In der Informatik versucht man daher gar nicht mehr, konkret auszurechnen, dass ein Programm auf einem ganz bestimmten PC 0,128 Sekunden lang ausgeführt wird. Stattdessen liefert die "O-Notation", auch Landau-Notation genannt, immerhin eine ungefähre Angabe, wieviel Zeit zwischen Programmstart und -ende vergehen würde (vgl. hierzu Asymptotische Laufzeit). Diese Größe beachtet keine Einflussgrößen außer der Eingabegröße mehr, und beschreibt ein ungefähres Wachstumsverhalten der Laufzeit für größere Eingaben.

Einige Beispiele anhand eines Programms, das n Zahlen sortiert:

"O (n)" beschreibt ein lineares Wachstum der Eingabe. Solch ein Programm macht pro eingegebener Zahl nur eine konstante Anzahl von Rechenschritten.
"O (n²)" bedeutet quadratisches Wachstum. Das Sortierprogramm macht pro eingegebener Zahl eine konstante Anzahl von Durchläufen durch die ganze Liste; die Laufzeit insgesamt ist ein Wert in der Größenordnung x · n² + y · n + z, wobei sich allerdings x, y und z nicht exakt bestimmen lassen.
"O (2ⁿ)" würde schließlich exponentielles Wachstum bedeuten. Im Beispiel des Sortierprogramms würde sich mit jeder weiteren Zahl die Laufzeit (ungefähr) verdoppeln, was bereits bei 100 Zahlen mehrere hundert Millionen Jahre dauern kann. Solch einen Zeitverbrauch erreicht ein Sortierprogramm beispielsweise, indem es alle möglichen Reihenfolgen der Zahlen daraufhin testet, ob sie sortiert sind.

Verfahren mit exponentieller Laufzeit versucht man daher nach Möglichkeit zu vermeiden – ob das überhaupt geht, ist eine der Fragen, die man sich in der Theoretischen Informatik stellt (vgl. dazu Komplexitätstheorie, "NP-vollständige" Probleme (NP-vollständig). Angestrebt werden Verfahren mit polynomieller Laufzeit, also salopp gesagt "n hoch irgendwas". Man beachte dabei, dass ein Programm im Grunde dreigeteilt ist – Eingabe, Verarbeitung, Ausgabe – und dass sich nur der mittlere Teil in dieser Hinsicht optimieren lässt.

Laufzeitfehler

Im Zusammenhang mit Softwareentwicklung hat sich hier der leicht umgangssprachliche Begriff von "Laufzeitfehlern" eingebürgert. Darunter werden Fehler verstanden, die sich erst bemerkbar machen, während das Programm ausgeführt wird. Eine Anweisung wie "a = b/c", die b durch c dividieren und das Ergebnis in a speichern soll, mag syntaktisch korrekt sein und wird deshalb auch vom Compiler nicht als Fehler markiert. Kritisch wird die Situation dann, wenn c zu diesem Zeitpunkt den Wert 0 enthält.

Es gibt hier zwei Arten von "Laufzeitfehlern":

Der Typ, den das Programm berücksichtigen kann.
Den Typ, den der beste Programmierer der Welt nicht berücksichtigen kann.

Zur ersten Kategorie gehören beispielsweise folgende Fehler:

Division durch Null
Verwendung von Objektverweisen, die bisher nicht auf ein Objekt verweisen, sondern auf "gar nichts" (z. B. Nullpointer in C)
fehlerhafte Speicherreservierung – tritt vor allem bei älteren Programmiersprachen auf, bei denen der Programmierer nicht mehr benötigten Speicher selbst wieder freigeben musste; moderne Programmiersprachen wie Java oder VB.NET erledigen das im Hintergrund durch ihre Automatische Speicherbereinigung.
fehlende Dateien, aus denen das Programm Daten beziehen soll.
versehentlicher "Angriff" auf einen Server – durch fehlerhafte Programmierung überflutet das Programm einen Server dermaßen mit Anfragen, dass der Server nicht mehr mithalten kann

Falsch berechnete Zwischenergebnisse gehören eher in den Bereich der Fehler, die durch einen falsch programmierten Ablauf entstehen.

Zur zweiten Kategorie gehören unerwartete Änderungen an der verfügbaren Hardware, die das Programm weder testen noch selbst beheben oder umgehen kann:

eine Druckerausgabe wird versucht, der Drucker ist jedoch ausgeschaltet, nicht angeschlossen oder hat kein Papier mehr
Versuch eines Datenbankzugriffs, der Datenbankserver ist jedoch ausgefallen
ein Versuch, Daten auf einem Wechseldatenträger zu speichern, scheitert daran, dass jemand die Diskette aus dem Laufwerk bzw. die DVD aus dem Brenner genommen hat oder dass der Datenträger schreibgeschützt ist.
bei verteilten Anwendungen, wo mehrere Rechner gleichzeitig Teile desselben Programmes ausführen, kann einer der Rechner ausgefallen sein. Dadurch fehlen dem restlichen Programm Berechnungsergebnisse.

Siehe auch

Programmierung

Gourt Home::Gourt :: Laufzeit (Informatik)

Laufzeitfehler

Siehe auch