Adressräume und Adressübersetzung

Ein laufendes Programm arbeitet mit einem Adressraum: seiner eigenen Sicht auf den Speicher mit nummerierten Bytepositionen. Das Betriebssystem platziert den Speicher des Programms im Rechner und sorgt dafür, dass seine Adressen die richtigen physischen Bytes erreichen. Der Aufbau aus Sicht des Programms und die Anordnung in der Hardware sind verschiedene Dinge.

Warum mehrere Programme im Speicher bleiben

Frühe Systeme konnten neben dem Betriebssystem ein Programm halten. Das Betriebssystem konnte beispielsweise die ersten 64 KB und das Programm den übrigen Speicher belegen. Der Mehrprogrammbetrieb hielt mehr als einen Prozess bereit, sodass die CPU arbeiten konnte, während ein anderer Prozess auf eine Ein- oder Ausgabe wartete. Das Zeitteilverfahren wechselte die CPU häufig genug zwischen Prozessen, um interaktive Benutzer zu bedienen.

Den gesamten Speicher eines Prozesses bei jedem Wechsel auf die Festplatte zu schreiben, würde den Wechsel viel zu langsam machen. Mehrere Prozesse im physischen Speicher zu halten, vermeidet dieses Kopieren, schafft aber ein Schutzproblem. Eine von einem Prozess erzeugte Adresse darf es ihm nicht erlauben, das Betriebssystem oder einen benachbarten Prozess zu überschreiben.

Speichergrößen folgen hier der in diesen Modellen verwendeten binären Konvention: 1 KB sind 1.024 Bytes, auch als 1 KiB geschrieben; 1 MB sind 1.024 KB. Ein 16 KB großer Adressraum hat 16.384 Bytepositionen, nummeriert von 0 bis 16.383. Die Zahl 16.384 ist die Endgrenze, keine gültige Byteadresse.

Code, Daten, Heap und Stack

In einer klassischen Lehrbuchdarstellung mit 16 KB belegt der Code die niedrigen Adressen von 0 bis zur 1-KB-Grenze. Der Heap beginnt oberhalb des Codes und wächst nach oben. Der Stack beginnt an der oberen Grenze und wächst nach unten. Die freie Lücke dazwischen gibt beiden Bereichen Platz zum Wachsen. Reale Anordnungen unterscheiden sich; beispielsweise hat jeder Thread seinen eigenen Stack. Die Aufgaben der Bereiche bleiben auch dann hilfreich, wenn sich ihre Positionen ändern.

Verfolge einen Zeiger zum richtigen Speicher

Eine virtuelle Adresse bezeichnet ein Byte im Adressraum eines Prozesses. Eine physische Adresse bezeichnet ein Byte in der Speicherhardware des Rechners. Wenn C-Code printf("%p", (void *) &x) ausführt, gibt er eine virtuelle Adresse aus. Der ausgegebene Zeiger verrät nicht, welches physische Byte x speichert.

Angenommen, zwei Prozesse verwenden beide die virtuelle Adresse 1.000. Jede Adresse wird im eigenen Adressraum des jeweiligen Prozesses interpretiert, sodass die Zugriffe unterschiedliche physische Bytes erreichen können. Ebenso muss Code an der virtuellen Adresse 0 nicht die physische Adresse 0 belegen. Das Betriebssystem kann ihn anderswo platzieren und die Hardwareübersetzung so einrichten, dass sie ihn erreicht.

Der Prozessor übersetzt Befehlsabrufe sowie Lese- und Schreibzugriffe. Das Betriebssystem wählt und verwaltet die Abbildungen; dabei kann es auch physische Speicherorte ändern und die virtuellen Adressen des Programms stabil halten.

Ein Speichersystem muss mehr leisten, als eine Zahl korrekt zu übersetzen. Es muss gewöhnliche Programme ausführen lassen, ohne dass diese ihre physische Platzierung verwalten, die Übersetzung mit geringem Aufwand durchführen und die Grenzen durchsetzen, die gemeinsame Nutzung sicher machen. Diese Anforderungen heißen Transparenz, Effizienz und Schutz.

Bewahre die Sicht des Programms

Transparenz bedeutet, dass ein Programm so läuft, als hätte es privaten Speicher. Es verwendet seine eigenen Adressen für Code und Daten, ohne zu verfolgen, welche anderen Prozesse vorhanden sind oder wo deren Bytes liegen. Betriebssystem und Hardware bewahren diese Sicht im Hintergrund. Um einen Prozess im physischen Speicher zu verschieben, sollte der Prozess seine Zeiger nicht umschreiben müssen.

Die Illusion erfordert keine eigene physische Kopie jedes Bytes für jeden Prozess. Geschützter Code, der nur gelesen werden darf, kann beispielsweise gemeinsam genutzt werden. Entscheidend ist, dass die gemeinsame Nutzung das Verhalten und die Zugriffsrechte bewahrt, auf die jeder Prozess Anspruch hat.

Berücksichtige beide Arten von Aufwand

Jeder Befehlsabruf sowie jeder Lese- und Schreibzugriff muss übersetzt werden. Eine Betriebssystemroutine für jeden Zugriff auszuführen, würde die gewöhnliche Ausführung zu langsam machen. Die Hardware führt die häufigen Operationen aus; Betriebssystemcode behandelt Einrichtung, Änderungen und Fehler.

Auch Speichereffizienz ist wichtig. Ein kleiner, schneller Übersetzungsmechanismus kann dennoch erheblichen Speicher verschwenden. Ein einzelner Bereich mit Basis- und Grenzregister reserviert die ungenutzte Lücke zwischen Heap und Stack. Bei der Segmentierung muss für diese Lücke kein physischer Speicher bereitgestellt werden, dafür entstehen aber physische Bereiche unterschiedlicher Größe und Lücken dazwischen. Metadaten, ungenutzter reservierter Speicher und Lücken beeinflussen alle, wie viel nützliche Arbeit in den Speicher passt.

Halte einen unzulässigen Zugriff an der Grenze auf

Ohne Schutz könnte ein fehlgeleiteter Zeiger in einem Texteditor einen anderen Prozess oder den Kernel überschreiben. Der Schaden könnte sich viel später in einem anderen Codeteil zeigen. Werden Grenzen durchgesetzt, weist die Hardware einen Zugriff außerhalb des erlaubten Bereichs ab und löst eine Ausnahme aus. Das Betriebssystem behandelt die Ausnahme und beendet üblicherweise den fehlerhaften Prozess, wobei häufig eine Speicherzugriffsverletzung gemeldet wird.

Schutz isoliert Prozesse voneinander. Er macht die Speichernutzung in C innerhalb eines erlaubten Heap-Bereichs nicht sicher. Ein Schreibzugriff über einen zugewiesenen Block hinaus kann weiterhin einen anderen Block desselben Prozesses treffen. Prozessgrenzen und Grenzen von Blöcken des Allokators sind unterschiedliche Grenzen.

