Ist es möglich, statisch vorherzusagen, wann Speicher freigegeben werden soll - nur aus dem Quellcode heraus?

Speicher (und Ressourcensperren) werden an deterministischen Punkten während der Programmausführung an das Betriebssystem zurückgegeben. Der Steuerungsfluss eines Programms allein reicht aus, um zu wissen, wo eine bestimmte Ressource mit Sicherheit freigegeben werden kann. Genau wie ein menschlicher Programmierer weiß, wo er schreiben muss, fclose(file)wenn das Programm damit fertig ist.

GCs lösen dies, indem sie es direkt zur Laufzeit herausfinden, wenn der Steuerungsfluss ausgeführt wird. Die wahre Quelle der Wahrheit über den Kontrollfluss ist jedoch die Quelle. Theoretisch sollte es also möglich sein, free()vor dem Kompilieren zu bestimmen, wo die Aufrufe eingefügt werden sollen, indem die Quelle (oder AST) analysiert wird.

Die Referenzzählung ist ein naheliegender Weg, um dies zu implementieren, aber es ist leicht, Situationen zu begegnen, in denen noch auf Zeiger verwiesen wird (noch im Geltungsbereich), die jedoch nicht mehr benötigt werden. Dadurch wird die Verantwortung für die manuelle Freigabe von Zeigern in die Verantwortung für die manuelle Verwaltung des Bereichs / der Verweise auf diese Zeiger umgewandelt.

Es scheint möglich zu sein, ein Programm zu schreiben, das den Quellcode eines Programms lesen kann und:

1. prognostizieren Sie alle Permutationen des Programmablaufs - mit der gleichen Genauigkeit, mit der Sie die Live-Ausführung des Programms verfolgen
2. Verfolgen Sie alle Verweise auf zugewiesene Ressourcen
3. Durchlaufen Sie für jede Referenz den gesamten nachfolgenden Kontrollfluss, um den frühesten Punkt zu finden, von dem garantiert wird, dass die Referenz niemals dereferenziert wird
4. Fügen Sie an dieser Stelle eine Freigabeanweisung in die Quellcodezeile ein

Gibt es irgendetwas, das dies bereits tut? Ich denke nicht, dass Rust oder C ++ Smart Pointer / RAII dasselbe sind.

Nehmen Sie dieses (erfundene) Beispiel:

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

Wann soll kostenlos angerufen werden? vor malloc und zuweisen resource1können wir nicht, weil es kopiert werden könnte resource2, vor zuweisen resource2können wir nicht, weil wir möglicherweise 2 vom Benutzer zweimal ohne eine dazwischenliegende 1 bekommen haben.

Die einzige Möglichkeit, um sicherzugehen, besteht darin, resource1 und resource2 zu testen, um festzustellen, ob sie in den Fällen 1 und 2 nicht gleich sind, und den alten Wert freizugeben, wenn dies nicht der Fall ist. Dies ist im Wesentlichen die Referenzzählung, wenn Sie wissen, dass es nur 2 mögliche Referenzen gibt.

RAII ist nicht automatisch dasselbe, aber es hat den gleichen Effekt. Es bietet eine einfache Antwort auf die Frage "Woher wissen Sie, wann auf diese nicht mehr zugegriffen werden kann?" Indem der Bereich verwendet wird , um den Bereich abzudecken, in dem eine bestimmte Ressource verwendet wird.

Möglicherweise möchten Sie das ähnliche Problem in Betracht ziehen: "Woher weiß ich, dass in meinem Programm zur Laufzeit kein Typfehler auftritt?". Die Lösung besteht darin, nicht alle Ausführungspfade durch das Programm vorherzusagen, sondern mithilfe eines Systems mit Typanmerkungen und Schlussfolgerungen zu beweisen, dass es keinen solchen Fehler geben kann. Rust ist ein Versuch, diese Proof-Eigenschaft auf die Speicherzuordnung auszudehnen.

Es ist möglich, Beweise über das Programmverhalten zu schreiben, ohne das Halteproblem lösen zu müssen, aber nur, wenn Sie Anmerkungen verwenden, um das Programm einzuschränken. Siehe auch Sicherheitsnachweise (sel4 etc.)

Ja, das gibt es in freier Wildbahn. Das ML Kit ist ein Compiler in Produktionsqualität, der die beschriebene Strategie (mehr oder weniger) als eine der verfügbaren Speicherverwaltungsoptionen verwendet. Sie können auch einen herkömmlichen GC verwenden oder mit Referenzzählung hybridisieren (Sie können einen Heap-Profiler verwenden, um festzustellen, welche Strategie tatsächlich die besten Ergebnisse für Ihr Programm liefert).

Eine Retrospektive zum region-based Memory Management ist ein Artikel der Originalautoren des ML Kits, der sich mit seinen Erfolgen und Misserfolgen befasst. Die Schlussfolgerung ist, dass die Strategie praktisch ist, wenn mit Hilfe eines Heap-Profilers geschrieben wird.

