Máme-li volné bloky paměti různé délky seřazené do seznamu, je třeba při požadavku na přidělení paměti určité velikosti vyhledat v seznamu dostatečně velký blok. Obecně může být takových bloků v seznamu více a je tedy třeba zvolit určitou strategii výběru nejvhodnějšího z nich. Vybraný blok je ze seznamu volných bloků odstraněn a je-li delší než je požadovaná velikost, vloží se přebytečná část zpět do seznamu jako další volný blok. Vzhledem k tomu, že pro uložení délky bloku a adresy následujícího bloku v seznamu je nutné rezervovat určitý prostor, nemá někdy vytvoření samostatného bloku z nevyužité části přidělované paměti smysl; v tomto případě je obvykle přidělen celý volný blok.

Metoda výběru prvního vhodného bloku jednoduše prochází seznam volných bloků a vybere z něj první blok, jehož velikost je větší nebo rovna požadované velikosti. Je-li blok delší, rozdělí se a zbývající část je vložena zpět do seznamu. To však vede k situaci, že dělením velkých bloků na začátku seznamu vznikne mnoho malých bloků, jejichž sekvenční procházení může podstatně zpomalit operaci přidělování paměti. Jedním z možných řešení je využití složitějších datových struktur pro ukládání volných bloků, např. stromů.

Při uvolňování paměti je třeba volný blok zařadit zpět do seznamu. Nejjednodušší a nejrychlejší metodou je zařazení volného bloku na začátek seznamu. Jinou variantou je zařazení do uspořádaného seznamu podle adres bloku - to zjednodušuje slévání sousedních volných bloků do větších souvislých bloků volné paměti, ovšem za cenu sekvenčního vyhledávání při uvolňování paměti. Tato varianta zajišťuje menší fragmentaci paměti a je nejčastějši používaná. Další možností je umístění volného bloku na konec seznamu.

Příklad 5.3. Přidělování paměti metodou first fit

Následující ukázka implementuje přidělování paměti výběrem prvního vhodného bloku. Blok paměti je vždy uvozen záhlavím obsahujícím velikost volného prostoru (bez záhlaví) a ukazatel na následující blok v seznamu. Tato informace představuje prostorovou režii uvedené implementace. Uvolněné bloky, případně nevyužité zbytky přidělovaných bloků, se ukládají na začátek seznamu. class FirstFitAllocator { // Záhlaví bloku paměti struct BlockHeader { unsigned size; // velikost bloku BlockHeader* next; // adresa následujícího bloku }; // Vytvoří objekt typu FirstFitAllocator, přidělující volnou paměť z bloku // na adrese memAddr o velikosti memSize public FirstFitAllocator(char* memAddr, unsigned memSize) { m_first = (BlockHeader*)memAddr; m_first->size = memSize - sizeof(BlockHeader); m_first->next = 0; } // Přidělí blok paměti o velikosti size a vrátí jeho adresu. // Není-li požadovaný prostor k dispozici, aktivuje výjimku NoMemoryException public char* alloc(unsigned size) { BlockHeader* prev = 0; BlockHeader* blk = m_first; while( blk ) { // není-li blok dostatečně velký, přejdeme na další if( blk->size < size ) { prev = blk; blk = blk->next; continue; } // vyřadíme blok ze seznamu if( prev ) prev->next = blk->next; else m_first = blk->next; // není-li zbytek dostatečně velký, vyrobíme z něj // nový blok a zařadíme na začátek seznamu if( blk->size >= size + sizeof(BlockHeader) ) BlockHeader* newBlk = (BlockHeader*)((char*)blk + size); newBlk->size = blk->size - size - sizeof(BlockHeader); newBlk->next = m_first; m_first = newblk; blk->size = size; } return (char*)blk + sizeof(BlockHeader); } // dostatečně velký blok se nenašel throw new NoMemoryException(); } // Uvolnění bloku paměti na adrese addr public void free(char* addr) { // blok přidáme na začátek seznamu BlockHeader* blk = addr - sizeof(BlockHeader); blk->next = m_first; m_first = blk; } // Adresa prvního volného bloku paměti protected BlockHeader* m_first; }

Modifikací metody je výběr dalšího volného bloku (next fit), kdy vyhledávání vhodného bloku začíná vždy na pozici, kde předchozí vyhledávání skončilo. Prohledávání tedy nezačíná vždy na stejném místě, ale postupně prochází celým seznamem, což zabrání hromadění menších bloků na začátku seznamu. Velkou nevýhodou této metody je však to, že bloky přidělované v téže fázi výpočtu mohou být od sebe značně vzdáleny, z čehož pak vyplývá menší lokalita odkazů a s ní spojený pomalejší přístup do paměti. Naopak bloky s různou dobou života mohou ležet vedle sebe, a to zase způsobuje větší fragmentaci paměti poté, co jsou bloky s kratší dobou života uvolněny. Celkově lze tedy říci, že i přes některé výhody vede výběr dalšího volného bloku k menší efektivitě přidělování paměti.

Implementujte třídu NextFitAllocator, která bude využívat metodu výběru dalšího volného bloku.

Upravte třídu FirstFitAllocator tak, aby se volné bloky zařazovaly do seznamu podle adresy bloku a zajistěte, aby se sousedící volné bloky vždy spojily do jednoho souvislého bloku volné paměti.