Speicherverwaltung

Speichermanagement (auch dynamisches Speichermanagement , dynamische Speicherzuweisung oder dynamische Speicherallokation genannt) ist eine Form des Ressourcenmanagements für den Computerspeicher . Die grundlegende Anforderung an das Speichermanagement besteht darin, Möglichkeiten bereitzustellen, Programmen auf deren Anforderung hin dynamisch Speicherbereiche zuzuweisen und diese wieder freizugeben, sobald sie nicht mehr benötigt werden. Dies ist für jedes moderne Computersystem, in dem mehrere Prozesse gleichzeitig ausgeführt werden können ( Multitasking ), von entscheidender Bedeutung. ^{[ 1 ]}

Es wurden verschiedene Methoden entwickelt, um die Effektivität des Speichermanagements zu steigern. Virtuelle Speichersysteme trennen die von einem Prozess verwendeten Speicheradressen von den tatsächlichen physischen Adressen. Dies ermöglicht die Trennung von Prozessen und erweitert den virtuellen Adressraum über den verfügbaren Arbeitsspeicher (RAM) hinaus , indem Daten auf Sekundärspeicher ausgelagert werden . Die Qualität des virtuellen Speichermanagements hat einen erheblichen Einfluss auf die Gesamtleistung des Systems . Das System ermöglicht es einem Computer, so zu erscheinen, als stünde ihm mehr Speicher zur Verfügung, als physisch vorhanden ist, wodurch mehrere Prozesse diesen gemeinsam nutzen können.

In einigen Betriebssystemen , z. B. Burroughs/Unisys MCP [ ^{2 ] und} OS /360 und Nachfolgern [ ^{3 ] ,} wird der Speicher vom Betriebssystem verwaltet. ^{[ Anmerkung 1 ]} In anderen Betriebssystemen, z. B. Unix-ähnlichen Betriebssystemen, erfolgt die Speicherverwaltung auf Anwendungsebene.

Die Speicherverwaltung innerhalb eines Adressraums wird im Allgemeinen entweder in manuelle oder in automatische Speicherverwaltung unterteilt.

Die Erfüllung einer Speicheranforderung besteht darin, einen ausreichend großen, ungenutzten Speicherblock zu finden. Speicheranforderungen werden erfüllt, indem Speicherbereiche aus einem großen Speicherpool, dem sogenannten Heap (Anmerkung 2) oder freien Speicher, allokiert werden ^{. Zu} jedem Zeitpunkt ^{sind Teile des Heaps} belegt , während andere „frei“ (unbenutzt) und somit für zukünftige Speicherzuweisungen verfügbar sind. In der Programmiersprache C wird die Funktion, die Speicher aus dem Heap allokiert, als Heap-Speicher bezeichnet, und die Funktion, die zuvor allokierten Speicher als „frei“ markiert (um ihn für zukünftige Speicherzuweisungen zu verwenden), wird als Heap-Speicherzuweisung bezeichnet . ^{( Anmerkung 4 )}mallocfree

Mehrere Probleme erschweren die Implementierung, beispielsweise die externe Fragmentierung . Diese entsteht, wenn zwischen zugewiesenen Speicherblöcken viele kleine Lücken bestehen, wodurch deren Verwendung für eine Zuweisungsanforderung ungültig wird. Auch die Metadaten des Speicherverwaltungssystems können die Größe einzelner kleiner Zuweisungen unnötig vergrößern. Dies wird häufig durch Chunking kompensiert . Das Speicherverwaltungssystem muss ausstehende Zuweisungen überwachen, um Überschneidungen und Speicherverluste (Speicherlecks ) zu vermeiden .

Der verwendete dynamische Speicherallokationsalgorithmus kann die Leistung erheblich beeinflussen. Eine Studie der Digital Equipment Corporation aus dem Jahr 1994 veranschaulicht den damit verbundenen Aufwand für verschiedene Allokatoren. Die kürzeste durchschnittliche Befehlspfadlänge für die Allokation eines einzelnen Speicherslots betrug 52 (gemessen mit einem Befehlsprofiler auf verschiedenen Softwareanwendungen). ^{[ 1 ]}

Da der genaue Speicherort nicht im Voraus bekannt ist, erfolgt der Speicherzugriff indirekt, üblicherweise über einen Speicherzeiger . Der spezifische Algorithmus zur Organisation des Speicherbereichs sowie zur Zuweisung und Freigabe von Speicherblöcken ist mit dem Kernel verknüpft und kann eine der folgenden Methoden verwenden:

