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

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.