Algorytm bliźniaków
Algorytm bliźniaków (ang. buddy algorithm) to technika alokacji pamięci, która wyróżnia się dużą szybkością oraz prostotą implementacji, a także niską fragmentacją zewnętrzną. Jednakże, wiąże się to z istotną fragmentacją wewnętrzną.
W ramach tego algorytmu zarządza się blokami pamięci, których liczba wynosi
2n (gdzie n zależy od konkretnej implementacji). Na początku cały obszar pamięci jest dostępny, traktowany jako ciągły blok o rozmiarze 2n. W momencie, gdy występuje potrzeba alokacji mniejszego fragmentu, wykonywany jest rekurencyjny podział wolnego obszaru na dwie części, aż do uzyskania najmniejszego fragmentu o rozmiarze 2m (gdzie zawsze jest to potęga dwójki, co prowadzi do dużej fragmentacji wewnętrznej). Obszary powstałe w wyniku podziału nazywa się bliźniaczymi.
Podczas dealokacji pamięci można w prosty sposób sprawdzić, czy obszar bliźniaczy jest również wolny, co umożliwia ich scalanie w jeden większy blok; proces ten również ma charakter rekurencyjny.
Algorytm ten znajduje zastosowanie m.in. w jądrze systemu Linux do zarządzania stronami pamięci.
Zobacz też
- drzewo binarne
Bibliografia
System bloków bliźniaczych. W: Donald Ervin Knuth: Sztuka programowania. T. 1: Algorytmy podstawowe. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 460-462. ISBN 83-204-2540-9.
