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ę ${\displaystyle 2^{n}}$ blokami pamięci (wartość ${\displaystyle n}$ zależy od implementacji). Początkowo cała pamięć jest wolna, traktowana jako ciągły obszar o rozmiarze ${\displaystyle 2^{n}}$ 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 ${\displaystyle 2^{m}}$ (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.

• drzewo binarne

• 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.