Listy wolnych bloków i ponowne użycie
Będzie Pan/Pani śledzić i ponownie wykorzystywać bloki.
Listy wolnych bloków i ponowne użycie to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 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.
Co dalej po alokatorze bump
Aby zwalniać pojedyncze bloki i ponownie je wykorzystywać, potrzebujemy metadanych. Lista wolnych bloków to lista jednokierunkowa dostępnych bloków, którą alokator przeszukuje przed pobraniem nowej pamięci.
Każdy blok zawiera nagłówek, dzięki któremu alokator może odczytać jego rozmiar i odwołanie do następnego bloku w łańcuchu.
Nagłówek bloku z odwołaniem
Rozszerzamy nagłówek o wskaźnik next i flagę free. Razem zmieniają one naszą pulę w listę bloków, po której można się poruszać.
Dane użytkownika znajdują się w pamięci bezpośrednio za nagłówkiem.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Inicjalizacja jednego dużego wolnego bloku
Po uruchomieniu cała pula jest jednym ogromnym wolnym blokiem. Podczas alokacji dzielimy go, a podczas zwalniania oznaczamy bloki jako możliwe do ponownego użycia.
Głową listy jest ten początkowy blok obejmujący całą arenę.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}Wyszukiwanie first-fit
Najprostsza strategia ponownego użycia to first-fit: przechodzimy listę i zwracamy pierwszy wolny blok o wystarczającym rozmiarze. Jest szybka i zwykle utrzymuje małe bloki blisko początku listy.
Alternatywy to best-fit (najmniejszy wystarczający blok) i worst-fit, które wymieniają szybkość na inne zachowanie związane z fragmentacją.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Alokowanie z wolnego bloku
Po znalezieniu odpowiedniego bloku oznaczamy go jako używany i zwracamy wskaźnik znajdujący się bezpośrednio za jego nagłówkiem. Na razie przekazujemy cały blok; dzielenie omówimy w następnej lekcji.
Zwracany wskaźnik to block + 1, dzięki czemu nagłówek jest ukryty przed wywołującym.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Zwalnianie bloku
Aby zwolnić blok, cofamy się od wskaźnika użytkownika do jego nagłówka i zmieniamy flagę free. Blok może teraz zostać ponownie użyty podczas następnego wyszukiwania.
Odzyskanie nagłówka z danych użytkownika wykorzystuje tę samą prostą sztuczkę ze wskaźnikiem, którą poznaliśmy wcześniej.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Scalanie sąsiednich wolnych bloków
Samo zwalnianie pozostawia pulę pełną małych wolnych bloków. Scalanie łączy zwolniony blok z następnym, jeśli on również jest wolny, odbudowując większe ciągłe obszary.
Przeciwdziała to fragmentacji zewnętrznej, dzięki czemu można nadal obsługiwać przyszłe duże żądania.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Uruchamialny przykład listy wolnych bloków
Ten kompletny program inicjalizuje pulę, przydziela dwa bloki, zwalnia pierwszy, a następnie ponownie wykorzystuje go dla mniejszego żądania, pokazując, że lista wolnych bloków działa.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}Koszt wyszukiwania
Pojedyncza lista jednokierunkowa wolnych bloków oznacza, że alokacja ma złożoność O(n) względem liczby bloków. Przy wielu alokacjach staje się to powolne.
Rzeczywiste alokatory używają rozdzielonych list wolnych bloków (koszyków według rozmiaru) albo drzew, aby wyszukiwanie miało złożoność bliską O(1). Zasada ponownego użycia pozostaje taka sama.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Podwójne zwolnienie i uszkodzenie pamięci
Dwukrotne oznaczenie bloku jako wolnego albo zapis poza jego rozmiarem uszkadza sąsiednie nagłówki. Podczas następnego wyszukiwania program podąża wtedy za błędnym wskaźnikiem next i ulega awarii.
Dlatego błędy pamięci w języku C są tak niebezpieczne: metadane samego alokatora znajdują się bezpośrednio obok danych użytkownika.
Połączenie elementów ponownego użycia
Działający alokator z listą wolnych bloków potrzebuje inicjalizacji, strategii wyboru bloku, operacji allocate i free oraz scalania. Dzięki temu pamięć krąży w puli zamiast rosnąć bez końca.
Pozostałe udoskonalenia to dzielenie zbyt dużych bloków i zachowanie wyrównania — tym zajmiemy się w ostatniej lekcji.
Szybkie sprawdzenie
Zastanów się, co zapobiega nadmiernej fragmentacji listy wolnych bloków.
Podsumowanie
Lista wolnych bloków łączy bloki za pomocą nagłówków, dzięki czemu pojedyncze alokacje można zwalniać i ponownie wykorzystywać. Wyszukiwanie first-fit znajduje blok, zwalnianie zmienia flagę, a scalanie sąsiadów przeciwdziała fragmentacji.
Wyszukiwanie liniowe ma złożoność O(n); produkcyjne alokatory grupują bloki według rozmiaru, aby przyspieszyć działanie. Następnie dodamy dzielenie i wyrównanie.
Ucz się C dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 39
- Lekcje
- 144
Często zadawane pytania
Czy lekcja „Listy wolnych bloków i ponowne użycie” jest bezpłatna?
Tak — pełny tekst „Listy wolnych bloków i ponowne użycie” 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 „Listy wolnych bloków i ponowne użycie”?
Będzie Pan/Pani śledzić i ponownie wykorzystywać 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 3 z 4.
Ile czasu zajmuje lekcja „Listy wolnych bloków i ponowne użycie”?
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
- Jak działa malloc
- Prosty alokator bump
- Listy wolnych bloków i ponowne użycie
- Wyrównanie i dzielenie