Hromada (paměť)

Halda ( angl.  heap ) v informatice a programování  je název datové struktury , která implementuje dynamicky alokovanou aplikační paměť.

Velikost haldy  – množství paměti přidělené operačním systémem (OS) pro uložení haldy (pod haldu).

Jak to funguje

Když se proces spustí , operační systém přidělí paměť pro umístění haldy. V budoucnu může být paměť pro haldu (pod haldou) alokována dynamicky.

Uživatelský program pomocí funkcí jako , může získat ukazatele na oblasti paměti patřící do haldy. Programy používají haldu k hostování dynamicky vytvářených datových struktur. Program může uvolnit paměť pomocí funkcí jako . malloc()free()

Paměť haldy lze rozdělit na použitou (přidělenou programu pomocí nebo podobných funkcí) a volnou (dosud neobsazená nebo již uvolněná pomocí nebo podobných funkcí). malloc()free()

Pro uložení informací o tom, která oblast haldy je obsazená a která je volná, se obvykle používá další oblast paměti.

Před spuštěním programu je halda inicializována, během které je paměť alokovaná pro haldu označena jako volná.

Funkce jako tato dělá něco takového: malloc()

• prohlédne si seznam použitých/volných oblastí paměti přidělených na hromadě a hledá volnou oblast vhodné velikosti;
• v případě nedostatku volné paměti si může vyžádat další paměť z OS;
• přidá nalezenou oblast do seznamu obsazených oblastí (nebo označí oblast jako obsazenou);
• vrátí ukazatel na začátek oblasti paměti;
• pokud z toho či onoho důvodu nebylo možné alokovat paměť, hlásí chybu (například vrací ).malloc()NULL

Funkce jako tato dělá něco takového: free()

• prohledá seznam obsazených / volných oblastí paměti alokovaných na hromadě a hledá zadanou oblast;
• odstraní nalezenou oblast ze seznamu obsazených oblastí paměti;
• přidá nalezenou oblast do seznamu volných oblastí (nebo označí oblast jako volnou).

Program si může být jistý, že mezi voláními funkcí jako a nebude oblast paměti označená jako obsazená znovu alokována. Po volání nebo podobné funkci se paměťová oblast uvolní a může být později znovu použita nebo poskytnuta OS. Použití ukazatele na uvolněnou oblast paměti způsobí selhání nebo nepředvídatelné spuštění programu. malloc()free()free()

Algoritmy a výkon

Halda je souvislá oblast paměti rozdělená na obsazené a volné oblasti (bloky) různých velikostí.

Informace o volných a obsazených oblastech haldy mohou být uloženy v seznamech různých formátů. Výkon funkcí jako a přímo závisí na zvoleném formátu seznamu , protože tyto funkce tráví většinu času hledáním seznamu vhodných oblastí. malloc()free()

Chcete-li zvětšit velikost haldy a podobných funkcí, použijte systémové volání (volání funkce OS). V tomto případě dojde k přepnutí kontextu z uživatelského prostoru do prostoru jádra OS a naopak. Prohledávání seznamu použitých/volných oblastí haldy je rychlejší než přepínání kontextu, takže je výhodnější použít systémové volání jednou k přidělení velké oblasti paměti pro haldu a poté přidělit menší oblasti programu ze stávající velké oblasti. vedení seznamu využitých/volných ploch. malloc()

Počet prvků zahrnutých do seznamu obsazených/volných oblastí haldy lze snížit sloučením prvků obsahujících informace o po sobě jdoucích oblastech. Tím se zkrátí doba procházení seznamu.

Každý prvek seznamu může uložit adresu paměťové oblasti, její velikost, informace o následující (pro dopředné vyhledávání) a/nebo předchozí (pro zpětné vyhledávání) oblasti.

Příklad implementace

Vytvořte více seznamů pro ukládání informací o oblastech stejné nebo podobné velikosti. Výběr seznamu na základě velikosti oblasti.

Viz také

• dynamická paměť
• NULA

• malloc()
• volný, uvolnit()