Trenne die Operation von der Entscheidung

Ein Mechanismus beschreibt, wie eine Operation ausgeführt wird. Das Addieren eines Basisregisterwerts und das Prüfen eines Grenzregisters sind Mechanismen. Eine Strategie wählt zwischen möglichen Handlungen: wo ein Prozess platziert wird, welche freie Lücke genutzt wird oder wann ein Segment verschoben wird.

Diese Trennung erlaubt es dem Betriebssystem, seine Platzierungsstrategie zu ändern und dieselbe Hardwareübersetzung beizubehalten. Speichervirtualisierung beginnt mit dieser privaten, geschützten Sicht; sie ist nicht durch die Nutzung der Festplatte als zusätzlicher Speicher definiert.

Eine Zeigervariable und der Speicher, auf den sie zeigt, sind getrennte Objekte. Ihre Lebensdauern zu verstehen, ist der Ausgangspunkt für die C-Speicherverwaltungsschnittstelle. Gewöhnliche lokale Variablen nutzen typischerweise automatischen Stack-Speicher, Heap-Blöcke bleiben bis zu ihrer Freigabe bestehen, und globale sowie lokale static-Variablen haben während der gesamten Programmausführung Speicher.

Verfolge die Speicherzuweisung, nicht nur den Zeiger

void f(void) {
    int x;
    int *p = malloc(sizeof(int));
}

Im üblichen Stackaufbau gehören x und p zu diesem Aufruf von f. Die angeforderte Ganzzahl gehört zum Heap. Bei der Rückkehr wird die lokale Zeigervariable entfernt; der Heap-Block wird dadurch nicht freigegeben. Bleibt keine Kopie der Adresse erhalten, hat das Programm den Zugriff auf eine aktive Speicherbelegung verloren: ein Speicherleck.

malloc(size) fordert mindestens so viele Bytes an und gibt einen Zeiger zurück oder NULL, wenn die Anforderung nicht erfüllt werden kann. Die Bytes werden für das Programm nicht initialisiert. Verwende für 10 Ganzzahlen malloc(10 * sizeof(int)); ist eine Ganzzahl 4 Bytes groß, fordert das 40 Bytes an. Reserviere für eine Zeichenkette ihre Zeichen plus ein Byte für das abschließende Nullzeichen: malloc(strlen(s) + 1).

sizeof(a) misst das Objekt mit dem Namen a. Ist a ein Zeiger, ergibt sich die Größe des Zeigers, nicht die Größe des zugewiesenen Speichers. Ein 8 Byte großer Zeiger kann auf einen 40 Byte großen Block verweisen.

Kenne die Aufgaben der Bibliotheksoperationen

free erhält den zurückgegebenen Zeiger ohne Größenargument. Der Allokator speichert Metadaten zur Größe, üblicherweise in einem Verwaltungskopf vor dem Block. Übergib den zurückgegebenen Zeiger eines aktuell zugewiesenen Blocks; ein Zeiger ins Innere des Blocks ist kein gültiger Ersatz. free(NULL) ist zulässig und bewirkt nichts. Diese Funktionen sind Routinen der C-Bibliothek, keine Systemaufrufe.

Erkenne Fehler an Lebensdauer oder Grenze

Ein Zeiger ohne gültige Speicherzuweisung darf nicht so verwendet werden, als zeige er bereits auf Speicher. Neu zugewiesene Bytes vor ihrer Initialisierung zu lesen, ist ein Lesen nicht initialisierter Daten. Schreiben über das Ende des zugewiesenen Bereichs hinaus ist ein Pufferüberlauf; das Weglassen des abschließenden Bytes einer Zeichenkette kann einen solchen verursachen.

Nach free sind alte Zeiger auf den Block hängende Zeiger. Ein Zugriff über einen solchen Zeiger ist ein Zugriff nach Freigabe. Den Block erneut freizugeben, ist eine doppelte Speicherfreigabe. Die Freigabe einer Adresse, die der Allokator nicht für einen aktiven Block zurückgegeben hat, ist eine ungültige Freigabe. Ein Speicherleck ist etwas anderes: Der Block bleibt zugewiesen, aber das Programm gibt ihn nicht mehr frei, obwohl es das sollte.

Verstehe, was die Hardware prüfen kann

Die Kompilierung kann trotz all dieser Fehler gelingen. Die Hardware prüft normalerweise Prozessbereiche und Berechtigungen, nicht jede Speicherzuweisung der Bibliothek. Das Überschreiten einer Blockgrenze innerhalb des zulässigen Heaps des Prozesses kann undefiniertes Verhalten auslösen, ohne sofort einen Fehler zu verursachen. Das Programm kann Daten beschädigen, später abstürzen, bedeutungslose Werte lesen oder scheinbar funktionieren. Valgrind und AddressSanitizer können viele solcher Fehler während der Ausführung erkennen.

Die C-Bibliothek und das Betriebssystem verwalten Speicher auf unterschiedlichen Ebenen. Das Betriebssystem richtet Bereiche im Adressraum eines Prozesses ein und stellt den zugehörigen physischen Speicher bereit. Der Allokator teilt verfügbaren Heap-Speicher in Blöcke auf, erfasst freie Stücke und verwendet sie über mehrere Aufrufe hinweg erneut.

Verschiebe den Program Break

Der Program Break ist die Adresse unmittelbar hinter dem Ende des traditionellen Heaps. brk setzt diese Grenze auf eine gewählte Adresse. sbrk(n) verschiebt sie um eine Anzahl von Bytes und gibt bei Erfolg den alten Program Break zurück. sbrk(0) meldet den aktuellen Program Break, ohne ihn zu verschieben.

Angenommen, der Program Break liegt bei 40.960 und der Allokator ruft erfolgreich sbrk(8192) auf. Der Rückgabewert ist 40.960. Die neue Grenze ist:

Die hinzugefügten Bytes belegen die virtuellen Adressen 40.960 bis 49.151. Der neue Program Break, 49.152, liegt unmittelbar hinter dem hinzugefügten Bereich. Verwechselt man den Rückgabewert mit der neuen Grenze, verschiebt das jede spätere Platzierungsberechnung.

Anwendungen nutzen die Speicherverwaltungsbibliothek, statt den Program Break direkt zu verschieben. Die Bibliothek erfasst, welche Teile ihres Bereichs ihr gehören. Unabhängige Änderungen dieser Grenze können ihre Verwaltungsdaten ungültig machen.

Erhalte eine separate Speicherabbildung

mmap kann einen anonymen Bereich erzeugen: Speicher, der nicht an eine Datei gebunden und anfangs mit Nullbytes gefüllt ist. munmap entfernt eine Speicherabbildung. Ein Allokator kann separate Speicherabbildungen für große Speicherzuweisungen verwenden und sie bei der Freigabe an das Betriebssystem zurückgeben.

