Algorytm bliźniaków

Algorytm bliźniaków (ang. buddy algorithm) – metoda alokacji pamięci, która charakteryzuje się dużą szybkością i łatwością implementacji oraz niską fragmentacją zewnętrzną, kosztem jednak znaczącej fragmentacji wewnętrznej. W algorytmie zarządza się blokami pamięci (wartość zależy od implementacji). Początkowo cała pamięć jest wolna, traktowana jako ciągły obszar o rozmiarze bloków. Gdy zachodzi potrzeba alokacji mniejszego obszaru, dokonywany jest rekurencyjny podział na dwie części wolnego obszaru aż do uzyskania najmniejszego fragmentu o rozmiarze (zawsze jest to potęga dwójki, co skutkuje dużą fragmentacją wewnętrzną). Dwa mniejsze obszary powstałe przy podziale są nazywane bliźniaczymi. Z kolei przy dealokacji pamięci można bardzo łatwo stwierdzić, czy wolny jest też obszar bliźniaczy i scalić je w jeden większy; scalanie ma również charakter rekurencyjny. Algorytm jest używany m.in. w jądrze systemu Linux do zarządzania stronami pamięci.