(Dies ist ein gutes Beispiel dafür, warum Sie sich normalerweise nicht mit dem Problem des Anhaltens befassen sollten, um Antworten auf praktische technische Fragen zu erhalten: Wir möchten oder müssen den allgemeinen Fall für die meisten realistischen Programme nicht lösen.)

prognostizieren Sie alle Permutationen des Programmablaufs

Hier liegt das Problem. Die Anzahl der Permutationen ist für jedes nicht-triviale Programm so groß (in der Praxis unendlich), dass die benötigte Zeit und der benötigte Speicher dies völlig unpraktisch machen würden.

Das Stopp-Problem beweist, dass dies nicht in allen Fällen möglich ist. Es ist jedoch in vielen Fällen immer noch möglich und wird in der Tat von fast allen Compilern für wahrscheinlich die Mehrheit der Variablen durchgeführt. Auf diese Weise kann ein Compiler feststellen, dass es sicher ist, lediglich eine Variable auf dem Stack oder sogar ein Register zuzuweisen, anstatt einen längerfristigen Heap-Speicher zu verwenden.

Wenn Sie reine Funktionen oder eine wirklich gute Besitzersemantik haben, können Sie diese statische Analyse weiter ausbauen, obwohl dies mit zunehmender Verzweigung Ihres Codes unerschwinglich teurer wird.

Wenn ein einzelner Programmierer oder ein einzelnes Team das gesamte Programm schreibt, ist es sinnvoll, Entwurfspunkte zu identifizieren, an denen Speicher (und andere Ressourcen) freigegeben werden sollen. Daher kann eine statische Analyse des Entwurfs in eingeschränkteren Kontexten ausreichend sein.

Wenn Sie jedoch DLLs, APIs, Frameworks von Drittanbietern (und Threads ebenfalls einbeziehen), kann es für die benutzenden Programmierer sehr schwierig (ja unmöglich in allen Fällen) sein, richtig zu urteilen, welche Entität welchen Speicher besitzt und wenn der letzte Gebrauch davon ist. Unser gewöhnlicher Sprachverdacht dokumentiert die Übertragung des Speichereigentums an Objekten und Arrays, flach und tief, nicht ausreichend. Wenn ein Programmierer darüber nicht nachdenken kann (statisch oder dynamisch!), Kann ein Compiler dies höchstwahrscheinlich auch nicht. Dies ist wiederum auf die Tatsache zurückzuführen, dass Speichereigentumsübertragungen nicht in Methodenaufrufen oder durch Schnittstellen usw. erfasst werden. Daher ist es nicht möglich, statisch vorherzusagen, wann oder wo im Code Speicher freigegeben werden soll.

Da dies ein so schwerwiegendes Problem ist, entscheiden sich viele moderne Sprachen für die Garbage Collection, bei der der Speicher einige Zeit nach der letzten Live-Referenz automatisch wiederhergestellt wird. GC hat erhebliche Leistungskosten (insbesondere für Echtzeitanwendungen), ist also kein Allheilmittel. Außerdem kann es mit GC immer noch zu Speicherverlusten kommen (z. B. eine Sammlung, die nur wächst). Trotzdem ist dies eine gute Lösung für die meisten Programmierübungen.

Es gibt einige Alternativen (einige entstehen).

Die Rust-Sprache bringt RAII auf ein Extrem. Es bietet sprachliche Konstrukte, die die Übertragung von Eigentumsrechten in Methoden von Klassen und Schnittstellen detaillierter definieren, z. B. Objekte, die zwischen einem Aufrufer und einem Angerufenen übertragen werden, oder Objekte mit längerer Lebensdauer. Es bietet ein hohes Maß an Sicherheit bei der Kompilierung in Bezug auf die Speicherverwaltung. Es ist jedoch keine triviale Sprache und auch nicht ohne Probleme (z. B. glaube ich nicht, dass das Design vollständig stabil ist, bestimmte Dinge noch experimentiert werden und sich daher ändern).

Swift und Objective-C gehen eine weitere Route, bei der es sich zumeist um eine automatische Referenzzählung handelt. Die Referenzzählung stößt auf Probleme mit Zyklen, und es gibt beispielsweise erhebliche Herausforderungen für Programmierer, insbesondere bei Abschlüssen.

Wenn ein Programm von keiner unbekannten Eingabe abhängt, sollte dies möglich sein (mit der Einschränkung, dass es sich um eine komplexe Aufgabe handelt und lange dauern kann; dies gilt jedoch auch für das Programm). Solche Programme wären zum Zeitpunkt der Kompilierung vollständig lösbar. in C ++ könnten sie (fast) vollständig aus constexprs bestehen. Einfache Beispiele wären, die ersten 100 Stellen von pi zu berechnen oder ein bekanntes Wörterbuch zu sortieren.

Das Freigeben von Speicher entspricht im Allgemeinen dem Problem des Anhaltens. Wenn Sie nicht statisch feststellen können, ob ein Programm anhält (statisch), können Sie auch nicht feststellen, ob es Speicher freigibt (statisch).

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

Trotzdem ist Rust sehr nett ... https://doc.rust-lang.org/book/ownership.html