Was ist eine kostenlose Liste?
Eine freie Liste ist eine Datenstruktur, die die Adressen der Computerspeicherorte enthält, die für ein laufendes Programm bei Verwendung der dynamischen Speicherzuweisung verfügbar sind.Die Liste wird erforderlich, wenn ein Programm Speicherplatz zuweisen muss Die Implementierung einer freien Liste kann eine einfache verknüpfte Liste oder eine komplexere Datenstruktur wie z Sortierbaum: Die meisten höheren Computerprogrammiersprachen verarbeiten die freie Liste automatisch, sodass keine manuelle Verwaltung erforderlich ist.
Wenn ein Programm Speicherplatz zum Speichern von Informationen während der Programmausführung benötigt, muss es eine bestimmte Menge an Speicher vom zugrunde liegenden Betriebssystem anfordern. Die Speicherorte der Speicherblöcke, die verwendet werden können, werden im freien Speicher abgelegt list. Damit die Zuordnung erfolgreich ist, muss die Menge des angeforderten Speichers in einem oder mehreren dieser Blöcke verfügbar sein. Wenn ein Zeiger auf einen geeigneten Speicherort zurückgegeben wird, Dieses Element der Liste wird entfernt.
Nachdem ein Programm den Speicher verwendet hat, kann es die Zuweisung aufheben, indem der Zeiger auf den Speicherblock zurück in die freie Liste übergeben wird, wo er bei der nächsten Zuweisung verfügbar wird Es ist möglich, dass die Speicherzuweisung fehlschlägt, weil die Liste leer ist oder weil keine Speicherblöcke verfügbar sind, die groß genug sind, um die Programmanforderung zu erfüllen.
Die einfachste Form der Speicherverwaltung stellt das First-Fit-System dar. Dieses System verwaltet eine einzige Liste freier Speicherplätze. Wenn eine Speicheranforderung gesendet wird, wird die Liste durchlaufen und der erste Block Wenn der Block mehr als doppelt so groß wie die angeforderte Größe ist, wird er halbiert und die nicht verwendete Hälfte wieder zur Liste hinzugefügt das Risiko fragmentierter Speicherbereiche, die möglicherweise nie wieder in die Liste aufgenommen werden.
Eine andere Form der Speicherverwaltung stellt das Buddy-Zuweisungssystem dar. Bei der Buddy-Zuweisung werden im Gegensatz zum First-Fit-System mehrere freie Listen geführt, die jeweils nur Blöcke einer bestimmten Größe enthalten Wenn eine Zuordnungsanforderung empfangen wird, wird die Liste mit Blöcken konsultiert, die gerade groß genug sind, um die Anforderung zu füllen, und es wird ein offener Speicherort zurückgegeben angefordert sind verfügbar, ein größerer Block wird zweigeteilt, um die Anforderungen zu erfüllen.
Der Begriff "freie Liste" kann sich entweder auf eine einzelne verknüpfte Liste von Speicheradressen beziehen, oder er kann sich auf eine viel komplexere Art von Datenstruktur beziehen. kann dazu beitragen, die Geschwindigkeit beim Auffinden offener Speicherblöcke zu erhöhen, was den Quellcode erschwert. Eine verknüpfte Liste kann langsamer sein als ein spezialisierter Sortierbaum, erstellt jedoch Programmcode, der viel einfacher zu lesen ist. debuggen und modifizieren.
Einige Programmiersprachen und Betriebssysteme verwenden einen speziellen Mechanismus namens Garbage Collection (Speicherbereinigung). Dieser Vorgang kann dazu beitragen, die verschiedenen Einträge in eine freie Liste aufzunehmen und die freien Speicherplätze so zu konsolidieren, dass sie zusammenhängend sind Dies verhindert die Fragmentierung und ermöglicht die Zuweisung größerer Speicherblöcke.