Co je seznam zdarma?
Volný seznam je datová struktura, která uchovává adresy umístění paměti počítače, které jsou k dispozici pro použití běžícím programem při použití dynamického přidělování paměti. Seznam se stává nezbytným, když program musí alokovat místo z oblasti volné paměti zvané halda. Implementace bezplatného seznamu může být jednoduchý propojený seznam nebo by mohla být složitější datovou strukturou, jako je Řadicí strom Většina jazykových programovacích jazyků na vysoké úrovni automaticky zpracovává seznam volných položek, což odstraňuje potřebu ruční správy.
Pokud program vyžaduje místo pro uložení informací během provádění programu, musí od základního operačního systému vyžadovat určité množství paměti. Umístění bloků paměti, které lze využít, jsou uloženy ve volné paměti seznam. Aby bylo přidělení úspěšné, musí být množství požadované paměti k dispozici v jednom nebo více z těchto bloků. Když je vrácen ukazatel na příslušné místo v paměti, tento prvek seznamu je odstraněn.
Poté, co je program hotový pomocí paměti, může jej delokovat, což zahrnuje předání ukazatele na blok paměti zpět do volného seznamu, kde bude k dispozici při příštím přidělení Je možné, že přidělení paměti selže, protože seznam je prázdný nebo protože neexistují žádné dostupné bloky paměti dostatečně velké pro splnění požadavku programu.
Nejjednodušší forma správy paměti se nazývá first fit systém. Tento systém udržuje jediný seznam volných paměťových míst. Když je odeslána žádost o paměť, seznam je procházen a první blok Pokud je blok větší než dvojnásobek požadované velikosti, je poloviční a nevyužitá polovina je přidána zpět do seznamu. Tato metoda obchoduje jednoduché kódování pro riziko fragmentace oblastí paměti, které by se do seznamu nikdy neměly vrátit.
Jiná forma správy paměti se nazývá systém přidělování kamarádů. Na rozdíl od prvního systému přizpůsobení si buddy přidělování udržuje několik volných seznamů, z nichž každý drží otevřené bloky pouze jedné konkrétní velikosti. To znamená, že po přijetí žádosti o přidělení je konzultován seznam, který obsahuje bloky, které jsou dostatečně velké, aby vyplnily požadavek, a vrátí se otevřené umístění. Pokud žádné volné bloky nejsou menší než dvojnásobek velikosti jsou k dispozici, větší blok je rozdělen na dva, aby splnil požadavky.
Termín „volný seznam“ se může vztahovat buď na jeden propojený seznam adres paměti, nebo může odkazovat na mnohem složitější typ datové struktury. Různé typy stromů řazení, pokud jsou udržovány jednoduché a vyvážené, může pomoci zvýšit rychlost hledání bloků otevřené paměti na úkor komplikace zdrojového kódu. Propojený seznam může být pomalejší než specializovaný strom řazení, ale vytváří programovací kód, který je mnohem snadněji čitelný, ladit a upravovat.
Některé programovací jazyky a operační systémy využívají speciální mechanismus nazývaný sběr odpadků. Jedná se o proces, který může pomoci převzít různé položky do volného seznamu a konsolidovat volné prostory tak, aby byly souvislé. účinek zabránění fragmentace a umožnění přidělení větších bloků paměti.