Justering och uppdelning
Gör block användbara och välordnade.
Justering och uppdelning är en gratis lektion i C Academy på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för C Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C Academy innehåller totalt 4 lektioner.
Varför justering är viktig
Varje typ har ett justeringskrav: dess adress måste vara en multipel av en tvåpotens. En double behöver vanligtvis 8 bytes justering.
Eftersom malloc inte vet vad ni kommer att lagra måste den returnera pekare som är justerade för den typ som har strängast krav, vanligtvis 16 byte på 64-bitarsystem.
#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t); /* often 16 */Tricket med align_up
Att avrunda en storlek uppåt till nästa multipel av en justering som är en tvåpotens är ett klassiskt bittrick: lägg till a - 1 och maskera sedan bort de lägsta bitarna.
Det fungerar bara när a är en tvåpotens, vilket alla verkliga justeringar är.
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 */Verifiera att matematiken fungerar
Låt oss verifiera align_up med ett körbart program. Det avrundar flera storlekar uppåt till 8- och 16-bytesgränser och skriver ut resultaten.
#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;
}Justera begärda storlekar
Inuti allokeraren är det första steget för varje begäran att avrunda den begärda storleken uppåt till justeringen. Det garanterar att även nästa block börjar på en justerad adress.
Utfyllnadsbytena är intern fragmentering – priset för universell 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 att återanvända hela block
I den föregående lektionen returnerade vi ett helt ledigt block även för små begäranden. Ett ledigt block på 4000 byte som lämnas över för en begäran på 16 byte slösar bort resten.
Uppdelning delar blocket i den del vi använder och en rest som förblir ledig.
Dela upp ett block
Om ett valt block är mycket större än vad som behövs placerar vi ett nytt huvud i slutet av det begärda området. Det som blir över blir ett mindre ledigt block i listan.
Vi delar bara upp blocket när resten är tillräckligt stor för att rymma ett huvud plus viss nyttolast; annars är fragmentet oanvändbart.
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;
}Allokera, justera, dela upp
Den fullständiga allokeringsvägen justerar nu storleken, hittar ett passande block, delar av en tillräckligt stor rest och markerar blocket som använt.
Det håller blocken tätt dimensionerade och lämnar användbart ledigt utrymme efter sig.
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);
}Hålla själva poolen justerad
För att allt ska vara korrekt bör även poolens startadress och huvudets storlek följa justeringen, så att varje nyttolast hamnar på en gräns.
Genom att använda alignas på den statiska bufferten garanteras att hela konstruktionen börjar justerad.
#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */En körbar justerad allokering
Det här programmet allokerar från en justerad pool och skriver ut den returnerade adressen modulo 16. Resultatet är alltid noll, vilket visar att adressen är korrekt justerad.
#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;
}Uppdelning kontra sammanfogning
Uppdelning och sammanfogning är motsatser som balanserar varandra. Allokering delar upp stora block, medan frigöring slår ihop små block igen.
Tillsammans gör de att samma pool kan hantera en varierande blandning av begärda storlekar utan att utrymme läcker bort eller fragmenteras permanent.
Från leksaksallokerare till riktig allokerare
Ni har nu alla fyra grundpelare: en minneskälla, justerade huvuden, återanvändning via free list med sammanfogning samt uppdelning. Riktiga allokerare lägger till storleksklassade fack, trådcache och integration med operativsystemet för bättre hastighet och skalbarhet.
Men kärnidéerna ni har byggt här ligger till grund för alla implementationer av malloc.
Snabb kontroll
Fundera på varför block delas upp under allokeringen.
Sammanfattning
Justering avrundar storlekar uppåt med bittricket (n + a - 1) & ~(a - 1), så att varje nyttolast passar för alla typer. Uppdelning delar för stora lediga block i en använd del och en ledig rest, medan sammanfogning gör det omvända vid frigöring.
Dessa fyra grundpelare bildar tillsammans en komplett och korrekt minnesallokerare.
Lär dig C med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 39
- Lektioner
- 144
Vanliga frågor
Är lektionen ”Justering och uppdelning” gratis?
Ja – hela texten till ”Justering och uppdelning” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i C Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i C Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Justering och uppdelning”?
Gör block användbara och välordnade. Ni övar på C Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig C Academy?
Du behöver inga förkunskaper. Utbildningen i C Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Justering och uppdelning”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här C Academy-lektionen?
Ja. Varje C Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Så fungerar malloc
- En enkel bump-allokerare
- Lediga listor och återanvändning
- Justering och uppdelning