Clevere Speicherverwaltung mit konstanten Zeitoperationen?

Question

Betrachten wir ein Speichersegment (dessen Größe bei Bedarf wie eine Datei wachsen oder schrumpfen kann), auf der Sie zwei grundlegende Speicherzuweisungsvorgänge mit festen Größenblöcken ausführen können:

• Zuteilung eines Blocks
• Befreiung eines zuvor zugewiesenen Blocks, der nicht mehr verwendet wird.

Als Anforderung darf das Speicherverwaltungssystem auch nicht zugewiesene Blöcke umgehen: Ihr Index/ihre Adresse muss unverändert bleiben.

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

Besserer Ansatz: Halten Sie den Zähler, aber pflegen Sie eine Liste von verationalen Blöcken (die in ständiger Zeit erfolgen können) und verwenden Sie sie als Quelle für neue Zuteilungen, solange er nicht leer ist.

Was nun? Gibt es etwas Kluges, das getan werden kann, immer noch mit Einschränkungen der ständigen Zeitzuweisung und Deallokation, das das Speichersegment so kurz wie möglich halten würde?

(Ein Ziel könnte es sein, den aktuell nicht zugeordneten Block mit der kleinsten Adresse zu verfolgen, aber er scheint in ständiger Zeit nicht machbar zu sein…)

Answer 1

Mit festen Blöcken, die Sie beschrieben haben, ist a Kostenlose Liste. Dies ist eine sehr häufige Technik mit der folgenden Wendung: Die Liste der freien Blöcke wird in den freien Blöcken selbst gespeichert. In C -Code würde es 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 die gleiche Größe haben, und diese Größe ist ein Vielfaches der Größe eines Zeigers, so dass die Ausrichtung erhalten bleibt. Zuweisung und Deallocation sind konstante Zeit (dh so, wie der Speicherzugriff und elementare Ergänzungen-in einem modernen Computer kann ein Speicherzugriff Cache-Missen und sogar virtuelle Speicher beinhalten, weshalb der Festplatten zugreift, sodass die "konstante Zeit", also die "konstante Zeit" kann ziemlich groß sein). Es gibt keinen Speicheraufwand (keine zusätzlichen Zeiger pro Block oder solche Dinge; die zugewiesenen Blöcke sind zusammenhängend). Außerdem erreicht der Zeiger der Allokation nur dann einen bestimmten Punkt, wenn zu einer Zeit, dass viele Blöcke zugewiesen werden mussten: Da die Zuweisung die Verwendung der freien Liste bevorzugt, wird der Zeiger nur dann erhöht, wenn der Platz unter dem aktuellen Zeiger voll ist. In diesem Sinne ist dies ein optimal Technik.

Abnehmen Der Zeiger der Allokation nach einer Veröffentlichung kann komplexer sein, da freie Blöcke nur durch Befolgen der freien Liste zuverlässig identifiziert werden können, die sie in unvorhersehbarer Reihenfolge durchläuft. Wenn Sie die große Segmentgröße, wenn möglich, für Sie wichtig ist, möchten Sie eine alternative Technik mit mehr Overhead verwenden: Zwischen zwei beliebigen zugewiesenen Blöcken setzen Sie ein "Loch" ein. Die Löcher sind zusammen mit einer doppelt verknüpften Liste in Speicherreihenfolge verknüpft. Sie benötigen ein Datenformat für ein Loch, sodass Sie die Loch -Startadresse suchen können, indem Sie wissen, wo es endet, und auch die Lochgröße, wenn Sie wissen, wo das Loch im Speicher beginnt. Wenn Sie dann einen Block veröffentlichen, erstellen Sie ein Loch, das Sie mit dem nächsten und den vorherigen Löchern verschmelzen und die geordnete Liste aller Löcher wieder aufbauen. Der Overhead ist dann etwa zwei Wörter in Zeigergröße pro zugewiesenem Block; Zu diesem Preis können Sie jedoch das Auftreten eines "endgültigen Lochs" zuverlässig erkennen, dh eine Gelegenheit, die große Segmentgröße zu verringern.

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

Answer 2

In dieser Antwort geht es um generische Gedächtnisverwaltungstechniken. Ich habe es verpasst, dass die Frage nach dem Fall stellt, in dem alle Blöcke die gleiche Größe haben (und ausgerichtet sind).

---

Die grundlegenden Strategien, die Sie kennen sollten Freunde-System. Ich schrieb eine kurze Zusammenfassung Einmal für einen Kurs, den ich unterrichtete, hoffe ich, dass es lesbar ist. Ich zeige dort auf Eine ziemlich erschöpfende Umfrage.

In der Praxis sehen Sie verschiedene Änderungen dieser grundlegenden Strategien. Aber keine davon ist wirklich konstante Zeit! Ich denke nicht, dass das im schlimmsten Fall möglich ist, wenn sie eine begrenzte Menge an Speicher verwendet.

Answer 3

Vielleicht möchten Sie einen Blick sehen Amortisierte Analyse und insbesondere dynamische Arrays. Auch wenn die Operationen bei jedem Schritt nicht wirklich in ständiger Zeit erledigt sind, sieht es auf lange Sicht so aus, als wäre es der Fall.