Vapaat listat ja uudelleenkäyttö
Seuratkaa ja kierrättäkää lohkoja.
Vapaat listat ja uudelleenkäyttö on ilmainen C Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu C Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C Academy-kurssilla on yhteensä 4 oppituntia.
Bump-varaajan jälkeen
Yksittäisten lohkojen vapauttaminen ja uudelleenkäyttö edellyttävät kirjanpitoa. Vapaiden lohkojen lista on käytettävissä olevien lohkojen linkitetty lista, jonka varaaja käy läpi ennen uuden muistin ottamista.
Jokainen lohko sisältää otsakkeen, josta varaaja löytää lohkon koon ja linkin ketjun seuraavaan lohkoon.
Linkin sisältävä lohkon otsake
Laajennamme otsaketta next-osoittimella ja free-lipulla. Yhdessä ne muuttavat poolimme lohkojen läpikäytäväksi listaksi.
Hyötykuorma sijaitsee muistissa heti otsakkeen jälkeen.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Yhden suuren vapaan lohkon alustaminen
Käynnistyksen yhteydessä koko pooli on yksi valtava vapaa lohko. Varausten yhteydessä jaamme sen osiin, ja vapautusten yhteydessä merkitsemme lohkot uudelleenkäytettäviksi.
Listan pää on tämä alkuperäinen lohko, joka kattaa koko arena-alueen.
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;
}First-fit-haku
Yksinkertaisin uudelleenkäyttöstrategia on first-fit: käy lista läpi ja palauta ensimmäinen riittävän suuri vapaa lohko. Se on nopea ja pitää pienet lohkot yleensä lähellä listan alkua.
Vaihtoehtoja ovat best-fit (pienin riittävä lohko) ja worst-fit, joissa nopeus vaihdetaan pirstoutumiskäyttäytymiseen.
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;
}Varaaminen vapaasta lohkosta
Kun löydämme sopivan lohkon, merkitsemme sen käytetyksi ja palautamme osoittimen heti sen otsakkeen jälkeen. Toistaiseksi luovutamme koko lohkon; jakaminen käsitellään seuraavassa oppitunnissa.
Palautettu osoitin on block + 1, joten otsake jää kutsujalta piiloon.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Lohkon vapauttaminen
Vapauttaaksesi lohkon siirry käyttäjän osoittimesta taaksepäin sen otsakkeeseen ja vaihda free-lipun arvo. Lohko voidaan nyt ottaa uudelleen käyttöön seuraavassa haussa.
Otsakkeen palauttaminen hyötykuormasta on sama yhden askeleen osoitintemppu, jonka näimme aiemmin.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Peräkkäisten vapaiden lohkojen yhdistäminen
Pelkkä vapauttaminen jättää poolin täyteen pieniä vapaita lohkoja. Yhdistäminen liittää vapautetun lohkon seuraavaan lohkoon, jos sekin on vapaa, ja muodostaa uudelleen suurempia yhtenäisiä alueita.
Tämä torjuu ulkoista pirstoutumista, joten tuleville suurille pyynnöille voidaan edelleen löytää tilaa.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Suoritettava vapaiden lohkojen listan esimerkki
Tämä kokonainen ohjelma alustaa poolin, varaa kaksi lohkoa, vapauttaa ensimmäisen ja käyttää sitä sitten uudelleen pienempään pyyntöön osoittaen, että vapaiden lohkojen lista toimii.
#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;
}Haun kustannus
Yksinkertainen linkitetty vapaiden lohkojen lista tekee varauksesta lohkojen määrään nähden O(n)-operaation. Monien varausten yhteydessä tämä hidastuu.
Oikeat varaajat käyttävät koon mukaan jaettuja vapaiden lohkojen listoja (kokoalueita) tai puita, jotta haku saadaan lähelle O(1):tä. Uudelleenkäytön periaate pysyy samana.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Kaksoisvapautus ja korruptio
Jos lohko merkitään vapaaksi kahdesti tai sen koon yli kirjoitetaan, viereiset otsakkeet korruptoituvat. Seuraava haku seuraa tällöin virheellistä next-osoitinta ja kaatuu.
Siksi muistivirheet ovat C:ssä niin vaarallisia: varaajan omat metatiedot sijaitsevat aivan omien tietojesi vieressä.
Uudelleenkäytön kokoaminen
Toimiva vapaiden lohkojen listaa käyttävä varaaja tarvitsee alustuksen, sopivan lohkon valintastrategian, varauksen, vapautuksen ja yhdistämisen. Näiden avulla muisti kiertää poolissa sen sijaan, että pooli kasvaisi loputtomasti.
Jäljelle jäävänä parannuksena on liian suurten lohkojen jakaminen ja kohdistuksen noudattaminen, joita käsitellään viimeisessä oppitunnissa.
Pikatarkistus
Mieti, mikä estää vapaiden lohkojen listaa pirstoutumasta pahasti.
Kertaus
Vapaiden lohkojen lista yhdistää lohkot otsakkeiden avulla, joten yksittäiset varaukset voidaan vapauttaa ja käyttää uudelleen. First-fit-haku löytää lohkon, vapauttaminen vaihtaa lipun arvon ja yhdistäminen liittää naapurilohkot yhteen pirstoutumisen torjumiseksi.
Lineaarinen haku on O(n); tuotantovaraajat ryhmittelevät lohkot koon mukaan nopeuden parantamiseksi. Seuraavaksi lisäämme jakamisen ja kohdistuksen.
Opi C tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 39
- Oppitunnit
- 144
Usein kysytyt kysymykset
Onko oppitunti ”Vapaat listat ja uudelleenkäyttö” ilmainen?
Kyllä – oppitunnin ”Vapaat listat ja uudelleenkäyttö” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko C Academy-kurssin, päivitä CoddyKit PROhon. C Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Vapaat listat ja uudelleenkäyttö”?
Seuratkaa ja kierrättäkää lohkoja. Harjoittelet C Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni C Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin C Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Vapaat listat ja uudelleenkäyttö”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä C Academy-oppitunnilla?
Kyllä. Jokainen C Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Miten malloc toimii
- Yksinkertainen bump-allokaattori
- Vapaat listat ja uudelleenkäyttö
- Kohdistus ja jakaminen