Die Speicherverwaltung mit Blöcken fester Größe, auch Speicherpool-Verwaltung genannt, verwendet eine Liste freier Speicherblöcke fester Größe (oft alle gleich groß). Dies eignet sich gut für einfache eingebettete Systeme , in denen keine großen Objekte benötigt werden, führt aber insbesondere bei langen Speicheradressen zu Fragmentierung . Aufgrund des deutlich reduzierten Overheads kann diese Methode die Leistung jedoch erheblich verbessern, wenn häufig Speicher allokiert und freigegeben werden muss, und wird daher oft in Videospielen eingesetzt .

In diesem System wird der Speicher in mehrere Speicherpools anstatt nur eines aufgeteilt. Jeder Pool repräsentiert Speicherblöcke mit einer bestimmten Größe, die eine Zweierpotenz ist , oder Blöcke mit einer anderen geeigneten Größenprogression. Alle Blöcke einer bestimmten Größe werden in einer sortierten verketteten Liste oder einem Baum gespeichert , und alle neu erstellten Blöcke werden ihrem jeweiligen Speicherpool zur späteren Verwendung hinzugefügt. Wird eine kleinere Größe angefordert als verfügbar ist, wird die kleinste verfügbare Größe ausgewählt und aufgeteilt. Dabei wird ein Block in zwei kleinere Blöcke geteilt, die jeweils einen eindeutigen „Partnerblock“ bilden. Einer der resultierenden Teile wird ausgewählt, und der Vorgang wiederholt sich, bis die Anforderung vollständig erfüllt ist. Bei der Zuweisung eines Blocks beginnt der Speicherallokator mit dem kleinsten ausreichend großen Block, um unnötige Blockteilungen zu vermeiden. Wird ein Block freigegeben, wird er mit seinem Partnerblock verglichen. Sind beide frei, werden sie zusammengeführt und in die Liste der Partnerblöcke mit der entsprechenden Größe eingefügt.

Dieser Speicherverwaltungsmechanismus reserviert vorab Speicherbereiche, die für Objekte eines bestimmten Typs oder einer bestimmten Größe geeignet sind. ^{[ 5 ]} Diese Bereiche werden als Caches bezeichnet, und der Speicherverwalter muss lediglich eine Liste freier Cache-Slots verwalten. Beim Erstellen eines Objekts wird ein beliebiger freier Cache-Slot verwendet, und beim Zerstören eines Objekts wird ein Slot zur Liste der freien Cache-Slots hinzugefügt. Dieses Verfahren reduziert die Speicherfragmentierung und ist effizient, da nicht nach einem geeigneten Speicherbereich gesucht werden muss – jeder freie Slot genügt.

Viele Unix-ähnliche Systeme sowie Microsoft Windows implementieren eine Funktion namens `alloca` allocazur dynamischen Speicherallokation auf dem Stack, ähnlich der Heap-basierten Speicherallokation malloc. Ein Compiler übersetzt diese Funktion typischerweise in Inline-Anweisungen, die den Stackpointer manipulieren. ^{[ 6 ]} Obwohl der so allokierte Speicher nicht manuell freigegeben werden muss, da dies automatisch nach allocaRückgabe der aufrufenden Funktion geschieht, besteht die Gefahr eines Überlaufs. Da `alloca` eine Ad-hoc- Erweiterung ist, die zwar in vielen Systemen vorkommt, aber weder in POSIX noch im C-Standard definiert ist, ist ihr Verhalten im Falle eines Stack-Überlaufs undefiniert.

Eine sicherere Version von alloca namens `alloc` _malloca, die Fehler meldet, existiert unter Microsoft Windows. Sie erfordert die Verwendung von `malloc` _freea. ^{[ 7 ]} gnulib bietet eine äquivalente Schnittstelle, delegiert jedoch anstelle einer SEH-Ausnahme bei einem Überlauf an `malloc`, wenn eine zu große Speichergröße erkannt wird. ^{[ 8 ]} Eine ähnliche Funktionalität lässt sich durch manuelle Speicherverwaltung und Größenprüfung emulieren, beispielsweise durch die Verwendung von `malloc` alloca_accountin glibc. ^{[ 9 ]}

Die korrekte Speicherverwaltung in einer Anwendung ist ein schwieriges Problem, und es wurden verschiedene Strategien für die Speicherverwaltung entwickelt.

