Freilisten und Wiederverwendung
Verwalten und recyceln Sie Speicherblöcke.
Freilisten und Wiederverwendung ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Über den Bump Allocator hinaus
Um einzelne Blöcke freizugeben und wiederzuverwenden, benötigen wir Verwaltungsdaten. Eine Free List ist eine verkettete Liste verfügbarer Blöcke, die der Allocator durchsucht, bevor er neuen Speicher verwendet.
Jeder Block enthält einen Header, damit der Allocator seine Größe ermitteln und ihn mit dem nächsten Block in der Kette verknüpfen kann.
Block-Header mit Verknüpfung
Wir erweitern den Header um einen next-Zeiger und ein free-Flag. Zusammen verwandeln sie unseren Pool in eine navigierbare Liste von Blöcken.
Die Nutzdaten folgen im Speicher unmittelbar auf den Header.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Einen großen freien Block initialisieren
Beim Start ist der gesamte Pool ein einziger großer freier Block. Bei Allokationen teilen wir ihn auf, bei Freigaben markieren wir Blöcke als wiederverwendbar.
Der Kopf der Liste ist dieser ursprüngliche Block, der die gesamte Arena abdeckt.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}First-Fit-Suche
Die einfachste Strategie zur Wiederverwendung ist First-Fit: Durchlaufen Sie die Liste und geben Sie den ersten freien Block zurück, der groß genug ist. Das ist schnell und hält kleine Blöcke meist am Anfang.
Alternativen sind Best-Fit (der kleinste passende Block) und Worst-Fit, wobei Geschwindigkeit gegen das Fragmentierungsverhalten abgewogen wird.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Aus einem freien Block allokieren
Sobald wir einen passenden Block gefunden haben, markieren wir ihn als belegt und geben den Zeiger direkt hinter seinem Header zurück. Vorerst übergeben wir den gesamten Block; das Aufteilen folgt im nächsten Abschnitt.
Der zurückgegebene Zeiger ist block + 1, sodass der Header für den Aufrufer verborgen bleibt.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Einen Block freigeben
Um einen Block freizugeben, gehen Sie vom Benutzerzeiger zurück zu seinem Header und ändern Sie das Free-Flag. Der Block kann nun bei der nächsten Suche wiederverwendet werden.
Den Header aus den Nutzdaten zurückzugewinnen ist derselbe einfache Zeigertrick, den wir zuvor gesehen haben.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Benachbarte freie Blöcke zusammenführen
Allein durch Freigaben bleibt der Pool voller kleiner freier Blöcke. Coalescing führt einen freigegebenen Block mit dem nächsten Block zusammen, wenn auch dieser frei ist, und stellt so größere zusammenhängende Bereiche wieder her.
Dadurch wird externe Fragmentierung bekämpft, sodass auch zukünftige große Anforderungen erfüllt werden können.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Ein ausführbares Free-List-Beispiel
Dieses vollständige Programm initialisiert einen Pool, allokiert zwei Blöcke, gibt den ersten frei und verwendet ihn anschließend für eine kleinere Anforderung wieder. Damit zeigt es, dass die Free List funktioniert.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}Die Kosten der Suche
Eine einfach verkettete Free List bedeutet, dass eine Allokation in der Anzahl der Blöcke O(n) benötigt. Bei vielen Allokationen wird das langsam.
Echte Allocators verwenden nach Größen getrennte Free Lists (Bins) oder Bäume, um die Suche näher an O(1) zu bringen. Das Prinzip der Wiederverwendung bleibt dasselbe.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Doppelte Freigabe und Beschädigung
Wenn ein Block zweimal als frei markiert wird oder über seine Größe hinaus geschrieben wird, werden benachbarte Header beschädigt. Bei der nächsten Suche folgt der Allocator dann einem ungültigen next-Zeiger und stürzt ab.
Deshalb sind Speicherfehler in C so gefährlich: Die Metadaten des Allocators liegen direkt neben Ihren Daten.
Wiederverwendung zusammenführen
Ein funktionierender Free-List-Allocator benötigt Initialisierung, eine Fit-Strategie, Allokation, Freigabe und Coalescing. Damit wird der Speicher im Pool wiederholt verwendet, anstatt dass der Pool ständig wächst.
Die verbleibende Verfeinerung besteht darin, übergroße Blöcke aufzuteilen und die Ausrichtung einzuhalten. Das ist das Thema des letzten Abschnitts.
Kurze Überprüfung
Überlegen Sie, wodurch eine Free List vor starker Fragmentierung geschützt wird.
Zusammenfassung
Eine Free List verknüpft Blöcke über Header, sodass einzelne Allokationen freigegeben und wiederverwendet werden können. Die First-Fit-Suche findet einen Block, bei der Freigabe wird ein Flag geändert, und Coalescing führt benachbarte Blöcke zusammen, um Fragmentierung zu bekämpfen.
Eine lineare Suche benötigt O(n); Produktions-Allocator ordnen Blöcke zur Beschleunigung nach Größen in Bins ein. Als Nächstes fügen wir Aufteilung und Ausrichtung hinzu.
Lerne C mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 39
- Lektionen
- 144
Häufig gestellte Fragen
Ist die Lektion „Freilisten und Wiederverwendung“ kostenlos?
Ja — der vollständige Text von „Freilisten und Wiederverwendung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Freilisten und Wiederverwendung“?
Verwalten und recyceln Sie Speicherblöcke. Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C Academy zu starten?
Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Freilisten und Wiederverwendung“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?
Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Wie malloc funktioniert
- Ein einfacher Bump-Allocator
- Freilisten und Wiederverwendung
- Ausrichtung und Aufteilung