Verwalten eines zusammenhängenden Chunks ohne Malloc/Neu oder Frei/Löschen

Question

Wie würde man einen benutzerdefinierten MemoryManager erstellen, um einen bestimmten, zusammenhängenden Speicherbereich ohne die Hilfe anderer Speichermanager (wie Malloc/New) zu verwalten C++?

Hier einige weitere Kontext:

MemManager::MemManager(void* memory, unsigned char totalsize) 
    { 
     Memory = memory; 
     MemSize = totalsize; 
    } 

Ich muss in der Lage, vergeben und frei bis Blöcke dieser zusammenhängenden Speicher einen MemManager verwenden. Der Konstruktor erhält die Gesamtgröße des Chunks in Bytes.

Eine Allocate-Funktion sollte die erforderliche Speichermenge in Byte aufnehmen und einen Zeiger auf den Anfang dieses Speicherblocks zurückgeben. Wenn kein Speicher mehr vorhanden ist, wird ein NULL-Zeiger zurückgegeben.

Eine Deallocate-Funktion sollte den Zeiger auf den Speicherblock aufnehmen, der freigegeben werden muss, und ihn zur späteren Verwendung an den MemManager zurückgeben.

Beachten Sie die folgenden Einschränkungen:

-Aside aus dem Teil des Speichers zu ihm gegeben, kann der MemManager nicht alle dynamischen Speicher verwendet

-wie ursprünglich angegeben, können die MemManager NICHT andere Speicher-Manager verwenden, um Führen Sie seine Funktionen, einschließlich new/malloc und löschen/frei

Ich habe diese Frage auf mehrere Vorstellungsgespräche bereits erhalten, aber auch Stunden der Online-Recherche hat mir nicht geholfen und ich habe jedes Mal versagt. Ich habe ähnliche Implementierungen gefunden, aber sie haben entweder malloc/new verwendet oder waren allgemeiner und angeforderter Speicher vom Betriebssystem, was ich nicht tun darf.

Beachten Sie, dass ich malloc/new und free/delete bequem bin und mit ihnen wenig Mühe habe.

Ich habe versucht, Implementierungen, die Knotenobjekte in einer LinkedList-Mode verwenden, die auf den Block des zugeordneten Speichers verweisen und angeben, wie viele Bytes verwendet wurden. Bei diesen Implementierungen war ich immer gezwungen, neue Knoten auf dem Stack zu erstellen und sie in die Liste einzufügen, aber sobald sie den Rahmen sprengten, brach das gesamte Programm, da die Adressen und Speichergrößen verloren gingen.

Wenn jemand irgendeine Idee hat, wie man so etwas implementiert, würde ich es sehr schätzen. Danke im Voraus!

BEARBEITEN: Ich habe vergessen, dies direkt in meinem ursprünglichen Beitrag anzugeben, aber die mit diesem MemManager zugewiesenen Objekte können unterschiedliche Größen haben.

BEARBEITEN 2: Am Ende habe ich homogene Speicherblöcke verwendet, was dank der Informationen in den Antworten sehr einfach zu implementieren war. Die genauen Regeln bezüglich der Implementierung selbst wurden nicht angegeben, daher habe ich jeden Block in 8 Bytes aufgeteilt. Wenn der Benutzer mehr als 8 Bytes angefordert hat, konnte ich es nicht geben, aber wenn der Benutzer weniger als 8 Bytes anforderte (aber> 0), würde ich zusätzlichen Speicher geben. Wenn die übergebene Speichermenge nicht durch 8 teilbar wäre, gäbe es am Ende verschwendeten Speicher, was viel besser ist, als mehr Speicher zu verwenden, als Sie bekommen.

Answer 1

I haben versucht Implementierungen, die Knotenobjekte in einer VerketteteListe Mode verwenden, die zugeordnet zu den Speicherblock zeigen und angeben, wie viele Bytes verwendet wurden.Mit diesen Implementierungen wurde ich jedoch immer gezwungen, neue Knoten auf dem Stapel zu erstellen und sie in die Liste einzufügen, aber sobald sie den Rahmen sprengten, brach das gesamte Programm , da die Adressen und Speichergrößen verloren gingen.

Sie sind auf dem richtigen Weg. Sie können den LinkedList-Knoten in den Speicherblock einbetten, den Sie mit "reinterpret_cast <>" erhalten haben. Da Sie Variablen im Speichermanager speichern dürfen, solange Sie Speicher nicht dynamisch zuweisen, können Sie den Kopf der Liste mit einer Elementvariablen verfolgen. Unter Umständen müssen Sie besonders auf die Objektgröße achten (Sind alle Objekte gleich groß? Ist die Objektgröße größer als die Größe Ihres verknüpften Listenknotens?)

Angenommen, die Antworten auf die vorherigen Fragen sind wahr Verarbeiten Sie dann den Speicherblock und teilen Sie ihn mit Hilfe einer Hilfsliste, die freie Knoten verfolgt, in kleinere, objektgroße Blöcke auf. Ihre freie Knoten Struktur wird so etwas wie

struct FreeListNode 
{ 
    FreeListNode* Next; 
}; 

werden, wenn die Zuweisung, alles, was Sie tun, ist der Kopfknoten aus der freien Liste entfernen und gibt es zurück. Beim Aufheben der Zuordnung wird nur der freigegebene Speicherblock in die freie Liste eingefügt. nur eine Schleife ist, den Speicherblock bis Splitting:

