Kann eine Laufzeitumgebung eine Endlosschleife erkennen?

Wäre es einer Laufzeitumgebung möglich, Endlosschleifen zu erkennen und anschließend den zugehörigen Prozess zu stoppen, oder wäre die Implementierung einer solchen Logik gleichbedeutend mit der Lösung des Halteproblems?

Für den Zweck dieser Frage definiere ich eine "Endlosschleife" als eine Reihe von Anweisungen und zugehörigen Start-Stack- / Heap-Daten, die den Prozess bei der Ausführung auf genau den gleichen Zustand (einschließlich der Daten) wie zuvor zurücksetzen Initiieren der Endlosschleife. (Mit anderen Worten, ein Programm, das eine unendlich lange Dezimalerweiterung von pi erzeugt, bleibt nicht in einer Endlosschleife hängen, weil es bei jeder Iteration mehr Stellen von pi irgendwo im zugehörigen Speicher hat.)

(Portiert von /programming//q/16250472/1858225 )

Es ist theoretisch möglich, dass eine Laufzeitumgebung mit dem folgenden Verfahren nach solchen Schleifen sucht:

Nach jeder ausgeführten Anweisung erstellt die Laufzeitumgebung ein vollständiges Abbild des Status eines laufenden Prozesses (dh des gesamten damit verbundenen Speichers, einschließlich der Register, des PCs, des Stacks, des Heapspeichers und der globalen Speicher), speichert dieses Abbild irgendwo und prüft es dann Überprüfen Sie, ob es mit einem der zuvor gespeicherten Bilder für diesen Vorgang übereinstimmt. Wenn es eine Übereinstimmung gibt, steckt der Prozess in einer Endlosschleife. Andernfalls wird der nächste Befehl ausgeführt und der Vorgang wiederholt.

Anstatt diese Prüfung nach jeder einzelnen Anweisung durchzuführen, könnte die Laufzeitumgebung den Prozess in regelmäßigen Abständen anhalten und einen Sicherungszustand herstellen. Wenn der Prozess in einer Endlosschleife mit n Zuständen steckt , wird nach höchstens n Prüfungen ein doppelter Zustand beobachtet.

Beachten Sie natürlich, dass dies keine Lösung für das Halteproblem ist. Die Unterscheidung wird hier diskutiert .

Ein solches Merkmal wäre jedoch eine enorme Verschwendung von Ressourcen . Wenn ein Prozess ständig angehalten wird, um den gesamten damit verbundenen Speicherplatz zu sparen , wird er enorm verlangsamt und es wird sehr schnell eine enorme Menge an Speicher verbraucht. (Obwohl alte Bilder nach einer Weile gelöscht werden könnten, wäre es riskant, die Gesamtzahl der Bilder zu begrenzen, die gespeichert werden könnten, da eine große Endlosschleife - dh eine mit vielen Zuständen - möglicherweise nicht abgefangen wird, wenn zu wenige vorhanden sind Zustände im Gedächtnis behalten.) Darüber hinaus würde diese Funktion nicht wirklich so viel Nutzen bringen, da ihre Fähigkeit, Fehler abzufangen, extrem eingeschränkt wäre und weil es relativ einfach ist, Endlosschleifen mit anderen Debug-Methoden zu finden (z. B. einfach durch den Code zu gehen und Erkennen des Logikfehlers).

Daher bezweifle ich, dass eine solche Laufzeitumgebung existiert oder jemals existieren wird, es sei denn, jemand programmiert sie nur für Tritte. (Zu was ich jetzt etwas versucht bin.)

Nehmen wir an, das Programm interagiert nicht mit der Außenwelt, so dass es wirklich möglich ist, den gesamten Status des Programms zu kapseln. (Dies bedeutet, dass zumindest keine Eingabe erfolgt.) Nehmen wir außerdem an, dass das Programm in einer deterministischen Umgebung ausgeführt wird, sodass jeder Status einen eindeutigen Nachfolger hat kann deterministisch auf eine Sequenz reduziert werden.

Unter diesen höchst unwahrscheinlichen, aber theoretisch nicht einschränkenden Voraussetzungen können wir das Programm duplizieren und in zwei separaten Laufzeiten ausführen. Jeder führt genau die gleiche Berechnung durch.

Also lass uns das machen. Wir werden es einmal in der Tortoise-Laufzeit ausführen und gleichzeitig in der Hare-Laufzeit. Wir werden jedoch dafür sorgen, dass die Hare-Laufzeit genau doppelt so schnell arbeitet. Jedes Mal, wenn die Tortoise-Laufzeit einen Schritt ausführt, führt die Hare-Laufzeit zwei Schritte aus.

$n$$p$$kn$$k$$kn\ge p$

Die Gesamtkosten des Tests betragen einen zusätzlichen Status und einen Statusvergleich pro Schritt. Der Test wird in höchstens der dreifachen Anzahl von Schritten beendet, die das Programm benötigt, um seine erste Schleife abzuschließen. (Einmal in der Schildkröte und zweimal im Hasen, insgesamt dreimal.)

Wie die von mir verwendeten Begriffe andeuten, handelt es sich nur um Robert Floyds berühmten Algorithmus zur Erkennung von Schildkröten- und Hasen- Zyklen.

Gerade als ich Floyds Zykluserkennungsalgorithmus vorschlagen wollte, schlug mich Ricis Beitrag. Das Ganze kann jedoch praktischer gestaltet werden, indem Vergleiche von Vollzuständen beschleunigt werden.

Der Engpass des vorgeschlagenen Algorithmus wäre der Vergleich des vollständigen Zustands. Diese Vergleiche werden in der Regel nicht beendet, sondern hören früh auf - beim ersten Unterschied. Eine Optimierung besteht darin, sich zu merken, wo die früheren Unterschiede aufgetreten sind, und diese Teile des Zustands zuerst zu überprüfen. Führen Sie beispielsweise eine Liste mit Standorten, und gehen Sie diese Liste durch, bevor Sie einen vollständigen Vergleich durchführen. Wenn ein Ort aus dieser Liste einen Unterschied aufdeckt, stoppen Sie den Vergleich (mit Fehler) und verschieben Sie den Ort an den Anfang der Liste.

Ein anderer (und möglicherweise besser skalierbarer) Ansatz ist die Verwendung von inkrementellem Hashing. Wählen Sie eine Funktion für den vollständigen Status, sodass die Hash-Werte in O (1) leicht angepasst werden können, wenn sich ein Teil des Status ändert. Nehmen Sie zum Beispiel eine gewichtete Summe von Zustandswörtern mit einer großen Primzahl und verknüpfen Sie sie mit der ungewichteten Summe mit einer anderen großen Primzahl (Sie können auch eine modulare gewichtete Summe von Wortquadraten mit unterschiedlicher Gewichtung und unterschiedlichem Modul eingeben). Auf diese Weise dauern Hash-Aktualisierungen bei jedem Ausführungsschritt 0 (1) und Vergleiche 0 (1), bis Sie einen Treffer erhalten. Die Wahrscheinlichkeit eines falschen Positivs (dh die Hashes stimmen überein, während sich die Zustände unterscheiden) ist sehr gering, und selbst wenn dies jemals passiert, wird es sich über eine große Anzahl von echten Negativen amortisieren (falsche Negative sind unmöglich).

Natürlich scheint es in der Praxis wahrscheinlicher zu sein, dass es zu Situationen kommt, in denen Ziffern der Zahl pi generiert werden - Dinge ändern sich ständig, enden aber nie. Eine andere häufige Möglichkeit besteht darin, dass die Endlosschleife Speicher zuweist. In diesem Fall erschöpft sie schnell den gesamten verfügbaren Speicher.

In meinem Kurs über Algorithmen und Datenstrukturen muss sich unser Autograder mit Studentenbeiträgen befassen, die manchmal in Endlosschleifen geraten. Dies wird durch ein 30-Sekunden-Timeout und ein bestimmtes Speicherlimit behoben. Beide sind weitaus lockerer als das Laufzeit- und Speicherbudget, das wir im Rahmen der Einstufung festlegen. Ich bin mir nicht sicher, ob die Implementierung einer echten Endlosschleifenerkennung in diesem Zusammenhang sinnvoll ist, da solche Programme etwas langsamer ausgeführt werden (hier könnte die Hardwareunterstützung für State-Hashing helfen, aber auch hier wären zusätzliche Verwendungszwecke erforderlich) begründen dies). Wenn die Schüler wissen, dass ihr Programm abgelaufen ist, können sie normalerweise die Endlosschleife finden.

Das AProVE- Terminierungstool führt statische Analysen auf Neuschreibsystemen (einschließlich einer Unterklasse von Haskell-Programmen) durch, die sich als nicht terminierend erweisen können. Dies ist ein aktuelles Beispiel für ein nicht terminierendes Programm. Die Technik ist ziemlich leistungsfähig und arbeitet mit einer Variante einer Technik, die als Verengung bezeichnet wird .

Soweit ich weiß, wurde nicht viel daran gearbeitet, die tatsächliche Nichtbeendigung für allgemeine Sprachen festzustellen.