In glibc liegt der anfängliche Standardschwellenwert für diesen Weg bei 128 KB oder 131.072 Bytes und kann nach oben angepasst werden. Eine ausreichend große Speicherzuweisung erhält typischerweise eine separate Speicherabbildung, wenn sie nicht aus vorhandenem freiem Speicher bedient werden kann. Dies ist eine Strategie der Bibliothek, keine allgemeingültige Trennlinie in der Sprache C.

Gib auf Bibliotheks- oder Betriebssystemebene frei

Ein Aufruf von free gibt einen kleinen Block üblicherweise an den Speichervorrat der Bibliothek zurück. Der Prozess kann danach daher denselben Speicherverbrauch ausweisen. Der Speicher steht zur Wiederverwendung bereit, ohne das Betriebssystem erneut anfordern zu müssen.

Beim Prozessende werden auch Speicherzuweisungen zurückgewonnen, die das Programm verloren hat. Während der Lebensdauer eines langlebigen Servers verbrauchen wiederholte Speicherlecks jedoch immer mehr seines verfügbaren Speichers. Die Rückgewinnung beim Beenden verhindert diesen Speicherdruck während der Ausführung nicht.

Verbinde Heap-Wachstum und Übersetzung

Im Segmentierungsmodell ist der Heap ein zusammenhängendes physisches Segment. Damit er wachsen kann, müssen unmittelbar darüber freie physische Bytes liegen. Sind diese Bytes belegt, kann das Betriebssystem das Segment in eine größere Lücke verschieben und seinen Übersetzungszustand aktualisieren. Ist kein geeigneter Bereich verfügbar, schlägt das Wachstum fehl. Kann der Allokator nicht genügend Platz erhalten, gibt malloc NULL zurück.

Dynamische Relokation übersetzt Adressen während der Programmausführung. Im Modell mit Basis- und Grenzregister belegt ein Prozess einen zusammenhängenden physischen Bereich. Beginne mit gleich großen Adressräumen, die in den physischen Speicher passen; ein Registerpaar beschreibt dann den Bereich des aktuell laufenden Prozesses.

Prüfe zuerst die virtuelle Adresse

Das Basisregister enthält die physische Adresse des ersten Bytes des Bereichs. Das Grenzregister, auch Limitregister genannt, enthält die Größe des Bereichs in Bytes. Für eine nicht negative virtuelle Adresse gilt:

Ist die Prüfung erfolgreich, gilt:

Andernfalls löst die Hardware eine Ausnahme aus. Eine Größe ist eine Anzahl, daher liegt die Adresse, die der Grenze entspricht, bereits außerhalb des Bereichs. Negative virtuelle Adressen sind ebenfalls ungültig.

Gehe die Bytegrenzen durch

Betrachte einen 8 KB großen Adressraum mit Basis 20.480 und Grenze 8.192. Seine virtuellen Bytes reichen von 0 bis 8.191. Die virtuelle Adresse 1.000 besteht die Prüfung und erreicht das physische Byte 21.480. Das letzte zulässige virtuelle Byte, 8.191, erreicht 28.671. Adresse 9.000 besteht die Prüfung nicht, weil sie mindestens 8.192 beträgt; die Hardware muss sie abweisen, bevor sie den physischen Zugriff ausführt.

Befehlsabrufe verwenden dieselbe Übersetzung wie Daten. Lädt ein Befehl an der virtuellen Adresse 128 von der virtuellen Adresse 3.000, erreicht der Abruf die physische Adresse 20.608 und der Lesezugriff 23.480. Das sind zwei Speicherzugriffe mit zwei übersetzten Adressen, keine gemeinsame Übersetzung für den gesamten Befehl.

Halte die Grenzkonventionen auseinander

Derselbe 8-KB-Bereich hat die physische Endgrenze 28.672. Beide Konventionen erlauben genau die Bytes 20.480 bis 28.671. Der Vergleich der physischen Adresse 21.480 mit der Größe 8.192 vermischt die beiden Konventionen und weist einen zulässigen Zugriff fälschlich ab.

Verschiebe Speicher, ohne Zeiger zu ändern

Die MMU, die Speicherverwaltungseinheit, führt die Prüfungen und die Addition aus. Das Betriebssystem kann einen Prozess anhalten, seinen Bereich an eine andere Stelle kopieren und die Basis ändern. Der Prozess verwendet weiterhin dieselben virtuellen Adressen, weshalb die Relokation dynamisch ist.

Bei der statischen Relokation schreibt dagegen ein Ladeprogramm eingebettete Adressen beim Laden des Codes um. Wird ein Verweis von 1.000 auf 21.480 umgeschrieben, wird eine physische Platzierung im Programm festgehalten. Ein späteres Verschieben erfordert weiteres Umschreiben, und das Umschreiben allein hindert ein Programm nicht daran, eine Adresse außerhalb seines Bereichs zu bilden.

Addiere eine Basis nur zu einer virtuellen Adresse. Sie zu einer bereits übersetzten physischen Adresse zu addieren, verschiebt den Speicherort ein zweites Mal und zerstört die Abbildung.

Die Hardware enthält Übersetzungsregister für den Prozess, der auf einer CPU läuft. Das Betriebssystem verwahrt den gespeicherten Zustand wartender Prozesse. Der Schutz hängt davon ab, dass nur privilegierter Betriebssystemcode diesen Zustand ändern darf.

Stelle die Hardwareoperationen bereit

Die CPU benötigt Benutzer- und Kernelmodus, ein Basis- und Grenzregisterpaar in ihrer MMU sowie Schaltungen für Prüfung und Addition. Außerdem benötigt sie privilegierte Operationen, um das Registerpaar zu ändern und Ausnahmebehandlungsroutinen zu installieren. Unzulässige Adressen und Versuche, privilegierte Befehle im Benutzermodus auszuführen, müssen Ausnahmen auslösen.

Könnte ein Benutzerprogramm seine Basis ändern, könnte es seine Adressen in den Kernel oder in einen anderen Prozess umlenken. Die Grenzprüfungen würden dann den falschen Bereich schützen. Die Beschränkung von Änderungen ist daher Teil des Schutzmechanismus und nicht nur eine administrative Erleichterung.

Erzeuge und starte einen Prozess

Beim Systemstart installiert das Betriebssystem seine Trap- und Ausnahmebehandlungsroutinen, startet den Interrupt-Timer und bereitet seine Aufzeichnungen über freien Speicher vor. Wenn ein Prozess startet, findet das Betriebssystem einen physischen Platz für seinen Adressraum. Bei gleich großen Plätzen kann eine Freispeicherliste einfach erfassen, welche Plätze ungenutzt sind.

Das Betriebssystem markiert den gewählten Platz als belegt, erfasst Basis und Grenze des Prozesses, lädt die Register und wechselt in den Benutzermodus. Der Prozess läuft dann direkt auf der CPU. Die Hardware übersetzt gewöhnliche Zugriffe, ohne für jedes Byte das Betriebssystem aufzurufen.

