5.4. Přidělování s omezenou velikostí bloku (buddy system)

Obsah

5.4.1. Binární přidělování
5.4.2. Fibonacciho přidělování

Tyto metody přidělování paměti jsou založeny na hierarchickém dělení volného paměťového prostoru na části. V nejjednodušším případě je paměťo rozdělena na dvě velké části, ty se dále dělí na menší části atd. Toto dělení paměti definuje omezující podmínky na to, kde jsou bloky paměti alokovány, jaká je jejich možná velikost a jak mohou být volné bloky znovu spojovány do větších celků. Pro každou možnou velikost bloku se udržuje samostatný seznam volných bloků, takže jde v podstatě o variantu přidělování výběrem nejlepšího vhodného bloku, i když s nejrůznějšími variacemi týkajícími se způsobu rozdělování a spojování bloků. Zásadou spojování bloků je, že se mohou spojit pouze ty bloky, které spolu sousedí na stejné úrovni hierarchie (buddies). Výsledný blok pak patří do bezprostředně vyšší úrovně hierarchie.

Cílem tohoto systému je, aby bylo možné při uvolnění bloku najít jeho souseda pouze jednoduchým adresovým výpočtem. Tímto sousedem může být buď celý volný blok, nebo blok, jenž je přidělen jako celek nebo je rozdělen na další bloky. Další výhodou je nízká paměťová režie, postačuje pouze jediný bit obsahující informaci o tom, zda je blok volný nebo ne. Žádné další ukazatele nebo pomocné informace nejsou potřeba. Cenou za tuto výhodu je, že při uvolňování bloku musíme znát jeho velikost - ta je však obvykle v typovaných jazycích známa.