Heap Allocator
1.0.0
Schreiben eines Speicherallocators
Snippet für einen Speicher Allocator in C.
Speicherallocators 101 - Schreiben Sie einen einfachen Speicher Allocator
void * malloc ( size_t size );
void free ( void * ptr );
Block * merge_blocks ( Block * block );
// the above three will be implemented first later calloc and realloc Definieren Sie die Datenstruktur : Sie benötigen eine Datenstruktur, um die Größe und den Zuordnungsstatus jedes Blocks zu verfolgen. Dies kann eine einfache Struktur mit Größe und einem Flag sein, das angibt, ob der Block frei ist oder nicht.
Initialisieren Sie den Heap : Wenn Ihr Programm startet, müssen Sie einen Speicherback beiseite legen, um als Haufen zu fungieren. Dies kann mit dem mmap() -Systemanruf erfolgen.
malloc() implementieren: Diese Funktion sollte einen freien Block finden, der groß genug ist, um die Anfrage zu erfüllen. Wenn kein solcher Block existiert, sollte er die Größe des Haufens erhöhen. Sobald ein geeigneter Block gefunden wurde, sollte er als zugewiesene und seine Adresse zurückgegeben werden.
Implementieren Sie free() : Diese Funktion sollte einen Zeiger zu einem Speicherblock bringen, ihn als frei markieren und möglicherweise die Größe des Haufens reduzieren, wenn sich der befreite Block am Ende befindet.
Implementieren Sie realloc() : Diese Funktion sollte die Größe eines zugewiesenen Blocks ändern. Dies könnte dazu beinhalten, einen neuen Block zu finden und die alten Daten zu kopieren.
Handlungsfragmentierung : Im Laufe der Zeit kann der Haufen mit freien Blöcken fragmentiert werden, die überall verstreut sind. Möglicherweise möchten Sie eine Strategie zur Defragmentierung des Haufens umsetzen, z.
Im Kontext eines Heap -Allocators beziehen sich "Blöcke" auf Speicherbrocken im Haufen. Hier ist, warum Sie sie brauchen und wie sie funktionieren:
Warum Blöcke? : Wenn Sie Speicher verwalten, ist es hilfreich, ihn in überschaubare Stücke oder "Blöcke" zu teilen. Jeder Block kann unabhängig zugewiesen und verhandelt werden. Dies ermöglicht den effizienten Einsatz des Speichers, da Sie genau so viel Speicher wie Sie benötigen können, nicht mehr und nicht weniger.
Blockstruktur : Jeder Block enthält typischerweise Metadaten um den Block (z. B. seine Größe und ob er frei oder zugewiesen ist) und die tatsächlichen Daten, die im Block gespeichert sind. Die Metadaten werden vom Allocator verwendet, um den Speicher zu verwalten.
Zuordnung : Wenn Sie malloc() anrufen, sucht der Allocator nach einem kostenlosen Block, der groß genug ist, um die angeforderte Datenmenge zu halten. Wenn es einen findet, markiert es diesen Block als zugewiesene Block und gibt einen Zeiger auf den Datenabschnitt des Blocks zurück.
OVALLOCATION : Wenn Sie free() anrufen, markiert der Allocator den Block als kostenlos und stellt ihn für zukünftige Zuteilungen zur Verfügung. Wenn sich der befreite Block am Ende des Haufens befindet, kann der Allocator auch die Größe des Haufens reduzieren, um den Speicher zu befreien.
Fragmentierung : Im Laufe der Zeit kann der Haufen fragmentiert werden, da Blöcke zugewiesen und verhandelt werden. Dies bedeutet, dass der freie Speicher in kleine, nicht zusammenhängende Blöcke unterteilt ist. Dies kann es schwierig machen, einen ausreichend großen Block für einen malloc() -Anruf zu finden, auch wenn genügend kostenloses Speicher vorhanden ist. Um dies zu bewältigen, beinhalten Allokatoren häufig Logik, um den Haufen zu entfalten, z.
