Implementierung von malloc() und free() – Aufteilen großer Blöcke

Im vorherigen Beitrag dieser Serie haben wir gesehen, wie die Reihenfolge, in der wir Speicherblöcke zur Wiederverwendung auswählen, zu einem größeren oder geringeren Speicherverbrauch führen kann, und wir haben unsere Funktionen geändert, um dies zu vermeiden Abfall. Aber wir müssen ein anderes, noch schwerwiegenderes Problem lösen: Manchmal kann ein sehr großer Speicherblock den Platz belegen, den mehrere kleinere Blöcke nutzen könnten. Betrachten Sie den folgenden Fall, in dem wir einen großen Teil des Speichers zuweisen, ihn wieder freigeben und dann zwei viel kleinere Blöcke zuweisen:

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

Hier haben wir einen freien 128-Byte-Speicherblock, und wenn wir einen Block von nur 8 Bytes zuweisen, sind alle 128 Bytes nicht mehr verfügbar. Wenn wir einen weiteren 8-Byte-Block zuweisen, muss der Heap erneut wachsen. Dies ist keine effiziente Speichernutzung.

Für diesen Fall gibt es mindestens zwei beliebte Lösungen. Eine effizientere Methode ist die Verwendung von bins: Listen, die Blöcke nach Größe gruppieren. Dies ist ein ausgefeilterer und effizienterer Ansatz, aber komplexer. Eine andere, einfachere Möglichkeit besteht darin, einen großen Block zu finden und ihn in kleinere Blöcke aufzuteilen. Wir werden diesen Ansatz verfolgen.

Aber denken Sie daran: einfacher bedeutet nicht unbedingt einfach ;-)

Erstes Refactoring

Bevor wir beginnen, führen wir eine kleine Umgestaltung durch. Derzeit führt die Funktion header_new() zwei Dinge aus: Sie reserviert mehr Speicher für einen neuen Block und initialisiert seinen Header, indem er die Metadaten und Zeiger auf den vorherigen Block setzt. Der Teil der Initialisierung des Headers könnte nützlich sein, also extrahieren wir ihn. Wir werden zwei neue Funktionen erstellen, um die Lesbarkeit zu verbessern:

• Die header_plug()-Funktion, die den initialisierten Block an den vorherigen und nächsten Block „anschließt“.
• Die Funktion header_init(), die die Anfangswerte der Metadaten des Blocks (Größe und Verfügbarkeit) festlegt.

So sehen sie aus:

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

Jetzt müssen wir nur noch header_new() ändern, um diese neuen Funktionen zu verwenden:

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

(Zusätzlich können wir die Zeile last-> previous->next = last; aus der abmalloc()-Funktion entfernen, da header_plug() das jetzt erledigt.)

Blöcke teilen

Mit diesen Tools erstellen wir die Funktion header_split(). Bei gegebenem Header und einer erforderlichen Mindestgröße teilt diese Funktion den Speicherblock in zwei Teile, wenn der ursprüngliche Block groß genug ist, um

aufzunehmen

• die erforderliche Größe,
• ein neuer Header für den neuen Block und
• etwas zusätzlicher Speicher.

Zuerst prüfen wir, ob der Block groß genug ist:

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

Wenn diese Bedingung erfüllt ist, teilen wir den Block. Zuerst reduzieren wir die Größe des aktuellen Blocks, indem wir die Größe eines Headers und den von abmalloc:
angeforderten Speicherplatz subtrahieren

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

Dadurch bleibt nach dem aktuellen Block ein Speicherplatz übrig, den wir zum Erstellen des neuen Blocks verwenden. Wir berechnen den Zeiger für diesen neuen Block:

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

Da wir nun den Zeiger auf den neuen Block haben, initialisieren wir seinen Header mit header_init():

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

Und wir verbinden den neuen Block mit dem vorherigen und nächsten Block mithilfe von header_plug():

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

Wenn der ursprüngliche Block der letzte war, ist der neue Block jetzt der letzte, also aktualisieren wir den letzten Zeiger:

header->size = original_size - size - sizeof(Header);

Zuletzt geben wir den neuen Block zurück:

Header *new_header = header + sizeof(Header) + header->size;

Wenn der Originalblock nicht groß genug ist, geben wir einfach den Originalblock zurück:

header_init(new_header, size, true);

abmalloc() aktualisieren

Jetzt müssen wir nur noch zur Funktion abmalloc() zurückkehren und an der Stelle, an der wir einen verwendbaren Block finden, header_split() aufrufen, um zu versuchen, ihn zu teilen:

header_plug(new_header, header, header->next);

Wenn der Block geteilt werden kann, wird der neue Block zurückgegeben. Andernfalls wird der ursprüngliche Block beibehalten und wie zuvor zurückgegeben.

Hinweis zur Blockaufteilung

Beachten Sie, dass wir den neuen Block am Ende des ursprünglichen Blocks erstellt haben. Wir hätten ihn am Anfang erstellen können, aber durch die Erstellung des neuen verwendeten Blocks am Ende bleibt der neue freie Block näher an den älteren Blöcken. Auf diese Weise wird es beim nächsten Aufruf von abmalloc() zuerst gefunden.

Das Aufteilen großer Speicherblöcke ist ein Fortschritt, aber es gibt ein gegenteiliges Problem: Kleine Speicherblöcke können zu Fragmentierung führen, während größere Anfragen dazu führen, dass der Heap wächst. Wir werden im nächsten Beitrag sehen, wie wir das lösen können.

Das obige ist der detaillierte Inhalt vonImplementierung von malloc() und free() – Aufteilen großer Blöcke. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!