Ausrichtung und Aufteilung
Machen Sie Blöcke nutzbar und ordentlich.
Ausrichtung und Aufteilung ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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.
Warum Ausrichtung wichtig ist
Jeder Typ hat eine Ausrichtungsanforderung: Seine Adresse muss ein Vielfaches einer bestimmten Zweierpotenz sein. Ein double benötigt typischerweise eine 8-Byte-Ausrichtung.
Da malloc nicht weiß, was Sie speichern werden, muss es Zeiger zurückgeben, die für den strengsten Typ ausgerichtet sind, auf 64-Bit-Systemen normalerweise auf 16 Bytes.
#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t); /* often 16 */Der align_up-Trick
Eine Größe auf das nächste Vielfache einer Ausrichtung als Zweierpotenz aufzurunden, ist ein klassischer Bit-Trick: Addieren Sie a - 1 und maskieren Sie anschließend die niederwertigen Bits aus.
Das funktioniert nur, wenn a eine Zweierpotenz ist, was bei allen echten Ausrichtungen der Fall ist.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1);
}
/* align_up(13, 8) == 16, align_up(16, 8) == 16 */Die Berechnung praktisch überprüfen
Überprüfen wir align_up mit einem ausführbaren Programm. Es rundet mehrere Größen auf 8- und 16-Byte-Grenzen auf und gibt die Ergebnisse aus.
#include <stdio.h>
#include <stddef.h>
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1);
}
int main(void) {
printf("%zu\n", align_up(13, 8)); /* 16 */
printf("%zu\n", align_up(16, 8)); /* 16 */
printf("%zu\n", align_up(1, 16)); /* 16 */
printf("%zu\n", align_up(33, 16)); /* 48 */
return 0;
}Angeforderte Größen ausrichten
Im Allocator besteht der erste Schritt jeder Anforderung darin, die angeforderte Größe auf die Ausrichtung aufzurunden. Dadurch beginnt auch der nächste Block korrekt ausgerichtet.
Die Padding-Bytes sind interne Fragmentierung und somit der Preis für eine universelle Ausrichtung.
#define ALIGN 16
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
/* now find a block of this aligned size */
/* ... */
return NULL;
}Das Problem bei der Wiederverwendung ganzer Blöcke
Im vorherigen Abschnitt haben wir selbst bei kleinen Anforderungen einen gesamten freien Block zurückgegeben. Ein freier Block von 4000 Bytes, der für eine Anforderung von 16 Bytes ausgegeben wird, verschwendet den restlichen Speicher.
Durch Aufteilen wird der Block in den verwendeten Teil und einen Rest geteilt, der frei bleibt.
Einen Block aufteilen
Wenn ein ausgewählter Block wesentlich größer als nötig ist, platzieren wir am Ende des angeforderten Bereichs einen neuen Header. Der Rest wird zu einem kleineren freien Block in der Liste.
Wir teilen nur dann auf, wenn der Rest groß genug für einen Header und einige Nutzdaten ist. Andernfalls wäre das Fragment nutzlos.
void split(block_t *b, size_t size) {
size_t rem = b->size - size;
if (rem < sizeof(block_t) + ALIGN) return; /* too small */
block_t *nb = (block_t *)((char *)(b + 1) + size);
nb->size = rem - sizeof(block_t);
nb->free = 1;
nb->next = b->next;
b->size = size;
b->next = nb;
}Allokieren, ausrichten, aufteilen
Der vollständige Allokationspfad richtet nun die Größe aus, findet einen passenden Block, teilt einen ausreichend großen Rest ab und markiert den Block als belegt.
Dadurch bleiben die Blöcke passend dimensioniert und nutzbarer freier Speicher bleibt erhalten.
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
block_t *b = first_fit(size);
if (!b) return NULL;
split(b, size);
b->free = 0;
return (void *)(b + 1);
}Den Pool selbst ausrichten
Für die Korrektheit sollten auch die Startadresse des Pools und die Header-Größe die Ausrichtung einhalten, damit jede Nutzlast auf einer Grenze liegt.
Die Verwendung von alignas beim statischen Puffer garantiert, dass das gesamte Verfahren ausgerichtet beginnt.
#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */Eine ausführbare ausgerichtete Allokation
Dieses Programm allokiert aus einem ausgerichteten Pool und gibt die zurückgegebene Adresse modulo 16 aus. Das Ergebnis ist immer null, die Adresse ist also korrekt ausgerichtet.
#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>
static size_t align_up(size_t n, size_t a){ return (n+a-1)&~(a-1); }
alignas(16) static unsigned char pool[1024];
static size_t off = 0;
void *alloc16(size_t s){ off=align_up(off,16); if(off+s>sizeof(pool)) return NULL; void*p=&pool[off]; off+=s; return p; }
int main(void){
void *a = alloc16(1);
void *b = alloc16(20);
printf("a %% 16 = %lu\n", (unsigned long)((size_t)a % 16));
printf("b %% 16 = %lu\n", (unsigned long)((size_t)b % 16));
return 0;
}Aufteilen und Zusammenführen
Aufteilen und Zusammenführen sind entgegengesetzte Vorgänge, die sich ausgleichen. Bei der Allokation werden große Blöcke aufgeteilt, bei der Freigabe werden kleine Blöcke wieder zusammengeführt.
Zusammen ermöglichen sie es demselben Pool, wechselnde Anforderungsgrößen zu bedienen, ohne Speicher zu verlieren oder dauerhaft zu fragmentieren.
Vom Spielzeug- zum echten Allocator
Sie verfügen nun über alle vier Grundpfeiler: eine Speicherquelle, ausgerichtete Header, die Wiederverwendung über eine Free List mit Coalescing und das Aufteilen von Blöcken. Echte Allocators ergänzen Größenklassen-Bins, Thread-Caches und die Integration in das Betriebssystem, um Geschwindigkeit und Skalierbarkeit zu verbessern.
Die hier entwickelten Grundideen bilden jedoch die Basis jeder malloc-Implementierung.
Kurze Überprüfung
Überlegen Sie, warum Blöcke bei der Allokation aufgeteilt werden.
Zusammenfassung
Die Ausrichtung rundet Größen mit dem Bit-Trick (n + a - 1) & ~(a - 1) auf, sodass jede Nutzlast für jeden Typ geeignet ist. Durch Aufteilen werden übergroße freie Blöcke in einen belegten Teil und einen freien Rest zerlegt, während Coalescing dies bei der Freigabe rückgängig macht.
Diese vier Grundpfeiler bilden zusammen einen vollständigen und korrekten Memory Allocator.
Häufig gestellte Fragen
Ist die Lektion „Ausrichtung und Aufteilung“ kostenlos?
Ja — der vollständige Text von „Ausrichtung und Aufteilung“ 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 „Ausrichtung und Aufteilung“?
Machen Sie Blöcke nutzbar und ordentlich. 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 4 von 4.
Wie lange dauert die Lektion „Ausrichtung und Aufteilung“?
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