Stelle beim Kontextwechsel das richtige Paar wieder her

Ein Timerinterrupt übergibt die Kontrolle an das Betriebssystem. Es sichert die Register des bisherigen Prozesses einschließlich Basis und Grenze in dessen Prozesskontrollblock und stellt dann die Werte des nächsten Prozesses wieder her, bevor es in den Benutzermodus zurückkehrt.

Angenommen, die Basis von A ist 20.480 und die von B 40.960, beide mit der Grenze 8.192. Die virtuelle Adresse 1.000 von A erreicht 21.480. Nach dem Wechsel zu B erreicht derselbe virtuelle Wert 41.960. Würden die CPU-Register ohne den Übersetzungszustand wiederhergestellt, würde B mit seinen Zeigern auf den Bereich von A zugreifen.

Die CPU enthält das aktive Paar; jeder Prozess hat sein eigenes gespeichertes Paar. Stelle dir weder ein einziges dauerhaftes Paar für den ganzen Rechner vor noch nimm an, dass die Paare aller Prozesse gleichzeitig auf einer CPU aktiv sind.

Verschieben, Fehler behandeln und beenden

Um A an die physische Adresse 49.152 zu verschieben, nimmt das Betriebssystem A von der CPU, kopiert seinen 8-KB-Bereich und aktualisiert die gespeicherte Basis von A. Sobald A mit dieser geladenen Basis weiterläuft, erreicht die virtuelle Adresse 1.000 die Adresse 50.152. Seine virtuellen Zeigerwerte müssen nicht geändert werden.

Bei einem ungültigen Zugriff löst die Hardware eine Ausnahme aus und übergibt die Ausführung im Kernelmodus an die registrierte Behandlungsroutine. Das Betriebssystem beendet üblicherweise den verursachenden Prozess. Bei der Beendigung gibt es den Platz an die Freispeicherliste zurück und gibt die Prozessdaten frei.

Das Verfahren mit Basis- und Grenzregister erfüllt zwei Ziele mit geringem Aufwand: Die Übersetzung ist transparent und jede Adresse wird anhand des zugewiesenen Bereichs geprüft. Seine größte Schwäche liegt im Verhältnis zwischen diesem Bereich und den Bytes, die der Prozess tatsächlich nutzt.

Reserviere die gesamte Spanne

Die Hardware benötigt bei der häufigen Ausführung nur eine Addition und einen Vergleich. Ein Allokator für Plätze fester Größe kann zudem schnell einen freien Platz auswählen. Keiner dieser Vorteile bedeutet, dass der Platz mit nützlichen Daten gefüllt ist.

In der klassischen Anordnung liegen Code und Heap nahe dem einen Ende und der Stack nahe dem anderen. Ein Basis- und Grenzregisterpaar übersetzt das gesamte Intervall. Die ungenutzte Lücke zwischen Heap und Stack belegt ebenso physischen Speicher wie die genutzten Teile.

Für einen 16 KB großen Adressraum, der 1 KB Code, 2 KB Heap und 1 KB Stack nutzt:

Die Verschwendung ist interne Fragmentierung: ungenutzte Bytes innerhalb eines bereits einem Prozess zugewiesenen Bereichs. Sie entsteht nicht dadurch, dass der Heap-Allokator einen schlechten Block wählt. Selbst ein lückenlos gefüllter 2-KB-Heap lässt die große Lücke in der Mitte reserviert.

Unterscheide drei Größenfragen

Die Spanne des Adressraums, die aktuell genutzten Bytes und der verfügbare physische Speicher sind unterschiedliche Größen. Ein byteadressierter 32-Bit-Adressraum umfasst $2^{32}$ Bytes oder 4 GB. Ihn als einen physischen Block zu reservieren, erfordert die gesamten 4 GB, selbst wenn der Prozess aktuell nur einige Megabyte nutzt.

Unterschiedlich große Plätze heben die Beschränkung auf gleiche Größen auf, beseitigen aber nicht den Bedarf an einer zusammenhängenden Lücke. Außerdem entsteht ein Platzierungsproblem: Das Betriebssystem muss zwischen freien Lücken unterschiedlicher Größe wählen. Wird ein Platz verkleinert, können die niedrigen Codeadressen und eine weit entfernte hohe Stackadresse nicht beide erhalten bleiben, wenn die gesamte Spanne in derselben einfachen Abbildung gültig bleiben muss.

Relokiere die Bereiche getrennt

Code, Heap und Stack müssen im physischen Speicher nicht benachbart sein, damit die Sicht des Programms erhalten bleibt. Erhält jeder Bereich eine eigene Basis und Grenze, kann das Betriebssystem nur für seine genutzte Ausdehnung Speicher zuweisen und die virtuelle Lücke ohne physischen Speicher lassen. Das ist Segmentierung, die Verallgemeinerung eines Relokationspaars auf mehrere logische Bereiche.

Für die obige 16-KB-Anordnung benötigen die drei genutzten Bereiche vor ihrem eigenen Verwaltungsaufwand insgesamt nur 4 KB. Die Speicherersparnis entsteht dadurch, dass andere Einheiten relokiert werden, nicht dadurch, dass die Addition des Basisregisterwerts schneller wird.

Ein Segment ist ein zusammenhängender Bereich eines Adressraums mit einem bestimmten Zweck. Im klassischen Modell erhalten Code, Heap und Stack jeweils ein eigenes Basis- und Größenregisterpaar. Ihre physischen Bereiche können unabhängig voneinander platziert werden, während der Prozess seinen vertrauten virtuellen Aufbau behält.

Stelle nur für die genutzten Bereiche Speicher bereit

Verwende einen 16 KB großen Adressraum mit den folgenden Platzierungen. Die Größen verwenden binäre KB oder KiB.

Code und Heap wachsen zu höheren Adressen hin; die Stackübersetzung verwendet die obere Grenze und einen negativen Offset. Die drei physischen Bereiche benötigen zusammen nur 7 KB. Die virtuellen Lücken dazwischen benötigen keinen physischen Speicher. Ein Segment bleibt zusammenhängend; nur die Segmente selbst müssen nicht mehr nebeneinanderliegen.

Übersetze ein nach oben wachsendes Segment

Bestimme zuerst das Segment. Berechne dann den Offset von seinem virtuellen Anfang aus. Prüfe, ob der Offset nicht negativ und kleiner als die aktuelle Segmentgröße ist, und addiere ihn dann zur physischen Basis:

Für die virtuelle Adresse 500 ist der Code-Offset 500. Er liegt unter 2.048, sodass der Zugriff die physische Adresse 41.460 erreicht.

Für die virtuelle Adresse 5.000 ist der Heap-Offset:

