Kupac (memória)

A kupac ( eng.  heap ) a számítástechnikában és a programozásban egy olyan adatstruktúra  neve , amely dinamikusan lefoglalt alkalmazásmemóriát valósít meg .

Heap  mérete – az operációs rendszer (OS) által a kupac tárolására (a kupac alatt) lefoglalt memória mennyisége.

Hogyan működik

Amikor egy folyamat elindul , az operációs rendszer memóriát foglal le a kupac befogadására. A jövőben a kupac memóriája (a kupac alatt) dinamikusan lefoglalható.

A felhasználói program az olyan függvények segítségével, mint a , képes mutatókat szerezni a kupachoz tartozó memóriaterületekre. A programok a kupacot használják dinamikusan létrehozott adatstruktúrák tárolására. A program memóriát szabadíthat fel olyan funkciók használatával, mint a . malloc()free()

A kupacmemória felosztható használt (egy programhoz vagy hasonló funkciókat használó) és szabad (még nem foglalt vagy már felszabadult vagy hasonló funkciók használatával) szabadra. malloc()free()

Az információk tárolására arról, hogy a kupac melyik területe foglalt és melyik szabad, általában egy további memóriaterületet használnak.

A program indítása előtt a kupac inicializálása megtörténik, melynek során a kupac számára lefoglalt memória szabadnak lesz jelölve.

Egy ehhez hasonló függvény valami ilyesmit csinál: malloc()

• átnézi a kupacon lefoglalt használt/szabad memóriaterületek listáját, és keres egy megfelelő méretű szabad területet;
• szabad memória hiánya esetén további memóriát kérhet az operációs rendszertől;
• felveszi a talált területet a lakott területek listájára (vagy megjelöli a területet foglaltnak);
• visszaad egy mutatót a memóriaterület elejére;
• ha ilyen vagy olyan okból nem lehetett memóriát lefoglalni, hibát jelez (például visszatér ).malloc()NULL

Egy ehhez hasonló függvény valami ilyesmit csinál: free()

• átnézi a kupacon lefoglalt memória foglalt/szabad területek listáját, és megkeresi a megadott területet;
• eltávolítja a talált területet a foglalt memóriaterületek listájáról;
• hozzáadja a talált területet a szabad területek listájához (vagy szabadként jelöli meg).

A program biztos lehet benne, hogy az és a függvények hívásai között a foglaltként megjelölt memóriaterület nem kerül újrafoglalásra. Hívás vagy hasonló funkció után a memóriaterület felszabadul, és később újra felhasználható vagy átadható az operációs rendszernek. Ha egy felszabadult memóriaterületre mutató mutatót használ, a program összeomlik vagy kiszámíthatatlanul fut. malloc()free()free()

Algoritmusok és teljesítmény

A kupac egy összefüggő memóriaterület, amely különböző méretű foglalt és szabad területekre (blokkokra) van felosztva.

A kupac szabad és foglalt területeire vonatkozó információk különféle formátumú listákban tárolhatók. Az olyan funkciók teljesítménye, mint és közvetlenül függ a kiválasztott listaformátumtól , mivel ezek a funkciók az idejük nagy részét a megfelelő területek listájának keresésével töltik. malloc()free()

A kupac méretének növeléséhez és a hasonló funkciókhoz használjon rendszerhívást (az operációs rendszer függvényének hívását). Ebben az esetben kontextusváltás történik a felhasználói területről az operációs rendszer kernelterületére és fordítva. A használt/szabad kupacterületek listájában való keresés gyorsabb, mint a kontextusváltás, így kifizetődőbb egyszer egy rendszerhívással nagy memóriaterületet lefoglalni a kupac számára, majd a meglévő nagy területről kisebb területeket lefoglalni a program számára. a használt/szabad területek listájának vezetése. malloc()

A foglalt/szabad kupacterületek listájában szereplő elemek száma csökkenthető az egymást követő területekre vonatkozó információkat tartalmazó elemek összevonásával. Ez csökkenti a lista bejárási idejét.

A lista minden eleme tárolhatja egy memóriaterület címét, méretét, a következő (előre kereséshez) és/vagy az előző (fordított kereséshez) területre vonatkozó információkat.

Megvalósítási példa

Hozzon létre több listát, hogy információkat tároljon az azonos vagy hasonló méretű területekről. A terület mérete alapján listázza ki a kiválasztást.

Lásd még

• dinamikus memória
• NULLA

• malloc()
• ingyenes()