In vielen Programmiersprachen reserviert die Laufzeitumgebung beim Aufruf einer Unterroutine automatisch Speicher im Aufrufstapel für nicht-statische lokale Variablen (sogenannte automatische Variablen) und gibt diesen Speicher beim Verlassen der Unterroutine wieder frei. Spezielle Deklarationen ermöglichen es, dass lokale Variablen ihre Werte zwischen den Aufrufen der Prozedur behalten oder von anderen Unterroutinen darauf zugegriffen werden kann. Die automatische Reservierung lokaler Variablen ermöglicht Rekursion bis zu einer durch den verfügbaren Speicher begrenzten Tiefe.

Die automatische Speicherbereinigung (Garbage Collection) erkennt automatisch Speicher, der nicht mehr benötigten Objekten zugewiesen ist, und gibt diesen Speicher an einen Pool freier Speicheradressen zurück. Dies steht im Gegensatz zur manuellen Speicherverwaltung, bei der der Programmierer Speicheranforderungen und -freigaben explizit im Programmcode festlegt. Obwohl die automatische Speicherbereinigung den Programmieraufwand reduziert und bestimmte Speicherbelegungsfehler verhindert, benötigt sie selbst Speicherressourcen und kann mit dem Anwendungsprogramm um Rechenzeit konkurrieren.

Referenzzählung ist eine Strategie, um zu erkennen, wann ein Programm nicht mehr auf Speicher zugreifen kann. Dazu wird ein Zähler geführt, der die Anzahl unabhängiger Zeiger auf den Speicherbereich erfasst. Sobald ein neuer Zeiger auf einen Speicherbereich verweist, erhöht der Programmierer den Zähler. Ändert sich das Ziel des Zeigers, verweist er auf keinen Bereich mehr oder wurde er selbst freigegeben, verringert sich der Zähler. Erreicht der Zähler den Wert Null, gilt der Speicher als ungenutzt und wird freigegeben. Manche Referenzzählungssysteme erfordern die Eingabe des Programmierers, andere werden automatisch vom Compiler implementiert. Ein Nachteil der Referenzzählung ist, dass zirkuläre Referenzen entstehen und zu Speicherlecks führen können. Dies lässt sich durch die Einführung von „ schwacher Referenz “ (einer Referenz, die nicht an der Referenzzählung teilnimmt, aber benachrichtigt wird, wenn der von ihr referenzierte Bereich nicht mehr gültig ist) oder durch die Kombination von Referenzzählung und automatischer Speicherbereinigung (Garbage Collection) abmildern.

Ein Memory-Pool ist eine Technik zur automatischen Speicherfreigabe basierend auf dem Anwendungszustand, beispielsweise dem Lebenszyklus einer Anfrage oder Transaktion. Viele Anwendungen führen große Codeblöcke aus, die Speicherbelegungen erzeugen können. Es gibt jedoch einen Zeitpunkt in der Ausführung, an dem diese Codeblöcke nicht mehr benötigt werden. Beispielsweise benötigt ein Webdienst nach jeder Anfrage keinen der während der Anfrageausführung belegten Speicher mehr. Anstatt also zu verfolgen, ob aktuell auf Speicher zugegriffen wird, wird der Speicher entsprechend der zugehörigen Anfrage oder Lebenszyklusphase zugewiesen. Sobald diese Anfrage oder Phase abgeschlossen ist, wird der gesamte zugehörige Speicher gleichzeitig freigegeben.

Virtueller Speicher ist eine Methode, die Speicherorganisation von der physischen Hardware zu entkoppeln. Anwendungen greifen über virtuelle Adressen auf den Speicher zu . Jeder Zugriff einer Anwendung auf eine bestimmte virtuelle Speicheradresse führt dazu, dass diese in eine tatsächliche physische Adresse übersetzt wird . ^{[ 10 ]} Dadurch ermöglicht die Verwendung von virtuellem Speicher eine präzise Steuerung von Speichersystemen und Zugriffsmethoden.

In virtuellen Speichersystemen beschränkt das Betriebssystem den Speicherzugriff eines Prozesses . Diese Funktion, der sogenannte Speicherschutz , verhindert, dass ein Prozess auf Speicher zugreift, der ihm nicht zugewiesen ist. Dadurch wird verhindert, dass schädlicher oder fehlerhafter Code in einem Programm die Funktion eines anderen Programms beeinträchtigt.

Auch wenn der für bestimmte Prozesse reservierte Speicher normalerweise isoliert ist, müssen Prozesse manchmal Informationen austauschen können. Gemeinsamer Speicher ist eine der schnellsten Techniken für die Interprozesskommunikation .

