Clevere Speicherverwaltung mit konstanten Zeitvorgängen?

18

Betrachten wir ein Speichersegment (dessen Größe bei Bedarf wie eine Datei wachsen oder schrumpfen kann), für das Sie zwei grundlegende Speicherzuweisungsoperationen mit Blöcken fester Größe ausführen können:

  • Zuweisung eines Blocks
  • Freigeben eines zuvor zugewiesenen Blocks, der nicht mehr verwendet wird.

Außerdem darf sich das Speicherverwaltungssystem nicht in aktuell zugewiesenen Blöcken bewegen: Ihr Index / ihre Adresse müssen unverändert bleiben.

Der einfachste Speicherverwaltungsalgorithmus würde einen globalen Zähler (mit dem Anfangswert 0) inkrementieren und seinen neuen Wert als Adresse für die nächste Zuordnung verwenden. Dies wird es jedoch niemals ermöglichen, das Segment zu verkürzen, wenn nur wenige zugewiesene Blöcke übrig bleiben.

Besserer Ansatz: Behalten Sie den Zähler bei, aber führen Sie eine Liste von freigegebenen Blöcken (die in konstanter Zeit ausgeführt werden können) und verwenden Sie ihn als Quelle für neue Zuweisungen, solange er nicht leer ist.

Was nun? Gibt es etwas Kluges, das trotz konstanter Zeitzuweisung und Freigabe der Zuweisung getan werden kann, um das Speichersegment so kurz wie möglich zu halten?

(Ein Ziel könnte sein, den momentan nicht zugewiesenen Block mit der kleinsten Adresse zu verfolgen, aber es scheint nicht in konstanter Zeit machbar zu sein ...)

Stéphane Gimenez
quelle
Wäre die Überprüfung einer Liste nicht mehr zeitlich konstant, da die Liste aufgrund einiger zuvor durchgeführter Zuordnungen / Aufhebungen möglicherweise wächst oder schrumpft?
Sim
@ Sim, ich nahm an, es ist eine verknüpfte Liste und mit ihr wären die Operationen , weil Sie immer nur mit dem Kopf arbeiten. O(N)
Svick
Ich denke, Ihr "besserer Ansatz" wird bereits die optimale Menge an Speicher verwenden, dh, er wird niemals zusätzlichen Speicher zuweisen, wenn ein freier Block vorhanden ist. Wie können Sie sich vorstellen, dass der „clevere“ Ansatz das verbessern würde? Meinen Sie damit, dass die Allokation kurz vor dem Beginn erfolgen sollte, damit die Chance größer ist, dass Sie das Segment nach der Aufhebung der Allokation verkleinern können?
Svick
@Sim: Entschuldigung, vielleicht hätte ich den Begriff Stack verwenden sollen (aber ich dachte, es könnte verwirrend sein), 'Deallocate' ist Push und 'Allocation' ist Pop, oder in dem Fall, dass es fehlschlägt, einfach auf die Zählerinkrementierung zurückgreifen. Beides ist konstante Zeit.
Stéphane Gimenez
Haben Sie Echtzeitbeschränkungen, oder ist Ihnen die amortisierte konstante Zeit recht? Die Antworten dürften ziemlich unterschiedlich sein.
Gilles 'SO- hör auf böse zu sein'

Antworten:

11

Bei Blöcken mit fester Größe ist das, was Sie beschrieben haben, eine freie Liste . Dies ist eine sehr verbreitete Technik mit der folgenden Wendung: Die Liste der freien Blöcke wird in den freien Blöcken selbst gespeichert. In C-Code würde das so aussehen:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Dies funktioniert gut, solange alle zugewiesenen Blöcke dieselbe Größe haben und diese Größe ein Vielfaches der Größe eines Zeigers ist, sodass die Ausrichtung erhalten bleibt. Zuweisung und Freigabe erfolgen in konstanter Zeit (dh so konstant wie Speicherzugriffe und elementare Ergänzungen). In einem modernen Computer kann ein Speicherzugriff Cachefehler und sogar virtuellen Speicher, also Festplattenzugriffe, zur Folge haben. kann ziemlich groß sein). Es gibt keinen Speicheraufwand (keine zusätzlichen Zeiger pro Block oder ähnliches; die zugewiesenen Blöcke sind zusammenhängend). Außerdem erreicht der Zuweisungszeiger nur dann einen bestimmten Punkt, wenn zu einem Zeitpunkt so viele Blöcke zugewiesen werden mussten: Da die Zuweisung die freie Liste bevorzugt, wird der Zuweisungszeiger nur erhöht, wenn der Raum unter dem aktuellen Zeiger taktvoll ist. In diesem Sinne, Technik.