Die Größenprüfung ist erfolgreich, weil 904 unter 3.072 liegt. Das Ergebnis ist:

Die vollständige virtuelle Adresse zur Heap-Basis zu addieren, ergäbe 31.624. Dabei würde fälschlich die virtuelle Anfangsposition des Heaps in eine Berechnung übernommen, die nur den Abstand innerhalb des Segments benötigt.

Prüfe das Segment, nicht nur die Spanne des Adressraums

Die virtuelle Adresse 7.500 passt zwar noch in 14 Bits, ist aber deshalb nicht zulässig. Ihr Heap-Offset beträgt 3.404 und liegt damit außerhalb des aktuellen Bereichs von 3.072 Bytes. Die Hardware löst eine Ausnahme aus. Eine Adresse kann also innerhalb der gesamten Spanne des Adressraums und dennoch außerhalb jedes gültigen Bereichs liegen.

Der Begriff Speicherzugriffsverletzung entstand im Zusammenhang mit ungültigen Zugriffen bei der Segmentierung und wird weiterhin für unzulässige Zugriffe auf Systemen mit anderen Übersetzungsverfahren verwendet. Der Fehlername allein bezeichnet nicht den Übersetzungsmechanismus des Rechners.

Bevor die Hardware Basis und Größe eines Segments verwenden kann, muss sie entscheiden, welches Segment ein Zugriff bezeichnet. Ein expliziter Entwurf legt diese Auswahl in Adressbits ab. Ein impliziter Entwurf leitet sie daraus ab, wie die CPU die Adresse gebildet hat.

Teile eine 14-Bit-Adresse auf

Verwende die obersten zwei Bits für die Segmentnummer und die unteren zwölf Bits für den Offset. Das Zwei-Bit-Feld hat vier mögliche Werte. Verwende 00 für Code, 01 für den Heap und 11 für den Stack; lasse 10 ungenutzt.

Das Offsetfeld kann 4.096 verschiedene Werte von 0 bis 4.095 darstellen. Das maximale virtuelle Fenster jedes Segments ist daher 4 KB groß, selbst wenn der aktuell gültige Bereich des Segments kleiner ist. Maximale Kapazität und aktuelle Größe sind unterschiedliche Begrenzungen.

Für die virtuelle Adresse 5.000 lautet die 14-Bit-Darstellung:

01 0011 1000 1000

Das führende 01 wählt den Heap. Das verbleibende 0011 1000 1000 entspricht dezimal 904. Bei einer Heap-Größe von 3.072 und einer physischen Basis von 26.624 besteht der Offset die Größenprüfung und erreicht die physische Adresse 27.528.

Verwende eine Maske und eine Verschiebung

Dieselbe Aufteilung lässt sich als Code ausdrücken:

segment = (va & 0x3000) >> 12;
offset = va & 0x0FFF;

Die Maske 0x3000 behält die beiden Selektorbits; die Verschiebung um zwölf Stellen bewegt sie an die unteren Positionen und ergibt so die Segmentnummer. Die Maske 0x0FFF setzt diese Selektorbits auf null und behält den Offset. Für va = 0x1388 sind die Ergebnisse Segment 1 und Offset 0x388 oder 904.

Addiere 0x1388 nicht direkt zur Heap-Basis. Der Wert enthält sowohl den Segmentselektor als auch den Offset. Der Selektor wählt die Register; nur der Offset geht in die Übersetzung innerhalb des Segments ein. Die resultierende physische Adresse muss das Bitmuster des Selektors nicht beibehalten.

Erkenne die Kosten der Aufteilung

Ein Zwei-Bit-Selektor erzeugt vier Fenster. Bleibt 10 ungenutzt, ist ein Viertel der virtuellen Spanne von 16 KB nicht verfügbar. Kein Segment kann über sein 4-KB-Fenster hinaus wachsen, nur weil mehr physischer Speicher frei wird. Andere Entwürfe können eine andere Aufteilung verwenden; fasst man Code und Heap in einem Segment zusammen, kann ein einzelnes Selektorbit dieses vom Stack unterscheiden.

Lasse stattdessen die Zugriffsart entscheiden

Bei einem impliziten Entwurf verwenden Befehlsabrufe das Codesegment, weil ihre Adresse aus dem Befehlszähler stammt. Verweise über den Stapelzeiger oder Framepointer verwenden das Stacksegment. Andere Zugriffe verwenden in diesem vereinfachten Modell das Heap-Segment.

Der Stack wächst zu niedrigeren Adressen hin. Seine Übersetzung benötigt neben Basis und Größe ein Richtungsbit. In diesem Modell steht 1 für Wachstum nach oben und 0 für Wachstum nach unten. Zugriffsberechtigungen bilden eine weitere unabhängige Prüfung: Ein Byte kann innerhalb der Grenzen liegen und die angeforderte Operation trotzdem verbieten.

Betrachte die Stackbasis als obere Grenze

Bei einem nach oben wachsenden Segment bezeichnet die Basis sein erstes physisches Byte. Bei einem nach unten wachsenden Segment bezeichnet sie die Grenze unmittelbar oberhalb seines höchstgelegenen physischen Bytes. Im durchgehenden Beispiel umfassen die Stackbasis 53.248 und die Größe 2.048 die physischen Bytes 51.200 bis 53.247.

Wandle für das durch 11 ausgewählte 4-KB-Stackfenster das zwölf Bit große Offsetfeld in einen negativen Versatz um:

Das Feld reicht von 0 bis 4.095, daher ist dieser Versatz immer negativ. Er ist gültig, wenn sein Betrag die aktuelle Stackgröße nicht überschreitet. Addiere dann den vorzeichenbehafteten Versatz zur Basis.

Rechne einen zulässigen Stackzugriff durch

Die virtuelle Adresse 15.500 wählt den Stack. Sein Fenster beginnt virtuell bei 12.288, daher ist ihr Offsetfeld 3.212. Wandle das Feld um:

Die Tiefe 884 liegt innerhalb der Größe 2.048. Die Übersetzung ergibt:

Die positive Zahl 3.212 zur Basis zu addieren, würde auf eine Stelle oberhalb des Stacks verweisen. Das Feld ist noch nicht der Versatz, der für ein nach unten wachsendes Segment benötigt wird.

Die virtuelle Adresse 13.000 ergibt dagegen das Feld 712 und den Versatz −3.384. Seine Tiefe überschreitet 2.048, sodass die Hardware eine Ausnahme auslöst. Vergrößert das Betriebssystem den Stack erfolgreich, können durch die größere Stackgröße weitere niedrige Adressen gültig werden.

Berücksichtige den unteren Endpunkt

Ein Versatz von −2.048 erreicht das niedrigste Byte des Stacks, 51.200, und ist zulässig. Ein Versatz von −2.049 liegt außerhalb. Die Prüfung nach unten schließt daher einen Betrag ein, der der Größe entspricht. Das ergibt dieselbe Byteanzahl wie die Regel für Wachstum nach oben, obwohl diese einen Offset ausschließt, der der Größe entspricht: Die Basis eines nach oben wachsenden Segments ist ein Byte, die eines nach unten wachsenden Segments eine Endgrenze.