Der Speicher wird üblicherweise anhand der Zugriffsrate in Primärspeicher und Sekundärspeicher unterteilt . Speichermanagementsysteme verwalten unter anderem auch den Datenaustausch zwischen diesen beiden Speicherebenen.

Ein Betriebssystem verwaltet verschiedene Ressourcen im Computersystem. Das Speichersubsystem ist die Systemkomponente für die Speicherverwaltung. Es kombiniert die Hardware-Speicherressource mit der MCP-OS-Software, die diese Ressource verwaltet.

Das Speichersubsystem verwaltet den physischen und den virtuellen Speicher des Systems (beide Teil der Hardware-Ressourcen). Der virtuelle Speicher erweitert den physischen Speicher durch die Nutzung zusätzlichen Speicherplatzes auf einem Peripheriegerät, üblicherweise einer Festplatte. Das Speichersubsystem ist für das Verschieben von Code und Daten zwischen Haupt- und virtuellem Speicher verantwortlich, ein Vorgang, der als Overlaying bezeichnet wird. Burroughs war die erste kommerzielle Implementierung von virtuellem Speicher (obwohl er an der Universität Manchester für den Ferranti Atlas-Computer entwickelt wurde) und integrierte virtuellen Speicher von Anfang an (1961) in das Systemdesign des B5000, sodass keine externe Speichermanagementeinheit (MMU) erforderlich war. ^{[ 11 ] : 48}

Das Speichersubsystem ist für die Zuordnung logischer Speicherblockanforderungen zu physischen Speicherbereichen (Segmenten) in der Liste der freien Segmente zuständig. Jeder zugewiesene Block wird mittels eines Segmentdeskriptors verwaltet ^{[ 12 ]} , einem speziellen Steuerwort, das relevante Metadaten über das Segment enthält, darunter Adresse, Länge, Maschinentyp und das P-Bit (Präsenzbit), das angibt, ob sich der Block im Hauptspeicher befindet oder von der im Deskriptor angegebenen Adresse geladen werden muss.

Deskriptoren sind unerlässlich für die Speichersicherheit, um zu verhindern, dass Operationen den referenzierten Block über- oder unterlaufen (bekannt als Pufferüberlauf). Deskriptoren selbst sind geschützte Steuerwörter, die nur von bestimmten Elementen des MCP-Betriebssystems manipuliert werden können (aktiviert durch die Blockdirektive UNSAFE in NEWP ).

Donald Knuth beschreibt ein ähnliches System in Abschnitt 2.5 „Dynamische Speicherzuweisung“ von „Fundamentale Algorithmen“ .

IBM System/360 unterstützt keinen virtuellen Speicher. ^{[ Anmerkung 5 ]} Die Speicherisolation von Jobs kann optional mithilfe von Schutzschlüsseln erfolgen , wobei jedem Job ein anderer Schlüssel zugewiesen wird: 0 für den Supervisor oder 1–15. Die Speicherverwaltung in OS/360 ist eine Supervisor- Funktion. Speicher wird mit dem GETMAINMakro `request` angefordert und mit dem FREEMAINMakro `free` freigegeben, was jeweils einen Aufruf des Supervisors ( SVC ) zur Durchführung der Operation auslöst.

Bei OS/360 variieren die Details je nachdem, wie das System generiert wird , z. B. für PCP , MFT , MVT .

In OS/360 MVT basiert die Unterzuweisung innerhalb der Region eines Jobs oder des gemeinsamen Systemwarteschlangenbereichs (SQA) auf Subpools . Diese Bereiche sind ein Vielfaches von 2 KB groß – der Größe eines durch einen Schutzschlüssel geschützten Bereichs. Die Subpools sind von 0 bis 255 nummeriert. ^{[ 13 ]} Innerhalb einer Region wird den Subpools entweder der Speicherschutz des Jobs oder der Schlüssel des Supervisors (Schlüssel 0) zugewiesen. Die Subpools 0 bis 127 erhalten den Schlüssel des Jobs. Anfangs wird nur Subpool 0 erstellt, und alle Speicheranforderungen der Benutzer werden von Subpool 0 bedient, sofern in der Speicheranforderung kein anderer angegeben ist. Die Subpools 250 bis 255 werden durch Speicheranforderungen des Supervisors im Namen des Jobs erstellt. Die meisten dieser Subpools erhalten Schlüssel 0, einige wenige jedoch den Schlüssel des Jobs. Subpoolnummern sind auch in MFT relevant, die Details sind dort jedoch deutlich einfacher. ^{[ 14 ]} MFT verwendet feste , vom Operator neu definierbare Partitionen anstelle dynamischer Regionen, und PCP verfügt nur über eine einzige Partition.