AbnehmendDer Zuweisungszeiger nach einer Freigabe kann komplexer sein, da freie Blöcke nur durch Befolgen der freien Liste, die sie in unvorhersehbarer Reihenfolge durchläuft, zuverlässig identifiziert werden können. Wenn es für Sie wichtig ist, die Größe des großen Segments nach Möglichkeit zu verringern, können Sie eine alternative Technik mit mehr Overhead verwenden: Zwischen zwei zugewiesenen Blöcken wird ein "Loch" eingefügt. Die Löcher werden mit einer doppelt verknüpften Liste in der Speicherreihenfolge miteinander verknüpft. Sie benötigen ein Datenformat für eine Bohrung, damit Sie die Bohrungsstartadresse ermitteln können, indem Sie wissen, wo sie endet, und auch die Bohrungsgröße, wenn Sie wissen, wo die Bohrung im Speicher beginnt. Wenn Sie dann einen Block freigeben, erstellen Sie eine Bohrung, die Sie mit der nächsten und der vorherigen Bohrung zusammenführen. Dabei wird (noch in konstanter Zeit) die geordnete Liste aller Bohrungen neu erstellt. Der Overhead beträgt dann ungefähr zwei Wörter in Zeigergröße pro zugewiesenem Block; Zu diesem Preis können Sie jedoch zuverlässig das Auftreten eines "endgültigen Lochs" erkennen, dh eine Gelegenheit, die Größe des großen Segments zu verringern.

Es gibt viele mögliche Variationen. Ein gutes Einführungspapier ist Dynamic Storage Allocation: Eine Umfrage und eine kritische Überprüfung von Wilson et al.

Thomas Pornin
quelle
4
Wie finden Sie die Löcher, die in konstanter Zeit einem Standort am nächsten liegen?
Raphael
1
Bei der zweiten von mir beschriebenen Methode ist ein Loch ein Header (ein Paar Zeiger für die Liste der Löcher) zusammen mit Platz für einen oder mehrere Datenblöcke. Zwischen zwei zugewiesenen Blöcken befindet sich immer ein Loch, auch wenn es sich um ein Mikroloch handelt, das nur aus einem Lochkopf besteht. Das Auffinden der nächstgelegenen Löcher ist also einfach: Sie befinden sich direkt vor und direkt nach dem Schlitz. Natürlich werden Mikrolöcher nicht in die Liste der freien Löcher aufgenommen (die Liste der zuweisungsberechtigten Löcher). Eine andere Sichtweise ist, dass Sie jedem Block und jedem (Nicht-Mikro-) Loch einen Header hinzufügen (die Zuweisung unter 16-Bit-Ms-Dos hat so funktioniert).
Thomas Pornin
4

In dieser Antwort geht es um allgemeine Speicherverwaltungstechniken. Ich vermisste, dass die Frage nach dem Fall fragt, in dem alle Blöcke die gleiche Größe haben (und ausgerichtet sind).


Die grundlegenden Strategien, die Sie kennen sollten, sind First-Fit, Next-Fit, Best-Fit und das Buddy-System . Ich habe einmal eine kurze Zusammenfassung für einen Kurs geschrieben, ich hoffe, er ist lesbar. Ich weise dort auf eine ziemlich ausführliche Umfrage hin .

In der Praxis sehen Sie verschiedene Modifikationen dieser Grundstrategien. Aber keine davon ist wirklich konstante Zeit! Ich denke nicht, dass dies im schlimmsten Fall möglich ist, wenn nur wenig Speicherplatz zur Verfügung steht.

rgrig
quelle
Interessant, ich muss das im Detail lesen. Es scheint jedoch, dass sich diese Systeme speziell mit nicht konstanten Größenzuweisungen befassen, mit denen ich nicht konfrontiert bin.
Stéphane Gimenez
Richtig. Entschuldigung, ich habe deine Frage viel zu schnell gelesen.
Rgrig
OK, nur ein Kommentar, bevor ich schlafen gehe: Ich denke, Sie müssen den kleinsten freien Block zuweisen, wenn Sie für alle möglichen Abläufe das kürzestmögliche Segment behalten möchten. Die einzige Verbesserung, die mir in den Sinn kommt, ist die Verwendung eines Heaps anstelle Ihrer Liste, aber das wird , nicht konstant. O(lgn)
Rgrig
s / kleinster freier Block / freier Block bei kleinster Adresse /
rgrig
2

Möglicherweise möchten Sie sich die amortisierte Analyse und insbesondere dynamische Arrays ansehen . Auch wenn die Operationen nicht bei jedem Schritt wirklich in konstanter Zeit ausgeführt werden, sieht es auf lange Sicht so aus, als ob dies der Fall wäre.

Gallais
quelle
2
Und wie genau helfen dynamische Arrays bei der Speicherzuweisung?
Svick
Sie würden Blöcke zusammenhängender Zellen mit der gleichen Art von Algorithmus (de) zuweisen? Ihre gesamte Datei wäre eine verknüpfte Liste von immer größeren Stücken.
Gallais