C Academy · Lekcja

Wyrównanie i dzielenie

Przygotuje Pan/Pani użyteczne i uporządkowane bloki.

Wyrównanie i dzielenie to bezpłatna lekcja C Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Dlaczego wyrównanie ma znaczenie

Każdy typ ma wymaganie dotyczące wyrównania: jego adres musi być wielokrotnością pewnej potęgi dwójki. Typ double zazwyczaj wymaga wyrównania do 8 bajtów.

Ponieważ malloc nie wie, co zostanie zapisane w pamięci, musi zwracać wskaźniki wyrównane dla najbardziej wymagającego typu — zwykle do 16 bajtów w systemach 64-bitowych.

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

Sztuczka align_up

Zaokrąglanie rozmiaru w górę do następnej wielokrotności wyrównania będącego potęgą dwójki to klasyczna sztuczka bitowa: dodaj a - 1, a następnie wyzeruj niższe bity za pomocą maski.

Działa to tylko wtedy, gdy a jest potęgą dwójki, a tak jest w przypadku wszystkich rzeczywistych wyrównań.

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 */

Sprawdzenie działania obliczeń

Sprawdźmy działanie align_up za pomocą uruchamialnego programu. Zaokrągla on kilka rozmiarów w górę do granic 8 i 16 bajtów, a następnie wyświetla wyniki.

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

Wyrównywanie żądanych rozmiarów

W alokatorze pierwszym krokiem przy każdym żądaniu jest zaokrąglenie żądanego rozmiaru w górę do granicy wyrównania. Gwarantuje to, że następny blok również rozpocznie się prawidłowo wyrównany.

Bajty dopełnienia stanowią fragmentację wewnętrzną — cenę uniwersalnego wyrównania.

#define ALIGN 16
void *my_alloc(size_t size) {
    size = align_up(size, ALIGN);
    /* now find a block of this aligned size */
    /* ... */
    return NULL;
}

Problem z ponownym użyciem całego bloku

W poprzedniej lekcji zwracaliśmy cały wolny blok nawet dla bardzo małych żądań. Wolny blok o rozmiarze 4000 bajtów przekazany dla żądania 16 bajtów marnuje całą pozostałą przestrzeń.

Dzielenie rozkłada blok na używaną część i pozostałość, która pozostaje wolna.

Dzielenie bloku

Jeśli wybrany blok jest znacznie większy od potrzebnego, umieszczamy nowy nagłówek na końcu żądanego obszaru. Pozostała część staje się mniejszym wolnym blokiem na liście.

Dzielimy blok tylko wtedy, gdy pozostałość jest wystarczająco duża, aby pomieścić nagłówek i pewną ilość danych; w przeciwnym razie fragment byłby bezużyteczny.

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

Alokowanie, wyrównywanie i dzielenie

Pełna ścieżka alokacji wyrównuje teraz rozmiar, znajduje odpowiedni blok, wydziela każdą dużą pozostałość i oznacza blok jako używany.

Dzięki temu bloki są ściśle dopasowane do rozmiaru, a za nimi pozostaje użyteczne wolne miejsce.

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

Zachowanie wyrównania samej puli

Aby zachować poprawność, adres początkowy puli i rozmiar nagłówka również powinny uwzględniać wyrównanie, tak aby każdy obszar danych użytkownika znajdował się na właściwej granicy.

Użycie alignas dla bufora statycznego gwarantuje, że cały schemat rozpoczyna się z prawidłowym wyrównaniem.

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

Uruchamialna wyrównana alokacja

Ten program przydziela pamięć z wyrównanej puli i wyświetla adres zwróconego obszaru modulo 16, pokazując, że wynik zawsze wynosi zero, czyli adres jest prawidłowo wyrównany.

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

Dzielenie a scalanie

Dzielenie i scalanie to przeciwstawne operacje, które wzajemnie się równoważą. Alokacja dzieli duże bloki na mniejsze, a zwalnianie scala małe bloki w większe.

Razem pozwalają tej samej puli obsługiwać zmienny zestaw żądań o różnych rozmiarach bez wycieku miejsca i trwałej fragmentacji.

Od przykładu do rzeczywistego alokatora

Masz już wszystkie cztery filary: źródło pamięci, wyrównane nagłówki, ponowne użycie listy wolnych bloków ze scalaniem oraz dzielenie. Rzeczywiste alokatory dodają koszyki klas rozmiarów, pamięci podręczne wątków i integrację z systemem operacyjnym, aby zwiększyć szybkość i skalowalność.

Jednak podstawowe idee zbudowane tutaj napędzają każdą implementację malloc.

Szybkie sprawdzenie

Zastanów się, dlaczego bloki są dzielone podczas alokacji.

Podsumowanie

Wyrównanie zaokrągla rozmiary w górę za pomocą sztuczki bitowej (n + a - 1) & ~(a - 1), dzięki czemu każdy obszar danych użytkownika pasuje do dowolnego typu. Dzielenie rozdziela zbyt duże wolne bloki na używaną część i wolną pozostałość, a scalanie odwraca ten proces podczas zwalniania.

Te cztery filary tworzą razem kompletny i poprawny alokator pamięci.

Często zadawane pytania

Czy lekcja „Wyrównanie i dzielenie” jest bezpłatna?

Tak — pełny tekst „Wyrównanie i dzielenie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Wyrównanie i dzielenie”?

Przygotuje Pan/Pani użyteczne i uporządkowane bloki. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Wyrównanie i dzielenie”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C Academy