Prüfe die angeforderte Operation

Schutzbits erfassen Lese-, Schreib- und Ausführungsberechtigung. Code darf typischerweise gelesen und ausgeführt werden; Heap und Stack dürfen typischerweise gelesen und beschrieben werden. Ein Schreibzugriff auf Code mit Lese- und Ausführungsberechtigung löst selbst bei gültigem Offset eine Ausnahme aus. Auch das Ausführen von Daten löst eine Ausnahme aus, wenn die Ausführungsberechtigung fehlt.

Code, der nur gelesen werden darf, kann gemeinsam genutzt werden. Das Betriebssystem kann die Codesegmente zweier Prozesse auf denselben physischen Bereich verweisen lassen und beiden Schreibzugriffe verbieten. Die Befehlsbytes belegen eine physische Kopie, während jeder Prozess einen eigenen Heap und Stack behält.

Segmentierung ersetzt einen großen Bereich durch mehrere kleinere. Dadurch muss für leere virtuelle Lücken kein physischer Speicher bereitgestellt werden. Das Betriebssystem muss nun aber Bereiche unterschiedlicher Größe platzieren und vergrößern und dabei den Übersetzungszustand jedes Prozesses bewahren.

Sichere jeden Teil der Abbildung

Bei einem Kontextwechsel reichen Basis und Größe allein nicht mehr aus. Das Betriebssystem sichert Basis, Größe, Wachstumsrichtung und Berechtigungen jedes Segments und stellt sie wieder her. Würde ein Stack mit der falschen Richtung oder Code mit den falschen Berechtigungen wiederhergestellt, änderte das die Bedeutung ansonsten identischer Adressen.

Benötigt ein Allokator mehr Heap-Speicher, muss das Betriebssystem das physische Heap-Segment erweitern. Freie Bytes unmittelbar darüber erlauben ein direktes Wachstum. Andernfalls kann das Betriebssystem es in eine geeignete größere Lücke verschieben und seine Basis aktualisieren. Kann es keinen geeigneten Bereich erhalten, schlägt das Wachstum fehl.

Wähle die Granularität

Multics verwendete feingranulare Segmentierung. Mehr Segmente erlauben kleinere Kontrolleinheiten, erfordern aber mehr Übersetzungsmetadaten und Verwaltung.

Finde eine ausreichend große Lücke

Physische Segmente unterschiedlicher Größe hinterlassen freie Lücken unterschiedlicher Größe, wenn Prozesse starten, wachsen und enden. Externe Fragmentierung entsteht, wenn insgesamt genügend Bytes frei sind, aber keine einzelne Lücke das angeforderte Segment aufnehmen kann.

Angenommen, die freien Lücken sind 8 KB, 6 KB und 10 KB groß. Zusammen sind das 24 KB. Ein 12 KB großes Heap-Segment passt dennoch nicht hinein: Die größte verfügbare Lücke ist nur 10 KB groß. Die Lücken auf dem Papier zusammenzufassen, macht ihre physischen Adressen nicht benachbart.

Kompaktierung kann diese Anordnung bereinigen. Das Betriebssystem hält Prozesse an, kopiert Segmente nebeneinander und aktualisiert ihre Basen. Virtuelle Adressen funktionieren weiterhin, weil die Übersetzung die physischen Verschiebungen verbirgt. Das Ergebnis ist ein großer zusammenhängender freier Bereich, doch das Kopieren ist aufwendig und neue Speicherzuweisungen können den Speicher erneut fragmentieren.

Platzierungsstrategien wie First Fit und Best Fit versuchen, ungünstige Reste ohne Kopieren zu begrenzen. Keine Platzierungsstrategie für unterschiedliche Größen beseitigt externe Fragmentierung für jede Folge von Anforderungen. Auch ein einzelnes großes Segment kann innerhalb seiner eigenen Ausdehnung Platz verschwenden, wenn nur verstreute Teile genutzt werden.

Erkenne das Modell in modernen Systemen

Seitenverwaltung teilt Speicher in Stücke fester Größe und vermeidet, dass jeder logische Bereich eine einzige physische Lücke belegen muss. Das Segmentierungsmodell bleibt hilfreich, um Bereiche, Schutz und gemeinsame Nutzung zu verstehen. Im 64-Bit-Modus von x86-64 gelten die gewöhnlichen Segmentbasen für Code, Daten und Stack als null und ihre Grenzen werden nicht geprüft; FS und GS behalten nutzbare Basen für Daten pro Thread oder CPU. Eine Meldung über einen unzulässigen Zugriff als Speicherzugriffsverletzung bedeutet nicht, dass das klassische Modell mit drei Segmenten aktiv ist.

Die Freispeicherverwaltung erfasst verfügbaren Speicher und wählt aus, wo jede Anforderung platziert wird. Gleich große Anforderungen können eine Liste austauschbarer Blöcke nutzen. Unterschiedliche Größen sind schwieriger: Sowohl ein Heap-Allokator als auch ein Betriebssystem, das Segmente platziert, muss einen zusammenhängenden Block finden, der für die nächste Anforderung groß genug ist.

Erkenne externe Fragmentierung

Betrachte einen 60 Byte großen Bereich mit freien Bytes 0–19, einem zugewiesenen Stück bei 20–39 und freien Bytes 40–59. Vierzig Bytes sind frei, aber keine der beiden freien Lücken kann eine Anforderung von 25 Bytes aufnehmen. Das aktive Stück in der Mitte verhindert, dass die Lücken als ein Bereich behandelt werden.

Das ist externe Fragmentierung: Außerhalb zugewiesener Stücke ist Kapazität frei, aber ihre Anordnung macht sie für eine bestimmte zusammenhängende Anforderung unbrauchbar. Die freien Bytes sind nicht verschwunden. Sie können weiterhin kleinere Anforderungen bedienen oder nutzbar werden, wenn dazwischenliegende Stücke freigegeben werden.

Erkenne interne Fragmentierung

Ein Allokator, der Anforderungen auf Vielfache von 16 aufrundet, gibt für eine Anforderung von 20 Bytes ein 32 Byte großes Stück aus. Die 12 zusätzlichen Bytes liegen innerhalb eines bereits vergebenen Stücks. Diese Verschwendung ist interne Fragmentierung.

Die ungenutzte Lücke zwischen Heap und Stack in einem Platz mit Basis- und Grenzregister ist ein weiteres Beispiel. Der Buddy-Allokator verursacht dieselbe Art von Verschwendung, wenn er auf Zweierpotenzen aufrundet. Die Verwaltungsebene ist unterschiedlich, aber der Ort des ungenutzten Speichers ist das bestimmende Merkmal.

