Alignment og opsplitning
Gør blokke anvendelige og ryddelige.
Alignment og opsplitning er en gratis C Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.
Hvorfor justering er vigtig
Alle typer har et justeringskrav: Deres adresse skal være et multiplum af en potens af to. En double kræver typisk justering til 8 byte.
Fordi malloc ikke ved, hvad du vil gemme, skal den returnere pointere, der er justeret til den strengeste type, normalt 16 byte på 64-bit-systemer.
#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t); /* often 16 */Tricket med align_up
At runde en størrelse op til det næste multiplum af en justering, der er en potens af to, er et klassisk bit-trick: Læg a - 1 til, og maskér derefter de lave bit væk.
Det virker kun, når a er en potens af to, hvilket alle reelle justeringer er.
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 */Verificering af matematikken
Lad os verificere align_up med et kørbart program. Det runder flere størrelser op til grænser på 8 og 16 byte og udskriver resultaterne.
#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;
}Justering af anmodede størrelser
Inde i allokatoren er det første trin ved enhver anmodning at runde den anmodede størrelse op til justeringen. Det garanterer, at den næste blok også starter korrekt justeret.
Udfyldningsbytterne er intern fragmentering, som er prisen for universel justering.
#define ALIGN 16
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
/* now find a block of this aligned size */
/* ... */
return NULL;
}Problemet med genbrug af hele blokke
I den forrige lektion returnerede vi en hel fri blok, selv ved meget små anmodninger. En fri blok på 4000 byte, der udleveres til en anmodning på 16 byte, spilder resten.
Opdeling skærer blokken i den del, vi bruger, og en rest, der forbliver fri.
Opdeling af en blok
Hvis en valgt blok er meget større end nødvendigt, placerer vi en ny header i slutningen af det anmodede område. Resten bliver til en mindre fri blok i listen.
Vi opdeler kun, når resten er stor nok til at indeholde en header og nogle nyttedata; ellers er fragmentet ubrugeligt.
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;
}Allokér, juster, opdel
Den fulde allokeringssti justerer nu størrelsen, finder en passende blok, opdeler en eventuel stor rest og markerer blokken som brugt.
Det holder blokkene tæt på den nødvendige størrelse og efterlader brugbar fri plads.
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);
}Hold selve puljen justeret
For at sikre korrekthed bør puljens startadresse og headerens størrelse også overholde justeringen, så alle nyttedata lander på en grænse.
Ved at bruge alignas på den statiske buffer garanterer vi, at hele konstruktionen starter korrekt justeret.
#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */En kørbar justeret allokering
Dette program allokerer fra en justeret pulje og udskriver den returnerede adresse modulo 16, hvilket viser, at resultatet altid er nul, altså korrekt justeret.
#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;
}Opdeling kontra sammenlægning
Opdeling og sammenlægning er modsætninger, der afbalancerer hinanden. Allokering opdeler store blokke; frigivelse samler små blokke igen.
Tilsammen gør de det muligt for den samme pulje at håndtere en skiftende blanding af anmodningsstørrelser uden at lække plads eller blive permanent fragmenteret.
Fra legetøjsallokator til rigtig allokator
Du har nu alle fire grundpiller: en hukommelseskilde, justerede headere, genbrug via free-list med sammenlægning og opdeling. Rigtige allokatorer tilføjer bøtter efter størrelsesklasse, trådcaches og integration med operativsystemet for at opnå hastighed og skalerbarhed.
Men de grundlæggende idéer, du har bygget her, driver enhver malloc-implementering.
Hurtigt tjek
Overvej, hvorfor blokke opdeles under allokering.
Opsummering
Justering runder størrelser op med bit-tricket (n + a - 1) & ~(a - 1), så alle nyttedata passer til enhver type. Opdeling udskærer for store frie blokke i en brugt del og en fri rest, mens sammenlægning vender processen om ved frigivelse.
Tilsammen udgør disse fire grundpiller en komplet og korrekt hukommelsesallokator.
Lær C med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 39
- Lektioner
- 144
Ofte stillede spørgsmål
Er lektionen “Alignment og opsplitning” gratis?
Ja — hele teksten til “Alignment og opsplitning” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Alignment og opsplitning”?
Gør blokke anvendelige og ryddelige. Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på C Academy?
Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Alignment og opsplitning”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne C Academy-lektion?
Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Sådan fungerer malloc
- En simpel bump-allokator
- Free lists og genbrug
- Alignment og opsplitning