// static_cast only needed if constructor takes a void pointer; can't perform pointer arithmetic on void* 
char* memoryEnd = static_cast<char*>(memory) + totalSize; 
for (char* blockStart = block; blockStart < memoryEnd; blockStart += objectSize) 
{ 
    FreeListNode* freeNode = reinterpret_cast<FreeListNode*>(blockStart); 
    freeNode->Next = freeListHead; 
    freeListHead = freeNode; 
} 

Wie Sie die Funktion übernimmt in der Objektgröße Weisen erwähnt, müssen die oben wird zum Speichern von Metadaten geändert werden. Sie können dies tun, indem Sie die Größe des freien Blocks in die Daten des freien Listenknotens einbeziehen. Dies beseitigt die Notwendigkeit, den Anfangsblock zu teilen, führt jedoch Komplexität in Allocate() und Deallocate() ein. Sie müssen sich außerdem Gedanken über die Speicherfragmentierung machen, denn wenn Sie keinen freien Block mit genügend Speicher zum Speichern des angeforderten Betrags haben, können Sie nichts anderes tun als die Zuweisung zu verwerfen. Ein paar Allocate() -Algorithmen könnten sein:

1) Gib einfach den ersten verfügbaren Block zurück, der groß genug ist, um die Anfrage zu halten, und aktualisiere den freien Block wie nötig. Dies ist O (n) in Bezug auf die Suche in der freien Liste, muss aber möglicherweise nicht viele freie Blöcke durchsuchen und könnte zu Fragmentierungsproblemen auf der Straße führen.

2) Suchen Sie die freie Liste nach dem Block, der die kleinste Menge frei hat, um den Speicher zu halten. Dies ist immer noch O (n) in Bezug auf die Suche in der freien Liste, da Sie jeden Knoten untersuchen müssen, um den am wenigsten verschwenderischen zu finden, aber dazu beitragen können, Fragmentierungsprobleme zu verzögern.

Wie auch immer, mit variabler Größe müssen Sie auch Metadaten für Zuordnungen speichern. Wenn Sie überhaupt keine dynamische Zuordnung vornehmen können, ist der beste Platz vor oder nach dem vom Benutzer angeforderten Block; Sie können Features hinzufügen, um Pufferüberläufe/-unterläufe während Deallocate() zu erkennen, wenn Sie einen mit einem bekannten Wert initialisierten Padding hinzufügen und das Auffüllen für einen Unterschied überprüfen möchten. Sie können auch einen kompakten Schritt hinzufügen, wie in einer anderen Antwort erwähnt, wenn Sie damit umgehen wollen.

Eine letzte Anmerkung: Sie müssen vorsichtig sein, wenn Sie der FreeListNode-Helperstruktur Metadaten hinzufügen, da die kleinste zulässige freie Blockgröße sizeof (FreeListNode) ist. Dies liegt daran, dass Sie die Metadaten im freien Speicherblock selbst speichern. Je mehr Metadaten Sie für Ihre internen Zwecke speichern müssen, desto verschwenderischer ist Ihr Speichermanager.

Answer 2

Wenn Sie Speicher verwalten, möchten Sie im Allgemeinen den von Ihnen verwalteten Speicher verwenden, um alle Metadaten zu speichern, die Sie benötigen. Wenn Sie sich eine der Implementierungen von malloc ansehen (ptmalloc, phkmalloc, tcmalloc, etc ...), werden Sie sehen, dass sie so allgemein implementiert sind (natürlich unter Vernachlässigung statischer Daten).Die Algorithmen und Strukturen sind sehr unterschiedlich, aus verschiedenen Gründen, aber ich werde versuchen, einen kleinen Einblick in das allgemeine Speichermanagement zu geben.

Die Verwaltung homogener Speicherbereiche unterscheidet sich von der Verwaltung nicht homogener Abschnitte, und es kann viel einfacher sein. Ein Beispiel ...

MemoryManager::MemoryManager() { 

    this->map = std::bitset<count>(); 
    this->mem = malloc(size * count); 

    for (int i = 0; i < count; i++) 
    this->map.set(i); 
} 

Zuteilen darum, das nächste Bit in der std::bitset zu finden (Compiler optimieren könnte), Kennzeichnung der Brocken als zugewiesen und wiederkehr es. Die Aufhebung der Zuweisung erfordert nur die Berechnung des Index und die Markierung als nicht zugewiesen. A free list ist ein anderer Weg (was here beschrieben wird), aber es ist ein wenig weniger Speicher effizient, und möglicherweise nicht CPU-Cache gut.

Eine freie Liste kann die Grundlage für die Verwaltung nichthomogener Speicherbereiche sein. Damit müssen Sie die Größe der Chunks zusätzlich zum nächsten Zeiger im Speicherbereich speichern. Mit der Größe können Sie größere Stücke in kleinere Stücke teilen. Dies führt jedoch im Allgemeinen zu einer Fragmentierung, da das Zusammenführen von Blöcken nicht trivial ist. Aus diesem Grund behalten die meisten Datenstrukturen Listen von Blöcken gleicher Größe bei und versuchen, Anforderungen so genau wie möglich zuzuordnen.