C Academy · leksjon

Justering og oppdeling

Gjør blokker brukbare og ryddige.

Leksjon 4 av 413 trinn

Justering og oppdeling er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.

Hvorfor justering er viktig

Hver type har et justeringskrav: adressen må være et multiplum av en potens av to. En double trenger vanligvis 8-bytes justering.

Fordi malloc ikke vet hva De skal lagre, må den returnere pekere som er justert for den strengeste typen, vanligvis 16 byte på 64-biters systemer.

#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t);   /* often 16 */

align_up-trikset

Å runde en størrelse opp til neste multiplum av en justering som er en potens av to, er et klassisk bittriks: legg til a - 1, og masker deretter bort de laveste bitene.

Dette fungerer bare når a er en potens av to, noe 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 */

Å kontrollere at matematikken fungerer

La oss kontrollere align_up med et kjørbart program. Det runder flere størrelser opp til grenser på 8 og 16 byte og skriver ut resultatene.

#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 av forespurte størrelser

Inne i allokatoren er det første trinnet i hver forespørsel å runde den forespurte størrelsen opp til justeringen. Dette garanterer at den neste blokken også starter riktig justert.

Utfyllingsbytene er intern fragmentering – prisen for 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 gjenbruk av hele blokker

I forrige leksjon returnerte vi en hel ledig blokk, selv for små forespørsler. En ledig blokk på 4000 byte som gis ut til en forespørsel på 16 byte, sløser bort resten.

Oppdeling deler blokken i den delen vi bruker, og en rest som forblir ledig.

Oppdeling av en blokk

Hvis en valgt blokk er mye større enn nødvendig, plasserer vi en ny header på slutten av det forespurte området. Resten blir en mindre ledig blokk i listen.

Vi deler bare opp når resten er stor nok til å inneholde en header og noe nyttelast; ellers er fragmentet ubrukelig.

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;
}

Alloker, juster, del opp

Den fullstendige allokeringsbanen justerer nå størrelsen, finner en passende blokk, deler av en eventuell stor rest og markerer blokken som brukt.

Dette holder blokkene tett tilpasset størrelsen og etterlater brukbar ledig plass.

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);
}

Å holde selve poolen riktig justert

For at dette skal være korrekt, bør også poolens startadresse og headerstørrelsen respektere justeringen, slik at hver nyttelast havner på en grense.

Ved å bruke alignas på den statiske bufferen garanterer vi at hele opplegget starter riktig justert.

#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */

En kjørbar justert allokering

Dette programmet allokerer fra en justert pool og skriver ut den returnerte adressen modulo 16. Det viser at resultatet alltid er null, altså at adressen er riktig justert.

#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;
}

Oppdeling kontra sammenslåing

Oppdeling og sammenslåing er motsetninger som balanserer hverandre. Allokering deler store blokker opp; frigjøring slår små blokker sammen igjen.

Sammen gjør de at den samme poolen kan håndtere en skiftende blanding av forespurte størrelser uten å lekke plass eller bli permanent fragmentert.

Fra lekeallokator til ekte allokator

De har nå alle de fire grunnpilarene: en minnekilde, justerte headere, gjenbruk via friliste med sammenslåing og oppdeling. Ekte allokatorer legger til bøtter for størrelsesklasser, trådcacher og integrasjon med operativsystemet for hastighet og skalerbarhet.

Men kjerneideene De har bygget her, driver enhver malloc-implementasjon.

Rask kontroll

Vurder hvorfor blokker deles opp under allokering.

Besvar den i den interaktive leksjonen

Oppsummering

Justering runder størrelser opp med bittrikset (n + a - 1) & ~(a - 1), slik at enhver nyttelast passer for alle typer. Oppdeling deler overdimensjonerte ledige blokker i en brukt del og en ledig rest, mens sammenslåing gjør det motsatte ved frigjøring.

Disse fire grunnpilarene utgjør til sammen en komplett og korrekt minneallokator.

Gratis å komme i gang

Lær deg C med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 39
Leksjoner: 144

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Justering og oppdeling» gratis?

Ja – hele teksten i «Justering og oppdeling» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Justering og oppdeling»?

Gjør blokker brukbare og ryddige. Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med C Academy?

Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Justering og oppdeling»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?

Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til C Academy