Jeder Subpool wird durch eine Liste von Kontrollblöcken abgebildet, die belegte und freie Speicherblöcke innerhalb des Subpools identifizieren. Die Speicherbelegung erfolgt durch das Auffinden eines ausreichend großen freien Bereichs oder durch die Zuweisung zusätzlicher Blöcke im Subpool bis zur Regionsgröße des Jobs. Es ist möglich, einen belegten Speicherbereich vollständig oder teilweise freizugeben. ^{[ 15 ]}

Die Details für OS/VS1 ähneln denen von MFT und MVT ^{[ 16 ]} ; die Details für OS/VS2 ähneln denen von MVT, mit der Ausnahme, dass die Seitengröße 4 KiB beträgt. Sowohl bei OS/VS1 als auch bei OS/VS2 ist der gemeinsam genutzte Systemwarteschlangenbereich (SQA) nicht auslagerbar.

In MVS umfasst der Adressraum ^{[ 17 ]} einen zusätzlichen auslagerbaren gemeinsamen Bereich, den Common Storage Area (CSA), sowie zwei zusätzliche private Bereiche: den nicht auslagerbaren lokalen Systemwarteschlangenbereich (LSQA) und den auslagerbaren Systemarbeitsbereich (SWA). Die Speicherschlüssel 0–7 sind ausschließlich für die Verwendung durch privilegierten Code reserviert.

• Dynamisches Array
• Speicher erschöpft
• Müllhaldenverschmutzung

• Donald Knuth . Fundamentale Algorithmen , dritte Auflage. Addison-Wesley, 1997. ISBN 0-201-89683-4Abschnitt 2.5: Dynamische Speicherzuweisung, S. 435–456.
• Einfache Speicherverwaltungsalgorithmen ( Archiviert am 5. März 2016 in der Wayback Machine , ursprünglich veröffentlicht auf OSDEV Community)
• Wilson, P. R.; Johnstone, M. S.; Neely, M.; Boles, D. (1995). „Dynamische Speicherzuweisung: Eine Übersicht und kritische Betrachtung“ (PDF) . Memory Management . Lecture Notes in Computer Science. Band 986. S.  1–116 . CiteSeerX  10.1.1.47.275 . doi : 10.1007/3-540-60368-9_19 . ISBN 978-3-540-60368-9Die
• Berger, ED; Zorn, BG; McKinley, KS (Juni 2001). „Composing High-Performance Memory Allocators“ (PDF) . Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation . PLDI '01. S.  114–124 . CiteSeerX  10.1.1.1.2112 . doi : 10.1145 /378795.378821 . ISBN 1-58113-414-2. S2CID  7501376 .
• Berger, ED; Zorn, BG; McKinley, KS (November 2002). „Reconsidering Custom Memory Allocation“ (PDF) . Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications . OOPSLA '02. S.  1–12 . CiteSeerX  10.1.1.119.5298 . doi : 10.1145/582419.582421 . ISBN 1-58113-471-1. S2CID  481812 .

OS360Sup

OS Release 21 IBM System/360 Betriebssystem Supervisor-Dienste und Makroanweisungen (PDF) . IBM Systems Reference Library (Achte Auflage). IBM . September 1974. GC28-6646-7.

OSVS1Dig

OS/VS1 Programmer's Reference Digest Release 6 (PDF) . Systems (Sechste Auflage). IBM . 15. September 1976. GC24-5091-5 mit TNLs.

• "Generischer Speichermanager" C++-Bibliothek
• Beispiel eines bit-abgebildeten Arena-Speicherallokators in C
• TLSF: ein konstanter Zeitallokator für Echtzeitsysteme
• Folien zur dynamischen Speicherverwaltung
• Im Inneren eines Speicherverteilers
• Die Speicherverwaltungsreferenz

• Speichermanagement-Referenz, Anfängerleitfaden zur Speicherzuweisung

• Linux-Speicherverwaltung
• Speicherverwaltung für Systemprogrammierer
• VMem – allgemeiner Ersatz für malloc/free. Schneller, threadsicherer C++-Allokator.
• Speicherverwaltung des Betriebssystems