Ein Allokator kann unter beidem leiden. Das Aufrunden einer Anforderung kann Bytes innerhalb ihres Stücks verschwenden, während andernorts freie Blöcke getrennt bleiben.

Verschmelze freie Nachbarn, ohne aktive Daten zu verschieben

Das Verschmelzen freier Blöcke verbindet physisch benachbarte freie Blöcke. Wird das mittlere Stück im 60-Byte-Bereich freigegeben, können alle drei Stücke zu einer 60 Byte großen Lücke verschmelzen. Bleibt das mittlere Stück zugewiesen, kann das Verschmelzen es nicht überbrücken. Verschmelzen verringert externe Fragmentierung, garantiert aber nicht für jede Anforderung eine ausreichend große Lücke.

Mehr Speicher für einen Heap kann den Druck verringern, ändert aber nicht die Adressen bestehender aktiver Blöcke. Ihre Platzierung kann weiterhin unbrauchbare kleine Lücken hinterlassen.

Erkläre, warum das Betriebssystem Segmente kompaktieren kann

Das Betriebssystem kann physische Segmente kopieren und ihre Basen aktualisieren. Programme behalten virtuelle Adressen, sodass die Abbildung diese Verschiebungen verbergen kann. Ein allgemeiner C-Heap-Allokator hat keine Übersetzungsschicht zwischen zurückgegebenen Zeigern und Stellen innerhalb des Heaps. Ein Programm kann einen Zeiger in viele Objekte kopiert haben, und der Allokator kann nicht jede Kopie finden und umschreiben.

Würde ein aktiver Heap-Block allein verschoben, würden diese Zeiger weiterhin auf seine alte Position verweisen. Deshalb hält die gewöhnliche malloc-Verwaltung aktive Blöcke an ihren zurückgegebenen Adressen, bis sie freigegeben werden. Sie muss die Fragmentierung durch Platzierung, Wiederverwendung, Aufteilung und Verschmelzen freien Speichers handhaben.

Eine Freispeicherliste erfasst freie Blöcke nach Adresse und Größe. Bei einer Zuweisung wird ein Block aufgeteilt oder aus der Liste entfernt; bei einer Freigabe wird ein Stück zurückgegeben und möglicherweise mit Nachbarn verschmolzen. Die Größenkonvention ist wichtig: Eine erfasste Größe kann die nutzbaren Nutzdaten oder das gesamte Stück einschließlich Metadaten bezeichnen.

Teile einfache Bereiche auf und verschmelze sie

Ignoriere zunächst Verwaltungsköpfe. In einem 60 Byte großen Bereich mit den freien Einträgen (0, 20) und (40, 20) gibt eine am Anfang platzierte Anforderung von 8 Bytes die Adresse 0 zurück. Die verbleibenden Einträge sind (8, 12) und (40, 20).

Beginne erneut mit der ursprünglichen Anordnung und gib die zugewiesenen Bytes 20–39 in der Mitte frei. Ohne Verschmelzen können drei Einträge zu je 20 Bytes eine Anforderung von 30 Bytes einzeln weiterhin nicht bedienen. Das Verschmelzen benachbarter Bereiche ergibt (0, 60), womit dies möglich ist. Die Adressreihenfolge hilft dem Allokator, Nachbarn zu erkennen; benachbarte Listeneinträge allein reichen nicht aus, wenn ihre physischen Bereiche nicht aneinandergrenzen.

Finde den Verwaltungskopf über den Benutzerzeiger

free(ptr) erhält keine Größe. Ein einfacher Allokator speichert einen Verwaltungskopf mit der Größe unmittelbar vor den Nutzdaten, manchmal zusammen mit einem Prüfwert oder einer magischen Zahl. Durch Abziehen der Länge des Verwaltungskopfs findet er die Metadaten.

Bei einem 16 Byte großen Verwaltungskopf belegt eine Anforderung von 96 Bytes insgesamt 112 Bytes. Das Programm erhält einen Zeiger 16 Bytes nach dem Anfang des Stücks. Die Freigabe gibt den gesamten Bereich von 112 Bytes einschließlich Verwaltungskopf für die weitere Verwaltung zurück. Die Speicherausrichtung kann eine Aufrundung hinzufügen; diese Beispielgrößen erfüllen bereits die Ausrichtung auf 16 Bytes.

Verfolge eine eingebettete Freispeicherliste

Angenommen, ein 4.096 Byte großer Heap beginnt bei 32.768. Ein freier Knoten benötigt 16 Bytes und erfasst die nutzbaren Bytes nach dem Knoten. Anfangs erfasst er 4.080 nutzbare Bytes.

Drei Anforderungen von je 96 Bytes verbrauchen jeweils 112 Bytes:

Der verbleibende freie Knoten beginnt bei 33.104. Seine nutzbare Größe beträgt 3.744 Bytes. Die Rechnung lautet:

Die Freigabe des Zeigers 32.896 führt zum Verwaltungskopf bei 32.880. Dieses Stück wird zu einem freien Knoten mit 96 nutzbaren Bytes. Es kann nicht mit dem letzten Knoten bei 33.104 verschmelzen, weil die dritte Speicherzuweisung dazwischenliegt. Werden alle drei Speicherzuweisungen freigegeben und verschmolzen, beschreibt ein Knoten wieder 4.080 nutzbare Bytes. Durch das Einbeziehen der alten inneren Verwaltungsköpfe werden deren Bytes innerhalb des verschmolzenen Bereichs verfügbar.

Halte die Verwaltungsdaten im verwalteten Bereich

Eingebettete Listenknoten liegen im freien Speicher selbst, sodass die Verwaltung der Liste keine separate Speicherzuweisung für jeden Eintrag benötigt. Der Knoten enthält eine Größe und einen Verweis auf den nächsten freien Block. Passt kein Block, kann der Allokator mit sbrk oder mmap weiteren Speicher anfordern; kann er nicht genug Speicher erhalten, führt das zu NULL.

Ein Überlauf kann einen benachbarten Verwaltungskopf oder Knoten überschreiben. Das erklärt, warum der sichtbare Fehler bei einem späteren malloc oder free auftreten kann, nachdem der Schreibzugriff die Liste beschädigt hat.

Eine Platzierungsstrategie wählt zwischen Blöcken, die für eine Anforderung groß genug sind. Unterschiedliche Entscheidungen hinterlassen unterschiedliche Lücken für spätere Anforderungen. Neben der Fragmentierung spielt die Suchzeit eine Rolle, und keine Strategie ist für jede Arbeitslast überlegen.

Vergleiche die Suchregeln

Für Best Fit und Worst Fit muss eine einfache unsortierte Liste vollständig durchsucht werden. Andere Strukturen können passende Größen schneller finden. First Fit bedeutet den ersten Block in der gewählten Listenreihenfolge; das muss nicht die kleinste Adresse sein, sofern die Liste nicht nach Adressen sortiert ist.

