In Sprachen wie C wird vom Programmierer erwartet, dass er Aufrufe an free einfügt. Warum macht der Compiler das nicht automatisch? Menschen tun dies in einer angemessenen Zeitspanne (Ignorieren von Fehlern), so dass es nicht unmöglich ist.
EDIT: Zum späteren Nachschlagen hier noch eine Diskussion, die ein interessantes Beispiel hat.
compilers
memory-management
garbage-collection
Milton Silva
quelle
quelle
Antworten:
Denn es ist nicht zu entscheiden, ob das Programm den Speicher wieder nutzen wird. Dies bedeutet, dass kein Algorithmus
free()
in allen Fällen bestimmen kann, wann er aufgerufen werden soll. Dies bedeutet, dass jeder Compiler, der dies versucht hat, notwendigerweise einige Programme mit Speicherlecks und / oder einige Programme erzeugt, die weiterhin den freigegebenen Speicher verwenden. Selbst wenn Sie sichergestellt haben, dass Ihr Compiler niemals den zweiten Compiler ausgeführt hat und dem Programmierer das Einfügen von Aufrufen zurfree()
Behebung dieser Fehler gestattet hatfree()
, ist es noch schwieriger , zu wissen, wann dieser Compiler aufgerufen werden muss,free()
wenn ein Compiler verwendet wird, der es nicht versucht hat helfen.quelle
free()
richtig einfügt.Wie David Richerby zu Recht feststellte, ist das Problem im Allgemeinen nicht zu entscheiden. Die Objektlebensfähigkeit ist eine globale Eigenschaft des Programms und kann im Allgemeinen von den Eingaben in das Programm abhängen.
Sogar präzise dynamische Speicherbereinigung ist ein unbestreitbares Problem! Alle echten Müllsammler verwenden die Erreichbarkeit als konservative Annäherung an die Frage, ob ein zugewiesenes Objekt in Zukunft benötigt wird oder nicht. Es ist eine gute Annäherung, aber es ist trotzdem eine Annäherung.
Das stimmt aber nur generell. Eine der berüchtigtsten Auseinandersetzungen in der Informatikbranche ist "es ist im Allgemeinen unmöglich, deshalb können wir nichts tun". Im Gegenteil, es gibt viele Fälle, in denen es möglich ist, Fortschritte zu erzielen.
Implementierungen, die auf der Referenzzählung basieren, sind sehr nah an "dem Compiler, der Freigabezuweisungen einfügt", sodass es schwierig ist, den Unterschied zu erkennen. Die automatische Referenzzählung von LLVM (verwendet in Objective-C und Swift ) ist ein berühmtes Beispiel.
Region Inference und Garbage Collection während der Kompilierung sind derzeit aktive Forschungsbereiche. In deklarativen Sprachen wie ML und Merkur gestaltet sich dies wesentlich einfacher , in denen Sie ein Objekt nach seiner Erstellung nicht mehr ändern können .
In Bezug auf Menschen gibt es drei Hauptmethoden, mit denen Menschen die Allokationslebensdauer manuell verwalten können:
quelle
Es ist ein Unvollständigkeitsproblem, kein Unentscheidbarkeitsproblem
Es stimmt zwar, dass die optimale Platzierung von Freigabebescheinigungen nicht zu entscheiden ist, aber das ist hier einfach nicht das Problem. Da dies sowohl für den Menschen als auch für den Compiler unentscheidbar ist, ist es unmöglich, immer wissentlich die optimale Platzierung für die Freigabe auszuwählen, unabhängig davon, ob es sich um einen manuellen oder einen automatischen Prozess handelt. Und da niemand perfekt ist, sollte ein ausreichend fortgeschrittener Compiler in der Lage sein, Menschen zu übertreffen, um annähernd optimale Platzierungen zu erraten. Also, Unentscheidbarkeit ist nicht , warum wir explizite Freigabe Aussagen müssen .
Es gibt Fälle, in denen externes Wissen die Platzierung von Freigabeerklärungen beeinflusst. Das Entfernen dieser Anweisungen entspricht dann dem Entfernen eines Teils der Betriebslogik, und das Auffordern eines Compilers, diese Logik automatisch zu generieren, entspricht dem Auffordern, zu erraten, was Sie denken.
Angenommen, Sie schreiben eine Read-Evaluate-Print-Loop (REPL). : Der Benutzer gibt einen Befehl ein und Ihr Programm führt ihn aus. Der Benutzer kann Speicher zuweisen / freigeben, indem er Befehle in Ihren REPL eingibt. Ihr Quellcode würde angeben, was die REPL für jeden möglichen Benutzerbefehl tun soll, einschließlich der Freigabe, wenn der Benutzer den Befehl dafür eingibt.
Wenn der C-Quellcode jedoch keinen expliziten Befehl für die Freigabe der Zuweisung bereitstellt, muss der Compiler darauf schließen, dass er die Zuweisung durchführen soll, wenn der Benutzer den entsprechenden Befehl in REPL eingibt. Ist dieser Befehl "freigeben", "frei" oder etwas anderes? Der Compiler kann nicht wissen, wie der Befehl lauten soll. Selbst wenn Sie in der Logik programmieren, um nach diesem Befehlswort zu suchen, und die REPL es findet, kann der Compiler nicht wissen, dass es mit Freigabe reagieren soll, es sei denn, Sie weisen es ausdrücklich im Quellcode an.
tl; dr Das Problem istCode CQuelle nicht den Compiler mit externem Wissen zur Verfügung stellen. Unentscheidbarkeit ist nicht das Problem, da es dort ist, ob der Prozess manuell oder automatisiert ist.
quelle
Derzeit ist keine der angegebenen Antworten vollständig korrekt.
Einige tun. (Ich erkläre es später.)
Trivialerweise können Sie
free()
kurz vor dem Beenden des Programms aufrufen . In Ihrer Frage besteht jedoch die implizite Notwendigkeit,free()
so schnell wie möglich anzurufen .Das Problem, wann
free()
ein C-Programm aufgerufen werden muss, sobald der Speicher nicht erreichbar ist, ist nicht zu lösen, dh für jeden Algorithmus, der die Antwort in endlicher Zeit liefert, gibt es einen Fall, den es nicht abdeckt. Dies und viele andere Unentscheidbarkeiten willkürlicher Programme lassen sich anhand des Halteproblems nachweisen .Ein unentscheidbares Problem kann nicht immer in endlicher Zeit von jedem Algorithmus gelöst werden, sei es von einem Compiler oder von einem Menschen.
Menschen (versuchen es), in eine Teilmenge von C-Programmen zu schreiben , die durch ihren Algorithmus (selbst) auf Speicherrichtigkeit überprüft werden können.
Einige Sprachen erreichen die Nummer 1, indem sie die Nummer 5 in den Compiler einbauen. Sie erlauben keine Programme mit willkürlicher Verwendung der Speicherzuordnung, sondern eine entscheidbare Teilmenge davon. Foth und Rust sind zwei Beispiele für Sprachen mit einer restriktiveren Speicherzuordnung als C
malloc()
, die (1) erkennen können, ob ein Programm außerhalb ihrer entscheidbaren Menge geschrieben wurde. (2) Aufhebungszuordnungen automatisch einfügen.quelle
"Menschen tun es, also ist es nicht unmöglich" ist ein bekannter Irrtum. Wir verstehen die Dinge, die wir erschaffen, nicht unbedingt (geschweige denn kontrollieren) - Geld ist ein weit verbreitetes Beispiel. Wir neigen dazu, unsere Erfolgsaussichten in technologischen Fragen (manchmal dramatisch) zu überschätzen, insbesondere wenn menschliche Faktoren fehlen.
Die menschlichen Leistungen in der Computerprogrammierung sind sehr schlecht , und das Studium der Informatik (das in vielen Berufsbildungsprogrammen fehlt) hilft zu verstehen, warum dieses Problem nicht einfach behoben werden kann. Wir könnten eines Tages, vielleicht nicht zu weit entfernt, durch künstliche Intelligenz am Arbeitsplatz ersetzt werden. Selbst dann wird es keinen allgemeinen Algorithmus geben, mit dem die Zuordnung automatisch aufgehoben wird.
quelle
Das Fehlen einer automatischen Speicherverwaltung ist ein Merkmal der Sprache.
C soll kein Werkzeug zum einfachen Schreiben von Software sein. Es ist ein Tool, mit dem Sie den Computer dazu bringen, das zu tun, was Sie ihm sagen. Dazu gehört das Zuweisen und Aufheben der Speicherzuweisung zum Zeitpunkt Ihrer Wahl. C ist eine einfache Sprache, die Sie verwenden, wenn Sie den Computer präzise steuern möchten oder wenn Sie Dinge auf eine andere Weise tun möchten, als von den Entwicklern der Sprache / Standardbibliothek erwartet.
quelle
Das Problem ist meist ein historisches Artefakt, keine Unmöglichkeit der Implementierung.
Die Art und Weise, wie die meisten C-Compiler Code erstellen, ist so, dass der Compiler nur jede Quelldatei gleichzeitig sieht. es sieht nie das ganze Programm auf einmal. Wenn eine Quelldatei eine Funktion aus einer anderen Quelldatei oder einer Bibliothek aufruft, sieht der Compiler nur die Headerdatei mit dem Rückgabetyp der Funktion und nicht den tatsächlichen Code der Funktion. Das heißt, wenn es eine Funktion gibt, die einen Zeiger zurückgibt, kann der Compiler nicht feststellen, ob der Speicher, auf den der Zeiger zeigt, freigegeben werden muss oder nicht. Die zu entscheidenden Informationen werden dem Compiler zu diesem Zeitpunkt nicht angezeigt. Dem menschlichen Programmierer steht es frei, den Quellcode der Funktion oder die Dokumentation nachzuschlagen, um herauszufinden, was mit dem Zeiger zu tun ist.
Wenn Sie sich mit modernen Low-Level-Sprachen wie C ++ 11 oder Rust beschäftigen, werden Sie feststellen, dass diese das Problem meistens gelöst haben, indem Sie den Speichertyp explizit in den Zeigertyp aufnehmen. In C ++ würden Sie a
unique_ptr<T>
anstelle einer Ebene verwendenT*
, um den Speicher zu speichern. Dadurchunique_ptr<T>
wird sichergestellt, dass der Speicher freigegeben wird, wenn das Objekt im Gegensatz zur Ebene das Ende des Gültigkeitsbereichs erreichtT*
. Der Programmierer kann den Speicher von einemunique_ptr<T>
zum anderen übergeben, aber es kann immer nur einen gebenunique_ptr<T>
, der auf den Speicher zeigt. So ist immer klar, wem das Gedächtnis gehört und wann es freigegeben werden muss.C ++ erlaubt aus Gründen der Abwärtskompatibilität immer noch die manuelle Speicherverwaltung im alten Stil und damit die Erzeugung von Fehlern oder Möglichkeiten, um den Schutz von a zu umgehen
unique_ptr<T>
. Rust ist insofern noch strenger, als es durch Compiler-Fehler die Regeln für den Speichereigentum erzwingt.Was die Unentscheidbarkeit, das Problem des Anhaltens und dergleichen betrifft, ist es nicht möglich, für alle Programme zu entscheiden, wann der Speicher freigegeben werden soll, wenn Sie sich an die C-Semantik halten. Für die meisten aktuellen Programme, nicht für akademische Übungen oder Buggy-Software, wäre es jedoch absolut möglich zu entscheiden, wann und wann nicht. Das ist schließlich der einzige Grund, warum der Mensch herausfinden kann, wann er sich überhaupt befreien soll oder nicht.
quelle
Andere Antworten haben sich darauf konzentriert, ob es möglich ist, Speicherbereinigungen durchzuführen, einige Details darüber, wie es gemacht wird, und einige der Probleme.
Ein Thema, das noch nicht behandelt wurde, ist die unvermeidliche Verzögerung bei der Müllabfuhr. Wenn ein Programmierer in C free () aufruft, steht dieser Speicher sofort zur Wiederverwendung zur Verfügung. (Zumindest theoretisch!) So kann ein Programmierer seine 100-MB-Struktur freigeben, eine Millisekunde später eine weitere 100-MB-Struktur zuweisen und davon ausgehen, dass der Gesamtspeicherbedarf gleich bleibt.
Dies gilt nicht für die Garbage Collection. Speicherbereinigte Systeme haben einige Verzögerungen bei der Rückgabe von nicht verwendetem Speicher auf den Heap. Dies kann erheblich sein. Wenn Ihre 100-MB-Struktur den Rahmen verlässt und ein Millisekunden später Ihr Programm eine weitere 100-MB-Struktur einrichtet, können Sie davon ausgehen, dass Ihr System für kurze Zeit 200 MB verwendet. Dieser "kurze Zeitraum" kann je nach System Millisekunden oder Sekunden betragen, es tritt jedoch immer noch eine Verzögerung auf.
Wenn Sie auf einem PC mit viel RAM und virtuellem Speicher arbeiten, werden Sie dies wahrscheinlich nie bemerken. Wenn Sie jedoch auf einem System mit begrenzteren Ressourcen (z. B. einem eingebetteten System oder einem Telefon) arbeiten, müssen Sie dies ernst nehmen. Dies ist nicht nur theoretisch - ich persönlich habe gesehen, dass dies Probleme verursacht (wie z. B. beim Absturz des Geräts), wenn auf einem WinCE-System mit .NET Compact Framework gearbeitet und in C # entwickelt wurde.
quelle
Die Frage geht davon aus, dass der Programmierer eine Freigabe aus anderen Teilen des Quellcodes ableiten soll. Es ist nicht. "Zu diesem Zeitpunkt im Programm ist die Speicherreferenz FOO nicht mehr nützlich" sind Informationen, die nur dem Programmierer bekannt sind bis sie in (in prozeduralen Sprachen) eine Freigabeanweisung codiert sind.
Es unterscheidet sich theoretisch nicht von anderen Codezeilen. Warum fügen Compiler nicht automatisch "An dieser Stelle im Programm das Register BAR auf Eingabe prüfen" oder "Wenn der Funktionsaufruf ungleich Null zurückgibt, das aktuelle Unterprogramm verlassen" ein ? Aus der Sicht des Compilers ist der Grund "Unvollständigkeit", wie in dieser Antwort gezeigt . Aber jedes Programm leidet an Unvollständigkeit, wenn der Programmierer nicht alles gesagt hat, was er weiß.
Im wirklichen Leben handelt es sich bei den Aufhebungsarbeiten um Grunzarbeiten oder Boilerplates. Unsere Gehirne füllen sie automatisch aus und meckern darüber, und das Gefühl "der Compiler könnte es genauso gut oder besser machen" ist wahr. In der Theorie ist dies jedoch nicht der Fall, obwohl uns glücklicherweise andere Sprachen mehr Wahlmöglichkeiten bei der Theorie bieten.
quelle
Was wird getan ? Es gibt Garbage Collection und Compiler, die die Referenzzählung verwenden (Objective-C, Swift). Diejenigen, die Referenzzählungen durchführen, benötigen Hilfe vom Programmierer, indem sie starke Referenzzyklen vermeiden.
Die eigentliche Antwort auf das "Warum" ist, dass Compiler-Autoren keinen Weg gefunden haben, der gut und schnell genug ist, um ihn in einem Compiler nutzbar zu machen. Da Compiler-Autoren normalerweise ziemlich schlau sind, kann man daraus schließen, dass es sehr, sehr schwierig ist, einen Weg zu finden, der gut genug und schnell genug ist.
Einer der Gründe, warum es sehr, sehr schwierig ist, ist natürlich, dass es nicht zu entscheiden ist. Wenn wir in der Informatik von "Entscheidbarkeit" sprechen, meinen wir "die richtige Entscheidung treffen". Menschliche Programmierer können natürlich leicht entscheiden, wo Speicher freigegeben werden soll, da sie nicht auf korrekte Entscheidungen beschränkt sind. Und sie treffen oft Entscheidungen, die falsch sind.
quelle
Denn die Lebensdauer eines Speicherblocks hängt von der Entscheidung des Programmierers ab, nicht von der des Compilers.
Das ist es. Dies ist das Design von C. Compiler kann nicht wissen, was die Absicht war, einen Speicherblock zuzuweisen. Menschen können es tun, weil sie den Zweck jedes Speicherblocks kennen und wenn dieser Zweck erfüllt ist, kann er befreit werden. Das gehört zum Design des Programms, das gerade geschrieben wird.
C ist eine einfache Sprache, daher kommt es häufig vor, dass ein Block Ihres Speichers an einen anderen Prozess oder sogar an einen anderen Prozessor übergeben wird. Im Extremfall kann ein Programmierer absichtlich einen Teil des Speichers zuweisen und ihn nie wieder verwenden, nur um Speicherdruck auf andere Teile des Systems auszuüben. Der Compiler kann nicht erkennen, ob der Block noch benötigt wird.
quelle
In C und vielen anderen Sprachen gibt es in der Tat eine Möglichkeit, den Compiler dazu zu bringen, dies in den Fällen zu tun, in denen zum Zeitpunkt der Kompilierung klar ist, wann dies getan werden sollte: Verwendung von Variablen mit automatischer Dauer (dh gewöhnlichen lokalen Variablen) . Der Compiler ist dafür verantwortlich, für genügend Speicherplatz für solche Variablen zu sorgen und diesen Speicherplatz freizugeben, wenn ihre (genau definierte) Lebensdauer endet.
Da Arrays mit variabler Länge seit C99 ein C-Merkmal sind, erfüllen Objekte mit automatischer Dauer im Prinzip im Wesentlichen alle Funktionen in C, die dynamisch zugewiesene Objekte mit berechenbarer Dauer erfüllen. In der Praxis können C- Implementierungen der Verwendung von VLAs natürlich erhebliche praktische Grenzen setzen - dh, ihre Größe kann aufgrund der Zuweisung auf dem Stapel begrenzt sein -, dies ist jedoch eine Überlegung zur Implementierung, keine Überlegung zum Sprachdesign.
Die Objekte, deren beabsichtigte Verwendung eine automatische Dauer ausschließt, sind genau diejenigen, deren Lebensdauer zum Zeitpunkt der Kompilierung nicht bestimmt werden kann.
quelle