Verfolge die erste Anforderung

Nimm freie Blöcke von 30, 12, 50 und 20 Bytes in Adressreihenfolge. Ignoriere Verwaltungsköpfe und nimm an, dass bei der Aufteilung jeder Rest erhalten bleiben kann. Eine Anforderung von 18 Bytes verändert die Liste wie folgt:

• Best Fit nutzt 20 und hinterlässt 30, 12, 50, 2.
• Worst Fit nutzt 50 und hinterlässt 30, 12, 32, 20.
• First Fit nutzt 30 und hinterlässt 12, 12, 50, 20.
• Next Fit beginnt beim vierten Block, nutzt 20 und hinterlässt 30, 12, 50, 2.

Next Fit benötigt eine Anfangsposition, um die Auswahl zu bestimmen. Der Name allein bezeichnet nicht den ersten Eintrag der Liste. Bei der Verfolgung muss dieser Suchzustand zwischen Anforderungen erhalten bleiben.

Sieh, warum die nächste Anforderung das Urteil ändert

Eine anschließende Anforderung verlangt 45 Bytes. Best Fit und First Fit haben beide den 50-Byte-Block erhalten, daher gelingt die Anforderung bei beiden. Der größte verbleibende Block bei Worst Fit ist 32 Bytes groß, sodass die Anforderung trotz insgesamt 94 freier Bytes fehlschlägt:

Dieser Fehlschlag ist externe Fragmentierung. Die frühere Entscheidung hat die einzige ausreichend große Lücke aufgeteilt. Best Fit hat dagegen einen 2 Byte großen Rest hinterlassen, der für nützliche spätere Anforderungen zu klein sein kann. Ein unmittelbar kleiner Rest ist kein Beleg dafür, dass eine Strategie den Speicher über die gesamte Folge von Anforderungen gut nutzt.

Stimme Strategie und Datenstruktur aufeinander ab

Das Durchsuchen Tausender Einträge kann aufwendig sein, selbst wenn jede Platzierung gut ist. Praktische Allokatoren gruppieren Blöcke nach Größe oder verwenden durchsuchbare Strukturen wie balancierte Bäume. Eine nach Adressen sortierte Liste unterstützt außerdem das Verschmelzen, weil physische Nachbarn leichter zu finden sind.

Der Zuweisungsmechanismus (finden, aufteilen, Metadaten aktualisieren) kann gleich bleiben, während sich die Strategie ändert. Um Strategien fair zu vergleichen, verfolge dieselben Anforderungen und Freigaben, halte die Regeln für den Verwaltungsaufwand gleich und berücksichtige sowohl die entstehenden Lücken als auch den Suchaufwand.

Die allgemeine Suche in einer Freispeicherliste ist flexibel, kann aber aufwendig sein. Spezialisierte Allokatoren machen häufige Anforderungen vorhersehbar, indem sie Größen gruppieren, wiederverwendbare Objekte erhalten oder Blockgrößen auf Zweierpotenzen beschränken.

Verwende häufige Größen und initialisierte Objekte wieder

Nach Größenklassen getrennte Freispeicherlisten halten für häufige Größen separate Listen bereit und verwenden für andere Anforderungen einen allgemeinen Allokator. Eine Anforderung einer häufigen Größe kann direkt mit einem Block aus ihrer Liste bedient werden. Gleich große Blöcke erzeugen untereinander keine externe Fragmentierung, aber die Aufteilung der Kapazität auf Listen ist eine Strategieentscheidung: Übrige Blöcke einer Größe können eine andere Größe möglicherweise nicht bedienen.

Ein Slab-Allokator unterhält einen Objektcache für einen wiederkehrend benötigten Kernelobjekttyp, etwa einen Inode, eine Sperre oder einen Prozessdeskriptor. Ein Slab ist in Objekte dieses Typs unterteilt. Der Cache erhält bei Bedarf weitere Slabs und kann einen vollständig freien Slab an einen allgemeinen Allokator zurückgeben. Jeff Bonwick entwickelte diesen Ansatz für Solaris.

Der Cache hält freigegebene Objekte in einem initialisierten Zustand und vermeidet so wiederholtes Einrichten und Zerstören. Das spart über die Suche selbst hinaus Zeit.

Teile einen Buddy-Bereich auf

Ein binärer Buddy-Allokator beginnt mit einem Bereich, dessen Größe eine Zweierpotenz ist, und rundet jede Anforderung auf eine Blockgröße auf, die einer Zweierpotenz entspricht. Er teilt einen freien Block wiederholt in gleiche Hälften, bis eine Hälfte gerade noch passt. Die beiden Hälften einer Teilung sind Buddies.

Runde für eine Anforderung von 5 KB in einem 64-KB-Bereich 5 KB auf 8 KB auf. Teile 64 in zwei 32-KB-Blöcke, dann den gewählten 32-KB-Block in zwei 16-KB-Blöcke und anschließend den gewählten 16-KB-Block in zwei 8-KB-Blöcke. Die Rückgabe des ersten 8-KB-Blocks hinterlässt freie Buddies bei den Offsets 8 KB, 16 KB und 32 KB mit den jeweiligen Größen 8 KB, 16 KB und 32 KB.

Die Zuweisung verschwendet 3 KB innerhalb ihres 8-KB-Blocks. Das ist interne Fragmentierung, die für regelmäßiges Aufteilen und Verschmelzen in Kauf genommen wird.

Finde den einzig zulässigen Partner zum Verschmelzen

Für Offsets, die vom Anfang des verwalteten Bereichs aus gemessen werden, gilt:

Das exklusive Oder kehrt das der Blockgröße entsprechende Bit um. Bei einem 8-KB-Block mit Offset 0 liegt sein Buddy bei Offset 8.192. Bei einem 16-KB-Block mit Offset 16.384 liegt sein Buddy bei 0.

Wird der erste 8-KB-Block freigegeben, verschmilzt er mit seinem freien 8-KB-Buddy. Der entstehende 16-KB-Block kann mit seinem freien Buddy verschmelzen, danach kann der entstehende 32-KB-Block erneut verschmelzen. Das Verschmelzen endet, wenn der benötigte gleich große Buddy belegt ist. Dass zwei Blöcke benachbart und frei sind, reicht nicht aus, wenn sie keine Buddies aus derselben Teilung sind.

Eine Anforderung von 20 KB erhält 32 KB, wobei 12 KB oder 37,5 % des Blocks verschwendet werden. Linux kombiniert einen Buddy-Allokator für physischen Speicher mit Objektcaches nach dem Slab-Prinzip. Allokatoren für Programme mit mehreren Threads verwenden außerdem lokale Caches oder mehrere Arenen, um das Warten auf eine gemeinsame Zuweisungssperre zu verringern; glibc, jemalloc und tcmalloc nutzen Varianten dieser Ideen.